OddArray

Algorithm Gossip: 奇数魔方阵

说明

将1到n(为奇数)的数字排列在nxn的方阵上，且各行、各列与各对角线的和必须相同，如下所示：

解法

填魔术方阵的方法以奇数最为简单，第一个数字放在第一行第一列的正中央，然后向右(左)上填，如果右(左)上已有数字，则向下填，如下图所示： 一般程式语言的阵列索引多由0开始，为了计算方便，我们利用索引1到n的部份，而在计算是向右(左)上或向下时，我们可以将索引值除以n值，如果得到余数为1就向下，否则就往右(左)上，原理很简单，看看是不是已经在同一列上绕一圈就对了。

实作

• C /#include /#include /#define N 5 int main(void) { int i, j, key; int square[N+1][N+1] = {0}; i = 0; j = (N+1) / 2; for(key = 1; key <= N/*N; key++) { if((key % N) == 1) i++; else { i--; j++; } if(i == 0) i = N; if(j > N) j = 1; square[i][j] = key; } for(i = 1; i <= N; i++) { for(j = 1; j <= N; j++) printf("%2d ", square[i][j]); } return 0; }

• Java public class Matrix { public static int[][] magicOdd(int n) { int[][] square = new int[n+1][n+1]; int i = 0; int j = (n+1) / 2; for(int key = 1; key <= n/*n; key++) { if((key % n) == 1) i++; else { i--; j++; } if(i == 0) i = n; if(j > n) j = 1; square[i][j] = key; } int[][] matrix = new int[n][n]; for(int k = 0; k < matrix.length; k++) { for(int l = 0; l < matrix[0].length; l++) { matrix[k][l] = square[k+1][l+1]; } } return matrix; } public static void main(String[] args) { int[][] magic = Matrix.magicOdd(5); for(int k = 0; k < magic.length; k++) { for(int l = 0; l < magic[0].length; l++) { System.out.print(magic[k][l] + " "); } System.out.println(); } } }

GrayCode

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如下： 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 观察奇数项的变化时，我们发现无论它是第几个Gray Code，永远只改变最右边的位元，如果是1就改为0，如果是0就改为1。 观察偶数项的变化时，我们发现所改变的位元，是由右边算来第一个1的左边位元。 以上两个变化规则是固定的，无论位元数为何；所以只要判断位元的位置是奇数还是偶数，就可以决定要改变哪一个位元的值，为了程式撰写方便，将阵列索引 0当作最右边的值，而在列印结果时，是由索引数字大的开始反向列印。 将2位元的Gray Code当作平面座标来看，可以构成一个四边形，您可以发现从任一顶点出发，绕四边形周长绕一圈，所经过的顶点座标就是一组Gray Code，所以您可以得到四组Gray Code。 同样的将3位元的Gray Code当作平面座标来看的话，可以构成一个正立方体，如果您可以从任一顶点出发，将所有的边长走过，并不重复经过顶点的话，所经过的顶点座标顺序之组合也就是一组Gray Code。

实作

• C /#include /#include /#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, odd; printf("输入位元数："); scanf("%d", &bits); for(i = 0; i < bits; 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 Code break; CHANGE_BIT(digit[i+1]); } for(i = bits - 1; i >= 0; i--) printf("%c", digit[i]); printf("\n"); NEXT(odd); } return 0; }

• Java public class GrayCode { private char[] digit; private boolean first; private boolean odd; private int count; public GrayCode(int length) { digit = new char[length]; for(int i = 0; i < length; i++) { digit[i] = '0'; } first = true; odd = true; } public boolean hasNext() { // 计算第一个1的位置 for(count = 0; (count < digit.length) && (digit[count] == '0'); count++) ; return count != digit.length - 1; } public char[] next() { if(first) { first = false; return digit; } if(odd) chargeBit(digit, 0); else { // 最后一个Gray Code 吗 if(hasNext()) chargeBit(digit, count+1); } odd = ((odd == true) ? false : true); return digit; } private void chargeBit(char[] digit, int i) { digit[i] = ((digit[i] == '0') ? '1' : '0'); } public static void main(String[] args) { GrayCode code = new GrayCode(4); while(code.hasNext()) { char[] digit = code.next(); for(int i = digit.length - 1; i >= 0; i--) System.out.print(digit[i]); System.out.println(); } } }

MultiColorHanoiTower

Algorithm Gossip: 双色、三色河内塔

说明

双色河内塔与三色河内塔是由之前所介绍过的河内塔规则衍生而来，双色河内塔的目的是将下图左上的圆环位置经移动成为右下的圆环位置： 而三色河内塔则是将下图左上的圆环经移动成为右上的圆环： 在移动的过程中，一样遵守大盘必须在小盘之下的规则，而颜色顺序则无限制。

解法

无论是双色河内塔或是三色河内塔，其解法观念与之前介绍过的河内塔是类似的，同样也是使用递回来解，不过这次递回解法的目的不同，我们先来看只有两个 盘的情况，这很简单，只要将第一柱的黄色移动至第二柱，而接下来第一柱的蓝色移动至第三柱。 再来是四个盘的情况，首先必须用递回完成下图左上至右下的移动： 接下来最底层的就不用管它们了，因为它们已经就定位，只要再处理第一柱的上面两个盘子就可以了。 那么六个盘的情况呢？一样！首先必须用递回完成下图左上至右下的移动： 接下来最底层的就不用管它们了，因为它们已经就定位，只要再处理第一柱上面的四个盘子就可以了，这又与之前只有四盘的情况相同，接下来您就知道该如何进行解题了，无论是八个盘、十个盘以上等，都是用这个观念来解题。 那么三色河内塔呢？一样，直接来看九个盘的情况，首先必须完成下图的移动结果： 接下来最底两层的就不用管它们了，因为它们已经就定位，只要再处理第一柱上面的三个盘子就可以了。 您也可以看看 Towers of Hanoi Page 中有关于河内塔的讨论。

实作

以下Java演算实例由 http://www.javaworld.com.tw 的 T5555 提供，感谢他的协助，我根据他的实例，转换为C语言的实作部份，您可以参考这个 讨论串 有关于河内塔的讨论。

• 双色河内塔 C 实作 /#include 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'; int i; 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() { int n; printf("请输入盘数："); scanf("%d", &n); hanoi2colors(n); return 0; }

• 三色河内塔 C 实作 /#include 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'; int i; 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() { int n; printf("请输入盘数："); scanf("%d", &n); hanoi3colors(n); return 0; }

• 双色河内塔 Java 实作 public class Hanoi2Colors { public static void help() { System.out.println( "Usage: java Hanoi2Colors number_of_disks"); System.out.println( "\t number_of_disks: must be a even number."); System.exit(0); } public static void main(String[] args) { int disks = 0; try { disks = Integer.parseInt(args[0]); } catch (Exception e) { help(); } if ((disks <= 0) || (disks % 2 != 0)) { help(); } hanoi2colors(disks); } public static void hanoi(int disks, char source, char temp, char target) { if (disks == 1) { System.out.println("move disk from "

• source + " to " + target); System.out.println("move disk from "
• source + " to " + target); } else { hanoi(disks-1, source, target, temp); hanoi(1, source, temp, target); hanoi(disks-1, temp, source, target); } } public static void hanoi2colors(int disks) { char source = 'A'; char temp = 'B'; char target = 'C'; for (int i = disks / 2; i > 1; i--) { hanoi(i-1, source, temp, target); System.out.println("move disk from "
• source + " to " + temp); System.out.println("move disk from "
• source + " to " + temp); hanoi(i-1, target, temp, source); System.out.println("move disk from "
• temp + " to " + target); } System.out.println("move disk from "
• source + " to " + temp); System.out.println("move disk from "
• source + " to " + target); } }

• 三色河内塔 Java 实作 public class Hanoi3Colors { public static void help() { System.out.println( "Usage: java Hanoi3Colors number_of_disks"); System.out.println( "\tnumber_of_disks: must be a number divisible by 3."); System.exit(0); } public static void main(String[] args) { int disks = 0; try { disks = Integer.parseInt(args[0]); } catch (Exception e) { help(); } if ((disks <= 0) || (disks % 3 != 0)) { help(); } hanoi3colors(disks); } public static void hanoi(int disks, char source, char temp, char target) { if (disks == 1) { System.out.println("move disk from "

• source + " to " + target); System.out.println("move disk from "
• source + " to " + target); System.out.println("move disk from "
• source + " to " + target); } else { hanoi(disks-1, source, target, temp); hanoi(1, source, temp, target); hanoi(disks-1, temp, source, target); } } public static void hanoi3colors(int disks) { char source = 'A'; char temp = 'B'; char target = 'C'; if (disks == 3) { System.out.println("move disk from "
• source + " to " + temp); System.out.println("move disk from "
• source + " to " + temp); System.out.println("move disk from "
• source + " to " + target); System.out.println("move disk from "
• temp + " to " + target); System.out.println("move disk from "
• temp + " to " + source); System.out.println("move disk from "
• target + " to " + temp); } else { hanoi(disks/3-1, source, temp, target); System.out.println("move disk from "
• source + " to " + temp); System.out.println("move disk from "
• source + " to " + temp); System.out.println("move disk from "
• source + " to " + temp); hanoi(disks/3-1, target, temp, source); System.out.println("move disk from "
• temp + " to " + target); System.out.println("move disk from "
• temp + " to " + target); System.out.println("move disk from "
• temp + " to " + target); hanoi(disks/3-1, source, target, temp); System.out.println("move disk from "
• target + " to " + source); System.out.println("move disk from "
• target + " to " + source); hanoi(disks/3-1, temp, source, target); System.out.println("move disk from "
• source + " to " + temp); for (int i = disks / 3 - 1; i > 0; i--) { if (i>1) { hanoi(i-1, target, source, temp); } System.out.println("move disk from "
• target + " to " + source); System.out.println("move disk from "
• target + " to " + source); if (i>1) { hanoi(i-1, temp, source, target); } System.out.println("move disk from "
• source + " to " + temp); } } } }

TriangleArray

Algorithm Gossip: 上三角、下三角、对称矩阵

说明

上三角矩阵是矩阵在对角线以下的元素均为0，即Aij = 0，i > j，例如： 1 2 3 4 5 0 6 7 8 9 0 0 10 11 12 0 0 0 13 14 0 0 0 0 15 下三角矩阵是矩阵在对角线以上的元素均为0，即Aij= 0，i < j，例如： 1 0 0 0 0 2 6 0 0 0 3 7 10 0 0 4 8 11 13 0 5 9 12 14 15 对称矩阵是矩阵元素对称于对角线，例如： 1 2 3 4 5 2 6 7 8 9 3 7 10 11 12 4 8 11 13 14 5 9 12 14 15 上三角或下三角矩阵也有大部份的元素不储存值（为0），我们可以将它们使用一维阵列来储存以节省储存空间，而对称矩阵因为对称于对角线，所以可以视为上三角或下三角矩阵来储存。

解法

假设矩阵为nxn，为了计算方便，我们让阵列索引由1开始，上三角矩阵化为一维阵列，若以列为主，其公式为： loc = n/(i-1) - i/(i-1)/2 + j 化为以行为主，其公式为： loc = j/(j-1)/2 + i 下三角矩阵化为一维阵列，若以列为主，其公式为： loc = i/(i-1)/2 + j 若以行为主，其公式为： loc = n/(j-1) - j/(j-1)/2 + i 公式的导证其实是由等差级数公式得到，您可以自行绘图并看看就可以导证出来，对于C/C++或Java等索引由0开始的语言来说，只要将i与j各加1，求得loc之后减1即可套用以上的公式。

实作

• C /#include /#include /#define N 5 int main(void) { int arr1[N][N] = { {1, 2, 3, 4, 5}, {0, 6, 7, 8, 9}, {0, 0, 10, 11, 12}, {0, 0, 0, 13, 14}, {0, 0, 0, 0, 15}}; int arr2[N/(1+N)/2] = {0}; int i, j, loc = 0; printf("原二维资料：\n"); for(i = 0; i < N; i++) { for(j = 0; j < N; j++) { printf("%4d", arr1[i][j]); } printf("\n"); } printf("\n以列为主："); for(i = 0; i < N; i++) { for(j = 0; j < N; j++) { if(arr1[i][j] != 0) arr2[loc++] = arr1[i][j]; } } for(i = 0; i < N/(1+N)/2; i++) printf("%d ", arr2[i]); printf("\n输入索引(i, j)："); scanf("%d, %d", &i, &j); loc = N/i - i/(i+1)/2 + j; printf("(%d, %d) = %d", i, j, arr2[loc]); printf("\n"); return 0; }

• Java public class TriangleArray { private int[] arr; private int length; public TriangleArray(int[][] array) { length = array.length; arr = new int[length/(1+length)/2]; int loc = 0; for(int i = 0; i < length; i++) { for(int j = 0; j < length; j++) { if(array[i][j] != 0) arr[loc++] = array[i][j]; } } } public int getValue(int i, int j) { int loc = length/i - i/*(i+1)/2 + j; return arr[loc]; } public static void main(String[] args) { int[][] array = { {1, 2, 3, 4, 5}, {0, 6, 7, 8, 9}, {0, 0, 10, 11, 12}, {0, 0, 0, 13, 14}, {0, 0, 0, 0, 15}}; TriangleArray triangleArray = new TriangleArray(array); System.out.print(triangleArray.getValue(2, 2)); } }

MergeSort

Algorithm Gossip: 合并排序法

说明

之前所介绍的排序法都是在同一个阵列中的排序，考虑今日有两笔或两笔以上的资料，它可能是不同阵列中的资料，或是不同档案中的资料，如何为它们进行排序？

解法

可以使用合并排序法，合并排序法基本是将两笔已排序的资料合并并进行排序，如果所读入的资料尚未排序，可以先利用其它的排序方式来处理这两笔资料，然后再将排序好的这两笔资料合并。 有人问道，如果两笔资料本身就无排序顺序，何不将所有的资料读入，再一次进行排序？排序的精神是尽量利用资料已排序的部份，来加快排序的效率，小笔资料的 排序较为快速，如果小笔资料排序完成之后，再合并处理时，因为两笔资料都有排序了，所有在合并排序时会比单纯读入所有的资料再一次排序来的有效率。 那么可不可以直接使用合并排序法本身来处理整个排序的动作？而不动用到其它的排序方式？答案是肯定的，只要将所有的数字不断的分为两个等分，直到最后剩一个数字为止，然后再反过来不断的合并，就如下图所示： 不过基本上分割又会花去额外的时间，不如使用其它较好的排序法来排序小笔资料，再使用合并排序来的有效率。 下面这个程式范例，我们使用快速排序法来处理小笔资料排序，然后再使用合并排序法处理合并的动作。

实作

• C /#include /#include /#include /#define MAX1 10 /#define MAX2 10 /#define SWAP(x,y) {int t; t = x; x = y; y = t;} int partition(int[], int, int); void quicksort(int[], int, int); void mergesort(int[], int, int[], int, int[]); int main(void) { int number1[MAX1] = {0}; int number2[MAX1] = {0}; int number3[MAX1+MAX2] = {0}; int i, num; srand(time(NULL)); printf("排序前："); printf("\nnumber1[]："); for(i = 0; i < MAX1; i++) { number1[i] = rand() % 100; printf("%d ", number1[i]); } printf("\nnumber2[]："); for(i = 0; i < MAX2; i++) { number2[i] = rand() % 100; printf("%d ", number2[i]); } // 先排序两笔资料 quicksort(number1, 0, MAX1-1); quicksort(number2, 0, MAX2-1); printf("\n排序后："); printf("\nnumber1[]："); for(i = 0; i < MAX1; i++) printf("%d ", number1[i]); printf("\nnumber2[]："); for(i = 0; i < MAX2; i++) printf("%d ", number2[i]); // 合并排序 mergesort(number1, MAX1, number2, MAX2, number3); printf("\n合并后："); for(i = 0; i < MAX1+MAX2; i++) printf("%d ", number3[i]); printf("\n"); return 0; } int partition(int number[], int left, int right) { int i, j, s; s = number[right]; i = left - 1; for(j = left; j < right; 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) { int q; if(left < right) { q = partition(number, left, right); quicksort(number, left, q-1); quicksort(number, q+1, right); } } void mergesort(int number1[], int M, int number2[], int N, int number3[]) { int i = 0, j = 0, k = 0; while(i < M && j < N) { if(number1[i] <= number2[j]) number3[k++] = number1[i++]; else number3[k++] = number2[j++]; } while(i < M) number3[k++] = number1[i++]; while(j < N) number3[k++] = number2[j++]; }

• Java public class MergeSort { public static int[] sort(int[] number1, int[] number2) { int[] number3 = new int[number1.length + number2.length]; int i = 0, j = 0, k = 0; while(i < number1.length && j < number2.length) { if(number1[i] <= number2[j]) number3[k++] = number1[i++]; else number3[k++] = number2[j++]; } while(i < number1.length) number3[k++] = number1[i++]; while(j < number2.length) number3[k++] = number2[j++]; return number3; } }