一个不知名大学生，江湖人称菜狗
original author: Jacky Li
Email : 3435673055@qq.comTime of completion：2024.03.24
Last edited: 2024.03.24
目录
递归课堂案例
第1关：斐波那契数列
任务描述
相关知识
编程要求
代码如下：
第2关：阿克曼函数
任务描述
相关知识
编程要求
代码如下：
第3关：排列问题
任务描述
编程要求
输入输出
代码如下：
第4关：整数划分问题
任务描述
编程要求
输入输出
代码如下：
第5关：汉诺塔问题
任务描述
输入输出
递归课堂案例
第1关：斐波那契数列
任务描述
本关需要你用递归函数实现斐波那契数列。
相关知识
斐波那契数列公式为：
F(1)=1，F(2)＝1，F(n)＝F(n-1)+F(n-2)
编程要求
请用递归函数实现斐波那契数列，在主函数中调用该递归函数，输出第n项的值。
效果如下：
输入：3 输出：2
开始你的任务吧，祝你成功！
代码如下：
#include <iostream>
using namespace std;
int F(int n)
{
if(n == 1 || n == 2) return 1;
else return F(n - 1) + F(n - 2);
}
int main()
{
int n;
cin >> n;
cout << F(n);
return 0;
}第2关：阿克曼函数
任务描述
本关需要你根据公式来编写一个递归函数的程序，且输出答案。
相关知识
编程要求
编写递归函数Acm(n,m)实现如下图所示的Acm函数，其中m、n为正整数。例如：Acm(2,1)=4，Acm(3,3)=16。
输入n和m两个整数，输出Acm(n,m)。如果n小于0或m小于0，则返回-1。
输入：2 1 输出：4
开始你的任务吧，祝你成功！
代码如下：
#include <iostream>
using namespace std;
int Acm(int m,int n)
{
if(n < 0 || m < 0) return -1;
if(m == 1 && n == 0) return 2;
else if(m == 0) return 1;
else if(n == 0) return m + 2;
else return Acm(Acm(m - 1, n), n - 1);
}
int main()
{
int m, n;
cin >> m >> n;
cout << Acm(m, n);
return 0;
}第3关：排列问题
任务描述
本关任务：设R={r1,r2,…rn}是要进行排列的n个元素，Ri=R−{ri},集合X中元素的全排列记为Perm(X)。(ri)Perm(X)表示在全排列Perm(X)的每个排列前加上前缀ri得到的排列。R的全排列可归纳定义如下：
- 当
n=1时，Perm(R)=(r),其中r是集合R中唯一元素； - 当
n>1时，Perm(R)由(r1)Perm(R1),(r2)Perm(R2),(r3)Perm(R3)...(rn)Perm(Rn)构成。
写出Perm(R)的递归算法。
编程要求
根据提示，在右侧编辑器补充代码。
输入输出
输入格式：一个正整数n，随后一行 n个字符（空格隔开） 输出格式：每种排列一行，以空格隔开（最后一个字符后也有一个空格） 平台会对你编写的代码进行测试,。
测试输入： 4 a b c d
预期输出：
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
开始你的任务吧，祝你成功！
代码如下：
#include<iostream>
using namespace std;
const int N = 100;
void swaps(char &a,char &b)//引用符号&是C++操作符，函数参数使用该符号将
{
char c;
c = a;
a = b;
b = c;
}
void perm(char item[], int k, int m)
{
/*********Begin*********/
if(k == m)
{
for(int i = 0; i <= m; i ++)
cout << item[i] << ' ';
cout << '\n';
}
for(int i = k; i <= m; i ++)
{
swaps(item[k], item[i]);
perm(item, k + 1, m);
swaps(item[k], item[i]);
}
/*********End**********/
}
int main()
{
int n;
char item[N];
cin>>n;
for(int i = 0; i < n; i ++)cin>>item[i];
perm(item,0,n-1);
return 0;
}第4关：整数划分问题
任务描述
任务描述:将正整数n表示成一系列正整数之和,n=n1+n2+⋯+nk(n1≥n2≥…,≥nk≥1,k≥1)正整数n的不同划分个数称为正整数n的划分数，记为p(n)。例如6有如下11种划分： 5+1;4+2,4+1+1;3+3,3+2,3+1+1;2+2+2,2+2+1+1,2+1+1+1+1;1+1+1+1+1+1 则p(6)=11 试求一个正整数n的划分数p(n)。
编程要求
根据提示，在右侧编辑器补充代码。
输入输出
输入格式：一个正整数n 输出格式：n划分数 测试输入：6 预期输出：11
开始你的任务吧，祝你成功！
代码如下：
#include<iostream>
using namespace std;
int q(int n,int m)
{
if(n == 1 || m == 1) return 1;
else if(m == n)
return q(n, n - 1) + 1;
else if(m > n)
return q(n, n);
else
return q(n, m - 1) + q(n-m, m);
}
int main()
{
int n;
cin>>n;
cout<<q(n,n);
return 0;
}第5关：汉诺塔问题
任务描述
本关任务：设a,b,c是三个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小叠在一起，各圆盘从小到大编号为1,2,…,n，如下图所示，现在要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样的顺序叠放。在移动圆盘时遵守以下移动规则：
- 规则1：每次只能移动一个圆盘；
- 规则II：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；
- 规则III:在满足移动规则I和II的前提下，可将圆盘移至a,b,c中任一塔座上。
输入输出
输入格式：一个证正整数表示圆盘个数n 输出格式：若干行，每行一次移动：盘号：起始塔座->目标塔座
平台会对你编写的代码进行测试：
测试输入：
3
预期输出：
1:a->b
2:a->c
1:b->c
3:a->b
1:c->a
2:c->b
1:a->b
开始你的任务吧，祝你成功！
#include<iostream>
using namespace std;
void move(int n,char x,char y)
{
printf("%d:%c->%c\n", n, x, y);
}
void hanoi(int n,char x,char y,char z)
{
if(n == 1) move(1, x, z);
else
{
hanoi(n-1, x, z, y);
move(n, x, z);
hanoi(n-1, y, x, z);
}
}
int main()
{
int n;
char A='a',B = 'b',C='c';
cin>>n;
hanoi(n,A,C,B);
return 0;
}作者有言
如果感觉博主讲的对您有用，请点个关注支持一下吧，将会对此类问题持续更新……
