win7系统
MyEclipse开发工具
jdk1.60
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时，则n=64。如果对这数字没什幺概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。以下实例演示了 Java 河内之塔的实现：public class MainClass { public static void main(String[] args) { int nDisks = 3; doTowers(nDisks, 'A', 'B', 'C'); } public static void doTowers(int topN, char from,char inter, char to) { if (topN == 1){ System.out.println('盘子 1 从 '+ from + ' 到 ' + to); }else { doTowers(topN - 1, from, to, inter); System.out.println('盘子 '+ topN + ' 从 ' + from + ' 到 ' + to); doTowers(topN - 1, inter, from, to); } }}运行结果如下图：
2. 费式数列 斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368……特别指出：第0项是0，第1项是第一个1。这个数列从第三项开始，每一项都等于前两项之和。以下实例演示了 Java 斐波那契数列的实现：public class MainClass { public static long fibonacci(long number) { if ((number == 0) || (number == 1)) return number; else return fibonacci(number - 1) + fibonacci(number - 2); } public static void main(String[] args) { for (int counter = 0; counter <= 10; counter++) { System.out.printf('斐波那契数列 of %d is: %d\n', counter,fibonacci(counter)); } }}运行结果如下图：
3. 巴斯卡三角形巴斯卡（Pascal）三角形基本上就是在解 nCr ，因為三角形上的每一個數字各對應一個nCr，其中 n 為 row，而 r 為 column，如下： 0C0 1C0 1C1 3C0 3C1 3C2 3C3 4C0 4C1 4C2 4C3 4C4以下实例演示了 Java 巴斯卡三角形的实现：public class MainClass {public static void main(String[] args){ Scanner scanner = new Scanner(System.in); System.out.println('请输入巴斯卡三角行数：'); int num = scanner.nextInt(); pascalAssemble(num); } public static void pascalAssemble(int num){ int[][] value = new int[num][num]; for(int i = 0; i < num ;i++){ value[i][0] = 1; value[i][i] = 1; if(i > 1){ for(int j = 1; j < i ;j++){ value[i][j] = value[i-1][j-1] + value[i-1][j]; } } } for(int i = 0; i < num ;i++){ for(int k = 0; k <= num - i;k++){ System.out.print(' '); } for(int j = 0; j<= i ;j++){ System.out.print(value[i][j]+' '); } System.out.println(); } } } 运行结果如下图：
4. 三色棋问题说明： 三色旗的问题最早由E.W.Dijkstra所提出，他所使用的用语为Dutch Nation Flag(Dijkstra为荷兰人)，而多数的作者则使用Three-Color Flag来称之。假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上进行这个动作，而且一次只能调换两个旗子。解法在一条绳子上移动，在程式中也就意味只能使用一个阵列，而不使用其它的阵列来作辅助，问题的解法很简单，您可以自己想像一下在移动旗子，从绳子开头进行，遇到蓝色往前移，遇到白色留在中间，遇到红色往后移。只是要让移动次数最少的话，就要有些技巧。以下实例演示了 Java 三色棋的实现：public class MainClass { private void swap(char[] flags, int x, int y) { char temp; temp = flags[x]; flags[x] = flags[y]; flags[y] = temp; } public String move(char[] flags) { int wFlag = 0; int bFlag = 0; int rFlag = flags.length - 1; while (wFlag <= rFlag) { if (flags[wFlag] == 'W') { wFlag++; } else if (flags[wFlag] == 'B') { swap(flags, bFlag, wFlag); bFlag++; wFlag++; } else { while (wFlag < rFlag && flags[rFlag] == 'R') rFlag--; swap(flags, rFlag, wFlag); rFlag--; } } return new String(flags); } public static void main(String[] args) throws IOException { BufferedReader buf = new BufferedReader(new InputStreamReader(System.in)); System.out.print('输入三色的顺序（例如： RWBBWRWR）：'); String flags = buf.readLine(); MainClass threeColorsFlag = new MainClass(); flags = threeColorsFlag.move(flags.toUpperCase().toCharArray()); System.out.println('移动后的顺序为：' + flags); }}运行结果如下图：
15. Eratosthenes 筛选求质数说明: 除了自身之外，无法被其它整数整除的数称之为质数，在自然数中，除了1和此整数自身外，不能够被其他自然数整除的数，称之为质数。要求质数很简单，但如何快速的求出质数则一直是程式设计人员与数学家努力的课题，在这边介绍一个着名的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 15 16 17 18 19 20 21 ........ N先用2的去做筛选，从4=22 开始，筛去2的倍数，循环步长为2： 2 3 5 7 9 11 13 15 17 19 21 ........ N再用3的去做筛选，从9=32 开始，筛去3的倍数，循环步长为3： 2 3 5 7 11 13 17 19 ........ N再用5的去做筛选，再用5的去做筛选，再用11的去做筛选........，如此进行到最后留下的数就都是质数，这就是Eratosthenes筛选方法（Eratosthenes Sieve Method）。代码如下：public class MainClass { public static void main(String[] args) { int N = 100; int i = 0, j = 0, count = 0; int prime[] = new int[N + 1]; // 初始化数据 for (i = 2; i <= N; i++) { prime[i] = 1; } // 循环1(N 开方 次) for (i = 2; i * i <= N; i++) { if (prime[i] == 0) { count++; continue; } // 循环2(N/i 次) 筛选被i整除的数 for (j = i * i; j <= N; j = j + i) { prime[j] = 0; count++; } } System.out.println('计算次数: ' + count); j = 0; for (i = 2; i <= N; i++) { if (prime[i] == 1) { System.out.print('\t'); System.out.print(i); j++; if (j % 5 == 0) { System.out.println(); } } } }}