普及层次第三讲递归递推分治-普及班.pdfVIP

第三讲第三讲 递归、递推、分治递归、递推、分治 递归、递推、分治 2 0 1 6 江苏省青少年信息学奥林匹克冬令营普及层次教学 第三讲第三讲 递归、递推、分治递归、递推、分治 一、递归一、递归 2 0 1 6 江苏省青少年信息学奥林匹克冬令营普及层次教学 第三讲第三讲 递归、递推、分治递归、递推、分治 递归 描述递归定义的函数或过程称为递归算法。 两个条件： 1.1.递归式（递归关系）；递归式（递归关系）； 2.递归终止条件。 递归表达式是解题的关键！ 2 0 1 6 江苏省青少年信息学奥林匹克冬令营普及层次教学 第三讲第三讲 递归、递推、分治递归、递推、分治 递归应用：菲波拉契数列 1,1,2,3,5,8,13,21… Function f(x:integer):integer; Begin if if (x=0)or(x=1) then (x=0)or(x=1) then f:=1 else f:=f(x-1)+f(x-2); End; 2 0 1 6 江苏省青少年信息学奥林匹克冬令营普及层次教学 第三讲第三讲 递归、递推、分治递归、递推、分治 例、 输出Fibonacci数列的第n项, n较大时,第n项的 数会很大,故只需输出f(n) mod 10000的值即可。 const max=1000; var a:array[1 max] of integer; function f(n:integer):integer; begin 采用记忆化采用记忆化采用记忆化采用记忆化 if a[n]0 then f:=a[n]if a[n]0 then f:=a[n] else if n=1 then begin a[1]:=1;f:=1;end else if n=2 then begin a[2]:=1; f:=1;end else begin a[n]:=(f(n-1)+f(n-2)) mod 10000; f:=a[n]; end; end; 2 0 1 6 江苏省青少年信息学奥林匹克冬令营普及层次教学 第三讲第三讲 递归、递推、分治递归、递推、分治 例 背包问题 问题一：给定背包容量W和物体种类N ，以及每种 物体的重量W ，每种物体只有一个，问是否能将背 i 包装满。若能，输出YES ，否则输出NO。 样例输入：样例输入：5 45 4 1 2 3 4 样例输出：YES 2 0 1 6 江苏省青少年信息学奥林匹克冬令营普及层次教学 分析 第三讲第三讲 递归、递推、分治递归、递推、分治 对第n个物体,只有两种情况, 即取或者不取。 若取, 原问题就转化为search(w-a[n],n- 1), 若不取, 则转