数学研发论坛

 找回密码
 欢迎注册
查看: 23748|回复: 80

[分享] 经典算法普及——基础篇

[复制链接]
发表于 2009-2-25 10:51:24 | 显示全部楼层 |阅读模式
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-25 10:52:16 | 显示全部楼层
选择排序是一种简单而有效的排序算法,在问题规模不是很大的情况下就大胆的使用这个算法吧。
   算法主过程如下:
  1.    PROCEDURE selectsort;
  2.       VAR
  3.         i,j,k,temp:integer;
  4.       BEGIN
  5.         FOR i:=1 to n-1 DO
  6.           BEGIN
  7.             k:=i;
  8.             FOR j:=i+1 to n DO
  9.               IF a[k]>a[j]
  10.                  THEN k:=j;
  11.            IF k<>i
  12.              THEN BEGIN
  13.                     temp:=a[k];
  14.                     a[k]:=a[i];
  15.                     a[i]:=temp;
  16.                   END;
  17.           END;
  18.        END;
复制代码

[ 本帖最后由 kon3155 于 2009-2-25 10:56 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-25 10:55:39 | 显示全部楼层
快速排序是基于分治排序算法,在数据规模很大的情况下一般使用该算法。
   算法主过程如下:
  1.     procedure qsort(L,R:longint);
  2.        var
  3.          i,j,mid,temp:longint;
  4.        begin
  5.            i:=L;
  6.            j:=R;
  7.            mid:=a[L+random(R-L+1)];   {随机选择一个数组中的数作为对比数}
  8.            repeat
  9.               while a[i]< mid do inc(i);    {在左半部分寻找比中间数大的数}
  10.               while mid< a[j] do dec(j);    {在右半部分寻找比中间数小的数}
  11.               if i< =j then     {若找到一组与排序目标不一致的数对则交换它们}
  12.                  begin
  13.                    temp:=a[i];
  14.                    a[i]):=a[j];
  15.                    a[j]:=temp;
  16.                    inc(i);dec(j); {继续找}
  17.                  end;
  18.             until i >j;
  19.             if L< j then qsort(L,j);   {若未到两个数的边界,则递归搜索左右区间}
  20.             if i< R then qsort(i,R);
  21.         end;
复制代码
注意:主程序中必须加randomize语句。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-25 10:58:15 | 显示全部楼层
由于待处理的数据超过了任何一种数据类型所能容纳的范围,因此必须采用数串形式输入,并将其转化为数组。该数组的每一个元素对应一个十进制数,由其下标顺序指明位序号。由于高精度运算可能使得数据长度发生变化,因此除要用整数数组存储数据外,还需要一个整数变量纪录整数数组的元素个数,即数据的实际长度。
  1. type
  2.   numtype=array[1..255] of byte;
  3. var
  4.   a:numtype;
  5.   la:byte;
  6.   s:string;
  7. begin
  8.   readln(s);
  9.   la:=length(s);
  10.   for i:=1 to la do
  11.     a[la-i+1]:=ord(s[i])-ord('0');
  12. end.
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-25 10:58:50 | 显示全部楼层
高精度加法运算

    首先,确定a和b中的最大位数x,然后依照由低位至高位的顺序进行加法运算。在每一次运算中,a当前位加b当前位的和除以10,其整商即为进位,其余数即为和的当前位。在进行了x位的加法后,若最高位有进位(a[x+1]<>0),则a的长度为x+1。
以下只列出关键程序:
  1. type
  2.   numtype=array[1..255] of byte;
  3. var
  4.   a,b:numtype;
  5.   la,lb:byte;
  6. procedure plus(var a:numtype;var la:byte;b:numtype);  {利用过程实现}
  7.   var
  8.     i,x:byte;
  9.   begin
  10.     if la>=lb
  11.        then x:=la
  12.        else x:=lb;
  13.     for i:=1 to x do
  14.       begin
  15.         a[i]:=a[i]+b[i];
  16.         a[i+1]:=a[i+1]+a[i] div 10;
  17.         a[i]:=a[i] mod 10;
  18.       end;
  19.    while a[x+1]<>0 do
  20.       x:=x+1;   
  21.    la:=x;             {最高位若有进位,则长度增加}
  22.   end;

复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-25 10:59:12 | 显示全部楼层
高精度减法运算(a>b)

    依照由低位至高位的顺序进行减法运算。在每一次位运算中,若出现不够减的情况,则向高位借位。在进行了la位的减法后,若最高位为零,则a的长度减1。
以下只列出关键程序:
  1. type
  2.   numtype=array[1..255] of byte;
  3. var
  4.   a,b:numtype;
  5.   la,lb:byte;
  6. procedure minus(var a:numtype;var la:byte;b:numtype);
  7.   var
  8.     i:byte;
  9.   begin
  10.     for i:=1 to la do
  11.       begin
  12.         if a[i]<b[i]
  13.            then begin
  14.                   dec(a[i+1]);
  15.                   a[i]:=a[i]+10;
  16.                 end;
  17.         a[i]:=a[i]-b[i];
  18.       end;
  19.     while (a[la]=0) and (la>1) do
  20.        dec(la);
  21.   end;
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-25 10:59:39 | 显示全部楼层
高精度乘法运算

    按照乘法规则,从a的第1位开始逐位与c(c为字节型)相乘。在第i位乘法运算中,a的i位与c的乘积必须加上i-1位的进位,然后规整积的i-1位。
以下只列出关键程序:
  1. type
  2.   numtype=array[1..255] of word;
  3. var
  4.   a,b:numtype;
  5.   la,lb:byte;
  6. procedure multiply(var a:numtype;c:byte);
  7.   var
  8.     i:byte;
  9.   begin
  10.     a[1]:=a[1]*c;
  11.     for i:=2 to la do
  12.       begin
  13.         a[i]:=a[i]*c;
  14.         a[i]:=a[i]+a[i-1] div 10;
  15.         a[i-1]:=a[i-1] mod 10;
  16.       end;
  17.     while a[la]>=10 do
  18.       begin
  19.        inc(la);
  20.        a[la]:=a[la-1] div 10;
  21.        a[la-1]:=a[la-1] mod 10;
  22.       end;
  23.   end;

复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-25 11:01:16 | 显示全部楼层
扩大进制数改善高精度运算效率

    用整数数组每一个元素表示一个十进制整数的方法存在的缺点是:如果十进制的位数很多,则对应的数组的长度会很长,并增加了高精度计算的时间。
    如果用一个元素记录2位数字、3位数字或更多位数字,则数组的长度可以明显缩小,但是还要考虑数的取值范围问题,必须保证程序运行过程中不越界。在权衡了两方面的情况后得出:用一个longint记录4位数字是最佳的方案。那么这个数组就相当于一个10000进制的数,其中每一个元素都是10000进制下的一位数。

  1. 一、数据类型定义:type
  2.   numtype=array[1..10000] of longint;  {可以存储40000位十进制数}
  3. var
  4.   a,n:numtype;
  5.   la,ln:byte;
  6.   s:ansistring;       {任意长度的字符串类型}
复制代码
二、整数数组的建立和输出
  1. readln(s);
  2. k:=length(s);
  3. for i:=1 to k do
  4. begin
  5. j:=(k-i+4) div 4;
  6. n[j]:=n[j]*10+ord(s[i])-48;
  7. end;
  8. ln:=(k+3) div 4;

  9. 当得出最后结果n后,必须按照次高位到最低位的顺序,将每一位元素由10000进制数转换成十进制数,即必须保证每个元素对应4位十进制数。例如n[i]=0015(0<=i<=ln-2),对应的十进制数不能为15,否则会导致错误结果。可以按照如下方法输出n对应的十进制数:[code]write(n[ln]);
  10. for i:=ln-1 downto 1 do
  11.   write(n[i] div 1000,(n[i] div 100) mod 10,(n[i] div 10) mod 10,n[i] mod 10);

  12. 三、基本运算
  13.     两个10000进制整数的加法和减法与前面的十进制运算方法类似,只是进制变成了10000进制。
  14.     1、整数数组减1(n:=n-1,n为整数数组)
  15.     从n[1]出发寻找第一个非零的元素,由于接受了低位的借位,因此减1,其后缀全为9999。如果最高位为0,则n的长度减1。
  16.     j:=1;
  17.     while (n[j]=0) do inc(j);             {寻找第一个非零的元素}
  18.     dec(n[j]);                            {该位接受低位的借位,因此减1}
  19.     for i:=1 to j-1 do
  20.        n[i]:=9999;                        {其后缀全为9999}
  21.     if (j=ln) and (n[j]=0)                {如果最高位为0,则n的长度减1}
  22.        then dec(ln);

  23. 2、整数数组除以整数(a:=a div i,a为整数数组,i为整数)
  24.     按照从高位到低位的顺序,逐位相除,把余数乘进制后加到下一位继续相除。如果最高位为0,则a的长度减1。
  25. l:=0;
  26.     for j:=la downto 1 do
  27.       begin
  28.         inc(a[j],l*10000);
  29.         l:=a[j] mod i;
  30.         a[j]:=a[j] div i;
  31.       end;
  32.     while a[la]=0 do dec(la);3、两个整数数组相乘(a:=a*n,a和n为整数数组)
  33.     按照从高位到低位的顺序,将数组a的每一个元素与n相乘。[code]procedure multiply(a,b:numtype;la,lb:longint;var s:numtype;var ls:longint);
  34.   var
  35.     i,j:longint;
  36.   begin
  37.     for i:=1 to la do
  38.       for j:=1 to lb do
  39.           s[i+j-1]:=s[i+j-1]+a[i]*b[j];
  40.     for i:=1 to la+lb-1 do
  41.       begin
  42.         s[i+1]:=s[i+1]+s[i] div 10000;
  43.         s[i]:=s[i] mod 10000;
  44.       end;
  45.     if s[la+lb]=0
  46.        then ls:=la+lb-1
  47.        else ls:=la+lb;
  48.   end;
复制代码

[ 本帖最后由 kon3155 于 2009-2-25 13:11 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-25 11:02:38 | 显示全部楼层
习题与练习

一、用高精度计算出s=1!+2!+3!+...+100!。
    参考答案

二、两个高精度数相乘。
    参考答案

三、2k进制数(digital.pas)(NIOP2006第四题)
【问题描述】设r是个2k 进制数,并满足以下条件:
   (1)r至少是个2位的2k 进制数。
   (2)作为2k 进制数,除最后一位外,r的每一位严格小于它右边相邻的那一位。
   (3)将r转换为2进制数q后,则q的总位数不超过w。
    在这里,正整数k(1≤k≤9)和w(k<W≤30000)是事先给定的。
    问:满足上述条件的不同的r共有多少个?
    我们再从另一角度作些解释:设S是长度为w 的01字符串(即字符串S由w个“0”或“1”组成),S对应于上述条件(3)中的q。将S从右起划分为若干个长度为k 的段,每段对应一位2k进制的数,如果S至少可分成2段,则S所对应的二进制数又可以转换为上述的2k 进制数r。
    例:设k=3,w=7。则r是个八进制数(23=8)。由于w=7,长度为7的01字符串按3位一段分,可分为3段(即1,3,3,左边第一段只有一个二进制位),则满足条件的八进制数有:
    2位数:高位为1:6个(即12,13,14,15,16,17),高位为2:5个,…,高位为6:1个(即67)。共6+5+…+1=21个。
    3位数:高位只能是1,第2位为2:5个(即123,124,125,126,127),第2位为3:4个,…,第2位为6:1个(即167)。共5+4+…+1=15个。
    所以,满足要求的r共有36个。
【输入文件】
    输入文件digital.in只有1行,为两个正整数,用一个空格隔开:
k W
【输出文件】
    输出文件digital.out为1行,是一个正整数,为所求的计算结果,即满足条件的不同的r的个数(用十进制数表示),要求最高位不得为0,各数字之间不得插入数字以外的其他字符(例如空格、换行符、逗号等)。
(提示:作为结果的正整数可能很大,但不会超过200位)
【输入样例】
3 7
【输出样例】
36

【题目分析】
    考虑一个首位为r、位数为n且除最后一位每一位严格小于右边的2k进制数,它的种数等于从2k-(r+1)个自然数中选出n-1个升序排列。
    而题目所求答案等于首位为1..2w mod k-1、位数为w/k+1且符合要求的2k进制数种数,加上首位任意、位数不超过w/k不低于2的且符合要求的2k进制数种数。(当w mod k=0时直接考虑后者即可)
    因为k,W是指定的,则可以确定2k进制数r的最长位数是w div k +1,设d=w div k,则d位2k进制数组成的2位以上d位以下的升序排列数应该是:

这里还要比较d与的2k-1大小,必须保证d<=2k-1。
    最后考虑首位的情况,显然首位的最大二进制位数是w mod k,则最大值m=2w mod k  - 1,则首位不大于m,总位数是d+1位的升序排列数应是:
        
这里也要比较d与的2k-1大小,必须保证d<=2k-1-m。
         两者相加即所求,因为最终的运算结果可能会很大,所以必须使用高精度运算。
参考程序
NIOP满分程序

[ 本帖最后由 kon3155 于 2009-2-25 11:27 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-25 11:03:05 | 显示全部楼层
枚举法(通常也称穷举法)是指在一个有穷的可能的解的集合中,枚举出集合中的每一个元素,用题目给定的约束条件去判断其是否符合条件,若满足条件,则该元素即为整个问题的解;否则就不是问题的解。
     【枚举算法解题必须满足下列条件】
    ⑴ 可预先确定解元素的个数n,且问题的规模不是很大;
    ⑵ 对于每个解变量A1,A2,…An的可能值必须为一个连续的值域。
    【枚举算法实现】
    通常使用嵌套的FOR结构循环语句枚举每个变量的取值,在最里层的循环中判断是否满足给定的条件,若满足则输出一个解。
    【枚举算法优化】
    ⑴ 减少枚举的变量。
     在使用枚举法之前,先考虑一下解元素之间的关联,将那些能由已枚举解元素推算出来的变量直接用计算表达式代替。
    ⑵ 减少枚举变量的值域。
    通过各枚举变量间的数学关系定义解元素的值域,在保证不遗漏的情况下越小越好。
    ⑶ 分解约束条件。
    将拆分的约束条件嵌套在相应的循环体间,即尽可能根据约束条件减少变量个数和缩小值域。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-1-20 09:26 , Processed in 0.058272 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表