当前位置:文档之家› JAVA经典算法

JAVA经典算法

河内塔问题(Towers of Hanoi)问题说明:河內之塔(Towers of Hanoi)是法国人M.Claus(Lucas)於1883年从泰国带至法国的,河內为越战时北越的首都,即现在的胡志明市;1883年法国数学家 Edouard Lucas曾提及這个故事,据说创世紀时Benares有一座波罗教塔,是由三支钻石棒(Pag)所支撑,开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘(Disc),並命令僧侣将所有的金盘从第一根石棒移至第三根石棒,且搬运过程中遵守大盘子在小盘子之下的原则,若每日仅搬一个盘子,则当盘子全数搬运完毕之时,此塔将损毁,而也就是世界末日來临之时。

算法代码(Java):复制内容到剪贴板import java.io.*;public class Hanoi {public static void main(String args[]) throws IOException {int n;BufferedReader buf;buf = new BufferedReader(new InputStreamReader(System.in));System.out.print("请输入盘子个数");n = Integer.parseInt(buf.readLine());Hanoi hanoi = new Hanoi();hanoi.move(n, 'A', 'B', 'C');}public void move(int n, char a, char b, char c) {if(n == 1)System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);else {move(n - 1, a, c, b);System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);move(n - 1, b, a, c);}}}背包为题(Kanpsack Problem)问题说明:假设一个背包的负重最大可达8公斤,而希望在背包内放置负重范围你价值最高的物品。

算法代码(Java):复制内容到剪贴板class Fruit {private String name;private int size;private int price;public Fruit(String name, int size, int price) { = name;this.size = size;this.price = price;}public String getName() {return name;}public int getPrice() {return price;}public int getSize() {return size;}}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.length; 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] = newvalue;item[s] = i;}}}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]);}}双色,三色河内塔(Hanoi2Colors)问题说明:双色,三色河内塔是由河内塔演变而来的一种算法。

算法代码(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);}}三色河内塔复制内容到剪贴板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);}}}}字符串核对(String Match)问题说明:现在的一些高级程序语言对于字符串的处理支持越来越大,不过字符串搜寻本身仍是值得探讨的课题,在这里以Boyer Moore法来说明如何进行字符串说明,这个方法速度快且容易理解。

相关主题