给个网站做填空题,上海企业登记一网通办,竞价网站如何设计,网站空间域名能不能自己续费递归
在编程中#xff0c;我们把函数直接或者间接调用自身的过程叫做递归。
递归处理问题的过程是#xff1a;通常把一个大型的复杂问题#xff0c;转变成一个与原问题类似的#xff0c;规模更小的问题来进行求解。
递归的三大要素
函数的参数。在用递归解决问题时我们把函数直接或者间接调用自身的过程叫做递归。
递归处理问题的过程是通常把一个大型的复杂问题转变成一个与原问题类似的规模更小的问题来进行求解。
递归的三大要素
函数的参数。在用递归解决问题时要合理地去设计函数的参数达到当前问题与子问题之间的变化可以通过参数进行准确地描述。递推关系。要能够找到当前问题与子问题之间的联系能够用子问题去描述当前问题的解。递归出口(边界条件)。要找到问题的边界避免出现无限递归的情况。每次我们在设计递归函数时第一步就是先判断当前是否已经到达递归出口若未到达则再继续递归。
偶数的递归定义
现在我们采用递归的方式来定义偶数
0是一个偶数。一个偶数与2的和是一个偶数。
这里我们在定义偶数时就使用了偶数的这个概念。
证明10是偶数
现在我们需要使用刚才的定义来证明10是否为偶数。
因为1082根据第二条定义可以知道一个偶数与2的和是一个偶数现在我们只需要证明8是否是偶数即可得到结论。
我们现在用f(10)表示证明10是否为偶数的函数。
则整个的证明过程如下
f(10) - f(8) - f(6) - f(4) - f(2) - f(0)最终我们的问题变成证明0是否为偶数而定义中已经给出0是偶数所以我们可以得到2是偶数...依次类推。
f(0) - f(2) - f(4) - f(6) - f(8) - f(10) 。
得出10是偶数。
参考代码
#includebits/stdc.h
using namespace std;
bool f(int n){if(n0)//如果n0,则n是偶数return true;return f(n-2); //否则证明n-2是否为偶数
}
int main(){int n;cinn;coutf(n);return 0;
} 输入奇数会怎么样
输入奇数就会无限递归下去因为我们并没有为n是奇数的情况设计递归出口。如果n7就会去求n5、3、1、-1、-3...一直递归下去。
我们可以在函数中添加针对奇数情况的递归出口。当n1时返回false
训练递归求和
请使用递归的方法计算123...n的和。
【输入描述】1行输入一个整数n。
【输出描述】1行输出一个整数表示求和的结果。
【样例输入】5
【样例输出】15
参考代码
#includebits/stdc.h
using namespace std;
int sum(int n){if(n1)return 1;return sum(n-1)n;
}
int main(){int n;cinn;coutsum(n);return 0;
}训练汉诺塔问题
汉诺塔河内塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定在小圆盘上不能放大圆盘在三根柱子之间一次只能移动一个圆盘。 问题建模
我们可以使用4个参数去描述汉诺塔问题。
void Hanoi(int n,char a,char b,char c)
n表示移动的是第n号盘子
a,b,c分别表示汉诺塔问题中的三个柱子。
我们称a,b,c分别为起始柱辅助柱目标柱。
递归关系
根据游戏规则想要移动n号盘则需要先将n-1号盘从a柱移动到b柱。
此时我们的问题变成Hanoi(n-1, a, c, b)
即将n-1号盘从a柱出发借助c柱移动到b柱。
在这次移动的过程中a,c,b分别为起始柱辅助柱目标柱。
将n-1号盘子移到b柱之后我们就可以将n号盘子直接从a移动到c,即a-c。
到这一步我们完成了第n号盘子的移动。
接下来我们还需要将n-1号盘子(在b柱)移动到c柱上。
即Hanoi(n-1, b, a, c)
在这次移动的过程中b,a,c分别为起始柱辅助柱目标柱。
边界条件
当问题变成只有一个盘子时我们就无须借助辅助柱
直接从a移动到c柱即可。
参考代码
void Hanoi(int n,char a,char b,char c){if(n1){coutn:a-cendl;return ;}else{Hanoi(n-1,a,c,b);coutn:a-cendl;Hanoi(n-1,b,a,c);}
}
int main(){Hanoi(3,a,b,c);return 0;
} 从C入门到算法再到数据结构查看全部文章请点击http://www.bigbigli.com/
