[記概筆記]Chapter 5: Algorithms

5-1

演算法的定義: An alogorithm is an order set of unambigious,executable steps  that defines aterminating process.

5-2

primitive:為演算法基本,基本通常包含2部分 syntax , semantics.

Pseudcode:假碼,使用假碼來解決問題,假碼為設想出來,有些就與程式的語法類似

                用方便了解跟規劃

Assignment 指派變數
Conditional selection 與if語法類似
Repeated execution 迴圈
 Procedure 與method語法同

5-3

Polya’s Problem Solving Steps

1. Understand the problem.
2. Devise a plan for solving the problem.
3. Carry out the plan.
4. Evaluate the solution for accuracy and its
potential as a tool for solving other problems.

 

解決問題:

1.stepwise refinement:先整看過,將問題分成幾個子問題,子問題比整個問題來的好解.
2.top-down:由上往下解決問題
3.botton-up:由下往上解決(以程式來說就如先將所需的METHOD做好)

5-4

迴圈

Pretest loop:while (condition) do(loop body)
Posttest loop:repeat (loop body)until(condition)

迴圈除了解決有規律的問題
也可用來search(這也是規律@@)
有氣泡式,Insertion sort,sequential search,binary search

5-5

遞回

程式來說就是由method再呼叫自己

*要有停止條件

5-6

演算法的效率
須以同狀態,同所有問題之下才能比較好壞

在p251的圖
適合來解資料少的問題

而p252的圖適合
資料多的問題

 

END.