c语言数据结构 - 图文

递归（续）*

?

递归算法十分简洁，编译后得到的目标代码也很短，但它并不节省（实际上还要增加）运行时所需的时间和空间，因为它必须维持一个要处理的值的栈。此外，递归算法并不是语言必须的，不用它同样可以实现相应功能，如上例中，递归函数fact可用非递归方法实现：int fact(int n)

{

int f = 1;while(n){

f *= n;n--;

}

return ( f);}

问题4.3：一个经典递归程序示例*例：汉诺塔(hanoitower)游戏voidhanoi(intn,chara,charb,charc){如果要移动64个盘子,则移动次数为264-1.如果每秒移动一个盘子,则需要约5*1011年.一般认为地球的寿命为50亿年(约5*109).以每秒10亿次的移动速度计算,约需要500年.if(n>0){hanoi(n-1,a,c,b);printf(“MOVE%d:%c?%c\\n”,n,a,c);hanoi(n-1,b,a,c);}}main(){intn;scanf(“%d”,&n);hanoi(n,?A?,?B?,?C?);}printf(“Pleaseinputthenumberofhanoitower:”);ABC问题4.4：生成全排列数*

【问题描述】输入整数N( 1 <= N <= 10 )，生成从1~N所有整数的全排列。【输入形式】输入整数N。

【输出形式】输出有N!行，每行都是从1~N所有整数的一个全排列，各整数之间以空格分隔。各行上的全排列不重复。输出各行遵循“小数优先”原则, 在各全排列中，较小的数尽量靠前输出。如果将每行上的输出看成一个数字，则所有输出构成升序数列。具体格式见输出样例。【样例输入1】3【样例输出1】1 2 31 3 22 1 32 3 13 1 23 2 1

【样例说明1】输入整数N=3，要求整数1、2、3的所有全排列, 共有N!=6行。且先输出1开头的所有排列数，再输出2开头的所有排列数，最后输出3开头的所有排列数。在以1开头的所有全排列中同样遵循此原则。

【样例输入2】10 【样例输出2】1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 10 91 2 3 4 5 6 7 9 8 101 2 3 4 5 6 7 9 10 81 2 3 4 5 6 7 10 8 91 2 3 4 5 6 7 10 9 8……………………

【样例说明2】输入整数N=10，要求整数1、2、3、……、10的所有全排列。上例显示了输出的前10行。

问题4.4：算法分析*

?

对于N的全排列：MNMN-1…Mn…M1

其中Mn的值应为1,2,…,N数字中不为MNMN-1…Mn+1的数字，并且应从小到大取值。因此，可设一个数组int Mark[N]用来分别标识一个数字是否已被使用。因此，对于生成Mn数字的算法如下：If(n==0)/*当前排列已生成*/

输出数字串MNMN-1…Mn…M1;结束；

使用递归方法！

for(i=1; i<=N; i++)

If(Mark[i] == 0) /*表示该数字i未使用*/

Mark[i] = 1; /*数字i将被使用*/

将数字i放到全排列位置n上（即MNMN-1…Mn的Mn）生成Mn-1数字；

Mark[i] = 0; /*数字i将被释放*/