用java实现的各种算法.docx

用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