C++少儿编程（14）递归算法

C++少儿编程（14）递归算法

一递归概述pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

递归：是一种通过函数调用自身来解决问题的方法。

递归的核心思想：将大问题分解为相同结构的子问题，直到最小子问题，然后逐步解决。这也是“分治算法”的核心思想。pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

递归与递推的区别：递推是从已知到未知的过程，递归是从未知到已知的过程；递推是单向的，按照从前往后或者从后往前的单一顺序计算，递归是双向的，先递推下去，再原路回归（也叫“回溯”）。pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

二递归的实现步骤pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

1、确定结束条件（最小子问题的解）；
2、根据递推公式计算子问题。
由于递归算法是通过函数调用自身实现的，所以，只需定义递归函数，并在递归函数中完成以上两个步骤即可。
注意：
1、递归的过程，就是频繁调用函数的过程，这个过程需要不停地执行压栈和出栈操作，非常消耗时间，所以递归的效率不高；
2、递归操作，不仅耗时，还消耗空间，当递归深度（调用递归函数的次数）高于某个值的时候，就会耗尽内存，导致程序出错和电脑宕机，所以递归深度不宜过深；
3、如果结束条件不写或者写错，递归可能会陷入无限循环。
 
【例题-1】计算n的阶乘（递归算法）
阶乘（Factorial）是指一个自然数从1乘到它本身的积，用“!”表示。
例如：5的阶乘，记作“5!”。5! = 1*2*3*4*5。
特殊说明：1! = 1, 0! = 1。
【递归过程】f(n)表示n的阶乘
1、结束条件：f(1) = 1；
2、递推公式：f(n) = n * f(n-1)。
【例题-1 示例程序】
  1. # include <bits/stdc++.h> 
  2. using namespace std; 
  3. // 创建递归函数，计算 n 的阶乘 
  4. int factorial(int n) { 
  5.     if (n < 2) return 1;    // 确定结束条件（最小子问题的解） 
  6.     return n * factorial(n-1);  // 根据递推公式计算子问题 
  7. } 
  8. int main() { 
  9.     int n; 
  10.     cin >> n; 
  11.     // 调用递归函数，计算并输出 n 的阶乘 
  12.     cout << factorial(n) << endl; 
  13.     return 0; 
  14. } 
 
 
斐波那契数列前10项如下：
0
1
1
2
3
5
8
13
21
34
 
【例题-2】递归计算斐波那契数列第n项
【递归过程】f(n)表示斐波那契数列的第n项
1、结束条件：f(0) = 0，f(1) = 1；
2、递推公式：f(n) = f(n-1) + f(n-2)。
【例题-2 示例程序】
  1. # include <bits/stdc++.h> 
  2. using namespace std; 
  3. // 创建递归函数，计算斐波那契数列第 n 项 
  4. int fib(int n) { 
  5.     if (n < 2) return n;    // 确定结束条件（最小子问题的解） 
  6.     return fib(n-1) + fib(n-2);  // 根据递推公式计算子问题 
  7. } 
  8. int main() { 
  9.     int n; 
  10.     cin >> n; 
  11.     // 调用递归函数，计算并输出 n 的阶乘 
  12.     cout << fib(n) << endl; 
  13.     return 0; 
  14. } 
 
 
【例题-3】上楼梯问题（递归算法）
假设楼梯共有n个台阶（1<=n<=100），上楼梯时，可以一步上一个台阶，也可以一步上两个台阶，请问爬上第n个台阶共有多少种不同的走法？
【递归过程】f(n)表示到第n个台阶的走法
1、结束条件：f(1) = 1，f(2) = 2；
2、递推公式：f(n) = f(n-1) + f(n-2)。
【例题-3 示例程序】
  1. # include <bits/stdc++.h> 
  2. using namespace std; 
  3. // 创建递归函数，计算到第 n 个台阶的走法 
  4. int slt(int n) { 
  5.     if (n < 3) return n;    // 确定结束条件（最小子问题的解） 
  6.     return slt(n-1) + slt(n-2); // 根据递推公式计算子问题 
  7. } 
  8. int main() { 
  9.     int n; 
  10.     cin >> n; 
  11.     // 调用递归函数，计算并输出到第 n 个台阶的走法 
  12.     cout << slt(n) << endl; 
  13.     return 0; 
  14. } 
 
 
【例题-4】信封问题（递归算法）
有n封信和n个信封，如果所有的信都装错信封，有几种装法？
【问题分析】
  • 任取一封信，装错的情况：n-1。
  • 在剩余的信中，再任取一封信，装错的情况有两种：
    1、与上一封信位置互换，接下来就变成了n-2封信的错排问题；
    2、不与上一封信位置互换，接下来就成了n-1封信的错排问题。
  • 总结递推式：f(n) = (n-1) * [f(n-1) + f(n-2)]。
【递推过程】f(n)表示n封信的错排装法
1、结束条件：f(1) = 0，f(2) = 1；
2、递推公式：f(n) = (n-1) * [f(n-1) + f(n-2)]。
【例题-4 示例程序】
 
  1. # include <bits/stdc++.h> 
  2. using namespace std; 
  3. // 创建递归函数，计算 n 封信的错排装法 
  4. int cuo_pai(int n) { 
  5.     // 确定结束条件（最小子问题的解） 
  6.     if (n == 1) return 0; 
  7.     if (n == 2) return 1; 
  8.     // 根据递推公式计算子问题 
  9.     return (n-1) * (cuo_pai(n-1) + cuo_pai(n-2)); 
  10. } 
  11. int main() { 
  12.     int n; 
  13.     cin >> n; 
  14.     // 调用递归函数，计算并输出 n 封信的错排装法 
  15.     cout << cuo_pai(n) << endl; 
  16.     return 0; 
  17. } 
 
【例题-5】施工问题（用递归实现倒推）
有n个施工小队共同完成一项工程，第一小队完成工程总量的一半加1，第二小队完成剩余工程的一半加2，第三小队完成剩余工程的一半加3，按照这种施工进度，第n小队完成剩余的全部工程，恰好等于施工队的数量n。求工程总量。（1<=n<=10）
【问题分析】倒推递归要用后项表示前项
设第n小队面临的施工数量为f(n)。
根据题意：f(n+1) = f(n)/2 - n，
整理之后：f(n) = 2 * f(n+1) + 2 * n。
【递推过程】注意朝着结束条件进行递归计算
1、结束条件：f(最后一队的任务) = 最后一队的编号；
2、递推公式：f(n) = 2 * f(n+1) + 2 * n。
【例题-5 示例程序】
  1. # include <bits/stdc++.h> 
  2. using namespace std; 
  3. // 创建递归函数，倒推计算第 i 施工队面临的任务（n为施工小队数量） 
  4. int dao_tui(int i, int n) { 
  5.     // 确定结束条件（当前施工队编号等于施工队数量时，结束递归） 
  6.     if (i == n) return n; 
  7.     // 根据递推公式计算子问题 
  8.     return 2 * dao_tui(i+1, n) + 2 * i; 
  9. } 
  10. int main() { 
  11.     int n; 
  12.     cin >> n; 
  13.     // 调用递归函数，计算并输出第 i 施工队面临的任务 
  14.     cout << dao_tui(1, n) << endl; 
  15.     return 0; 
  16. } 

三求最大公约数pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

 

最大公约数（Greatest Common Divisor）是指两个或多个整数公有约数中最大的一个。求最大公约数有多种方法，简略介绍以下三种方法。pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

方法一、质因数分解法
【步骤】
1、将每个数分解为质因数的乘积；
2、找出所有公共质因数；
3、将公共质因数相乘，得到最大公约数。
【示例】求 24 和 36 的最大公约数
1、质因数分解：
24 = 2 * 2 * 2 * 3
36 = 2 * 2 * 3 * 3
2、公共质因数：2 、2、3
3、最大公约数：2 * 2 * 3 = 12
 
方法二、欧几里得算法（辗转相除法）
【步骤】
1、用较大的数除以较小的数，得到余数；
2、将除数作为新的被除数，余数作为新的除数，继续相除；
3、重复步骤 2，直到余数为 0，此时的除数即为最大公约数。
【示例】求 24 和 36 的最大公约数
1、36 ÷ 24 = 1，余数为12；
2、24 ÷ 12 = 2，余数为0；
3、最大公约数为12。
 
方法三、更相减损术（辗转相减法）
这是我国古代计算最大公约数的算法。
【步骤】
1、用较大的数减去较小的数，得到差；
2、将上一步的减数和差再进行操作1；
3、直到减数和差相等，此时的差就是最大公约数。
【示例】求 24 和 36 的最大公约数
1、36 - 24 = 12；
2、24 - 12 = 12；
3、最大公约数为12。
 
【例题-6】用辗转相除法求最大公约数（递归算法）
让用户输入两个大于1的整数a、b，求a、b两数的最大公约数。（a!=b）
【问题分析】
输入之后，确保a>b，a为被除数，b为除数。
当余数为0时，返回除数。
【递推过程】
1、结束条件：余数为0；
2、递推关系：除数变被除数，余数变除数。
【例题-6 示例程序】
  1. # include <bits/stdc++.h> 
  2. using namespace std; 
  3. // 定义递归函数，使用辗转相除法求最大公约数 
  4. int gcd(int a, int b) { 
  5.     if (a % b == 0) return b;  // 结束条件 
  6.     return gcd(b, a % b);  // 更新被除数和除数 
  7. } 
  8. int main() { 
  9.     int a, b; 
  10.     cin >> a >> b; 
  11.     // 确保 a > b 
  12.     if (a < b) swap(a, b); 
  13.     // 调用递归函数，求a、b两数的最大公约数 
  14.     cout << gcd(a, b) << endl; 
  15.     return 0; 
  16. } 

 pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

四分解质因数pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

分解质因数（Decomposition of prime factors）是指将一个正整数表示为一系列质数的乘积形式。
例如，对60分解质因数：60 = 2 * 2 * 3 * 5。
除了1和它本身之外，还有其它因数的数，叫作“合数”。
特殊情况：1 既不是质数，也不是合数。
 
算术基本定理：也称为唯一分解定理，是数论中的一个核心定理，即：每个大于1的自然数，要么本身就是质数，要么可以写成2个或更多质数的乘积，若将这些质因数从小到大排列之后，有且仅有一种写法。
算术基本定理包含两个核心内容：
1、分解的存在性；
2、分解的唯一性。
 
分解质因数的基础方法是试除法，具体步骤如下：
1、从最小的质数2开始，尝试能否整除n；（n为待分解数）
2、如果能整除，记录这个质数，并用商继续分解；
3、如果不能整除，尝试更大的除数；
4、直到待分解数为1的时候，分解结束。
 
示例：分解84

  • 84 ÷ 2 = 42 → 2pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

  • 42 ÷ 2 = 21 → 2pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

  • 21 ÷ 3 = 7 → 3pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

  • 7 ÷ 7 = 1 → 7pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

结果：84 = 2 * 2 * 3 * 7。
 
【例题-7】用递归算法分解质因数
输入一个大于2的正整数n，用递归算法从小到大输出它的所有质因子。所有的质因子输出一行，用空格分隔。
【递推过程】
1、结束条件：待分解数为1；
2、递推关系：如果余数为0，商为新的待分解数，除数不变；否则，待分解数不变，除数加1。
【例题-7 示例程序】
  1. # include <bits/stdc++.h> 
  2. using namespace std; 
  3. // 定义递归函数，分解质因数 
  4. // n 为待分解数，m 为当前分解出来的数 
  5. void fen_jie(int n, int m) { 
  6.     if (n == 1) return;  // 结束条件 
  7.     if (n%m == 0) { 
  8.         cout << m << " "; 
  9.         fen_jie(n/m, m);  // 递归调用 
  10.     } else { 
  11.         fen_jie(n, m+1);  // 递归调用 
  12.     } 
  13. } 
  14. int main() { 
  15.     int n; 
  16.     cin >> n; 
  17.     // 调用递归函数，对 n 分解质因数，从2开始分解 
  18.     fen_jie(n, 2); 
  19.     return 0; 
  20. } 
五课后习题
 

1、【阅读程序】理解递归函数的执行流程pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

阅读下列程序，在脑海里预演输出结果，然后再用电脑验证你的猜想。pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

  1. # include <bits/stdc++.h> 
  2. using namespace std; 
  3. // 声明递归函数 
  4. void test(int n) { 
  5.     if (n > 0){ 
  6.         test(n-1); 
  7.         for (int i=1; i<=n; i++) cout << "*"; 
  8.         cout << endl; 
  9.     } 
  10.     return; 
  11. } 
  12. int main() { 
  13.     test(5);  // 调用递归函数 
  14.     return 0; 
  15. } 

简单说说上述代码的执行流程，理解递归函数的压栈、出栈过程。pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【思考】pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

如果想得到垂直翻转的图案，该怎么修改上述代码？pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

 pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

 pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

2、用递归算法分解质因数pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【描述】输入一个正整数n，用递归算法从小到大输出它所有的质因数，以及质因数的总个数。pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【输入】一行一个整数n（2<n<10000）。pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【输出】第一行为n的质因数，用空格分隔；第二行为质因数的总个数。pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【样例输入】24pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【样例输出】2  2  2  3pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

                  4pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

 pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【参考代码】用递归算法分解质因数pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

  1. # include <bits/stdc++.h> 
  2. using namespace std; 
  3. // 定义递归函数，分解质因数 
  4. // n 为待分解数，m 为当前分解出来的数，cnt为计数器 
  5. void fen_jie(int n, int m, int cnt) { 
  6.     if (n == 1) { 
  7.         cout << endl << cnt; 
  8.         return; 
  9.     } 
  10.     if (n%m == 0) { 
  11.         cout << m << " "; 
  12.         cnt++; 
  13.         fen_jie(n/m, m, cnt); 
  14.     } else { 
  15.         fen_jie(n, m+1, cnt); 
  16.     } 
  17. } 
  18. int main() { 
  19.     int n; 
  20.     cin >> n; 
  21.     // 调用递归函数，从2开始分解，计数器从0开始 
  22.     fen_jie(n, 2, 0); 
  23.     return 0; 
  24. } 

【思考】pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

计数器变量cnt能不能在递归函数中声明，而不是通过参数传给递归函数？pyy100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

关 键 词

递归算法

相关教程

C++少儿编程（14）递归算法
C++少儿编程（13）递推算法
编写程序打印乘法表。
“鸡兔同笼”问题：笼子里有多只鸡和兔，从上面数有35个头，从下面数有94只脚，求鸡和兔各有多少只?
请编写程序统计表中每位学生的总分。
五(2)班准备挑选一名最高的学生参加学校篮球队，请编程帮助他们挑选。
求两个自然数m、n的最小公倍数。
求两个自然数x，y的最大公约数。
求水仙花数。所谓水仙花数是指一个三位数，例如：abc如果满足abc=a3＋b3＋c3，则称abc为水仙花数。例如：153=13＋53＋33，所以153就是水仙花数。
阶乘的定义：n!=n×(n-1)×(n-2)×…×4×3×2×1，请编程计算n!。

提示声明

  • 免责声明：本站资源均来自网络或者用户投稿，仅供用于学习和交流：如有侵权联系删除!

猜你喜欢

  • ©2016-2021 100150.com
  • 一个专注于青少年科技类考级、竞赛题库的网站
  • 提供电子学会python等级考试练习，C语言等级考试真题，
  • 蓝桥杯竞赛真题，信息学奥赛NOIP CSP-J/S真题等
  • 沪ICP备19038360号-4