蚂蚁过杆问题

 问题:有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;
}
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 蚂蚁过杆问题

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡