| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 544 人关注过本帖
标题:[讨论]在网上看到一个题目,挺好玩,欢迎来看看,呵呵
只看楼主 加入收藏
孤风的边缘
Rank: 1
等 级:新手上路
威 望:2
帖 子:66
专家分:0
注 册:2006-11-19
收藏
 问题点数:0 回复次数:4 
[讨论]在网上看到一个题目,挺好玩,欢迎来看看,呵呵
有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细,不能同时通过一只蚂蚁。开始时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。


似乎是某公司面试题~~偶用穷举法实现了一下~~但是这个肯定考的不是穷举法,应该有优化的多的算法~有兴趣且有时间的朋友可以做着玩玩~~

PS:没时间的话如果有好的算法也可以说出来分享一下~HOHO~
搜索更多相关主题的帖子: 欢迎 
2006-11-19 20:25
孤风的边缘
Rank: 1
等 级:新手上路
威 望:2
帖 子:66
专家分:0
注 册:2006-11-19
收藏
得分:0 

发一下偶的巨土的穷举法实现~~
package com.gufengdebianyuan;
import java.util.*;
import java.lang.*;

/*
* 该类的主要作用是模拟蚂蚁的各种属性
*/
public class Mayi {

//构造函数
public Mayi(String para,int coordinate){
this.coordinate = coordinate;

sum = 0;

state = true;

if(para.equals("0")){
direction = -1;
}
else
{
direction = 1;
}
}

//方向
public int direction;

//走动量
public int sum;

//当前坐标
public int coordinate;

//状态(是已落杆还是行进中)
public boolean state;

//判断蚂蚁是否已经落杆
public void judge()
{
if(coordinate<=0||coordinate>=27)
{
state = false;
}
}

//模拟蚂蚁走路的步骤
public void go()
{
if(state){
coordinate = coordinate + direction;
sum++;
}
judge();
}

}

/**
* 该类的主要作用是穷举所有可能发生的蚂蚁的初始化状态
*/
public class Step {

//存放所有的初始化状态
public ArrayList list;

//构造函数,初始化链表
public Step()
{
list = new ArrayList();
}

//把每种初始化状态加到链表中
public void addStep(int a,int b,int c,int d,int e){

String tal = String.valueOf(a)+String.valueOf(b)+String.valueOf(c)+
String.valueOf(d)+String.valueOf(e);

list.add(tal);

}

//返回链表的大小
public int size(){
return list.size();
}

//返回指定位置的初始化状态
public Object get(int i){
return list.get(i);
}
}

/**
* 主类,模拟蚂蚁的运动过程,并记录数据进行分析
*/
public class Test {

//存放所有可能出现的初始情况
Step steplist;
int a,b ,c ,d ,e;


public Test(){
a = 0;
b = 0;
c = 0;
d = 0;
e = 0;

steplist = new Step();
}

//把所有的初始情况增加到steplist中
public void add(){

for(int a=0;a<2;a++)
{
for(int b=0;b<2;b++)
{
for(int c=0;c<2;c++)
{
for(int d=0;d<2;d++)
{
for(int e=0;e<2;e++)
{
steplist.addStep(a,b,c,d,e);
}
}
}
}
}

}

//看两只蚂蚁是否碰头,若碰头则进行转向处理
public static void balance(Mayi mayia,Mayi mayib){
if(mayia.coordinate==mayib.coordinate)
{
mayia.direction = (-1)*mayia.direction;
mayib.direction = (-1)*mayib.direction;
}
}

public static void main(String []args)
{
Test test = new Test();
test.add();

//用向量存放每种情况的最后一只蚂蚁爬下杆子时的步数
Vector total = new Vector();


Mayi mayi1,mayi2,mayi3,mayi4,mayi5;

//循环每一种初始化状态
for(int i=0;i<test.steplist.size();i++)
{
//取当前的五个蚂蚁的初始化状态
String tempTest = (String)test.steplist.get(i);

mayi1 = new Mayi(tempTest.substring(0,1),3);

mayi2 = new Mayi(tempTest.substring(1,2),7);

mayi3 = new Mayi(tempTest.substring(2,3),11);

mayi4 = new Mayi(tempTest.substring(3,4),17);

mayi5 = new Mayi(tempTest.substring(4,5),23);


while(mayi1.state||mayi2.state||mayi3.state||mayi4.state||mayi5.state)
//判断是否所有的蚂蚁都已下杆,若不是则继续循环
{

//蚂蚁开始行走
mayi1.go();
mayi2.go();
mayi3.go();
mayi4.go();
mayi5.go();

//判断蚂蚁是否有碰头
Test.balance(mayi1,mayi2);
Test.balance(mayi2,mayi3);
Test.balance(mayi3,mayi4);
Test.balance(mayi4,mayi5);

}

int []temp = new int[]{mayi1.sum,mayi2.sum,mayi3.sum,mayi4.sum,mayi5.sum};

//为当前次每个蚂蚁行走的步数排序
Arrays.sort(temp);

total.add(String.valueOf(temp[4]));
}

//为每次的最大步数组成的链表排序
Collections.sort(total);

System.out.println("蚂蚁爬出杆子的最短时间为:"+total.elementAt(0)+"秒;");

System.out.println("蚂蚁爬出杆子的最长时间为:"+total.lastElement()+"秒。");


}

}

[此贴子已经被作者于2006-11-19 20:27:17编辑过]


把爱留给爱你的人。。。。
2006-11-19 20:26
千里冰封
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:灌水之王
等 级:版主
威 望:155
帖 子:28477
专家分:59
注 册:2006-2-26
收藏
得分:0 
呵呵,在CSDN上看到的吧

可惜不是你,陪我到最后
2006-11-19 20:30
孤风的边缘
Rank: 1
等 级:新手上路
威 望:2
帖 子:66
专家分:0
注 册:2006-11-19
收藏
得分:0 
哈哈,不是,是在一个别的论坛上看到的,但是据说是在CSDN上转的~

把爱留给爱你的人。。。。
2006-11-19 20:31
孤风的边缘
Rank: 1
等 级:新手上路
威 望:2
帖 子:66
专家分:0
注 册:2006-11-19
收藏
得分:0 

去CSDN上看了一下。。。。发现如果用鬼魂算法来解是如此的简单。。。。。还是数学思想不行啊~55555555,谁让偶上大学的时候直接把数学扔了呢~~

把爱留给爱你的人。。。。
2006-11-20 10:18
快速回复:[讨论]在网上看到一个题目,挺好玩,欢迎来看看,呵呵
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017674 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved