怎么用数据结构的java语言实现二进制转换为八，十，十六进制？ 就是_百度知道
怎么用数据结构的java语言实现二进制转换为八，十，十六进制？ 就是
怎么用数据结构的java语言实现二进制转换为八，十，十六进制？
就是不用java中现有的函数。
而且在运行之后是“输入一个二进制数:”输入之后Enter 键，就能够分别显示出三个进制的数类似下图
我有更好的答案
System.out.println(&十六进制值:&&+&=&input.next().in)import&new&Scanner(S
System.out.println(&请输入二进制值:&);
String&str&
int&oct&{ public&input&=&十进制值:&&+&2);
Spublic&static&nbsp.println(&quot.out.println(&=&Integer.parseInt(Integer.toOctalString(oct));oct);
System.toHexString(oct));void&nbsp.S八进制值:&&+&nbsp,&Iclass&ConversionOfNumberSystems&java.util.main(String[]&args)&nbsp
我知道java有现有的函数，但是如果不用这些函数呢。😲
自己写其实是一样的,你完全可以直接去看Integer.parseInt(String s, int radix)的源码,他里面实现的就是将任意数字字符串,按照指定进制转成10进制的通用算法,去掉一些校验的逻辑,这个转换算法一共也就三十几行代码
采纳率：75%
来自团队：
其他类似问题
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。当前位置： >>
史上最全最经典数据结构-100个经典算法
C 语言经典算法大全? 老掉牙 河内塔 费式数列 巴斯卡三角形 三色棋 老鼠走迷官（一） 老鼠走迷官（二） 骑士走棋盘 八个皇后 八枚银币 生命游戏 字串核对 双色、三色河内塔 背包问题（Knapsack Problem） ? 数、运算 蒙地卡罗法求 PI Eratosthenes筛选求质数 超长整数运算（大数运算） 长 PI 最大公因数、最小公倍数、因式分解 完美数 阿姆斯壮数 最大访客数 中序式转后序式（前序式） 后序式的运算 ? 关于赌博 洗扑克牌（乱数排列） Craps赌博游戏 约瑟夫问题（Josephus Problem） ? 集合问题 排列组合 格雷码（Gray Code） 产生可能的集合m元素集合的n个元素子集 数字拆解 ? 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap 排序法 - 改良的选择排序 快速排序法（一） 快速排序法（二） 快速排序法（三） 合并排序法 基数排序法 ? 搜寻 循序搜寻法（使用卫兵） 二分搜寻法（搜寻原则的代表） 插补搜寻法 费氏搜寻法 ? 矩阵 稀疏矩阵 多维矩阵转一维矩阵 上三角、下三角、对称矩阵 奇数魔方阵 4N 魔方阵 2(2N+1) 魔方阵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时，则 所需次数为：2 - 1 = .82e+16年，也就是约5000世纪， 如果对这数字没什幺概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。 #include &stdio.h& 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, C); hanoi(n-1, B, A, C); } } int main() { printf(&请输入盘数：&); scanf(&%d&, &n); hanoi(n, 'A', 'B', 'C'); return 0; }642.Algorithm Gossip: 费式数列说明Fibonacci为1200年代的欧洲数学家，在他的着作中曾经提到： 「若有一只免子每个月生一只小免 子，一个月后小免子也开始生产。起初只有一只免子，一个月后就有两只免子，二个月后有三 只免子，三个月后有五只免子（小免子投入生产）......。 如果不太理解这个例子的话，举个图就知道了，注意新生的小免子需一个月成长期才会投入生 产，类似的道理也可以用于植物的生长，这就是Fibonacci数列，一般习惯称之为费氏数列，例 如以下： 1、1 、2、3、5、8、13、21、34、55、89......解法依说明，我们可以将费氏数列定义为以下： fn = fn-1 + fn-2 if n & 1 fn = n if n = 0, 1 #include &stdio.h& #include &stdlib.h& #define N 20 int main(void) { int Fib[N] = {0}; Fib[0] = 0; Fib[1] = 1; for(i = 2; i & N; i++) Fib[i] = Fib[i-1] + Fib[i-2]; for(i = 0; i & N; i++) printf(&%d &, Fib[i]); printf(&\n&); return 0; }3. 巴斯卡三角形#include &stdio.h& #define N 12 long combi(int n, int r){ long p = 1; for(i = 1; i &= i++) p = p * (n-i+1) / } void paint() { int n, r, for(n = 0; n &= N; n++) { for(r = 0; r &= r++) {/* 排版设定开始 */ if(r == 0) { for(i = 0; i &= (N-n); i++) printf(& &); }else { printf(& &); } /* 排版设定结束 */ printf(&%3d&, combi(n, r)); } printf(&\n&); } }4.Algorithm Gossip: 三色棋说明三色旗的问题最早由E.W.Dijkstra所提出，他所使用的用语为Dutch Nation Flag(Dijkstra为荷兰 人)，而多数的作者则使用Three-Color Flag来称之。 假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您 希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上 进行这个动作，而且一次只能调换两个旗子。解法在一条绳子上移动，在程式中也就意味只能使用一个阵列，而不使用其它的阵列来作辅助，问 题的解法很简单，您可以自己想像一下在移动旗子，从绳子开头进行，遇到蓝色往前移，遇到 白色留在中间，遇到红色往后移，如下所示： 只是要让移动次数最少的话，就要有些技巧： 如果图中W所在的位置为白色，则W+1，表示未处理的部份移至至白色群组。 如果W部份为蓝色，则B与W的元素对调，而B与W必须各+1，表示两个群组都多了一个元素。 如果W所在的位置是红色，则将W与R交换，但R要减1，表示未处理的部份减1。 注意B、W、R并不是三色旗的个数，它们只是一个移动的指标；什幺时候移动结束呢？一开始 时未处理的R指标会是等于旗子的总数，当R的索引数减至少于W的索引数时，表示接下来的旗 子就都是红色了，此时就可以结束移动，如下所示： #include &stdio.h& #include &stdlib.h& #include &string.h& #define BLUE 'b' #define WHITE 'w' #define RED 'r' #define SWAP(x, y) { \ temp = color[x]; \ color[x] = color[y]; \ color[y] = } 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; for(i = 0; i & strlen(color); i++) printf(&%c &, color[i]); printf(&\n&); while(wFlag &= rFlag) { if(color[wFlag] == WHITE) wFlag++; else if(color[wFlag] == BLUE) { SWAP(bFlag, wFlag); bFlag++; wFlag++; } else { while(wFlag & rFlag && color[rFlag] == RED) rFlag--; SWAP(rFlag, wFlag); rFlag--; } } for(i = 0; i & strlen(color); i++) printf(&%c &, color[i]); printf(&\n&); return 0; }5.Algorithm Gossip: 老鼠走迷官（一）说明老鼠走迷宫是递回求解的基本题型，我们在二维阵列中使用2表示迷宫墙壁，使用1来表示老鼠的行走路径，试以程式求出由入口至出口的路径。解法老鼠的走法有上、左、下、右四个方向，在每前进一格之后就选一个方向前进，无法前进时退回选择下一个可前进方向，如此在阵列中依序测试四个方向，直到走到出口为止，这是 递回的基本题，请直接看程式应就可以理解。 #include &stdio.h& #include &stdlib.h& int visit(int, int); int maze[7][7] = {{2, 2, 2, 2, 2, 2, 2}, {2, 0, 0, 0, 0, 0, 2}, {2, 0, 2, 0, 2, 0, 2}, {2, 0, 0, 2, 0, 2, 2}, {2, 2, 0, 2, 0, 2, 2}, {2, 0, 0, 0, 0, 0, 2}, {2, 2, 2, 2, 2, 2, 2}}; int startI = 1, startJ = 1; // 入口 int endI = 5, endJ = 5; // 出口 int success = 0; int main(void) { int i, printf(&显示迷宫：\n&); for(i = 0; i & 7; i++) { for(j = 0; j & 7; j++) if(maze[i][j] == 2) printf(&&); else printf(& &); printf(&\n&); } if(visit(startI, startJ) == 0) printf(&\n没有找到出口！\n&);else { printf(&\n显示路径：\n&); for(i = 0; i & 7; i++) { for(j = 0; j & 7; j++) { if(maze[i][j] == 2) printf(&&); else if(maze[i][j] == 1) printf(&◇ &); else printf(& &); } printf(&\n&); } } return 0; } int visit(int i, int j) { maze[i][j] = 1; if(i == endI && j == endJ) success = 1; if(success != 1 && maze[i][j+1] == 0) visit(i, j+1); if(success != 1 && maze[i+1][j] == 0) visit(i+1, j); if(success != 1 && maze[i][j-1] == 0) visit(i, j-1); if(success != 1 && maze[i-1][j] == 0) visit(i-1, j); if(success != 1) maze[i][j] = 0; }6.Algorithm Gossip: 老鼠走迷官（二）说明由于迷宫的设计， 老鼠走迷宫的入口至出口路径可能不只一条， 如何求出所有的路径呢？ 解法求所有路径看起来复杂但其实更简单，只要在老鼠走至出口时显示经过的路径，然后退回上一格重新选择下一个位置继续递回就可以了，比求出单一路径还简单，我们的程式只要作 一点修改就可以了。 #include &stdio.h& #include &stdlib.h& void visit(int, int); int maze[9][9] = {{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, 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, 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.Algorithm Gossip: 骑士走棋盘说明骑士旅游（Knighttour）在十八世纪初倍受数学家与拼图迷的注意，它什么时候被提出已不可考，骑士的走法为西洋棋的走法，骑士可以由任一个位置出发，它要如何走完[所有的位 置？解法骑士的走法，基本上可以使用递回来解决，但是纯\的递回在维度大时相当没有效率，一个聪明的解法由J.C. Warnsdorff在1823年提出，简单的说，先将最难的位置走完，接下来的路 就宽广了，骑士所要走的下一步， 「为下一步再选择时，所能走的步数最少的一步。 」 ，使用这个 方法，在不使用递回的情况下，可以有较高的机率找出走法（找不到走法的机会也是有的） 。 #include &stdio.h& int board[8][8] = {0}; int main(void) { int startx, int i, 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; } 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, int tmpi, int count, min, i = j = board[i][j] = 1; for(m = 2; m &= 64; m++) { for(l = 0; l & 8; l++) exists[l] = 0; l = 0; // 试探八个方向 for(k = 0; k & 8; k++) { tmpi = i + ktmove1[k]; tmpj = j + ktmove2[k]; // 如果是边界了，不可走 if(tmpi & 0 || tmpj & 0 || tmpi & 7 || tmpj & 7) // 如果这个方向可走，记录下来 if(board[tmpi][tmpj] == 0) { nexti[l] = nextj[l] = // 可走的方向加一个 l++; } } count = // 如果可走的方向为0个，返回 if(count == 0) {return 0; } else if(count == 1) { // 只有一个可走的方向 // 所以直接是最少出路的方向 min = 0; } else { // 找出下一个位置的出路数 for(l = 0; l & 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) { } if(board[tmpi][tmpj] == 0) exists[l]++; } } tmp = exists[0]; min = 0; // 从可走的方向中寻找最少出路的方向 for(l = 1; l & l++) { if(exists[l] & tmp) { tmp = exists[l]; min = } } } // 走最少出路的方向 i = nexti[min]; j = nextj[min]; board[i][j] = } return 1; }8.Algorithm Gossip: 八皇后说明西洋棋中的皇后可以直线前进，吃掉遇到的所有棋子，如果棋盘上有八个皇后，则这八个皇后如何相安无事的放置在棋盘上，1970年与1971年， E.W.Dijkstra与N.Wirth曾经用这个问 题来讲解程式设计之技巧。解法关于棋盘的问题，都可以用递回求解，然而如何减少递回的次数？在八个皇后的问题中，不必要所有的格子都检查过，例如若某列检查过，该该列的其它格子就不用再检查了，这个方 法称为分支修剪。#include &stdio.h& #include &stdlib.h& #define N 8 int column[N+1]; // 同栏是否有皇后，1表示有 int rup[2*N+1]; // 右上至左下是否有皇后 int lup[2*N+1]; // 左上至右下是否有皇后 int queen[N+1] = {0}; // 解答编号 void backtrack(int); // 递回求解 int main(void) { num = 0; for(i = 1; i &= N; i++) column[i] = 1; for(i = 1; i &= 2*N; i++) rup[i] = lup[i] = 1; backtrack(1); return 0; } void showAnswer() { int x,printf(&\n解答 %d\n&, ++num); for(y = 1; y &= N; y++) { for(x = 1; x &= N; x++) { if(queen[y] == x) { printf(& Q&); } else { printf(& .&); } } printf(&\n&); } } void backtrack(int i) { if(i & N) { showAnswer(); } else { for(j = 1; j &= N; j++) { if(column[j] == 1 && rup[i+j] == 1 && lup[i-j+N] == 1) { queen[i] = // 设定为占用 column[j] = rup[i+j] = lup[i-j+N] = 0; backtrack(i+1); column[j] = rup[i+j] = lup[i-j+N] = 1; } } } }9.Algorithm Gossip: 八枚银币说明现有八枚银币a b c d e f g h，已知其中一枚是假币，其重量不同于真币，但不知是较轻或较重，如何使用天平以最少的比较次数，决定出哪枚是假币，并得知假币比真币较轻或较重。解法单就求假币的问题是不难，但问题限制使用最少的比较次数，所以我们不能以单纯的回圈比较来求解，我们可以使用决策树（decision tree） ，使用分析与树状图来协助求解。一个简单 的状况是这样的，我们比较a+b+c与d+e+f ，如果相等，则假币必是g或h，我们先比较g或h哪个 较重，如果g较重，再与a比较（a是真币） ，如果g等于a，则g为真币，则h为假币，由于h比g轻 而 g是真币，则h假币的重量比真币轻。#include &stdio.h& #include &stdlib.h& #include &time.h& void compare(int[], int, int, int); void eightcoins(int[]); int main(void) { int coins[8] = {0}; srand(time(NULL)); for(i = 0; i & 8; i++) coins[i] = 10; printf(&\n输入假币重量(比10大或小)：&); scanf(&%d&, &i); coins[rand() % 8] = eightcoins(coins); printf(&\n\n列出所有钱币重量：&); for(i = 0; i & 8; i++) printf(&%d &, coins[i]); printf(&\n&); return 0;} void compare(int coins[], int i, int j, int k) { if(coins[i] & coins[k]) printf(&\n假币 %d 较重&, i+1); else printf(&\n假币 %d 较轻&, j+1); } void eightcoins(int coins[]) { if(coins[0]+coins[1]+coins[2] == coins[3]+coins[4]+coins[5]) { if(coins[6] & coins[7]) compare(coins, 6, 7, 0); else compare(coins, 7, 6, 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, 2, 5, 0); else if(coins[0]+coins[3] & 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.Algorithm Gossip: 生命游戏说明生命游戏（game of life）为1970年由英国数学家J. H. Conway所提出，某一细胞的邻居包括上、下、左、右、左上、左下、右上与右下相邻之细胞，游戏规则如下： 孤单死亡：如果细胞的邻居小于一个，则该细胞在下一次状态将死亡。 拥挤死亡：如果细胞的邻居在四个以上，则该细胞在下一次状态将死亡。 稳定：如果细胞的邻居为二个或三个，则下一次状态为稳定存活。 复活：如果某位置原无细胞存活，而该位置的邻居为三个，则该位置将复活一细胞。解法生命游戏的规则可简化为以下，并使用CASE比对即可使用程式实作：邻居个数为0、1、4、5、6、7、8时，则该细胞下次状态为死亡。 邻居个数为2时，则该细胞下次状态为复活。 邻居个数为3时，则该细胞下次状态为稳定。 #include &stdio.h& #include &stdlib.h& #include &ctype.h& #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, 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; case 2: newmap[row][col] = map[row][col]; case 3: newmap[row][col] = ALIVE; } } } copyMap(); printf(&\nContinue next Generation ? &); getchar(); ans = toupper(getchar()); if(ans != 'Y') } return 0; } void init() { int row, 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 &= x &= %d, 0 &= y &= %d\n&, MAXROW-1, MAXCOL-1); puts(&Terminate with x, y = -1, -1&); while(1) { scanf(&%d %d&, &row, &col); if(0 &= row && row & MAXROW &&0 &= col && col & MAXCOL) map[row][col] = ALIVE; else if(row == -1 || col == -1) else printf(&(x, y) exceeds map ranage!&); } } int neighbors(int row, int col) { int count = 0, c, for(r = row-1; r &= row+1; r++) for(c = col-1; c &= col+1; c++) { if(r & 0 || r &= MAXROW || c & 0 || c &= MAXCOL) if(map[r][c] == ALIVE) count++; } if(map[row][col] == ALIVE) count--; } void outputMap() { int row, printf(&\n\n%20cGame of life cell status\n&); for(row = 0; row & MAXROW; row++) { printf(&\n%20c&, ' '); for(col = 0; col & MAXCOL; col++) if(map[row][col] == ALIVE) putchar('#'); else putchar('-'); } } void copyMap() { int row, for(row = 0; row & MAXROW; row++) for(col = 0; col & MAXCOL; col++) map[row][col] = newmap[row][col]; }11.Algorithm Gossip: 字串核对说明今日的一些高阶程式语言对于字串的处理支援越来越强大（例如Java、Perl等） ，不过字串搜寻本身仍是个值得探讨的课题，在这边以Boyer- Moore法来说明如何进行字串说明，这个 方法快且原理简洁易懂。解法字串搜寻本身不难，使用暴力法也可以求解，但如何快速搜寻字串就不简单了，传统的字串搜寻是从关键字与字串的开头开始比对，例如 Knuth-Morris-Pratt 演算法 字串搜寻，这个 方法也不错，不过要花时间在公式计算上；Boyer-Moore字串核对改由关键字的后面开始核对字 串，并制作前进表，如果比对不符合则依前进表中的值前进至下一个核对处，假设是p好了，然 后比对字串中p-n+1至p的值是否与关键字相同。 如果关键字中有重复出现的字元，则前进值就会有两个以上的值，此时则取前进值较小的值， 如此就不会跳过可能的位置， 例如texture这个关键字， t的前进值应该取后面的3而不是取前面的 7。 #include &stdio.h& #include &stdlib.h& #include &string.h& 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, 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 = strlen(key); for(k = 0; k &= 255; k++) skip[k] = for(k = 0; k & n - 1; k++) skip[key[k]] = n - k - 1; } int search(int p, char* input, char* key) { int i, m, char tmp[80] = {'\0'}; m = strlen(input); n = strlen(key); while(p & m) { substring(input, tmp, p-n+1, p); if(!strcmp(tmp, key)) // 比较两字串是否相同 return p-n+1; p += skip[input[p]]; } return -1; } void substring(char *text, char* tmp, int s, int e) { int i, for(i = s, j = 0; i &= i++, j++) mp[j] = text[i]; tmp[j] = '\0'; }12.Algorithm Gossip: 双色、三色河内塔说明双色河内塔与三色河内塔是由之前所介绍过的河内塔规则衍生而来，双色河内塔的目的是将下图左上的圆环位置经移动成为右下的圆环位置：而三色河内塔则是将下图左上的圆环经移动成为右上的圆环：解法无论是双色河内塔或是三色河内塔，其解法观念与之前介绍过的河内塔是类似的，同样也是使用递回来解，不过这次递回解法的目的不同，我们先来看只有两个盘的情况，这很简单， 只要将第一柱的黄色移动至第二柱，而接下来第一柱的蓝色移动至第三柱。 再来是四个盘的情况，首先必须用递回完成下图左上至右下的移动：接下来最底层的就不用管它们了，因为它们已经就定位，只要再处理第一柱的上面两个盘子就 可以了。那么六个盘的情况呢？一样！首先必须用递回完成下图左上至右下的移动：接下来最底层的就不用管它们了，因为它们已经就定位，只要再处理第一柱上面的四个盘子就 可以了，这又与之前只有四盘的情况相同，接下来您就知道该如何进行解题了，无论是八个盘、 十个盘以上等，都是用这个观念来解题。 那么三色河内塔呢？一样，直接来看九个盘的情况，首先必须完成下图的移动结果：接下来最底两层的就不用管它们了，因为它们已经就定位，只要再处理第一柱上面的三个盘子 就可以了。双色河内塔 C 实作 #include &stdio.h& void hanoi(int disks, char source, char temp, char target) { if (disks == 1) { printf(&move disk from %c to %c\n&, source, target); printf(&move disk from %c to %c\n&, source, target); } else { hanoi(disks-1, source, target, temp); hanoi(1, source, temp, target); hanoi(disks-1, temp, source, target); } } void hanoi2colors(int disks) { char source = 'A'; char temp = 'B'; char target = 'C'; for(i = disks / 2; i & 1; i--) { hanoi(i-1, source, temp, target); printf(&move disk from %c to %c\n&, source, temp); printf(&move disk from %c to %c\n&, source, temp); hanoi(i-1, target, temp, source); printf(&move disk from %c to %c\n&, temp, target); }printf(&move disk from %c to %c\n&, source, temp); printf(&move disk from %c to %c\n&, source, target); } int main() { printf(&请输入盘数：&); scanf(&%d&, &n); hanoi2colors(n); return 0; } 三色河内塔 C 实作 #include &stdio.h& void hanoi(int disks, char source, char temp, char target) { if (disks == 1) { printf(&move disk from %c to %c\n&, source, target); printf(&move disk from %c to %c\n&, source, target); printf(&move disk from %c to %c\n&, source, target); } else { hanoi(disks-1, source, target, temp); hanoi(1, source, temp, target); hanoi(disks-1, temp, source, target); } } void hanoi3colors(int disks) { char source = 'A'; char temp = 'B'; char target = 'C'; if(disks == 3) { printf(&move disk from %c to %c\n&, source, temp); printf(&move disk from %c to %c\n&, source, temp); printf(&move disk from %c to %c\n&, source, target); printf(&move disk from %c to %c\n&, temp, target); printf(&move disk from %c to %c\n&, temp, source); printf(&move disk from %c to %c\n&, target, temp);;} else { hanoi(disks/3-1, source, temp, target); printf(&move disk from %c to %c\n&, source, temp); printf(&move disk from %c to %c\n&, source, temp); printf(&move disk from %c to %c\n&, source, temp); hanoi(disks/3-1, target, temp, source); printf(&move disk from %c to %c\n&, temp, target); printf(&move disk from %c to %c\n&, temp, target); printf(&move disk from %c to %c\n&, temp, target); hanoi(disks/3-1, source, target, temp); printf(&move disk from %c to %c\n&, target, source); printf(&move disk from %c to %c\n&, target, source); hanoi(disks/3-1, temp, source, target); printf(&move disk from %c to %c\n&, source, temp); for (i = disks / 3 - 1; i & 0; i--) { if (i&1) { hanoi(i-1, target, source, temp); } printf(&move disk from %c to %c\n&,target, source); printf(&move disk from %c to %c\n&,target, source); if (i&1) { hanoi(i-1, temp, source, target); } printf(&move disk from %c to %c\n&, source, temp); } } } int main() { printf(&请输入盘数：&); scanf(&%d&, &n); hanoi3colors(n); return 0; }13.Algorithm Gossip: 背包问题（Knapsack Problem）说明假设有一个背包的负重最多可达8公斤，而希望在背包中装入负重范围内可得之总价物品，假设是水果好了，水果的编号、单价与重量如下所示： 0 4KG 李子 1 5KG 苹果 2 2KG 橘子 3 1KG 草莓 4 6KG 甜瓜 NT$4500 NT$5700 NT$2250 NT$1100 NT$6700解法 背包问题是关于最佳化的问题，要解最佳化问题可以使用「动态规划」 （ Dynamicprogramming） ，从空集合开始，每增加一个元素就先求出该阶段的最佳解，直到所有的元素加 入至集合中，最后得到的就是最佳解。 以背包问题为例，我们使用两个阵列value与item，value表示目前的最佳解所得之总价，item表 示最后一个放至背包的水果，假设有负重量 1～8的背包8个，并对每个背包求其最佳解。 逐步将水果放入背包中，并求该阶段的最佳解： 放入李子 1 2 3 4 背 包 负 重 valu ０ 450 ０ ０ e 0 item － － － ０ 放入苹果 背 包 负 重 valu e item 放入橘子 1 2 3 4 5 6 7 85678450 0 ０450 0 ０450 0 ０900 0 ００ －０ －０ －450 0 ０570 0 1570 0 1570 0 1900 0 ０背 包 负 重 valu e item 放入草莓 背 包 负 重 valu e item 放入甜瓜 背 包 负 重 valu e item12345678０ －225 0 2225 0 2450 0 ０570 0 1675 0 2795 0 2900 0 ０12345678110 0 3225 0 2335 0 3450 0 ０570 0 1680 0 3795 0 2905 0 312345678110 0 3225 0 2335 0 3450 0 ０570 0 1680 0 3795 0 2905 0 3由最后一个表格，可以得知在背包负重8公斤时，最多可以装入9050元的水果，而最后一个装入 的 水果是3号，也就是草莓，装入了草莓，背包只能再放入7公斤（8-1）的水果，所以必须看 背包负重7公斤时的最佳解，最后一个放入的是2号，也就 是橘子，现在背包剩下负重量5公斤 （7-2） ，所以看负重5公斤的最佳解，最后放入的是1号，也就是苹果，此时背包负重量剩下0公 斤（5-5） ，无法 再放入水果，所以求出最佳解为放入草莓、橘子与苹果，而总价为9050元。实作C #include &stdio.h& #include &stdlib.h& #define LIMIT 8 // 重量限制#define N 5 #define MIN 1 struct body { char name[20]; };// 物品种类 // 最小重量typede int main(void) { int item[LIMIT+1] = {0}; int value[LIMIT+1] = {0}; int newvalue, i, s, object a[] = {{&李子&, 4, 4500}, {&苹果&, 5, 5700}, {&橘子&, 2, 2250}, {&草莓&, 1, 1100}, {&甜瓜&, 6, 6700}}; for(i = 0; i & N; i++) { for(s = a[i]. s &= LIMIT; s++) { p = s - a[i]. newvalue = value[p] + a[i]. if(newvalue & value[s]) {// 找到阶段最佳解 value[s] = item[s] = } } } printf(&物品\t价格\n&); for(i = LIMIT; i &= MIN; i = i - a[item[i]].size) { printf(&%s\t%d\n&, a[item[i]].name, a[item[i]].price); } printf(&合计\t%d\n&, value[LIMIT]);return 0; } Java class Fruit { private S public Fruit(String name, int size, int price) { this.name = this.size = this.price = } public String getName() { } public int getPrice() { } public int getSize() { } } public class Knapsack { public static void main(String[] args) { final int MAX = 8; final int MIN = 1; int[] item = new int[MAX+1]; int[] value = new int[MAX+1]; Fruit fruits[] = { new Fruit(&李子&, 4, 4500), new Fruit(&苹果&, 5, 5700), new Fruit(&橘子&, 2, 2250), new Fruit(&草莓&, 1, 1100),new Fruit(&甜瓜&, 6, 6700)}; for(int i = 0; i & fruits. i++) { for(int s = fruits[i].getSize(); s &= MAX; s++) { int p = s - fruits[i].getSize(); int newvalue = value[p] + fruits[i].getPrice(); if(newvalue & value[s]) {// 找到阶段最佳解 value[s] = item[s] = } } } System.out.println(&物品\t价格&); for(int i = MAX; i &= MIN; i = i - fruits[item[i]].getSize()) { System.out.println(fruits[item[i]].getName()+ &\t& + fruits[item[i]].getPrice()); } System.out.println(&合计\t& + value[MAX]); } }14.Algorithm Gossip: 蒙地卡罗法求 PI说明蒙地卡罗为摩洛哥王国之首都，该国位于法国与义大利国境，以赌博闻名。蒙地卡罗的基本原理为以乱数配合面积公式来进行解题，这种以机率来解题的方式带有赌博的意味，虽然 在精确度上有所疑虑，但其解题的思考方向却是个值得学习的方式。解法蒙地卡罗的解法适用于与面积有关的题目，例如求PI值或椭圆面积，这边介绍如何求PI值；假设有一个圆半径为1，所以四分之一圆面积就为PI，而包括此四分之一圆的正方形面积就 为1，如下图所示：如果随意的在正方形中投射飞标（点）好了，则这些飞标（点）有些会落于四分之一圆内，假 设所投射的飞标（点）有n点，在圆内的飞标（点）有c点，则依比例来算，就会得到上图中最 后的公式。 至于如何判断所产生的点落于圆内，很简单，令乱数产生X与Y两个数值，如果X^2+Y^2等于1 就是落在圆内。 #include &stdio.h& #include &stdlib.h& #include &time.h& #define N 50000 int main(void) { int i, sum = 0; double x, srand(time(NULL));for(i = 1; i & N; i++) { x = (double) rand() / RAND_MAX; y = (double) rand() / RAND_MAX; if((x * x + y * y) & 1) sum++; } printf(&PI = %f\n&, (double) 4 * sum / N); return 0; }15.Algorithm Gossip: Eratosthenes筛选求质数说明除了自身之外，无法被其它整数整除的数称之为质数，要求质数很简单，但如何快速的求出质数则一直是程式设计人员与数学家努力的课题， 在这边介绍一个着名的 Eratosthenes求质 数方法。解法首先知道这个问题可以使用回圈来求解，将一个指定的数除以所有小于它的数，若可以整除就不是质数，然而如何减少回圈的检查次数？如何求出小于N的所有质数？ 首先假设要检查的数是N好了，则事实上只要检查至N的开根号就可以了，道理很简单，假设 A*B = N，如果A大于N的开根号，则事实上在小于A之前的检查就可以先检查到B这个数可以整 除N。 不过在程式中使用开根号会精确度的问题， 所以可以使用 i*i &= N进行检查， 且执行更快。 再来假设有一个筛子存放1～N，例如： 2 3 4 5 6 7 8 9 10 11 12 13 14 先将2的倍数筛去： 2 3 5 7 9 11 13 15 再将3的倍数筛去： 2 3 5 7 11 1315161718 1920 21 ........ N17 1921 ........ N1719........ N再来将5的倍数筛去，再来将7的质数筛去，再来将11的倍数筛去........，如此进行到最后留下的 数就都是质数，这就是Eratosthenes筛选方法（Eratosthenes Sieve Method） 。 检查的次数还可以再减少，事实上，只要检查6n+1与6n+5就可以了，也就是直接跳过2与3的倍 数，使得程式中的if的检查动作可以减少。实作C #include &stdio.h& #include &stdlib.h& #define N 1000 int main(void) { int i,int prime[N+1]; for(i = 2; i &= N; i++) prime[i] = 1; for(i = 2; i*i &= N; i++) { // 这边可以改进 if(prime[i] == 1) { for(j = 2*i; j &= N; j++) { if(j % i == 0) prime[j] = 0; } } } for(i = 2; i & N; i++) { if(prime[i] == 1) { printf(&%4d &, i); if(i % 16 == 0) printf(&\n&); } } printf(&\n&); return 0; }16.Algorithm Gossip: 超长整数运算（大数运算）说明基于记忆体的有效运用，程式语言中规定了各种不同的资料型态，也因此变数所可以表达的最大整数受到限制，例如456789这样的 整数就不可能储存在long变数中（例 如C/C++等） ，我们称这为long数，这边翻为超长整数（避免与资料型态的长整数翻译混淆） ，或 俗称大数运算。解法一个变数无法表示超长整数，则就使用多个变数，当然这使用阵列最为方便，假设程式语言的最大资料型态可以储存至65535的数好了，为了计算方便及符合使用十进位制的习惯，让 每一个阵列元素可以储存四个位数，也就是0到9999的数，例如：很多人问到如何计算像50!这样的问题，解法就是使用程式中的乘法函式，至于要算到多大，就 看需求了。 由于使用阵列来储存数值，关于数值在运算时的加减乘除等各种运算、位数的进位或借位就必 须自行定义，加、减、乘都是由低位数开始运算，而除法则是由高位数开始运算，这边直接提 供加减乘除运算的函式供作参考，以下的N为阵列长度。void add(int *a, int *b, int *c) { int i, carry = 0;for(i = N - 1; i &= 0; i--) { c[i] = a[i] + b[i] + if(c[i] & 10000) carry = 0; else { // 进位 c[i] = c[i] - 10000; carry = 1; } } } void sub(int *a, int *b, int *c) { int i, borrow = 0; for(i = N - 1; i &= 0; i--) { c[i] = a[i] - b[i] - if(c[i] &= 0) borrow = 0; else { // 借位 c[i] = c[i] + 10000; borrow = 1; } } } void mul(int *a, int b, int *c) { // b 为乘数 int i, tmp, carry = 0; for(i = N - 1; i &=0; i--) { tmp = a[i] * b + c[i] = tmp % 10000; carry = tmp / 10000; } } void div(int *a, int b, int *c) { // b 为除数 int i, tmp, remain = 0; for(i = 0; i & N; i++) { tmp = a[i] + c[i] = tmp / remain = (tmp % b) * 10000; } }17.Algorithm Gossip: 长 PI说明圆周率后的小数位数是无止境的，如何使用电脑来计算这无止境的小数是一些数学家与程式设计师所感兴趣的，在这边介绍一个公式配合 大数运算，可以计算指定位数的圆周率。解法首先介绍J.Marchin的圆周率公式：PI = [16/5 - 16 / (3*5 ) + 16 / (5*5 ) - 16 / (7*5 ) + ......] [4/239 - 4/(3*239 ) + 4/(5*239 ) - 4/(7*239 ) + ......]3 5 7 3 5 7可以将这个公式整理为： PI = [16/5 - 4/239] - [16/(5 ) - 4/(239 )]/3+ [16/(5 ) - 4/(239 )]/5 + ......3 3 5 5也就是说第n项，若为奇数则为正数，为偶数则为负数，而项数表示方式为： [16/52*n-1- 4/2392*n-1] / (2*n-1)2*n-1 2*n-1 2*n-1 2*n-1如果我们要计算圆周率至10的负L次方，由于[16/5 大，具有决定性，所以表示至少必须计算至第n项： [16/52*n-1- 4/239]中16/5比4/239来的] / (2*n-1) = 10-L将上面的等式取log并经过化简，我们可以求得： n = L / (2log5) = L / 1.39794 所以若要求精确度至小数后L位数，则只要求至公式的第n项，其中n等于： n = [L/1.39794] + 1 在上式中[]为高斯符号，也就是取至整数（不大于L/1.39794的整数） ；为了计简方便，可以在程 式中使用下面这个公式来计简第n项： [Wn-1/5 - Vn-1 / (239 )] / (2*n-1)2 2这个公式的演算法配合大数运算函式的演算法为： div(w, 25, w); div(v, 239, v); div(v, 239, v); sub(w, v, q); div(q, 2*k-1, q)至于大数运算的演算法，请参考之前的文章，必须注意的是在输出时，由于是输出阵列中的整 数值，如果阵列中整数位数不满四位，则必须补上0，在C语言中只要 使用格式指定字%04d， 使得不足位数部份自动补上0再输出，至于Java的部份，使用 NumberFormat来作格式化。 #include &stdio.h& #define L 1000 #define N L/4+1 // L 为位数，N是array长度 void add(int*, int*, int*); void sub(int*, int*, int*); void div(int*, int, int*); int main(void) { int s[N+3] = {0}; int w[N+3] = {0}; int v[N+3] = {0}; int q[N+3] = {0}; int n = (int)(L/1.39793 + 1); w[0] = 16*5; v[0] = 4*239; for(k = 1; k &= k++) { // 套用公式 div(w, 25, w); div(v, 239, v); div(v, 239, v); sub(w, v, q); div(q, 2*k-1, q); if(k%2) // 奇数项 add(s, q, s); else // 偶数项 sub(s, q, s); } printf(&%d.&, s[0]);for(k = 1; k & N; k++) printf(&%04d&, s[k]); printf(&\n&); return 0; } void add(int *a, int *b, int *c) { int i, carry = 0; for(i = N+1; i &= 0; i--) { c[i] = a[i] + b[i] + if(c[i] & 10000) carry = 0; else { // 进位 c[i] = c[i] - 10000; carry = 1; } } } void sub(int *a, int *b, int *c) { int i, borrow = 0; for(i = N+1; i &= 0; i--) { c[i] = a[i] - b[i] - if(c[i] &= 0) borrow = 0; else { // 借位 c[i] = c[i] + 10000; borrow = 1; } } } void div(int *a, int b, int *c) { // b 为除数 int i, tmp, remain = 0; for(i = 0; i &= N+1; i++) { tmp = a[i] + c[i] = tmp / remain = (tmp % b) * 10000; } }18.Algorithm Gossip: 最大公因数、最小公倍数、因式分解说明最大公因数使用辗转相除法来求，最小公倍数则由这个公式来求：GCD * LCM = 两数乘积解法最大公因数可以使用递回与非递回求解，因式分解基本上就是使用小于输入数的数值当作除数，去除以输入数值，如果可以整除就视为因数，要比较快的解法就是求出小于该数的所 有质数，并试试看是不是可以整除，求质数的问题是另一个课题，请参考 Eratosthenes 筛选求 质数。实作（最大公因数、最小公倍数）#include &stdio.h& #include &stdlib.h& int main(void) { int m, n, printf(&输入两数：&); scanf(&%d %d&, &m, &n); s = m * while(n != 0) { r = m % m = n = } printf(&GCD：%d\n&, m); printf(&LCM：%d\n&, s/m); return 0; }实作（因式分解）C（不用质数表） #include &stdio.h& #include &stdlib.h& int main(void) { int i, printf(&请输入整数：&); scanf(&%d&, &n); printf(&%d = &, n); for(i = 2; i * i &=) { if(n % i == 0) { printf(&%d * &, i); n /= } else i++; } printf(&%d\n&, n); return 0; } C（使用质数表） #include &stdio.h& #include &stdlib.h& #define N 1000 int prime(int*); // 求质数表 void factor(int*, int); // 求factor int main(void) { int ptable[N+1] = {0}; int count, i, count = prime(ptable);printf(&请输入一数：&); scanf(&%d&, &temp); factor(ptable, temp); printf(&\n&); return 0; } int prime(int* pNum) { int i, int prime[N+1]; for(i = 2; i &= N; i++) prime[i] = 1; for(i = 2; i*i &= N; i++) { if(prime[i] == 1) { for(j = 2*i; j &= N; j++) { if(j % i == 0) prime[j] = 0; } } } for(i = 2, j = 0; i & N; i++) { if(prime[i] == 1) pNum[j++] = } } void factor(int* table, int num) { for(i = 0; table[i] * table[i] &=) { if(num % table[i] == 0) { printf(&%d * &, table[i]); num /= table[i]; } else i++; } printf(&%d\n&, num); }19.Algorithm Gossip: 完美数说明如果有一数n， 其真因数 （Proper factor） 的总和等于n， 则称之为完美数 （Perfect Number） ，例如以下几个数都是完美数： 6 = 1 + 2 + 3 28 = 1 + 2 + 4 + 7 + 14 496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 程式基本上不难，第一眼看到时会想到使用回圈求出所有真因数，再进一步求因数和，不过若n 值很大， 则此法会花费许多时间在回圈测试上， 十分没有效率， 例如求小于10000的所有完美数。解法如何求小于10000的所有完美数？并将程式写的有效率？基本上有三个步骤：求出一定数目的质数表 利用质数表求指定数的因式分解 利用因式分解求所有真因数和，并检查是否为完美数步骤一 与 步骤二 在之前讨论过了，问题在步骤三，如何求真因数和？方法很简单，要先知道 将所有真因数和加上该数本身，会等于该数的两倍，例如： 2 * 28 = 1 + 2 + 4 + 7 + 14 + 28 等式后面可以化为： 2 * 28 = (2 + 2 + 2 ) * (7 + 7 ) 所以只要求出因式分解，就可以利用回圈求得等式后面的值，将该值除以2就是真因数和了；等 式后面第一眼看时可能想到使用等比级数公式来解，不过会使用到次方运算，可以在回圈走访 因式分解阵列时，同时计算出等式后面的值，这在下面的实作中可以看到。0 1 2 0 1#include &stdio.h& #include &stdlib.h& #define N 1000 #define P 10000 int prime(int*); // 求质数表 int factor(int*, int, int*); // 求factor int fsum(int*, int); // sum ot proper factor int main(void) {int ptable[N+1] = {0}; // 储存质数表 int fact[N+1] = {0}; // 储存因式分解结果 int count1, count2, count1 = prime(ptable); for(i = 0; i &= P; i++) { count2 = factor(ptable, i, fact); if(i == fsum(fact, count2)) printf(&Perfect Number: %d\n&, i); } printf(&\n&); return 0; } int prime(int* pNum) { int i, int prime[N+1]; for(i = 2; i &= N; i++) prime[i] = 1; for(i = 2; i*i &= N; i++) { if(prime[i] == 1) { for(j = 2*i; j &= N; j++) { if(j % i == 0) prime[j] = 0; } } } for(i = 2, j = 0; i & N; i++) { if(prime[i] == 1) pNum[j++] = } }int factor(int* table, int num, int* frecord) { int i, for(i = 0, k = 0; table[i] * table[i] &=) { if(num % table[i] == 0) { frecord[k] = table[i]; k++; num /= table[i]; } else i++; } frecord[k] = return k+1; } int fsum(int* farr, int c) { int i, r, s, i = 0; r = 1; s = 1; q = 1; while(i & c) { do { r *= farr[i]; q += i++; } while(i & c-1 && farr[i-1] == farr[i]); s *= r = 1; q = 1; } return s / 2; }20.Algorithm Gossip: 阿姆斯壮数说明在三位的整数中，例如153可以满足1 + 5 + 3 = 153，这样的数称之为Armstrong数，试写出一 程式找出所有的三位数Armstrong数。3 3 3解法Armstrong数的寻找，其实就是在问如何将一个数字分解为个位数、十位数、百位数......，这只 要使用除法与余数运算就可以了，例如输入 input为abc，则： a = input / 100 b = (input%100) / 10 c = input % 10#include &stdio.h& #include &time.h& #include &math.h& int main(void) { int a, b, printf(&寻找Armstrong数：\n&); for(input = 100; input &= 999; input++) { a = input / 100; b = (input % 100) / 10; c = input % 10; if(a*a*a + b*b*b + c*c*c == input) printf(&%d &, input); } printf(&\n&); return 0; }21.Algorithm Gossip: 最大访客数说明现将举行一个餐会，让访客事先填写到达时间与离开时间，为了掌握座位的数目，必须先估计 不同时间的最大访客数。解法这个题目看似有些复杂，其实相当简单，单就计算访客数这个目的，同时考虑同一访客的来访 时间与离开时间，反而会使程式变得复杂；只要将来访时间与离开时间分开处理就可以了，假 设访客 i 的来访时间为x[i]，而离开时间为y[i]。 在资料输入完毕之后，将x[i]与y[i]分别进行排序（由小到大） ，道理很简单，只要先计算某时之 前总共来访了多少访客，然后再减去某时之前的离开访客，就可以轻易的解出这个问题。#include &stdio.h& #include &stdlib.h& #define MAX 100 #define SWAP(x,y) { t = x = y =} int partition(int[], int, int); void quicksort(int[], int, int); // 快速排序法 int maxguest(int[], int[], int, int); int main(void) { int x[MAX] = {0}; int y[MAX] = {0}; int time = 0; int count = 0; printf(&\n输入来访与离开125;时间(0~24)：&); printf(&\n范例：10 15&); printf(&\n输入-1 -1结束&); while(count & MAX) { printf(&\n&&&); scanf(&%d %d&, &x[count], &y[count]); if(x[count] & 0)count++; } if(count &= MAX) { printf(&\n超出最大访客数(%d)&, MAX); count--; } // 预先排序 quicksort(x, 0, count); quicksort(y, 0, count); while(time & 25) { printf(&\n%d 时的最大访客数：%d&, time, maxguest(x, y, count, time)); time++; } printf(&\n&); return 0; } int maxguest(int x[], int y[], int count, int time) { int i, num = 0; for(i = 0; i &= i++) { if(time & x[i]) num++; if(time & y[i]) num--; } } int partition(int number[], int left, int right) { int i, j, s = number[right]; i = left - 1;for(j = j & j++) { if(number[j] &= s) { i++; SWAP(number[i], number[j]); } } SWAP(number[i+1], number[right]); return i+1; } void quicksort(int number[], int left, int right) { if(left & right) { q = partition(number, left, right); quicksort(number, left, q-1); quicksort(number, q+1, right); } }22.Algorithm Gossip: 中序式转后序式（前序式）说明平常所使用的运算式，主要是将运算元放在运算子的两旁，例如a+b/d这样的式子，这称之为中序（Infix）表示式，对于人类来说，这样的式子很容易理 解，但由于电脑执行指令时是 有顺序的，遇到中序表示式时，无法直接进行运算，而必须进一步判断运算的先后顺序，所以 必须将中序表示式转换为另一种表示方 法。 可以将中序表示式转换为后序 （Postfix） 表示式， 后序表示式又称之为逆向波兰表示式 （Reverse polish notation） ，它是由波兰的数学家卢卡谢维奇提出，例如(a+b)*(c+d)这个式子，表示为后序 表示式时是ab+cd+*。解法用手算的方式来计算后序式相当的简单， 将运算子两旁的运算元依先后顺序全括号起来，然后将所有的右括号取代为左边最接近的运算子（从最内层括号开始） ，最后去掉所有的左括号 就可以完成后序表示式，例如： a+b*d+c/d =& ((a+(b*d))+(c/d)) -& bd*+cd/+ 如果要用程式来进行中序转后序，则必须使用堆叠，演算法很简单，直接叙述的话就是使用回 圈，取出中序式的字元，遇运算元直接输出，堆叠运算子与左括号， ISP&ICP的话直接输出堆 叠中的运算子，遇右括号输出堆叠中的运算子至左括号。 OUTPUT 例 如 (a+b)*(c+d) STACK 这个式子， 依演算 法的输出过程如 下： OP ( ( a ( a + (+ a b (+ ab ) ab+ * * ab+ ( *( ab+ c *( ab+c + *(+ ab+c d *(+ ab+cd ) * ab+cd+ ab+cd+* 如果要将中序式转为前序式，则在读取中序式时是由后往前读取，而左右括号的处理方式相反， 其余不变，但输出之前必须先置入堆叠，待转换完成后再将堆叠中的 值由上往下读出，如此就 是前序表示式。实作C #include &stdio.h& #include &stdlib.h& int postfix(char*); // 中序转后序 int priority(char); // 决定运算子优先顺序 int main(void) { char input[80]; printf(&输入中序运算式：&); scanf(&%s&, input); postfix(input); return 0; } int postfix(char* infix) { int i = 0, top = 0; char stack[80] = {'\0'}; while(1) { op = infix[i]; switch(op) { case '\0': while(top & 0) { printf(&%c&, stack[top]); top--; } printf(&\n&); return 0; // 运算子堆叠 case '(': if(top & (sizeof(stack) / sizeof(char))) { top++;stack[top] = } case '+': case '-': case '*': case '/': while(priority(stack[top]) &= priority(op)) { printf(&%c&, stack[top]); top--; } // 存入堆叠 if(top & (sizeof(stack) / sizeof(char))) { top++; stack[top] = } // 遇 ) 输出至 ( case ')': while(stack[top] != '(') { printf(&%c&, stack[top]); top--; } top--; // 不输出( // 运算元直接输出 default: printf(&%c&, op); } i++; } } int priority(char op) { switch(op) { case '+': case '-': p = 1; case '*': case '/': p = 2;default: p = 0; } }23.Algorithm Gossip: 后序式的运算说明 将中序式转换为后序式的好处是，不用处理运算子先后顺序问题，只要依序由运算式由 前往后读取即可。解法运算时由后序式的前方开 始读取，遇到运算元先存入 堆叠，如果遇到运算子，则 由堆叠中取出两个运算元进 行对应的运算，然后将结果 存回堆叠，如果运算式读取 完 毕， 那么堆叠顶的值就是 答案了，例如我们计算 12+34+*这个运算式 （也就是 (1+2)*(3+4)） ： 读取 1 2 + 3 4 + * 堆叠1 12 3 // 1+2 后存回 33 334 3 7 // 3+4 后存回 21 // 3 * 7 后存回#include &stdio.h& #include &stdlib.h& void evalPf(char*); double cal(double, char, double); int main(void) { char input[80]; printf(&输入后序式：&); scanf(&%s&, input); evalPf(input); return 0; } void evalPf(char* postfix) {double stack[80] = {0.0}; char temp[2]; int top = 0, i = 0; temp[1] = '\0'; while(1) { token = postfix[i]; switch(token) { case '\0': printf(&ans = %f\n&, stack[top]); case '+': case '-': case '*': case '/': stack[top-1] = cal(stack[top], token, stack[top-1]); top--; default: if(top & sizeof(stack) / sizeof(float)) { temp[0] = postfix[i]; top++; stack[top] = atof(temp); } } i++; } } double cal(double p1, char op, double p2) { switch(op) { case '+': return p1 + p2; case '-': return p1 - p2; case '*': return p1 * p2; case '/': return p1 / p2; } }24.Algorithm Gossip: 洗扑克牌（乱数排列）说明洗扑克牌的原理其实与乱数排列是相同的，都是将一组数字（例如 1～N）打乱重新排列，只 不过洗扑克牌多了一个花色判断的动作而已。解法初学者通常会直接想到，随机产生1～N的乱数并将之存入阵列中，后来产生的乱数存入阵列 前必须先检查阵列中是否已有重复的数字，如果有这个数就不存入，再重新产生下一个数，运 气不好的话，重复的次数就会很多，程式的执行速度就很慢了，这不是一个好方法。 以1～52的乱数排列为例好了，可以将阵列先依序由1到52填入，然后使用一个回圈走访阵列， 并随机产生1～52的乱数， 将产生的乱数当作索引取出阵列值， 并与目前阵列走访到的值相交换， 如此就不用担心乱数重复的问题了，阵列走访完毕后，所有的数字也就重新排列了。 至于如何判断花色？这只是除法的问题而已，取商数判断花色，取余数判断数字，您可以直接 看程式比较清楚。实作C #include &stdio.h& #include &stdlib.h& #include &time.h& #define N 52 int main(void) { int poker[N + 1]; int i, j, tmp, // 初始化阵列 for(i = 1; i &= N; i++) poker[i] = srand(time(0)); // 洗牌 for(i = 1; i &= N; i++) {j = rand() % 52 + 1; tmp = poker[i]; poker[i] = poker[j]; poker[j] = } for(i = 1; i &= N; i++) { // 判断花色 switch((poker[i]-1) / 13) { case 0: printf(&桃&); case 1: printf(&心&); case 2: printf(&砖&); case 3: printf(&梅&); } // 扑克牌数字 remain = poker[i] % 13; switch(remain) { case 0: printf(&K &); case 12: printf(&Q &); case 11: printf(&J &); default: printf(&%d &, remain); } if(i % 13 == 0) printf(&\n&); } return 0; }25.Algorithm Gossip: Craps赌博游戏说明一个简单的赌博游戏，游戏规则如下：玩家掷两个骰子，点数为1到6，如果第一次点数和为7或11，则玩家胜，如果点数和为2、3或12，则玩家输，如果和 为其它点数，则记录第一 次的点数和，然后继续掷骰，直至点数和等于第一次掷出的点数和，则玩家胜，如果在这之前 掷出了点数和为7，则玩家输。解法规则看来有些复杂，但是其实只要使用switch配合if条件判断来撰写即可，小心不要弄错胜负顺序即可。 #include &stdio.h& #include &stdlib.h& #include &time.h& #define WON 0 #define LOST 1 #define CONTINUE 2 int rollDice() { return (rand() % 6) + (rand() % 6) + 2; } int main(void) { int firstRoll = 1; int gameStatus = CONTINUE; int die1, die2, sumOfD int firstPoint = 0; srand(time(0)); printf(&Craps赌博游戏，按Enter键开始游戏****&); while(1) { getchar(); if(firstRoll) { sumOfDice = rollDice(); printf(&\n玩家掷出点数和：%d\n&, sumOfDice); switch(sumOfDice) {case 7: case 11: gameStatus = WON; case 2: case 3: case 12: gameStatus = LOST; default: firstRoll = 0; gameStatus = CONTINUE; firstPoint = sumOfD } } else { sumOfDice = rollDice(); printf(&\n玩家掷出点数和：%d\n&, sumOfDice); if(sumOfDice == firstPoint) gameStatus = WON; else if(sumOfDice == 7) gameStatus = LOST; } if(gameStatus == CONTINUE) puts(&未分胜负，再掷一次****\n&); else { if(gameStatus == WON) puts(&玩家胜&); else puts(&玩家输&); printf(&再玩一次？&); scanf(&%c&, &c); if(c == 'n') { puts(&游戏结束&); } firstRoll = 1; } } return 0; }26.Algorithm Gossip: 约瑟夫问题（Josephus Problem）说明据说着名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹 太人与Josephus及他的朋友躲到一个洞中， 39个犹太人决定宁愿死也不要被敌人到， 于是决定了 一个自杀方式，41个人排成一个圆圈，由第1个人 开始报数，每报数到第3人该人就必须自杀， 然后再由下一个重新报数，直到所有人都自杀身亡为止。 然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排 在第16个与第31个位置，于是逃过了这场死亡游戏。解法约瑟夫问题可用代数分析来求解，将这个问题扩大好了，假设现在您与m个朋友不幸参与了这个游戏，您要如何保护您与您的朋友？只要画两个圆圈就可以让自己与朋友免于死亡游 戏，这两个圆圈内圈是排列顺序，而外圈是自杀顺序，如下图所示：使用程式来求解的话，只要将阵列当作环状来处理就可以了，在阵列中由计数1开始，每找到三 个无资料区就填入一个计数，直而计数达41为止，然后将阵列由索引1开始列出，就可以得知每 个位置的自杀顺序，这就是约瑟夫排列，41个人而报数3的约琴夫排列如下所示： 14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23 由上可知，最后一个自杀的是在第31个位置，而倒数第二个自杀的要排在第16个位置，之前的 人都死光了，所以他们也就不知道约琴夫与他的朋友并没有遵守游戏规则了。#include &stdio.h& #include &stdlib.h& #define N 41 #define M 3 int main(void) { int man[N] = {0}; int count = 1; int i = 0, pos = -1; int alive = 0; while(count &= N) { do { pos = (pos+1) % N; // 环状处理 if(man[pos] == 0) i++; if(i == M) { // 报数为3了 i = 0; } } while(1); man[pos] = count++; } printf(&\n约琴夫排列：&); for(i = 0; i & N; i++) printf(&%d &, man[i]); printf(&\n\n您想要救多少人？&); scanf(&%d&, &alive); printf(&\nL表示这%d人要放的位置：\n&, alive); for(i = 0; i & N; i++) { if(man[i] & alive) printf(&D&); else printf(&L&); if((i+1) % 5 == 0) printf(& &); } printf(&\n&); return 0; }27.Algorithm Gossip: 排列组合说明将一组数字、字母或符号进行排列，以得到不同的组合顺序，例如1 2 3这三个数的排列组合有：1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1。解法可以使用递回将问题切割为较小的单元进行排列组合，例如1 2 3 4的排列可以分为1 [2 34]、2 [1 3 4]、3 [1 2 4]、4 [1 2 3]进行排列，这边利用旋转法，先将旋转间隔设为0，将最右边的 数字旋转至最左边，并逐步增加旋转的间隔，例如： 1 2 3 4 -& 旋转1 -& 继续将右边2 3 4进行递回处理 2 1 3 4 -& 旋转1 2 变为 2 1-& 继续将右边1 3 4进行递回处理 3 1 2 4 -& 旋转1 2 3变为 3 1 2 -& 继续将右边1 2 4进行递回处理 4 1 2 3 -& 旋转1 2 3 4变为4 1 2 3 -& 继续将右边1 2 3进行递回处理#include &stdio.h& #include &stdlib.h& #define N 4 void perm(int*, int); int main(void) { int num[N+1], for(i = 1; i &= N; i++) num[i] = perm(num, 1); return 0; } void perm(int* num, int i) { int j, k, if(i & N) { for(j = j &= N; j++) { tmp = num[j]; // 旋转该区段最右边数字至最左边 for(k = k & k--) num[k] = num[k-1]; num[i] = perm(num, i+1); // 还原for(k = k & k++) num[k] = num[k+1]; num[j] = } } else { // 显示此次排列 for(j = 1; j &= N; j++) printf(&%d &, num[j]); printf(&\n&); } }28.Algorithm Gossip: 格雷码（Gray Code）说明Gray Code是一个数列集合，每个数使用二进位来表示，假设使用n位元来表示每个数好了，任 两个数之间只有一个位元值不同，例如以下为3位元的Gray Code： 000 001 011 010 110 111 101 100 由定义可以知道， Gray Code的顺序并不是唯一的， 例如将上面的数列反过来写， 也是一组Gray Code： 100 101 111 110 010 011 001 000 Gray Code是由贝尔实验室的Frank Gray在1940年代提出的，用来在使用PCM（Pusle Code Modulation）方法传送讯号时避免出错，并于1953年三月十七日取得美国专利。解法由于Gray Code相邻两数之间只改变一个位元，所以可观 察Gray Code从1变0或从0变1时的 位置，假设有4位元的Gray Code如下： 11 11 00 10 01 1000 观察奇数项的变化时，我们发现无论它是第几个Gray Code，永远只改变最右边的位元，如果 是1就改为0，如果是0就改为1。 观察偶数项的变化时，我们发现所改变的位元，是由右边算来第一个1的左边位元。 以上两个变化规则是固定的，无论位元数为何；所以只要判断位元的位置是奇数还是偶数，就 可以决定要改变哪一个位元的值，为了程式撰写方便，将阵列索引 0当作最右边的值，而在列 印结果时，是由索引数字大的开始反向列印。 将2位元的Gray Code当作平面座标来看，可以构成一个四边形，您可以发现从任一顶点出发， 绕四边形周长绕一圈， 所经过的顶点座标就是一组Gray Code， 所以您可以得到四组Gray Code。 同样的将3位元的Gray Code当作平面座标来看的话，可以构成一个正立方体，如果您可以从任 一顶点出发，将所有的边长走过，并不重复经过顶点的话，所经过的顶点座标顺序之组合也就 是一组Gray Code。#include &stdio.h& #include &stdlib.h&#define MAXBIT 20 #define TRUE 1 #define CHANGE_BIT(x) x = ((x) == '0' ? '1' : '0') #define NEXT(x) x = (1 - (x)) int main(void) { char digit[MAXBIT]; int i, bits, printf(&输入位元数：&); scanf(&%d&, &bits); for(i = 0; i & i++) { digit[i] = '0'; printf(&0&); } printf(&\n&); odd = TRUE; while(1) { if(odd) CHANGE_BIT(digit[0]); else { // 计算第一个1的位置 for(i = 0; i & bits && digit[i] == '0'; i++) ; if(i == bits - 1) // 最后一个Gray C CHANGE_BIT(digit[i+1]); } for(i = bits - 1; i &= 0; i--) printf(&%c&, digit[i]); printf(&\n&); NEXT(odd); } return 0; }29.Algorithm Gossip: 产生可能的集合说明给定一组数字或符号，产生所有可能的集合（包括空集合） ，例如给定1 2 3，则可能的集合为： {}、{1}、{1,2}、{1,2,3}、{1,3}、{2}、{2,3}、{3}。解法如果不考虑字典顺序，则有个简单的方法可以产生所有的集合，思考二进位数字加法，并注意 1出现的位置，如果每个位置都对应一个数字，则由1所对应的数字所产生的就是一个集合，例 如： 000 {} 001 {3} 010 {2} 011 {2,3} 100 {1} 101 {1,3} 110 {1,2} 111 {1,2,3} 了解这个方法之后， 剩下的就是如何产生二进位数？有许多方法可以使用， 您可以使用unsigned 型别加上&位元运算来产生，这边则是使用阵列搜 寻，首先阵列内容全为0，找第一个1，在还 没找到之前将走访过的内容变为0，而第一个找到的0则变为 1，如此重复直到所有的阵列元素 都变为1为止，例如： 000 =& 100 =& 010 =& 110 =& 001 =& 101 =& 011 =& 111 如果要产生字典顺序，例如若有4个元素，则： {} =& {1} =& {1,2} =& {1,2,3} =& {1,2,3,4} =& {1,2,4} =& {1,3} =& {1,3,4} =& {1,4} =& {2} =& {2,3} =& {2,3,4} =& {2,4} =& {3} =& {3,4} =& {4} 简单的说，如果有n个元素要产生可能的集合，当依序产生集合时，如果最后一个元素是n，而 倒数第二个元素是m的话，例如： {a b c d e n}则下一个集合就是{a b c d e+1}，再依序加入后续的元素。 例如有四个元素，而当产生{1 2 3 4}集合时，则下一个集合就是{1 2 3+1}，也就是{1 2 4}，由 于最后一个元素还是4，所以下一个集合就是{1 2+1}，也就是{1 3}，接下来再加入后续元素4， 也就是{1 3 4}，由于又遇到元素4，所以下一个集合是{1 3+1}，也就是{1 4}。实作C（无字典顺序） #include &stdio.h& #include &stdlib.h& #define MAXSIZE 20 int main(void) { char digit[MAXSIZE]; int i, printf(&输入集合个数：&); scanf(&%d&, &n); for(i = 0; i & i++) digit[i] = '0'; printf(&\n{}&); // 空集合 while(1) { // 找第一个0，并将找到前所经过的元素变为0 for(i = 0; i & n && digit[i] == '1'; digit[i] = '0', i++); if(i == n) // 找不到0 else // 将第一个找到的0变为1 digit[i] = '1'; // 找第一个1，并记录对应位置 for(i = 0; i & n && digit[i] == '0'; i++); printf(&\n{%d&, i+1);for(j = i + 1; j & j++) if(digit[j] == '1') printf(&,%d&, j + 1); printf(&}&); } printf(&\n&); return 0; } C（字典顺序） #include &stdio.h& #include &stdlib.h& #define MAXSIZE 20 int main(void) { int set[MAXSIZE]; int i, n, position = 0; printf(&输入集合个数：&); scanf(&%d&, &n); printf(&\n{}&); set[position] = 1; while(1) { printf(&\n{%d&, set[0]); // 印第一个数 for(i = 1; i &= i++) printf(&,%d&, set[i]); printf(&}&); if(set[position] & n) { // 递增集合个数 set[position+1] = set[position] + 1; position++; } else if(position != 0) { // 如果不是第一个位置 position--; // 倒退 set[position]++; // 下一个集合尾数 }else // 已倒退至第一个位置 } printf(&\n&); return 0; }30.Algorithm Gossip: m元素集合的n个元素子集说明假设有个集合拥有m个元素，任意的从集合中取出n个元素，则这n个元素所形成的可能子集有 那些？解法假设有5个元素的集点，取出3个元素的可能子集如下： {1 2 3}、{1 2 4 }、{1 2 5}、{1 3 4}、{1 3 5}、{1 4 5}、{2 3 4}、{2 3 5}、{2 4 5}、 {3 4 5} 这些子集已经使用字典顺序排列，如此才可以观察出一些规则： 如果最右一个元素小于m，则如同码表一样的不断加1 如果右边一位已至最大值，则加1的位置往左移 每次加1的位置往左移后，必须重新调整右边的元素为递减顺序所以关键点就在于哪一个位置必须进行加1的动作，到底是最右一个位置要加1？还是其它的位 置？ 在实际撰写程式时，可以使用一个变数 positon来记录加1的位置，position的初值设定为n-1， 因为我们要使用阵列，而最右边的索引值为最大 的n-1，在position位置的值若小于m就不断加 1，如果大于m了，position就减1，也就是往左移一个位置；由于位置左移后，右边的元素会 经 过调整，所以我们必须检查最右边的元素是否小于m，如果是，则position调整回n-1，如果不 是，则positon维持不变。实作C #include &stdio.h& #include &stdlib.h& #define MAX 20 int main(void) { int set[MAX]; int m, n,
printf(&输入集合个数 m：&); scanf(&%d&, &m); printf(&输入取出元素 n：&); scanf(&%d&, &n); for(i = 0; i & i++) set[i] = i + 1; // 显示第一个集合 for(i = 0; i & i++) printf(&%d &, set[i]); putchar('\n'); position = n - 1; while(1) { if(set[n-1] == m) position--; else position = n - 1; set[position]++; // 调整右边元素 for(i = position + 1; i & i++) set[i] = set[i-1] + 1; for(i = 0; i & i++) printf(&%d &, set[i]); putchar('\n'); if(set[0] &= m - n + 1) } return 0; }31.Algorithm Gossip: 数字拆解说明这个题目来自于 数字拆解，我将之改为C语言的版本，并加上说明。 题目是这样的： 3 = 2+1 = 1+1+1 所以3有三种拆法 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五种 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1 共七种 依此类推，请问一个指定数字NUM的拆解方法个数有多少个？解法我们以上例中最后一个数字5的拆解为例，假设f( n )为数字n的可拆解方式个数，而f(x, y)为使 用y以下的数字来拆解x的方法个数，则观察： 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1 使用函式来表示的话： f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,4) + f(0,5) 其中f(1, 4) = f(1, 3) + f(1, 2) + f(1, 1)， 但是使用大于1的数字来拆解1没有意义， 所以f(1, 4) = f(1, 1)，而同样的，f(0, 5)会等于f(0, 0)，所以： f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,1) + f(0,0) 依照以上的说明，使用动态程式规画（Dynamic programming）来进行求解，其中f(4,1)其实就 是f(5-1, min(5-1,1))，f(x, y)就等于f(n-y, min(n-x, y))，其中n为要拆解的数字，而min()表示取两 者中较小的数。 使用一个二维阵列表格table[x][y]来表示f(x, y)，刚开始时，将每列的索引0与索引1元素值设定 为1，因为任何数以0以下的数拆解必只有1种，而任何数以1以下的数拆解也必只有1种： for(i = 0; i & NUM +1; i++){ table[i][0] = 1; // 任何数以0以下的数拆解必只有1种 table[i][1] = 1; // 任何数以1以下的数拆解必只有1种 }接下来就开始一个一个进行拆解了，如果数字为NUM，则我们的阵列维度大小必须为NUM x (NUM/2+1)，以数字10为例，其维度为10 x 6我们的表格将会如下所示： 1 1 0 0 0 0 1 1 0 0 0 0 1 1 2 0 0 0 1 1 2 3 0 0 1 1 3 4 5 0 1 1 3 5 6 7 1 1 4 7 9 0 1 1 4 8 0 0 1 1 5 0 0 0 1 1 0 0 0 0实作C #include &stdio.h& #include &stdlib.h& #define NUM 10 // #define DEBUG 0 要拆解的数字int main(void) { int table[NUM][NUM/2+1] = {0}; // 动态规画表格 int count = 0; int result = 0; int i, j, printf(&数字拆解\n&); printf(&3 = 2+1 = 1+1+1 所以3有三种拆法\n&); printf(&4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1&); printf(&共五种\n&); printf(&5 = 4 + 1 = 3 + 2 = 3 + 1 + 1&); printf(& = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1&); printf(&共七种\n&); printf(&依此类推，求 %d 有几种拆法？&, NUM); // 初始化 for(i = 0; i & NUM; i++){ table[i][0] = 1; // 任何数以0以下的数拆解必只有1种table[i][1] = 1; // 任何数以1以下的数拆解必只有1种 } // 动态规划 for(i = 2; i &= NUM; i++){ for(j = 2; j &= j++){ if(i + j & NUM) // 大于 NUM count = 0; for(k = 1 ; k &= k++){ count += table[i-k][(i-k &= k) ? k : i-k]; } table[i][j] = } } // 计算并显示结果 for(k = 1 ; k &= NUM; k++) result += table[NUM-k][(NUM-k &= k) ? k : NUM-k]; printf(&\n\nresult: %d\n&, result); if(DEBUG) { printf(&\n除错资讯\n&); for(i = 0; i & NUM; i++) { for(j = 0; j & NUM/2+1; j++) printf(&%2d&, table[i][j]); printf(&\n&); } } return 0; }32.Algorithm Gossip: 得分排行说明假设有一教师依学生座号输入考试分数， 现希望在输入完毕后自动显示学生分数的排行，当然学生的分数可能相同。解法这个问题基本上要解不难，只要使用额外的一个排行阵列走访分数阵列就可以了，直接使用下面的程式片段作说明： for(i = 0; i & i++) { juni[i] = 1; for(j = 0; j & j++) { if(score[j] & score[i]) juni[i]++; } } printf(&得分\t排行\n&); for(i = 0; i & i++) printf(&%d\t%d\n&, score[i], juni[i]); 上面这个方法虽然简单，但是反覆计算的次数是n^2，如果n值变大，那么运算的时间就会拖长； 改变juni阵列的长度为n+2，并将初始值设定为0，如下所示：接下来走访分数阵列，并在分数所对应的排行阵列索引元素上加1，如下所示：将排行阵列最右边的元素设定为1， 然后依序将右边的元素值加至左边一个元素， 最后排行阵列 中的「分数+1」 」就是得该分数的排行，如下所示：这样的方式看起来复杂， 其实不过在计算某分数之前排行的人数， 假设89分之前的排行人数为x人，则89分自然就是x+1了，这也是为什么排行阵列最右边要设定为1的原因；如果89分有y人， 则88分自然就是x+y+1，整个阵列右边元素向左加的原因正是如此。 如果分数有负分的情况，由于C/C++或Java等程式语言无法处理负的索引，所以必须加上一个 偏移值，将所有的分数先往右偏移一个范围即可，最后显示的时候记得减回偏移值就可以了。#include &stdio.h& #include &stdlib.h& #define MAX 100 #define MIN 0 int main(void) { int score[MAX+1] = {0}; int juni[MAX+2] = {0}; int count = 0, do { printf(&输入分数，-1结束：&); scanf(&%d&, &score[count++]); } while(score[count-1] != -1); count--; for(i = 0; i & i++) juni[score[i]]++; juni[MAX+1] = 1; for(i = MAX; i &= MIN; i--) juni[i] = juni[i] + juni[i+1]; printf(&得分\t排行\n&); for(i = 0; i & i++) printf(&%d\t%d\n&, score[i], juni[score[i]+1]); return 0; }33.Algorithm Gossip: 选择、插入、气泡排序说明选择排序（Selection sort） 、插入排序（Insertion sort）与气泡排序（Bubble sort）这三个排序方式是初学排序所必须知道的三个基本排序方式，它们由于速度不快而不实用（平均与最 快的时间复杂度都是O(n )） ，然而它们排序的方式确是值得观察与探讨的。2解法选择排序 将要排序的对象分作两部份，一个是已排序的，一个是未排序的，从后端未排序部份选择一个 最小值，并放入前端已排序部份的最后一个，例如： 排序前：70 80 31 37 10 1 48 60 33 80 [1] 80 31 37 10 70 48 60 33 80 选出最小值1 [1 10] 31 37 80 70 48 60 33 80 选出最小值10 [1 10 31] 37 80 70 48 60 33 80 选出最小值31 [1 10 31 33] 80 70 48 60 37 80 ...... [1 10 31 33 37] 70 48 60 80 80 ...... [1 10 31 33 37 48] 70 60 80 80 ...... [1 10 31 33 37 48 60] 70 80 80 ...... [1 10 31 33 37 48 60 70] 80 80 ...... [1 10 31 33 37 48 60 70 80] 80 ......插入排序 像是玩朴克一样，我们将牌分作两堆，每次从后面一堆的牌抽出最前端的牌，然后插入前面一 堆牌的适当位置，例如： 排序前：92 77 67 8 6 84 55 85 43 67 [77 92] 67 8 6 84 55 85 43 67 将77插入92前 [67 77 92] 8 6 84 55 85 43 67 将67插入77前 [8 67 77 92] 6 84 55 85 43 67 将8插入67前 [6 8 67 77 92] 84 55 85 43 67 将6插入8前 [6 8 67 77 84 92] 55 85 43 67 将84插入92前 [6 8 55 67 77 84 92] 85 43 67 将55插入67前 [6 8 55 67 77 84 85 92] 43 67 ...... [6 8 43 55 67 77 84 85 92] 67 ...... [6 8 43 55 67 67 77 84 85 92] ......气泡排序法 顾名思义，就是排序时，最大的元素会如同气泡一样移至右端，其利用比较相邻元素的方法， 将大的元素交换至右端，所以大的元素会不断的往右移动，直到适当的位置为止。 基本的气泡排序法可以利用旗标的方式稍微减少一些比较的时间，当寻访完阵列后都没有发生 任何的交换动作，表示排序已经完成，而无需再进行之后的回圈比较与交换动作，例如： 排序前：95 27 90 49 80 58 6 9 18 50 27 90 49 80 58 6 9 18 50 [95] 95浮出 27 49 80 58 6 9 18 50 [90 95] 90浮出 27 49 58 6 9 18 50 [80 90 95] 80浮出 27 49 6 9 18 50 [58 80 90 95] ...... 27 6 9 18 49 [50 58 80 90 95] ...... 6 9 18 27 [49 50 58 80 90 95] ...... 6 9 18 [27 49 50 58 80 90 95] 由于接下来不会再发生交换动作，排序提早结束在上面的例子当中，还加入了一个观念，就是当进行至i与i+1时没有交换的动作，表示接下来的 i+2至n已经排序完毕，这也增进了气泡排序的效率。#include &stdio.h& #include &stdlib.h& #include &time.h& #define MAX 10 #define SWAP(x,y) { t = x = y =} void selsort(int[]); // 选择排序 void insort(int[]); // 插入排序 void bubsort(int[]); // 气泡排序 int main(void) { int number[MAX] = {0}; srand(time(NULL)); printf(&排序前：&); for(i = 0; i & MAX; i++) {number[i] = rand() % 100; printf(&%d &, number[i]); } printf(&\n请选择排序方式：\n&); printf(&(1)选择排序\n(2)插入排序\n(3)气泡排序\n:&); scanf(&%d&, &i); switch(i) { case 1: selsort(number); case 2: insort(number); case 3: bubsort(number); default: printf(&选项错误(1..3)\n&); } return 0; } void selsort(int number[]) { int i, j, k, for(i = 0; i & MAX-1; i++) { m = for(j = i+1; j & MAX; j++) if(number[j] & number[m]) m = if( i != m) SWAP(number[i], number[m]) printf(&第 %d 次排序：&, i+1); for(k = 0; k & MAX; k++) printf(&%d &, number[k]); printf(&\n&); } }void insort(int number[]) { int i, j, k, for(j = 1; j & MAX; j++) { tmp = number[j]; i = j - 1; while(tmp & number[i]) { number[i+1] = number[i]; i--; if(i == -1) } number[i+1] = printf(&第 %d 次排序：&, j); for(k = 0; k & MAX; k++) printf(&%d &, number[k]); printf(&\n&); } } void bubsort(int number[]) { int i, j, k, flag = 1; for(i = 0; i & MAX-1 && flag == 1; i++) { flag = 0; for(j = 0; j & MAX-i-1; j++) { if(number[j+1] & number[j]) { SWAP(number[j+1], number[j]); flag = 1; } } printf(&第 %d 次排序：&, i+1); for(k = 0; k & MAX; k++) printf(&%d &, number[k]); printf(&\n&); } }34.Algorithm Gossip: Shell 排序法 - 改良的插入排序说明插入排序法由未排序的后半部前端取出一个值，插入已排序前半部的适当位置，概念简单但速 度不快。 排序要加快的基本原则之一，是让后一次的排序进行时，尽量利用前一次排序后的结果，以加 快排序的速度，Shell排序法即是基于此一概念来改良插入排序法。解法Shell排序法最初是D.L Shell于1959所提出，假设要排序的元素有n个，则每次进行插入排序时 并不是所有的元素同时进行时，而是取一段间隔。 Shell首先将间隔设定为n/2，然后跳跃进行插入排序，再来将间隔n/4，跳跃进行排序动作，再来 间隔设定为n/8、n/16，直到间隔为1之后的最 后一次排序终止，由于上一次的排序动作都会将 固定间隔内的元素排序好，所以当间隔越来越小时，某些元素位于正确位置的机率越高，因此 最后几次的排序动作将 可以大幅减低。 举个例子来说，假设有一未排序的数字如右：89 12 65 97 61 81 27 2 61 98 数字的总数共有10个，所以第一次我们将间隔设定为10 / 2 = 5，此时我们对间隔为5的数字进行 排序，如下所示：画线连结的部份表示 要一起进行排序的部份，再来将间隔设定为5 / 2的商，也就是2，则第二 次的插入排序对象如下所示：再来间隔设定为2 / 2 = 1，此时就是单纯的插入排序了，由于大部份的元素都已大致排序过了， 所以最后一次的插入排序几乎没作什么排序动作了：将间隔设定为n / 2是D.L Shell最初所提出，在教科书中使用这个间隔比较好说明，然而Shell排 序法的关键在于间隔的选定， 例如Sedgewick证明选用以下的间隔可以加 快Shell排序法的速度：其中4*(2 ) + 3*(2 ) + 1不可超过元素总数n值，使用上式找出j后代入4*(2 ) + 3*(2 ) + 1求得第一 j 个间隔，然后将2 除以2代入求得第二个间隔，再来依此类推。 后来还有人证明有其它的间隔选定法可以将Shell排序法的速度再加快；另外Shell排序法的概念 也可以用来改良气泡排序法。j 2jj 2j实作C #include &stdio.h& #include &stdlib.h& #include &time.h& #define MAX 10 #define SWAP(x,y) { t = x = y =} void shellsort(int[]); int main(void) { int number[MAX] = {0}; srand(time(NULL)); printf(&排序前：&); for(i = 0; i & MAX; i++) { number[i] = rand() % 100; printf(&%d &, number[i]); }shellsort(number); return 0; } void shellsort(int number[]) { int i, j, k, gap, gap = MAX / 2; while(gap & 0) { for(k = 0; k & k++) { for(i = k+ i & MAX; i+=gap) { for(j = i - j &= j-=gap) { if(number[j] & number[j+gap]) { SWAP(number[j], number[j+gap]); } } } } printf(&\ngap = %d：&, gap); for(i = 0; i & MAX; i++) printf(&%d &, number[i]); printf(&\n&); gap /= 2; } }35.Algorithm Gossip: Shaker 排序法 - 改良的气泡排 序说明请看看之前介绍过的气泡排序法： for(i = 0; i & MAX-1 && flag == 1; i++) { flag = 0; for(j = 0; j & MAX-i-1; j++) { if(number[j+1] & number[j]) { SWAP(number[j+1], number[j]); flag = 1; } } }事实上这个气泡排序法已经不是单纯的气泡排序了，它使用了旗标与右端左移两个方法来改进 排序的效能，而Shaker排序法使用到后面这个观念进一步改良气泡排序法。解法在上面的气泡排序法中，交换的动作并不会一直进行至阵列的最后一个，而是会进行至 MAX-i-1，所以排序的过程中，阵列右方排序好的元素会一直增加，使得左边排序的次数逐渐减 少，如我们的例子所示： 排序前：95 27 90 49 80 58 6 9 18 50 27 90 49 80 58 6 9 18 50 [95] 95浮出 27 49 80 58 6 9 18 50 [90 95] 90浮出 27 49 58 6 9 18 50 [80 90 95] 80浮出 27 49 6 9 18 50 [58 80 90 95] ...... 27 6 9 18 49 [50 58 80 90 95] ...... 6 9 18 27 [49 50 58 80 90 95] ...... 6 9 18 [27 49 50 58 80 90 95]方括号括住的部份表示已排序完毕，Shaker排序使用了这个概念，如果让左边的元素也具有这 样的性质，让左右两边的元素都能先排序完成，如此未排序的元素会集中在中间，由于左右两边同时排序，中间未排序的部份将会很快的减少。 方法就在于气泡排序的双