《六只狼》编程竞赛-答案及获奖名单

工作 2009-01-05 6465 13 1845字
- N +
《六只狼》编程竞赛-答案及获奖名单

前言

2008年的最后一天,本人非官方地组织了一次题为《六只狼》的编程竞赛

本来只是为了好玩。却不料几日来,大家反应非常积极。特别是昨天晚上,有些人一直为这个题目熬到深夜。同事们有这么高的热情参与这次竞赛,实在让我感动不已。在此先向所有参赛者表示感谢啦!

我总共收到了6个人的答案。其中一个答案不是用计算机语言实现的,而是用“自然语言”实现的。

评奖

由于除本人以外所有人全部是参赛者,所以评判团就只有我一个人啦!

为了尽可能公正地评奖,我伤透了脑筋。觉得每个人的程序都不错,而且可以说都是沥血之作,光这种热情就该评特等奖。但名额是有限的,总得有个取舍,这实在让我不忍心。

后来转念一想,这也不过是一场民间的非官方组织的活动而已。能够通过活动,调动一下大家的热情,锻练一下大家的思维,观摩一下别人的程序,并且从中学到一些东西,这就达到目的了。至于给谁颁奖,则是次要的事情了。于是,我放下了包袱,再看了一遍大家交给我的程序,结果马上就出来了。希望每一位参赛者也能用同样的心态来看待获奖结果。

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

答案
定义一 解:满足要求把六只狼从东岸运到西岸的运载序列。
定义二 非重现解:在整个运载的过程中,不存在二个相同状态的解。
比如说,在初始状态下ABCabc六只狼全在东岸;把Aa二只狼运到西岸后,BbCc在东,Aa在西;如果这时又把Aa运回东岸,则六只狼全回到了东岸,和初始状态一样了。这是不允许的。

定理一 非重现解不可能无限多个。(证明略)

定义三 最优解:运载步数最少的解
定义四 最长解:运载步数最多的非重现解

定理二 如果这个问题有解,则肯定存在最优解和最长解

对于这个问题,相关的结论如下:

这个问题的非重现解共有19602个。
最优解为11步,共486个。
最长解为23步,共有3456个。

详细求解程序与求解结果见本人提供的参考答案以及其它参赛者递交的答案。

本人提供的参考答案(程序+运行结果)
下载解压后先阅读readme.txt。为提高大家读程序的能力,我故意去掉了所有注释。

特别年终奖
空缺。其原因是2008年12月31日当天有许多人请假了。

特别鼓励奖
(每位获奖者将得到由《说个明白》博客网站赞助的价值为500元的OK卡[face05])

Vincent下载程序点这里,当选原因:
第一个按要求递交的程序和运行结果
程序运行结果正确,不仅给出了所有的最优解,而且给出了所有的非重现解
程序结构清晰易懂

JinsuoMA下载程序点这里,当选原因:
程序运行结果正确,给出了486个最优解
程序结构清晰易懂,没有使用太多的技巧,但实现了要求的功能
程序运行效率较高,15种可运载的方案事先提练了出来

为了勉励大家的热情,鼓励大家以更高的热情参与以后类似的活动,现额外颁布“特别参与奖”

特别参与奖(以精神奖励为主,不能让博主破产了[face08])
Louie,当选原因:
积极参与的热情
第二个递交答案,但没有按要求递交运行结果
用shell程序实现,思路清晰,编程者有较高的shell编程技巧

xiagaoming,当选原因:
熬夜积极参与的热情
按要求递交程序与运行结果
程序结构清晰,但对题目的理解略有偏差,导致运行结果有误(太可惜了)

sxfrick,当选原因:
积极参与的热情
尝试了多种方法,想过用SCADE实现,遇到挫折后又改用C语言

后记
通过这次竞赛,我感触很多。让大家一起去思考一个问题,然后每人把各自思考的东西写成程序,与其它同事交流,这本身就是一件很有意义的事情。另外,我作为一个局外的“组办方”,看到了每个员工对待这个问题的态度,也折射出了员工对待工作、对待生活的态度……有熬夜做题目的,有参阅网络资料,有茶饭不思的,还有vincent同事用TCL做了个程序,拿了奖后意犹未尽又写个C程序,而在一个月以后又写了个SCADE模型的……程序本身让我们有了技术交流的机会,而这种做程序的态度则更是我们学习的榜样。

想看vincent同事写的SCADE模型的请从这里下载。请使用SCADE6.1版打开模型。还没有SCADE的看官们赶快让你公司买一个SCADE吧!

分享到您的社交平台:

评论: 13 条 访客:13 条, 博主:0 条 查看引用: 0

  • louie    1楼 回复

    答案不敢说全看懂了
    因为看懂了一点点就已经一身的汗了 (ORZ)

    首先
    过河的老虎都会排队了 还排得整齐美观
    1000001
    1000010
    1000100
    1001000
    1010000
    1100000
    1000011
    1000101
    1000110
    1011000
    1101000
    1110000
    1001001
    1010010
    1100100
    其次
    老虎们 还知道表简单得来回划
    浪费力气还不产生生产力

    最后
    每个小老虎都知道怎么保护自己
    不论是在两头的岸边 还是在船上

    总结
    被计算机处理过的老虎不是吃不吃人的问题了
    而是能把人给玩了 所以 吓得我一身的汗

    ps:再ORZ下答案

  • vincent    2楼 回复

    这两天晚上被儿子折腾得没法睡觉,给他喂奶时就想了想这个用C语言实现的版本:基本思路与Tcl版本还是一样的,不作任何预处理和分析,“直接用船运”。不过C运行效率很高,大概就一两秒的样子:
    #include <stdio.h>
    #include <string.h>
    #define MAXSTEP 30
    int number = 0;
    int elevennumber = 0;
    //判断即将开始的某次移动是不是重复的移动:重复意味着当前左右两边的状态以及当前等进行的操作方向:船的位置)
    int isrepeated(char *result,char *history,int left2right,int step) {
        int i,j,k;
        for (i=0;i<step;i++) {
            k = 0;
            for(j=0;j<32;j++) {
                if (result[j] == history[j+i*33]) {
                    k++;
                }
            }
            if ((k == 32) && ((left2right && history[i*33+32] == ‘1’) || (!left2right && history[i*33+32] == ‘0’))) {
                return 1;
            }
        }
        return 0;
    }

  • vincent    3楼 回复

    一次发不完 [face08]
    //实现一次移动:检查选中的两只儿狼会不会有问题,以及移动后左、右两边会不会有问题
    int move(char *status,int i,int j,int left2right) {
        char temp[33];
        int from1,from2,to1,to2;
        memcpy(temp,status,sizeof(temp));
        if (left2right) {
            from1 = i * 2;
            from2 = j * 2;
            to1 = (i + 9) * 2;
            to2 = (j + 9) * 2;
        } else {
            from1 = (i + 9) * 2;
            from2 = (j + 9) * 2;
            to1 = i * 2;
            to2 = j * 2;
        }
        //选中的不能为都为空,且不能重复选取(i只能在取0时表示空,其它时候如果为空,表示出现了重复;j位置为空则肯定是重复):返回-1
        if (temp[from2] == ‘-‘ || (temp[from1] == ‘-‘ && i != 0)) {
            return -1;
        }
        //选中的不能出问题:返回-2
        if ((temp[from1] == ‘C’ && temp[from2] == ‘M’ && temp[from1+1] != temp[from2+1]) || (temp[from2] == ‘C’ && temp[from1] == ‘M’ && temp[from2+1] != temp[from1+1])) {
            return -2;
        }

  • vincent    4楼 回复

        //移动
        if (temp[from1] != ‘-‘) {
            temp[to1]     = temp[from1];
            temp[to1+1]   = temp[from1+1];
            temp[from1]   = ‘-‘;
            temp[from1+1] = ‘-‘;
        }
        if (temp[from2] != ‘-‘) {
            temp[to2]     = temp[from2];
            temp[to2+1]   = temp[from2+1];
            temp[from2]   = ‘-‘;
            temp[from2+1] = ‘-‘;
        }
        //左边会不会出问题:小狼的妈妈不在,且有其它母狼(以下三种情况分别对小狼A、B、C被吃掉):返回-3
        if (temp[8] != ‘-‘ && temp[2] == ‘-‘ && (temp[4] != ‘-‘ || temp[6] != ‘-‘)) {
            return -3;
        }
        if (temp[10] != ‘-‘ && temp[4] == ‘-‘ && (temp[2] != ‘-‘ || temp[6] != ‘-‘)) {
            return -3;
        }
        if (temp[12] != ‘-‘ && temp[6] == ‘-‘ && (temp[2] != ‘-‘ || temp[4] != ‘-‘)) {
            return -3;
        }

  • vincent    5楼 回复

        //右边会不会出问题:小狼的妈妈不在,且有其它母狼(以下三种情况分别对小狼A、B、C被吃掉):返回-4
        if (temp[26] != ‘-‘ && temp[20] == ‘-‘ && (temp[22] != ‘-‘ || temp[24] != ‘-‘)) {
            return -4;
        }
        if (temp[28] != ‘-‘ && temp[22] == ‘-‘ && (temp[20] != ‘-‘ || temp[24] != ‘-‘)) {
            return -4;
        }
        if (temp[30] != ‘-‘ && temp[24] == ‘-‘ && (temp[20] != ‘-‘ || temp[22] != ‘-‘)) {
            return -4;
        }
        memcpy(status,temp,sizeof(temp));
        return 0;
    }

  • vincent    6楼 回复

    //递归实现搬运
    int transfer(char *status,char *history,int left2right,int step) {
        char cases[MAXSTEP * 33 + 1];
        char temp[33];
        int i,j;
        for (i=0;i<=6;i++) {
            for (j=i+1;j<=6;j++) {
                //移动,如果失败了就跳过去
                memcpy(temp,status,sizeof(temp));
                if (move(temp,i,j,left2right) != 0) {
                    continue;
                }
                //将当前状态作为历史状态记录下来
                memcpy(cases, history, step * 33);
                memcpy(cases + step * 33, temp, 32);
                if (left2right) {
                    cases[step * 33 + 32] = ‘0’;
                } else {
                    cases[step * 33 + 32] = ‘1’;
                }
                //检查是否结束
                if (strcmp(temp,”——————–MAMBMCCACBCC”) == 0) {
                    number++;
                    if (step == 11) {
                        elevennumber++;
                        //可以在这里打印搬运步骤:0~step : cases
                    }
                    continue;
                } else {
                    //否则,换个方向接着搬:先判断这种状态是否已经存在过
                    if(isrepeated(temp,history,!left2right,step-1)) {
                        //如果该状态已处理过,结束
                        continue;
                    }
                    transfer(temp,cases,!left2right,step+1);
                }
            }
        }
        return 0;
    }

  • vincent    7楼 回复

    int main() {
        char cases[MAXSTEP * 33 + 1], status[33];
        strcpy(status,”–MAMBMCCACBCC——————”);
        memcpy(cases,status,32);
        cases[32] = ‘1’;
        printf(“go…
    “);
        transfer(status,cases,1,1);
        printf(“Total solutions: %d and 11-step solutions: %d
    “,number,elevennumber);
        return 0;
    }

  • vincent    8楼 回复

    如果想减少代码量,可以用一个整数来代表状态,用不同位的0或1值表示狼是否存在。同时大量用位运算,速度快且代码量小,不过可读性较差。比较起来还是Tcl的可读性好。 上面代码中MA表示母狼A,CA表示母狼A的孩子,看C代码是比较费劲的…… [face03]

  • vincent    9楼 回复

    补充一下,改天有空了,看看能不能搞个SCADE版本出来。不过估计要做来的话得对问题进行数学建模,进行预处理……

  • louie    10楼 回复

    老大
    你这个东西 直接又让我晕了。。。

    [face08]

  • ywang    11楼 回复

    vincent同事显然是意犹未尽啊,拿了奖还不过瘾,还要再用C写一遍,还不过瘾,还想着用SCADE再做一遍。就这精神,就够我们学习的。

    你说的那段话“可以用一个整数来代表状态,用不同位的0或1值表示狼是否存在。同时大量用位运算,速度快且代码量小”,其实这就是我实现的方法。见本人提供的参考答案(程序+运行结果),除去打印程序,核心的过河代码也就50行,还包括了空行与单行的{及}。

  • ywang    12楼 回复

    vincent在1月7日发表评论说想做一个SCADE模型解决这个问题,现在他做到了。

    我在文章最后添加了后记,把vincent的SCADE模型也放了上去。想学习的朋友自己下载吧。

    向vincent这种孜孜不倦、精益求精、言出必行的精神致敬!

  • 幽兰    13楼 回复

    这里不该我来的,顶一下[face41],撤[face05]

发表评论:

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

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