3算法第三章递归.ppt

range(A,1,3) If 1=3 then print(A) else for i ?1 to 3 do A(1) ? A(i); call range(A,2,3) 略 A={a, b, c} abc 1) i=1, a?a A={a,b,c} 2) i=2, b?b A={a,b,c} acb 3) i=3, b?c A={a,c,b} bac 4) i=2, a?b A={b,a,c} 5) i=2, a?a A={b,a,c} bca 6) i=3, a?c A={b,c,a} range(A,2,3)… for i ?2 to 3 do A(2) ? A(i); call range(A,3,3) 略 range(A,3,3) If 3=3 print(A) 略 7) i=3, a?c A={c,b,a} cba 8) i=2, b?b A={c,b,a} cab 9) i=3, b?a A={c,a,b} 例3.7 自然数拆分 任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和，试求n的所有拆分(用不完全归纳法)。 n=2 2 = 1+1 n=3 3 = 1+2 = 1+1+1 n=4 4 = 1+3 = 1+1+2 = 1+1+1+1 = 2+2 n/2 n=7 7= 1+6 = 1+1+5 = 1+1+1+4 = 1+1+1+1+3 = 1+1+1+1+1+2 = 1+1+1+1+1+1+1 = 1+1+1+2+2 = 1+1+2+3 = 1+2+4 = 1+2+2+2 = 1+3+3 = 2+5 = 2+2+3 = 3+4 实现思想： 拆分可以分为n/2大类； 每类第一行元素是a[1]←i,a[2]←n-i； 对a[k]进行拆分,k初值为2。 若a[k-1]≤a[k]/2 ，a[k]分成a[k-1]到a[k]/2类。 procedure split(t) for k ?1 to t do write(A(k)) ; repeat j ?t; L ? A(j) for i ? A(j?1) to L/2 do A(j) ? i; A(j+1) ? L?i ; call split(j+1) repeat end split procedure main(n) for i ? 1 to n/2 do A(1) ? i; A(2) ? n?i; call split(2) repeat end main 自然数拆分（正整数拆分）算法 输出已产生的 一种拆分 本次拆分的起始位置 本次拆分的数值 split(2) Print:1,3 j=2; L=3 i在1~3/2之间 i=1: A[2]=1; A[3]=2; main(4) i在1~4/2之间 i=1: A[1]=1; A[2]=3; i=2: A[1]=2; A[2]=2; 1 split(3) Print:1,1,2 j=3; L=2 i在1~2/2之间 i=1: A[3]=1; A[4]=1 2 split(4) Print:1,1,1,1 j=4; L=1 i在1~1/2之间 3 split(2) Print:2,2 j=2; L=2 i在2~2/2之间 4 拆分算法的例子 第三章 递归算法 一个递归问题 从前有座山，山上有座庙，庙里有个老和尚讲故事，讲的是 从前有座山，山上有座庙，庙里有个老和尚讲故事，讲的是 从前有座山，山上有座庙，庙里有个老和尚讲故事，讲的是 …… …… 调用自己 目录 3.1 递归算法实现机制 3.2 递归转非递归(略) 3.3 递归算法设计 3.4 递归关系式的计算(略) 3.1 递归算法实现机制 子程序实现原理 子程序调用的一般形式 值回传方式 子程序调用的内部操作 递归程序实现原理 子程序调用的一般形式 主程序 Cal