Java算法之经典题目篇

Java算法之经典题目篇现在先推出比较经典问题的Java算法，过段时间会继续推出，关于查询，数列，排序之类的java算法。谢谢大家。应版主要求我一楼放个目录，呵呵。1：费式数列2：巴斯卡三角形3:三色棋4：老鼠走迷宫5：骑士走棋盘6：八个皇后7：八枚银币8：生命游戏9：字符串核对10：双色，三色河内塔11：背包问题12：河内塔[本帖最后由橡树心于2008-1-1108:51编辑]看来祖国还是需要我的!TOP有奖|电脑报2010年度中国IT品牌风云读者调查“我对电脑报有话说”有奖活动橡树心一展身手2F大中小发表于2008-1-918:47只看该作者硬派江湖年度压轴大戏开唱费式数列（Fibonacci）问题说明：Fibonacci为1200年代的欧洲数学家，在他的著作中曾经提到：若有一只兔子每个月生一只小兔子，一个月后小兔子也开个人空间发短消息加为好友当前离线始生产。起初只有一只兔子，一个月后就有两只兔子，两个月后有三只兔子，三个月后有五只兔子（小兔子投入生产）……这就是Fibonacci数列，一般习惯称之为费式数列，例如：1，1，2，3，5，8，13，21，34，55，89，……算法代码（Java）：复制内容到剪贴板代码:publicclassFibonacci{publicstaticvoidmain(String[]args){int[]fib=newint[20];fib[0]=0;fib[1]=1;for(inti=2;ifib.length;i++)fib[i]=fib[i-1]+fib[i-2];for(inti=0;ifib.length;i++)System.out.print(fib[i]+);System.out.println();}}[本帖最后由橡树心于2008-1-918:51编辑]看来祖国还是需要我的!TOP电脑报2010年度中国IT品牌风云读者调查橡树心3F大中小发表于2008-1-918:50只看该作者第49期黑客小游戏奇妙的配酒一展身手个人空间发短消息加为好友当前离线巴斯卡三角形（Pascal）问题说明：巴斯卡（Pascal）三角形基本上就是在解nCr，因为三角形上的每一个数字各对应一个nCr，其中n为row，而r为colnmu，算法代码（Java）：复制内容到剪贴板代码:importjava.awt.*;importjavax.swing.*;publicclassPascalextendsJFrame{publicPascal(){setBackground(Color.white);setTitle(巴斯卡三角形);setSize(520,350);setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);show();}privatelongcombi(intn,intr){inti;longp=1;for(i=1;i=r;i++)p=p*(n-i+1)/i;returnp;}publicvoidpaint(Graphicsg){finalintN=12;intn,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);}}publicstaticvoidmain(Stringargs[]){Pascalfrm=newPascal();}}看来祖国还是需要我的!TOP看照片，猜名字——电脑报编辑猜猜乐橡树心一展身手个人空间发短消息加为好友当前4F大中小发表于2008-1-918:54只看该作者三色旗（ThreeColorFlags）问题说明：三色旗的问题最早由E.W.Dijkstra所提出，塔所使用的用语为DutchNationFlag（Dijkstra为荷兰人），而多数的作者则使用Three-ColorFlag来说明。假设有一条绳子，上面有红，白，蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您希望将之分类，并排列蓝，白，红的顺序，要如何移动次数才会最少，注意您只能在绳子上进行这个动作，而且一次只能调换两个旗子。算法代码（Java）:离线复制内容到剪贴板代码:importjava.io.*;publicclassThreeColorsFlags{privatevoidswap(char[]flags,intx,inty){chartemp;temp=flags[x];flags[x]=flags[y];flags[y]=temp;}publicStringmove(char[]flags){intwFlag=0;intbFlag=0;intrFlag=flags.length-1;while(wFlag=rFlag){if(flags[wFlag]=='W'){wFlag++;}elseif(flags[wFlag]=='B'){swap(flags,bFlag,wFlag);bFlag++;wFlag++;}else{while(wFlagrFlag&&flags[rFlag]=='R')rFlag--;swap(flags,rFlag,wFlag);rFlag--;}}returnnewString(flags);}publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderbuf;buf=newBufferedReader(newInputStreamReader(System.in));System.out.print(输入三色旗顺序（ex.RWBBWRWR）：);Stringflags=buf.readLine();ThreeColorsFlagsthreeColorsFlag=newThreeColorsFlags();flags=threeColorsFlag.move(flags.toUpperCase().toCharArray());System.out.println(移动顺序后：+flags);}}[本帖最后由橡树心于2008-1-919:06编辑]看来祖国还是需要我的!TOP橡树心一展身手5F大中小发表于2008-1-918:54只看该作者老鼠走迷宫（Mouse）问题说明：老鼠走迷宫是循环求解的基本类型，我们在二维数组中用2个人空间发短消息加为好友当前离线来表示迷宫的墙壁，使用1来表示老鼠的行走路径，并用程序求出从入口到出口的距离。算法代码（Java）：复制内容到剪贴板代码:publicclassMouse{privateintstartI,startJ;//入口privateintendI,endJ;//出口privatebooleansuccess=false;publicstaticvoidmain(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(inti=0;imaze.length;i++){for(intj=0;jmaze[0].length;j++)if(maze[j]==2)System.out.print(█);elseSystem.out.print();System.out.println();}Mousemouse=newMouse();mouse.setStart(1,1);mouse.setEnd(5,5);if(!mouse.go(maze)){System.out.println(\n没有找到出口！);}else{System.out.println(\n找到出口！);for(inti=0;imaze.length;i++){for(intj=0;jmaze[0].length;j++){if(maze[j]==2)System.out.print(█);elseif(maze[j]==1)System.out.print(◇);elseSystem.out.print();}System.out.println();}}}publicvoidsetStart(inti,intj){this.startI=i;this.startJ=j;}publicvoidsetEnd(inti,intj){this.endI=i;this.endJ=j;}publicbooleango(int[][]maze){returnvisit(maze,startI,startJ);}privatebooleanvisit(int[][]maze,inti,intj){maze[j]=1;if(i==endI&&j==endJ)success=true;if(!success&&maze[j+1]==0)visit(maze,i,j+1);if(!success&&maze[i+1][j]==0)visit(maze,i+1,j);if(!success&&maze[j-1]==0)visit(maze,i,j-1);if(!success&&maze[i-1][j]==0)visit(maze,i-1,j);if(!success)maze[j]=0;returnsuccess;}}由于迷宫的设计，老鼠从迷宫的入口到出口的路径可能不只一条，下面我们显示所有路径。复制内容到剪贴板代码:publicclassMouse{privateintstartI,startJ;//入口privateintendI,endJ;//出口publicstaticvoidmain(String[]args){intmaze[][]={{2,2,2,2,2,2,2,2,2},{2,0,0,0,0,0,0,0,2},{2,0,2,2,0,2,2,0,2},{2,0,2,0,0,2,0,0,2},{2,0,2,0,2,0,2,0,2},{2,0,0,0,0,0,2,0,2},{2,2,0,2,2,0,2,2,2},{2,0,0,0,0,0,0,0,2},{2,2,2,2,2,2,2,2,2}};System.out.println(显示迷宫：);for(inti=0;imaze.length;i++){for(intj=0;jmaze[0].length;j++)if(maze[i][j]==2)System.out.print(█);elseSystem.out.print();System.out.println();}Mousemouse=newMouse();mouse.setStart(1,1);mouse.setEnd(7,7);mouse.go(maze);}publicvoidsetStart(inti,intj){this.startI=i;this.startJ=j;}publicvoidsetEnd(inti,intj){this.endI=i;this.endJ=j;}publicvoidgo(int[][]maze){visit(maze,startI,startJ);}privatevoidvisit(int[][]maze,inti,intj){maze[i][j]=1;if(i==endI&&j==endJ){System.out.println(\n找到出口！);for(intm=0;mmaze.length;m++){for(intn=0;nmaze[0].length;n++){if(maze[m][n]==2)System.out.print(█);elseif(maze[m][n]==1)System.out.print(◇);elseSyste