CPP2022-14-递归（下）

输入样例：

6

输出样例：

8

1. int f( int n )
2. {
3. if(n<=1)
4.     {
5. return n;
6.     }
7. else
8.     {
9. return f(n-1)+f(n-2);
10.     }
11. }

6-5 十进制转换二进制

分数 10

全屏浏览题目

切换布局

作者 C课程组

单位 浙江大学

本题要求实现一个函数，将非负整数n转换为二进制后输出。

函数接口定义：

void dectobin( int n );

函数dectobin应在一行中打印出二进制的n。建议用递归实现。

裁判测试程序样例：

#include <stdio.h> void dectobin( int n ); int main() { int n; scanf("%d", &n); dectobin(n); return 0; } /* 你的代码将被嵌在这里 */

输入样例：

10

输出样例：

1010

1. void dectobin( int n )
2. {
3. if(n==0)
4.     {
5. printf("0");
6.     }
7. else if(n==1)
8.     {
9. printf("1");
10.     }
11. else
12.     {
13. dectobin(n/2);
14. printf("%d",n%2);
15.     }
16. }

6-6 递归计算P函数

分数 15

全屏浏览题目

切换布局

作者 C课程组

单位 浙江大学

本题要求实现下列函数P(n,x)的计算，其函数定义如下：

函数接口定义：

double P( int n, double x );

其中n是用户传入的非负整数，x是双精度浮点数。函数P返回P(n,x)函数的相应值。题目保证输入输出都在双精度范围内。

裁判测试程序样例：

#include <stdio.h> double P( int n, double x ); int main() { int n; double x; scanf("%d %lf", &n, &x); printf("%.2f\n", P(n,x)); return 0; } /* 你的代码将被嵌在这里 */

输入样例：

10 1.7

输出样例：

3.05

1. double P( int n, double x )
2. {
3. if(n==0)
4.     {
5. return 1;
6.     }
7. else if(n==1)
8.     {
9. return x;
10.     }
11. else
12.     {
13. return ((2*n-1)*P(n-1,x)-(n-1)*P(n-2,x))/n;
14.     }
15. }

6-7 递归计算Ackermenn函数

分数 15

全屏浏览题目

切换布局

作者 C课程组

单位 浙江大学

本题要求实现Ackermenn函数的计算，其函数定义如下：

函数接口定义：

int Ack( int m, int n );

其中m和n是用户传入的非负整数。函数Ack返回Ackermenn函数的相应值。题目保证输入输出都在长整型

范围内。

裁判测试程序样例：

#include <stdio.h> int Ack( int m, int n ); int main() { int m, n; scanf("%d %d", &m, &n); printf("%d\n", Ack(m, n)); return 0; } /* 你的代码将被嵌在这里 */

输入样例：

2 3

输出样例：

9

1. int Ack( int m, int n )
2. {
3. if(m==0)
4.     {
5. return n+1;
6.     }
7. else if(n==0&&m>0)
8.     {
9. return Ack(m-1,1);
10.     }
11. else if(m>0&&n>0)
12.     {
13. return Ack(m-1,Ack(m,n-1));
14.     }
15. }

6-8 汉诺塔问题

分数 20

全屏浏览题目

切换布局

作者 李祥

单位 湖北经济学院

汉诺塔是一个源于印度古老传说的益智玩具。据说大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘，大梵天命令僧侣把圆盘移到另一根柱子上，并且规定：在小圆盘上不能放大圆盘，每次只能移动一个圆盘。当所有圆盘都移到另一根柱子上时，世界就会毁灭。

请编写函数，完成移动汉诺塔的任务。

函数原型

void MoveTower(int num, char src, char dst, char trs);

说明：参数 num 为金片数，src、dst 和 trs 分别为起始柱、目的柱和过渡柱。若金片数大于 0，则函数将金片组成的汉诺塔由起始柱利用过渡柱最终搬到目的柱，否则什么也不做。

下面的程序，输入汉诺塔圆片的数量，输出移动汉诺塔的步骤。

裁判程序

#include <stdio.h> void MoveTower(int num, char src, char dst, char trs); int main() { int n; char s, d, t; scanf("%d %c %c %c", &n, &s, &d, &t); MoveTower(n, s, d, t); return 0; } /* 你提交的代码将被嵌在这里 */

输入格式

圆盘数

起始柱 目的柱 过渡柱

输出格式

移动汉诺塔的步骤

每行显示一步操作，具体格式为：

盘片号: 起始柱 -> 目的柱

其中盘片号从 1 开始由小到大顺序编号。

输入样例

1. 3
2. a c b

输出样例

1. 1: a -> c
2. 2: a -> b
3. 1: c -> b
4. 3: a -> c
5. 1: b -> a
6. 2: b -> c
7. 1: a -> c

1. void MoveTower(int num, char src, char dst, char trs)
2. {
3. if(num==1)
4.  {
5.    printf("1: %c -> %c\n",src,dst);
6.    return;
7.  }
8.  MoveTower(num-1,src,trs,dst);
9.  printf("%d: %c -> %c\n",num,src,dst);
10.   MoveTower(num-1,trs,dst,src);
11.   return;
12. }