螞蟻過桿問題
來源：程序員人生 發布時間：2015-04-28 08:21:17 閱讀次數：2882次
問題：有1根27厘米的細木桿，在第3厘米、7厘米、11厘米、18厘米、23厘米這5個位置上各有1只螞蟻。木桿很細，不能同時通過兩只螞蟻。開始時，螞蟻的頭朝左還是朝右是任意的，它們只會朝前走或調頭，但不會后退。當任意兩只螞蟻碰頭時，兩只螞蟻會同時調頭朝反方向走。假定螞蟻們每秒鐘可以走1厘米的距離。編寫程序，求所有螞蟻都離開木桿的最小時間和最大時間。
思路：由于沒有告知螞蟻的初始朝向，所以要對初始化螞蟻朝向。用0表示朝左，1表示朝右，用2進制00000（0）表示5只螞蟻都是朝向左，然后每次加1，直到加到11111（31）時，表示5只螞蟻初始的所有朝向。讓后隨時間的推移，有些螞蟻可能碰頭，這是就的對螞蟻的朝向就行修改，即：如原來朝向為0，則變成1，原來為1的變成0,。做到這里就會想到如何判斷螞蟻朝向問題，這個可以通過異或來解決問題。如：當要判斷第1只螞蟻朝向時，可以用2進制10000(16)與原來朝向異或，若結果為0，則表示朝向為1，朝右，否則相反；用2進制01000(8)與原來朝向異或，可以判斷第2個螞蟻的朝向，以此類推。
代碼實現：
import java.util.*;
public class Ant{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
System.out.println("輸入5只螞蟻的位置(厘米）（大于0小于27且不能有相同的）：");
while(sc.hasNext()){
int[] q=new int[5];//{3,7,11,18,23};輸入5只螞蟻的初始位置
for(int b=0;b<q.length;b++){
q[b]=sc.nextInt();
}
int maxtime=⑴,mintime=10000,signmax=0,signmin=0;
for(int num=0;num<=31;num++){//5只螞蟻初始的朝向
int i=num;//1種初始朝向后，直到所有螞蟻掉下的進程中中途朝向的變化
int[] p=new int[5];//{3,7,11,18,23};
for(int b=0;b<p.length;b++){//保存q[]的初值
p[b]=q[b];
}
int sum=0;//所有螞蟻掉下去的時間
while(1>0){
if(f(p)==p.length){//直到5只螞蟻都掉下去時，退出循環，進行下1種5只螞蟻初始朝向的計算
break;
}
sum++;
for(int j=0;j<p.length;j++){//通過判斷朝向 對位置進行加減
int k=(int)Math.pow(2,j);
if((i&k)==0){
p[j]-=1;
}else{
p[j]+=1;
}
}
for(int j=0;j<p.length⑴;j++){//判斷有無碰頭 然后重新記錄5只螞蟻的朝向
if(p[j]==p[j+1]){
int k=(int)Math.pow(2,j);
if((i&k)==0){
i-=k;
}else{
i+=k;
}
}
}
}
if(sum>maxtime){
maxtime=sum;signmax=num;
}
if(sum<mintime){
mintime=sum;signmin=num;
}
//System.out.print(sum+" ");
}
System.out.println("maxtime= "+maxtime+" 秒 ");
System.out.println("mintime= "+mintime+" 秒
");
System.out.println("輸入5只螞蟻的位置(厘米）（大于0小于27且不能有相同的）：");
}
}
public static int f(int a[]){//記錄螞蟻掉下去的個數
int k=0;
for(int i=0;i<a.length;i++){
if(a[i]>=27||a[i]<=0){
k++;
}
}
return k;
}
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
