《六只狼》编程竞赛

工作 2008-12-31 6476 17 368字
- N +

公司里一部分员工刚学完C语言,出个题目给大家做做。

有六只狼,其中三只母狼,每只母狼分别带着一只小狼。
有一条河,六只狼都在河的东岸。
有一条船,也在河的东岸,每次只能载二只狼。每只狼(包括母狼和小狼)都会划船。
如果一只小狼,其母亲不和它在一起,则会被其它母狼吃掉(但不会被其它小狼吃掉)。
问:如何才能把六只狼平安地载到河的西岸?最少需要运多少次才能过河?在最少次数的前提下,共有多少种不同的运载方法?

为公平起见,使用计算机语言不限(C,Shell,Pascal,Basic,SCADE,Esterel等等),递交答案请给出源程序和运行结果。

在今年(2008年12月31日24:00以前)做出来的并把正确答案递交给我的发特别年终奖哦!
在2009年1月4日24:00以前做出来把答案递交给我的,我选二个最佳程序公布,并给特别鼓励奖!

大家加油啊!

分享到您的社交平台:

评论: 17 条 访客:16 条, 博主:0 条 查看引用: 1

  • louie    1楼 回复

    搬个板凳 看着。。。

  • ywang    2楼 回复

    现在已经2009年了,我要发的年终奖省下来了,呵呵!

    昨天有些同事请假,不知道情况,这是导致我把钱省下来的主要原因。考虑到请假的人在元旦三天假期里也可能不会做这个题目,我把鼓励奖的时间往后延迟了一天,到2009年1月4日。

    大家加油啊!

  • ywang    3楼 回复

    元旦假日快结束了,竞赛还有一天时间。大家加油啊。

    已经让我省了“特别年终奖”,别再让我省“特别鼓励奖”啊!

  • ywang    4楼 回复

    顺便告诉大家,我自己对这个问题的求解写过C语言程序,除去打印等代码,核心的求解程序只有50行C语句,其中还包括空行,和单独成行的{及}。

    本人的程序和鼓励奖的程序在竞赛结束后一起给大家公布吧。

    同事们一定要加油啊!

  • vincent    5楼 回复

    答案:最少需要11次才能过河,对应的运载方法为486个。
    实现:TCL脚本,没有优化,30秒左右算完,代码量太大(加上注释、结果处理、输出等共有160多行 [face08] ),贴不上来,附一个解:
    1 2 3 4 5 6 => 5 6 => {}
    1 2 3 4 <= 6 <= 5 6
    1 2 3 4 6 => 4 6 => 5
    1 2 3 <= 6 <= 4 5 6
    1 2 3 6 => 1 2 => 4 5
    3 6 <= 2 5 <= 1 2 4 5
    2 3 5 6 => 2 3 => 1 4
    5 6 <= 4 <= 1 2 3 4
    4 5 6 => 5 6 => 1 2 3
    4 <= 6 <= 1 2 3 5 6
    4 6 => 4 6 => 1 2 3 5

  • ywang    6楼 回复

    先赞一个[face41],口头鼓励一下。

    正式的“特别鼓励奖”明天再来颁发吧。

  • louie    7楼 回复

    抄了别人的答案 大家可以看看 shell写的 嘿嘿
    其中A a B b C c表示6只老虎,大写字母是大老虎,小写字母是小老虎。附上几个答案 代码大 发给老板让他审批下。
    Aa–> A<– bc–> a<– BC–> Bb<– AB–> c<– ab–> a<– ac–>

    Aa–> A<– bc–> a<– BC–> Bb<– AB–> c<– ab–> b<– bc–>

    Aa–> A<– bc–> a<– BC–> Bb<– AB–> c<– ab–> C<– Cc–>

    Aa–> A<– bc–> a<– BC–> Bb<– AB–> c<– ac–> a<– ab–>

  • louie    8楼 回复

    老大 牛啊
    才30秒运行时间
    shell跑半天要 总数貌似一样的 是486种方案。

  • ywang    9楼 回复

    怎么我的狼变成你的老虎了?

  • louie    10楼 回复

    抄别人的答案 就是这样的 [face03]

  • xiagaoming    11楼 回复

    今天休假刚回来,早上一来就看到老板的题目。
    刚开始看简单,后来越看越难啊。。。

    奋斗了一晚上,先公布一下我的答案:
    最少需要运9次才能过河;
    在最少次数的前提下,共有54种不同的运载方法。

    不知道对不对?请指教啊。[face05]

  • ywang    12楼 回复

    你仔细检查一下你的过河方案,然后把你的程序和运行结果给我发email过来吧。

  • xiagaoming    13楼 回复

    更正一下我的结果,应该有243种不同的运载方法。[face08]

  • xiagaoming    14楼 回复

    摘选我的一条结果:

    –>[1,4]<–[1]–>[2,5]<–[2]–>[3,6]<–[3]–>[1,2]<–[6]–>[3,6]

    123:母狼
    456:小狼

  • xiagaoming    15楼 回复

    惭愧啊,惭愧。[face08]

    我犯了2个错误。先少考虑了一个条件,就是船回来时是可以带两只狼回来的。然后就是母狼到右岸放小狼直接开船回去不会吃右还没有保护的小狼,这个也是不对的。

    而我说没有解,就是因为没有考虑到可以两只狼回来!!!

  • edwin123_chen    16楼 回复

    哈,刚刚从家里回来,看到这么一个有意思的题目。
    一直想用SCADE来实现这个题目,不过发现很难呀。。。
    王博,请教一下,要实现这个命题,用我们SCADE IDE可以的吧?

发表评论:

请输入您的昵称!(必填)

正确格式为:http://yunmingwang.cn/blog(选填)