?

前言

　　校歷第五周，面向?qū)ο蟪绦蛟O計課程的第一單元告一段落。在第一單元的作業(yè)中，我們圍繞著“表達式求導”的題目展開，從第一次作業(yè)的最簡單的多項式求導，到第二次作業(yè)增加簡單的三角函數(shù)求導，再到第三次作業(yè)增加復合函數(shù)嵌套求導……難度是在不斷增加的，但是如果從一開始的第一次作業(yè)的設計就有著清晰的層次和邏輯，為后面的兩次作業(yè)留下擴展的空間，那么在后續(xù)的作業(yè)中可謂是事半功倍。但是想必大多數(shù)人拿到新作業(yè)都是要對代碼進行重構(gòu)的，包括我本人。

　　完成第一單元的三次作業(yè)，回過頭看，還是有很多值得分析和思考的地方的。這篇博客就將對本人在這三次作業(yè)中的代碼進行分析，并簡單給出自己的做題思路，若有不當之處，還請大家及時指出。

一、分析程序結(jié)構(gòu)

　　1. 第一次作業(yè)（簡單多項式求導）

　　在做第一次作業(yè)時，我還完全不理解面向?qū)ο笫鞘裁?#xff08;雖然現(xiàn)在也只是一知半解……）。但是為了避免“一main到底”的情況出現(xiàn)，我還是象征性的建了一個類。

　　在Exp這個類中，有很多對表達式進行操作的方法，如判斷合法，split分成一項一項，求導運算等等。以下是第一次作業(yè)的復雜度和行數(shù)統(tǒng)計。

　　由此得出在Exp.calculate()方法中的復雜度還是比較高的，也是后續(xù)可以優(yōu)化的一個方面。在本次作業(yè)中，最主要的思路是用每一項的正則表達式去匹配，匹配到之后用substring將匹配的字符串取出并對其用 * 和 ^ 進行split分割，然后用正常的多項式求導公式計算，并分情況輸出?；喴脖容^簡單，只需要考慮指數(shù)是否相同，若相同將系數(shù)相加即可。若想再提高性能分，可以將系數(shù)為正的項提到第一項（若有正項）。

　　2. 第二次作業(yè)（三角函數(shù)）

　　在做第二次作業(yè)的時候簡單分析了一下，和第一次作業(yè)沒有什么太大的不同，也就是新增添了三角函數(shù)。只需要改一下正則表達式，增添對sin(x)和cos(x)（可以帶指數(shù)）的判斷，然后設置四個Arraylist，每一個位置分別對應存儲該項的常數(shù)項系數(shù)、冪函數(shù)指數(shù)、sin的指數(shù)、cos的指數(shù)。然后用高中所學的求導方法對一般情況（a*x^b*sin(x)^c*cos(x)^d）進行求導，求出通式。化簡的話，合并同類項與第一次作業(yè)類似，并刪除常數(shù)項系數(shù) a=0 的項。

　　化簡的話，我主要針對可以把 (sin(x)^2+cos(x)^2) 提出來的情況進行化簡，也是求出通式并進行化簡。由于做了這一項操作，最后強測的性能分還不錯（雖然互測被找到了化簡bug……）。

　　由于沒有對第一次作業(yè)進行完全的重構(gòu)，所以第二次作業(yè)是在第一次作業(yè)的基礎上進行修改，也有點“一main到底”的意思。

　　下面是復雜度和行數(shù)統(tǒng)計。

　　由于化簡部分需要考慮的情況很多，因為是對兩個項進行操作，所以寫了一個雙重循環(huán)，復雜度比較高。

　　3. 第三次作業(yè)

　　第三次作業(yè)難度劇增，由于復合函數(shù)的引入，讓我們不得不采用遞歸的思路，并且也要應用繼承和接口，使我們的代碼更具有層次化，可讀性也會增強。

　　在思考如何判斷輸入合法時，我的思路是這樣的：

　　判斷輸入表達式合法 --> 判斷每一項合法?--> 判斷每一個因子合法

　　在本題中，我把因子分成了三類。第一類是常規(guī)因子（Normal Factor）：帶符號整數(shù)與冪函數(shù)；第二類是嵌套因子（Nest Factor），由于因子可以嵌套到三角函數(shù)中，所以最基本的三角函數(shù)也可以看成嵌套因子的一種；第三類是本次作業(yè)新增的表達式因子（Expression Factor），一個表達式外套了一層括號。

　　接著上述流程，判斷每一個因子合法 -->

• 若是常規(guī)因子，則正常判斷并返回。
• 若是嵌套因子，則嵌套的因子又可以分成上述三類，這時就要判斷因子是哪一類，再次進入判斷因子合法的階段，判斷三個因子的方法（函數(shù)）都要調(diào)用一遍，包括調(diào)用自身，也就是遞歸的思想。
• 若是表達式因子，則要調(diào)用最開始的“判斷輸入表達式合法”的方法（函數(shù))。

　　這種遞歸是十分容易理解且操作起來比較方便的，缺點就是有的時候可能會對遞歸結(jié)構(gòu)的理解思路突然不清晰，容易寫錯代碼；并且存儲成樹狀結(jié)構(gòu)也會有點困難，很難直觀理解；也不太容易化簡（其實遍歷子結(jié)點理論可行）。

　　以下是本次作業(yè)的具體層次，所有的類都是因子（Factor）的子類，其中Expression是用于處理數(shù)據(jù)的一個類。

　　在求導過程中，我會先判斷因子與因子之間的關系（對我自己存的樹的結(jié)構(gòu)進行完完全全的刨析，由于樹就比較亂，所以這部十分麻煩），相乘？或是嵌套？如果判斷出來是項和項的話，就直接相加輸出就好了。對于本思路的化簡，目前沒有一個特別好的方法，我的代碼只是對 1* ，0+，這一類可有可無的小尾巴進行刪除。

　　由于在判斷嵌套函數(shù)、求導、打印輸出都使用了遞歸思想，所以復雜度較高。

二、分析自己程序的bug

　　1. 第一次作業(yè)

　　在第一次作業(yè)的互測階段中，我被找出的bug為，如 x-x , 0*x^n 形式的，求導結(jié)果為0的情況，我的程序輸出無輸出。

　　針對這個bug的修復，我會先對已有的存放常數(shù)項系數(shù)的Arraylist進行遍歷判斷，如果均為0，則輸出也為0。

　　2. 第二次作業(yè)

　　在第二次作業(yè)的互測階段，我的bug出現(xiàn)在化簡 sin(x)^4 - cos(x)^4 這類的情況，我沒有判斷兩項的常數(shù)項系數(shù)和冪函數(shù)指數(shù)要分別相等，導致化簡錯誤。

　　針對該bug的修復，僅需要在化簡前增添if判斷條件。

　　3. 第三次作業(yè)

　　在第三次作業(yè)的互測階段，我對第一項前可以多添加的負號沒做處理，導致如同 -x+x 的情況會出錯。

　　針對該bug的修復，僅需要在第一項前判斷符號為負時，在表達式樹中的該層增添一個 -1 的因子與第一項相乘。

三、互測階段的策略

　　在互測階段，我首先是對一些邊界條件進行了測試。比如，長度很大的數(shù)據(jù)（爆棧），特殊字符如 \f\v 等，或者一個常數(shù)，等等。

　　在第一次和第二次的作業(yè)中都可以采用一個自動生成測試數(shù)據(jù)的文件，并采用.bat腳本和.py的程序?qū)Ψ块g內(nèi)的其余人的代碼運行和比對。

　　在第三次的作業(yè)中，生成測試數(shù)據(jù)變得有些困難，所以自己在本地輸入一些嵌套比較多，比較復雜，每一個因子都帶有指數(shù)（帶符號）的數(shù)據(jù)。

　　在前兩次的作業(yè)中，我會簡單的看一下房間內(nèi)其余人的正則表達式，和代碼的思路，如果發(fā)現(xiàn)可以錯誤就輸入數(shù)據(jù)測試；但是由于第三次的作業(yè)代碼量很大，思路也很復雜，所以我并沒有分析其余人的代碼，通過代碼找bug，而是輸入了一些自己在做作業(yè)時會犯一些錯誤的數(shù)據(jù)。

四、Applying Creational Pattern

　　在前兩次的作業(yè)中，創(chuàng)建對象都是通過簡單的自定義構(gòu)造函數(shù)模式，容易理解上手。

　　在第三次的作業(yè)中，為了處理復雜的邏輯關系，我在判斷表達式合法時，就將每一個因子（項）以工廠模式新建一個對象。在函數(shù)內(nèi)部顯式地創(chuàng)建了對象，并將該對象作為函數(shù)的返回值，插入到表達式樹中的一個節(jié)點，便于最后的求導運算。

轉(zhuǎn)載于:https://www.cnblogs.com/zja1999/p/10597851.html

總結(jié)

以上是生活随笔為你收集整理的2019_BUAAOO_第一单元总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。