Download presentation
Presentation is loading. Please wait.
1
河內塔(Hanoi)問題
2
河內塔是由三根柱子，和n個不同直徑的圓盤所組成，它的遊戲方法是，將這n個圓盤由其一個柱子，全部搬至另一個柱子上，它的遊戲規則如下：
在搬動的過程中，直徑大的一定要在直徑小的圓盤下面。 一次只能搬動一個圓盤，且圓盤只能在這三個柱子之間移動，不得超出範圍。
3
演算法：虛擬碼 若有ｋ個圓盤，則圓盤移動的總次數為： 2k-1＋2k-2＋…＋2k-k＝2k－1
設三個木樁為a 、 b 、 c，數量為n，而函式則為Hanoi (n , a , b , c) 當N為1時表示只要再移動一次就完成工作，也就是只要把a移到c就完成工作。 當N不為1時，作2個動作 1.執行Hanoi(n-1,a,c,b) 2.執行Hanoi(n-1,b,a,c)
4
void Hanoi(int n , a, b,c) { if (n ==1) 列印 Move disk 1 form a to c; else Hanoi(n-1,a,b,c); 列印Move disk n form a to c; Hanoi(n-1,b,c,a)； 列印 Move disk 1~n-1 form b to c }
5
C語言：程式碼 #include <stdio.h> //#define SHOW_DETAILS
#ifdef SHOW_DETAILS int Max_Disks; #endif
6
void enter_recursion(int n, int from, int to, int middle)
{ #ifdef SHOW_DETAILS printf(">>進入第 %d 層遞迴深度: (n=%d, from=%d, to=%d, mid=%d)\n", Max_Disks - n, n, from, to, middle); #endif }
7
void leave_recursion(int n, int from, int to, int middle)
{ #ifdef SHOW_DETAILS printf("<<離開第 %d 層遞迴深度: (n=%d, from=%d, to=%d, mid=%d)\n", Max_Disks - n, n, from, to, middle); #endif }
8
void move_a_disk(int from, int to)
{ printf("從 %d 搬到 %d\n", from, to); } /* 從第 from 個柱子起，透過第 middle 個柱子當中介， 將 n 負碟子搬到第 to 個柱子上。*/
9
void hanoi(int n, int from, int to, int middle)
{ if (n <= 1) move_a_disk(from, to); else { /* 第一步驟 */ enter_recursion(n-1, from, middle, to); hanoi(n-1, from, middle, to); leave_recursion(n-1, from, middle, to);
10
/* 第二步驟 */ move_a_disk(from, to); /* 第三步驟 */ enter_recursion(n-1, middle, to, from); hanoi(n-1, middle, to, from); leave_recursion(n-1, middle, to, from); } } /* hanoi */
11
int main() { int number; printf("How many disks do you want to start with? "); scanf("%d", &number); if (number < 1) { printf("Sorry, the number must be greater than zero.\n"); return 1; } # ifdef SHOW_DETAILS Max_Disks = number; # endif printf("Now we're trying to move %d disks from 1 to 3...\n", number); hanoi(number, 1, 3, 2);
12
應用-老鼠迷宮
13
老鼠走迷宮是實驗心理學家常做的一項實驗，在這實驗中老鼠被置於一個無頂大盒子的入口處，盒子中利用牆將大部份移動去向阻隔起來，這樣科學家們就可以仔細觀察老鼠再迷宮中如何移動直到最後抵達另一端出口為止。從出口到入口只有一條路徑，而在最後出口處有一塊香甜的乳酪在等著。在這實驗中每當老鼠走錯路徑時就得重頭來，一直到它能正確無誤地一次走到出口為止，而這個實驗的次數也就代表老鼠學習的曲線。
14
老鼠走迷宮
15
二維陣列的宣告 struct offsets { short int vert; short int horiz; };
struct offsets move[4];
16
可移動的方向
17
佇列在電腦資料處理的應用
18
佇列在電腦資料處理的應用 佇列在電腦中的應用與堆疊不同，大多屬於硬體處理流程的控制。佇列具有先進先出的特性，經常被電腦的作業系統用來安排電腦執行工作 (job) 的優先順序。尤其是多人使用 (Multiuser) 之多工 (Multitask) 電腦必須安排每一位使用者都有相等的電腦使用權。為了公平起見，大都採先要求先服務之原則，而少數特權要求則用優先佇列來控制。 另一種應用我們稱之為Spooling，它是採用佇列的特性將磁碟當做資料輸入及輸出的緩衝區 (Buffer)，當資料輸入時先暫存於磁碟，再依序送入電腦處理。
19
事件驅動程式 (Event-driven Programs)
一般的資料處理模式多半是一種資料驅動 (data-driven) 的方式如下圖所示：
20
資料處理模式＝＞資料驅動 (data-driven) 之流程圖
21
資料處理模式 → 事件驅動 (event-driven) 之流程圖
22
程式佇列 (Process Queue) 所謂的程序 (processes) 指的是正在執行的程式。所謂的「多工」指的是電腦在一個時段內能夠同時執行多個程式。譬如：多工的作業系統 (如MS Windows 95、IBM OS/2) 能夠讓一個使用者同時編輯文書、編譯程式、和上網路抓取資料。如此一來，提高了使用者的工作效率。或者，多工的作業系統也可以提供許多使用者同時使用同一部電腦 (如UNIX) 使得電腦達到最大的使用效率。
23
資料處理模式 → Process Queue之流程圖
24
系統模擬 佇列在計算機科學中一個重要的應用就是系統模擬(System simulation)，它是用來建立真實世界狀況的模型，而由其中獲取知識，真實狀況下的每一事物和動作，在程式中都有對應的模擬項目。 高速公路的車輛數、時速、以及我們希望最小的延遲時間和達到最大流量，可以藉由系統模擬得出應該要提供多少線道，才能達到需求量。
Similar presentations
