信息学奥赛常考算法——分治法

★分治法

一个问题要用计算机解决，影响时间的关键因素是问题的规模。分治法是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

一般来说，分治法是按照以下步骤工作的：

    ⑴将问题的实例划分为同一个问题的几个较小的实例，最好有同样的规模；

    ⑵对这些较小的实例求解（一般使用递归方法，但在问题规模足够小的时候，有时也会使用一些其它的方法）；

⑶如果必要的话，合并这些较小问题的解，以得到原始问题的解。

典型例题：

【例题】折半查找。

    对于有序数组的查找，折半查找是一种优越的算法.它通过比较查找数x和数组中的中间元素a[m]来完成查找工作。如果他们相等，则算法结束；否则，若x就对数组的前半部分执行该操作，若x>a[m]，则对数组的后半部分执行该操作。这里假设数组a中元素按升序排列。

program zheban;

var x,i:integer;

    a:array[0..10000] of integer;

{在数组left~right之间查询值为x的数，返回其位置，如果未找到则返回0}

function search(x,left,right:integer):integer;

  var m,i,j:integer;

  begin

    if left>right

      then search:=0

      else begin

             m:=(right+left) div 2;

             if x

                       else if x=a[m] then search:=m

                                      else search:=search(x,m+1,right);

           end;

  end;

 begin

  a[0]:=0;

  for i:=1 to 10 do    {为了便于验证，构造了一个有10个元素的递增序列}

  begin

    a[i]:=a[i-1]+random(10);

    write(a[i],' ');

  end;

  writeln;

  readln(x);   {读入要查找的数}

  writeln(search(x,1,10));

end.