遞迴演算法.

Presentation on theme: "遞迴演算法."— Presentation transcript:

1 遞迴演算法

2 遞迴演算法 程序呼叫 void tt() { } 程序呼叫時流程的轉換 SS(int data,int n) { }
void SS(int data[],int n) { } SS(int data,int n) 程序呼叫時流程的轉換

3 遞迴演算法 直接遞迴 (direct recursion)：當程序執行完成前呼叫了自己這個程序。 程序呼叫時流程的轉換 {
…void SS(int data[],int n) { } void SS(int data[],int n) { } SS(int data[],int n) 程序呼叫時流程的轉換

4 遞迴演算法 間接遞迴 (indirect recursion) ：在程序執行完成前呼叫了其它會再度引用到自己的程序。 程序呼叫時流程的轉換
void SS(int data[],int n) { yy() } void TT() { SS(int data[],int n) } void yy() { TT() } 程序呼叫時流程的轉換

5 遞迴演算法 在設計遞迴程式時，切記終結條件 (termination condition) 的設立，否則易造形成無窮迴圈 。
void RS() { RS(); } void RS() { RS(); } void RS() { RS(); } void RS() { RS(); }

6 計算階乘 階乘的計算即可用遞迴的概念詮釋，請看： 於是可以寫一個計算階乘的程序 F(int n)，
它接受傳入的整數 n，傳回 n*F(n-1) int F(int n) { if (n ==1) return 1; return n*F(n-1); }

7 遞迴練習 輸入正整數n，輸出費氏(Fibonacci)數列的第0個至第n個。
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

8 費氏(Fibonacci)數列 程式 #define ERROR -1 int Fib(int n) {
if (n<0) return ERROR; // n=0 if (n==0) return 0; // n=1 if (n==1) return 1; // n>=2 return Fib(n-1)+Fib(n-2); }

9 費氏(Fibonacci)數列 測試程式 #include <stdio.h>
#include <stdlib.h> int main() { int n, i; // Input a positive number printf("Input a positive integer:", n); scanf("%d",&n); // output Fibnacci number from 0 to n for (i=0; i<=n; i++) printf("Fib(%d)= %d \n", i, Fib(i)); // pause system("pause"); }

10 遞迴練習：河內塔遊戲 Hanoi Tower：十九世紀在歐洲的一個遊戲。有3根柱子， 及64個大小不同中間有洞的盤子，由上到下由小到大的置於第一根柱子裡。 現在要將這些盤子搬到第三根柱子，一樣由小到大的堆放在第三根柱子裡。 規則： 搬運的過程中，小盤子必須一直保持在大盤子的上面。 可以藉助第二根柱子來完成。

11 遞迴練習：河內塔遊戲 示範程式

12 產生排列 (Permutation)

13 排列(permutation) 1 12, 21 123, 132, 213, 231, 312, 321 4123, 4132, 4213, 4231, 4312, 4321 3124, 3142, 3214, 3241, 3412, 3421 2134, 2143, 2314, 2341, 2413, 2431 1234, 1243, 1324, 1342, 1423, 1432

14 排列(permutation) k n 1 2 3 4 1234, 1243, 1324, 1342, 1423, 1432 2134, 2143, 2314, 2341, 2413, 2431 3124, 3142, 3214, 3241, 3412, 3421 4123, 4132, 4213, 4231, 4312, 4321

15 產生排列演算法 void perm(char c[], int k, int n) { // 產生 c[k],...,c[n] 的所有排列
if (k == n) { // 終結條件成立時(只有1個字元)輸出此項排列 } else {// 讓c[k]固定不動，求 perm(c[],k+1,n) //讓c[k]~c[n]輪流當c[k] //產生 c[k+1],…,c[n]的所有排列 //還原 原字元順序

16 產生排列程式 void perm(char c[], int k, int n) { // 產生 c[k],...,c[n] 的所有排列
if (k == n) { //終結條件成立時(只有1個字元)輸出此項排列 for (int i = 0; i < n; i++) cout << c[i] << " "; cout << endl; } else { // 讓c[k]固定不動，求 perm(c[], k+1, n) for (i=k; i<n; i++) { //讓c[k]~c[n]輪流當c[k] swap(c[k], c[i]); //產生a[k+1],…,a[n]的所有排列 perm(c,k+1,n); //還原 字元順序

17 程式1-3 產生排列 void perm(char c[], int k, int n)
{ // 產生 c[k],...,c[n-1] 的所有排列 if (k == n-1) //終結條件成立時輸出此項排列 { for (int i = 0; i < n; i++) cout << c[i] << " "; cout << endl; } else // 讓c[k]固定不動，求 perm(c[], k+1, n) { for (i=k; i<n; i++){ //讓c[k]~c[n-1]輪流當c[k] char temp=c[k]; c[k]=c[i]; c[i]=temp; //產生a[k+1],…,a[n-1]的所有排列 perm(c,k+1,n); //還原原字元順序 temp=c[k]; c[k]=c[i]; c[i]=temp; } 程式1-3 產生排列

18 產生排列的測試程式 int main() { char a[] = {‘A', ‘B', ‘C', ‘D'};
A B D C A C B D A C D B A D C B A D B C B A C D B A D C B C A D B C D A B D C A B D A C C B A D C B D A C A B D C A D B C D A B C D B A D B C A D B A C D C B A D C A B D A C B D A B C 產生排列的測試程式 int main() { char a[] = {‘A', ‘B', ‘C', ‘D'}; cout << “A B C D 的排列：" << endl; perm(a, 0, 3); system(“pause”); return 0; }