# 資訊二乙_11027240_許展榮 DSNote1

## 單元1

* 遞迴:
思考核心:使問題越來越小(使用相同方法解決問題)
優點:寫程式快速,容易解釋,看懂
缺點:容易造成系統負擔
遞迴定義:
1.遞迴呼叫必須減小問題
2.完整的結束條件
3.確定每個問題都能終止

遞迴例子：
* 一元遞迴:
1.找第K小的數值(選出一點分堆,大的放左邊,小的放右邊,接下來只需要找其中一邊,結束條件:一點為第K小的數值)
2.河內塔(將小盤子搬到輔助的竿子上,將最大盤搬到另一根柱子,將小盤子搬到大盤上,結束條件:盤子為一個)
3.指數函數計算(用二分法計算較有效率,分成指數為奇或偶)
4.排列,組合方法
* 二元遞迴:(不一定會比一元遞迴快)
1.畫尺刻度(畫小一個長度的遞迴,畫自己長度的尺,畫小一個長度的遞迴,結束條件:長度為1)
2.費氏數列(會有算過的函式被重複呼叫,可以用空間換時間,將算過的函式存起來,就不須再算一次)

* 尾端遞迴:函式的最後一個指令是呼叫遞迴
可以直接改寫為迴圈的形式

* 心得:
遞迴之前有在CAL練習過,當時只是練習寫法
沒有很認真地去計算使用迴圈與遞迴的效率
或去想沒有被要求寫成遞迴的題目可否使用遞迴來寫(反之亦然)
本來雖然對遞迴不致陌生,但卻不知他真正的實作意義
看完影片之後,給予了我一種新的思考問題的方式(可能這應該是他本來應在CAL就達到的效果)
不過我在思考遞迴定義時很容易想得太過複雜
有些寫成多個case的地方其實都能用更簡短的方式合併
這個問題我可能要努力改

## 單元2
* 寫程式應該:
1.模組化
2.程式風格
3.有修改空間
4.容易使用
5.發生錯誤也保證安全
6.能debug
7.測試

* 物件導向(OOP)
運算合約:
1.目的 2.假設 3.輸入 4.輸出

* 資料抽象化(ADT): 優點:容易讀寫與修改
必須有描述與實作(隱藏資訊),限制程式對其直接存取(只能用給的operations)
設計ADT:1.屬性(想解決的問題屬性?) 2.運算(用怎麼樣的運算比較好?/需要甚麼樣的運算?)
1. 建構子(constructor):(可以不只一個,因應不同需求)
1.名子跟class的名子一樣
2.沒有return type
1. 解構子(destructor):(歸還記憶體,防止memory leak)
繼承(inherit):在class名稱後寫: public 你要繼承的class名稱
能繼承歸在public裡面的東西
ex: class ColoredSphere: public Sphere
ColoredSphere為Sphere的子類別(derived class)
1. 多載(overloading):
method名稱一樣但傳入參數資料型態(參數列)不同
1. 覆載(overriding):(繼承時才能使用)
method名稱和參數列跟父類別一樣(呼叫時依物件選擇method)
using namespace使用命名空間 使用範圍解析::去觸及裡面的東東
1. 命名空間 std : C++ Standard Library

1. exceptions(例外處理)也是一個class
try{ throw(type); } 發生問題時丟出例外(需限定例外規格)
catch(type x){} 接收例外嘗試修補(可以集中寫)
catch(type y){}
predecessor(前面一個)
successor(後面一個)

* 優解:
高內聚:盡可能地讓每個函式只做一件事情
低耦合:盡可能的減少傳入函式的參數

* 心得:
這章講了很多物件導向的概念,其中我沒有用過繼承,覆載和解構子所以不太熟
還有講了一些寫程式時應該注意的事以提升程式品質
現在打作業的時候我覺得我沒有用到物件導向的核心
就是從頭寫到尾,然後分幾個function
我覺得下個作業開始我可以練習先好好思考如何解決問題再開始打程式
(不然寫挑戰的時候不好修改,擴寫)

## 單元3
* 鏈結串列(Linked list):
優點:動態存取(不需要搬動資料,容易增減資料),資料可以不用在連續位置
缺點:必要花的空間較多(多了存指標的空間),拿取資料比較慢(需要走訪)
每個節點會有資料和next(指到下一個節點的位置,但最後一個要指到NULL)
基本功能:新增刪除(在頭會是special case),走訪
淺層複製(shallow copy):僅copy頭的位址(可存取同個linked list的資料)
深層複製(deep copy):複製整個鏈結串列(新的)
存檔:只存資料(走訪並逐一寫入,不必寫入指標)
重建:使用tail,每抓到一個資料就new一個新的節點並把資料寫入節點

* 變形:(可以實作在一起)
環狀鏈結串列(circular):在尾端指向head(能重複走訪)
dummy head node(在head前面新增一個無用節點,可以去除一些special case ex:新增,刪除)
雙向鏈結串列(doubly linked list):有指向前一個節點的指標(功能性好,但要花更多空間與時間維護)
*須更注意指標連結順序
用鏈接串列串鏈結串列

* 陣列版鏈結串列
有head和free(存放陣列中可以使用的空間,類似new配給的記憶體)
也有item和next(兩個值)

* 多項式的鏈結串列:(加法)
存係數和指數(還有next)
可以依兩個鏈結串列指數的大小( a>b, a==b, a<b )不同做不同的事
最後一邊為空時並把剩下的接完

* 指標:
(型別*) 變數名稱 宣告指標
&變數名稱 拿取位址
*指標 指標指的內容
指標 = new 型別 配置記憶體(如果沒有memory 會丟出exception)
不用時要delete(防止memory leak) (並通常會讓指標為NULL,防止動到不該動的地方)

* 動態陣列:
型別* 變數名稱 = new 變數名稱[arraysize] (指標會指向此陣列的頭)
指標名稱[k] 等同於 *(指標名稱+k)
變數名稱 = new 型別[x * arraysize] (要求更大空間)

* 心得:
指標的概念之前有學過,也在CAL練習過一些
本來我只有用過單向的鏈結串列,也聽過(但沒實做過)雙向的鏈結串列
也沒想過能用dommy head node這麼簡單的方式解決鏈結串列的special case
至於用鏈接串列存鏈接串列也有做過
當時只覺得很麻煩
現在可以多思考怎麼樣的資料結構更適合拿來解題(考慮方便性,效率等等)
還有以前寫的都是規模比較小的程式
所以沒有去做delete的動作,應該養成釋放記憶體的好習慣
也可以嘗試去思考能有怎麼樣的應用(或去查資料)

## 單元4
* 定義語言
x|y means x or y
xy means x followed by y

* C++ identifier grammer(不只有一個表示法)
<identifier> = <letter>|<identifier><letter>|<identifier><digit>
<letter> = a|b|...|z||A|B|...|Z|
<digit> = 0|1|...|9
(單一的letter為遞迴的base case)

例子:

* 回文定義
<pal> = empty string|<ch>|<ch><pal><ch>
<ch> = a|b|...|z|A|B|...|Z
<SU> = <L>|<D><SU><SU>
<L> = A|B
<D> = 1|2
包含三個字元的字串 : 1AA, 1AB, 1BA, 1BB, 2AA, 2AB, 2BA, 2BB
包含三個字元以上的字串: 11AAAA
至少一個字母組成的字串語言,第一個字母是大寫其餘則為小寫(用遞迴文法描述)
<SU> = <UA>|<SU><L>
<UA> = A|B|...|Z
<L> = a|b|...|z

* 運算式
前,中,後序運算式(依據運算子在運算元的哪裡)
後序式的優點:不用加上括號或定義沒有括號時的優先順序,只要從左到右依序計算
中序式轉(前)後序式:
完整加入括號並將運算子移到括號(左)右邊
後序式定義:
<postfix> = <identifier> | <postfix><postfix><operator>
<operator> = +|-|*|/
<identifier> = a|b|...|z

* 回朔(backtracking):
八皇后問題:
終止條件:填滿八個欄位
遞迴呼叫:填下一個欄位,如果填不了則回朔,嘗試下一種可能

* 航班問題:抵達目的地(起點到終點有無航班)
base case:起點(目前的點)等於終點
去每個相鄰且沒有走過的城市(確認有無航班以及重複的城市)

* 數學歸納法:
假設base case
假設在x=n對,證明在x=n+1也對(歸納)

* 心得:
這章對我來說滿難理解的
看完影片後發現可能是我在面對遞迴問題時的思考方式有根本上的問題
我在看可以使用遞會做的問題時也習慣從數據去尋找規律
但是這樣反而使我不容易去作規則的簡化,導致最後出來的程式很複雜
有失本來使用遞迴的意義
現在我知道想解決遞迴問題時應該從定義著手去思考程式寫法比較可能是更好的選擇