ACM程序设计课内实验(5)递归
2023-12-14 05:01:02
前言
定义:自己调用自己(需要调用栈来执行)
两个基本要素:边界条件(何时结束)和 递归模式(大问题如何转化为小问题)
关键:根据递推关系式写程序(用数学归纳法证明)
注意:递归算法在数据量特别大的时候会出现段错误(例如:递归运算100000000!时)
1.汉诺塔-递归
Description
从前有一座庙,庙里有三个柱子,柱A柱 B柱 C。柱A有64个盘子,从上往下盘子越来越大。要求庙里的老和尚把这64个盘子全部移动到柱子C上。移动的时候始终只能小盘子压着大盘子。而且每次只能移动一个。 现在问题来了,老和尚相知道将柱A上面前n个盘子从柱A搬到柱C搬动方法。要求移动次数最少。Input
输入有多组,每组输入一个正整数n(0<n<16)Output
每组测试实例,输出每一步的步骤,输出“number..a..form..b..to..c”。表示将第a个盘子从柱b搬到柱c.Sample Input
2Sample Output
number..1..form..A..to..B number..2..form..A..to..C number..1..form..B..to..CHint
#include <iostream>
using namespace std;
void hanoi(int n, char A, char B, char C) {
if (n == 1) {
printf("number..%d..form..%c..to..%c\n",n, A, C);
} else {
hanoi(n - 1, A, C, B);
printf("number..%d..form..%c..to..%c\n",n, A, C);
hanoi(n - 1, B, A, C);
}
}
int main() {
int n;
ios::sync_with_stdio(false);
while (scanf("%d", &n) != EOF) {
hanoi(n, 'A', 'B', 'C');
}
return 0;
}
2.幂次方-递归
Description
任何一个正整数都可以用2的幂次方表示。例如 137=2^7+2^3+2^0 由此可知,137可表示为: 2(7)+2(3)+2(0) 而7又可以表示为:2(2)+2+2(0) 3可以表示为:2+2(0) 因此137最终表示为: 2(2(2)+2+2(0))+2(2+2(0))+2(0)Input
一个正整数n(n≤20000)。Output
符合约定的n的0,2表示(在表示中不能有空格)Sample Input
1315Sample Output
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
#include <iostream>
using namespace std;
// 递归函数,将正整数n表示为2的幂次方的形式
void dfs(int n) {
if (n == 0) { // 如果n为0,表示已经表示完成,直接返回
return;
}
if (n == 1) { // 如果n为1,表示2^0,直接输出2(0)
cout << "2(0)";
return;
}
if (n == 2) { // 如果n为2,表示2^1,直接输出2
cout << "2";
return;
}
int k = 0, t = n;
// 计算n可以表示为2的几次幂
while (t > 1) {
t /= 2;
k++;
}
if (k == 1) { // 如果k为1,表示2^1,直接输出2
cout << "2";
} else {
cout << "2("; // 否则输出2(,表示2的幂次方
dfs(k); // 递归计算k的2的幂次方表示
cout << ")"; // 输出)
}
if (n - (1 << k) > 0) { // 如果n减去2^k后大于0,表示还有余数需要继续表示
cout << "+"; // 输出+
dfs(n - (1 << k)); // 递归计算n减去2^k后的表示
}
}
int main() {
int n;
cin >> n; // 输入正整数n
dfs(n); // 调用递归函数表示n的2的幂次方形式
cout << endl;
return 0;
}
?3.数的计算-递归
Description
我们要求找出具有下列性质数的个数(包含输入的自然数n): 先输入一个自然数n(n≤500),然后对此自然数按照如下方法进行处理: 1、不作任何处理; 2、在它的左边加上一个自然数,但该自然数不能超过原数的一半; 3、加上数后,继续按此规则进行处理,直到不能再加自然数为止.Input
1个自然数n(n≤500)Output
1个整数,表示具有该性质数的个数。Sample Input
6Sample Output
6Hint
满足条件的数为 6,16,26,126,36,136Source
洛古
#include <bits/stdc++.h>
using namespace std;
int num=0;
int dfs(int n)
{
for(int i=1; i<=n/2; i++)
{
num++;
dfs(i);
}
return 0;
}
int main()
{
int n;
cin>>n;
dfs(n);
cout<<num+1<<endl;
return 0;
}
?4.数的计算加强版-递推
Description
我们要求找出具有下列性质数的个数(包含输入的自然数n): 先输入一个自然数n(n≤10000),然后对此自然数按照如下方法进行处理: 1、不作任何处理; 2、在它的左边加上一个自然数,但该自然数不能超过原数的一半; 3、加上数后,继续按此规则进行处理,直到不能再加自然数为止.Input
1个自然数n(n≤10000)Output
1个整数,表示具有该性质数的个数。(64位的整数范围)Sample Input
6Sample Output
6 例子二: 输入:10 输出:14Hint
对于例子一满足条件的数为 6,16,26,126,36,136Source
洛古
#include <bits/stdc++.h>
using namespace std;
long long a[10001]; // 定义一个数组a,用来存储具有指定性质的数的个数
int main() {
int n;
cin >> n; // 输入自然数n
a[0] = a[1] = 1; // 初始化a[0]和a[1]为1,表示0和1都满足条件
for (int i = 1; i <= n; i++) { // 从1到n中遍历每个自然数
if (i & 1) { // 如果i为奇数,说明不能加自然数,直接继承前一个数的结果
a[i] = a[i - 1];
} else { // 如果i为偶数,可以加上前面的数或者前面的数除以2
a[i] = a[i - 1] + a[i / 2];
}
}
cout << a[n] << endl; // 输出具有指定性质的数的个数
return 0;
}
5.数字分段-递归
Description
给你N个正整数,把这些正整数分成一些段,顺序不能乱,每段的数字和最大为K;请你输出每段的开始下标和结束下标;前面的段和尽量小(也就是后面的和尽量大);Input
第一行输入N和K,(1<=n,k<=1000); 第二行是这n个数a[i],(1<=a[i]<=100); k大于任意a[i];Output
输出每段的起点和终点的下标(从1开始);Sample Input
6 20 1 6 5 10 15 20Sample Output
1 2 3 4 5 5 6 6
这是一个贪心算法的问题,我们可以从左到右遍历数组,每次尽可能多地取数,直到当前段的和大于K。然后输出当前段的开始下标和结束下标,接着从下一个位置重新开始计算新的段。0?
#include <bits/stdc++.h>
using namespace std;
int a[100];
int n, k;
// 递归函数,用于查找每个段的起点和终点下标
int dfs(int r, int l) {
int s = 0;
for (int i = r; i >= l; i--) {
s += a[i];
if (s > k) {
dfs(i, l); // 递归调用,查找下一个段的起点和终点下标
cout << i + 1 << " " << r << endl; // 输出当前段的起点和终点下标
return 0;
}
}
cout << 1 << " " << r << endl; // 输出最后一个段的起点和终点下标
}
int main() {
cin >> n >> k; // 读取输入的N和K
for (int i = 1; i <= n; i++)
cin >> a[i]; // 读取输入的N个正整数a[i]
dfs(n, 1); // 调用递归函数,从最后一个数字开始查找每个段的起点和终点下标
return 0;
}
?6.FBI树-递归
Description
我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。 FBI树是一种二叉树,它的结点类型也包括F结点,B结点和I结点三种。由一个长度为2^N 的“01”串S可以构造出一棵FBI树T,递归的构造方法如下: 1) T的根结点为R,其类型与串S的类型相同; 2) 若串S的长度大于1,将串S从中间分开,分为等长的左右子串S_1 和S_2 ;由左子串S_1 构造R的左子树T_1,由右子串S_2 构造R的右子树T_2。 现在给定一个长度为2^N 的“01”串,请用上述构造方法构造出一棵FBI树,并输出它的后序遍历序列。Input
第一行是一个整数N(0≤N≤10), 第二行是一个长度为2^N 的“01”串。Output
一个字符串,即FBI树的后序遍历序列。Sample Input
3 10001011Sample Output
IBFBBBFIBFIIIFF
?解析:首先需要根据输入的字符串长度N,计算出字符串的长度为2^N。然后根据题目要求,构造一棵FBI树,并输出它的后序遍历序列。
#include <iostream>
#include <string>
using namespace std;
// 递归构造FBI树的函数
void dfs(string s, int start, int end) {
// 当子串长度为1时,根据字符输出对应的B结点或I结点
if (start == end) {
if (s[start] == '0') {
cout << "B";
} else {
cout << "I";
}
} else {
// 将子串分为左右两部分
int mid = (start + end) / 2;
// 递归构造左右子树
dfs(s, start, mid);
dfs(s, mid + 1, end);
// 统计左右子树中0和1的个数
int count0 = 0, count1 = 0;
for (int i = start; i <= end; i++) {
if (s[i] == '0') {
count0++;
} else {
count1++;
}
}
// 根据左右子树的类型输出当前结点的类型
if (count0 == 0 && count1 > 0) {
cout << "I";
} else if (count1 == 0 && count0 > 0) {
cout << "B";
} else {
cout << "F";
}
}
}
int main() {
int n;
string s;
cin >> n >> s;
// 从根节点开始递归构造FBI树并输出后序遍历序列
dfs(s, 0, (1 << n) - 1);
cout << endl;
return 0;
}
?7.数的划分-递归
Description
将整数n分成k份,且每份不能为空,任意两个方案不相同(不考虑顺序)。 例如:n=7k=3,下面三种分法被认为是相同的。 1 1 5 1 5 1 5 1 1 问有多少种不同的划分方法?Input
输入 n,k(n<=200, 2<=k<=6)Output
一个整数,划分的方法!Sample Input
7 3Sample Output
4Hint
四种分法为: 1,1,5; 1,2,4; 1,3,3; 2,2,3.
#include <iostream>
using namespace std;
int countPartitions = 0;
// 递归计算整数n分成k份的不同划分方法
void dfs(int n, int k, int start, int count, int sum) {
// 当划分数达到k时,如果sum等于n,则找到一种划分方法
if (count == k) {
if (sum == n) {
countPartitions++;
}
return;
}
// 从start开始尝试不同的划分
for (int i = start; i <= n - sum; i++) {
dfs(n, k, i, count + 1, sum + i);
}
}
int main() {
int n, k;
cin >> n >> k;
dfs(n, k, 1, 0, 0);
cout << countPartitions << endl;
return 0;
}
文章来源:https://blog.csdn.net/qq_62377885/article/details/134984612
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!