递归与深度优先搜索算法ppt课件.ppt

《递归与深度优先搜索算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3讲递归与深度优先搜索算法一.递归"从前有座山山上有座庙,庙里有个老和尚,老和尚在给小和尚讲故事:"从前有座山山上有座庙,庙里有个老和尚,老和尚在给小和尚讲故事:"从前有座山山上有座庙,庙里有个老和尚,老和尚在给小和尚讲故事:……"从前有座山山上有座庙,庙里有个老和尚,老和尚在给小和尚讲故事:这就是递归递归的概念：一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).满足某个条件后递归终止。递归的关键：1.确定递归公式（关系）2.确定边界(终止)条件当递归没有到达边界终止时，继续向前，直至边界才返回。Functi

2、on函数名（参数）：类型；Procedure过程名（）参数；Int函数名（参数）；Void函数名（参数）；过程过程过程……过程递归结束小猴摘了很多桃子。第一天吃了一半又多吃一个；第二天又吃掉剩下的一半再多吃一个；……以后每天都是吃前一天剩下的一半再多一个。如此下去，到第十天恰好还剩一个桃子。问第一天小猴摘了多少桃子？【例1】猴子吃桃问题关系：第i天的桃子=(第i+1天的桃子+1)*2i=10时，有1只桃子。f(10)=1f(i)=2*(f(i+1)+1)求f(1)=?方法1：varn:longint;functionf(i:longint):

3、longint;beginifi=10thenf:=1elsef:=(f(i+1)+1)*2;end;beginn:=f(1);writeln(n);end.方法1：varn:longint;functionf(i:longint):longint;beginifi=10thenexit(1);exit((f(i+1)+1)*2);end;beginn:=f(1);writeln(n);end.#include#includeusingnamespacestd;intf(inti){if(i==10)ret

4、urn1;return2*(f(i+1)+1);}intmain(){cout<1时递归的执行过程varn:integer;functionf(i:integer):integer;beginifi=1thenf:=

5、1elsef:=i*f(i-1);end;beginreadln(n);writeln(f(n));end.varn:integer;functionf(i:integer):integer;beginifi=1thenexit(1);exit(i*f(i-1));end;beginreadln(n);writeln(f(n));end.【例3】求最大公约数输入a和b，输出a和b的最大公约数。如：输入：10075输出：25欧几里德算法（又称辗转相除法）用于计算两个正整数a，b的最大公约数。一般把a和b的最大公约数记为gcd(a,b)。公式：g

6、cd(a,b)=gcd(b,amodb)gcd(a,0)=a如：gcd(100,75)=gcd(75,25)=gcd(25,0)=25；【方法1】vara,b,r:longint;beginreadln(a,b);whileb>0dobeginr:=amodb;a:=b;b:=r;end;writeln(a);end.【方法2】递归vara,b:longint;functiongcd(a,b:longint):longint;beginifb=0thenexit(a);exit(gcd(b,amodb));end;beginreadln(a,

7、b);writeln(gcd(a,b));end.varn:longint;proceduref(n:longint);beginifn>0thenbeginf(ndiv2);write(nmod2);end;end;beginreadln(n);f(n);End.#include#includeusingnamespacestd;voiddfs(inti){if(i>0){dfs(i/2);printf("%d",i%2);}}intmain(){intn;scanf("%d",&n);dfs(n);re

8、turn0;}n=204.读程序写结果varn:longint;proceduredfs(i:longint);beginwriteln(i);dfs(i+1);e