数据结构算法集锦.txt

数据结构算法集锦：包括大量常用算法

                        边界：f[0,0]:=true.
                        For I:=1 to n do
                         For j:=w[I] to v do  F[I,j]:=f[I-1,j-w[I]];
                        优化：当前状态只与前一阶段状态有关，可降至一维。
                        F[0]:=true;
                        For I:=1 to n do begin
                         F1:=f;
                         For j:=w[I] to v do
                        If f[j-w[I]] then f1[j]:=true;
                         F:=f1;
                        End;
                        B.求可以放入的最大价值。
                        F[I,j] 为容量为I时取前j个背包所能获得的最大价值。
                        F [i,j] = max { f [ i – w [ j ], j-1] + p [ j ],  f[ 
                        i,j-1] }
                        C.求恰好装满的情况数。
                        DP:
                        Procedure update;
                        var j,k:integer;
                        begin
                           c:=a;
                           for j:=0 to n do
                             if a[j]>0 then
                                 if j+now<=n then inc(c[j+now],a[j]);
                           a:=c;
                        end;
                        2．可重复背包
                        A求最多可放入的重量。
                         F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。
                        状态转移方程为
                            f[I,j] = f [ I-1, j – w[I]*k ] (k=1.. j div w[I])
                        B.求可以放入的最大价值。
                         USACO 1.2  Score Inflation
                         
                        进行一次竞赛，总时间T固定，有若干种可选择的题目，每种题目可选入的数量不限，每种题目有一个ti（解答此题所需的时间）和一个si（解答此题所得的分数），现要选择若干题目，使解这些题的总时间在T以内的前提下，所得的总分最大，求最大的得分。
                         *易想到：
                              f[i,j] = max { f [i- k*w[j], j-1] + k*p[j] }  
                        (0<=k<= i div w[j])
                        其中f[i,j]表示容量为i时取前j种背包所能达到的最大值。
                         *实现：
                        Begin
                         FillChar(f,SizeOf(f),0);
                         For i:=1 To M Do
                         For j:=1 To N Do
                           If i-problem[j].time>=0 Then
                           Begin
                             t:=problem[j].point+f[i-problem[j].time];
                             If t>f[i] Then f[i]:=t;
                           End;
                         Writeln(f[M]);
                        End.
                        C.求恰好装满的情况数。
                        Ahoi2001 Problem2
                        求自然数n本质不同的质数和的表达式的数目。
                        思路一，生成每个质数的系数的排列，在一一测试，这是通法。
                        procedure try(dep:integer);
                           var i,j:integer;
                           begin
                             cal; {此过程计算当前系数的计算结果，now为结果}
                             if now>n then exit; {剪枝}
                             if dep=l+1 then begin {生成所有系数}
                               cal;
                               if now=n then inc(tot);
                               exit;
                             end;
                             for i:=0 to n div pr[dep]  do  begin
                               xs[dep]:=i;
                               try(dep+1);
                               xs[dep]:=0;
                             end;
                           end;
                        思路二，递归搜索效率较高
                         procedure try(dep,rest:integer);
                           var i,j,x:integer;
                           begin
                             if (rest<=0) or (dep=l+1) then begin
                               if rest=0 then inc(tot);
                               exit;
                             end;
                             for i:=0 to rest div pr[dep] do
                               try(dep+1,rest-pr[dep]*i);
                           end;
                        {main: try(1,n); }
                        思路三：可使用动态规划求解
                        USACO1.2 money system
                        V个物品，背包容量为n，求放法总数。
                        转移方程：

                        Procedure update;
                        var j,k:integer;
                        begin
                           c:=a;
                           for j:=0 to n do
                             if a[j]>0 then
                               for k:=1 to n div now do
                                 if j+now*k<=n then inc(c[j+now*k],a[j]);
                           a:=c;
                        end;
                        {main}
                        begin 
                        read(now); {读入第一个物品的重量}
                         i:=0;   {a[i]为背包容量为i时的放法总数}
                         while i<=n do begin 
                        a[i]:=1; inc(i,now); end;  {定义第一个物品重的整数倍的重量a值为1，作为初值}
                        for i:=2 to v do
                         begin
                           read(now);
                           update; {动态更新}
                         end;
                         writeln(a[n]);
                        四、排序算法
                        1.快速排序：
                        procedure qsort(l,r:integer);
                          var i,j,mid:integer;
                          begin
                               i:=l;j:=r; mid:=a[(l+r) div 2]; 
                        {将当前序列在中间位置的数定义为中间数}
                           repeat
                             while a[i]<mid do inc(i); {在左半部分寻找比中间数大的数}
                             while a[j]>mid do dec(j);{在右半部分寻找比中间数小的数}
                             if i<=j then begin  {若找到一组与排序目标不一致的数对则交换它们}
                               swap(a[i],a[j]);
                               inc(i);dec(j);  {继续找}
                             end;
                          until i>j;
                          if l<j then qsort(l,j); {若未到两个数的边界，则递归搜索左右区间}
                          if i<r then qsort(i,r);
                         end;{sort}
                        B.插入排序：
                        思路：当前a[1]..a[i-1]已排好序了，现要插入a[i]使a[1]..a[i]有序。
                         procedure insert_sort;
                         var i,j:integer;
                         begin
                           for i:=2 to n do begin
                             a[0]:=a[i];
                             j:=i-1;
                             while a[0]<a[j] do begin
                               a[j+1]:=a[j];
                        j:=j-1;
                             end;
                             a[j+1]:=a[0];
                           end;
                         end;{inset_sort}
                        C.选择排序：
                        procedure sort;
                          var i,j,k:integer;
                          begin
                            for i:=1 to n-1 do 
                              for j:=i+1 to n do
                                if a[i]>a[j] then swap(a[i],a[j]);
                          end;
                        D. 冒泡排序
                        procedure bubble_sort;
                          var i,j,k:integer;
                          begin
                           for i:=1 to n-1 do
                             for j:=n downto i+1 do
                               if a[j]<a[j-1] then swap( a[j],a[j-1]); 
                        {每次比较相邻元素的关系}
                         end;
                        E.堆排序：
                        procedure sift(i,m:integer);{调整以i为根的子树成为堆,m为结点总数}
                         var k:integer;
                         begin
                           a[0]:=a[i]; k:=2*i;{在完全二叉树中结点i的左孩子为2*i,右孩子为2*i+1}
                           while k<=m do begin
                             if (k<m) and (a[k]<a[k+1]) then 
                        inc(k);{找出a[k]与a[k+1]中较大值}
                           if a[0]<a[k] then begin a[i]:=a[k];i:=k;k:=2*i; end
                           else k:=m+1;
                           end;
                           a[i]:=a[0]; {将根放在合适的位置}
                         end;
                        procedure heapsort;
                         var
                           j:integer;
                         begin
                           for j:=n div 2 downto 1 do sift(j,n);
                           for j:=n downto 2 do begin
                             swap(a[1],a[j]);
                             sift(1,j-1);
                           end;
                        end;
                        F. 归并排序
                        {a为序列表，tmp为辅助数组}
                        procedure merge(var a:listtype; p,q,r:integer);
                        {将已排序好的子序列a[p..q]与a[q+1..r]合并为有序的tmp[p..r]}
                         var I,j,t:integer;
                            tmp:listtype;
                         begin
                           t:=p;i:=p;j:=q+1;{t为tmp指针，I,j分别为左右子序列的指针}
                           while (t<=r) do begin
                             if (i<=q){左序列有剩余} and ((j>r) or (a[i]<=a[j])) 
                        {满足取左边序列当前元素的要求}
                               then begin
                                     tmp[t]:=a[i]; inc(i);
                               end
                             else begin
                                   tmp[t]:=a[j];inc(j);
                             end;
                           inc(t);
                         end;
                         for i:=p to r do a[i]:=tmp[i];
                        end;{merge}
                        procedure merge_sort(var a:listtype; p,r: integer); 
                        {合并排序a[p..r]}
                         var  q:integer;
                         begin
                           if p<>r then begin
                             q:=(p+r-1) div 2;
                             merge_sort (a,p,q);
                             merge_sort (a,q+1,r);
                             merge (a,p,q,r);
                           end;
                         end;
                        {main}
                        begin
                         merge_sort(a,1,n);
                        end.
                        G.基数排序
                        思想：对每个元素按从低位到高位对每一位进行一次排序
                        五、高精度计算
                        高精度数的定义：
                         type
                           hp=array[1..maxlen] of integer;
                        1．高精度加法
                        procedure plus ( a,b:hp; var c:hp);
                         var i,len:integer;
                        begin
                         fillchar(c,sizeof(c),0);
                         if a[0]>b[0] then len:=a[0] else len:=b[0];
                         for i:=1 to len do begin
                           inc(c[i],a[i]+b[i]);
                        if c[i]>10 then begin dec(c[i],10); inc(c[i+1]); end; 
                        {进位}
                        end;
                         if c[len+1]>0 then inc(len);
                         c[0]:=len;
                        end;{plus}
                        2．高精度减法
                        procedure substract(a,b:hp;var c:hp); 
                         var i,len:integer;
                         begin
                           fillchar(c,sizeof(c),0);
                           if a[0]>b[0] then len:=a[0] else len:=b[0];
                           for i:=1 to len do begin
                             inc(c[i],a[i]-b[i]);
                             if c[i]<0 then begin inc(c[i],10);dec(c[i+1]); end;
                             while (len>1) and (c[len]=0) do dec(len);
                           c[0]:=len;
                         end;
                        3．高精度乘以低精度
                        procedure multiply(a:hp;b:longint;var c:hp);
                         var i,len:integer;
                         begin
                           fillchar(c,sizeof(c),0);
                           len:=a[0];
                           for i:=1 to len do begin
                             inc(c[i],a[i]*b);
                             inc(c[i+1],(a[i]*b) div 10);
                             c[i]:=c[i] mod 10;
                           end;
                           inc(len);
                           while (c[len]>=10) do begin {处理最高位的进位}
                             c[len+1]:=c[len] div 10;
                             c[len]:=c[len] mod 10;
                             inc(len);
                            end;
                           while (len>1) and (c[len]=0) do dec(len); 
                        {若不需进位则调整len}
                           c[0]:=len;
                         end;{multiply}
                        4．高精度乘以高精度
                        procedure high_multiply(a,b:hp; var c:hp}
                         var i,j,len:integer;
                         begin
                           fillchar(c,sizeof(c),0);
                           for i:=1 to a[0] do
                             for j:=1 to b[0] do begin
                               inc(c[i+j-1],a[i]*b[j]);
                            inc(c[i+j],c[i+j-1] div 10);
                            c[i+j-1]:=c[i+j-1] mod 10;
                             end;
                           len:=a[0]+b[0]+1;
                           while (len>1) and (c[len]=0) do dec(len);
                           c[0]:=len;