爱因斯坦的思考题(C++实现)
爱因斯坦的思考题(C++实现)
那位先生 发表于2年前
爱因斯坦的思考题(C++实现)
  • 发表于 2年前
  • 阅读 152
  • 收藏 11
  • 点赞 0
  • 评论 2

【腾讯云】如何购买服务器最划算?>>>   

分析点这里

/** 
 *  问题描述: 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;
}

共有 人打赏支持
粉丝 125
博文 53
码字总数 59920
评论 (2)
丹心之城
6666
丹心之城
4
×
那位先生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: