C语言经典算法100例（三） |
您所在的位置：网站首页 › c语言经典算法100例pdf › C语言经典算法100例（三） |
C语言经典算法100例（三）
|
1.河内之塔
说明河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡志明市；1883年法国数学家 Edouard Lucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。 解法如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B当作辅助柱。如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A->B、A ->C、B->C这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。事实上，若有n个盘子，则移动完毕所需之次数为2^n - 1，所以当盘数为64时，则所需次数为：264- 1 = 18446744073709551615为5.05390248594782e+16年，也就是约5000世纪，如果对这数字没什幺概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。 /************************************************************************/ /* 汉诺塔问题 */ /************************************************************************/ void Hanoi(int n,char A,char B,char C) { if(n == 1) { printf("Move sheet %d from %c to %c \n",n,A,C); } else { Hanoi(n-1,A,C,B); printf("Move sheet %d from %c to %c \n",n,A,B); Hanoi(n-1,B,A,C); } }2. 费式数列 说明 Fibonacci为1200年代的欧洲数学家，在他的着作中曾经提到：「若有一只免子每个月生一只小免子，一个月后小免子也开始生产。起初只有一只免子，一个月后就有两只免子，二个月后有三只免子，三个月后有五只免子（小免子投入生产）......。 如果不太理解这个例子的话，举个图就知道了，注意新生的小免子需一个月成长期才会投入生产，类似的道理也可以用于植物的生长，这就是Fibonacci数列，一般习惯称之为费氏数列，例如以下： 1、1 、2、3、5、8、13、21、34、55、89...... /************************************************************************/ /* fibonacci数列 */ /************************************************************************/ void fibonacci() { int Fib[N] = {0}; int i = 0; Fib[0] = 0; Fib[1] = 1; for(i = 2; i < N; i++) Fib[i] = Fib[i-1] + Fib[i-2]; for(i = 1; i < N; i++) printf("%d ",Fib[i]); printf("\n"); }3. 字串核对 说明今日的一些高阶程式语言对于字串的处理支援越来越强大（例如Java、Perl等），不过字串搜寻本身仍是个值得探讨的课题，在这边以Boyer- Moore法来说明如何进行字串说明，这个方法快且原理简洁易懂。 解法字串搜寻本身不难，使用暴力法也可以求解，但如何快速搜寻字串就不简单了，传统的字串搜寻是从关键字与字串的开头开始比对，例如Knuth-Morris-Pratt演算法字串搜寻，这个方法也不错，不过要花时间在公式计算上；Boyer-Moore字串核对改由关键字的后面开始核对字串，并制作前进表，如果比对不符合则依前进表中的值前进至下一个核对处，假设是p好了，然后比对字串中p-n+1至p的值是否与关键字相同。 如果关键字中有重复出现的字元，则前进值就会有两个以上的值，此时则取前进值较小的值，如此就不会跳过可能的位置，例如texture这个关键字，t的前进值应该取后面的3而不是取前面的7。 #include #include #include void table(char*); // 建立前进表 int search(int, char*, char*); // 搜寻关键字 void substring(char*, char*, int, int); // 取出子字串 int skip[256]; int main(void) { char str_input[80]; char str_key[80]; char tmp[80] = {'\0'}; int m, n, p; printf("请输入字串："); gets(str_input); printf("请输入搜寻关键字："); gets(str_key); m = strlen(str_input); // 计算字串长度 n = strlen(str_key); table(str_key); p = search(n-1, str_input, str_key); while(p != -1) { substring(str_input, tmp, p, m); printf("%s\n", tmp); p = search(p+n+1, str_input, str_key); } printf("\n"); return 0; } void table(char *key) { int k, n; n = strlen(key); for(k = 0; k {2, 2, 2, 2, 2, 2, 2, 2, 2}, {2, 0, 0, 0, 0, 0, 0, 0, 2}, {2, 0, 2, 2, 0, 2, 2, 0, 2}, {2, 0, 2, 0, 0, 2, 0, 0, 2}, {2, 0, 2, 0, 2, 0, 2, 0, 2}, {2, 0, 0, 0, 0, 0, 2, 0, 2}, {2, 2, 0, 2, 2, 0, 2, 2, 2}, {2, 0, 0, 0, 0, 0, 0, 0, 2}, {2, 2, 2, 2, 2, 2, 2, 2, 2}}; int startI = 1, startJ = 1; // 入口 int endI = 7, endJ = 7; // 出口 int main(void) { int i, j; printf("显示迷宫：\n"); for(i = 0; i < 7; i++) { for(j = 0; j < 7; j++) if(maze[i][j] == 2) printf("█"); else printf(" "); printf("\n"); } visit(startI, startJ); return 0; } void visit(int i, int j) { int m, n; maze[i][j] = 1; if(i == endI && j == endJ) { printf("\n显示路径：\n"); for(m = 0; m < 9; m++) { for(n = 0; n < 9; n++) if(maze[m][n] == 2) printf("█"); else if(maze[m][n] == 1) printf("◇"); else printf(" "); printf("\n"); } } if(maze[i][j+1] == 0) visit(i, j+1); if(maze[i+1][j] == 0) visit(i+1, j); if(maze[i][j-1] == 0) visit(i, j-1); if(maze[i-1][j] == 0) visit(i-1, j); maze[i][j] = 0; }7. 骑士走棋盘 说明骑士旅游（Knight tour）在十八世纪初倍受数学家与拼图迷的注意，它什么时候被提出已不可考，骑士的走法为西洋棋的走法，骑士可以由任一个位置出发，它要如何走完[所有的位置？ 解法骑士的走法，基本上可以使用递回来解决，但是纯綷的递回在维度大时相当没有效率，一个聪明的解法由J.C. Warnsdorff在1823年提出，简单的说，先将最难的位置走完，接下来的路就宽广了，骑士所要走的下一步，「为下一步再选择时，所能走的步数最少的一步。」，使用这个方法，在不使用递回的情况下，可以有较高的机率找出走法（找不到走法的机会也是有的）。 #include int board[8][8] = {0}; int travel(int x, int y) { // 对应骑士可走的八个方向 int ktmove1[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; int ktmove2[8] = {1, 2, 2, 1, -1, -2, -2, -1}; // 测试下一步的出路 int nexti[8] = {0}; int nextj[8] = {0}; // 记录出路的个数 int exists[8] = {0}; int i, j, k, m, l; int tmpi, tmpj; int count, min, tmp; i = x; j = y; board[i][j] = 1; for(m = 2; m 7 || tmpj > 7) continue; // 如果这个方向可走，记录下来 if(board[tmpi][tmpj] == 0) { nexti[l] = tmpi; nextj[l] = tmpj; // 可走的方向加一个 l++; } } count = l; // 如果可走的方向为0个，返回 if(count == 0) { return 0; } else if(count == 1) { // 只有一个可走的方向 // 所以直接是最少出路的方向 min = 0; } else { // 找出下一个位置的出路数 for(l = 0; l < count; l++) { for(k = 0; k < 8; k++) { tmpi = nexti[l] + ktmove1[k]; tmpj = nextj[l] + ktmove2[k]; if(tmpi < 0 || tmpj < 0 || tmpi > 7 || tmpj > 7) { continue; } if(board[tmpi][tmpj] == 0) exists[l]++; } } tmp = exists[0]; min = 0; // 从可走的方向中寻找最少出路的方向 for(l = 1; l < count; l++) { if(exists[l] < tmp) { tmp = exists[l]; min = l; } } } // 走最少出路的方向 i = nexti[min]; j = nextj[min]; board[i][j] = m; } return 1; } int main(void) { int startx, starty; int i, j; printf("输入起始点："); scanf("%d %d", &startx, &starty); if(travel(startx, starty)) { printf("游历完成！\n"); } else { printf("游历失败！\n"); } for(i = 0; i < 8; i++) { for(j = 0; j < 8; j++) { printf("%2d ", board[i][j]); } putchar('\n'); } return 0; }8.八皇后 说明西洋棋中的皇后可以直线前进，吃掉遇到的所有棋子，如果棋盘上有八个皇后，则这八个皇后如何相安无事的放置在棋盘上，1970年与1971年， E.W.Dijkstra与N.Wirth曾经用这个问题来讲解程式设计之技巧。 解法关于棋盘的问题，都可以用递回求解，然而如何减少递回的次数？在八个皇后的问题中，不必要所有的格子都检查过，例如若某列检查过，该该列的其它格子就不用再检查了，这个方法称为分支修剪。 #include #include #define N 8 int column[N+1]; // 同栏是否有皇后，1表示有 int rup[2*N+1]; // 右上至左下是否有皇后 int lup[2*N+1]; // 左上至右下是否有皇后 int queen[N+1] = {0}; int num; // 解答编号 //void backtrack(int); // 递回求解 void showAnswer() { int x, y; printf("\n解答 %d\n", ++num); for(y = 1; y coins[1]+coins[4]) compare(coins, 0, 4, 1); if(coins[0]+coins[3] < coins[1]+coins[4]) compare(coins, 1, 3, 0); } else if(coins[0]+coins[1]+coins[2] < coins[3]+coins[4]+coins[5]) { if(coins[0]+coins[3] == coins[1]+coins[4]) compare(coins, 5, 2, 0); else if(coins[0]+coins[3] > coins[1]+coins[4]) compare(coins, 3, 1, 0); if(coins[0]+coins[3] < coins[1]+coins[4]) compare(coins, 4, 0, 1); } }10.生命游戏 说明生命游戏（game of life）为1970年由英国数学家J. H. Conway所提出，某一细胞的邻居包括上、下、左、右、左上、左下、右上与右下相邻之细胞，游戏规则如下： 孤单死亡：如果细胞的邻居小于一个，则该细胞在下一次状态将死亡。 拥挤死亡：如果细胞的邻居在四个以上，则该细胞在下一次状态将死亡。 稳定：如果细胞的邻居为二个或三个，则下一次状态为稳定存活。 复活：如果某位置原无细胞存活，而该位置的邻居为三个，则该位置将复活一细胞。 解法生命游戏的规则可简化为以下，并使用CASE比对即可使用程式实作： 邻居个数为0、1、4、5、6、7、8时，则该细胞下次状态为死亡。 邻居个数为2时，则该细胞下次状态为复活。 邻居个数为3时，则该细胞下次状态为稳定。 #include #include #include #define MAXROW 10 #define MAXCOL 25 #define DEAD 0 #define ALIVE 1 int map[MAXROW][MAXCOL], newmap[MAXROW][MAXCOL]; void init(); int neighbors(int, int); void outputMap(); void copyMap(); int main() { int row, col; char ans; init(); while(1) { outputMap(); for(row = 0; row < MAXROW; row++) { for(col = 0; col < MAXCOL; col++) { switch (neighbors(row, col)) { case 0: case 1: case 4: case 5: case 6: case 7: case 8: newmap[row][col] = DEAD; break; case 2: newmap[row][col] = map[row][col]; break; case 3: newmap[row][col] = ALIVE; break; } } } copyMap(); printf("\nContinue next Generation ? "); getchar(); ans = toupper(getchar()); if(ans != 'Y') break; } return 0; } void init() { int row, col; for(row = 0; row < MAXROW; row++) for(col = 0; col < MAXCOL; col++) map[row][col] = DEAD; puts("Game of life Program"); puts("Enter x, y where x, y is living cell"); printf("0 |
【本文地址】
今日新闻 |
推荐新闻 |