分治算法（二）-白红宇

分治算法（二）

阅读量：5098 次

发布时间：2019-06-13

本文共 5292 字，大约阅读时间需要 17 分钟。

例5、取余运算(mod)

源程序名 mod.???（pas, c, cpp）

可执行文件名 mod.exe

输入文件名 mod.in

输出文件名 mod.out

【问题描述】

输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整型数。

【样例】

mod.in

2 10 9

mod.out

2^10 mod 9=7

【知识准备】

进制转换的思想、二分法。

【算法分析】

本题主要的难点在于数据规模很大(b, p都是长整型数)，对于b^p显然不能死算，那样的话时间复杂度和编程复杂度都很大。

下面先介绍一个原理：a*b mod k＝(a mod k)*(b mod k)mod k。显然有了这个原理，就可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。

那么怎样分解最有效呢?显然对于任何一个自然数P，有p＝2*(p div 2)+p mod 2，如19＝2*(19 div 2)+19 mod 2＝2*9+1，利用上述原理就可以把b的19次方除以k的余数转换为求b的9次方除以k的余数，即b¹⁹=b^2*9+1＝b*b⁹*b⁹，再进一步分解下去就不难求得整个问题的解。

这是一个典型的分治问题，具体实现的时候是用递推的方法来处理的，

如p=19，有

19=2*9+1 b¹⁹=b¹*b⁹*b⁹

9=2*4+1 b⁹=b¹*b⁴*b⁴

4=2*2+0 b⁴=b⁰*b²*b²

2=2*1+0 b²=b⁰*b¹*b¹

1＝2*0+1 b¹=b¹*b⁰*b⁰

反过来，我们可以从0出发，通过乘以2再加上一个0或1而推出1，2，4，9，19，这样就逐步得到了原来的指数，

进而递推出以b为底，依次以这些数为指数的自然数除以k的余数。

不难看出这里（倒推）每一次乘以2后要加的数就是19对应的二进制数的各位数字，即1，0，0，1，1，而19＝(10011)2，求解的过程也就是将二进制数还原为十进制数的过程。

具体实现请看下面的程序，程序中用数组binary存放p对应的二进制数，总位数为len，binary[1]存放最底位。变量rest记录每一步求得的余数。

1 var b,p,k,i,len,rest,temp:longint; 2      binary:array[1..32] of longint; 3 begin 4   assign(input,'mod.in'); 5   assign(output,'mod.out'); 6   reset(input); 7   rewrite(output); 8   readln(b,p,k);   {
     输入三个数} 9   len:=0;10   temp:=p;11   while temp<>0 do    {
     存放p的二进制转换}12     begin13       len:=len+1;14       binary[len]:=temp mod 2;  //也可以写成binary[len]:=temp and 1;15       temp:=temp div 2        //也可以写成temp:=temp shr 1;16     end;17   rest:=1;18   for i:=len downto 1 do    {
     用二分法实现b^p mod k}19     begin20       temp:=rest*rest mod k;21       if binary[i]=1 then rest:=b mod k * temp mod k    {
     如果是奇数，就多乘b}        //rest:=(b mod k * temp) mod k 22                      else rest:=temp     {
     否则就是rest*rest}23     end;24   writeln(b,'^',p,' mod ',k,' = ',rest);   {
     输出b^p mod k}25   close(input);26   close(output)27 end.

例6 黑白棋子的移动(chessman)

源程序名 chessman.???（pas, c, cpp）

可执行文件名 chessman.exe

输入文件名 chessman.in

输出文件名 chessman.out

1 const max=100; 2 var n,st,sp:integer; 3     c:array[1..max] of char;  {
     工作场所} 4  5 procedure print;  {
     打印} 6   var i:integer; 7   begin 8     write('step',st:2,':'); 9     for i:=1 to 2*n+2 do write(c[i]);10     writeln;11     st:=st+112   end;13 14 procedure init(n:integer);  {
     初始化}15   var i:integer;16   begin17     st:=0;18     sp:=2*n+1;19     for i:=1 to n do c[i]:='o';20     for i:=n+1 to 2*n do c[i]:='*';21     c[2*n+1]:='-';c[2*n+2]:='-';  22     print23   end;24 25 procedure move(k:integer);  {
     移动一步}//将两个横线（空）移到k处（以左横线位置为序号）26   var j:integer;27   begin28     for j:=0 to 1 do begin c[sp+j]:=c[k+j];c[k+j]:='-';end;29     sp:=k;30     print31   end;32 33 procedure mv(n:integer);    {
     主要过程}34   var i,k:integer;35   begin36     if n=4 then begin37                   move(4);38                   move(8);39                   move(2);40                   move(7);41                   move(1)42                 end43            else begin44                   move(n);45                   move(2*n-1);46                   mv(n-1)47                 end48   end;49 50 begin  {
     main}51   assign(input,'chessman.in');52   assign(output,'chessman.out');53   reset(input);54   rewrite(output);55   readln(n);56   init(n);57   mv(n);58   close(input);59   close(output)60 end.

例7、小车问题（car）

【问题描述】

甲、乙两人同时从A地出发要尽快同时赶到 B地。出发时A 地有一辆小车，可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样，且小于车的速度。问：怎样利用小车才能使两人尽快同时到达。

【问题输入】

仅一行，三个数据分别表示 AB两地的距离s，人的步行速度a，车的速度 b。

【问题输出】

两人同时到达B地需要的最短时间。

【输入输出样例】

car.in

120 5 25

car.out

9.6000000000E+00

自己推了一下确实是这样的。数学太弱了。。。

1 var 2   s,a,b,k,x,t:real; 3 begin 4 assign(input,'car.in'); 5 reset(input); 6 assign(output,'car.out'); 7 rewrite(output); 8   readln(s,a,b); 9    k:=s*(a+b)/(3*a+b);10    t:=k/b+(s-k)/a;11   writeln(t:0:2);12 close(input);close(output);13 end.

数学法

1 program car1(input,output);  2 const zero=1e-4;  3 var s,a,b,c,c0,c1,t1,t2,t3,t4:real;  4 BEGIN  5 assign(input,’car.in’);  6 assign(output,’car.out’);  7 reset(input);  8 rewrite(output);  9   readln(s,a,b); 10   c0:=0; 11   c1:=s; 12   repeat 13     c:=(c0+c1)/2; 14     t3:=c/b;  //甲到K乘汽车用时；也是乙走到C用时。即 乙TAC=甲TAK15     t1:=t3+(s-c)/a;  //甲到终点用时。即 甲TAB16     t4:=(c-t3*a)/(a+b);  //乙从C走，车从K来接乙相遇用时。即 乙TCD17     t2:=t3+t4+(s-(t3+t4)*a)/b;   //乙到终点用时。即 乙TAB18     if t1

分治法

【深入思考】

现在把上述问题稍改一下，已知 A、B两地相距 S=100公里，在A 地有 n人，现有一辆汽车，此汽车除司机外只能载 1 人，已知汽车的速度为 V1=50 公里/小时，人的速度为 V2=5公里/小时。要求设计一种方案，使得最后一个人用最少的时间到达B。