计算概论习题课xiaogang.pptx

函数的递归问题Services分析与求解递归问题

Services分析与求解递归问题递归的定义一个过程或函数在其定义或说明中直接或间接调用自身的一种方法把一个大型复杂的问题层层的转换成一个与原问题相似的规模较小的问题来求解优点少量的程序就可以描述出解体过程所需要的重复计算大大减少了程序的代码量缺点运行效率较低见递归的定义

Services分析与求解递归问题递归问题的分析步骤考虑问题规模在初始情况下的求解初始情况通常情况下是已经条件或者可以通过非递归求解的函数考虑问题规模向较小规模的发展子问题的性质和原问题具有相同的性质，只是规模上比原问题有所缩小处理如何将子问题的解集合处理得到原问题的解常常是约束使用递规思维的瓶颈

Services分析与求解递归问题递归必须要有基本条件f(n)=f(n-1)+f(n-2)递归必须朝基本条件运行f(0)=0f(n)=f(n/3+1)+n–1;longfunction(intN)

{

if(N==0)return0;

??if(N1)

????returnfunction(N/3+1);

}longfunction(intN)

{

return(function(N-1)+function(N-2));

}递归问题的基本原则

分析与求解递归问题推理方法归纳推理：从特殊归纳出普遍特殊：所有观察到的乌鸦都是黑色的普遍：所有乌鸦都是黑色的演绎推理：从前提的已知的事实，“必然的”得出的推理前提1：所有公乌鸦都是黑色的，所有母乌鸦都是黑色的前提2：乌鸦要么是公的，要么是母的结论：所有乌鸦都是黑色基于公理的演绎推理总是正确的归纳推理在演绎上通常是无效的归纳是开放的，但是演绎是封闭的“对所有事情都坚持可靠的演绎上的正当有理的人会饿死”——大卫.休谟

分析与求解递归问题数学归纳方法数学归纳法的定义证明当n等于任意一个自然数时，某命题成立。证明当n=1时，命题成立假设当n=m,m为任意自然数时命题成立，推导出n=m+1时命题也成立注意，这里的推导必须是演绎推理方法。数学归纳法的变体从0以外的数字开始只针对偶数或者奇数递降归纳法超限归纳法将数学归纳法的第2步改成：假设当nm，m为任意自然数时命题成立，推导出n=m时命题也成立

分析与求解递归问题更一般的归纳法*良基关系对于类X上一个二元关系R被称为是良基的，当且仅当所有X的非空子集都有一个R-极小元，就是说对于X的每一个非空子集S，都存在一个S中的元素m使得对于所有S中的s，二元组(s,m)都不在R中??数学归纳法是良机归纳法的一种特殊情况0是自然数集合上后继关系的一个极小元，因此只需要证明对于n=0，命题成立(m,m+1)属于后继关系，因此假设n=m成立的时候，只需要证明n=m+1的时候也成立

分析与求解递归问题利用数学归纳思想求解递规问题最简单的数学归纳关系已知一个数组,对一个数组进行求和解法循环解法，依次遍历数组，求和，演绎推理思维intSum_Loop(int*array,intarray_size)

{intsum=0;for(inti=0;iarray_size;i++)sum+=array[i];returnsum;

}递规解法，假设前n-1项已经知道，那么加上第n项的值那么就是前n项的求和，归纳推理思想intSum_Recursion(int*array,intarray_index)

{if(array_index==0)returnarray[0];elsereturnarray[array_index]+Sum_Recursion(array,array_index–1);

}

分析与求解递归问题1063斐波那契数列描述第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1=a=20)菲波那契数列是指这样的数列:数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。

给出一个正整数a，要求菲波那契数列中第a个数是多少。输出n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数的大小输入

longfunction(intN)

{if(N==1||N==2)return1;

re