文档章节

爱因斯坦的思考题(C++实现)

那位先生
 那位先生
发布于 2015/10/15 00:30
字数 1302
阅读 157
收藏 11

分析点这里

/** 
 *  问题描述: 5人, 住5间房. 5人不同国家, 5房不同颜色, 5人不同宠物, 5人不同饮品, 5人抽不同烟, 满足下面条件 
 *  (1)     英国人住在红色的房子里; 
 *  (2)     瑞典人养狗作为宠物; 
 *  (3)     丹麦人喝茶; 
 *  (4)     绿房子紧挨着白房子,在白房子的左边; 
 *  (5)     绿房子的主人喝咖啡; 
 *  (6)     抽Pall Mall牌香烟的人养鸟; 
 *  (7)     黄色房子里的人抽Dunhill牌香烟; 
 *  (8)     住在中间那个房子里的人喝牛奶; 
 *  (9)     挪威人住在第一个房子里面; 
 *  (10)    抽Blends牌香烟的人和养猫的人相邻; 
 *  (11)    养马的人和抽Dunhill牌香烟的人相邻; 
 *  (12)    抽BlueMaster牌香烟的人和啤酒; 
 *  (13)    德国人抽Prince牌香烟; 
 *  (14)    挪威人和住在蓝房子的人相邻; 
 *  (15)    抽Blends牌香烟的人和喝矿泉水的人相邻。 

 	output:
 	房子:3 国籍:0 饮料:3 宠物:2 香烟:0
	房子:0 国籍:3 饮料:0 宠物:3 香烟:1
	房子:1 国籍:1 饮料:4 宠物:1 香烟:2
	房子:2 国籍:4 饮料:1 宠物:4 香烟:4
	房子:4 国籍:2 饮料:2 宠物:0 香烟:3

	house:24 nation:576 drink:13824 pet:1658880 cigaret:199065600
 */
//基本模型
#include <iostream>
typedef enum tagItemType{
	type_house=0,//房子
	type_nation=1,//国籍
	type_drink=2,//饮料
	type_pet=3,//宠物
	type_cigaret=4//香烟
}ITEM_TYPE;
int count_house=0;
int count_nation=0;
int count_drink=0;
int count_pet=0;
int count_cigaret=0;
//房子颜色
const int COLOR_BLUE=0;
const int COLOR_RED=1;
const int COLOR_GREEN=2;
const int COLOR_YELLOW=3;
const int COLOR_WHITE=4;
//饮料类型
const int DRINK_TEA=0;
const int DRINK_COFFEE=1;
const int DRINK_BEER=2;
const int DRINK_WATER=3;
const int DRINK_MILK=4;
//香烟
const int CIGARET_DUNHILL=0;
const int CIGARET_BLENDS=1;
const int CIGARET_PALLMALL=2;
const int CIGARET_BLUEMASTER=3;
const int CIGARET_PRINCE=4;
//宠物
const int PET_DOG=0;
const int PET_BIRD=1;
const int PET_CAT=2;
const int PET_HORSE=3;
const int PET_FISH=4;
//国籍
const int NATION_NORWAY=0;
const int NATION_ENGLAND=1;
const int NATION_SWEDEND=2;
const int NATION_DANMARK=3;
const int NATION_GREMANY=4;

const int GROUPS_COUNT=5;
const int GROUPS_ITEMS=5;
typedef struct tagGroup{
	int itemValue[GROUPS_ITEMS];
}GROUP;
//查看一个group中房子的颜色是否是蓝色:if(group.itemValue[type_house]==COLOR_BLUE)


//线索模型
typedef struct tagBind{
	ITEM_TYPE first_type;
	int first_val;
	ITEM_TYPE second_type;
	int second_val;
}BIND;

const BIND binds[]={
	{type_house,COLOR_RED,type_nation,NATION_ENGLAND},			//(1)
	{type_nation,NATION_SWEDEND,type_pet,PET_DOG},				//(2)
	{type_nation,NATION_DANMARK,type_drink,DRINK_TEA},			//(3)
	{type_house,COLOR_GREEN,type_drink,DRINK_COFFEE},			//(5)
	{type_cigaret,CIGARET_PALLMALL,type_pet,PET_BIRD},			//(6)
	{type_house,COLOR_YELLOW,type_cigaret,CIGARET_DUNHILL},		//(7)
	{type_cigaret,CIGARET_BLUEMASTER,type_drink,DRINK_BEER},	//(12)
	{type_nation,NATION_GREMANY,type_cigaret,CIGARET_PRINCE}	//(13)
};
//线索模型
typedef struct tagRelation{
	ITEM_TYPE type;
	int val;
	ITEM_TYPE relation_type;
	int relation_val;
}RELATION;

const RELATION relations[]={
	{type_cigaret,CIGARET_BLENDS,type_pet,PET_CAT},				//(10)
	{type_pet,PET_HORSE,type_cigaret,CIGARET_DUNHILL},			//(11)
	{type_nation,NATION_NORWAY,type_house,COLOR_BLUE},			//(14)
	{type_cigaret,CIGARET_BLENDS,type_drink,DRINK_WATER}		//(15)
};
void EnumHouseColors(GROUP *groups,int groupIdx);
void EnumHouseNations(GROUP *groups,int groupIdx);
void EnumHouseDrinks(GROUP *groups,int groupIdx);
void EnumHousePat(GROUP *groups,int groupIdx);
void EnumHouseCigarets(GROUP *groups,int groupIdx);

void ArrangeHouseNations(GROUP *groups);
void ArrangeHouseDrinks(GROUP *groups);
void ArrangePeoplePat(GROUP *groups);
void ArrangeHousePat(GROUP *groups);
void ArrangeHouseCigert(GROUP *groups);

int GetGroupItemValue(GROUP *group,ITEM_TYPE type){
	return group->itemValue[type];
}
int FindGroupIndexByItem(GROUP *groups,ITEM_TYPE type,int value){
	for(int i=0;i<GROUPS_COUNT;i++){
		if(groups[i].itemValue[type]==value){
			return i;
		}
	}
	return -1;
}
bool CheckGroupRelation(GROUP *groups,int groupIdx,ITEM_TYPE type,int value){
    if(groupIdx==0){
        if(GetGroupItemValue(&groups[groupIdx+1],type)!=value){
            return false;
        }
    }else if(groupIdx==(GROUPS_COUNT-1)){
        if(GetGroupItemValue(&groups[groupIdx-1],type)!= value){
            return false;
        }
    }else{
        if((GetGroupItemValue(&groups[groupIdx-1],type)!=value)&&(GetGroupItemValue(&groups[groupIdx+1],type)!=value)){
            return false;
        }
    }
    return true;
}
void DoGroupsfinalCheck(GROUP *groups){
	int i=0;
	for(i=0;i<sizeof(relations)/sizeof(RELATION);i++){
		int group=FindGroupIndexByItem(groups,relations[i].type,relations[i].val);
		if(group>=0){
			if(!CheckGroupRelation(groups,group,relations[i].relation_type,relations[i].relation_val)){
				return;
			}
		}
	}
	for(i=0;i<sizeof(binds)/sizeof(BIND);i++){
		int group=FindGroupIndexByItem(groups,binds[i].first_type,binds[i].first_val);
		if(group>=0){
			if(groups[group].itemValue[binds[i].second_type]!=binds[i].second_val){
				return;
			}
		}
		else{
			return;
		}
	}
	std::cout<<"find result!!!"<<std::endl;
	for(i=0;i<GROUPS_COUNT;i++){
		std::cout<<"房子:"<<groups[i].itemValue[type_house]<<" ";
		std::cout<<"国籍:"<<groups[i].itemValue[type_nation]<<" ";
		std::cout<<"饮料:"<<groups[i].itemValue[type_drink]<<" ";
		std::cout<<"宠物:"<<groups[i].itemValue[type_pet]<<" ";
		std::cout<<"香烟:"<<groups[i].itemValue[type_cigaret]<<" ";
		std::cout<<std::endl;
	}
}
bool IsGroupItemValueUsed(GROUP *groups,int groupIdx,ITEM_TYPE type,int i){
	if(groupIdx==0){
		return false;
	}
	else{
		for(int j=0;j<groupIdx;j++){
			if(groups[j].itemValue[type]==i){
				return true;
			}
		}
		return false;
	}
}
void EnumHouseColors(GROUP *groups,int groupIdx){
	if(groupIdx==GROUPS_COUNT){
		count_house++;
		ArrangeHouseNations(groups);//继续枚举国籍
		return;
	}
	for(int i=COLOR_BLUE;i<=COLOR_YELLOW;i++){
		if(!IsGroupItemValueUsed(groups,groupIdx,type_house,i)){
			groups[groupIdx].itemValue[type_house]=i;
			if(i==COLOR_GREEN){//绿房子紧挨着白房子,在白房子的左边 //(4)
				groups[++groupIdx].itemValue[type_house]=COLOR_WHITE;
			}
			EnumHouseColors(groups,groupIdx+1);
			if(i==COLOR_GREEN){
				groupIdx--;
			}
		}
	}
}
void ArrangeHouseNations(GROUP *groups){
	//挪威人住在第一个房子里面 									//(9)
	groups[0].itemValue[type_nation]=NATION_NORWAY;
	EnumHouseNations(groups,1);//从第二个房子开始
}
void EnumHouseNations(GROUP *groups, int groupIdx){
    if(groupIdx == GROUPS_COUNT){/*递归终止条件*/
		// for(int j=0;j<GROUPS_COUNT;j++){
		// 	std::cout<<j<<"的国籍为"<<groups[j].itemValue[type_nation];
		// }
		// std::cout<<std::endl;
		count_nation++;
        ArrangeHouseDrinks(groups);
        return;
    }
    for(int i = NATION_NORWAY; i <= NATION_GREMANY; i++){
        if(!IsGroupItemValueUsed(groups, groupIdx, type_nation, i)){
        	//std::cout<<"设置"<<groupIdx<<"的国籍为"<<i<<std::endl;
            groups[groupIdx].itemValue[type_nation] = i;
            EnumHouseNations(groups, groupIdx + 1);
        }
    }
}
//枚举饮料
void ArrangeHouseDrinks(GROUP *groups){
	EnumHouseDrinks(groups,0);
}
void EnumHouseDrinks(GROUP *groups, int groupIdx){
    if(groupIdx == GROUPS_COUNT){ /*递归终止条件*/
        if(groups[2].itemValue[type_drink] == DRINK_MILK){/*应用规则(8):住在中间那个房子里的人喝牛奶;*/
			count_drink++;
            ArrangeHousePat(groups);
        }
        return;
    }
    for(int i = DRINK_TEA; i <= DRINK_MILK; i++){
        if(!IsGroupItemValueUsed(groups, groupIdx, type_drink, i)){
            groups[groupIdx].itemValue[type_drink] = i;
            EnumHouseDrinks(groups, groupIdx + 1);
        }
    }
}
//枚举宠物
void ArrangeHousePat(GROUP *groups){
	EnumHousePat(groups,0);
}
void EnumHousePat(GROUP *groups, int groupIdx){
	if(groupIdx == GROUPS_COUNT){
		count_pet++;
        ArrangeHouseCigert(groups);
        return;
    }
    for(int i = PET_DOG; i <= PET_FISH; i++){
        if(!IsGroupItemValueUsed(groups, groupIdx, type_pet, i)){
            groups[groupIdx].itemValue[type_pet] = i;
            EnumHousePat(groups, groupIdx + 1);
        }
    }	
}
//枚举香烟
void ArrangeHouseCigert(GROUP *groups){
	EnumHouseCigarets(groups,0);
}
void EnumHouseCigarets(GROUP *groups, int groupIdx){
    if(groupIdx == GROUPS_COUNT){
    	count_cigaret++;
        DoGroupsfinalCheck(groups);
        return;
    }
    for(int i = CIGARET_DUNHILL; i <= CIGARET_PRINCE; i++){
        if(!IsGroupItemValueUsed(groups, groupIdx, type_cigaret, i)){
            groups[groupIdx].itemValue[type_cigaret] = i;
            EnumHouseCigarets(groups, groupIdx + 1);
        }
    }
}
int main(){
	GROUP *groups=new GROUP[5];
	EnumHouseColors(groups,0);
	std::cout<<"house:"<<count_house<<" nation:"<<count_nation<<" drink:"<<count_drink<<" pet:"<<count_pet<<" cigaret:"<<count_cigaret<<std::endl;
}

© 著作权归作者所有

共有 人打赏支持
那位先生
粉丝 131
博文 59
码字总数 65305
作品 0
深圳
后端工程师
加载中

评论(2)

丹心之城
4
丹心之城
6666
C++ STL编程轻松入门 3

2 牛刀小试:且看一个简单例程   2.1 引子   如果你是一个纯粹的实用主义者,也许一开始就可以从这里开始看起,因为此处提供了一个示例程序,它可以带给你有关使用STL的最直接的感受。是...

暖冰
2015/11/21
0
0
【转载】数据结构利器之私房STL

数据结构利器之私房STL 此系列的文章适合初学有意剖析STL和欲复习STL的同学们。 学过c++的同学相信都有或多或少接触过STL。STL不仅仅是c++中很好的编程工具(这个词可能有点歧义,用类库更恰...

悠米海
2012/12/02
0
0
C++ STL编程轻松入门 2

1.3.3 STL和GP,GP和OOP   正如前面所提到的,在STL的背后蕴含着泛型化程序设计(GP)的思想,在这种思想里,大部分基本算法被抽象,被泛化,独立于与之对应的数据结构,用于以相同或相近的...

暖冰
2015/11/21
0
0
C语言/C++编程学习强势之处的体现

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
05/12
0
0
CSDN回帖得分大全(近两年)

√ vs2005调用dll的时候Initialize()函数返回错误 [VC/MFC 基础类] √ 为什么我创建登陆框之后,然后获取登陆框的数据时候总是出现非法操作! [VC/MFC 界面] √ CFileFind::FindFile 支持通配...

junwong
2012/03/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Mac OS X下Maven的安装与配置

Mac OS X 安装Maven: 下载 Maven, 并解压到某个目录。例如/Users/robbie/apache-maven-3.3.3 打开Terminal,输入以下命令,设置Maven classpath $ vi ~/.bash_profile 添加下列两行代码,之后...

TonyStarkSir
今天
3
0
关于编程,你的练习是不是有效的?

最近由于工作及Solution项目的影响,我在重新学习DDD和领域建模的一些知识。然后,我突然就想到了这个问题,以及我是怎么做的? 对于我来说,提升技能的项目会有四种: 纯兴趣驱动的项目。即...

问题终结者
今天
4
0
打开eclipse出现an error has occurred see the log file

解决方法: 1,打开eclipse安装目录下的eclipse.ini文件; 2,打开的文本文件最后添加一行 --add-modules=ALL-SYSTEM 3,保存重新打开Eclipse。...

任梁荣
昨天
4
0
搞定Northwind示例数据库,无论哪个版本的SQLServer都受用

Northwind数据库 从这里可以找到突破口: http://social.msdn.microsoft.com/Forums/zh-CN/Vsexpressvb/thread/8490a1c6-9018-40c9-aafb-df9f79d29cde 下面是MSDN: http://msdn2.microsoft......

QQZZFT
昨天
1
0
mysql主从同步,安装配置操作

准备 两台mysql服务,我这里准备了如下: 主库:192.168.176.128 从库:192.168.176.131 如何在Linux上安装mysql服务,请看https://blog.csdn.net/qq_18860653/article/details/80250499 操作...

小致dad
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部