爱因斯坦智力题算法的分析

2023-10-22 08:40
文章标签 算法 分析 智力题 爱因斯坦

本文主要是介绍爱因斯坦智力题算法的分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前些天，试着编程解一下爱因斯坦出过一道著名的智力题，多年前就见过，当时尝试编程解决，失败了。经过几年编程实践，不参考别人的，看能不能独立写出一个比较好的算法。 

//有五个具有五种不同颜色的房间；每个房间裏分别住著一个不同国籍的人；每个人都在喝一种特定品牌的饮料，
// 抽一特定品牌的香烟，养一特定的宠物；没有任意两个人在抽相同品牌的香烟，或喝相同品牌的饮料，或养相同的宠物。//1.英国人住在红色的房子裏；
//2.瑞典人养狗作为宠物；
//3.丹麦人喝茶；
//4.绿房子紧挨著白房子，在白房子的左边；
//5.绿房子的主人喝咖啡；
//6.抽 Pall Mall 牌香烟的人养鸟；
//7.黄色房子裏的人抽 Dunhill 牌香烟；
//8.住在中间那个房子裏的人喝牛奶；
//9.挪威人住在第一个房子裏(最左边)；
//10.抽 Blends 香烟的人和养猫的人相邻；
//11.养马的人和抽 Dunhill 牌香烟的人相邻；
//12.抽 BlueMaster 牌香烟的人喝啤酒；
//13.德国人抽 Prince 牌香烟；
//14.挪威人和住蓝房子的人相邻；
//15.抽Blends 香烟的人和喝矿泉水的人相邻；

如今以不可同日而语之犀利眼光，一眼发现这些条件真面目，不过是一个个Predicate委托而已。当然先建五个枚举：

    enum Color{Red,Green,Yellow,Blue,White}enum Nation{Britain,Norway,Danmark, Sweden,Germany}enum Pet{Bird,Horse,Cat,Dog,Fish}enum Drink{Tea, Beer, Coffee, Water,Milk}enum Smoke{Blends, BlueMaster, PallMall, DunHill, Prince}

又刷刷刷地敲出了这样的代码：

3. Danish.Drink == Drink.Tea;4. var guyInGreen = AllPeople.First(g=>g.HColor==HColor.Green); var guyInWhite = AllPeople.First(g=>g.HColor==HColor.White); guyInWhite.Position - guyInGreen.Position == 1; 5. guy = AllPeople.Where(g=>g.HColor==HColor.Green||g.Drink ==Drink.Coffee); if(guy.Count() > 1) throw; if(guy.HColor == Green) guy.Drink = Coffee; 
……

写了几段，就意识到不对劲了。主要是每个条件最后一句，是该判断呢，还是该赋值呢？比如说如果一个人，住在红房子里，那他一定是英国人。那就要看这个人有哪些属性已经确定了。

而且，如果既现在既不确定哪个住红房子，也不知道谁是英国人，怎么办？经过反复思考，我想每个条件，除了能提供判断，以及合适时赋值，还要提供推断，即可能的方案以供尝试。先选一种方案，然后下个条件再判断现在的状态是否合法，是的话再提出一组方案，不然就选上一条件中的下一个方案。

想到这里，算法的轮廓大致浮现了出来。每个条件，将成为一个个Condition类的实例。而另一个领域模型，之前没有想到的类，已经呼之欲出，即将登上舞台成为主角。导演，自然是偶了。

这场好戏，现在该考虑故事背景了。想在潘多拉星球上拍神雕侠侣，大概观众会吐血，当然更别说种山楂树，观众不吐我都要吐了。在上下班路上，内心经过痛苦的斗争，偶决定放弃风花雪月的属性，因为给每个属性创建状态标识的成本太高。于是偶移师海阔天空的大自然，不加雕琢的Dictionary成了这部戏的主要外景。

    class Guy{public Dictionary Properties = new Dictionary(6);......}class PN   //PropertyName{public const string Color = "Color";public const string Pet = "Pet";public const string Nation = "Nation";public const string Drink = "Drink";public const string Smoke = "Smoke";public const string Postion = "Postion";public static IEnumerable GetNames(){yield return Postion;yield return Nation;yield return Color;yield return Drink;yield return Pet;yield return Smoke;}}

Guy类的主要函数，就是围绕Guy.Properties这个属性字典进行操作，如何封装取决于Condition类的实现。对于条件中单独一个属性，本来可以用 KeyValuePair<string,int>表示，不过太长，所以自己写了个Property类。要是类型能定义别名就好了。看题目中的条件，不少都是根据位置作判断的，所以位置是特殊的属性，如果能用来作Guy的主键，应该可以事半功倍。

下面，期待中的主角露出了庐山真面目，完全是我们以抽象思维创作出来艺术形像。其实很简单，但没艺术细胞的想不出，不会创作的写不出，大家认为呢？

   class Attempt{public Guy[] Guys = new Guy[2];public Property[] Properties = new Property[2];public void Act(){Guys[0].SetProperty(Properties[0]);if(Guys[1] !=null) Guys[1].SetProperty(Properties[1]);}public void RollBack(){Guys[0].RemoveProperty(Properties[0]);if (Guys[1] != null) Guys[1].RemoveProperty(Properties[1]);}public Attempt(Property[] properties, Guy[] guys){Guys = guys;Properties = properties;}public Attempt(Property[] properties, Guy guy){Guys[0] = Guys[1] = guy;Properties = properties;}public Attempt(Property property, Guy guy){Guys[0] = guy;Properties[0] = property;}}

接着来参观下为主角量身打造的舞台吧，大导演拍大片，当然要打造大舞台，比世博园还大，看个样子就行了 :)

  abstract class Condition{protected Property[] Properties = new Property[2];protected Condition(Property p1, Property p2);protected Condition() { }public abstract MatchResult Match(IList guys, ref IList attempts);}/// /// 同人条件/// class SameGuyCondition : Condition{public SameGuyCondition(Property p1, Property p2);public override MatchResult Match(IList guys, ref IList attempts);}/// /// 相邻条件/// class AdjacentCondition : Condition{RelativePosition Relation;  //default is bothpublic AdjacentCondition(Property p1, Property p2);public AdjacentCondition(Property p1, Property p2, RelativePosition relation);public override MatchResult Match(IList guys, ref IList attempts);}

这场戏分十几场来拍，有了前面的准备，剧本一气呵成：

  class Puzzle{static IList conditions = new List();public static void Start(){......AddCondition(PN.Nation, Nation.Britain, PN.Color, Color.Red);AddCondition(PN.Nation, Nation.Sweden, PN.Pet, Pet.Dog);AddCondition(PN.Nation, Nation.Danmark, PN.Drink, Drink.Tea);AddCondition(PN.Color, Color.Green, PN.Color, Color.White, RelativePosition.Left);AddCondition(PN.Color, Color.Green, PN.Drink, Drink.Coffee);AddCondition(PN.Smoke, Smoke.PallMall, PN.Pet, Pet.Bird);AddCondition(PN.Color, Color.Yellow, PN.Smoke, Smoke.DunHill);AddCondition(PN.Postion, 3, PN.Drink, Drink.Milk);AddCondition(PN.Nation, Nation.Norway, PN.Postion, 1);AddCondition(PN.Smoke, Smoke.Blends, PN.Pet, Pet.Cat, RelativePosition.Both );AddCondition(PN.Pet, Pet.Horse, PN.Smoke, Smoke.DunHill, RelativePosition.Both);AddCondition(PN.Smoke, Smoke.BlueMaster, PN.Drink, Drink.Beer);AddCondition(PN.Smoke, Smoke.Prince, PN.Nation, Nation.Germany);AddCondition(PN.Nation, Nation.Norway, PN.Color, Color.Blue, RelativePosition.Both);AddCondition(PN.Drink, Drink.Water, PN.Smoke, Smoke.Blends, RelativePosition.Both);......}}

看上去万事俱备，只欠东风了。事实上要借到东风，还须一些神通，最后一步还有一道难题，这么多场景如何串联在一起？这种戏偶以前从未拍过，考验功底的时候到了。在僵局的时刻，“搜索树”在脑中灵光一现，对，听这名字就是我要的。虽然不知所谓，也从未用过，但“树”我懂的啊。实话说，偶很讨厌写这些树啊图啊的，不过关键时刻，难不倒偶的。

  class StepNode{/// /// The number of stage in the search tree, each stage match a condition/// public Int32 Index;StepNode[] Steps;public StepNode Parent;public Attempt Action;/// /// The index indicates which step should be continued now, the previous steps has failed./// Int32 currentStepIndex;Boolean Ending{get{if (Steps == null) return true;return currentStepIndex >= Steps.Length;}}public StepNode Next(){StepNode nextNode;if (Ending){if (Action != null) Action.RollBack(); nextNode = Parent.Next();}else nextNode = Steps[currentStepIndex];currentStepIndex++;return nextNode;}public StepNode Expand(IList attempts){if (attempts != null || attempts.Count > 0){Steps = new StepNode[attempts.Count];for (int i = 0; i < attempts.Count; i++){Steps[i] = new StepNode { Parent = this, Index = Index + 1, Action = attempts[i] };}}else{Steps = new StepNode[] {new StepNode { Parent = this, Index = Index + 1 } };}return this;}}class Puzzle{static IList conditions = new List();static IList attempts = new List();static IList guys;public static void Start(){guys = GuyRuler.Init();#region Init conditions... ...#endregionvar root = new StepNode();GoFrom(root);}static void GoFrom(StepNode node){if (node.Index >= conditions.Count) return;if (node.Action != null) node.Action.Act();var result = conditions[node.Index].Match(guys, ref attempts);if (result == MatchResult.Fail){if (node.Action != null) node.Action.RollBack();node = node.Parent.Next();}else{node = node.Expand(attempts).Next();}GoFrom(node);   }}

非常顺利，人就要敢于尝试和突破。照例，杀青前，测试下结果：

image

有点奇特是吧，结果差距怎么这么大？可千万别被迷惑了，由于输出结果时用了Enum的反射，这是个绝对的性能杀手。在我Core7200处理器,32位Win7电脑上，真正计算过程不到2ms!

附源代码下载，里面几个类都重写了ToString方法，在VS下调试时相当方便，这是其它开发环境望尘莫及的。怎么样，还是不够快啊。那好，下期再来优化它。

这篇关于爱因斯坦智力题算法的分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/260336。

相关文章

Redis主从复制实现原理分析

Redis主从复制实现原理分析

《Redis主从复制实现原理分析》Redis主从复制通过Sync和CommandPropagate阶段实现数据同步,2.8版本后引入Psync指令,根据复制偏移量进行全量或部分同步,优化了数据传输效率... 目录Redis主DodMIK从复制实现原理实现原理Psync: 2.8版本后总结Redis主从复制实
阅读更多...
锐捷和腾达哪个好? 两个品牌路由器对比分析

锐捷和腾达哪个好? 两个品牌路由器对比分析

《锐捷和腾达哪个好?两个品牌路由器对比分析》在选择路由器时，Tenda和锐捷都是备受关注的品牌，各自有独特的产品特点和市场定位，选择哪个品牌的路由器更合适，实际上取决于你的具体需求和使用场景，我们从... 在选购路由器时，锐捷和腾达都是市场上备受关注的品牌，但它们的定位和特点却有所不同。锐捷更偏向企业级和专
阅读更多...
Spring中Bean有关NullPointerException异常的原因分析

Spring中Bean有关NullPointerException异常的原因分析

《Spring中Bean有关NullPointerException异常的原因分析》在Spring中使用@Autowired注解注入的bean不能在静态上下文中访问,否则会导致NullPointerE... 目录Spring中Bean有关NullPointerException异常的原因问题描述解决方案总结
阅读更多...
python中的与时间相关的模块应用场景分析

python中的与时间相关的模块应用场景分析

《python中的与时间相关的模块应用场景分析》本文介绍了Python中与时间相关的几个重要模块：`time`、`datetime`、`calendar`、`timeit`、`pytz`和`dateu... 目录1. time 模块2. datetime 模块3. calendar 模块4. timeit
阅读更多...
python-nmap实现python利用nmap进行扫描分析

python-nmap实现python利用nmap进行扫描分析

《python-nmap实现python利用nmap进行扫描分析》Nmap是一个非常用的网络/端口扫描工具,如果想将nmap集成进你的工具里,可以使用python-nmap这个python库,它提供了... 目录前言python-nmap的基本使用PortScanner扫描PortScannerAsync异
阅读更多...
Oracle数据库执行计划的查看与分析技巧

Oracle数据库执行计划的查看与分析技巧

《Oracle数据库执行计划的查看与分析技巧》在Oracle数据库中,执行计划能够帮助我们深入了解SQL语句在数据库内部的执行细节,进而优化查询性能、提升系统效率,执行计划是Oracle数据库优化器为... 目录一、什么是执行计划二、查看执行计划的方法（一）使用 EXPLAIN PLAN 命令（二）通过 S
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2