pascal-基本算法模块

《pascal-基本算法模块》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基本算法模块ForNOIP2007Billy.Linux对于NOIP，基础是相当重要的，在3个小时之内做完4道题，那么就要求我们有相当快的速度。特别是对于一些简单的、常用的算法模块，一定要要熟练掌握并灵活运用。由于NOIP是一个比较基础的比赛，因此基本算法的掌握尤为重要，所以要求能够把这些基本的模块快速、准确的移植到不同的程序中，才能在稳中取胜。基本算法模块中最重要的是基本程序框架，也就是说，要养成适合于自己的程序风格，这样对于程序编写的速度与程序的准确度都有较大的提高。模块目录一、排序1．选择排序2．插入排序3．冒泡排序4．快速排序5．堆排序6．归并排序7．线性时间排序二、高精度1．高

2、精度比较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_sortprocedur

3、eselect_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(key0)dobegina[j+1]:=a[j];dec(j);end;a[j+1]:=key;end;end;3．冒泡排序——Bubble_sortprocedurebubble_so

4、rt;beginfori:=1ton-1doforj:=ndowntoi+1doifa[j]xdodec(j);{找右边比他小的}ifi<=jthen{交换}begintemp:=a[i];a[

5、i]:=a[j];a[j]:=temp;inc(i);dec(j);end;untili>j;ifs

6、nd;procedureheap_sort;beginfori:=ndiv2downto1doheap(i,n);fori:=ndownto2dobegintemp:=a[i];a[i]:=a[1];a[1]:=temp;heap(1,i-1);end;end;2．归并排序——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];

7、forj:=m+1totdoc[j-m]:=a[j];i:=1;j:=1;b[m-s+2]:=max;c[t-m+1]:=max;fork:=stotdoifb[i]