文档章节

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

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

© 著作权归作者所有

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

评论(2)

丹心之城
4
丹心之城
6666
C语言/C++编程学习强势之处的体现

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

小辰带你看世界 ⋅ 05/12 ⋅ 0

C语言/C++程序员编程学习自信心曲线图

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

小辰带你看世界 ⋅ 05/10 ⋅ 0

C语言/C++永远都不会过时的编程语言

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

小辰带你看世界 ⋅ 03/30 ⋅ 0

什么是 C 和 C ++ 标准库?

简要介绍编写C/C ++应用程序的领域,标准库的作用以及它是如何在各种操作系统中实现的。 我已经接触C++一段时间了,一开始就让我感到疑惑的是其内部结构:我所使用的内核函数和类从何而来? ...

oschina ⋅ 04/10 ⋅ 0

SWIG与JAVA 交互最全开发指南一

项目背景 最近开始研究做移动端项目,但是本人基本是做了五六年的c++的底层研发,对C++的研发可以说是驾轻就熟了,但是对于android还是属于刚入门阶段,虽然断断续续做移动端也做了一年,但是...

揽月凡尘 ⋅ 06/16 ⋅ 0

C语言/C++编程学习未来之路

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

小辰带你看世界 ⋅ 03/30 ⋅ 0

C语言/C++编程新手学习常见问题

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

小辰带你看世界 ⋅ 05/11 ⋅ 0

大神有话说之c++,还在迷茫的朋友可以来看一下

C++ 是一种中级语言,它是由 Bjarne Stroustrup 于 1979 年在贝尔实验室开始设计开发的。C++ 进一步扩充和完善了 C 语言,是一种面向对象的程序设计语言。C++ 可运行于多种平台上,如 Window...

悟空_b201 ⋅ 05/30 ⋅ 0

C语言/C++编程学习:获取电脑开机时间

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

小辰带你看世界 ⋅ 05/21 ⋅ 0

C语言/C++程序员编程基础学习代码训练

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

小辰带你看世界 ⋅ 03/27 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

从 Confluence 5.3 及其早期版本中恢复空间

如果你需要从 Confluence 5.3 及其早期版本中的导出文件恢复到晚于 Confluence 5.3 的 Confluence 中的话。你可以使用临时的 Confluence 空间安装,然后将这个 Confluence 安装实例升级到你现...

honeymose ⋅ 今天 ⋅ 0

用ZBLOG2.3博客写读书笔记网站能创造今日头条的辉煌吗?

最近两年,著名的自媒体网站今日头条可以说是火得一塌糊涂,虽然从目前来看也遇到了一点瓶颈,毕竟发展到了一定的规模,继续增长就更加难了,但如今的今日头条规模和流量已经非常大了。 我们...

原创小博客 ⋅ 今天 ⋅ 0

MyBatis四大核心概念

本文讲解 MyBatis 四大核心概念(SqlSessionFactoryBuilder、SqlSessionFactory、SqlSession、Mapper)。 MyBatis 作为互联网数据库映射工具界的“上古神器”,训有四大“神兽”,谓之:Sql...

waylau ⋅ 今天 ⋅ 0

以太坊java开发包web3j简介

web3j(org.web3j)是Java版本的以太坊JSON RPC接口协议封装实现,如果需要将你的Java应用或安卓应用接入以太坊,或者希望用java开发一个钱包应用,那么用web3j就对了。 web3j的功能相当完整...

汇智网教程 ⋅ 今天 ⋅ 0

2个线程交替打印100以内的数字

重点提示: 线程的本质上只是一个壳子,真正的逻辑其实在“竞态条件”中。 举个例子,比如本题中的打印,那么在竞态条件中,我只需要一个方法即可; 假如我的需求是2个线程,一个+1,一个-1,...

Germmy ⋅ 今天 ⋅ 0

Springboot2 之 Spring Data Redis 实现消息队列——发布/订阅模式

一般来说,消息队列有两种场景,一种是发布者订阅者模式,一种是生产者消费者模式,这里利用redis消息“发布/订阅”来简单实现订阅者模式。 实现之前先过过 redis 发布订阅的一些基础概念和操...

Simonton ⋅ 今天 ⋅ 0

error:Could not find gradle

一.更新Android Studio后打开Project,报如下错误: Error: Could not find com.android.tools.build:gradle:2.2.1. Searched in the following locations: file:/D:/software/android/andro......

Yao--靠自己 ⋅ 昨天 ⋅ 0

Spring boot 项目打包及引入本地jar包

Spring Boot 项目打包以及引入本地Jar包 [TOC] 上篇文章提到 Maven 项目添加本地jar包的三种方式 ,本篇文章记录下在实际项目中的应用。 spring boot 打包方式 我们知道,传统应用可以将程序...

Os_yxguang ⋅ 昨天 ⋅ 0

常见数据结构(二)-树(二叉树,红黑树,B树)

本文介绍数据结构中几种常见的树:二分查找树,2-3树,红黑树,B树 写在前面 本文所有图片均截图自coursera上普林斯顿的课程《Algorithms, Part I》中的Slides 相关命题的证明可参考《算法(第...

浮躁的码农 ⋅ 昨天 ⋅ 0

android -------- 混淆打包报错 (warning - InnerClass ...)

最近做Android混淆打包遇到一些问题,Android Sdutio 3.1 版本打包的 错误如下: Android studio warning - InnerClass annotations are missing corresponding EnclosingMember annotation......

切切歆语 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部