递归解决八皇后以及汉诺塔迷宫源码
假设欲计算出13*4，则：
13 * 4 = 13 + ( 13 * 3 )
= 13 + ( 13 + ( 13 * 2 ) )
= 13 + ( 13 + ( 13 + ( 13 * 1 ) ) )
= 13 + ( 13 + ( 13 + 13 ) )
= 13 + ( 13 + 26 )
= 13 + 39
= 52
程序源代码：
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 /* =============== Program Description ===============*/ /* 程序名称： multiply.c*/ /* 程序目的：设计一个可计算两数相乘，但仅用加法运算，*/ /* 不使用乘法运算的程序。*/ /* Written By (WANT Studio.)*/
/* ==================================================*/
/* --------------------------------------------------- */ /* 递归乘法运算*/ /* --------------------------------------------------- */ int Multiply(int M,int N)
{
int Result; /*运算结果*/
if ( N == 1)
Result = M; /* 递归结束条件*/
Else
Result = M + Multiply(M,N-1); /* 递归执行部分 */
return Result;
}
/* --------------------------------------------------- */ /* 主程序*/ /* --------------------------------------------------- */ void main ()
{
int NumA; /* 乘数变量 */
int NumB; /* 被乘数变量*/
int Product; /* 乘积变量*/
printf("Please enter Number A:"); /* 输入乘数 */
scanf("%d",&NumA);
printf("Please enter Number B:"); /* 输入被乘数*/
scanf("%d",&NumB);
Product = multiply(NumA,NumB);
printf("%d * %d = %d",NumA,NumB,Product);
}
运行结果：
我们由题意可知每次执行的过程相似，唯一的不同点为其中一个传入参数，每次执行都递减。递归结束条件为当被乘数为1时返回乘数的值。否则继续调用程序并递减传入被乘数值。其结构如下：
int Multiply(int M,int N)
{
int Result;
if ( N == 1)
Result = M; /* 递归结束条件(Stopping Case) */ else
Result = M + Multiply(M,N-1); /* 递归执行部分(Recursive Step) */
return Result;
}
处理递归问题，常采用if语句来判断是否符合递归结束条件，其算法格式如下：
if (符合递归结束条件)then
返回答案
else
使用递归将程序分割为更简单的小程序。
在C语言中，我们采用堆栈这个数据结构来记录函数调用后的返回地址。例如有一个程序如下：
int ProcedureA () /* 子程序A */
{
…
ProcedureB(); /* 调用子程序B */
…/* 返回地址2 */
}
int ProcedureB() /* 子程序B */
{
…
}
void main () /* 主程序 */
{
…
ProcedureA(); /* 调用子程序A */
…/* 返回地址1 */
}
程序源代码：
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
/* =============== Program Description =============== */ /* 程序名称： reverse.c */ /* 程序目的： 运用递归设计一个将字符串反转的程序。 */ /* Written By . (WANT Studio.) */
/* =================================================== */
char String[30]; /* 声明字符串变量 */ int Length; /* 字符串长度变量 */
/* --------------------------------------------------- */ /* 递归字符串反转 */ /* --------------------------------------------------- */ void Reverse(int N) { if ( N < Length) { Reverse(N+1); /* 递归执行部分 */ printf("%c",String[N]); } }
/* --------------------------------------------------- */ /* 主程序
*/ /* --------------------------------------------------- */ void main () { printf("Please enter string : "); /* 输入原字符串 */ scanf("%s",&String); Length = strlen(String); /* 取得字符串长度 */ printf("The reverse string : "); Reverse(0); /* 调用递归函数 */ printf("\n"); }
运行结果：
程序源代码：
01 02 03 04 05 06 07
/* =============== Program Description =============== */ /* 程序名称： factor.c */ /* 程序目的： 运用递归设计一个做阶乘运算的程序。 */ /* Written By . (WANT Studio.) */
/* ============================================================*/
/* --------------------------------------------------- */
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 /* 递归阶层运算*/
/* --------------------------------------------------- */
int Factor(int N)
{
if ( N <= 1) /* 递归结束条件 */
return 1;
else
return N * Factor(N-1); /* 递归执行部分 */
}
/* --------------------------------------------------- */
/* 主程序*/
/* --------------------------------------------------- */
void main ()
{
int Number; /* 运算数值变量*/ int Factorial; /* 阶乘数值变量*/
printf("Please enter a number : "); /* 输入数值*/ scanf("%d",&Number);
Factorial = Factor(Number); /* 调用递归函式*/ printf("%d! = %d\n",Number,Factorial); /* 输出运算结果*/ }
运行结果：
程序源代码：
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22 /* =============== Program Description ===============*/ /* 程序名称： gcd.c*/ /* 程序目的：运用递归设计一个求两数之最大公因子的程序*/ /* Written By. (WANT Studio.)*/
/* ===================================================*/
/* --------------------------------------------------- */ /* 递归求最大公因子*/ /* --------------------------------------------------- */ int GCD(int M,int N)
{
if (N == 0) /* 递归结束条件 */
return M;
else
return GCD(N,M % N); /* 递归执行部分 */
}
/* --------------------------------------------------- */ /* 主程序*/ /* --------------------------------------------------- */ void main ()
{
23 24 25 26 27 28 29 30 31 32 33 34 35
int NumberA; /* 运算数值变量 */ int NumberB; /* 运算数值变量 */ int
Result;
/* 运算结果变量 */
printf("The Great Common Divisor of Number A, Number B\n"); printf("Please enter number A : "); /* 输入数值 */ scanf("%d",&NumberA);
printf("Please enter number B : "); /* 输入数值 */ scanf("%d",&NumberB);
Result = GCD(NumberA,NumberB); /* 调用递归函式 */
printf("GCD(%d,%d) = %d\n",NumberA,NumberB,Result);
}
运行结果：
程序源代码：
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
/* =============== Program Description =============== */ /* 程序名称： fib.c */ /* 程序目的： 运用递归设计一个求费氏级数的程序。 */ /* Written . (WANT Studio.) */
/* =================================================== */
/* --------------------------------------------------- */ /* 递归求费氏级数 */ /* --------------------------------------------------- */ int Fib(int N) { if (N <= 1) /* 递归结束条件 */ return N; else return Fib(N-1) + Fib(N-2); /* 递归执行部分 */ }
/* --------------------------------------------------- */ /* 主程序 */ /* --------------------------------------------------- */ void main () { int Number; /* 运算数值变量 */ int Result; /* 运算结果变量 */ printf("The Fibonacci Numbers \n"); printf("Please enter a number : "); /* 输入数值 */ scanf("%d",&Number); Result = Fib(Number); /* 调用递归函式 */
31
32
printf("Fibonacci Numbers of %d = %d\n",Number,Result); }
运行结果：
程序源代码：
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 /* =============== Program Description ===============*/
/* 程序名称： comb.c*/
/* 程序目的：运用递归设计一个求组合公式的程序。*/
/* Written By . (WANT Studio.)*/
/* ===================================================*/
/* --------------------------------------------------- */
/* 递归求组合公式*/
/* --------------------------------------------------- */
int Comb(int N,int M)
{
if ( (N == M) || (M == 0) ) /* 递归结束条件 */
return 1;
else /* 递归执行部分 */
return Comb(N-1,M) + Comb(N-1,M-1);
}
/* --------------------------------------------------- */
/* 主程序*/
/* --------------------------------------------------- */
void main ()
{
int NumberN; /* 运算数值变量*/
int NumberM; /* 运算数值变量*/
int Result; /* 运算结果变量 */
printf("The Combination Number of two Numbers.\n");
printf("Please enter number N: "); /* 输入数值 */
scanf("%d",&NumberN);
printf("Please enter number M: "); /* 输入数值 */
scanf("%d",&NumberM);
if (NumberN >= NumberM)
{
Result = Comb(NumberN,NumberM); /* 调用递归函式*/ printf("Comb(%d,%d) = %d\n",NumberN,NumberM,Result);
}
else
printf("Error: N < M !!\n");
}
运行结果：程序源代码：
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 /* =============== Program Description ===============*/
/* 程序名称： hanoi.c*/
/* 程序目的：运用递归来解汉诺塔问题。*/
/* Written By . (WANT Studio.)*/
/* ===================================================*/
#include
int Counter; /* 计数器变量*/
/* --------------------------------------------------- */
/* 递归解汉诺塔问题*/
/* --------------------------------------------------- */
int Hanoi(char From,char To,char Auxiliary,int N)
{
if ( N == 1 ) /* 递归结束条件 */
{
Counter++; /* 计数器递增*/
printf("Step %d : ",Counter);
printf("Move disk 1 from peg-%c to peg-%c.\n",From,To);
}
else /* 递归执行部分 */
{
/* 将目的桩和辅助桩交换*/
Hanoi(From,Auxiliary,To,N-1);
Counter++; /* 计数器递增*/
printf("Step %d : ",Counter);
printf("Move disk %d from peg-%c to peg-%c.\n",N,From,To);
/* 将来源桩和辅助桩交换*/
Hanoi(Auxiliary,To,From,N-1);
}
}
/* --------------------------------------------------- */
/* 主程序*/
/* --------------------------------------------------- */
void main ()
{
int Number; /* 铁盘数目变量*/
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
char Source;
char Destination;
char Auxiliary;
Counter = 0;
printf("The Tower of Hanoi program.\n");
printf("Please enter the number of disks : ");
scanf("%d",&Number); /* 输入铁盘数*/
printf("The Source peg : ");
Source = getche(); /* 输入来源桩*/
printf("\nThe Auxiliary : ");
Auxiliary = getche(); /* 输入辅助桩*/
printf("\nThe Destination : ");
Destination = getche(); /* 输入目的桩*/
printf("\n");
Hanoi(Source,Destination,Auxiliary,Number); /* 调用递归函数*/ }
运行结果：
程序源代码：
01
02
03
04
05
06
07
08 /* =============== Program Description =============== */ /* 程序名称： queen.c*/ /* 程序目的：运用递归来解N皇后问题 */ /* Written . (WANT Studio.)*/
/* ===================================================*/ char Chessboard[8][8]; /* 声明8*8的空白棋盘*/
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69 /* ---------------------------------------------------*/
/* 递归解N皇后问题*/
/* ---------------------------------------------------*/
int N_Queens(int LocX,int LocY,int Queens)
{
int i,j; /* 循环计数变量*/
int Result=0;
if ( Queens == 8 ) /* 递归结束条件 */
return 1;
else /* 递归执行部分 */
if ( QueenPlace(LocX,LocY) )
{
Chessboard[LocX][LocY] = 'Q';
for (i=0;i<8;i++)
for (j=0;j<8;j++)
{
Result += N_Queens(i,j,Queens+1);
if (Result > 0)
break;
}
if (Result > 0)
return 1;
else
{
Chessboard[LocX][LocY] = 'X';
Return 0;
}
}
else
return 0;
}
/* --------------------------------------------------- */
/* 判断传入坐标是否可放置皇后*/
/* --------------------------------------------------- */
int QueenPlace(int LocX,int LocY)
{
int i,j;
if (Chessboard[LocX][LocY] != 'X') /* 判断是否有皇后*/ return 0;
for (j=LocY-1;j>=0;j--) /* 判断上方是否有皇后*/ if (Chessboard[LocX][j] != 'X')
return 0;
for (j=LocY+1;j<8;j++) /* 判断下方是否有皇后*/ if (Chessboard[LocX][j] != 'X')
return 0;
for (i=LocX-1;i>=0;i--) /* 判断左方是否有皇后*/ if (Chessboard[i][LocY] != 'X')
return 0;
for (i=LocX+1;i<8;i++) /* 判断右方是否有皇后*/ if (Chessboard[i][LocY] != 'X')
return 0;
i = LocX - 1;
j = LocY - 1;
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
while ( i>=0 && j>=0 ) /* 判断左上方是否有皇后*/ if (Chessboard[i--][j--] != 'X')
return 0;
i = LocX + 1;
j = LocY - 1;
while ( i<8 && j>=0 ) /* 判断右上方是否有皇后*/ if (Chessboard[i++][j--] != 'X')
return 0;
i = LocX - 1;
j = LocY + 1;
while ( i>=0 && j<8 ) /* 判断左下方是否有皇后*/ if (Chessboard[i--][j++] != 'X')
return 0;
i = LocX + 1;
j = LocY + 1;
while ( i<8 && j<8 ) /* 判断右下方是否有皇后*/ if (Chessboard[i++][j++] != 'X')
return 0;
return 1;
}
/* --------------------------------------------------- */
/* 主程序*/
/* --------------------------------------------------- */
void main ()
{
int i,j; /* 循环计数变量*/
for (i=0;i<8;i++)
for (j=0;j<8;j++)
Chessboard[i][j] = 'X';
N_Queens(0,0,0);
printf("The graph of 8 Queens on the Chessboard.\n");
printf(" 0 1 2 3 4 5 6 7 \n");
printf(" +---+---+---+---+---+---+---+---+\n");
for (i=0;i<8;i++)
{
printf(" %d |",i);
for (j=0;j<8;j++)
printf("-%c-|",Chessboard[i][j]);
printf("\n +---+---+---+---+---+---+---+---+\n");
}
}
运行结果：
程序源代码：
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 /* =============== Program Description ===============*/ /* 程序名称： maze.c*/ /* 程序目的：运用递归来解迷宫问题*/ /* Written B. (WANT Studio.)*/
/* ===================================================*/
int Maze[8][7] = { /* 声明5*4的迷宫，外围不可走 */ 1, 1, 1, 1, 1, 1, 1,
1, 0, 1, 0, 0, 0, 1,
1, 1, 0, 1, 1, 0, 1,
1, 1, 0, 1, 1, 0, 1,
1, 1, 1, 0, 1, 1, 1,
1, 0, 0, 1, 0, 1, 1,
1, 1, 1, 1, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1};
/* --------------------------------------------------- */ /* 递归解迷宫问题*/ /* --------------------------------------------------- */ int Way(int LocX,int LocY)
{
if ( Maze[6][5] == 2 ) /* 递归结束条件 */
return 1;
else /* 递归执行部分 */
if ( Maze[LocY][LocX] == 0 )
{
Maze[LocY][LocX] = 2;
if ( Way(LocX,LocY-1) )
return 1;
else if ( Way(LocX+1,LocY-1) )
return 1;
else if ( Way(LocX+1,LocY) )
return 1;
else if ( Way(LocX+1,LocY+1) )
return 1;
else if ( Way(LocX,LocY+1) )
return 1;
else if ( Way(LocX-1,LocY+1) )
return 1;
else if ( Way(LocX-1,LocY) )
return 1;
else if ( Way(LocX-1,LocY-1) )
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
return 1;
else
{
Maze[LocY][LocX] = 3;
return 0;
}
}
else
return 0;
}
/* --------------------------------------------------- */ /* 主程序*/ /* --------------------------------------------------- */ void main ()
{
int i,j; /* 循环计数变量*/
printf("==Problem of Maze ==\n");
printf("The Maze source is (1,1).\n");
printf("The Maze Destination is (6,5).\n");
Way(1,1);
printf("The graph of Maze.\n");
printf(" 0 1 2 3 4 5 6 \n");
printf(" +---+---+---+---+---+---+---+\n");
for (i=0;i<8;i++)
{
printf(" %d |",i);
for (j=0;j<7;j++)
printf("-%d-|",Maze[i][j]);
printf("\n +---+---+---+---+---+---+---+\n");
}
}
运行结果：
4. 有一个递归程序如下：
int fact(int N)
{
if (n<=0)
return 1;
else
return N * fact(N-1);
}
5. 有一个递归程序如下：
int X(int N)
{
if (N <= 3)
return 1;
else
return X(N-2) + X(N-4) + 1;
}
7. 有一个递归程序如下：
int maze(int a,int b,int c)
{
if (a return a; else return c*maze(a/b,b,c) + (a % b); } 3. 假设有一数学函数如下： A(m,n) = n+1, m=0 A(m,n) = A(m-1,1), m!=0 and n=0 A(m,n) = A(m-1,A(m,n-1)), otherwise 工学院 数据结构课程设计报告设计题目：八皇后 2008 年 6 月25 日 设计任务书 摘要： 八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．使用递归方法最终将其问题变得一目了然，更加易懂。 关键词：八皇后; c++; 递归法 目录 1. 课题综述 (1) 1.1课题的来源及意义 (1) 1.2面对的问题 (1) 2. 需求分析 (1) 2.1涉及到的知识 (2) 2.2软硬件的需求 (2) 2.3功能需求 (2) 3. 概要设计 (2) 4. 详细设计和实现 (3) 4.1算法描述及详细流程图 (3) 4.1.1算法描述 (3) 4.1.2算法流程图 (3) 5. 代码编写及详细注释 (4) 6. 程序调试 (8) 6.1调试过程、步骤及遇到的问题 (8) 7. 运行与测试 (8) 7.1运行演示 (8) 总结 (10) 致 (11) 参考文献 (12) . 1. 课题综述 1. 1课题的来源及意义 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。 在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。 到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。 1. 2 面对的问题 1）解决冲突问题： 这个问题包括了行，列，两条对角线； 列：规定每一列放一个皇后，不会造成列上的冲突； 行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态； 2）使用数据结构的知识，用递归法解决问题。 2. 需求分析 递归算法与递归程序 岳西中学：崔世义一、教学目标 1知识与技能 (1) ?认识递归现象。 (2) ?使用递归算法解决冋题往往能使算法的描述乘法而易于表达 (3) ?理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。 (4) ?认识递归算法往往不是咼效的算法。 (5) ? 了解递归现象的规律。 (6) ?能够设计递归程序解决适用于递归解决的问题。 (7) ?能够根据算法写出递归程序。 (8) ? 了解生活中的递归现象，领悟递归现象的既有重复，又有变化的特点，并且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2) 和练习(3)这两道题目的形式相差很远，但方法和答案却是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出递归算法的特点，以及递归算法解答某些实践问题通常得很简洁，从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 (1) 了解递归现象和递归算法的特点。 (2) 能够根据问题设计出恰当的递归程序。 2、教学难点 (1) 递归过程思路的建立。 (2) 判断冋题是否适于递归解法。 (3) 正确写出递归程序。 三、教学环境 1、教材处理 教材选自《浙江省普通高中信息技术选修：算法与程序设计》第五章，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自 定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习⑵ 和练习 // test_project.cpp : 定义控制台应用程序的入口点。//汉诺塔问题的 // //递归实现 /*#include "stdafx.h" #include { count++; cout<<"第"< /*后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放A B C； 若n为奇数，按顺时针方向依次摆放A C B。 （）按顺时针方向把圆盘从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘在柱子A，则把它移动到B；若圆盘在柱子B，则把它移动到C；若圆盘在柱子C，则把它移动到A。 （）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。 （）反复进行（）（）操作，最后就能按规定完成汉诺塔的移动。 所以结果非常简单，就是按照移动规则向一个方向移动金片： 如阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C 汉诺塔问题也是程序设计中的经典递归问题，下面我们将给出递归和非递归的不同实现源代码。*/ /*#include "stdafx.h" #include 一、教学思想（包括教学背景、教学目标） 1、教学背景 本课程“递归算法”，属于《数据结构与算法》课程中“栈和队列”章节的重点和难点。数据结构与算法已经广泛应用于各行各业的数据存储和信息处理中，与人们的社会生活密不可分。该课程是计算机类相关专业核心骨干课程，处于计算机学科的核心地位，具有承上启下的作用。不仅成为全国高校计算机类硕士研究生入学的统考科目，还是各企业招聘信息类员工入职笔试的必考科目。数据结构与算法课程面向计算机科学与技术、软件工程等计算机类学生，属于专业基础课。 2、教学大纲 通过本课程的学习，主要培养学生以下几个方面的能力： 1）理解递归的算法； 2）掌握递归算法的实现要素； 3）掌握数值与非数值型递归的实现方法。 根据学生在学习基础和能力方面的差异性，将整个课程教学目标分成三个水平：合格水平（符合课标的最低要求），中等以上水平（符合课标的基本要求），优秀水平（符合或超出课标提出的最高要求）。具体如下表： 二、课程设计思路（包括教学方法、手段） “递归算法”课程以故事引入、案例驱动法、示范模仿、启发式等多元化教学方法，设计课程内容。具体的课堂内容如下所示： 1 1 2 3 3 7 4 15 5 31 count = 2n-1 思考：若移动速度为1个/秒，则需要 (264-1)/365/24/3600 >= 5849亿年。 四、总结和思考 总结： 对于阶乘这类数值型问题，可以表达成数学公式，然后从相应的公式入手推导，解决这类问题的递归定义，同时确定这个问题的边界条件，找到结束递归的条件。 对于汉诺塔这类非数值型问题，虽然很难找到数学公式表达，但可将问题进行分解，问题规模逐渐缩小，直至最小规模有直接解。 思考： 数值型问题：斐波那契数列的递归设计。 非数值型问题：八皇后问题的递归设计。阐述总结知识拓展 三、教学特色（总结教学特色和效果） 递归算法课程主要讨论递归设计的思想和实现。从阶乘实例入手，由浅入深，层层深入介绍了递归的设计要点和算法的实现。从汉诺塔问题，通过“边提问，边思考”的方式逐层深入地给出算法的分析和设计过程。通过故事引入、案例导入、实例演示、PPT展示、实现效果等“多元化教学方式”，努力扩展课堂教学主战场。加上逐步引导、问题驱动，启发学生对算法的理解，并用实例演示展示算法的分析过程，在编译环境下实现该算法，加深对算法实现过程的认识。 1、知识点的引入使用故事诱导法讲授 通过“老和尚讲故事”引入函数的递归调用，并通过“世界末日问题” 故事引入非数值型问题的递归分析，激发学习积极性，挖掘学生潜能。 其实，求解迷宫问题的最好思想是递归，下面通过递归实现求解迷宫内所有的路径。实验代码为： #include"stdafx.h" #include"example35_maze.h" int maze[9][9]={ 1,1,1,1,1,1,1,1,1, 1,0,0,0,0,0,0,0,1, 1,0,1,1,0,1,1,0,1, 1,0,1,0,0,1,0,0,1, 1,0,1,0,1,0,1,0,1, 1,0,0,0,0,0,1,0,1, 1,1,0,1,1,0,1,1,1, 1,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1 }; void printmaze() { int i,j; for(i=0;i<9;i++) { for(j=0;j<9;j++) { if(maze[i][j] == 1) cout<<"*"; else if(maze[i][j]== -1) cout<<"o"; else cout<<" "; } cout< if(maze[x][y+1]==0) pass(x,y+1); if(maze[x+1][y]==0) pass(x+1,y); if(maze[x-1][y]==0) pass(x-1,y); if(maze[x][y-1]==0) pass(x,y-1); maze[x][y]=0; } int main(void) { int Inx=1,Iny=1; cout<<"the maze information is: "< 汉诺塔非递归算法C语言实现 #include 课程设计报告 课题名称：迷宫问题的求解及演示姓名： 学号： 专业：计算机与信息学院 班级： 指导教师： 数据结构课程设计任务书针对本课程设计，完成以下课程设计任务书： 1.熟悉系统实现工具和上机环境。 2.根据课程设计任务，查阅相关资料。 3.针对所选课题完成以下工作： （1）需求分析 （2）概要设计 （3）详细设计 （4）编写源程序 （5）静态走查程序和上机调试程序 4.书写上述文档和撰写课程设计报告 目录 第一部分课程设计任务书 (1) 第二部分课程设计报告 (2) 第一章课程设计内容和要求 (4) 2.1 问题描述 (4) 2.2 需求分析 (4) 第二章课程设计总体方案及分析 (4) 3.1 概要设计 (7) 3.2 详细设计 (7) 3.3 调试分析 (10) 3.4 测试结果 (10) 第三章设计总结 (13) 4.1课程设计总结 (13) 4.2参考文献………………………………………………… 4.3 附录(源代码) (14) 第二部分课程设计报告 第一章课程设计内容和要求 2.1问题描述： 迷宫以16*16的矩阵存储在数据文件中（迷宫中的障碍物要占到一定比例），编写非递归的程序，求出一条从入口到出口的路径并显示之（结果若能用C的绘图函数显示更好） 2.2需求分析： 1．要求设计程序输出如下： (1) 建立一个大小为m×n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏 幕上显示出来； （2）找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点的坐标。 （3）用一种标志（如数字8）在迷宫中标出该条通路； （4）在屏幕上输出迷宫和通路； （5）上述功能可用菜单选择。 2.迷宫的建立： 迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述， 3.迷宫的存储： 迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。 数据结构课程设计 选题：八皇后问题 姓名： 学号： 指导老师： 目录 一.选题概述---------------------------------------3 二.设计要求与分析--------------------------------3 三.数据结构与定义--------------------------------4 1.结构体定义 2.函数定义 3.函数之间的定义 四.程序段与分析----------------------------------5 五.完整程序代码及运行结果截图------------------7 六.心得体会--------------------------------------10 七.参考文献--------------------------------------10 一．选题概述： 在实际应用中，有相当一类问题需要找出它的解集合，或者要求找出某些约束条件下的最优解。求解时经常使用一种称为回溯的方法来解决。所谓回溯就是走回头路，该方法是在一定的约束条件下试探地搜索前进，若前进中受阻，则回头另择通路继续搜索。为了能够沿着原路逆序回退，需用栈来保存曾经到达的每一个状态，栈顶的状态即为回退的第一站，因此回溯法均可利用栈来实现。而解决八皇后问题就是利用回溯法和栈来实现的。 二．设计要求与分析 八皇后问题是在8x8的国际象棋棋盘上，安放8个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一条对角线。 八皇后在棋盘上分布的各种可能的格局，其数目非常大，约等于232种，但是，可以将一些明显不满足问题要求的格局排除掉。由于任意两个皇后不能同行，即每一行只能放置一个皇后，因此将第i个皇后放置在第i行上。这样在放置第i个皇后时，只要考虑它与前i 一1个皇后处于不同列和不同对角线位置上即可。因此，其算法基本思想如下： 从第1行起逐行放置皇后，每放置一个皇后均需要依次对第1，2，…，8列进行试探，并尽可能取小的列数。若当前试探的列位置 实验二知识表示方法 梵塔问题实验 1．实验目的 （1）了解知识表示相关技术； （2）掌握问题规约法或者状态空间法的分析方法。 2．实验内容（2个实验内容可以选择1个实现） （1）梵塔问题实验。熟悉和掌握问题规约法的原理、实质和规约过程；理解规约图的表示方法； （2）状态空间法实验。从前有一条河，河的左岸有m个传教士、m个野人和一艘最多可乘n人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。搜索一条可使所有的野人和传教士安全渡到右岸的方案。 3．实验报告要求 （1）简述实验原理及方法，并请给出程序设计流程图。 我们可以这样分析： （1）第一个和尚命令第二个和尚将63个盘子从A座移动到B座； （2）自己将底下最大的盘子从A移动到C； （3）再命令第二个和尚将63个盘子从B座移动到C；（4）第二个和尚命令第三个和尚重复（1）（2）（3）；以此类推便可以实现。这明显是个递归的算法科技解决的问 题。 （2）源程序清单： #include int n; printf("input the number of diskes\n"); scanf("%d",&n); hanoi(n,'A','B','C'); } void hanoi(int n,char p1,char p2,char p3) { if(1==n) cout<<"盘子从"< 1.实验目的： 通过本实验，掌握复杂性问题的分析方法，了解汉诺塔游戏的时间复杂性和空间复杂性。 2.问题描述： 汉诺塔问题来自一个古老的传说：在世界刚被创建的时候有一座钻石宝塔（塔A),其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A 上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。 3.算法设计思想： 对于汉诺塔问题的求解，可以通过以下三个步骤实现： (1)将塔A上的n-1个碟子借助塔C先移到塔B上。 (2)把塔A上剩下的一个碟子移到塔C上。 (3)将n-1个碟子从塔B借助于塔A移到塔C上。 4.实验步骤： 1.用c++ 或c语言设计实现汉诺塔游戏； 2.让盘子数从2 开始到7进行实验，记录程序运行时间和递 归调用次数； 3.画出盘子数n和运行时间t 、递归调用次数m的关系图， 并进行分析。 5.代码设计： Hanio.cpp #include"stdafx.h" #include 实验报告 【实验名称】项目一迷宫问题的求解 【实验目的】 1.了解栈的基本操作以及充分理解栈的特点。熟悉掌握栈的基本操作和结构体 的运用。 2.学会用栈或者递归方法解决迷宫问题。 【实验原理】 1.本次实验中，以二维数组maze[row][col]表示迷宫，0表示通路，1表示墙，在构建迷宫时，为了清晰显示，在最外层添加一圈墙。 2.算法的核心思想是利用栈后进先出的特点，对迷宫进行探索，如果此路可行，则将此坐标的信息入栈，如果此路不通，则将此坐标的信息出栈。 3.输入形式：根据控制台的提示，依次输入迷宫的行数、列数，然后输入迷宫，再输入入口和出口坐标。 4.输出形式：由用户选择，由递归、非递归两种求解方式输出一条迷宫通路。以非递归方式会显示一种求解方案，并给出相应的三元组序列和迷宫方阵；以递归方式则会显示出所有的路线。 【实验内容】 1.需求分析 （1）问题描述 以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 要求以递归和非递归两种方式分别输出一条迷宫的通路，以带方向坐标和迷宫图像表示。 （2）基本要求 （1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于下列数据的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。 （2）编写递归形式的算法，求得迷宫中所有可能的通路。 （3）以方阵形式输出迷宫及其通路。 2.概要设计 （1）栈的抽象数据类型 ADT Stack{ 数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0} 数据关系：R1={ 数据结构实验报告 实验名称：实验二——利用栈结构实现八皇后问题 学生姓名： 班级： 班内序号： 学号： 日期：2013年11月21日 1．实验要求 （1）实验目的 通过选择下面五个题目之一进行实现，掌握如下内容： 进一步掌握指针、模板类、异常处理的使用 掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力 （2）实验内容 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。 ①可以使用递归或非递归两种方法实现 ②实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线。 （3）代码要求 ①必须要有异常处理，比如删除空链表时需要抛出异常； ②保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 ③递归程序注意调用的过程，防止栈溢出 2. 程序分析 2.1 存储结构 栈（递归）： 2.2 关键算法分析 (1)递归 void SeqStack 汉诺塔问题的重点是分析移动的规则，找到规律和边界条件。 若需要将n个盘子从A移动到C就需要（1）将n-1个盘子从A移动到B；（2）将你第n个从A移动到C；（3）将n-1个盘子再从B 移动到C，这样就可以完成了。如果n!=1，则需要递归调用函数，将A上的其他盘子按照以上的三步继续移动，直到达到边界条件n=1为止。 思路清楚了，程序就好理解了。程序中的关键是分析好每次调用移动函数时具体的参数和对应的A、B、C塔的对应的关系。下面来以实际的例子对照程序进行说明。 ①move(int n,int x,int y,int z) ②{ ③if (n==1) ④printf("%c-->%c\n",x,z); ⑤else ⑥{ ⑦move(n-1,x,z,y); ⑧printf("%c-->%c\n",x,z); ⑨{getchar();}//此句有必要用吗？感觉可以去掉的吧 ⑩move(n-1,y,x,z); } } 比如有4个盘子，现在全部放在A塔上。盘子根据编号为1、2、3、4依次半径曾大。现在要将4个盘子移动到C上，并且是按原顺序罗列。首先我们考虑如何才可以将4号移动到C呢？就要以B为中介，首先将上面的三个移动到B。此步的操作也就是程序中的①开始调入move函数（首次调用记为一），当然现在的n=4，然后判断即③n！=1所以不执行④而是到⑤再次调用move函数（记为二）考虑如何将3个盘移动到B的方法。此处是递归的调用所以又一次回到①开始调入move函数，不过对应的参数发生了变化，因为这次要考虑的不是从A移动4个盘到C，而是要考虑从A如何移动移动3个盘到B。因为n=3，故不可以直接移动要借助C做中介，先考虑将两个移动到C的方法，故再一次到⑤再一次递归调用move函数（记为三）。同理两个盘还是不可以直接从A移动到C所以要以B为中介考虑将1个移动到B的过程。这次是以B为中介，移动到C为目的的。接下来再一次递归调用move函数（记为四），就是移动到B一个，可以直接进行。程序执行③④句，程序跳出最内一次的调用（即跳出第四次的调用）返回上一次（第三次），并且从第三次的调用move 函数处继续向下进行即⑧，即将2号移动到了C，然后继续向下进行到 ⑩，再将已经移到B上的哪一个移回C，这样返回第二次递归（以C 为中介将3个盘移动到B的那次）。执行⑧，将第三个盘从A移动到B，然后进入⑩，这次的调用时因为是将C上的两个盘移到B以A 1．实验要求 【实验目的】 1、进一步掌握指针、模板类、异常处理的使用 2、掌握栈的操作的实现方法 3、掌握队列的操作的实现方法 4、学习使用栈解决实际问题的能力 5、学习使用队列解决实际问题的能力 【实验内容】 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。 提示： 1、可以使用递归或非递归两种方法实现 2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析 2.1 存储结构 存储结构：栈（递归） 2.2 关键算法分析 【设计思想】 由于八皇后问题，可以分解成算法相同的子问题，所以使用递归的方法 【伪代码】 1、输入皇后个数n 2、k=1 3、判断k是否大于n 3.1 是：打印一组可能 3.2 否：循环行位置1~n 判断该位置是否符合要求，若符合记录q[k]的坐标y值 k+1 重复3 【关键算法】 1、递归 void Queen::Queens(int k,int n) { int i; if(k>n) { Print(n); count(); } else { for(i=1;i<=n;i++) if(Isavailable(i,k)) //判断该行中该位置放置‘皇后’是否符合要求 { q[k]=i; //记录改行中该点的位置 Queens(k+1,n); //放置下一行的‘皇后’ } } } 2、判断皇后放置位置是否符合要求 bool Queen::Isavailable(int i,int k) { int j; j=1; while(j 汉诺塔递归与非递归算法研究 作者1，作者2，作者33 (陕西师范大学计算机科学学院，陕西西安 710062) 摘要: 摘要内容(包括目的、方法、结果和结论四要素) 摘要又称概要,内容提要.摘要是以提供文献内容梗概为目的,不加评论和补充解释,简明,确切地记述文献重要内容的短文.其基本要素包括研究目的,方法,结果和结论.具体地讲就是研究工作的主要对象和范围,采用的手段和方法,得出的结果和重要的结论,有时也包括具有情报价值的其它重要的信息.摘要应具有独立性和自明性,并且拥有与文献同等量的主要信息,即不阅读全文,就能获得必要的信息. 关键词:关键词1; 关键词2；关键词3；……（一般可选3~8个关键词，用中文表示，不用英文 Title 如：XIN Ming-ming , XIN Ming (1.Dept. of ****, University, City Province Zip C ode, China；2.Dept. of ****, University, City Province Zip C ode, China；3.Dept. of ****, University, City Province Zip C ode, China) Abstract: abstract（第三人称叙述，尽量使用简单句；介绍作者工作（目的、方法、结果）用过去时，简述作者结论用一般现在时） Key words: keyword1;keyword2; keyword3;……（与中文关键词对应，字母小写(缩略词除外)）； 正文部分用小5号宋体字，分两栏排，其中图表宽度不超过8cm.。设置为A4页面 1 引言（一级标题四号黑体加粗） 这个问题当时老和尚和众僧们，经过计算后，预言当所有的盘子都从基柱A移到基座B上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。其实，不管这个传说的可信度有多大，如果考虑把64个盘子，由一个塔柱上移到另一根塔柱上，并且始终保持上小下大的顺序。假设有n个盘子，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此后不难证明f(n)=2n-1。n=64时， f(64)= 2^64-1=18446744073709551615 假如每秒钟一次，共需多长时间呢？一年大约有 31536926 秒，计算表明移完这些金片需要5800多亿年，比地球寿命还要长，事实上，世界、梵塔、庙宇和众生都早已经灰飞烟灭。 对传统的汉诺塔问题，目前还有不少的学者继续研究它的非递归解法，本文通过对递归算法的研究……. 提示：（1）可以定义问题的规模n,如盘子的数量；（2）塔柱的数量（目前有部分理论可以支撑，不妨用计算机实现）分析规模的变化与算法的复杂度比较。（3）可以对经典的汉诺塔问题条件放松、加宽，如在经典的汉诺塔问题中大盘只能在小盘下面，放松其他条件可以定义相邻两个盘子必须满足大盘只能在小盘下面。其它盘子不作要求。 2 算法设计 2.1 汉诺塔递归算法描述（二级标题小五黑体加粗） 用人类的大脑直接去解3，4或5个盘子的汉诺塔问题还可以，但是随着盘子个数的增多，问题的规模变的越来越大。这样的问题就难以完成，更不用说吧问题抽象成循环的机器操作。所以类似的问题可用递归算法来求解。下面n个盘的汉 淮阴工学院 数据结构课程设计报告 设计题目：八皇后 系（院）:计算机工程系 专业：信息安全 班级：信息 1 0 6 学生姓名: 叶青学号:1061303127 指导教师:张亚红寇海洲胡荣林夏森 学年学期: 2007 ~ 2008 学年第 2 学期 2008 年 6 月25 日 设计任务书 摘要： 八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．使用递归方法最终将其问题变得一目了然，更加易懂。 关键词：八皇后; c++; 递归法 目录 1. 课题综述 (1) 1.1课题的来源及意义 (1) 1.2面对的问题 (1) 2. 需求分析 (1) 2.1涉及到的知识 (1) 2.2软硬件的需求 (1) 2.3功能需求 (2) 3. 概要设计 (2) 4. 详细设计和实现 (2) 4.1算法描述及详细流程图 (2) 4.1.1算法描述 (3) 4.1.2算法流程图 (3) 5. 代码编写及详细注释 (4) 6. 程序调试 (7) 6.1调试过程、步骤及遇到的问题 (7) 7. 运行与测试 (7) 7.1运行演示 (7) 总结 (9) 致谢 (10) 参考文献 (11) . 如对您有帮助，请购买打赏，谢谢您！ 目录 一需求分析............................................ 错误！未定义书签。 1.1程序的功能：...................................... 错误！未定义书签。 1.2程序的输入输出要求：.............................. 错误！未定义书签。二概要设计............................................ 错误！未定义书签。 2.1程序的主要模块：.................................. 错误！未定义书签。 2.2程序涉及：........................................ 错误！未定义书签。三详细设计............................................. 错误！未定义书签。 3.1相关代码及算法..................................... 错误！未定义书签。 3.1.1 定义相关的数据类型如下：...................... 错误！未定义书签。 3.1.2 主模块类C码算法：............................. 错误！未定义书签。 3.1.3 画棋盘模块类C码算法........................... 错误！未定义书签。 3.1.4 画皇后模块类C码算法：........................ 错误！未定义书签。 3.1.5 八皇后摆法模块（递归法）：.................... 错误！未定义书签。 3.1.6 初始化模块.................................... 错误！未定义书签。 3.1.7 输出摆放好的八皇后图形（动态演示）：.......... 错误！未定义书签。 3.2相关流程图......................................... 错误！未定义书签。四调试分析............................................. 错误！未定义书签。五设计体会............................................ 错误！未定义书签。六附录................................................ 错误！未定义书签。七参考文献............................................ 错误！未定义书签。 课程实践报告 题目：汉诺塔 姓名： 学号： 班级： 日期： 一实践目的 1、初步具备根据应用需求选择合理数据结构并进行算法设计的能力； 2、进一步提升C语言的应用能力； 3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 5、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风； 6、提升文档写作能力。 二问题定义及题目分析 汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。这是一个著名的问题，几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是：18，446，744，073，709，551，615 这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔。后来，这个传说就演变为汉诺塔游戏: 1.有三根杆子A，B，C。A杆上有若干圆盘。2.每次移动一块圆盘，小的只能叠在大的上面。3.把所有圆盘从A杆全部移到C杆上。经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动圆盘：如3阶汉诺塔的移动：A→C，A→B，C→B，A→C，B→A，B→C，A→C。 程序所能达到的功能： 用户只需要输入所需的层数即可，程序会自动计算出最终需要的步骤，并同时给出中间移动的过程。 三概要设计 1、设计思想 如果盘子为1，则将这个盘子从塔座A移动到塔座C；如果不为1，则采用递归思想。将塔座A的前n-1个盘子借助C盘（即目的盘）移到塔座B，移后，此时C为空座，那我们就可以将塔座A的第n个盘子移到塔座C了。接下来就将塔座B的n-1个盘子借助A移到塔座C，从而完成盘子的移动。 2、数据类型 结构体：用来存放盘子的栈。同时，在函数的参数中还用到了结构体类型的引用。 其他类型：基本的数据类型，包括整形，字符型。用来存放临时变量。 3、主要模块 Make By Mr.Cai 思路介绍： 首先，可证明，当盘子的个数为n 时，移动的次数应等于2^n - 1。 然后，把三根桩子按一定顺序排成品字型（如：C ..B .A ），再把所有的圆盘按至上而下是从小到大的顺序放在桩子A 上。 接着，根据圆盘的数量确定桩子的排放顺序： 若n 为偶数，按顺时针方向依次摆放C ..B .A ； 若n 为奇数，按顺时针方向依次摆放B ..C .A 。 最后，进行以下步骤即可： （1）首先，按顺时针方向把圆盘1从现在的桩子移动到下一根桩子，即当n 为偶数时，若圆盘1在桩子A ，则把它移动到B ；若圆盘1在桩子B ，则把它移动到C ；若圆盘1在桩子C ，则把它移动到A 。 （2）接着，把另外两根桩子上可以移动的圆盘移动到新的桩子上。 即把非空桩子上的圆盘移动到空桩子上，当两根桩子都非空时，移动较小的圆盘。 （3）重复（1）、（2）操作直至移动次数为2^n - 1。 #include } void Push(int top)//进栈 { s[++this->top]=top; } void setNext(Stake *p) { next=p; } Stake *getNext()//获取下一个对象的地址 { return next; } int getName()//获取当前桩子的编号 { return name; } private: int s[Cap+1];//表示每根桩子放盘子的最大容量 int top,name; Stake *next; }; void main() { int n; void hanoi(int,int,int,int); cout<<"请输入盘子的数量："; cin>>n; if(n<1) cout<<"输入的盘子数量错误!!!"<八皇后问题的解决完整文档
《递归算法与递归程序》教学设计
汉诺塔问题的三种实现
汉诺塔问题与递归思想教学设计
递归算法求解迷宫问题
汉诺塔非递归算法C语言实现
迷宫问题求解
数据结构课程设计报告-8皇后问题
汉诺塔问题
汉诺塔问题实验报告
c语言迷宫问题的求解(栈和递归)
数据结构实验报告利用栈结构实现八皇后问题
汉诺塔问题的重点是分析移动的规则
数据结构实验报告——栈(八皇后问题)
汉诺塔问题的非递归算法分析
八皇后问题的解决完整文档
数据结构八皇后问题
课程实践报告_汉诺塔
汉诺塔问题非递归算法详解