用java实现的各种算法.docx
- 文档编号:2134709
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:38
- 大小:34.22KB
用java实现的各种算法.docx
《用java实现的各种算法.docx》由会员分享,可在线阅读,更多相关《用java实现的各种算法.docx(38页珍藏版)》请在冰点文库上搜索。
用java实现的各种算法
1Fibonacci
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;i fib[i]=fib[i-1]+fib[i-2]; for(inti=0;i System.out.print(fib[i]+""); System.out.println(); } } 2巴斯卡(Pascal) 三角形基本上就是在解nCr,因为三角形上的每一个数字各对应一个nCr,其中n为row,而r为colnmu Java代码 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(); } } 3ThreeColorFlags ThreeColorFlags问题最早由E.W.Dijkstra所提出,塔所使用的用语为DutchNationFlag(Dijkstra为荷兰人),而多数的作者则使用Three-ColorFlag来说明。 假设有一条绳子,上面有红,白,蓝三种颜色的旗子,起初绳子上的旗子颜色并没有顺序,您希望将之分类,并排列蓝,白,红的顺序,要如何移动次数才会最少,注意您只能在绳子上进行这个动作,而且一次只能调换两个旗子。 Java代码 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(wFlag 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); } } 4Mouse 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;i for(intj=0;j if(maze[i][j]==2) System.out.print("█"); else System.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;i for(intj=0;j if(maze[i][j]==2) System.out.print("█"); elseif(maze[i][j]==1) System.out.print("◇"); else System.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[i][j]=1; if(i==endI&&j==endJ) success=true; if(! success&&maze[i][j+1]==0) visit(maze,i,j+1); if(! success&&maze[i+1][j]==0) visit(maze,i+1,j); if(! success&&maze[i][j-1]==0) visit(maze,i,j-1); if(! success&&maze[i-1][j]==0) visit(maze,i-1,j); if(! success) maze[i][j]=0; returnsuccess; } } 5Knighttour 骑士游戏,在十八世纪倍受数学家与拼图迷的注意,骑士的走法为西洋棋的走发,骑士可以由任何一个位置出发,它要如何走完所有的位置。 Java代码 publicclassKnight{ publicbooleantravel(intstartX,intstartY,int[][]board){ //对应骑士可以走的八个方向 int[]ktmove1={-2,-1,1,2,2,1,-1,-2}; int[]ktmove2={1,2,2,1,-1,-2,-2,-1}; //下一个出路的位置 int[]nexti=newint[board.length]; int[]nextj=newint[board.length]; //记录出路的个数 int[]exists=newint[board.length]; intx=startX; inty=startY; board[x][y]=1; for(intm=2;m<=Math.pow(board.length,2);m++){ for(intk=0;k exists[k]=0; } intcount=0; //试探八个方向 for(intk=0;k inttmpi=x+ktmove1[k]; inttmpj=y+ktmove2[k]; //如果是边界,不可以走 if(tmpi<0||tmpj<0||tmpi>7||tmpj>7){ continue; } //如果这个方向可以走,记录下来 if(board[tmpi][tmpj]==0){ nexti[count]=tmpi; nextj[count]=tmpj; //可走的方向加一个 count++; } } intmin=-1; if(count==0){ returnfalse; }elseif(count==1){ min=0; }else{ //找出下个位置的出路数 for(intl=0;l for(intk=0;k inttmpi=nexti[l]+ktmove1[k]; inttmpj=nextj[l]+ktmove2[k]; if(tmpi<0||tmpj<0||tmpi>7||tmpj>7){ continue; } if(board[tmpi][tmpj]==0) exists[l]++; } } inttmp=exists[0]; min=0; //从可走的方向寻找最少出路的方向 for(intl=1;l if(exists[l] tmp=exists[l]; min=l; } } } //走最少出路的方向 x=nexti[min]; y=nextj[min]; board[x][y]=m; } returntrue; } publicstaticvoidmain(String[]args){ int[][]board=newint[8][8]; Knightknight=newKnight(); if(knight.travel(Integer.parseInt(args[0]),Integer.parseInt(args[1]), board)){ System.out.println("走棋完成! "); }else{ System.out.println("走棋失败! "); } for(inti=0;i for(intj=0;j if(board[i][j]<10){ System.out.print(""+board[i][j]); }else{ System.out.print(board[i][j]); } System.out.print(""); } System.out.println(); } } } 6Queen 西洋棋中的皇后可以直线前进,吃掉遇到的所有棋子,如果棋盘上有八个皇后,则这八个皇后如何相安无事的放置在棋盘上? Java代码 publicclassQueen{ //同位置是否有皇后,1表示有 privateint[]column; //右上至左下是否有皇后 privateint[]rup; //左上至右下是否有皇后 privateint[]lup; //解答 privateint[]queen; //解答编号 privateintnum; publicQueen(){ column=newint[8+1]; rup=newint[2*8+1]; lup=newint[2*8+1]; for(inti=1;i<=8;i++) column[i]=1; for(inti=1;i<=2*8;i++) rup[i]=lup[i]=1; queen=newint[8+1]; } publicvoidbacktrack(inti){ if(i>8){ showAnswer(); }else{ for(intj=1;j<=8;j++){ if(column[j]==1&&rup[i+j]==1&&lup[i-j+8]==1){ queen[i]=j; //设定为占用 column[j]=rup[i+j]=lup[i-j+8]=0; backtrack(i+1); column[j]=rup[i+j]=lup[i-j+8]=1; } } } } protectedvoidshowAnswer(){ num++; System.out.println("\n解答"+num); for(inty=1;y<=8;y++){ for(intx=1;x<=8;x++){ if(queen[y]==x){ System.out.print("Q"); }else{ System.out.print("."); } } System.out.println(); } } publicstaticvoidmain(String[]args){ Queenqueen=newQueen(); queen.backtrack (1); } } 7Coins 现在有八枚银币abcdefg,已知其中一枚是假币,其重量不同于真币,但不知道是轻还是重,如何用天平以最小的比较次数决定出那个是假币,并得知假币是比真币轻还是重。 Java代码 publicclassCoins{ privateint[]coins; publicCoins(){ coins=newint[8]; for(inti=0;i<8;i++) coins[i]=10; } publicvoidsetFake(intweight){ coins[(int)(Math.random()*7)]=weight; } publicvoidfake(){ if(coins[0]+coins[1]+coins[2]==coins[3]+coins[4]+coins[5]){ if(coins[6]>coins[7]) compare(6,7,0); else compare(7,6,0); }elseif(coins[0]+coins[1]+coins[2]>coins[3]+coins[4] +coins[5]){ if(coins[0]+coins[3]==coins[1]+coins[4]) compare(2,5,0); elseif(coins[0]+coins[3]>coins[1]+coins[4]) compare(0,4,1); if(coins[0]+coins[3] compare(1,3,0); }elseif(coins[0]+coins[1]+coins[2] +coins[5]){ if(coins[0]+coins[3]==coins[1]+coins[4]) compare(5,2,0); elseif(coins[0]+coins[3]>coins[1]+coins[4]) compare(3,1,0); if(coins[0]+coins[3] compare(4,0,1); } } protectedvoidcompare(inti,intj,intk){ if(coins[i]>coins[k]) System.out.print("\n假币"+(i+1)+"较重"); else System.out.print("\n假币"+(j+1)+"较轻"); } publicstaticvoidmain(String[]args){ if(args.length==0){ System.out.println("输入假币重量(比10大或小)"); System.out.println("ex.javaCoins5"); return; } CoinseightCoins=newCoins(); eightCoins.setFake(Integer.parseInt(args[0])); eightCoins.fake(); } } 8Lifegame 生命游戏,为1970年英国数学家J.H.Conway所提出,某一细胞的邻居包括上,下,左,右,左上,左下,右上与右下相邻的细胞,游戏规则如下: 1,孤单死亡: 如果细胞的邻居小于一个,则该细胞在下一个状态死亡。 2,拥挤死亡: 如果细胞的邻居在四个以上,则该细胞在下一个状态死亡。 3,稳定: 如果细胞的邻居为两个或三个,则该细胞在下一个状态稳定。 4,复活: 如果某位置原无细胞存活,而该位置的邻居为三个,则该位置将复活一个细胞。 Java代码 publicclassLifeGame{ privateboolean[][]map; privateboolea
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- java 实现 各种 算法