---
# System prepended metadata

title: '10824349'

---

# 10824349
## 單元1:遞迴
### 遞迴:
遞迴的基本觀念就是希望將大問題化成小問題，不見得會比較快但程式碼會較精簡，是一種套公式的概念。
遞迴種類議題:
階乘、費氏數、兩數之最大公因數、二項是係數等，其他類議題也包含河內塔問題等。
### Base case:
決定基本情況，即為迴圈的終止條件。
### 遞迴的例子:
找第k小的數值-
以找尋樞紐的概念解決。
以未排序之陣列為例，選取頭的位置之值作為樞紐，大於他的放置在右邊，小於她的放置在左邊，重新呼叫遞迴。
費氏數列-
base case為F(1)、F(2)的時候，其餘回傳F(n-1)+F(n-2)之和，可以一陣列存入已出現過的值，在遞迴呼叫後先檢查是否有出現過，即可直接回傳，達到以空間換時間的目的。
河內塔-
需要傳遞的參數包含個數、起點、終點、和輔助，base case設定為個數為1時，呼叫遞迴時確定好起點和終點，程式碼的函式中，呼叫三次函式，第一次為移動最底下的以外的片，第二次為最底下，最後則為將其他移動至最底下上方疊起來。
## 單元2:抽象化
### 物件導向程式設計:
程式設計以類別(class)作為程式中的基本單元，將程式和資料封裝其中，類別定義了一件事物的抽象特點，包含了數據的形式以及對數據的操作。物件指的就是類別的實例。一個類別的屬性和方法則被稱為成員。
### 模組化:
目的是能讓程式切割成小塊，使其比較有系統、方便於管理程式，讓error的發生較少、減少重複性等。總結三項特點:較簡單於寫、讀、修改。幫助決定程式如何寫有兩項指標:內聚、耦合。
  內聚:盡量使得每個函示只做一件事情。
  耦合:函式互相傳遞的資料越少越好。
因此我們要盡量達到--高內聚、低耦合(每個函示只做一件事情且函式之間傳遞參數少量)。模組化也可說是功能性的抽象化(Functional abstraction)，將目的和如何使用模組先進行描述(specifiactions)，之後再進行實作(implementation)，當他人要使用你的程式時只需看懂你的描述，而無須看懂實作，從而能達成資訊隱藏的目的，讓你隱藏實作，方便自己修改實作。
### 資料抽象化:
為模組化的衍伸，主程式將資料丟給函式，無論如何修改函式內部都不會影響外部結果(前提是函式功能正常)，並且兩者之間只有一個進行傳遞的窗口，這樣做能方便寫程式的人在有更好的寫法時修改內部。以製冰機為例，顧客所看到的製冰機的外部面板就是所謂描述，而內部則是實作的部分。
### 類別的繼承:
在新創立的class後加:public  底線處為父類別(base class)的class名稱，即可創立一子類別(derived class)，能繼承父類別中的所有method和data member等。
### 多載:
同一class內，當想要使用同一功能之function但要傳遞之參數不同時，可使用相同名稱宣告函式，在進行實作時在說明不同參數之功能，呼叫函式時輸入哪個參數就會進入哪個函式，不會跑錯。
## 單元三:鏈結串列
### 鏈結串列:
如同用一繩子將一群資料綁起來一樣，資料將能沿著這條繩子連接在一起，我們只能存取頭部，其後的資料則要從頭部沿著繩子去尋找，若需要再此串列中新增或刪除資料，只需將新資料安插在兩筆資料中間連接繩子或將繩子剪斷接至後面即可，而使用鏈結串列需要先理解指標。
### 指標:
我們可將記憶體視為房子，要放的資料就是住進去的人，指標則是房子的門牌，指標是一種資料型態，可以只記錄該門牌號碼。而我們可以用new來申請一種變數型態的記憶體空間，使得指標可以存放該變數型態的資料，並且之後也可以退掉(delete)該記憶體空間(配合NULL將門牌清空)，這樣的方式我們稱為動態配置，可以自己管理、配置記憶體空間。
### 動態(配置)陣列:
在new的時候申請為陣列的變數型態，即可有更大的空間進行存放。
### 鏈結串列實作:
使用struct，內部宣告任何我們要存放的內容，並且使用指標的概念使得此struct可以指向另一個該struct型態的結構。
### 深層複製:
可以用來複製一鏈結串列，是一個constructor，傳入的參數為要複製的該object，語法:object(const object& 任意名稱):內部資料(任意名稱.內部資料){這部分為複製鏈結串列的程式碼。}