之前看有的朋友谈百度的一道面试试题－
蚂蚁问题（有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间）。关于这道题目，网上给出了很多的解释，但从整体来看，基本都是用到了等价置换（等量代换）的思想。要求最小时间，即为“最不容易”先到达两端的蚂蚁以最短的时间到达，所以我们只需找到所有蚂蚁中间的一只（共奇数只蚂蚁）或两只（共偶数只蚂蚁）到达一端的最短时间。比较麻烦的是求最长时间，有人会觉得当有很多只蚂蚁时，中间的蚂蚁们相互碰撞的次数多些会增加时间，感觉上比较复杂，可如果我们用等量代换的思想来解释就比较容易。假设中间的任意两只相邻蚂蚁即将发生碰撞，如：A －> <－B，当A，B发生碰撞后，便有<－A B－>。A，B反向相当于<－B A －> ，即二者继续向着原来的方向前进，对于任意相邻的发生碰撞的蚂蚁都适用，所以只需求最两端的两只蚂蚁距离两端的最远距离。由以上分析可知，如果出这样的问题，我们可以不用通过程序便能说出结果：5个点，中间蚂蚁的位置为11，即0－11－27，显然最小为11，最两端蚂蚁，0－3－27，最大为24，0－23－27，最大为23，所以最大为24。对于这个题，给出如下Java代码（随便写了几句，不符合面向对象思想）。
public class Ant 
{
public static void main(String[] args){
int length=27,points=5,min=0,max=0,temp_min=0,temp_max=0;
int[] pos={3,7,11,17,23};
for(int i: pos){
temp_min=i>length-i?length-i:i;
temp_max=i<length-i?length-i:i;
if(temp_min>min)
min=temp_min;
if(temp_max>max)
max=temp_max;
}
System.out.println("最短时间:"+min+" 最长时间:"+max);
}
}
有了如上的想法，我们能做出判断，为什么还要写代码呢？其实这个问题出自Waterloo Local Contest Sep.19,2004 准确描述如下：
An army of ants walk on a horizontal pole of length l cm, each with a constant speed of 1 cm/s. When a walking ant reaches an end of the pole, it immediatelly falls off it. When two ants meet they turn back and start walking in opposite directions. We know the original positions of ants on the pole, unfortunately, we do not know the directions in which the ants are walking. Your task is to compute the earliest and the latest possible times needed for all ants to fall off the pole.
The first line of input contains one integer giving the number of cases that follow. The data for each case start with two integer numbers: the length of the pole (in cm) and n, the number of ants residing on the pole. These two numbers are followed by n integers giving the position of each ant on the pole as the distance measured from the left end of the pole, in no particular order. All input integers are not bigger than 1000000 and they are separated by whitespace.
For each case of input, output two numbers separated by a single space. The first number is the earliest possible time when all ants fall off the pole (if the directions of their walks are chosen appropriately) and the second number is the latest possible such time.
Sample Input
2
10 3
2 6 7
214 7
11 12 7 13 176 23 191
Sample Output
4 8
38 207
在这里给出相应的c++代码：
#include<iostream>
using namespace std;
int main()
{
int cases,l,n,min,max,temp_min,temp_max,pos;
cin>>cases;
while(cases--)
{
cin>>l>>n;
min=0;
max=0;
while(n--)
{
cin>>pos;
temp_min=pos>l-pos?l-pos:pos;
temp_max=pos<l-pos?l-pos:pos;
if(temp_min>min)
min=temp_min;
if(temp_max>max)
max=temp_max;
}
cout<<min<<' '<<max<<endl;
}
return 0;
}
posted on 2008-05-10 11:28
dreamingnest 阅读(936)
评论(7) 编辑 收藏 所属分类:
应用程序