《常见算法解题》由会员分享，可在线阅读，更多相关《常见算法解题（23页珍藏版）》请在金锄头文库上搜索。
1、1、汉诺塔算法2、八皇后问题3、费时数列4、八枚硬币的问题5、三色旗的解法6、巴斯卡三角形算法7、背包问题8、Eratosthenes筛选求质数1、河内之塔 (Towers of Hanoi) 是法国人M.Claus(Lucas) 于 1883 年从泰国带至法国的，河内为越战时北越的首都， 即现在的胡志明市；1883 年法国数学家Edouard Lucas曾提及这个故事， 据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag ）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（ Disc ） ，并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘
2、子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。解法如果柱子标为ABC ，要由 A 搬至 C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B 当作辅助柱。如果盘数超过 2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A-B 、A -C、B-C 这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。事实上，若有n 个盘子，则移动完毕所需之次数为2n - 1 ，所以当盘数为64时，则所需次数为：264- 1 = 18446744073709551615 为5.05390248594782e+16年，也就是约
3、 5000 世纪，如果对这数字没什么概念，就假设每秒钟搬一个盘子好了，也要约 5850 亿年左右。C 语言实现C 代码#include void hanoi( int n, char A, char B, char C) if(n = 1) printf(“Move sheet %d from %c to %cn“, n, A, C); else hanoi(n-1, A, C, B); printf(“Move sheet %d from %c to %cn“, n, A, C); hanoi(n-1, B, A, C); int main() int n; printf(“ 请输入盘数：
4、“); scanf(“%d“, hanoi(n, A, B, C); return 0; 2、西洋棋中的皇后可以直线前进，吃掉遇到的所有棋子，如果棋盘上有八个皇后，则这八个皇后如何相安无事的放置在棋盘上，1970 年与 1971 年， E.W.Dijkstra 与 N.Wirth 曾经用这个问题来讲解程式设计之技巧。解法关于棋盘的问题，都可以用递回求解，然而如何减少递回的次数？在八个皇后的问题中，不必要所有的格子都检查过，例如若某列检查过，该该列的其它格子就不用再检查了，这个方法称为分支修剪。所以检查时，先判断是否在已放置皇后的可行进方向上，如果没有再行放置下一个皇后，如此就可大大减少递回的次
5、数，例如以下为修剪过后的递回检查行进路径：八个皇后的话，会有92个解答，如果考虑棋盘的旋转，则旋转后扣去对称的，会有12组基本解。C 语言实现C 代码#include #include #define N 8 int columnN+1; / 同栏是否有皇后，1表示有int rup2*N+1; / 右上至左下是否有皇后int lup2*N+1; / 左上至右下是否有皇后int queenN+1 = 0; int num; / 解答编号void backtrack( int); / 递回求解int main( void ) int i; num = 0; for(i = 1; i N) show
6、Answer(); else for(j = 1; j 1 fn = n if n = 0, 1 C 语言实现C 代码#include #include #define N 20 int main( void ) int FibN = 0; int i; Fib0 = 0; Fib1 = 1; for(i = 2; i #include #include void compare( int , int, int, int); void eightcoins( int); int main( void ) int coins8 = 0; int i; srand(time(NULL); for(
7、i = 0; i coinsk) printf(“n 假币%d 较重 “, i+1); elseprintf(“n 假币%d 较轻 “, j+1); void eightcoins( int coins) if(coins0+coins1+coins2 = coins3+coins4+coins5) if(coins6 coins7) compare(coins, 6, 7, 0); elsecompare(coins, 7, 6, 0); else if(coins0+coins1+coins2 coins3+coins4+coins5) if(coins0+coins3 = coins1+
8、coins4) compare(coins, 2, 5, 0); else if(coins0+coins3 coins1+coins4) compare(coins, 0, 4, 1); if(coins0+coins3 coins1+coins4) compare(coins, 3, 1, 0); if(coins0+coins3 #include #include #define BLUE b #define WHITE w #define RED r #define SWAP(x, y) char temp; temp = colorx; colorx = colory; colory
9、 = temp; int main() char color = r, w, b, w, w, b, r, b, w, r, 0; int wFlag = 0; int bFlag = 0; int rFlag = strlen(color) - 1; int i; for(i = 0; i #define N 12 long combi( int n, int r) int i; long p = 1; for(i = 1; i #include #define LIMIT 8 / 重量限制#define N 5 / 物品种类#define MIN 1 / 最小重量struct body c
10、har name20; int size; int price; ; typedef struct body object; int main( void ) int itemLIMIT+1 = 0; int valueLIMIT+1 = 0; int newvalue, i, s, p; object a = “ 李子 “, 4, 4500, “苹果 “, 5, 5700, “橘子 “, 2, 2250, “草莓 “, 1, 1100, “甜瓜 “, 6, 6700; for(i = 0; i values) / 找到阶段最佳解values = newvalue; items = i; pr
11、intf(“ 物品 t 价格 n“); for(i = LIMIT; i = MIN; i = i - aitemi.size) printf(“%st%dn“, aitemi.name, aitemi.price); printf(“ 合计 t%dn“, valueLIMIT); return 0; 8、“ 除了自身之外，无法被其它整数整除的数” 称之为质数，要求质数很简单，但如何快速的求出质数则一直是程序设计人员与数学家努力的课题，在这边介绍一个著名的Eratosthenes求质数方法。解法首先知道这个问题可以使用循环来求解，将一个指定的数除以所有小于它的数，若可以整除就不是质数，然而如何
12、减少循环的检查次数？如何求出小于N 的所有质数？首先假设要检查的数是N 好了，则事实上只要检查至N 的开根号就可以了，道理很简单，假设A*B = N ，如果 A 大于 N 的开根号，则事实上在小于A 之前的检查就可以先检查到B 这个数可以整除N。不过在程序中使用开根号会精确度的问题，所以可以使用i*i #include #define N 1000 int main( void ) int i, j; int primeN+1; for(i = 2; i = N; i+) primei = 1; for(i = 2; i*i = N; i+) / 这边可以改进if(primei = 1) for(j = 2*i; j = N; j+) if(j % i = 0) primej = 0; for(i = 2; i N; i+) if(primei = 1) printf(“%4d “, i); if(i % 16 = 0) printf(“n“); printf(“n“); return 0;
