打印

基于穷举算法对德国逻辑思考学院的逻辑推断题的解答算法

基于穷举算法对德国逻辑思考学院的逻辑推断题的解答算法

目录
1. 问题
2. 穷举排序mksort
3. 程序设计
4. 运算结果


1. 问题

以前在论坛上见过一道题, 题目源自1981年柏林的德国逻辑思考学院改编的,98%的测试者无法解题,
(美国某家半导体设计公司曾以此题招考员工) 题名如下:
引用:
有五位小姐排成一列;所有的小姐穿的衣服颜色都不一样;所有的小姐姓也不同;所有的小姐都养不同的宠物,喝不同的饮料,吃不同的水果

钱小姐穿红色的衣服
翁小姐养了一只狗
陈小姐喝茶
穿绿衣服的站在穿白衣服的左边
穿绿衣服的小姐喝咖啡
吃西瓜的小姐养鸟
穿黄衣服的小姐吃柳丁
站在中间的小姐喝牛奶
赵小姐站在最左边
吃桔子的小姐站在养猫的隔壁
养鱼的小姐隔壁吃柳丁
吃苹果的小姐喝香槟
江小姐吃香蕉
赵小姐站在穿蓝衣服的隔壁
只喝开水的小姐站在吃桔子的隔壁
------请问哪位小姐养蛇?
昨晚整理硬盘的时候, 无意中发现以前保存下来了,
于是乎, 想完成以前的承诺, 写个program来计算


2. 穷举排序mksort

电脑的优点在于重复的运算, 不劳累也不会出错
所以设计这解决方案的时候, 几乎没有多想, 用穷举
( 后来 bc 1.06 告诉我, 一个属性有五种状态是 5!=120
  然后又有五种属性, 120*120*120*120*120=24883200000
  贰佰肆拾捌亿捌仟叁佰贰拾万!!! )

穷举, 第一步就是把所有情况都排列出来;
mksort实现了这功能,
当然, mksort也是用最笨的穷举方法来实现的
extern mksort( int *sort, int len );
第一个参数是整型数组的首地址, 第二个参数是整型数组的长度(基数)
初始化时候, 需要把数组被赋值为零

然后从数组的最低下标开始, 以长度为基数, 进行累加位
复制内容到剪贴板
代码:
static int mksort_add( int *sort, int base, int retval, int len )



{     



     if( base>=len )



     {



          return MKSORT_FAIL;



     }



     



     if( sort[base]>=(len-1) )



     {



          retval = mksort_add( sort, base+1, retval, len );



          sort[base] = 0;



     }



     else



     {



          sort[base] ++;



     }







     return retval;



};
每次进位后, 检测是否存在相同的单元, 排序不会让一个人同时排在两个位置的
复制内容到剪贴板
代码:
static int mksort_same( int *sort, int len )



{



     int i, j;







     for( i=0; i<len-1; i++ )



     {



          for( j=i+1; j<len; j++ )



          {



               if( sort==sort[j] )



               {



                    return MKSORT_YES;



               }



          }



     }



     return MKSORT_NO;



};
如果当前组合里面, 没有重复的单元, 那么这个组合被接受,
否则, 再累加, 继续找
复制内容到剪贴板
代码:
extern int mksort( int *sort, int len )



{



     do



     {



          if( !mksort_add( sort, 0, MKSORT_OKAY, len ) )



          {



               return MKSORT_FAIL;



          }



     }



     while( mksort_same(sort,len) );



     



     return MKSORT_OKAY;



};
这就是 mksort穷举排序的原理了, 看我们的 main函数, 来测试一下:
复制内容到剪贴板
代码:
#define MKSORT_BASE 4







int main( void )



{



        int i, m_sort[MKSORT_BASE];



        



        for( i=0; i<MKSORT_BASE; i++ )



        {



             m_sort = 0;



        }







        while( mksort(m_sort, MKSORT_BASE) )



        {



                for( i=0; i<MKSORT_BASE; i++ )



                          printf( "%d ", m_sort );



                printf( "\n" );



        }







        return 0;



};
我们来编译
引用:
$ make
gcc -c mksort.c
gcc -o mksort main.c mksort.o
$ ./mksort
3 2 1 0
2 3 1 0
3 1 2 0
1 3 2 0
2 1 3 0
1 2 3 0
3 2 0 1
2 3 0 1
3 0 2 1
0 3 2 1
2 0 3 1
0 2 3 1
3 1 0 2
1 3 0 2
3 0 1 2
0 3 1 2
1 0 3 2
0 1 3 2
2 1 0 3
1 2 0 3
2 0 1 3
0 2 1 3
1 0 2 3
0 1 2 3
好了, mksort无效率累死计算机的穷举排序算法完成了
mail: dorainm@gmail.com
blog: dorainm.cublog.cn

TOP

2. 程序设计

申明定义一些程序所需要的各种状态的枚举及描述
复制内容到剪贴板
代码:
#define NUM 5







enum var_attr { NAME=0, COLOR, PAT, DRINK, FRUIT };



char *str_attr[] = { "Name", "Color", "Pat", "Drink", "Frui" };



enum val_relation { LEFT=-1, IS=0, RIGHT=1 };







enum val_name { QIAN=0, WEN, CHEN, ZHAO, JIANG };



char *str_name[] = { "Qian", "Wen", "Chen", "Zhao", "Jiang" };



enum val_color { RED=0, GREEN, WHITE, YELLOW, BLUE };



char *str_color[] = { "Red", "Green", "White", "Yellow", "Blue" };



enum val_pat { DOG=0, BIRD, FISH, CAT, SNAKE };



char *str_pat[] = { "Dog", "Bird", "Fish", "Cat", "Snake" };



enum val_drink { TEA=0, COFFEE, MILK, XIANGBIN, WATER };



char *str_drink[] = { "Tea", "Coffee", "Milk", "Bubbly", "Water" };



enum val_fruit { WATERMELON=0, ORANGE, LIUDING, APPLE, BANANA };



char *str_fruit[] = { "W.Melon", "Orange", "LiuDing", "Apple", "Banana" };
因为题目的条件是一些钱小姐穿红色的衣服, 养鱼的小姐隔壁吃柳丁,
吃苹果的小姐喝香槟, 穿绿衣服的站在穿白衣服的左边 之类的条件,
当程序穷举出所有排列组合的时候,
就需要有个函数来测试每种组合是否符合所有的条件
看看check_okay函数, 输入参数是所有的状态数组组合, 返回是否Okay
复制内容到剪贴板
代码:
int check_okay( int *name, int *color, int *pat, int *drink, int *fruit )



{



     //钱小姐穿红色的衣服



     if( !check_relation( name, QIAN, color, RED, IS ) )



          return FALSE;



     //翁小姐养了一只狗



     if( !check_relation( name, WEN, pat, DOG, IS ) )



          return FALSE;



     //陈小姐喝茶



     if( !check_relation( name, CHEN, drink, TEA, IS ) )



          return FALSE;



     //穿绿衣服的站在穿白衣服的左边



     if( !check_relation( color, GREEN, color, WHITE, LEFT ) )



          return FALSE;



     //穿绿衣服的小姐喝咖啡



     if( !check_relation( color, GREEN, drink, COFFEE, IS ) )



          return FALSE;



     //吃西瓜的小姐养鸟



     if( !check_relation( fruit, WATERMELON, pat, BIRD, IS ) )



          return FALSE;



     //穿黄衣服的小姐吃柳丁



     if( !check_relation( color, YELLOW, fruit, LIUDING, IS ) )



          return FALSE;



     //站在中间的小姐喝牛奶



     if( get_location( drink, MILK )!=2 )



          return FALSE;



     //赵小姐站在最左边



     if( get_location( name, ZHAO )!=0 )



          return FALSE;



     //吃桔子的小姐站在养猫的隔壁



     if( !( check_relation( fruit, ORANGE, pat, CAT, LEFT ) ||



            check_relation( fruit, ORANGE, pat, CAT, RIGHT ) ) )



          return FALSE;



     //养鱼的小姐隔壁吃柳丁



     if( !( check_relation( pat, FISH, fruit, LIUDING, LEFT ) ||



            check_relation( pat, FISH, fruit, LIUDING, RIGHT ) ) )



          return FALSE;



     //吃苹果的小姐喝香槟



     if( !check_relation( fruit, APPLE, drink, XIANGBIN, IS ) )



          return FALSE;



     //江小姐吃香蕉



     if( !check_relation( name, JIANG, fruit, BANANA, IS ) )



          return FALSE;



     //赵小姐站在穿蓝衣服的隔壁



     if( !( check_relation( name, ZHAO, color, BLUE, LEFT ) ||



            check_relation( name, ZHAO, color, BLUE, RIGHT ) ) )



          return FALSE;



     //只喝开水的小姐站在吃桔子的隔壁



     if( !( check_relation( drink, WATER, fruit, ORANGE, LEFT ) ||



            check_relation( drink, WATER, fruit, ORANGE, RIGHT ) ) )



          return FALSE;



     return TRUE;



};
get_location函数是返回某一个数组中, 指定状态的位置
复制内容到剪贴板
代码:
int get_location( int *attr, int value )



{



     int i;



     for( i=0; i<NUM; i++ )



     {



          if( value==attr )



          {



               return i;



          }



     }



     return 0;



};
check_relation函数就是用来检测两组属性的关系, 我们设计的站位是[左 0-1-2-3-4 右]
来实现条件中所说的, 什么怎么样的人怎么样(IS=0),
什么怎么样的人在怎么样的人左边(LEFT=-1), 右边(RIGHT=1), 邻居(LEFT||RIGHT)
复制内容到剪贴板
代码:
int check_relation( int *attr1, int value1, int *attr2, int value2, int relation )



{



    int location1, location2;



    int location;







    location1 = get_location( attr1, value1 );



    location2 = get_location( attr2, value2 );



    location = location1 - location2 ;



    if( location == relation )



        return TRUE;



    else



        return FALSE;



};
程序的函数介绍完毕了, 现在看看主函数, 傻吧? 穷举都这个样!!
复制内容到剪贴板
代码:
int main( void )



{



     int name[NUM], color[NUM], pat[NUM], drink[NUM], fruit[NUM];



     int i;







     for( i=0; i<NUM; i++ )



     {



          name = 0;



          color = 0;



          pat = 0;



          drink = 0;



          fruit = 0;



     }







     while( mksort(name, NUM) )



     {



          while( mksort(color, NUM) )



          {



               while( mksort(pat, NUM) )



               {



                    while( mksort(drink, NUM) )



                    {



                         while( mksort(fruit, NUM) )



                         {



                              if( check_okay( name, color, pat, drink, fruit ) )



                              {



                                   display_info( name, color, pat, drink, fruit );



                              }



                         }



                    }   



               }



          }



     }



     return 0;



};
挖咔咔, 如果觉得闷地话, 就在最里面的 while里面显示些东西解解闷
( 如果显示器一直盯着看的话, 显卡的显示将是运算的瓶颈,
  切换到别的tty上, 眼不见, 让它后台飞快运行吧 )



4. 运算结果

ThinkPad X20 的主频是 Piii 500MHz
引用:
$ more /proc/cpuinfo
processor        : 0
vendor_id        : GenuineIntel
cpu family        : 6
model                : 8
model name        : Pentium III (Coppermine)
stepping        : 3
cpu MHz                : 500.000
cache size        : 256 KB
... ...
内寸也只有 128M
引用:
$ more /proc/meminfo
MemTotal:       126132 kB
MemFree:          2440 kB
Buffers:         36352 kB
Cached:          35056 kB
... ...
我运行起来, 然后去做论文答辩的幻灯片, 然后去看别人答辩论文,
然后自己参加答辩论文, 然后去拍毕业照, 然后庆祝lynn6.1生日,
然后... ...
四天呐, 居然还没有算完!!


实在恼火, 换其他电脑, 我手头的最高主频的CPU也才1.4GHz...
借只鸡, 下个蛋吧;-P

一台 SUN Fire x4100 的服务器,
有 2颗 2.4GHz的主频 AMD Opteron 280的双核芯片,
配 4G 内存, 是 Solaris 10 Update 3 for x86/x64系统
嘿嘿, 其实程序占的内寸不超过 1M的...

编译的时候用 gcc 的 3级优化处理
引用:
$ make
gcc -O3 -c mksort.c
gcc -O3 -o 5kind main.c mksort.o
现在开始穷举贰佰肆拾捌亿捌仟叁佰贰拾万次了, 睡觉去了
O_O => o_o => *_* => x_x => zzZZ ... ZZzz => p_- => O_O! 要去看运算结果了

整整 3小时 17分钟 22秒, 终于盼到了
( 话外音: dorainm真是宇宙猛人呐, 250亿次的穷举... )
引用:
$ more result.txt
------------- start informations -------------
Name        Color        Pat        Drink        Frui        
----------------------------------------------
Zhao        Yellow        Cat        Water        LiuDing
Chen        Blue        Fish        Tea        Orange
Qian        Red        Bird        Milk        W.Melon
Jiang        Green        Snake        Coffee        Banana
Wen        White        Dog        Bubbly        Apple
----------------------------------------------
只有一种结果啊, 养蛇的果然是江小姐


文章中出现的程序附件


其实, 兜售此文是想和大家一起来优化算法, 提高这穷举算法的速度的!
当然, 也欢迎数学方法来改变程序结构, 增加效率, dorainm在此抛砖引玉
附件: 您所在的用户组无法下载或查看附件
mail: dorainm@gmail.com
blog: dorainm.cublog.cn

TOP

赞。。。涨见识。。。
尤其是此程序的结构值得赞。。。
以前写逻辑推理题是很烦人的。。因为结构巨乱。。。
Mike

TOP