Chinaunix首页 | 论坛 | 博客
  • 博客访问: 322787
  • 博文数量: 69
  • 博客积分: 2090
  • 博客等级: 大尉
  • 技术积分: 708
  • 用 户 组: 普通用户
  • 注册时间: 2008-09-23 09:31
文章分类

全部博文(69)

文章存档

2012年(1)

2011年(4)

2010年(48)

2009年(14)

2008年(2)

我的朋友

分类: C/C++

2010-09-21 21:21:49

这个问题来自编程之美这本书。

问题:有一根27厘米的木杆,在第3厘米,7厘米,11厘米,17厘米,23厘米这五个位置上各有一蚂蚁。木杆很细,不能同时通过两个蚂蚁。开始的时候每个蚂蚁的头朝哪边是不确定的,它们只会朝前走或者掉头,但是不会后退。当任意两只蚂蚁碰头的时候,两只蚂蚁会同时调头向相反的方向走。假设蚂蚁们每秒可以走一厘米的距离。编写程序,求所有蚂蚁都离开木杆的最短时间和最长时间‘

解法一:这也许是大多人会想到的方法(哈哈,我刚开始的时候也这样想的)
考虑枚举蚂蚁的初始朝向,模拟每一个蚂蚁的运动来解决问题。

解法二:
考虑,虽然两只蚂蚁碰头后都掉头往相反的方向,但是,可以看作是是两只蚂蚁相遇后,擦肩而过了(看到这里的时候可能很多人就有一种恍然大悟的感觉了吧)。也就是说可以认为蚂蚁的运动独立的,是否有碰头并不是问题的中重点。

这样虽然每个蚂蚁的运动轨迹都与原来的不一样了。但是所有的蚂蚁离开木杆的最短的时间和最长时间是不变的。只需要分别计算每个蚂蚁离开木杆的时间,即可求出所有蚂蚁离开木杆的时间了。

这样,程序只需要遍历所有的蚂蚁,把每个蚂蚁走出木杆的最长时间(蚂蚁朝离自己较远的一端走去),最短时间(蚂蚁朝离自己较近的一端走去)分别求出来,就算出最大值,这两个最大值就是所有蚂蚁离开木杆的最长时间和最短时间。





void get_time(
            int length, //木杆的长度

            int pos[], //开始时候每个蚂蚁的位置

             int ant_num, //蚂蚁的速度

            int speed, //蚂蚁爬行的速度

            int *max, //最长时间

            int *min //最短时间

            )
{
    *max = 0;
    *min = 0;
   
    int current_max = 0;
    int current_min = 0;
    int i;
    for (i = 0;i < ant_num;i++)
    {
        current_max = 0;
        current_min = 0;
   
        if (pos[i] < length / 2)
        {
            current_max = (length - pos[i]) / speed;
            current_min = pos[i] / speed;
        }

        else
        {
            current_max = pos[i] / speed;
            current_min = (length - pos[i]) / speed;
        }
   

        if (*max < current_max)
            *max = current_max;
        if (*min < current_min)
            *min = current_min;
   
       
    }
}



扩展问题:
1、第i个蚂蚁什么时间走出木杆。
2、蚂蚁一共碰了多少此头

阅读(6829) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~