宁波网站建设企业网站制作,保定建站服务,江苏建设招标网站,友情链接交换的作用在于前言 定义#xff1a;自己调用自己#xff08;需要调用栈来执行#xff09; 两个基本要素#xff1a;边界条件#xff08;何时结束#xff09;和 递归模式#xff08;大问题如何转化为小问题#xff09; 关键#xff1a;根据递推关系式写程序#xff08;用数学归纳法…前言 定义自己调用自己需要调用栈来执行 两个基本要素边界条件何时结束和 递归模式大问题如何转化为小问题 关键根据递推关系式写程序用数学归纳法证明 注意递归算法在数据量特别大的时候会出现段错误例如递归运算100000000时 1.汉诺塔-递归 Description 从前有一座庙庙里有三个柱子柱A柱 B柱 C。柱A有64个盘子从上往下盘子越来越大。要求庙里的老和尚把这64个盘子全部移动到柱子C上。移动的时候始终只能小盘子压着大盘子。而且每次只能移动一个。
现在问题来了老和尚相知道将柱A上面前n个盘子从柱A搬到柱C搬动方法。要求移动次数最少。Input 输入有多组每组输入一个正整数n(0n16) 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..CHint #include iostreamusing 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的幂次方表示。例如
1372^72^32^0
由此可知137可表示为
2(7)2(3)2(0)
而7又可以表示为2(2)22(0)
3可以表示为22(0)
因此137最终表示为
2(2(2)22(0))2(22(0))2(0)Input 一个正整数n(n≤20000)。 Output 符合约定的n的0,2表示(在表示中不能有空格) Sample Input 1315Sample Output 2(2(22(0))2)2(2(22(0)))2(2(2)2(0))22(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 6Sample Output 6Hint 满足条件的数为
6162612636136 Source 洛古#include bits/stdc.h
using namespace std;
int num0;
int dfs(int n)
{for(int i1; in/2; i){num;dfs(i);}return 0;
}
int main()
{int n;cinn;dfs(n);coutnum1endl;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 对于例子一满足条件的数为
6162612636136 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和K1n,k1000;
第二行是这n个数a[i],1a[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和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
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份且每份不能为空任意两个方案不相同(不考虑顺序)。
例如n7k3下面三种分法被认为是相同的。
1 1 5
1 5 1
5 1 1
问有多少种不同的划分方法 Input 输入 n,k(n200, 2k6) Output 一个整数划分的方法 Sample Input 7 3 Sample 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;
}
