递归与深度优先有哪些信誉好的足球投注网站算法.pptVIP

2014年 赵宗昌 2014年 赵宗昌 2014年 赵宗昌 第3讲 递归与深度优先有哪些信誉好的足球投注网站算法 一. 递归 从前有座山山上有座庙,庙里有个老和尚,老和尚在给小和尚讲故事: 从前有座山山上有座庙,庙里有个老和尚,老和尚在给小和尚讲故事: 从前有座山山上有座庙,庙里有个老和尚,老和尚在给小和尚讲故事:…… 从前有座山山上有座庙,庙里有个老和尚,老和尚在给小和尚讲故事: 这就是递归 递归的概念： 一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数). 满足某个条件后递归终止。 递归的关键： 1.确定递归公式（关系） 2.确定边界(终止)条件 当递归没有到达边界终止时，继续向前，直至边界才返回。 Function 函数名（参数）：类型； Procedure 过程名（）参数； Int 函数名（参数）； Void 函数名（参数）； 过程 过程 过程 …… 过程 递归结束 小猴摘了很多桃子。 第一天吃了一半又多吃一个； 第二天又吃掉剩下的一半再多吃一个； …… 以后每天都是吃前一天剩下的一半再多一个。 如此下去，到第十天恰好还剩一个桃子。 问第一天小猴摘了多少桃子？ 【例1】猴子吃桃问题 关系： 第i天的桃子=(第i+1天的桃子 +1)*2 i=10时 ，有1只桃子。 f(10)=1 f(i)=2*(f(i+1)+1) 求 f(1)=? 方法1： var n:longint; function f(i:longint):longint; begin if i=10 then f:=1 else f:=(f(i+1)+1)*2; end; begin n:=f(1); writeln(n); end. 方法1： var n:longint; function f(i:longint):longint; begin if i=10 then exit(1); exit((f(i+1)+1)*2); end; begin n:=f(1); writeln(n); end. # include iostream # include cstdio using namespace std; int f(int i){ if (i==10) return 1; return 2*(f(i+1)+1); } int main() { coutf(1); return 0; } 方法2： var a:array[1..10] of longint; i:longint; begin a[10]:=1; for i:=9 downto 1 do a[i]:=(a[i+1]+1)*2; writeln(a[1]); end. 【例2】：计算n! 可用公式如下: f(n)=1 当 n=1 时?? f(n)=n*f(n-1) 当n1时 递归的执行过程 var n:integer; function f(i:integer):integer; begin if i=1 then f:=1 else f:=i*f (i-1); end; begin readln(n); writeln(f(n)); end. var n:integer; function f (i:integer):integer; begin if i=1 then exit(1); exit(i*f (i-1)); end; begin readln(n); writeln(f (n)); end. 【例3】求最大公约数 输入a和b，输出a和b的最大公约数。 如： 输入：100 75 输出：25 欧几里德算法（又称辗转相除法） 用于计算两个正整数a，b的最大公约数。 一般把a和b的最大公约数记为gcd(a,b)。 公式： gcd(a,b)=gcd(b,a mod b) gcd(a,0)=a 如：gcd(100,75)=gcd(75,25)=gcd(25,0)=25； 【方法1】 var a,b,r:longint; begin readln(a,b); while b0 do begin r:=a mod b; a:=b; b:=r; end; writeln(a); end.