QQ登录

只需一步，快速开始

 找回密码
 注册

QQ登录

只需一步，快速开始

返回列表 发新帖
查看: 2500|回复: 2

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

[复制链接]
dorainm
发表于 2007-7-31 04:40:53 | 显示全部楼层 |阅读模式
目录
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 );
第一个参数是整型数组的首地址, 第二个参数是整型数组的长度(基数)
初始化时候, 需要把数组被赋值为零

然后从数组的最低下标开始, 以长度为基数, 进行累加位
  1. static int mksort_add( int *sort, int base, int retval, int len )



  5. {     



  9.      if( base>=len )



  13.      {



  17.           return MKSORT_FAIL;



  21.      }



  25.      



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



  33.      {



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



  41.           sort[base] = 0;



  45.      }



  49.      else



  53.      {



  57.           sort[base] ++;



  61.      }







  69.      return retval;



  73. };
复制代码

每次进位后, 检测是否存在相同的单元, 排序不会让一个人同时排在两个位置的
  1. static int mksort_same( int *sort, int len )



  5. {



  9.      int i, j;







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



  21.      {



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



  29.           {



  33.                if( sort==sort[j] )



  37.                {



  41.                     return MKSORT_YES;



  45.                }



  49.           }



  53.      }



  57.      return MKSORT_NO;



  61. };
复制代码

如果当前组合里面, 没有重复的单元, 那么这个组合被接受,
否则, 再累加, 继续找
  1. extern int mksort( int *sort, int len )



  5. {



  9.      do



  13.      {



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



  21.           {



  25.                return MKSORT_FAIL;



  29.           }



  33.      }



  37.      while( mksort_same(sort,len) );



  41.      



  45.      return MKSORT_OKAY;



  49. };
复制代码

这就是 mksort穷举排序的原理了, 看我们的 main函数, 来测试一下:
  1. #define MKSORT_BASE 4







  9. int main( void )



  13. {



  17.         int i, m_sort[MKSORT_BASE];



  21.         



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



  29.         {



  33.              m_sort = 0;



  37.         }







  45.         while( mksort(m_sort, MKSORT_BASE) )



  49.         {



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



  57.                           printf( "%d ", m_sort );



  61.                 printf( "\n" );



  65.         }







  73.         return 0;



  77. };
复制代码


我们来编译
$ 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无效率累死计算机的穷举排序算法完成了
回复

使用道具 举报

dorainm
 楼主| 发表于 2007-7-31 04:41:43 | 显示全部楼层
2. 程序设计

申明定义一些程序所需要的各种状态的枚举及描述
  1. #define NUM 5







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



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



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







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



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



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



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



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



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



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



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



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



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



  5. {



  9.      //钱小姐穿红色的衣服



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



  17.           return FALSE;



  21.      //翁小姐养了一只狗



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



  29.           return FALSE;



  33.      //陈小姐喝茶



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



  41.           return FALSE;



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



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



  53.           return FALSE;



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



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



  65.           return FALSE;



  69.      //吃西瓜的小姐养鸟



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



  77.           return FALSE;



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



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



  89.           return FALSE;



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



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



  101.           return FALSE;



  105.      //赵小姐站在最左边



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



  113.           return FALSE;



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



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



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



  129.           return FALSE;



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



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



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



  145.           return FALSE;



  149.      //吃苹果的小姐喝香槟



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



  157.           return FALSE;



  161.      //江小姐吃香蕉



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



  169.           return FALSE;



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



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



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



  185.           return FALSE;



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



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



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



  201.           return FALSE;



  205.      return TRUE;



  209. };
复制代码
get_location函数是返回某一个数组中, 指定状态的位置
  1. int get_location( int *attr, int value )



  5. {



  9.      int i;



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



  17.      {



  21.           if( value==attr )



  25.           {



  29.                return i;



  33.           }



  37.      }



  41.      return 0;



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



  5. {



  9.     int location1, location2;



  13.     int location;







  21.     location1 = get_location( attr1, value1 );



  25.     location2 = get_location( attr2, value2 );



  29.     location = location1 - location2 ;



  33.     if( location == relation )



  37.         return TRUE;



  41.     else



  45.         return FALSE;



  49. };
复制代码
程序的函数介绍完毕了, 现在看看主函数, 傻吧? 穷举都这个样!!
  1. int main( void )



  5. {



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



  13.      int i;







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



  25.      {



  29.           name = 0;



  33.           color = 0;



  37.           pat = 0;



  41.           drink = 0;



  45.           fruit = 0;



  49.      }







  57.      while( mksort(name, NUM) )



  61.      {



  65.           while( mksort(color, NUM) )



  69.           {



  73.                while( mksort(pat, NUM) )



  77.                {



  81.                     while( mksort(drink, NUM) )



  85.                     {



  89.                          while( mksort(fruit, NUM) )



  93.                          {



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



  101.                               {



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



  109.                               }



  113.                          }



  117.                     }   



  121.                }



  125.           }



  129.      }



  133.      return 0;



  137. };
复制代码
挖咔咔, 如果觉得闷地话, 就在最里面的 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在此抛砖引玉

本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？注册

×
回复

使用道具 举报

发表于 2007-8-3 23:28:49 | 显示全部楼层
赞。。。涨见识。。。
尤其是此程序的结构值得赞。。。
以前写逻辑推理题是很烦人的。。因为结构巨乱。。。
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则

GMT+8, 2024-4-25 20:15 , Processed in 0.069285 second(s), 16 queries .

© 2021 Powered by Discuz! X3.5.

快速回复 返回顶部 返回列表