软件开发>杂文>9

共享软件开发的点滴心得

[中文][English][日本語]

[机器人制作] [软件开发] [豆知识] [Squeak] [关于]

 Logic deduction

说谎岛

刘新宇

20068

 

松下问童子,言师采药去;

只在此山中,云深不知处。

——贾岛《寻隐者不遇》

达尔文指出, 在动物大量繁殖的情况下,由于资源有限,就会发生残酷的生存竞争。动物的竞争有些很有趣。例如南美洲一种在山区生活的羚羊,在繁殖季节,雄性为了争夺配 偶,进行激烈的赛跑。雌羊在崎岖险峻的岩石间领头飞奔跳跃,大量的雄羊尾随其后,紧追不舍。一些雄性在这场赛跑中,技不如人,就放弃追逐,退出竞争。雌羊 不停奔跑,不断有雄性遭到淘汰。直到最后剩下一只最擅长奔跑,最坚忍不拔的雄性。他们双方才组建家庭、生儿育女。这样的竞争倒也痛快直率,跑不快的愿赌服 输。雌羊通过这样“公平”的竞赛,希望能和优秀的雄性繁殖出更优秀的下一代,在未来躲避食肉动物的追杀中,能尽量存活下来。也有的竞争很血腥,双方剑拔弩 张,使出浑身解数,为了争夺资源不惜置对方于死地。

比起动物的这些,人类才是不折不扣的尔虞我诈,钩心斗角。为了争夺资源,无所不用其极。即使表面看来文明的绅士、小姐、白领、专家,也是深谙制造谎言,踩着众人的头顶向上爬的本领。面对众多的谎言,事实却是“只在此山中,云深不知处”,要辨其真伪,何其难哉!

说谎岛

 

很久以前就流传着“说谎岛”的故事[1]。 一位王子要去“说谎岛”救一位被巫师用魔法关在城堡里的公主,他面前有五条路:大路,小路,山路,一条河和一座桥。如果走错路,可能会遇到杀人的火龙,凶 猛的狮子或是踏入死亡沼泽。王子遇到四位路人,向他们询问,但是他得到的答案不但不全,而且每个路人的答案中,都有一半是谎话:

  • 路人甲:小路上有狮子,沿着河走会踏入沼泽;
  • 路人乙:沿着大路走就会到达城堡,不要过桥,那会一事无成;
  • 路人丙:山路上什么也没有,杀人的火龙藏在河里;
  • 路人丁:小路通往死亡沼泽,狮子藏在桥的另一头。

在这些扑朔迷离 的答案中,王子怎样才能做出正确的判断呢?如果在现代,就可以让计算机来帮帮忙。由于计算机不知疲倦,所以可以用最笨的办法——穷举所有的情况。思路是把 五条路编上号,把城堡,火龙,狮子,沼泽这四种东西,每次拿出一个放到一条路上。然后判断甲乙丙丁四人的话是否对错参半(任何一个人的话不能都对或者都 错)。

穷举可以用一个四重循环来实现:

     for(int castle=0; castle<5; ++castle){

          for(int dragon=0; dragon<5; ++dragon){

              for(int lion=0; lion<5; ++lion){

                   for(int marsh=0; marsh<5; ++marsh){

                   //判断甲乙丙丁是否各说一半谎话。

                   }

              }

          }

     }

 

这里略作一些解释,首先五条路分别编号为0,1,2,3,4,也就是说第3条路代表河,第0条路代表大路,依此类推。这样的编号可以用一个枚举来代表:

enum WAY{ ROAD=0, PATH, MOUNTAIN, RIVER, BRIDGE };

如果dragon=2则代表火龙在第2条路,也就是山路上。根据这样的解释,可以写出判断“某条路上有什么”的函数如下:

bool meet(int target, int way){

     return target == way;

}

根据这样的约定,路人甲的答案(断言)可以表示为:

meet(lion, MOUNTAIN), meet(marsh, RIVER)

但是由于“说谎岛”上的居民都说谎话,路人甲说的话中有一半是真的一半是假的。可能山路上有狮子是假,而河流通向沼泽为真;也可能前一句山路上有狮子是真,而河流通向沼泽为假。总之不可能都真,或者不可能都假。为了直观,可以把这些规律归纳成表格:

meet(lion, MOUNTAIN)

meet(marsh, RIVER)

正确与否

true

true

错误

true

false

正确

false

true

正确

false

false

错误

通过此表格,可以发现判断一种情况是否符合“说谎岛”居民路人甲的答案,从而是真实情况的一种简便方法是:

if( meet(lion, MOUNTAIN) == meet(marsh, RIVER) ){

//错误

}

else{

     //正确

}

另外一个问题是,如何判断路人乙的后半句话“不要过桥,那会一事无成”的正确性?虽然有5条路,但却只有4种物体,这样就必然有一条路上是空的,没有任何物体存在。可以把这种情况定义为nothing,于是问题变为把城堡、狮子、火龙、沼泽和nothing一一摆放到编号为0,1,2,3,4的五条路上。如果已经确定了前四种东西在那条路上,则nothing就可以表示为:

nothing = (0+1+2+3+4)-castle-dragon-lion-marsh

这样路人乙说的后半句话就可以表示为:meet(nothing, BRIDGE)。通过这些方法,最上面的穷举判断程序可以进一步完成为:

for(int castle=0; castle<5; ++castle){

     for(int dragon=0; dragon<5; ++dragon){

          for(int lion=0; lion<5; ++lion){

              for(int marsh=0; marsh<5; ++marsh){

                   //判断甲乙丙丁是否各说一半谎话。

int nothing = (1+2+3+4)-castle-dragon-lion-marsh;

                     if( meet(lion, MOUNTAIN)==meet(marsh, RIVER) )

                           continue;

if( meet(castle, ROAD)==meet(nothing, BRIDGE) )

continue;

                     if( meet(nothing, MOUNTAIN)==meet(dragon, RIVER) )

continue;

                     if( meet(marsh, PATH)==meet(lion, BRIDGE) )

continue;

                     //输出正确答案。

              }

          }

     }

}

这段程序还存在一些问题,它在将一个物体摆放在某一条路上时,并不判断这条路上事先是否已经排放了其他物体。这样第一轮判断时,所有的四样东西,城堡、火龙、狮子、沼泽都在第0条路(也就是大路)上。所以要设法防止这种情况,提高效率。为此,可以给每条路增加一个标志,一旦把某个东西摆放到某一条路上,就设置这个标志。表明:“此路已被占用”。当判断完成后,在把此标记清楚,使得下一轮尝试能够使用此路。其实现如下:

bool onWay[5];     //道路占用标记

for(int i=0; i<5; ++i)

     onWay[i]=false;

for(int castle=0; castle<5; ++castle){

     onWay[castle]=true; //此路被占用,其上摆放了城堡

     for(int dragon=0; dragon<5; ++dragon){

          if(onWay[dragon]) continue//此路事先已被占用,换其他方案

          onWay[dragon]=true; //此路被占用,其上摆放了火龙

          //...

         

          onWay[dragon]=false//移除火龙,此路不再被占用

     }

     onWay[castle]=false//移除城堡,此路不再被占用

}

最后一个细节是如何输出最终结果,可以用一个字符串数组将道路标号和实际代表的大路、小路、山路、河、桥联系起来:

const char* ways[]={"road", "path", "mountain", "river", "bridge"};

这样就可以显示比较友好的结果,这段代码如下:

std::cout<<"castle\t"<<ways[castle]<<"\n"

     <<"dragon\t"<<ways[dragon]<<"\n"

     <<"lion\t"<<ways[lion]<<"\n"

     <<"marsh\t"<<ways[marsh]<<"\n"

     <<"nothing\t"<<ways[nothing]<<"\n";

把上面的内容综合在一起,王子就可以判断出各条路上究竟有什么,程序回答如下:

castle  road

dragon  path

lion    bridge

marsh   river

nothing mountain

也就是说,王子沿大路走就可以找到关押公主的城堡,沿着小路走会遇到杀人的火龙,一旦过桥就会碰到狮子,沿着河流会最终深陷沼泽,而走进山路,却会一无所获。

世界杯

记者小赵代表报社去采访首次在瑞士召开的世界杯足球赛。小组赛中最热门的是号称死亡之组的A组,汇集了英格兰、德国、巴西和法国队!由于观众太多,一票难求。小赵赶到日内瓦时,已经错过了前4场比赛。他只好向当地球迷询问这四场比赛的情况。但是球迷们一半由于激动,一半由于多喝了些啤酒,所以告诉小赵的情况含混不清。小赵搜集了半天,只知道这些情况:

  1. 德国、法国已经各踢了两场;
  2. 某支国家队已经赛了三场;
  3. 2场和第3场比赛中,四支国家队都亮相了;
  4. 德国队和巴西队至今还没有碰面;
  5. 四支队伍目前都取得了胜利,第一场英格兰获胜,第二场巴西获胜,第三场德国队获胜,第四场法国队获胜。

情况没有搞清,但是报社主编又打电话催稿了,小赵怎么才能知道前四场确切的比赛结果呢?

“说谎岛”的故事中,采用穷举可以找到答案。可是这次如果用参加四场比赛的8支队伍作为循环变量进行穷举的话,就要进行8重循环,每个循环尝试4个国家。有没有更好的办法呢?

目前已知的最详细情况是各场获胜的队伍,并且还有一些隐含规则:“任何一支国家队都不会和自己比赛”并且“两只国家队只碰面一次,不会重复比赛”。因此可以列出这样一张表格,表格的行代表比赛的场次,列代表参赛的队伍。若某一比赛中有某一国家队参赛,则在此空格若填入1,这样可以初步画出下面的表格:

England

Germany

Brazil

France

1

1

2

1

3

1

4

1

在这张表格中,只要在每行中,找出剩下的空格中哪个应该填入1就可以了。于是问题被简化为确定每场比赛另外一支输掉的国家队的问题。这样只需要4重循环进行穷举就可以了。可以初步写出穷举循环的样子:

enum NATION {England=0, Germany, Brazil, France};

const int winner[]={England, Brazil, Germany, France};

int loser[4];

for(loser[0]=0; loser[0]<4; ++loser[0]){

     if(loser[0]==winner[0]) continue;

     for(loser[1]=0; loser[1]<4; ++loser[1]){

          if(loser[1]==winner[1]) continue;

          for(loser[2]=0; loser[2]<4; ++loser[2]){

              if(loser[2]==winner[2]) continue;

              for(loser[3]=0; loser[3]<4; ++loser[3]){

                   if(loser[3]==winner[3]) continue;

                   //判断该种比赛组合是否符合已了解的情况

              }

          }

     }

}

这里略作解释,每个循环中的if(loser[j]==winner[j]) continue;都是用来保证任何一支国家队不会自己和自己比赛这一隐含规则的。下面就可以集中精力确定如何利用5条已了解的情况来判断穷举出的比赛某种组合是否合理。

首先需要用某种方式来表达上面的表格,其中自然而直观的选择是利用一个442维数组。然后把每组获胜和每组失败的队伍填为1。如果用一个类表示,则其实现如下:

class Match{

public:

     enum NATION {England=0, Germany, Brazil, France};

     Match(const int winner[], int loser[]){

          memset(table, 0, sizeof(int)*4*4);

          for(int i=0; i<4; ++i){

              table[i][winner[i]]=table[i][loser[i]]=1;

          }

     }

private:

     int table[4][4];

};

注意到考虑参赛国家名称的特殊性,和穷举判断算法的一般性,这里把国家枚举移动到了类的内部,相应主程序算法也要略作调整。此后,针对每一个穷举出的比赛组合,就可以这样生成一个比赛对阵表格:

Match game(winner, loser);

小赵了解的第一个情况是,德国和法国各踢了两场。因此需要一个根据对阵表统计出每支国家队参加了几场比赛的函数。该函数实现如下:

int Match::plays(int nation){

     int res=0;

     for(int i=0; i<4; ++i)

          res+=(table[i][nation]!=0);

     return res;

}

这个函数接受一个国家队参数,然后遍历表格中该国家所在的列,找出所有不为0的格子数目。这个数目也就是该国家队参加过的比赛的场次数。因此德国和法国各踢了两场这一条件可以表达为:

//外层循环略...

for(loser[3]=0; loser[3]<4; ++loser[3]){

     if(loser[3]==winner[3]) continue;

Match game(winner, loser);

     if(game.plays(Match::Germany)!=2 || game.plays(Match::France)!=2)

          continue;

     //其他条件判断...

     }

}

下一个判断条件是:“某支国家队已经赛了三场”。由于法国和德国都各踢了两场,所以这支比赛了三场的国家队不是巴西队,就是英格兰队。这一判断可以表示为:

Match game(winner, loser);

//德国、法国各赛两场

if(game.plays(Match::Germany)!=2 || game.plays(Match::France)!=2)

     continue;

//比赛了三场的不是英格兰队,就是巴西队

if(game.plays(Match::England)!=3 && game.plays(Match::Brazil)!=3)

     continue;

由于第2场和第3场比赛中,四支国家队都亮相了。这一条件可以这样理解:没有任何一支国家队既没有参加第2场比赛,也没有参加第3场比赛。也就是在表格中,没有一支国家队所在的列中,第二、第三个格子都为0。为了简化这种统计,可以开发这样一个函数:

bool Match::hasAbsent(int g1, int g2){

     for(int nation=0; nation<4; ++nation)

          if(table[g1][nation]==0 && table[g2][nation]==0)

              return true;

     return false;

}

这个函数接受两个比赛的场次作为参数,然后遍历所有国家队,看看有没有球队两场比赛都缺席。利用这个函数,可以把第三个判断也加入,这样判断部分就变为:

Match game(winner, loser);

//德国、法国各赛两场

if(game.plays(Match::Germany)!=2 || game.plays(Match::France)!=2)

     continue;

//比赛了三场的不是英格兰队,就是巴西队

if(game.plays(Match::England)!=3 && game.plays(Match::Brazil)!=3)

     continue;

//2场和第3场比赛中,所有球队都亮相了

if(game.hasAbsent(1,2))

     continue;

剩下最后一个已知条件是“德国队和巴西队至今还没有碰面”。判断这个条件,可以遍历表格中的所有列(所有比赛),检查每一列中德国队和巴西队所在的格子,他们不能都为1。为此可以给Match类增加下面的判断函数:

bool Match::hasPlayed(int nation1, int nation2){

     for(int i=0; i<4; ++i)

          if(table[i][nation1] && table[i][nation2])

              return true;

     return false;

}

该函数读入两个国家队的编号,然后判断这两个队是否比赛过。利用这个函数,最后一个已知条件可以表达为:

//...

//德国和巴西至今还没有比赛过

if(game.hasPlayed(Match::Germany, Match::Brazil))

     continue;

现在可以运行一下程序,看看小赵能否了解前四场比赛的所有情况了,为此还要增加一个打印这四场比赛对阵结果的输出函数,这个函数可以实现如下:

void Match::print(){

     const char* nation[]={"England", "Germany", "Brazil", "France"};

     for(int i=0; i<4; ++i){

          std::cout<<i+1<<":\t";

          for(int j=0; j<4; ++j)

              if(table[i][j])

                   std::cout<<nation[j]<<"\t";

          std::cout<<"\n";

     }

}

运行这个程序,会发现有两个解。

第一个解:

1:      England Germany

2:      England Brazil

3:      Germany France

4:      England France

第二个解:

1:      England Germany

2:      Brazil  France

3:      England Germany

4:      England France

仔细观察它们,会发现第二个解中,英格兰和德国比赛了两次,因此只有第一解合理。这种情况暗示,程序忽略了一个隐含条件:“不会重复比赛”。如何判断是否有重复比赛,就留给读者思考解决,本文最后给出了一个参考答案。

结论

和前几个月的文章比较,本文所涉及的内容,没有任何复杂之处。既不涉及对象理论,也不深入谈到C++特 性。几乎使用任何计算机语言都可以解决这些问题。但是真正有趣的是问题本身,以及使用计算机解决此类问题的尝试和规律。计算机具有计算功能和逻辑推理功 能,但是后一种往往容易被忽略。本文仅仅讨论了一种解决方法——穷举,其思路是充分利用计算机的特点来完成人所不愿意也不擅长做的内容。

我们身处的世界是残酷的,社会是复杂的。几乎天天都生活在残缺扭曲的信息和谎言之中。很难利用某种方法去伪存真,发现真相,本文的故事也无非是无法实现的“乌托邦”而已。

参考书目:

[1] The liar island story. http://mathforum.org/dr.math/faq/faq.liar.html

 

参考答案

 

世界杯问题的全部源代码:

class Match{

public:

     enum NATION {England=0, Germany, Brazil, France};

 

     Match(const int winner[], int loser[]){

           memset(table, 0, sizeof(int)*4*4);

           for(int i=0; i<4; ++i){

                table[i][winner[i]]=table[i][loser[i]]=1;

           }

     }

 

     int plays(int nation){

           int res=0;

           for(int i=0; i<4; ++i)

                res+=table[i][nation];

           return res;

     }

 

     bool hasAbsent(int g1, int g2){

           for(int nation=0; nation<4; ++nation)

                if(table[g1][nation]==0 && table[g2][nation]==0)

                     return true;

           return false;

     }

 

     bool sameGame(int g1, int g2){

           for(int i=0; i<4; ++i)

                if(table[g1][i] != table[g2][i])

                     return false;

           return true;

     }

 

     bool noSameGame(){

           for(int i=0; i<4; ++i)

                for(int j=0; j<4; ++j)

                     if((i!=j) && sameGame(i, j))

                           return false;

           return true;

     }

 

     bool hasPlayed(int nation1, int nation2){

           for(int i=0; i<4; ++i)

                if(table[i][nation1] && table[i][nation2])

                     return true;

           return false;

     }

 

     void print(){

           const char* nation[]={"England", "Germany", "Brazil", "France"};

 

           for(int i=0; i<4; ++i){

                std::cout<<i+1<<":\t";

                for(int j=0; j<4; ++j)

                     if(table[i][j])

                           std::cout<<nation[j]<<"\t";

                std::cout<<"\n";

           }

     }

 

private:

     int table[4][4];

};

 

void worldCup(){

     const int winner[]={

Match::England, Match::Brazil, Match::Germany, Match::France};

     int loser[4];

 

     for(loser[0]=0; loser[0]<4; ++loser[0]){

           if(loser[0]==winner[0]) continue;

 

           for(loser[1]=0; loser[1]<4; ++loser[1]){

                if(loser[1]==winner[1]) continue;

 

                for(loser[2]=0; loser[2]<4; ++loser[2]){

                     if(loser[2]==winner[2]) continue;

 

                     for(loser[3]=0; loser[3]<4; ++loser[3]){

                           if(loser[3]==winner[3]) continue;

 

                           Match game(winner, loser);

                           if(game.plays(Match::Germany)!=2 || game.plays(Match::France)!=2)

                                continue;

                           if(game.plays(Match::England)!=3 && game.plays(Match::Brazil)!=3)

                                continue;

 

                           if(game.hasAbsent(1,2))

                                continue;

 

                           if(!game.noSameGame())

                                continue;

 

                           if(game.hasPlayed(Match::Germany, Match::Brazil))

                                continue;

 

                           game.print();

                     }

                }

           }

     }

}


[English][上一篇][目录][下一篇][主页][联系我们: liuxinyu95@gmail.com]