CrapsGame

Algorithm Gossip: Craps赌博游戏

说明

一个简单的赌博游戏，游戏规则如下：玩家掷两个骰子，点数为1到6，如果第一次点数和为7或11，则玩家胜，如果点数和为2、3或12，则玩家输，如果和 为其它点数，则记录第一次的点数和，然后继续掷骰，直至点数和等于第一次掷出的点数和，则玩家胜，如果在这之前掷出了点数和为7，则玩家输。

解法

规则看来有些复杂，但是其实只要使用switch配合if条件判断来撰写即可，小心不要弄错胜负顺序即可。

实作

• C /#include /#include /#include /#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, sumOfDice; int firstPoint = 0; char c; 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; break; case 2: case 3: case 12: gameStatus = LOST; break; default: firstRoll = 0; gameStatus = CONTINUE; firstPoint = sumOfDice; break; } } 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("游戏结束"); break; } firstRoll = 1; } } return 0; }

• Java import java.io./; public class Craps { public static void main(String[] args) throws IOException { final int WON = 0, LOST = 1, CONTINUE = 2; boolean firstRoll = true; int gameStatus = CONTINUE; int die1, die2, sumOfDice; int firstPoint = 0; System.out.print( "Craps赌博游戏，按Enter键开始游戏////"); while(true) { System.in.read(); if(firstRoll) { sumOfDice = rollDice(); System.out.println( "\n玩家掷出点数和：" + sumOfDice); switch(sumOfDice) { case 7: case 11: gameStatus = WON; break; case 2: case 3: case 12: gameStatus = LOST; break; default: firstRoll = false; gameStatus = CONTINUE; firstPoint = sumOfDice; break; } } else { sumOfDice = rollDice(); System.out.println( "\n玩家掷出点数和：" + sumOfDice); if(sumOfDice == firstPoint) gameStatus = WON; else if(sumOfDice == 7) gameStatus = LOST; } if(gameStatus == CONTINUE) System.out.println("未分胜负，再掷一次////"); else { if(gameStatus == WON) System.out.println("玩家胜"); else System.out.println("玩家输"); System.out.print("再玩一次？"); if(System.in.read() == 'n') { System.out.println("游戏结束"); break; } firstRoll = true; } } } public static int rollDice() { int roll = ((int)(Math.random() / 6) + (int)(Math.random() /* 6)); if(roll < 2) { roll = 2; } return roll; } }

BinarySearch

Algorithm Gossip: 二分搜寻法（搜寻原则的代表）

说明

如果搜寻的数列已经有排序，应该尽量利用它们已排序的特性，以减少搜寻比对的次数，这是搜寻的基本原则，二分搜寻法是这个基本原则的代表。

解法

在二分搜寻法中，从数列的中间开始搜寻，如果这个数小于我们所搜寻的数，由于数列已排序，则该数左边的数一定都小于要搜寻的对象，所以无需浪费时间在左边的数；如果搜寻的数大于所搜寻的对象，则右边的数无需再搜寻，直接搜寻左边的数。 所以在二分搜寻法中，将数列不断的分为两个部份，每次从分割的部份中取中间数比对，例如要搜寻92于以下的数列，首先中间数索引为(0+9)/2 = 4（索引由0开始）： [3 24 57 57 67 68 83 90 92 95] 由于67小于92，所以转搜寻右边的数列： 3 24 57 57 67 [68 83 90 92 95] 由于90小于92，再搜寻右边的数列，这次就找到所要的数了： 3 24 57 57 67 68 83 90 [92 95]

实作

• C /#include /#include /#include /#define MAX 10 /#define SWAP(x,y) {int t; t = x; x = y; y = t;} void quicksort(int[], int, int); int bisearch(int[], int); int main(void) { int number[MAX] = {0}; int i, find; srand(time(NULL)); for(i = 0; i < MAX; i++) { number[i] = rand() % 100; } quicksort(number, 0, MAX-1); printf("数列："); for(i = 0; i < MAX; i++) printf("%d ", number[i]); printf("\n输入寻找对象："); scanf("%d", &find); if((i = bisearch(number, find)) >= 0) printf("找到数字于索引 %d ", i); else printf("\n找不到指定数"); printf("\n"); return 0; } int bisearch(int number[], int find) { int low, mid, upper; low = 0; upper = MAX - 1; while(low <= upper) { mid = (low+upper) / 2; if(number[mid] < find) low = mid+1; else if(number[mid] > find) upper = mid - 1; else return mid; } return -1; } void quicksort(int number[], int left, int right) { int i, j, k, s; if(left < right) { s = number[(left+right)/2]; i = left - 1; j = right + 1; while(1) { while(number[++i] < s) ; // 向右找 while(number[--j] > s) ; // 向左找 if(i >= j) break; SWAP(number[i], number[j]); } quicksort(number, left, i-1); // 对左边进行递回 quicksort(number, j+1, right); // 对右边进行递回 } }

• Java public class BinarySearch { public static int search(int[] number, int des) { int low = 0; int upper = number.length - 1; while(low <= upper) { int mid = (low+upper) / 2; if(number[mid] < des) low = mid+1; else if(number[mid] > des) upper = mid - 1; else return mid; } return -1; } public static void main(String[] args) { int[] number = {1, 4, 2, 6, 7, 3, 9, 8}; QuickSort.sort(number); int find = BinarySearch.search(number, 3); if(find != -1) System.out.println("找到数值于索引" + find); else System.out.println("找不到数值"); } }

TwoNOneArray

Algorithm Gossip: 2(2N+1) 魔方阵

说明

方阵的维度整体来看是偶数，但是其实是一个奇数乘以一个偶数，例如6X6，其中6=2X3，我们也称这种方阵与单偶数方阵。

解法

如果您会解奇数魔术方阵，要解这种方阵也就不难理解，首先我们令n=2(2m+1)，并将整个方阵看作是数个奇数方阵的组合，如下所示： 魔方阵") 首先依序将A、B、C、D四个位置，依奇数方阵的规则填入数字，填完之后，方阵中各行的和就相同了，但列与对角线则否，此时必须在A-D与C- B之间，作一些对应的调换，规则如下：

1. 将A中每一列(中间列除外)的头m个元素，与D中对应位置的元素调换。
2. 将A的中央列、中央那一格向左取m格，并与D中对应位置对调
3. 将C中每一列的倒数m-1个元素，与B中对应的元素对调 举个实例来说，如何填6X6方阵，我们首先将之分解为奇数方阵，并填入数字，如下所示： 魔方阵") 接下来进行互换的动作，互换的元素以不同颜色标示，如下： 魔方阵") 由于m-1的数为0，所以在这个例子中，C-B部份并不用进行对调。

实作

• C /#include /#include /#define N 6 /#define SWAP(x,y) {int t; t = x; x = y; y = t;} void magic_o(int [][N], int); void exchange(int [][N], int); int main(void) { int square[N][N] = {0}; int i, j; magic_o(square, N/2); exchange(square, N); for(i = 0; i < N; i++) { for(j = 0; j < N; j++) printf("%2d ", square[i][j]); printf("\n"); } return 0; } void magic_o(int square[][N], int n) { int count, row, column; row = 0; column = n / 2; for(count = 1; count <= n/n; count++) { square[row][column] = count; // 填A square[row+n][column+n] = count + n/n; // 填B square[row][column+n] = count + 2/n/n; // 填C square[row+n][column] = count + 3/n/n; // 填D if(count % n == 0) row++; else { row = (row == 0) ? n - 1 : row - 1 ; column = (column == n-1) ? 0 : column + 1; } } } void exchange(int x[][N], int n) { int i, j; int m = n / 4; int m1 = m - 1; for(i = 0; i < n/2; i++) { if(i != m) { for(j = 0; j < m; j++) // 处理规则 1 SWAP(x[i][j], x[n/2+i][j]); for(j = 0; j < m1; j++) // 处理规则 2 SWAP(x[i][n-1-j], x[n/2+i][n-1-j]); } else { // 处理规则 3 for(j = 1; j <= m; j++) SWAP(x[m][j], x[n/2+m][j]); for(j = 0; j < m1; j++) SWAP(x[m][n-1-j], x[n/2+m][n-1-j]); } } }

• Java public class Matrix { public static int[][] magic22mp1(int n) { int[][] square = new int[n][n]; magic_o(square, n/2); exchange(square, n); return square; } private static void magic_o(int[][] square, int n) { int row = 0; int column = n / 2; for(int count = 1; count <= n/n; count++) { square[row][column] = count; // 填A square[row+n][column+n] = count + n/n; // 填B square[row][column+n] = count + 2/n/n; // 填C square[row+n][column] = count + 3/n/n; // 填D if(count % n == 0) row++; else { row = (row == 0) ? n - 1 : row - 1 ; column = (column == n-1) ? 0 : column + 1; } } } private static void exchange(int[][] x, int n) { int i, j; int m = n / 4; int m1 = m - 1; for(i = 0; i < n/2; i++) { if(i != m) { for(j = 0; j < m; j++) // 处理规则 1 swap(x, i, j, n/2+i, j); for(j = 0; j < m1; j++) // 处理规则 2 swap(x, i, n-1-j, n/2+i, n-1-j); } else { // 处理规则 3 for(j = 1; j <= m; j++) swap(x, m, j, n/2+m, j); for(j = 0; j < m1; j++) swap(x, m, n-1-j, n/2+m, n-1-j); } } } private static void swap(int[][] number, int i, int j, int k, int l) { int t; t = number[i][j]; number[i][j] = number[k][l]; number[k][l] = t; } public static void main(String[] args) { int[][] magic = Matrix.magic22mp1(6); 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(); } } }

MaxGuest

Algorithm Gossip: 最大访客数

说明

现将举行一个餐会，让访客事先填写到达时间与离开时间，为了掌握座位的数目，必须先估计不同时间的最大访客数。

解法

这个题目看似有些复杂，其实相当简单，单就计算访客数这个目的，同时考虑同一访客的来访时间与离开时间，反而会使程式变得复杂；只要将来访时间与离开时间分开处理就可以了，假设访客 i 的来访时间为x[i]，而离开时间为y[i]。 在资料输入完毕之后，将x[i]与y[i]分别进行排序（由小到大），道理很简单，只要先计算某时之前总共来访了多少访客，然后再减去某时之前的离开访客，就可以轻易的解出这个问题。

实作

• C /#include /#include /#define MAX 100 /#define SWAP(x,y) {int t; t = x; x = y; y = t;} 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) break; 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 <= count; i++) { if(time > x[i]) num++; if(time > y[i]) num--; } return num; } 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); } }

• Java import java.io./; import java.util./; public class MaxVisit { public static int maxGuest(int[] x, int[] y, int time) { int num = 0; for(int i = 0; i < x.length; i++) { if(time > x[i]) num++; if(time > y[i]) num--; } return num; } public static void main(String[] args) throws IOException { BufferedReader buf = new BufferedReader( new InputStreamReader(System.in)); System.out.println("输入来访时间与离开时间(0~24)："); System.out.println("范例：10 15"); System.out.println("输入-1结束"); java.util.ArrayList list = new ArrayList(); while(true) { System.out.print(">>"); String input = buf.readLine(); if(input.equals("-1")) break; list.add(input); } int[] x = new int[list.size()]; int[] y = new int[list.size()]; for(int i = 0; i < x.length; i++) { String input = (String) list.get(i); String[] strs = input.split(" "); x[i] = Integer.parseInt(strs[0]); y[i] = Integer.parseInt(strs[1]); } Arrays.sort(x); Arrays.sort(y); for(int time = 0; time < 25; time++) { System.out.println(time + " 时的最大访客数："

• MaxVisit.maxGuest(x, y, time)); } } }

MatchString

Algorithm Gossip: 字串核对

说明

今日的一些高阶程式语言对于字串的处理支援越来越强大（例如Java、Perl等），不过字串搜寻本身仍是个值得探讨的课题，在这边以Boyer- Moore法来说明如何进行字串说明，这个方法快且原理简洁易懂。

解法

字串搜寻本身不难，使用暴力法也可以求解，但如何快速搜寻字串就不简单了，传统的字串搜寻是从关键字与字串的开头开始比对，例如 Knuth-Morris-Pratt 演算法 字串搜寻，这个方法也不错，不过要花时间在公式计算上；Boyer-Moore字串核对改由关键字的后面开始核对字串，并制作前进表，如果比对不符合则依前进表中的值前进至下一个核对处，假设是p好了，然后比对字串中p-n+1至p的值是否与关键字相同。 那么前进表该如何前进，举个实际的例子，如果要在字串中搜寻JUST这个字串，则可能遇到的几个情况如下所示： 依照这个例子，可以决定出我们的前进值表如下： 其它 J U S T 4 3 2 1 4（match?） 如果关键字中有重复出现的字元，则前进值就会有两个以上的值，此时则取前进值较小的值，如此就不会跳过可能的位置，例如texture这个关键字，t的前 进值应该取后面的3而不是取前面的7。

实作

• C /#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 <= 255; k++) skip[k] = n; for(k = 0; k < n - 1; k++) skip[key[k]] = n - k - 1; } int search(int p, char/ input, char/ key) { int i, m, n; 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, j; for(i = s, j = 0; i <= e; i++, j++) tmp[j] = text[i]; tmp[j] = '\0'; }

• Java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class StringMatch { private int[] skip; private int p; private String str; private String key; public StringMatch(String key) { skip = new int[256]; this.key = key; for(int k = 0; k <= 255; k++) skip[k] = key.length(); for(int k = 0; k < key.length() - 1; k++) skip[key.charAt(k)] = key.length() - k - 1; } public void search(String str) { this.str = str; p = search(key.length()-1, str, key); } private int search(int p, String input, String key) { while(p < input.length()) { String tmp = input.substring( p-key.length()+1, p+1); if(tmp.equals(key)) // 比较两字串是否相同 return p-key.length()+1; p += skip[input.charAt(p)]; } return -1; } public boolean hasNext() { return (p != -1); } public String next() { String tmp = str.substring(p); p = search(p+key.length()+1, str, key); return tmp; } public static void main(String[] args) throws IOException { BufferedReader bufReader = new BufferedReader( new InputStreamReader(System.in)); System.out.print("请输入字串："); String str = bufReader.readLine(); System.out.print("请输入搜寻关键字："); String key = bufReader.readLine(); StringMatch strMatch = new StringMatch(key); strMatch.search(str); while(strMatch.hasNext()) { System.out.println(strMatch.next()); } } }