文档章节

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

那位先生_
 那位先生_
发布于 2015/10/15 00:30
字数 1302
阅读 159
收藏 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;
}

© 著作权归作者所有

共有 人打赏支持
那位先生_

那位先生_

粉丝 132
博文 61
码字总数 69487
作品 0
深圳
后端工程师
私信 提问
加载中

评论(2)

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

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

暖冰
2015/11/21
0
0
C++ STL编程轻松入门 2

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

暖冰
2015/11/21
0
0
一个典型的 C++ 程序员成长经历

1. 完整的学一遍 C++ 所有语言特性,典型书籍 "The C++ Programming Language" Part1, Part2, "C++ Primer" 感觉 C++ 像大杂烩(多编程范型),各种精妙的语法特性 (friend, virtual/RTTI, c......

晨曦之光
2012/05/16
390
0
FFLIB之FFLUA——C++嵌入Lua&扩展Lua利器

摘要: 在使用C++做服务器开发中,经常会使用到脚本技术,Lua是最优秀的嵌入式脚本之一。Lua的轻量、小巧、概念之简单,都使他变得越来越受欢迎。本人也使用过python做嵌入式脚本,二者各有特...

知然
2013/01/27
0
0
看完这 7 条,模拟 C++ 新功能只是一个小目标!

但是,即使你无法使用这些功能,也不一定要放弃它们的好处。至少不用放弃全部。 有一些方法可以使用代码中新功能的思路,更准确地传达你的意图。 当然,这些方法肯定不如使用新版本C++本身的...

CSDN资讯
2018/09/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

深入理解JVM—JVM内存模型

深入理解JVM—JVM内存模型 我们知道,计算机CPU和内存的交互是最频繁的,内存是我们的高速缓存区,用户磁盘和CPU的交互,而CPU运转速度越来越快,磁盘远远跟不上CPU的读写速度,才设计了内存...

onedotdot
36分钟前
1
0
MVC、MVCS、MVVM、MVP、VIPER等这么多架构模式哪一个好呢?

在项目开启阶段,其中一个很重要的环节就是选架构。 那么面对目前已知的这么多架构模式我们该怎么选择呢?这确实是个很让人头疼的问题! 下面我就在这里梳理一下目前常见的一些架构模式。 先...

Java干货分享
今天
4
0
简单模仿配置文件的反射机制

//Student类 public class Student { public void love() { System.out.println("python"); } } //Tesy类 public class Tesy { public static void main(String[] args) throws Exceptio......

南桥北木
今天
2
0
你真的需要了解一下CSS变量 var()的用法

当Web项目变得越来越大时,他的CSS会变得像天文数字那么大而且还变得混乱。为了帮助我们解决这个问题,新的CSS变量很快就会出现在主流浏览器中,它让开发人员能够重用并轻松编辑重复出现的C...

前端小攻略
今天
2
0
嵌入式应用选择合适的微控制器

为嵌入式应用选择微控制器有几个原因,即低成本,高集成度,增加可靠性,节省空间等。 准备所需硬件接口列表使用微控制器的基本硬件框图,准备一份微控制器需要支持的所有外设接口的列表。微...

linux-tao
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部