pascal-基本算法

基本算法模块对于NOIP，基础是相当重要的，在3个小时之内做完4道题，那么就要求我们有相当快的速度。特别是对于一些简单的、常用的算法模块，一定要要熟练掌握并灵活运用。由于NOIP是一个比较基础的比赛，因此基本算法的掌握尤为重要，所以要求能够把这些基本的模块快速、准确的移植到不同的程序中，才能在稳中取胜。基本算法模块中最重要的是基本程序框架，也就是说，要养成适合于自己的程序风格，这样对于程序编写的速度与程序的准确度都有较大的提高。模块目录一、排序1．选择排序2．插入排序3．冒泡排序4．快速排序5．堆排序6．归并排序7．线性时间排序二、高精度1．高精度比较2．高精度加法3．高精度减法4．单精度乘法5．高精度乘法6．单精度除法7．高精度除法8．进制转换三、数论1．欧几里德算法2．扩展欧几里德3．求最小公倍数4．求解线形同余方程5．素数的判断6．素数的生成四、排列组合1．排列生成算法2．组合生成算法3．排列按序生成法4．排列字典序生成法五、图论1．图的读入2．深度优先搜索3．广度优先搜索4．强连同分量5．拓扑排序6．最小生成树7．最短路径六、背包问题1．装满背包2．一维价值最大背包3．二位价值最大背包一、排序算法vara:array[1..maxn]oflongint;——排序对象1．选择排序——Select_sortprocedureselect_sort;beginfori:=1ton-1doforj:=i+1tondoifa[i]a[j]thenbegintemp:=a[i];a[i]:=a[j];a[j]:=temp;end;end;2．插入排序——Insert_sortprocedureinsert_sort;beginfori:=2tondobeginkey:=a[i];j:=i-1;while(keya[j])and(j0)dobegina[j+1]:=a[j];dec(j);end;a[j+1]:=key;end;end;3．冒泡排序——Bubble_sortprocedurebubble_sort;beginfori:=1ton-1doforj:=ndowntoi+1doifa[j]a[j-1]thenbegintemp:=a[j];a[j]:=a[j-1];a[j-1]:=temp;end;end;4．快速排序——Quick_sortprocedureqsort(s,t:longint);vari,j,x:longint;begini:=s;j:=t;x:=a[(i+j)div2];repeatwhilea[i]xdoinc(i);{找左边比他大的}whilea[j]xdodec(j);{找右边比他小的}ifi=jthen{交换}begintemp:=a[i];a[i]:=a[j];a[j]:=temp;inc(i);dec(j);end;untilij;ifsjthenqsort(s,j);ifitthenqsort(i,t);end;5．堆排序——Heap_sortprocedureheap(i,n:longint);{将第i个元素向下筛}varj,x:longint;beginj:=i*2;x:=a[i];whilej=ndobeginif(jn)and(a[j]a[j+1])theninc(j);ifxa[j]thenbegina[i]:=a[j];i:=j;j:=i*2;endelsej:=n+1;end;a[i]:=x;end;procedureheap_sort;beginfori:=ndiv2downto1doheap(i,n);fori:=ndownto2dobegintemp:=a[i];a[i]:=a[1];a[1]:=temp;heap(1,i-1);end;end;6．归并排序——Merge_sortproceduremergesort(s,t:longint);varm,i,j,k:longint;beginift-s=0thenexit;m:=(s+t)div2;mergesort(s,m);mergesort(m+1,t);fori:=1tom-s+1dob[i]:=a[s+i-1];forj:=m+1totdoc[j-m]:=a[j];i:=1;j:=1;b[m-s+2]:=max;c[t-m+1]:=max;fork:=stotdoifb[i]c[j]thenbegina[k]:=b[i];inc(i);endelsebegina[k]:=c[j];inc(j);end;end;7．线性时间排序——基数排序、计数排序、桶排序二、高精度算法——High_precisionconstmaxcount=进制位maxlen=记录高精度数组大小typebignum=array[0..maxlen]oflongint;0为位数1．高精度比较functioncompare(a,b:bignum):longint;beginwhilea[a[0]]=0dodec(a[0]);{检查位数是否正确}whileb[b[0]]=0dodec(b[0]);whilea[a[0]+1]0doinc(a[0]);whileb[b[0]+1]0doinc(b[0]);ifa[0]b[0]thenexit(1);ifa[0]b[0]thenexit(-1);fori:=a[0]downto1dobeginifa[i]b[i]thenexit(1);ifa[i]b[i]thenexit(-1);end;exit(0);end;2．高精度加法procedureadd(a,b:bignum;varc:bignum);vari:longint;beginfillchar(c,sizeof(c),0);c[0]:=1;ifa[0]b[0]thenc[0]:=a[0]elsec[0]:=b[0];fori:=1toa[0]doinc(c[i],a[i]);fori:=1tob[0]doinc(c[i],b[i]);fori:=1toc[0]dobegininc(c[i+1],c[i]divmaxcount);c[i]:=c[i]mod10;end;whilec[c[0]+1]0dobegininc(c[0]);inc(c[c[0]+1],c[c[0]]divmaxcount);c[c[0]]:=c[c[0]]modmaxcount;end;end;3．高精度减法procedureminus(a,b:bignum;varc:bignum);vari:longint;beginfillchar(c,sizeof(c),0);c[0]:=a[0];fori:=1toc[0]doc[i]:=a[i]-b[i];fori:=1toc[0]doifc[i]0thenbegindec(c[i+1]);inc(c[i],maxcount);end;while(c[0]1)and(c[c[0]]=0)dodec(c[0]);end;4．单精度乘法proceduremulnum(a:bignum;x:longint,varc:bignum);vari:longint;beginfillchar(c,sizeof(c),0);c[0]:=a[0];fori:=1toc[0]doc[i]:=a[i]*x;fori:=1toc[0]dobegininc(c[i+1],c[i]divmaxcount);c[i]:=c[i]mod10;end;whilec[c[0]+1]0dobegininc(c[0]);inc(c[c[0]+1],c[c[0]]divmaxcount);c[c[0]]:=c[c[0]]modmaxcount;end;end;5．高精度乘法proceduremul(a,b:bignum;varc:bignum);vari,j:longint;beginfillchar(c,sizeof(c),0);c[0]:=a[0]+b[0]-1;fori:=1toa[0]doforj:=1tob[0]doinc(c[i+j-1],a[i]*b[j]);fori:=1toc[0]dobegininc(c[i+1],c[i]divmaxcount);c[i]:=c[i]mod10;end;whilec[c[0]+1]0dobegininc(c[0]);inc(c[c[0]+1],c[c[0]]divmaxcount);c[c[0]]:=c[c[0]]modmaxcount;end;end;6．单精度除法functiondivnum(a:bignum;x:longint;varc:bignum):longint;vari,temp:longint;beginfillchar(c,sizeof(c),0);c[0]:=a[0];temp:=0;fori:=a[0]downto1dobegintemp:=temp*maxcount+a[i];c[i]:=tempdivx;temp:=tempmodx;end;while(c[o]1)and(c[c[0]]=0)dodec(c[0]);exit(temp);end;7．高精度除法procedurediv(a,b:bignum;varc,d:bignum);vari:longint;beginfillchar(c,sizeof(c),0);c[0]:=a[0]-b[0]+1;fillchar(d,sizeof(d),0);d[0]:=1;fori:=c[0]downto1dobeginc[i]:=maxcount;repeatdec(c[i]);mul(c,b,temp);untilcompare(a,temp)=0;end;while(c[o]1)and(c[c[0]]=0)dodec(c[0]);minus(a,temp,d);end;8．进制转换10进制数用bignum记，maxcount=10k进制数用string记constrepchar:array[0..35]ofstring=(‘0’,‘1’,’2’,……,’a’,’b’,……,’z’);——数码对应的字符repnum:array[48..122]oflongint=(0,1,2……,34,35);——字符的ASCCI码对应的数码k进制转十进制：procedurechange_to_ten(s:string;k:longint):bignum;vari,l:longint;temp:bignum;beginl:=length(s);temp[0]:=1;temp[1]:=repnum[ord(s[l])];fori:=1tol-1dobegininc(temp[1],repnum[ord(s[l-i])]);mulnum(temp,k);end;exit(temp);end;十进制转k进制：procedurechange_to_k(num:bignum;k:longint):string;vari,temp:longint;s:string;beginif(num[0]=1)and(num[1]=0)thenexit(‘0’);whilenot((num[0]=1)and(num[1]=0))dobegintemp:=divnum(num,k,num);s:=repchar[temp]+s;end;exit(s);end;三、数论算法1．求最大公约数——gcd（欧几里德算法）递归(recursion)：functiongcd(a,b:longint):longint;beginifb=0thenexit(a);exit(gcd(b,amodb));end;非递归(iterative)：functiongcd(a,b:longint):longint;vart:longint;beginwhileb0dobegint:=a;a:=b;b:=tmodb;end;exit(