C++少儿编程(13)递推算法

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

  递推是一种通过已知条件和重复计算来解决问题的算法思想。它利用计算机高速运算的特征,通过循环结构从初始条件出发逐步推导出问题的解。Mcv100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

  递推算法的重点是通过分析,找到相邻项之间的关系,即“递推关系式”(简称“递推式”),然后循环迭代递推式,得到最终结果。Mcv100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

  二递推的实现步骤Mcv100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1、确定问题的已知条件;Mcv100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2、找出问题的递推式;Mcv100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3、选择合适的循环结构实现递推;Mcv100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
4、处理边界条件和特殊情况;Mcv100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5、输出结果。Mcv100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【例题-1】计算n的阶乘
阶乘(Factorial)是指一个自然数从1乘到它本身的积,用“!”表示。
例如:5的阶乘,记作“5!”。5! = 1*2*3*4*5。
特殊说明:1! = 1, 0! = 1。
【递推过程】
1、已知条件:1! = 1;
2、递推式:n! = (n-1)! * n;
3、选择循环结构:for循环;
4、边界:从1计算到n;
5、输出结果:n!。
【例题-1 示例程序】
  1. # include <bits/stdc++.h> 
  2. using namespace std; 
  3.  
  4. // 声明函数 factorial 用于计算整数n的阶乘,返回整数 
  5. int factorial(int n) { 
  6.     // 特殊情况处理(思考:省略这里的判断是否影响结果?) 
  7.     if (n == 1 || n == 0) return 1; 
  8.     // 声明计算结果 ret 
  9.     int ret = 1; 
  10.     for (int i = 1; i <= n; i++) { 
  11.         // 将 i 乘到 ret 中,得到 i! 
  12.         ret *= i; 
  13.     } 
  14.     return ret; 
  15.  
  16. int main() { 
  17.     // 声明阶乘数n,并输入n的值 
  18.     int n; 
  19.     cin >> n; 
  20.     // 调用函数计算阶乘,并输出结果 
  21.     cout << factorial(n) << endl; 
  22.     return 0; 
思考一下:
能否省略factorial函数里的特殊情况判断?

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

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

三斐波那契数列Mcv100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

斐波那契数列(Fibonacci)是一个著名的数列,又称“黄金分割数列”,其定义如下:
  • 第0项:f(0) = 0;
  • 第1项:f(1) = 1;
  • 从第2项开始,每一项都等于前两项之和:f(n) = f(n-1) + f(n-2)。
斐波那契数列前10项如下:Mcv100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
C++少儿编程(13)递推算法

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

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

【例题-2】计算斐波那契数列的第n项
【递推过程】
1、已知条件:f(0) = 0,f(1) = 1;
2、递推式:f(n) = f(n-1) + f(n-2);
3、选择循环结构:for循环;
4、边界:从第2项计算到第n项;
5、输出结果:第n项的值。
【例题-2 示例程序】
  1. # include <bits/stdc++.h> 
  2. using namespace std; 
  3.  
  4. // 声明函数 fibonacci 用于计算第n项的值,返回整数 
  5. int fibonacci(int n) { 
  6.     // 特殊情况处理 
  7.     if (n < 2) return n; 
  8.     // a、b、c 为相邻的3个数 
  9.     int a = 0, b = 1, c; 
  10.     // 从第2项计算到第n项 
  11.     for (int i = 2; i <= n; i++) { 
  12.         // 将前两项的和存入第三项 
  13.         c = a + b; 
  14.         // 更新前两项的值(依次后移) 
  15.         a = b; 
  16.         b = c; 
  17.     } 
  18.     return c; 
  19.  
  20. int main() { 
  21.     // 声明项数n,并输入n的值 
  22.     int n; 
  23.     cin >> n; 
  24.     // 调用函数计算斐波那契数列的第n项,并输出结果 
  25.     cout << fibonacci(n) << endl; 
  26.     return 0; 

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

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

 

类似斐波那契数列的问题有很多,上楼梯问题就是其中之一。Mcv100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【例题-3】上楼梯问题
假设楼梯共有n个台阶(1<=n<=100),上楼梯时,可以一步上一个台阶,也可以一步上两个台阶,请问爬上第n个台阶共有多少种不同的走法?
【问题分析】
从下往上走比较麻烦,不妨使用逆向思维,倒过来思考:
如果爬上第n个台阶,需要先爬上第n-1或n-2个台阶,所以爬上第n个台阶的走法等与爬上第n-1个台阶和n-2个台阶的走法总和。
假设用f(n)表示爬上第n个台阶的走法,则:f(n) = f(n-1) + f(n-2)。
前两项之和等于第三项,这种计算方式与斐波那契数列一样,唯一不同的是起始项的数值会有所不同。
如果有一个台阶,共有1种走法;如果有两个台阶,共有2种走法。
【递推过程】
1、已知条件:f(1) = 1,f(2) = 2;
2、递推式:f(n) = f(n-1) + f(n-2);
3、选择循环结构:for循环;
4、边界:从第3项计算到第n项;
5、输出结果:爬上第n个台阶的不同走法。
【例题-3 示例程序】
  1. # include <bits/stdc++.h> 
  2. using namespace std; 
  3.  
  4. // 声明函数 fib 计算爬上第 n 个台阶的不同走法 
  5. int fib(int n) { 
  6.     // 特殊情况处理 
  7.     if (n < 3) return n; 
  8.     // a、b、c 为相邻三个台阶的不同走法 
  9.     int a, b, c; 
  10.     a = 1;  // 第一个台阶的走法是 1 种 
  11.     b = 2;  // 第二个台阶的走法是 2 种 
  12.     // 使用 for 循环,从第 3 项计算到第 n 项 
  13.     for (int i = 3; i <= n; i++) { 
  14.         c = a + b;  // 计算第三个台阶的走法 
  15.         a = b;      // 更新第一个台阶的走法 
  16.         b = c;      // 更新第二个台阶的走法 
  17.     } 
  18.     return c;       // 返回第三个台阶的走法 
  19.  
  20. int main() { 
  21.     // n 为楼梯的台阶数量 
  22.     int n; 
  23.     // 输入台阶数量 n 
  24.     cin >> n; 
  25.     // 调用函数 fib 计算爬到第 n 个台阶的不同走法,并输出结果 
  26.     cout << fib(n) << endl; 
  27.     return 0; 

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

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

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

错位排序问题Mcv100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

 

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

错位排序问题(简称“错排问题”)是指排列中没有任何元素出现在其原始位置上的排列方式。
【例题-4】信封问题
有n封信和n个信封,如果所有的信都装错信封,有几种装法?
【问题分析】
  • 任取一封信,装错的情况:n-1。
  • 在剩余的信中,再任取一封信,装错的情况有两种:
    1、与上一封信位置互换,接下来就变成了n-2封信的错排问题;
    2、不与上一封信位置互换,接下来就成了n-1封信的错排问题。
  • 总结递推式:f(n) = (n-1) * [f(n-1) + f(n-2)]。
  • 根据递推式,至少确认前两项,才能计算后续项:
    1、当只有一封信和一个信封的时候,装错的情况为0,即:f(1) = 0;
    2、当有两封信和两个信封的时候,装错的情况为1,即:f(2) = 1。
【递推过程】
1、已知条件:f(1) = 0,f(2) = 1;
2、递推式:f(n) = (n-1) * [f(n-1) + f(n-2)];
3、选择循环结构:for循环;
4、边界:从第3项计算到第n项;
5、输出结果:n封信的错拍情况。
【例题-4 示例程序】
  1. # include <bits/stdc++.h> 
  2. using namespace std; 
  3.  
  4. // 声明函数 misplaced_sort 计算n封信的错排情况 
  5. int misplaced_sort(int n) { 
  6.     // 特殊情况处理 
  7.     if (n < 3) return n - 1; 
  8.     // a、b、c 为相邻的三项 
  9.     int a = 0, b = 1, c; 
  10.     // 从第3项计算到第n项 
  11.     for (int i = 3; i <= n; i++) { 
  12.         // 根据递推式计算第三项 
  13.         c = (i - 1) * (a + b); 
  14.         // 更新前两项的值(依次后移) 
  15.         a = b; 
  16.         b = c; 
  17.     } 
  18.     return c; 
  19.  
  20. int main() { 
  21.     // 声明项数n,并输入n的值 
  22.     int n; 
  23.     cin >> n; 
  24.     // 调用错排函数计算n封信的错排情况,并输出结果 
  25.     cout << misplaced_sort(n) << endl; 
  26.     return 0; 

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

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

 

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

倒推是指从后往前反向递推。前面都是从前往后,正向递推。仅仅是递推方向的不同,递推方法相同。
【例题-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,(用后项表示前项)
将n换成n-1得:f(n-1) = 2*f(n) + 2*(n-1)。(换元操作)
【递推过程】
1、已知条件:f(n) = n;
2、递推式:f(n-1) = 2*f(n) + 2*(n-1);(直接用整理后得递推式也行,不过要注意循环条件的起始值)
3、选择循环结构:for循环;
4、边界:从第n-1项计算到第1项;
5、输出结果:第1项的值。
【例题-5 示例程序】
  1. # include <bits/stdc++.h> 
  2. using namespace std; 
  3.  
  4. // 声明一维数组存每个施工小队面临的工程数量 
  5. int a[11]; 
  6. int n;  // n 为施工小队的数量 
  7.  
  8. int main() { 
  9.     cin >> n;   // 输入工程队数量:n 
  10.     a[n] = n;   // 初始化第 n 工程队面临的任务数量 
  11.     // 使用 for 循环从 n~1 倒序迭代 
  12.     for (int i = n; i > 1; i--) { 
  13.         // 根据递推式倒推计算前一项的值 
  14.         a[i-1] = 2 * a[i] + 2 * (i - 1); 
  15.     } 
  16.     // 第 1 工程队面临的任务数量就是工程总量 
  17.     cout << a[1] << endl; 
  18.     return 0; 

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

关 键 词

递推算法

相关教程

提示声明

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

猜你喜欢