一、递归
1，数学归纳法
（1）理论
1，如果想证明f(x)成立，先证明f(1)成立。
2，证明如果f(n)成立，那么f(n+1)也是成立的。
3，联合1，2，由此证明f(1)->f(n)成立的。
（2）例子
证明1+3+...+（2n-1） = n^2
1，假设f(1)是正确的.f(1) = 1^2 = 1
2，假设f(n-1)=（n-1）^2成立，f(n)=(n-1)^2 + 2n-1 = n^2 ，故f(n) = n^2 ，因为f(n-1)成立，故f(n)成立
3，联立1，2，由此证明f(1)->f(n)成立的。
2，递归设计的三个重要部分
1，给递归函数一个明确的语义信息（这个函数需要做什么）
2，实现边界条件的程序逻辑->f(1)，程序跳出判断（不能程序死循环吧）
3，假设递归函数的调用返回的结果是正确的，实现本层函数逻辑
3，程序设计例子
1，求阶乘n
int f(n)//1，先看此函数语义（f(n)是求n阶乘）
{
if(1 == n) return 1;//2，先看f(1)成立不。
return f(n-1) * n;//3，假设f(n-1)成立，f(n)成立，故成立（不需要知道f(n-1)是不是正确的，只需要假设就行了）这是数学归纳法的思想
}
2，小明吃桃子
1，题目是这样的小明买了一堆桃子不知道个数，第一天吃了一半的桃子，还不过瘾，又多吃了一个。以后他每天吃剩下的桃子的一半还多一个，到 n 天只剩下一个桃子了。小明想知道一开始买了多少桃子。
//第一步：语义信息,f(n)代表能吃n天的桃子数量
//第二步，边界条件。f(1) = 1，能吃1天的桃子只能是1
//第三步，能吃n天的桃子数量f(n) = (f(n-1)+1)*2
int f(int n)
{
if(n == 1) return 1;
return 2*(f(n-1) + 1);
}
int main()
{
int n = 0;
std::cin >> n;
std::cout << n << "天" <<" 能吃:" << f(n) << "个桃子" << std::endl;
return 0;
}
| 
发表于 2024-3-24 15:10
