蚂蚁过杆问题
来源：程序员人生 发布时间：2015-04-28 08:21:17 阅读次数：2684次
问题：有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;
}
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
