签到领奖

[每日活动] 又到周三小测试 —— 蚂蚁走木杆

  [复制链接]
查看: 8895|回复: 73
6风尘奇侠
2975/3000
排名
13
昨日变化
发表于 2017-1-11 14:49:37 | 显示全部楼层 |阅读模式
欢迎大家参与我们的“每周活动”

原谅我把每日活动做成了每周活动。。。_(:з」∠)_

大家平时就转转幸运转盘消遣一下吧~

DSC0000.gif

又见周三,小测试再开!
我们今天的话题是这个蚂蚁走木杆

有一根27厘米长的细木杆,在第3厘米,7厘米,11厘米,17厘米,23厘米这五个位置上各有一只蚂蚁,木杆很细,不能同时通过两只蚂蚁,开始时,蚂蚁的头朝向左还是右是任意的,他们只会朝前走或掉头,但不会后退,当两只蚂蚁相遇后,蚂蚁会同时掉头朝反方向走,假设蚂蚁们每秒钟可以走1厘米的距离. 求所有蚂蚁都离开木杆的最小时间和最大时间。

这其实是一道算法题,不用写代码,说说思路 & 最后的答案就好

又到周三小测试 —— 蚂蚁走木杆

又到周三小测试 —— 蚂蚁走木杆

回帖即得10泰斗币(50个名额)~
题目答案将在活动结束后公布~
答得靠谱的加20泰斗币~

又到周三小测试 —— 蚂蚁走木杆

又到周三小测试 —— 蚂蚁走木杆

对不起大家,这个坑忘记填了,公布答案!
问题分析:
1.最小时间肯定是各自朝最近的一端跑,27-11=14,11<14,所以中间的蚂蚁会朝11cm那端跑,最适时短时间11。
2. 最长时间呢,肯定两端的蚂蚁都往中间跑,具体怎么跑好像有点儿想不清楚,那试算之,假设3cm处的和7cm处的相对而行,碰面后会怎样?如果你眼神不好, 你会发现你分不出来哪个是哪个,因为3cm的转头后就相当于7cm的一直在走。到这里,一切就已经没有刚开始那样想不清楚了,事情很清楚:蚂蚁碰头可以用 等量代换的思想,在这种情况下,任何蚂蚁都是自由地向它面向的一端直接爬过去。那最长时间就清楚了:27-3=24,27-23=4 24>23,所以最长时间是24。 有了以上分析,算法就简单了。
算法:
1.找出中间的蚂蚁离两端的距离中较小的。 a[2]=11
a[2]''=27-11=14,
因为a[2]<a[2]'',所以最小距离是11,时间11/1=11
2.找出两端的蚂蚁距两端的距离中较大的。 a[0]=3
a[0]''=27-3=24 a[4]=23
a[4]''=27-23=4
这四个数中最大的是24
3.所以,最大时间24,最小时间11 程序:
1. public class Ant {   
2.   
3.     private static int LONG = 27;   
4.   
5.     private int[] a = { 3, 7, 11, 17, 23 };   
6.   
7.     private int min = 0, max = 0;   
8.   
9.     public void gogogo() {   
10.         for (int i = 0; i < a.length; i++) {   
11.              min = Math.max(min, Math.min(a, LONG - a));   
12.              max = Math.max(max, Math.max(a, LONG - a));   
13.          }   
14.      }   
15.   
16.     public int getMax() {   
17.         return max;   
18.      }   
19.   
20.     public int getMin() {   
21.         return min;   
22.      }   
23.   
24.     public static void main(String[] args) {   
25.   
26.          Ant client = new Ant();   
27.          client.gogogo();   
28.          System.out.println(client.getMax());   
29.          System.out.println(client.getMin());   
30.      }   
31. }  

+1
3036°C
70
  • 年少不懂事
  • frankwswswws
  • frankwswswws
  • Wahh_1314
  • frankwswswws
过: 他们
最近访问 头像模式 列表模式
3江湖小虾
295/500
排名
68
昨日变化
1
发表于 2017-1-11 15:56:33 | 显示全部楼层

回帖奖励 +10

3厘米,7厘米,11厘米 走一边 17厘米,23厘米走一边 最小是11秒     “灵魂算法”即是指当两只蚂蚁碰面后,理论上它们应该立即掉头反向而行,但此时我们可以认为它们是可以穿过对方的“灵魂”,碰面之后仍会坚持原来的方向行走.(要知道,对我们来说题目中两只蚂蚁并没有什么不同之处,这是算法思想的关键,理解了这里我想接下来计算最大时间就不成问题了).既然蚂蚁可以穿越对方而行走,那么用时最长的就是行走路线最长的那只蚂蚁喽,回头看看情景中给出条件,即可得出结果:
第一只:27-3=24/1=24(s)
第二只:27-7=20/1=20(s)
第三只:27-11=16/1=16(s)
第四只:17-0=10/1=17(s)
第五只:23-0=23/1=23(s)
最长时间为24s
[发帖际遇]: 年少不懂事 发帖时在路边捡到 4 泰斗币,偷偷放进了口袋. 幸运榜 / 衰神榜
回复 支持 1 反对 0

使用道具 举报

3江湖小虾
308/500
排名
124
昨日变化
发表于 2017-1-11 15:56:09 | 显示全部楼层
综上所述最小时间11秒,最大时间24秒,口算的,不知道对不?
回复 支持 1 反对 0

使用道具 举报

3江湖小虾
308/500
排名
124
昨日变化
发表于 2017-1-11 15:41:43 | 显示全部楼层

回帖奖励 +10

最小时间 3 7 11向0走,11秒,17和23向27走,10秒,所以最小时间是11秒.
排名
156
昨日变化
2
发表于 2017-1-11 15:46:16 | 显示全部楼层

回帖奖励 +10

本帖最后由 Wahh_1314 于 2017-1-11 16:54 编辑

每周都看测试,以前的都是逻辑题目。一直没答,这次是算法题目,我就参与一下吧

这个题目问题是:整个木杆的蚂蚁都走完了,需要的最小时间和最大时间。

首先我们知道这个题目对于蚂蚁来说是无差别的,也就是我们不在意哪个蚂蚁的具体时间、具体路径。
既然抓住这个要点我们就可以解决这个问题的最大难点,也就是碰头。碰头之后蚂蚁会相互往相反的方向。既然蚂蚁无差别,我们可以把蚂蚁都看作一个点。那么从运动路径上我们可以把问题等效为碰头之后继续往前走。那么所有蚂蚁的运动都是独立的。也就是说,整个最小时间就是每个蚂蚁走直线(无返回)的走完木杆的最小时间的最大值。整个最大时间就是每个蚂蚁走直线(无返回)的走完木杆的最大时间的最大值。

代码如下(C++):
[AppleScript] 纯文本查看 复制代码
#include <iostream>
using namespace std;
int tot_length;
int ant_num;
int* ant_pos;
int main()
{
    cout << "请输入细木杆长度:" << endl;
    cin >> tot_length;
    cout << "请输入蚂蚁个数:" << endl;
    cin >> ant_num;
    ant_pos = new int[ant_num];
    cout << "请输入蚂蚁位置:" << endl;
    for(int i = 0 ; i < ant_num ; i ++)
        cin >> ant_pos;
    int min_time = 0;
    int max_time = 0;
    for(int i = 0 ; i < ant_num ; i ++){
        int t1 = ant_pos;
        int t2 = tot_length - ant_pos;
        if(t1 > t2) t1^=t2^=t1^=t2;
        if(min_time < t1) min_time = t1;
        if(max_time < t2) max_time = t2;
    }
    cout << "最大时间: " << max_time << endl;
    cout << "最小时间: " << min_time << endl;
    delete[] ant_pos;
    return 0;
}


snipaste20170111_152242.png
什么是有差别的呢?

如果这个题目的问题这样改:求第三个蚂蚁(11位置)离开木杆的最大时间和最小时间。

如果题目这样问,蚂蚁就不是无差别的了,那么碰头问题就不能像如上那样等效。这样问题应该如何解决?

我们尝试化简问题为子问题:

我们知道一个蚂蚁要离开无非是从左边离开或者是右边离开,而从左(右)离开的前提就是它自己左(右)部分的蚂蚁都已经离开了。


那么我们令 TMAX(3)为3号蚂蚁离开木杆的最长时间。TLMAX(3) 为3号蚂蚁从左边离开木杆的最长时间。 TRMAX(3) 为3号蚂蚁从右边离开木杆的最长时间
TMIN(3)为3号蚂蚁离开木杆的最短时间。TLMIN(3) 为3号蚂蚁从左边离开木杆的最短时间。 TRMIN(3) 为3号蚂蚁从右边离开木杆的最短时间
那么
TMAX(3) = max(TLMAX(3),TRMAX(3))。
TMIN(3) = min(TLMIN(3),TRMIN(3))。

既然 我们知道一个蚂蚁要离开无非是从左边离开或者是右边离开,而从左(右)离开的前提就是它自己左(右)部分的蚂蚁都已经离开了。

那么上面的TMAX(3),TMIN(3)可以通过如下公式得到:

TMIN(3) = min(TLMIN(1)+TLMIN(2)+ pos[3] - pos[2],TRMIN(4)+TRMIN(5) + pos[4] - pos[3])
TMAX(3) = max(TLMAX(1)+TLMAX(2)+ pos[3] - pos[2],TRMAX(4)+TRMAX(5)+ pos[4] - pos[3])

可以看出来这是一个递归:

递归出口是什么呢?很简单:

TLMIN(1) = pos[1]
TLMAX(1) = pos[5]   (这里为什么是pos[5]。请看无差别问题)

TRMIN(5) = tot_length - pos[5]   (tot_length 为木杆长度)
TRMAX(5) = tot_length - pos[1]

既然递归关系有了,递归出口有了,那么就可以求解了。


这是关于蚂蚁木杆两类问题的思考方案。


点评

大神分析的很透彻,谢谢分享  发表于 2017-1-12 11:02
大神分析的很透彻,谢谢分享  发表于 2017-1-12 11:01
[发帖际遇]: Wahh_1314 向上天求妹纸,神仙看了看你 ,甩8 泰斗币给你说道,快打车去棒子国. 幸运榜 / 衰神榜
3江湖小虾
308/500
排名
124
昨日变化
发表于 2017-1-11 15:54:07 | 显示全部楼层
最大时间3(右) 7(右) 11(右)向27走,17(左)和23(左)向0走
第1次碰撞:11碰17要3秒 ,此时3在6(右),7在10(右),11在14(左),17在14(右),23在20(左)
第2次碰撞:10碰14要2秒 ,此时6在8(右),10在12(左),14在12(右),14在16(右),20在18(左)
第3次碰撞:16碰18要1秒 ,此时8在9(右),12在10(左),12在14(右),16在18(左),20在18(右)
第4次碰撞:9碰10要0.5秒,此时9在9.5(左),10在9.5(右),14在14.5(右),18在17.5(左),18在18.5(右)
第5次碰撞:14.5碰17.5要1.5秒,此时9.5在8(左),9.5在11(右),14.5在16(左),17.5在16(右),18.5在20(右)
最后碰撞:11碰16要2.5秒,此时8在5.5(左),11在13.5(左),16在13.5(右),16在18.5(右),20在22.5(右)
最中心的是13.5(左)要13.5秒出去,13.5(右)要13.5秒出去

最大时间3+2+1+0.5+1.5+2.5+13.5=24
[发帖际遇]: frankwswswws 乐于助人,奖励 4 泰斗币. 幸运榜 / 衰神榜
3江湖小虾
308/500
排名
124
昨日变化
发表于 2017-1-11 15:58:41 | 显示全部楼层
不过为什么每周活动只剩下周三的活动了?而且每天回帖有奖也降到5元奖励了......抽奖如果转到边界线算7等奖......

点评

TUT 因为年底事多,对不起你们 _(:з」∠)_ 至于抽奖的BUG 我真心整不了。。。  发表于 2017-1-11 18:08
4后起之秀
524/1000
排名
99
昨日变化
发表于 2017-1-11 17:08:23 | 显示全部楼层

回帖奖励 +10

最小时间按每个蚂蚁距离最近的出口走,很容易看出是11秒,关键是求最大时间,最大时间可以理解为朝最远的出口走,最大时间为24秒
3江湖小虾
319/500
排名
202
昨日变化
2
发表于 2017-1-11 17:20:55 | 显示全部楼层

回帖奖励 +10

啥也不说了,泰课就是给力!
3江湖小虾
319/500
排名
202
昨日变化
2
发表于 2017-1-11 17:21:40 | 显示全部楼层
啥也不说了,泰课就是给力!
[发帖际遇]: husheng 发帖时在路边捡到 4 泰斗币,偷偷放进了口袋. 幸运榜 / 衰神榜
发表于 2017-1-11 17:57:20 | 显示全部楼层

回帖奖励 +10

jhgjghj ghjghjghj ghjhgjghjghj ghjhgj hgjhgjhgj hgj gh jhgj
3江湖小虾
209/500
排名
191
昨日变化
2
发表于 2017-1-11 18:28:11 | 显示全部楼层

回帖奖励 +10

最短11 最长24 最长的走法有很多种都是24
3江湖小虾
282/500
排名
116
昨日变化
发表于 2017-1-11 18:51:50 | 显示全部楼层

回帖奖励 +10

啥也不说了,泰课就是给力!
5武林高手
1023/2000
排名
16
昨日变化
发表于 2017-1-11 19:28:17 | 显示全部楼层

回帖奖励 +10

啥也不说了,泰课就是给力!
3江湖小虾
209/500
排名
195
昨日变化
2
发表于 2017-1-11 20:46:23 | 显示全部楼层

回帖奖励 +10

综上所述最小时间11秒,最大时间24秒
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

站长推荐上一条 /3 下一条

在线客服(工作时间:9:00-22:00)
010-82609395
泰斗社区公众号

Copyright   ©2015-2016  【泰斗社区】-专注互联网游戏和应用的开发者平台  Powered by©Discuz!  技术支持:迪恩网络     ( 沪ICP备14023207号-9 )