基于穷举算法对德国逻辑思考学院的逻辑推断题的解答算法
目录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>=(len-1) )
{
retval = mksort_add( sort, base+1, retval, len );
sort = 0;
}
else
{
sort ++;
}
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 )
{
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;
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无效率累死计算机的穷举排序算法完成了 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函数, 输入参数是所有的状态数组组合, 返回是否Okayint 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, color, pat, drink, fruit;
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在此抛砖引玉 赞。。。涨见识。。。
尤其是此程序的结构值得赞。。。
以前写逻辑推理题是很烦人的。。因为结构巨乱。。。
页:
[1]