acm程序的算法模板与经典算法大集合.pdf

ACM 程序算法模板 （后半部分为经典算法大集合） 一、组合数学3 1.1、重复性全排列算法3 1.2、C （m,n ）3 1.3、无重复全组合4 1.4、大数相加5 二、数论7 2.1 、最大公约数7 2.2 、乘方取余7 2.3 、进制转换8 2.4 、素数表9 2.5 、素数表精简9 2.6 、N 阶乘最后非0 位 10 2.7 、约瑟夫环（不带路径） 10 2.8 、约瑟夫环（带路径） 10 2.9 、质因数分解 11 2.10 、判断是否为质数 12 2.11 、欧拉函数 12 三、数据结构 13 3.1、最小代价生成树—普利姆算法 13 四、动态规划 15 4.1 、LIS 最长不下降序列的算法 15 4.2 、交通最短路径算法 17 4.3 、数塔最大值算法 18 4.4 、最小代价字母树 19 4.5 、最长公共字串LCS 19 4.6 、可中断最长字串20 4.7 、从数组中取定值21 4.8 、最近点对22 4.9 、24 点25 4.10 、01 背包 极大界定 原始算法27 4.11 、01 背包 极大界定 空间优化30 4.12 、01 背包 恰好装满 附带组成31 4.13 、01 背包 恰好装满 空间优化34 4.14 、完全背包 恰好装满 买咖啡题35 4.15 、完全背包 极大界定 原始算法37 4.16 、背包扩展 等价匹配种数统计39 五、串40 5.1、KMP 算法40 六、高精度算法41 6.1 通用函数41 6.2、高精度加法42 6.3、高精度减法43 6.4、高精度乘法--高精度乘以低精度45 6.5、高精度乘法--高精度乘以高精度46 6.6、整型常量的阶乘47 6.7、整型常量的阶乘和47 6.8、高精度的乘方，幂数为整型常量48 6.9、高精度除法--高精度除以低精度，只产生余数48 6.10、高精度除法--高精度除以高精度，只产生余数49 七、排序搜索51 7.1、插入排序51 7.2、堆排序51 7.3、合并排序（分治）53 7.4、计数排序54 7.5、冒泡排序55 7.6、快速排序55 7.7、二分搜索56 八、技巧56 8.1、输入技巧56 8.2、递归57 8.3、位运算57 8.4、字典序57 8.5、省略末尾零57 一、组合数学 1.1、重复性全排列算法 #include iostream #include algorithm using namespace std; int main() { char s[101]; 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;