《acm程序算法模板》由会员分享，可在线阅读，更多相关《acm程序算法模板（54页珍藏版）》请在金锄头文库上搜索。
1、剑云雨啸 ACM算法总结ACM程序算法模板目录一、组合数学11.1、重复性全排列算法11.2、C（m,n）11.3、无重复全组合21.4、大数相加3二、数论52.1、最大公约数52.2、乘方取余52.3、进制转换52.4、素数表62.5、素数表精简72.6、N阶乘最后非0位72.7、约瑟夫环（不带路径）82.8、约瑟夫环（带路径）82.9、质因数分解92.10、判断是否为质数92.11、欧拉函数10三、数据结构113.1、最小代价生成树普利姆算法11四、动态规划124.1、LIS最长不下降序列的算法124.2、交通最短路径算法144.3、数塔最大值算法154.4、最小代价字母树154.5、最长
2、公共字串LCS164.6、可中断最长字串174.7、从数组中取定值184.8、最近点对194.9、24点214.10、01背包 极大界定 原始算法234.11、01背包 极大界定 空间优化264.12、01背包 恰好装满 附带组成274.13、01背包 恰好装满 空间优化304.14、完全背包 恰好装满 买咖啡题314.15、完全背包 极大界定 原始算法334.16、背包扩展 等价匹配种数统计34五、串355.1、KMP算法35六、高精度算法366.1通用函数366.2、高精度加法376.3、高精度减法386.4、高精度乘法-高精度乘以低精度406.5、高精度乘法-高精度乘以高精度416.6、
3、整型常量的阶乘416.7、整型常量的阶乘和426.8、高精度的乘方，幂数为整型常量426.9、高精度除法-高精度除以低精度，只产生余数436.10、高精度除法-高精度除以高精度，只产生余数44七、排序搜索457.1、插入排序457.2、堆排序467.3、合并排序（分治）477.4、计数排序487.5、冒泡排序497.6、快速排序497.7、二分搜索50八、技巧508.1、输入技巧508.2、递归518.3、位运算518.4、字典序518.5、省略末尾零51一、组合数学1.1、重复性全排列算法#include #include using namespace std;int main() cha
4、r s101; while(gets(s) int n=strlen(s); sort(s, s+n); puts(s); while(next_permutation(s, s+n) puts(s); return 0;1.2、C（m,n）int combination(int m,int n)/m为下标，n为上标 if(m 0|n 0|m n) return -1; n=n (m-n)?n:m-n;if(n=0) return 1; int result=m;for(int i=2,j=result-1;i =n;i+,j-) result=result*j/i; return resul
5、t; 1.3、无重复全组合#include #define MAX_N 10int n, m; /输入n个数，其中本质不同的有m个int rcdMAX_N; /记录每个位置填的数int usedMAX_N; /标记m个数可以使用的次数int numMAX_N; /存放输入中本质不同的m个数void unrepeat_combination(int l, int p) int i; for (i=0; il; i+) /每次都输出 printf(%d, rcdi);if (i l-1)printf( ); printf(n); for (i=p; i 0) /若还可以用，则usedi-; /可用
6、次数减1rcdl = numi; /在l位置放上该数unrepeat_combination(l+1, i); /填下一个位置usedi+; /可用次数恢复int read_data() int i, j, val; if (scanf(%d, &n) = EOF)return 0; m = 0; for (i=0; in; i+) scanf(%d, &val);for (j=0; jm; j+)if (numj = val)usedj+;break;if (j = m)numm = val;usedm = 1;m+; return 1;int main() while (read_data
7、()unrepeat_combination(0, 0); return 0;1.4、大数相加#include#include#define max 1000int nummax;char charAmax;char charBmax;char charCmax;void numsum(char charA,char charB,int num) /两个要相加的数和最后的结果保存的数组,并且结果存放在C中memset(num,0,sizeof(num);int lengthA=strlen(charA);int lengthB=strlen(charB);int lengthC=lengthA
8、lengthB?lengthA:lengthB;int i,j;int k=lengthC-1;i=lengthA-1;j=lengthB-1;while(i=0&j=0)numk=charAi+charBj-96;k-;j-;i-;while(i=0)numk=charAi-48;k-;i-;while(j=0)numk=charBj-48;k-;j-;for(i=lengthC-1;i0;i-)numi-1=numi-1+numi/10;numi=numi%10;for(i=1;i=lengthC;i+)charCi=numi-1+48;charC0=(charC1-48)/10+48;c
9、harC1=(charC1-48)%10+48;if(charC0!=0)printf(%c,charC0);for(i=1;i1,k); t=(t*t)%k; if(n%2=0) return t; return (t*a)%k;2.3、进制转换/10?其他int trans(int n,int d,char s) /数值n，转换成d(2-16)进制表示的字符串sstatic char digits=0123456789ABCDEF;char buf20;int j,i=19;if(d16)s0=0;return 0;bufi=0;dobuf-i=digitsn%d;n/=d;while(n
10、);for(j=0;(sj=bufi)!=0;i+,j+);return j;/其他?10int n2ten(char *x,int n)/其它进制转化成十进制char *a;int i,j,s=0,m=1;for(i=0;xi;i+);a=(char *)malloc(i+1)*sizeof(char);ai=0;for(j=0,i-;i=0;i-,j+)aj=xi;for(j=0;aj;j+)29s+=(int)(aj-0)*m;m*=n;return s;2.4、素数表bool primes100000001; void makeprimes() /素数表的产生，false是素数，这里0，1，2,3默认是。可自己改动memset(primes, 0, sizeof(primes);int i,j;for(j = 4; j 1001; j += 2)primesj = true;for(i =
