ACM程序设计课内实验（5）递归

本文主要是介绍ACM程序设计课内实验（5）递归，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

定义：自己调用自己（需要调用栈来执行）
两个基本要素：边界条件（何时结束）和 递归模式（大问题如何转化为小问题）
关键：根据递推关系式写程序（用数学归纳法证明）
注意：递归算法在数据量特别大的时候会出现段错误（例如：递归运算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

2

Sample Output

number..1..form..A..to..B
number..2..form..A..to..C
number..1..form..B..to..C

Hint

#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

1315

Sample 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，直接输出2cout << "2";return;}int k = 0, t = n;// 计算n可以表示为2的几次幂while (t > 1) {t /= 2;k++;}if (k == 1) { // 如果k为1，表示2^1，直接输出2cout << "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; // 输入正整数ndfs(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

6

Sample Output

6

Hint

满足条件的数为
6，16，26，126，36，136

Source

洛古

#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

6

Sample Output

6
例子二：
输入：10
输出：14

Hint

对于例子一满足条件的数为
6，16，26，126，36，136

Source

洛古

#include <bits/stdc++.h>
using namespace std;long long a[10001]; // 定义一个数组a，用来存储具有指定性质的数的个数int main() {int n;cin >> n; // 输入自然数na[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为偶数，可以加上前面的数或者前面的数除以2a[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 20

Sample 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和Kfor (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
10001011

Sample 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 3

Sample Output

4

Hint

四种分法为：
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;
}

这篇关于ACM程序设计课内实验（5）递归的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---