程式设计与演算法-国立屏东大学资讯工程学系.PPT

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 想要帶女朋友到所有的橋上照相，但卻又不想重複經過同樣的橋/wiki/File:Konigsberg_bridges.pnghttp://www.contracosta.cc.ca.us/math/KBRIDG3.GIF/wiki/Seven_Bridges_of_K%C3%B6nigsberg * /wikipedia/commons/f/fe/Erdosnumber.png * /wikipedia/commons/f/fe/Erdosnumber.png * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * main() { int loop = 0, number = 0; int i, j, k; for (i = 0; i = 5; i++) for (j = 0; j = 10; j++) for (k = 0; k = 50; k+=5) { loop++; if (i*10 + j*5+ k == 50) { number++; break; } } printf(共%d種,執行迴圈%d次\n,number,loop); } 【執行結果】 共36種,執行迴圈491次 * 【方法-4】 　　當 i 和 j 之值固定後，k 之值只有唯一的選擇， 　　因此不必考慮 k 的變化情形。 　　i=0,j可能為 0,1,2,…,10 (50-i*10)/5=10 　　i=1,j可能為 0,1,2,…,8 (50-i*10)/5=8 　　i=2,j可能為 0,1,2,…,6 (50-i*10)/5=6 . . . 　　i=5,j可能為 0 (50-i*10)/5=0 　　執行迴圈次數 36 * main() { int loop = 0, number = 0; int i, j; for (i = 0; i = 5; i++) for (j = 0; j = (50-i*10)/5; j++) { loop++; number++; } printf(共%d種,執行迴圈%d次\n,number,loop); } 【執行結果】 共36種,執行迴圈36次 * 【方法-5】 　　由上一個方法知，當 i 的值固定後，j 的變化情形 　　只有 (50-i*10)/5 種，因此只需對 i 做迴圈。 　　執行迴圈次數 6 main() { int loop = 0, number = 0; int i; for (i = 0; i = 5; i++) { loop++; number += (50-i*10)/5 + 1; } printf(共%d種,執行迴圈%d次\n,number,loop); } 【執行結果】 共36種,執行迴圈6次 * 【方法-6】 　　我們計算的值其實是一個等差級數，即 　　11+9+7+…+1=6*(11+1)/2=36 　　將等差級數的公式寫成程式即可計算。 main() { int number = 0, a, b, n = 50; a = n / 5 + 1; if (a % 2 == 0) b = 2; else b = 1; number = (a+b)*((a-b)/2+1)/2; printf(共%d種\n, number); } 【執行結果】 共36種 * 生活上實際範例 * 路線規劃—最短路徑問題 公車、捷運 最短路徑 最短時間 前鎮高中 文化中心 大遠百 火車站 雄女 高鐵左營站 西子灣 10 20 15 8 10 10 20 10 20 30 15 * Google地圖路線規劃 * 環球旅遊與推銷員問題 平面上給予 n 個點，從某一點出發，經過每個點一次，再回到出發點，而其總長度為最短 Traveling Salesperson Problem (TSP) 此為 NP-complete 問題 * 尤拉的七橋問題 Eulers Konigsbergs (1255) Bridges Problem (1946, Kaliningrad) 一筆劃問題 A B C D