用java实现的各种算法.docVIP

1 Fibonacci Fibonacci为1200年代的欧洲数学家，在他的著作中曾经提到：若有一只兔子每个月生一只小兔子，一个月后小兔子也开始生产。起初只有一只兔子，一个月后就有两只兔子，两个月后有三只兔子，三个月后有五只兔子（小兔子投入生产） 这就是Fibonacci数列，一般习惯称之为费式数列，例如：1，1，2，3，5，8，13，21，34，55，89， Java代码 public class Fibonacci public static void main(String args) int fib = new int20;fib0 = 0;fib1 = 1;for (int i = 2; i fib.length; i+)fibi = fibi - 1 + fibi - 2;for (int i = 0; i fib.length; i+)System.out.print(fibi + );System.out.println();2 巴斯卡（Pascal） 三角形基本上就是在解nCr ，因为三角形上的每一个数字各对应一个nCr ，其中n为row，而r为colnmu Java代码 public class Pascal extends JFrame public Pascal() setBackground(Color.white);setTitle(巴斯卡三角形);setSize(520, 350);setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);show();private long combi(int n, int r) int i;long p = 1;for (i = 1; i = r; i+)p = p * (n - i + 1) / i;return p;public void paint(Graphics g) final int N = 12;int n, r, t;for (n = 0; n = N; n+) for (r = 0; r = n; r+)g.drawString( + combi(n, r), (N - n) * 20 + r * 40,n * 20 + 50);public static void main(String args) Pascal frm = new Pascal();3 ThreeColorFlags ThreeColorFlags问题最早由E.W.Dijkstra所提出，塔所使用的用语为Dutch Nation Flag（Dijkstra为荷兰人），而多数的作者则使用Three-Color Flag来说明。 假设有一条绳子，上面有红，白，蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您希望将之分类，并排列蓝，白，红的顺序，要如何移动次数才会最少，注意您只能在绳子上进行这个动作，而且一次只能调换两个旗子。 Java代码 public class ThreeColorsFlags private void swap(char flags, int x, int y) char temp;temp = flagsx;flagsx = flagsy;flagsy = temp;public String move(char flags) int wFlag = 0;int bFlag = 0;int rFlag = flags.length - 1;while (wFlag = rFlag) if (flagswFlag = W) wFlag+; else if (flagswFlag = B) swap(flags, bFlag, wFlag);bFlag+;wFlag+; else while (wFlag rFlag & flagsrFlag = R)rFlag-;swap(flags, rFlag, wFlag);rFlag-;return new String(flags);public static void main(String args) throws IOException BufferedReader buf;buf = new BufferedReader(new InputStreamReader(System.in);System.out.print(输入三色旗顺序（ex. RWBBWRWR）：);String flags = buf.readLine();ThreeColorsFlags threeColorsFlag = new ThreeColorsFlags();flags = threeColorsFlag.move(flags.toUpperCase().toCharArray();System.out.println(移动顺序后： + flags);4 Mouse Mouse走迷宫是循环求解的基本类型，我们在二维数组中用2来表示迷宫的墙壁，使用1来表示老鼠的行走路径，并用程序求出从入口到出口的距离。 Java代码 public class Mouse private int startI, startJ; / 入口private int endI, endJ; / 出口private boolean success = false;public static void main(String args) int maze = 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 ;System.out.println(显示迷宫：);for (int i = 0; i maze.length; i+) for (int j = 0; j maze0.length; j+)if (mazeij = 2)System.out.print();elseSystem.out.print( );System.out.println();Mouse mouse = new Mouse();mouse.setStart(1, 1);mouse.setEnd(5, 5);if (!mouse.go(maze) System.out.println(n没有找到出口！); else System.out.println(n找到出口！);for (int i = 0; i maze.length; i+) for (int j = 0; j maze0.length; j+) if (mazeij = 2)System.out.print();else if (mazeij = 1)System.out.print();elseSystem.out.print( );System.out.println();public void setStart(int i, int j) this.startI = i;this.startJ = j;public void setEnd(int i, int j) this.endI = i;this.endJ = j;public boolean go(int maze) return visit(maze, startI, startJ);private boolean visit(int maze, int i, int j) mazeij = 1;if (i = endI & j = endJ)success = true;if (!success & mazeij + 1 = 0)visit(maze, i, j + 1);if (!success & mazei + 1j = 0)visit(maze, i + 1, j);if (!success & mazeij - 1 = 0)visit(maze, i, j - 1);if (!success & mazei - 1j = 0)visit(maze, i - 1, j);if (!success)mazeij = 0;return success; 5 Knight tour 骑士游戏，在十八世纪倍受数学家与拼图迷的注意，骑士的走法为西洋棋的走发，骑士可以由任何一个位置出发，它要如何走完所有的位置。 Java代码 public class Knight public boolean travel(int startX, int startY, int board) / 对应骑士可以走的八个方向int ktmove1 = -2, -1, 1, 2, 2, 1, -1, -2 ;int ktmove2 = 1, 2, 2, 1, -1, -2, -2, -1 ;/ 下一个出路的位置int nexti = new intboard.length;int nextj = new intboard.length;/ 记录出路的个数int exists = new intboard.length;int x = startX;int y = startY;boardxy = 1;for (int m = 2; m = Math.pow(board.length, 2); m+) for (int k = 0; k board.length; k+) existsk = 0;int count = 0;/ 试探八个方向for (int k = 0; k board.length; k+) int tmpi = x + ktmove1k;int tmpj = y + ktmove2k;/ 如果是边界，不可以走if (tmpi 0 | tmpj 7 | tmpj 7) continue;/ 如果这个方向可以走，记录下来if (boardtmpitmpj = 0) nexticount = tmpi;nextjcount = tmpj;/ 可走的方向加一个count+;int min = -1;if (count = 0) return false; else if (count = 1) min = 0; else / 找出下个位置的出路数for (int l = 0; l count; l+) for (int k = 0; k board.length; k+) int tmpi = nextil + ktmove1k;int tmpj = nextjl + ktmove2k;if (tmpi 0 | tmpj 7 | tmpj 7) continue;if (boardtmpitmpj = 0)existsl+;int tmp = exists0;min = 0;/ 从可走的方向寻找最少出路的方向for (int l = 1; l count; l+) if (existsl tmp) tmp = existsl;min = l;/ 走最少出路的方向x = nextimin;y = nextjmin;boardxy = m;return true;public static void main(String args) int board = new int88;Knight knight = new Knight();if ((Integer.parseInt(args0), Integer.parseInt(args1),board) System.out.println(走棋完成！); else System.out.println(走棋失败！);for (int i = 0; i board.length; i+) for (int j = 0; j board0.length; j+) if (boardij 10) System.out.print( + boardij); else System.out.print(boardij);System.out.print( );System.out.println();6 Queen 西洋棋中的皇后可以直线前进，吃掉遇到的所有棋子，如果棋盘上有八个皇后，则这八个皇后如何相安无事的放置在棋盘上？ Java代码 public class Queen / 同位置是否有皇后，1表示有private int column;/ 右上至左下是否有皇后private int rup;/ 左上至右下是否有皇后private int lup;/ 解答private int queen;/ 解答编号private int num;public Queen() column = new int8 + 1;rup = new int2 * 8 + 1;lup = new int2 * 8 + 1;for (int i = 1; i = 8; i+)columni = 1;for (int i = 1; i 8) showAnswer(); else for (int j = 1; j = 8; j+) if (columnj=1 & rupi+j=1 & lupi-j+8=1) queeni = j;/ 设定为占用columnj = rupi + j = lupi - j + 8 = 0;backtrack(i + 1);columnj = rupi + j = lupi - j + 8 = 1;protected void showAnswer() num+;System.out.println(n解答 + num);for (int y = 1; y = 8; y+) for (int x = 1; x = 8; x+) if (queeny = x) System.out.print( Q); else System.out.print( .);System.out.println();public static void main(String args) Queen queen = new Queen();queen.backtrack(1);7 Coins 现在有八枚银币abcdefg，已知其中一枚是假币，其重量不同于真币，但不知道是轻还是重，如何用天平以最小的比较次数决定出那个是假币，并得知假币是比真币轻还是重。 Java代码 public class Coins private int coins;public Coins() coins = new int8;for (int i = 0; i coins7)compare(6, 7, 0);elsecompare(7, 6, 0); else if (coins0 + coins1 + coins2 coins3 + coins4+ coins5) if (coins0 + coins3 = coins1 + coins4)compare(2, 5, 0);else if (coins0 + coins3 coins1 + coins4)compare(0, 4, 1);if (coins0 + coins3 coins1 + coins4)compare(1, 3, 0); else if (coins0 + coins1 + coins2 coins1 + coins4)compare(3, 1, 0);if (coins0 + coins3 coinsk)System.out.print(n假币 + (i + 1) + 较重);elseSystem.out.print(n假币 + (j + 1) + 较轻);public static void main(String args) if (args.length = 0) System.out.println(输入假币重量（比10大或小）);System.out.println(ex. java Coins 5);return;Coins eightCoins = new Coins();eightCoins.setFake(Integer.parseInt(args0);eightCoins.fake();8 Life game 生命游戏，为1970年英国数学家J.H.Conway所提出，某一细胞的邻居包括上，下，左，右，左上，左下，右上与右下相邻的细胞，游戏规则如下： 1，孤单死亡：如果细胞的邻居小于一个，则该细胞在下一个状态死亡。 2，拥挤死亡：如果细胞的邻居在四个以上，则该细胞在下一个状态死亡。 3，稳定：如果细胞的邻居为两个或三个，则该细胞在下一个状态稳定。 4，复活：如果某位置原无细胞存活，而该位置的邻居为三个，则该位置将复活一个细胞。 Java代码 public class LifeGame private boolean map;private boolean newmap;public LifeGame(int maxRow, int maxColumn) map = new booleanmaxRowmaxColumn;newmap = new booleanmaxRowmaxColumn;public void setCell(int x, int y) mapxy = true;public void next() for (int row = 0; row map.length; row+) for (int col = 0; col map0.length; col+) switch (neighbors(row, col) case 0:case 1:case 4:case 5:case 6:case 7:case 8:newmaprowcol = false;break;case 2:newmaprowcol = maprowcol;break;case 3:newmaprowcol = true;break;copyMap();public void outputMap() throws IOException System.out.println(nnGame of life cell status);for (int row = 0; row map.length; row+) System.out.print(n );for (int col = 0; col map0.length; col+)if (maprowcol = true)System.out.print(#);elseSystem.out.print(-);private void copyMap() for (int row = 0; row map.length; row+)for (int col = 0; col map0.length; col+)maprowcol = newmaprowcol;private int neighbors(int row, int col) int count = 0;for (int r = row - 1; r = row + 1; r+)for (int c = col - 1; c = col + 1; c+) if (r = map.length | c = map0.length)continue;if (maprc = true)count+;if (maprowcol = true)count-;return count;public static void main(String args) throws NumberFormatException,IOException BufferedReader bufReader = new BufferedReader(new InputStreamReader(System.in);LifeGame game = new LifeGame(10, 25);System.out.println(Game of life Program);System.out.println(Enter x, y where x, y is living cell);System.out.println(0 = x 10, 0 = y 25);System.out.println(Terminate with x, y = -1, -1);while (true) String strs = bufReader.readLine().split( );int row = Integer.parseInt(strs0);int col = Integer.parseInt(strs1);if (0 = row & row 10 & 0 = col & row 25)game.setCell(row, col);else if (row = -1 | col = -1) break; else System.out.print(x, y) exceeds map ranage!);while (true) game.outputMap();game.next();System.out.print(nContinue next Generation ? );String ans = bufReader.readLine().toUpperCase();if (!ans.equals(Y)break;9 String Match 现在的一些高级程序语言对于字符串的处理支持越来越大，不过字符串搜寻本身仍是值得探讨的课题，在这里以Boyer Moore法来说明如何进行字符串说明，这个方法速度快且容易理解。 Java代码 public class StringMatch private int skip;private int p;private String str;private String key;public StringMatch(String key) skip = new int256;this.key = key;for (int k = 0; k = 255; k+)skipk = key.length();for (int k = 0; k key.length() - 1; k+)skipkey.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 += skipinput.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();10 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 intMAX + 1;int value = new intMAX + 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 = fruitsi.getSize(); s values) / 找到阶段最佳解values = newvalue;items = i;System.out.println(物品t价格);for (int i = MAX; i = MIN; i = i - fruitsitemi.getSize() System.out.println(fruitsitemi.getName() + t+ fruitsitemi.getPrice();System.out.println(合计t + valueMAX);11 Towers of Hanoi 河內之塔(Towers of Hanoi)是法国人M.Claus(Lucas)於1883年从泰国带至法国的，河內为越战时北越的首都，即现在的胡志明市；1883年法国数学家 Edouard Lucas曾提及這个故事，据说创世紀时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小 至大排列的金盘（Disc），並命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当 盘子全数搬运完毕之时，此塔将损毁，而也就是世界末日來临之时。 Java代码 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);12 Hanoi2Colors 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(args0); catch (Exception e) help();if (disks 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写的常用算法放在了一起,希望可以对我们学习java有所帮助。 最后写一个很有用的星期的介绍 如何计算某一天是星期几? 蔡勒（Zeller）公式 历史上的某一天是星期几？未来的某一天是星期几？关于这个问题，有很多计算公式（两个通用计算公式和一些分段计算公式），其中最著名的是蔡勒（Zeller）公式。即w=y+y/4+c/4-2c+26(m+1)/10+d-1 公式中的符号含义如下，w：星期；c：世纪-1；y：年（两位数）；m：月（m大于等于3，小于等于14，即在蔡勒公式中，某年的1、2月要看作 上一年的13、14月来计算，比如2003年1月1日要看作2002年的13月1日来计算）；d：日； 代表取整，即只要整数部分。(C是世纪数减一，y是年份后两位，M是月份，d是日数。1月和2月要按上一年的13月和 14月来算，这时C和y均按上一年取值。) 算出来的W除以7，余数是几就是星期几。如果余数是0，则为星期日。 以2049年10月1日（100周年国庆）为例，用