算法系列之七:爱因斯坦的思考题(上) .

2023-11-22 21:59

本文主要是介绍算法系列之七:爱因斯坦的思考题(上) .,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

        这是一个很有趣的逻辑推理题,传说是爱因斯坦提出来的,他宣称世界上只有2%的人能解出这个题目,传说不一定属实,但是这个推理题还是很有意思的。题目是这样的,据说有五个不同颜色的房间排成一排,每个房间里分别住着一个不同国籍的人,每个人都喝一种特定品牌的饮料,抽一种特定品牌的烟,养一种宠物,没有任意两个人抽相同品牌的香烟,或喝相同品牌的饮料,或养相同的宠物,问题是谁在养鱼作为宠物?为了寻找答案,爱因斯坦给出了十五条线索:

 

(1)、英国人住在红色的房子里;

(2)、瑞典人养狗作为宠物;

(3)、丹麦人喝茶;

(4)、绿房子紧挨着白房子,在白房子的左边;

(5)、绿房子的主人喝咖啡;

(6)、抽Pall Mall牌香烟的人养鸟;

(7)、黄色房子里的人抽Dunhill牌香烟;

(8)、住在中间那个房子里的人喝牛奶;

(9)、挪威人住在第一个房子里面;

(10)、抽Blends牌香烟的人和养猫的人相邻;

(11)、养马的人和抽Dunhill牌香烟的人相邻;

(12)、抽BlueMaster牌香烟的人和啤酒;

(13)、德国人抽Prince牌香烟;

(14)、挪威人和住在蓝房子的人相邻;

(15)、抽Blends牌香烟的人和喝矿泉水的人相邻。

 

这个题目的答案就包含在5个种类共25个元素的所有组合当中,当某一个组合能够满足以上15条线索时,就可以从中找到答案,以下就是一个满足全部线索的组合,可以看出本题的答案是住在绿色房子中的德国人养鱼作为宠物:

房子

国家

饮料

宠物

黄色

挪威

Dunhill

蓝色

丹麦

Blends

红色

英国

牛奶

PallMall

绿色

德国

咖啡

Prince

白色

瑞士

啤酒

BlueMaster

 

        用计算机解决这个问题的本质就是枚举这5个种类25个元素的所有组合,应用15条线索对每个组合进行判断,能够满足全部线索的组合就是最终的结果。和其它用穷举法算法一样,解决这个推理题也需要解决三个关键点:定义能够描述这个问题的数据模型、基于这个数据模型的一套枚举算法和应用15条线索判断结果是否正确的方法。

考察这个问题的描述,需要枚举结果的元素分为5个类别,分别是房子(颜色)、国家、饮料类型、宠物种类和香烟的品牌。根据题意,5个种类的元素不能重复,但是彼此存在联系,这个联系简单描述就是:某个国家的人只能住在某个颜色的房子中,喝一种饮料,养一种宠物并抽一种品牌的香烟。定义数据模型时可以采用“组”(group)的概念来定义这种关系,每个“组”包含5个种类的各一个元素,保证了对上述固定关系的约束。每个元素都由两个属性,一个是类型,一个是值,比如“咖啡”,其类型是饮料,值是咖啡,可以这样对元素进行定义:

61 typedef struct tagItem

62 {

63     ITEM_TYPE type;

64     int value;

65 }ITEM;

确定了元素的数据定义,“组”的数据定义就可以确定了:

107 typedef struct tagGroup

108 {

109     ITEM items[GROUPS_ITEMS];

110 }GROUP;

 

这个GROUP的数据定义虽然清晰明了,但是对GROUP内的元素的定位不是很直观,比如对GROUP内的某个元素操作时需要遍历所有的元素逐个比较类型来定位元素,这就存在一个算法的效率问题。既然GROUP内的item用数组进行组织,而数组的下标天生就具有位置关系,何不利用这一点简化数据定义呢?首先对ITEM_TYPE的值进行一些约束,为每个类型赋一个明确的值,这个值就是item数据的位置,固定了值之后的ITEM_TYPE定义如下:

42 typedef enum tagItemType

43 {

44     type_house = 0,

45     type_nation = 1,

46     type_drink = 2,

47     type_pet = 3,

48     type_cigaret = 4

49 }ITEM_TYPE;

 对GROUP也重新定义:

107 typedef struct tagGroup

108 {

109     int itemValue[GROUPS_ITEMS];

110 }GROUP;

 

这样定义GROUP可以显著简化数据定位问题,比如“住在中间那个房子里的人喝牛奶”这个线索,就可以这样用代码实现:

groups[2].itemValue[type_drink] = DRINK_MILK;

         接下来要处理15条线索的数学模型问题。先分析一下这15条线索,大致可以分成三类:第一类是描述某些元素之间具有固定绑定关系的线索,比如,“丹麦人喝茶”和“住绿房子的人喝咖啡”等等,线索1、2、3、5、6、7、12、13可归为此类;第二类是描述某些元素类型所在的“组”所具有的相邻关系的线索,比如,“养马的人和抽Dunhill牌香烟的人相邻”和“抽Blends牌香烟的人和养猫的人相邻”等等,线索10、11、14、15可归为此类;第三类就是不能描述元素之间固定关系或关系比较弱的线索,比如,“绿房子紧挨着白房子,在白房子的左边”和“住在中间那个房子里的人喝牛奶”等等。

        对于第一类具有绑定关系的线索,其数学模型可以这样定义:

67 typedef struct tagBind

68 {

69     ITEM_TYPE first_type;

70     int first_val;

71     ITEM_TYPE second_type;

72     int second_val;

73 }BIND;

first_type和first_val是一个绑定关系中前一个元素的类型和值,second_type和second_val是绑定关系中后一个元素的类型和值。以线索6“绿房子的主人喝咖啡”为例,first_type就是type_house,first_val就是COLOR_GREEN(COLOR_GREEN是个整数型常量),second_type就是type_drink,second_val就是DRINK_COFFEE(DRINK_COFFEE是个整数型常量)。线索1、2、3、5、6、7、12、13就可以存储在binds数组中:

75 const BIND binds[] =

76 {

77     { type_house, COLOR_RED, type_nation, NATION_ENGLAND },

78     { type_nation, NATION_SWEDEND, type_pet, PET_DOG },

79     { type_nation, NATION_DANMARK, type_drink, DRINK_TEA },

80     { type_house, COLOR_GREEN, type_drink, DRINK_COFFEE },

81     { type_cigaret, CIGARET_PALLMALL, type_pet, PET_BIRD },

82     { type_house, COLOR_YELLOW, type_cigaret, CIGARET_DUNHILL },

83     { type_cigaret, CIGARET_BLUEMASTER, type_drink, DRINK_BEER },

84     { type_nation, NATION_GERMANY, type_cigaret, CIGARET_PRINCE }

85 };

        对于第二类描述元素所在的“组”具有相邻关系的线索,其数学模型可以这样定义:

89 typedef struct tagRelation

90 {

91     ITEM_TYPE type;

92     int val;

93     ITEM_TYPE relation_type;

94     int relation_val;

95 }RELATION;

type和val是某个“组”内的某个元素的类型和值,relation_type和relation_val是与该元素所在的“组”相邻的“组”中与之有关系的元素的类型和值。以线索10“抽Blends牌香烟的人和养猫的人相邻”为例,type就是type_cigaret,val就是CIGARET_BLENDS(CIGARET_BLENDS是个整数型常量),relation_type是type_pet,relation_val是PET_CAT(PET_CAT是个整数型常量)。线索10、11、14、15就可以存储在relations数组中:

097 const RELATION relations[] =

098 {

099     { type_cigaret, CIGARET_BLENDS, type_pet, PET_CAT },

100     { type_pet, PET_HORSE, type_cigaret, CIGARET_DUNHILL },

101     { type_nation, NATION_NORWAY, type_house, COLOR_BLUE },

102     { type_cigaret, CIGARET_BLENDS, type_drink, DRINK_WATER }

103 };

        对于第三类线索,无法建立统一的数学模型,只能在枚举算法进行过程中直接使用它们过滤掉一些不符合条件的组合结果。比如线索8“住在中间那个房子里的人喝牛奶”,就是对每个饮料类型组合结果直接判断groups[2].itemValue[type_drink]的值是否等于 DRINK_MILK,如果不满足这个线索就不再继续下一个元素类型的枚举。再比如线索4“绿房子紧挨着白房子,在白房子的左边”,就是在对房子类型进行组合排列时,将绿房子和白房子看成一个整体进行排列组合的枚举,得到的结果直接符合了线索4的要求。

        解决了数据模型的定义,接下来就要考虑如何判定一个组合结果符合题目要求的全部线索。这个判别是关键点,如果不能正确地从上亿个组合结果中识别出正确的结果,后面将要介绍的枚举算法就成了无的放失。根据本文建立的数学模型,第三类线索直接在枚举算法部分应用,因此只需要对枚举得到的组合结果应用第一类线索和第二类线索进行过滤即可。

        具有绑定关系的线索描述的是一个“组”内两种元素之间的固定关系,判断的方法就是遍历全部的“组”,找到BIND数据中的first_type和first_val标识的元素所在的组group,然后检查group组中类型为second_type的元素的值是否等于second_val,如果group中类型为second_type对应元素的值与second_val的值不一致就直接返回检查失败,否则就说明当前的组合结果满足此BIND数据对应的线索,然后对下一个BIND数据重复上述检查过程,直到检查完binds数组中所有线索对应的BIND数据。图(1)是具有绑定关系的线索检查流程图:

图(1)具有绑定关系的线索检查流程图

 

        “组”相邻关系的线索描述的是相邻的两个组之间元素的固定关系,判断的方法就是遍历全部的“组”,找到RELATION数据中的type和val标识的元素所在的组group,然后分别检查与group相邻的两个组(第一个组和最后一个组只有一个相邻的组)中类型为relation_type的元素对应的值是否等于relation_val,如果相邻的组中没有一个能满足RELATION数据就表示当前组合结果不满足线索,直接返回检查失败。相邻的组中只要一个组中的元素满足RELATION数据描述的关系就表示当前组合结果符合RELATION数据对应的线索,需要对下一个RELATION数据重复上述检查过程,直到检查完relations数组中的全部线索对应的RELATION数据。图(2)是具有“组”相邻关系的线索检查流程图:

 

图(2)“组”相邻关系的线索检查流程图

 

【未完,“算法系列之七:爱因斯坦的思考题(下)”继续】

这篇关于算法系列之七:爱因斯坦的思考题(上) .的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/413199

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

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

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

康拓展开(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]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

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

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

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言