[Algorithm] Day.1 演算法基本介紹 Part.1

2023-03-05

#algorithm #note

最近開始在北科大的隨班附讀！發現上課之後如果不複習一下好像沒辦法，所以就決定把上課筆記整理起來，希望可以藉此更熟悉上課內容 XDD

1.1 什麼是演算法

演算法就是一個擁有特定目的並且有限步驟的指令集，通常會有以下幾個特性：

  1. 有 input 跟 output
  2. Definiteness：每一個指令都清楚且不模稜兩可
  3. Finitness：在有限的步驟內會跑完
  4. Effectiveness and Efficientness：有效且有效率

1.2.1 Pseudocode conventions

每個程式語言的使用人數都不一定，但每個程式語言都會需要面對演算法這個非常重要的主題，所以在演算法的課程裡面通常都會使用 Pseudocode（虛擬碼）來作為範例讓不論是使用什麼語言的人都可以不受程式語言限制的看懂演算法這堂課所表達的知識，而在讀者自己看懂這些的 Pseudocode 之後就可以很容易地轉換成自己習慣的程式語言並且加以運用。

1.2.2 Recursive algorithm 遞迴演算法

遞迴的概念跟我們解決問題的基本邏輯很像，就是把 大的問題轉化為數個小問題，之後再逐步解決這些問小問題。而遞迴演算法就是利用在演算法中呼叫自己來解決問題，這種演算法就被我們稱為 遞迴演算法。

河內塔

這是一個非常著名的遞迴演算法的例子，根據維基百科的就是

有三根杆子 X，Y，Z。X 杆上有 N 個 (N>1) 穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至 Y 杆：

  1. 每次只能移動一個圓盤；
  2. 大盤不能疊在小盤上面。

提示：可將圓盤臨時置於 Y 杆，也可將從 X 杆移出的圓盤重新移回 X 杆，但都必須遵循上述兩條規則。

問：如何移？

這個問題的解法如果利用遞迴演算法就會是

  Algorithm TowerOfHanoi(圓盤數量, 起始杆, 目標杆子, 剩餘第三根杆子) {
	  if(圓盤數量 >= 1) then {
      TowersOfHanoi(圓盤數量 - 1, 起始杆子, 剩餘第三根杆子, 目標杆子);
      write ("把", 起始杆子, 最上面的圓盤移動到" , 目標杆子 , "最上面");
      TowersOfHanoi(圓盤數量 - 1, 剩餘第三根竿子, 目標杆子, 起始杆子);
	  }
}

這個演算法的意思就是利用把 X 杆子的圓盤依序移動到 Z 竿子上，這樣 Z 杆子上就會有從小到大（從上到下）的圓盤，之後再用一樣的方式一個一個移動到 Y 杆子上就會完成題目的要求。

讓我們跟著這個演算法跑一次試試看三個圓盤的河內塔吧

1. 初始演算法，呼叫第1次 TowerOfHanoi(3, x, y, z)
2. 3 >= 1，if 判斷成立，所以呼叫 TowerOfHanoi(2, x, z, y)，我們稱這次為第2次河內塔
3. 在第2次河內塔當中，2 >= 1，if 判斷成立，所以呼叫 TowerOfHanoi(1, x, y, z)，我們稱這次為第3次河內塔
4. 在第3次河內塔當中，1 >= 1，if 判斷成立，所以呼叫 TowerOfHanoi(0, x, z, y)，我們稱這次為第4次河內塔
5. 在第4次河內塔當中，0 >= 1，if 判斷不成立，第4次河內塔結束
6. 第3次河內塔印出 `把 x 最上面的圓盤移動到 y 最上面`，此時 y 上面有小圓盤，x 上有中間以及大圓盤
7. 第3次河內塔呼叫 TowerOfHanoi(0, z, y, x)，我們稱為第五次河內塔
8. 在第5次河內塔當中，0 >= 1，if 判斷不成立，第5次河內塔結束
9. 第3次河內塔結束
10. 第2次河內塔印出 `把 x 最上面的圓盤移動到 z 最上面`，此時 z 上有中圓盤，y 上有小圓盤，而 x 上有大圓盤
11. 第2次河內塔呼叫 TowerOfHanoi(1, y, z, x)，我們稱為第6次河內塔
12. 在第6次河內塔當中，1 >= 1，if 判斷成立，所以呼叫 TowerOfHanoi(0, y, x, z)，我們稱這次為第7次河內塔
13. 在第7次河內塔當中，0 >= 1，if 判斷不成立，第7次河內塔結束
14. 第6次河內塔印出 `把 y 最上面的圓盤移動到 z 最上面`，此時 x 上有大圓盤，y 上沒有圓盤，z 上有小圓盤和中圓盤
15. 第6次河內塔呼叫 TowerOfHanoi(0, x, z, y)，我們稱為第八次河內塔
16. 在第8次河內塔當中，0 >= 1，if 判斷不成立，第8次河內塔結束
17. 第6次河內塔結束
18. 第2次河內塔結束
19. 第1次河內塔印出 `把 x 最上面的圓盤移動到 y 最上面`，此時 y 上面有大圓盤，z 上有小圓盤和中圓盤
20. 第1次河內塔呼叫 TowerOfHanoi(2, z, y, x)，我們稱為第9次河內塔
21. 第9次河內塔當中，2 >= 1，if 判斷成立，所以呼叫 TowerOfHanoi(1, z, x, y)，我們稱這次為第10次河內塔
22. 在第10次河內塔當中，1 >= 1，if 判斷成立，所以呼叫 TowerOfHanoi(0, z, y, x)，我們稱這次為第11次河內塔
23. 在第11次河內塔當中，0 >= 1，if 判斷不成立，第11次河內塔結束
24. 第10次河內塔印出 `把 z 最上面的圓盤移動到 x 最上面`，此時 y 上面有大圓盤，x 上有小圓盤，而 z 上有中圓盤
25. 第10次河內塔呼叫 TowerOfHanoi(0, y, x, z)，我們稱為第12次河內塔
26. 在第12次河內塔當中，0 >= 1，if 判斷不成立，第12次河內塔結束
27. 第10次河內塔結束
28. 第9次河內塔印出 `把 z 最上面的圓盤移動到 y 最上面`，此時 y 上面有中圓盤和大圓盤，x 上有小圓盤，而 z 上沒有圓盤
29. 第9次河內塔呼叫 TowerOfHanoi(1, x, y, z)，我們稱為第13次河內塔
30. 在第13次河內塔當中，1 >= 1，if 判斷成立，所以呼叫 TowerOfHanoi(0, x, z, y)，我們稱這次為第14次河內塔
31. 在第14次河內塔當中，0 >= 1，if 判斷不成立，第14次河內塔結束
32. 第13次河內塔印出 `把 x 最上面的圓盤移動到 y 最上面`，此時 x 和 z 上沒有圓盤，y 上面有小圓盤，中圓盤和大圓盤
33. 第13次河內塔呼叫 TowerOfHanoi(0, z, y, x)，我們稱為第15次河內塔
34. 在第15次河內塔當中，0 >= 1，if 判斷不成立，第15次河內塔結束
35. 第13次河內塔結束
36. 第9次河內塔結束
37. 第1次河內塔結束，演算法跑完，總共 7 步

印出結果：
把 x 最上面的圓盤移動到 y 最上面
把 x 最上面的圓盤移動到 z 最上面
把 y 最上面的圓盤移動到 z 最上面
把 x 最上面的圓盤移動到 y 最上面
把 z 最上面的圓盤移動到 x 最上面
把 z 最上面的圓盤移動到 y 最上面
把 x 最上面的圓盤移動到 y 最上面

在這一個短短的 pseudo code 裡面總共呼叫了 15 次 TowerOfHanoi 這個演算法，說真的像我這種第一次跑遞迴的人過程中跑錯很多次，但是這樣一步一步拆解確實可以把河內塔這個問題利用這個演算法拆成一塊一塊的，最後移動完成並且算出步數。

另外一個很有名的遞迴例子就是費氏數列，大家可以自己去找找看之後跑一遍結果哦！

參考資料:

上一篇：
[QA]Day.2 什麼是 End-to-End Test 下一篇：
[Algorithm] Day.2 演算法基本介紹 Part.2