一、實驗名稱：算法問題求解基礎
二、實驗目的
練習以下算法
1.歐幾裡得遞歸算法
2.歐幾裡得迭代算法
3.連續整數檢測算法
4.遞歸算法
三、實驗內容
第一部分 歐幾裡得算法求最大公約數
問題：
1. 計算：34931與 75236 的最大公約數：
1 #include<iostream.h>
2
3 //1.歐幾裡得遞歸算法
4 void Swap(int&a,int&b)
5 {
6 int c=a;a=b;b=c;
7 }
8
9 int RGcd(int m,int n)
10 {
11 if(m==0)
12 return n;
13 return RGcd(n%m,m);
14 }
15
16 int Gcd1(int m,int n)//對照程序1-1
17 {
18
19 if(m>n)
20 {
21 Swap(m,n);
22 }
23 return RGcd(m,n);
24 }
25
26
27 // 2.歐幾裡得迭代算法
28 int Gcd2(int m,int n)//對照程序1-2
29 {
30 if(m==0)
31 {
32 return n;
33 }
34 if(n==0)
35 {
36 return m;
37 }
38 if(m>n)
39 {
40 Swap(m,n);
41 }
42 while(m>0){
43 int c=n%m;n=m;m=c;
44 }
45 return n;
46 }
47
48 //3.連續整數檢測算法
49
50 int Gcd3(int m,int n)//對照程序1-3
51 {
52 //學生輸入程序部分
53 if(m==0) return n;
54 if(n==0) return m;
55 int t = m>n?n:m;
56 while(m%t || n%t) t--;
57 return t;
58 }
59 int main(int argc, char *argv[])
60 {
61 int m,n;
62 cout<<"---歐幾裡得算法求最大公約數---"<<endl;
63 cout<<"請輸入第一個數m：";
64 cin>>m;
65 cout<<"請輸入第二個數n：";
66 cin>>n;
67 int result;
68 result = Gcd1(m,n);
69 cout<<"Gcd1函數運算結果為："<<result<<endl;
70 result = Gcd2(m,n);
71 cout<<"Gcd2函數運算結果為："<<result<<endl;
72 result = Gcd3(m,n);
73 cout<<"Gcd3函數運算結果為："<<result<<endl;
74 }
2. 增加Gcd1、Gcd2、Gcd3中計算運算次數的語句，估算哪一個更快，最快與最慢相差多少倍。
第二部分 逆序輸出正整數序列
程序問題：
1. 輸入一個1234567890求逆序。
2. 輸入一個4294967296 求逆序。
1 #include <iostream.h>
2 //逆序輸出正整數序列
3
4 void PrintDigit(int n){
5 cout<< n%10;
6 if(n>=10){
7 PrintDigit(n/10);
8 }
9 }
10
11 int main(){
12 int n;
13 cin>>n;
14 PrintDigit(n);
15 }
第三部分 漢諾塔問題
程序問題：
1． 3個盤子的移動順序：
The disk
is moved from
to top of tower
The disk
is moved from
to top of tower
The disk
is moved from
to top of tower
The disk
is moved from
to top of tower
The disk
is moved from
to top of tower
The disk
is moved from
to top of tower
The disk
is moved from
to top of tower
2. 如果5個盤子移動，需要（ ）步完成。
1 #include <stdio.h>
2 //第一個塔為初始塔，中間的塔為借用塔，最後一個塔為目標塔
3 int i=1;//記錄步數
4 void move(int n,char from,char to) //將編號為n的盤子由from移動到to
5 {printf("第%d步:將%d號盤子%c---->%c\n",i++,n,from,to);
6 }
7 void hanoi(int n,char from,char denpend_on,char to)//將n個盤子由初始塔移動到目標塔(利用借用塔)
8 {
9 if (n==1)
10 move(1,from,to);//只有一個盤子是直接將初塔上的盤子移動到目的地
11 else
12 {
13 hanoi(n-1,from,to,denpend_on);//先將初始塔的前n-1個盤子借助目的塔移動到借用塔上
14 move(n,from,to); //將剩下的一個盤子移動到目的塔上
15 hanoi(n-1,denpend_on,from,to);//最後將借用塔上的n-1個盤子移動到目的塔上
16 }
17 }
18 int main()
19 {
20 printf("請輸入盤子的個數:\n");
21 int n;
22 scanf("%d",&n);
23 char x='A',y='B',z='C';
24 printf("盤子移動情況如下:\n");
25 hanoi(n,x,y,z);
26 }
四、實驗總結
