nbhkdz.com冰点文库

普及层次第三讲递归递推分治


递归、递推、分治
南京第二十九中学 林晖

例3.1.1 背包问题
问题一:给定背包容量W和物体种类N,以及 每种物体的重量Wi,每种物体只有一个,问 是否能将背包装满。请统计箱装满的方案数

样例输入:5 4 1 2 3 4
样例输出:2

分析
对第n个物体,只有两种情况,

即取或者不取。 若取, 原问题就转化为search(w-a[n],n-1), 若不取, 则转化为search(w,n-1)。 若 w=0 则说明能够装满。
procedure search(w,n:integer); begin if w=0 then p:=p+1; if n>=1 then begin search(w-a[n],n-1); search(w,n-1) ; end; end;

递归转化为非递归
? 递归是算法设计中的一种重要方法, 它的优势在于能用有限的语句来定义对 象的无限集合。对于某些问题,用递归 处理起来简单明了,程序结构清晰、精 练,但是由于递归处理的过程需占用大 量的机时和空间,因而程序的效率低, 在必要的时候,需要将递归转化为非递 归来处理。

非递归算法一般要比递归算法效率高得多。

求斐波那契数列中的第n个数
用递归的方法
用非递归的方法

begin function fib(n:integer):integer; f[0]:=0; begin f[1]:=1; if n=0 then fib:=0 readln(n) ; else if n=1 then fib:=1 for m:=1 to n do fib:=fib(n-1)+fib(n-2); f[m]:=f[m-1]+f[m-2]; end; writeln(‘f[’,n,‘]=’,f[n]) end.

二、递推
递推算法:对于一个有规律的数列,我们可 以借助已知的项,利用特定的关系逐项推算出 它的后继项的,……,如此反复,直到找到所 需的那一项为止,这样的方法称为递推算法。
递推算法的首要问题是得到相邻的数据项间的关 系(即递推关系)。

解决递推问题的一般步骤
?建立递推关系式 ?确定边界条件

?递推求解

例3.2.1 NICOMACHUS (尼克马库斯)定理 [问题描述] NICOMACHUS定理:任何一个整数的立方都可以表 示成一串奇数的和,例如: 13=1 23=3+5=8 33=7+9+11=27 43=13+15+17+19=64 ...... 表示的规律: 分析:用 F(n) 表示 n 的3次方的数。 n为奇数: F(3) = (32-2)+32+(32+2) = 3*32=27 n为偶数: F(4) = ...... ……………..=4*42=64

例3.2.2 :切煎饼
王小二自夸刀工不错,有人放一张大的煎 饼在砧板上,问他:“饼不许离开砧板, 切100刀最多能分成多少块?”
找规律,如下图:

令q(n)为切n刀能分成的块数,从图中可见: q(1)=1+1=2 q(2)=1+1+2=4 q(3)=1+1+2+3=7 q(4)=1+1+2+3+4=11 在切法上让每两条线都有交点,则有 q(n)=q(n-1)+n q(0)=1

化简后:

q(n) = n(n+1)/2 +1;

例3.2.3 平面分割 设平面上有n条封闭曲线, 而任何两条封闭曲线恰好相交于两点,且任 何三条封闭曲线不相交于同一点,求这些封 闭曲线把平面分割成的区域个数。
14

2
1 1 2 3 4

8 1 10 11 6 8 9 2 1

6 3 4 7 12

3
5 4 7

2

5 13

n=1

n=2

n=3

n=4

[问题分析] 设an为n条封闭曲线把平面分割成的区域个数。 由上图可以看 出: a1=2 a2-a1=2 a2=4 a3-a2=4 a3=8 a4-a3=6 a4=14 (比较困难了?) a5-a4=8 a5=22 (很困难?) …… …… an-an-1=2(n-1)

f(1)=2 f(n)=f(n-1)+2(n-1)

例3.2.4 设有一个共有n级的楼梯,某人每 步可走1级,也可走2级,也可走3级,用递推 公式给出某人从底层开始走完全部楼梯的走法。 例如:当n=3时,共有4种走法,即 1+1+1,1+2,2+1,3。 用递推公式给出的某人从底层开始走完 全部楼梯的走法为(用F(N))记录不同方案数: F(1)=1 F(2)=2 F(3)=4 F(n)=F(n-3)+F(n-2)+F(n-1) (n≥4)

例3.2.5 汉诺塔问题,现在要求把全部 圆盘从A柱移到C柱的最小移动步数h(n)。
H(1)=1 H(2)=2*h(1)+1=3 H(3)=2*h(2)+1=7 H(4)=2*h(3)+1=15 H(5)=2*h(4)+1=31 …… h(n) =2*h(n-1)+1= 2^n-1

拓展:若是汉诺双塔呢?即:假如现在每 种大小的盘子都有两个,并且是相邻的, 设盘子个数为2n,问最小移动的步数? ⑴ 假如不考虑相同大小盘子的上下要多 少次移动,设移动次数为J(n);
分析: ⑴ 中的移动相当于是把前一个问题中的每个 盘子多移动一次,也就是: J(n) = 2*H(n) = 2*(2^n - 1) = 2^(n+1)-2

讨论交流:递归递推的关系
1、相互转换: 递归转递推 函数(过程)内部的“子过程”放 到循环体,边界相同 2、但是递推一定优越递归吗? 比如:快排换成递推如何实现 实现是可以的,用数组存放状态,模拟堆栈,但 要将递归转化递推,编写代码反而不易 总结:不能片面的说成递推的效率优于递归,得 会灵活应用,而且往往做题时,递归或递推的思路才 更重要。

求数组元素
[问题描述] 给出任意一个自然数 N (N≤100),输出满足下列条件的数 组元素及不同方案数,条件是: <1> 数组元素由各不相同自然数组成; <2> 数组元素的最后一个元素必为N; <3> 每一个数组元素都不小于它前面一个元素的平方 ( 第 一个元素除外); <4> 数组中包含的元素个数可不相同,但至少要有一个元 素。 又如: 例如: N=5 N=1 输入: N (不用判错) (1) 输出: 一个 (不同方案数) (5) (1,5) K=1 (以K记录不同的方案数) (1,2,5) (2,5) K=4

[问题分析]下面,我们罗列出N取不同值时的方案,以 便从中找到解决问题的方法。 N=1 K(1)=1 (1) N=2 K(2)=2 (2), (1,2) N=3 K(3)= 2 (3),(1,3) N=4 K(4)= 4 (4),(1,4),(1,2,4),(2,4) N=5 K(5)=4 (5),(1,5),(1,2,5),(2,5) N=6 K(6)= 4 (6),(1,6),(1,2,6),(2,6) N=9 K(9)=6 (9), (1,9), (1,2,9), (1,3,9),(2,9),(3,9)

不难看出: K(2)=K(1)+1 K(3)=K(1)+1 K(4)= K(2)+K(1)+1 K(5)= K(2)+K(1)+1 ...... K(9)= K(3)+K(2)+K(1)+1 由此,总结出递推公式: K(N)= K(M)+K(M-1)+......+K(1)+1, 其中M=取整(开平方SQRT(N)或 SQR(N)(BASIC)。

[算法分析] 利用递推公式进行求解,因为N 不大于100, 因此定义数组时10个下标变量就足够了。 为了避免反复过程调用,我们采用以下主要步骤: 1、先利用双重循环将10以内的方案数计算后,存放在数组A 中; 2、输入N; 3、在一重循环中,利用公式直接求和。 4、输出方案数K。 [程序清单] 略 [运行数据及测试结果] N=2 K=2 N=7 K=4 N=16 K=10 N=20 K=10 N=100 K=38

三、分治
分治法的设计思想是:

将一个难以直接解决的大问题,分割成一些 规模较小的相同问题,以便各个击破,分而治之。 凡治众如治寡,分数是也。
----孙子兵法

递归与分治基本原理
对这k个子问题分别求解。如果子问题的规模仍然不够小, 则再划分为k个子问题,如此递归的进行下去,直到问题 规模足够小,很容易求出其解为止。

T(n)

=

n

T(n/2)

T(n/2)

T(n/2)

T(n/2)

递归与分治基本原理
将求出的小规模的问题的解合并为一个更大规模的问题 的解,自底向上逐步求出原来问题的解。

T(n)
n/2

=
n/2

n
n/2 n/2

T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4

递归的概念
直接或间接地调用自身的算法称为递归算法。用函数 自身给出定义的函数称为递归函数。 由分治法产生的子问题往往是原问题的较小模式,这 就为使用递归技术提供了方便。在这种情况下,反复 应用分治手段,可以使子问题与原问题类型一致而其 规模却不断缩小,最终使子问题缩小到很容易直接求 出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟,经常同时应用在算法设 计之中,并由此产生许多高效算法。

递推与递归
递归与递推表面看来是相逆的过程,其实也是相 似的,最终的计算都是从小算到大。 递推的使用环境要求高导致了递推的高效性,递 推没有重复计算什么数据,保持了高效。 递归大多数会重复计算子问题,导致时间浪费, 所以一般不要使用过深的递归,甚至会空间溢出。 但是也不能说递推好,递归差,因为递归却能解决 很多递推做不到的事情,在某些特定的环境下也能 实现高效,并且递归容易使用。我们要就事论事!

例3.3.1 :找出伪币
给你一个装有1 6枚硬币的袋子。1 6枚硬币中有一个是伪造的,并且那个 伪造的硬币比真的硬币要轻一些。你的 任务是找出这枚伪造的硬币。 为了帮助你完成这一任务,将提供 一台可用来比较两组硬币重量的仪器, 比如天平。利用这台仪器,可以知道两 组硬币的重量是否相同。

方法1
任意取1枚硬币,与其他硬币进行 比较,若发现轻者,这那枚为伪币。 最多可能有15次比较。

方法2
将硬币分为8组,每组2个,每组比 较一次,若发现轻的,则为伪币。 最多可能有8次比较。

方法3

分析
上述三种方法,分别需要比较15次,8次,4 次,那么形成比较次数差异的根本原因在 哪里? 方法1:每枚硬币都至少进行了一次比较,而 有一枚硬币进行了15次比较 方法2:每一枚硬币只进行了一次比较 方法3:将硬币分为两组后一次比较可以将 硬币的范围缩小到了原来的一半,这样充 分地利用了只有1枚伪币的基本性质。

例3.3.2 :金块问题

有一个老板有一袋金块。每个月将有两名雇员会 因其优异的表现分别被奖励一个金块。按规矩, 排名第一的雇员将得到袋中最重的金块,排名第 二的雇员将得到袋中最轻的金块。根据这种方式, 除非有新的金块加入袋中,否则第一名雇员所得 到的金块总是比第二名雇员所得到的金块重。如 果有新的金块周期性的加入袋中,则每个月都必 须找出最轻和最重的金块。假设有一台比较重量 的仪器,我们希望用最少的比较次数找出最轻和 最重的金块。

方法1
假设袋中有n 个金块。可以用函数M a x通过 n-1次比较找到最重的金块。找到最重的金块 后,可以从余下的n-1个金块中用类似的方法 通过n-2次比较找出最轻的金块。这样,比较 的总次数为2n-3。 算法如下:
max:=a[1];min:=a[1]; for i:=2 to n do {2n-2次比较} begin if a[i]>max then max:=a[i]; if a[i]<min then min:=a[i]; end ;

max:=a[1]; for i:=2 to n do {n-1次比较,从n个元素中找到 最大的} if a[i]>max then begin max:=a[i]; j:=i end; for i:=j+1 to n do a[i-1]:=a[i]; {去掉最大的数a[j]} min:=a[1]; for i:=2 to n-1 do {n-2次比较,从剩下的元素 中 if a[i]>max then min:=a[i]; 找最小的}

找金块的示例图

方法2:
n≤2,识别出最重和最轻的金块,一次比较就 足够了。 n>2,第一步,把这袋金块平分成两个小袋A 和B。第二步,分别找出在A和B中最重和最轻 的金块。设A中最重和最轻的金块分别为HA 与LA,以此类推,B中最重和最轻的金块分别 为HB 和LB。第三步,通过比较HA 和HB, 可以找到所有金块中最重的;通过比较LA 和 LB,可以找到所有金块中最轻的。在第二步 中,若n>2,则递归地应用分而治之方法。

分治过程

比较过程

分析
从图例可以看出,当有8个金块的时候,方法1需 要比较15~16次,方法2只需要比较10次,那么形成 比较次数差异的根本原因在哪里? 其原因在于方法2对金块实行了分组比较。 对于N枚金块,我们可以推出比较次数的公式: 假设n是2的次幂,c(n)为所需要的比较次数。 方法1: c(n)=2n-1 方法2:c(n) = 2c(n/2 ) + 2。 由c(2)=1, 使用迭代方法可知c(n) = 3n/2 - 2。在本 例中,使用方法2比方法1少用了2 5%的比较次数。

分治思想
由分治法所得到的子问题与原问题具有相同的类型。 如果得到的子问题相对来说还太大,则可反复使用 分治策略将这些子问题分成更小的同类型子问题, 直至产生出不用进一步细分就可求解的子问题。 分治求解可用一个递归过程来表示。 要使分治算法效率高,关键在于如何分割?一般地, 出于一种平衡原则,总是把大问题分成K个规模尽 可能相等的子问题,但也有例外,如求表的最大最 小元问题的算法,当n=6时,等分定量成两个规 模为3的子表L1和L2不是最佳分割。

数据查找

例3.3.3 查找一个数是否属于 Fibonacci数列前n项,若在,则输出 属于第几项,否则输出-1 样例输入:8 样例输出:6
方法1:顺序查找 方法2:二分查找

const n=10; var a :array[1..n+1] of integer; x:integer; begin for i:=1 to n do read(a[i]); readln; readln(x); a[n+1]:=x; i:=1 ; while a[i]<>x do i:=i+1; if i=n+1 then writeln(‘not found’) else writeln(‘found in:’,i); end.

二分查找基本思想
n个从小到大排好序的整数,假设要在a[i..j]中查 找x这个数,(1)令mid=(i+j)div 2. (2)将查找值x与中间位置的值a[mid]比较 x=a[mid] 查找成功 x>a[mid] 则在a[mid+1..j]中查找x x<a[mid] 则在a[i..mid-1]中查找x 如果i>j则说明a[i..j]中不存在x.
例如:在有序数列 15 20 26 31 40中查找数x=19
第一次:left=1 right=5 mid=3 x<a[mid] 第二次:left=1 right=2 mid=1 x>a[mid] 第三次:left=2 right=2 mid=2 x<a[mid] left=2 right=1 查找结束,没找到

递归公式:
search(x,left, right)=

-1
mid search(x, left, mid-1) search(x,mid+1,right)

left>right x=a[mid] x<a[mid] x>a[mid]

function search(x,left,right:integer):integer; var mid:integer; begin if left>right (1) then search:=-1 else begin mid:=(left+right) div 2; if x=a[mid] then search:=mid (2) else begin left ,mid-1); if x<a[mid] then search:=search(x, (3) ; if x>a[mid] then search:=search(x,mid+1,right) (4) ; end; end; end;

练一练
1.某数列有1000个各不相同的单元,由低至高按 序排列;现要对该数列进行二分法检索(binarysearch),在最坏的情况下,需检查( B )次。 A.1000 B. 10 C. 100 D. 500
2、二分查找的条件是什么?

数列有序

例3.3.4 按枢纽元素分块
例如:49,38,65,58,76,13,27

例3.3.5 将n(n<1000000)个凌乱的 数据按从小到大的顺序进行排序。
快速排序思想:假设要对a[1..n]进行排序 1.设置两个指针i、j, 初始值:i=1,j=n; 2.将某元素作为关键数据,赋给x,不妨x=a[(i+j)div 2]; 3.从i,j两边开始向中间搜索,分别找到左边比x大的首个元 素,右边比x值小的元素,若找到,则交换a[i]与a[j]的值,调整i ,j的指针 4.重复第3步,直到 i>j; (当i>j时,该趟排序结束,x排在应在的位置上) 5.再对x左右两边的区域进行类似的递归操作 实际上,也是一种“二分”思想,即将大于某个数的所有 数交换到它的右边,小于它的数都交换到左边,直到所有 数都各就其位为止。

procedure qsort(left,right:integer); var i,j,x,temp:integer; begin i:=left; j:=right; x:=a[(i+j) div 2]; repeat while (x<a[j]) do ( 1) ; j:=j-1; while (a[i]>x) do ( 2) ; i:=i+1; if i<=j then begin temp:=a[j];a[j]:=a[i];a[i]:=temp; i:=i+1; j:=j-1 end; until i>j; if left<j then qsort( ( 3) j ); left, if i<right then qsort( i, ( 4) ); right end;

思考:如果原数列是1 2 3 4 5 6 7 时,会有什么结果?

例3.3.6 归并排序
已知某数列存储在序列A[1],A[2],……, A[n],现需要采用分治策略对它们进行从大 到小(从小到大)排序。 例如: 52461326 排序后为 12234566

归并排序的整个过程

procedure Merge(var A: ListType; P, Q, R: Integer); {将A[P..Q]和A[Q+1..R],合并到序列A[P..R]} var I, J, {左右子序列指针} T: Integer;{合并后的序列的指针} Lt: ListType; {暂存合并的序列} begin T:= P; I := P; J := Q + 1; while T <= R do begin{合并未完成} if (I <= Q) and ((J > R) or (A[I] <= A[J])) then begin Lt[t] := A[I]; Inc(I); end else begin {否则右序列的首元素进入合并序列} Lt[t] := A[J]; Inc(J); end; Inc(T); {合并后的序列的指针右移} end; A := Lt; {合并后的序列赋给A} end;

归并过程

二分过程
procedure Merge_Sort(var A: ListType; P, R: Integer); var Q: Integer; begin if P <> R then begin {若子序列A中不止一个元素} Q := (P + R - 1) div 2; {计算中间下标Q} Merge_Sort(A, P, Q); {继续对左子序列递归排序} Merge_Sort(A, Q + 1, R); {继续对右子序列递归排序} Merge(A, P, Q, R) {对左右子序列归并} end; end;

例3.3.7 :求逆序对个数
有一实数序列A[1]、A[2] 、A[3] 、……A[n-1] 、A[n], 若i<j,并且A[i]>A[j],则称A[i]与A[j]构成了一个逆序对, 求数列A中逆序对的个数。 n≤10000。 例如,5 2 4 6 2 3 2 6,可以组成的逆序对有 (5 2),(5 4),(5 2),(5 3),(5 2), (4 2),(4 3),(4 2), (6 2),(6 3),(6 2), (3 2) 共:12个

分析
在看完试题以后,我们不难想到一个非常简单 的算法——穷举算法,即对数组中任意的两个 元素进行判断,看它们是不是构成“逆序对”, 因此这种算法的时间复杂度为O(N2)。 时间效率不尽如人意….. 问题出现在哪里呢??

转换思维
用分治怎么样?

首先将这一序列A一分为二,分成两个不同的序列B、 C 如果求出了B,C的逆序对,那么可由B,C求出A的逆序 对. 如何来统计序列B和序列C之间的“逆序对”呢? 如果还按照穷举的思想来统计的话,那么我们采用 分治法就没有什么意义!!!

提示
在递归的求解B、C两个序列中的逆序对的个数以后,如 果对B、C两个序列当中的元素进行排序的话,要统计B、 C两个序列之间的“逆序对”是非常容易的. 如图 排序前 排序后 ? 在B数组当中,首先,B中的6,5,4都与C数组当中的3 ,2,2都构成了“逆序对”,而2不会构成逆序对,因此 B、C两个数组之间构成的逆序对的个数为3+3+3=9。

结论
由于B、C两个数组已经进行了排序,因此可以设置两个 指针进行操作,有效的统计B、C两个数组之间的“逆序 对”的个数。而且这一统计步骤是能够在线性时间内完 成的。考虑到我们设计的二分模型本身是递归定义的, 所以可以将我们所建立的二分模型完全与归并排序联系 起来。因为排序的过程是可以在递归求解子问题时就能 够完成的,算法的时间复杂度就降到了O(nlogn)。 在这里,虽然对B、C两个序列当中的元素进行了排序, 使得序列A当中某一部分元素的顺序被打乱了,但由于 求解过程是递归定义的,在排序之前B、C两个序列各自 其中的元素之间的“逆序对”个数已经被统计过了,并 且排不排序对统计B、C两个数组之间的“逆序对”的个 数不会产生影响。所以这个排序过程对整个问题的求解 的正确性是没有任何影响的。

例3.3.8 棋盘覆盖
在一个2k×2k 个方格组成的棋盘中,恰有一个方格与 其他方格不同,称该方格为一特殊方格,且称该棋盘 为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不 同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以 外的所有方格,且任何2个L型骨牌不得重叠覆盖。
3 3 3 3 3 4 3 2 4 4 4 2 2 4 4

棋盘覆盖
棋盘覆盖问题分析:
? 该问题的规模缩小到一定的程度就可 以容易地解决; 该问题可以分解为若干个规模较小的相 同问题; 分解出的子问题的解可以合并为原问题 的解; 分解出的各个子问题是相互独立的。
分析:当n=2时的特殊棋盘,可以直接判断拿 哪一个L型骨牌去覆盖。

棋盘覆盖
棋盘覆盖问题分析:
怎么办??

分析:分棋盘很容易,直接从中间把棋盘分成四部分, 但是分后的子棋盘和原来棋盘是否性质相同???

棋盘覆盖
当k>1时,将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所示。 特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘中无特 殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可 以用一个L型骨牌覆盖这3个较小棋盘的会合处,如 (b)所示, 从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用 这种分割,直至棋盘简化为棋盘1×1。

棋盘覆盖
棋盘覆盖问题分析:
? 该问题的规模缩小到一定的程度就可以容易地 解决; ? 该问题可以分解为若干个规模较小的相同问题; ? 分解出的子问题的解可以合并为原问题的解; ? 分解出的各个子问题是相互独立的。

分析:四个子棋牌合并既为原来的棋牌,而且 四个子棋牌都是独立的覆盖问题。

棋盘覆盖问题
还可以将棋盘覆盖推广到一般情况:
1
1 5 5

2
1 5 7

2
2 6 6

3
3 4 6

3
4 4 8

1
1

2
1

2
2

3
3

4
3

4
4

5
5 9 9

6
5 10 9

6
6 10 10

7
7 11 11

8
7 12 11

8
8 12 12

7

7

8

8

大数的运算
加法 ? 减法 ? 乘法
?
?

100! 700490 229915 758251

= 93 326215 443944 152681 699263 856266 715968 264381 621468 592963 895217 599993 608914 463976 156578 286253 697920 827223 185210 916864 000000 000000 000000 000000

除法 ? ……
?

问题描述:
?

大整数的乘法

设X和Y都是n位的二进制整数,请设计一个有效 的算法,可以进行两个n位大整数的乘法运算。 1.小学的方法:O(n2)
× 0 1 1 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0

分析:
?

效率太低
1 0 1 0 1 1 1

1

1

大整数的乘法
?

2.可以用分治法的原理设计一个更有效的算法。 将n位的二进制整数分为2段:
n/2位 X= A n/2位 B Y= n/2位 C n/2位 D

则:

X=A2n/2+B(乘2n/2,相当于左移n/2位) Y=C2n/2+D

于是: XY = (A2n/2+B) (C2n/2+D)
=AC2n + (AD+BC) 2n/2 + BD (1)

大整数的乘法
效率:
? 4次n/2位整数乘法(AC,

AD,BC, BD); ? 3次不超过n位整数加法; ? 2次移位(分别对应乘以2n和2n/2) ? 所有加法和移位共用O(n)步计算。 时间复杂性分析 T(n)=O(n2)

?没有改进

改进:把(1)式稍作修改:

XY = AC2n + ((A-B)(D-C)+AC+BD) 2n/2 + BD (2)
效率:
? ?

3次n/2位整数乘法(AC, BD, (A-B)(D-C));
6次不超过n位整数加、减法和2次移位;

时间复杂性分析 O(1) n ?1 ? T ( n) ? ? ?3T (n / 2) ? O(n) n ? 1

T(n)=O(nlog3) =O(n1.59)

?较大的改进

begin //两个n位整数相乘(伪代码) X=abs(X); Y=abs(Y); if(n==1) return (S*X*Y); else begin A:=X的左边n/2位; B:=X的右边n/2位; C:=Y的左边n/2位; D:=Y的右边n/2位; m1:=Mult(A, C, n/2); m2:=Mult(A-B, D-C, n/2); m3:=Mult(B, D, n/2); S:=S*(m1* 2n +(m1+m2+m3)*2n/2+m3); return S; end;End;

大整数的乘法
分析
?传统的方法:O(n2)
?分治法:

?效率太低
?较大的改进

O(n1.59)

更快的方法?
? 对于大整数乘法,它能在O(nlogn)时间内解

决。

是否能找到线性时间的算法?
? 目前为止还没有结果



循环赛日程表
设计一个满足以下要求的比赛日程表: (1)每个选手必须与其他n-1个选手各赛一次; (2)每个选手一天只能赛一次; (3)循环赛一共进行n-1天。

按分治策略,将所有的选手分为两半,n个选 手的比赛日程表就可以通过为n/2个选手设计 的比赛日程表来决定。递归地用对选手进行分 割,直到只剩下2个选手时,比赛日程表的制 定就变得很简单。这时只要让这2个选手进行 比赛就可以了。

循环赛日程表
队 天 ① 1 2
2 3 4 1 4 3 ② 3 4 1 2 ③ 4 3 2 1 ④ 5 6 7 8 ⑤ 6 5 8 7 ⑥ ⑦ 7 8 8 5 6 7 6 5

例如:

5
6 7 8

6
5 8 7

7
8 5 6

8
7 6 5

1
2 3 4

2
1 4 3

3
4 1 2

4
3 2 1

循环赛日程表
分析:
? 法1:分治策略

A1

A2

A2

A1

? 按分治策略,将所有的选手分为两半,n

个选手的比赛日程表就可以通过为n/2个 选手设计的比赛日程表来决定。 ? 递归地用对选手进行分割,直到只剩下2 个选手时,比赛日程表的制定就变得很简 单。这时只要让这2个选手进行比赛就可 以了。

分析
?

循环赛日程表
1 2 3 加4 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1

法2:递推法(迭代法)
1 2 2 1

1
加2

2
1 4 3

3
4 1 2

4
3 2 1

2 3 4

循环赛日程表
递推法(迭代法)
? 即2k个选手的比赛日程在2k-1个选手的比赛日

程基础上通过迭代完成,每次迭代,将问题分 为4个部分:
? 左上角:

2k-1个选手前半程的比赛日程 ? 左下角:另2k-1个选手前半程的比赛日程,由左上 角加2k-1得到 ? 右上角:将左下角抄到右上角,得到另2k-1个选手 后半程的比赛日程。 ? 右下角:将左上角抄到右下角,得到2k-1个选手后 半程的比赛日程。

例3.3.10 取余运算
[问题描述] 输入b,p,k的值,求bp mod k的值。其 中b,p,k*k为长整形数。

[输入输出样例] mod.in 2 10 9
mod.out 2^10 mod 9=7

预备知识1:同余
1、同余的概念 若a,b为两个整数,且它们的差a-b能 被某个自然数m所整除,则称a就模m来说同余于b,或者说a 和b关于模m同余,记为:a≡b (mod m)。它意味着:ab=m×k (k为 某一个整数)。例如,32≡2 (mod 5),此时k 为6。

2

同余的性质
(1) 自反性:a≡a (mod m) (2)对称性:若a≡b (mod m),则b≡a (mod m)

(3)传递性:若a≡b (mod m),b≡c (mod m),则a≡c (mod m) (4)同加性:若a≡b (mod m),则a+c≡b+c (mod m)

(5)同乘性: 若a≡b (mod m),则a×c≡b×c (mod m) 一般情况,a≡b (mod m),c≡d (mod m),则 有:a×c≡b×d(mod m) (6)同幂性:若a≡b (mod m),则an≡bn (mod m) 一个重要的推论: A*B mod K =(A mod K)*(B mod K)mod K

举例:求389 mod 7 31≡3 (mod 7)

32≡32 (mod 7)≡2 (mod 7) 34≡(32)2 (mod 7)≡22 (mod 7)≡4 38≡(34)2 (mod 7)≡42 (mod 7)≡2 316≡(38)2 (mod 7)≡22 (mod 7)≡4 332≡(316)2 (mod 7)≡42 (mod 7)≡2 364≡(332)2 (mod 7)≡22 (mod 7)≡4

389≡(364)×(316)×(38)×(31) (mod 7) ≡4×4×2×3 (mod 7) ≡96 (mod 7)≡5 (mod 7)

总结归纳
分治是一种解题的策略,它的基本思想是:“如果整个 问题比较复杂,可以将问题分化,各个击破。” 分治包含“分”和“治”两层含义,如何分,分后如何 “治”成为解决问题的关键所在 不是所有的问题都可以采用分治,只有那些能将问题分 成与原问题类似的子问题,并且归并后符合原问题的性 质的问题,才能进行分治 分治可进行二分,三分等等,具体怎么分,需看问题的 性质和分治后的效果。 只有深刻地领会分治的思想,认真分析分治后可能产生 的预期效率,才能灵活地运用分治思想解决实际问题。

谢 谢!

思考
问题二:若能,一共有多少种装载方案。
procedure search(w,n:integer); begin if w=0 then begin inc(total); exit ; end; if n>=1 then begin search(w-a[n],n-1); search(w,n-1); end; end;

思考
procedure search(w,n:integer); begin if w=0 then begin print(t); exit; end; if n>=1 then begin inc(t); c[t]:=a[n]; search(w-a[n],n-1); ; dec(t) search(w,n-1); end; end;


递推-递归-分治-回溯

递推递归分治—回溯 递推算法在程序编辑过程中,我们可能会遇到这样一类问题,出题者告诉你数列的前几个数,或 通过计算机获取了数列的前几个数,要求编程者求出...

算法设计与分析第二版课后习题解答

对于计算 n!的递归算法 F(n),建立其递归调用次数的递推关系并求解。 解: 3...解: a. Algorithms ClosestNumber(A[l..r]) //分治计算最近对问题的一维...

算法设计与分析试卷(A)及答案

B A、 递归;B、分治;C、迭代;D、模拟。 6、FIFO 是( A、分支界限法 7、投点法是( A、分支界限算法 B A )的一搜索方式。 B、动态规划法 )的一种。...

实验二 递归与分治策略

实验二(一) 、实验目的 递归分治策略 通过编程实现递归分治策略的有关算法,理解递归分治策略算 法的原理,掌握递归分治策略基本思想与应用技巧。 (二) 、...

递推递归例题

递推递归 4页 免费递​推​递​归​例​题 暂无评价|0人阅读|0次下载|举报文档 A​C​M​培​训​时​,​配​套​的​例​...

递归与递推上机习题

递归递推上机习题pascal;递归递推上机习题pascal;隐藏>> 进制转换源程序名 ...,所以,对于一个规模为 n 的问题,我们 很容易地就把它分治成了规模为 n-1 ...

递推与递归算法

递推与递归算法_IT/计算机_专业资料。详细介绍递推、递归递推与递归算法递推和递归是编程中常用的基本算法。在前面的解题中已经用到了这两种方法,下面 对这两种算...

递归与分治相关实验及代码

​归​分​治​实​验​报​告​,​代​码实验目的:掌握递归分治算法的基本原理和应用以及软件实现。 实验准备: 1. 在开始本实验之前,请...

递推与递归算法

递​推​与​递​归​算​法授课教师:南京市拉萨路小学韩孟江 hanmengjiang@126.com 第七讲 递推递归算法 学习重点 1、掌握基本的算法——递推。...

实验1++递归与分治算法

淮海工学院计算机工程学院 实验报告书课 程名:题目: 《算法分析与设计》 递归分治算法 实验 1 班学姓 级: 号: 名: 评语: 成绩: 指导教师: 批阅时间: 年...