C++实现离散数学“五个房子，不同颜色，不同国家...”问题
1>英国人住在红色的房子里；
2>西班牙人养了一条狗；
3>挪威人住在左边的第一个房子里；
4>黄房子里的人喜欢抽kools牌的香烟；
5>抽chesterfields牌香烟的人与养狐狸的人是邻居；
6>挪威人住在蓝色房子旁边；
7>抽winston牌香烟的人养了一个蜗牛；
8>抽lucky strike牌香烟的人喜欢喝橘子汁；M
9>乌克兰人喜欢喝茶；
10>日本人抽parlianments牌的烟；
11>抽kools牌香烟的人与养马的人是邻居；
12>喜欢喝咖啡的人住在绿房子里；
13>绿房子在象牙白房子的右边；
14>中间那个房子里的人喜欢喝牛奶。
根据以上条件，请你判断哪个房子里的人养斑马？哪个房子里的人喜欢喝水？最后把所有的东西对号入座。
我主要是用回溯法求出了其中的所有组合，然后把某些事件做为已知条件经行遍历查找，
唉！虽然这样也能求出最后结果，但我感觉这样的效率还是很低，等以后有时间了再来慢慢拿改进吧！
#include <iostream>
#include<list>
#include<string>
#include<math.h>
using namespace std;
/*参数说明
1 红色、英国人、狗、橙子汁、kool
2 黄色、西班牙人、狐狸、茶、chesterfileds
3 蓝色、挪威人、蜗牛、咖啡、winston
4 绿色、乌克兰人、马、牛奶、lucky strike
5 象牙白色、日本人、斑马、水、parlianment
*/
list<list<int>> ou_quanpailie; //1到5的全排列
list<list<int>> country_list;//国籍排列
list<list<int>> drink_list;//饮料排列
list<list<int>> pet_list;//宠物排列
list<list<int>> smoke_list;//烟牌排列
list<list<int>> color_list;//颜色排列
int counter = 0;
void swap(int &a, int &b);//交换
void permute(int array[], int begin, int end);
void permute(int array[], int begin, int end)
{
list<int> in_quanpailie;
if (begin == end)
{
for(int i=0;i<5;i++)
{
in_quanpailie.push_back(array[i]);
}
ou_quanpailie.push_back(in_quanpailie);
}
else
{
for (int j = begin; j <= end; ++j)
{
swap(array[j], array[begin]);
permute(array, begin+1, end);
swap(array[j], array[begin]);
}
}
return;
}
inline void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
return;
}
struct People //记录各国人的相关信息
{
int countrty;
int pet;
int drink;
int smoke;
};
struct House//记录各个房子的相关信息
{
int color;
int addr;
People person;
};
//找出国籍的排序列
void find_country_list()
{
for(list<list<int>>::const_iterator it = ou_quanpailie.begin();it !=ou_quanpailie.end();it++)
{
list<int>::const_iterator i = (*it).begin();
if((*i)==3)
{
country_list.push_back((*it));
}
}
}
//找出饮料的排序列
void find_drink_list()
{
for(list<list<int>>::const_iterator it = ou_quanpailie.begin();it !=ou_quanpailie.end();it++)
{
list<int>::const_iterator i = (*it).begin();
++i;
++i;
if((*i)==4)
{
drink_list.push_back((*it));
}
}
}
//找出宠物的排序列
void find_pet_list()
{
for(list<list<int>>::const_iterator it = ou_quanpailie.begin();it !=ou_quanpailie.end();it++)
{
pet_list.push_back((*it));
}
}
//找出烟牌的排序列
void find_smoke_list()
{
for(list<list<int>>::const_iterator it = ou_quanpailie.begin();it !=ou_quanpailie.end();it++)
{
list<int>::const_iterator i = (*it).begin();
if((*i)==1)
{
smoke_list.push_back((*it));
}
}
}
//找颜色排列
void find_color()
{
for(list<list<int>>::const_iterator it = ou_quanpailie.begin();it !=ou_quanpailie.end();it++)
{
list<int>::const_iterator i = (*it).begin();
if((*i)==2)
{
++i;
if((*i)==3)
{
color_list.push_back((*it));
}
}
}
}
void per_people(list<list<People>> & allzueh_people)
{
list<People> list_people;
People per1,per2,per3,per4,per5;
list_people.push_back(per1);
list_people.push_back(per2);
list_people.push_back(per3);
list_people.push_back(per4);
list_people.push_back(per5);
//先给国籍赋值
for(list<list<int>>::const_iterator it = country_list.begin();it!=country_list.end();it++)
{
list<People>::iterator iper = list_people.begin();
cout<<"国籍"<<endl;
for(list<int>::const_iterator ii = (*it).begin();ii !=(*it).end();ii++,iper++)
{
(*iper).countrty = (*ii);
}
//给烟牌赋值
for(list<list<int>>::const_iterator is = smoke_list.begin();is!=smoke_list.end();is++)
{
list<People>::iterator isper = list_people.begin();
for(list<int>::const_iterator ii = (*is).begin();ii !=(*is).end();ii++,isper++)
{
(*isper).smoke = (*ii);
}
//给饮料赋值
for(list<list<int>>::const_iterator id = drink_list.begin();id!=drink_list.end();id++)
{
list<People>::iterator idper = list_people.begin();
for(list<int>::const_iterator ii = (*id).begin();ii !=(*id).end();ii++,idper++)
{
(*idper).drink= (*ii);
}
//给宠物赋值
for(list<list<int>>::const_iterator ip = pet_list.begin() ; ip!=pet_list.end(); ++ip )
{
list<People>::iterator ipper = list_people.begin();
for(list<int>::const_iterator ii = (*ip).begin();ii !=(*ip).end();ii++)
{
(*ipper).pet = (*ii);
ipper++;
}
allzueh_people.push_back(list_people);
}
}
}
}
}
//求House的排列组合
void per_house(list<list<House>> & allzuhe_house,list<list<People>> & allzueh_people)
{
list<House> House_list;
House house1,house2,house3,house4,house5;
House_list.push_back(house1);
House_list.push_back(house2);
House_list.push_back(house3);
House_list.push_back(house4);
House_list.push_back(house5);
list<House>::iterator ih=House_list.begin();
(*ih).color = 2;
(*ih).addr = 1;
++ih;
(*ih).color = 3;
(*ih).addr = 2;
++ih;
(*ih).color = 1;
(*ih).addr = 3;
++ih;
(*ih).color = 5;
(*ih).addr = 4;
++ih;
(*ih).color = 4;
(*ih).addr = 5;
//房子颜色和地址初始化完毕
for(list<list<People>>::const_iterator ip = allzueh_people.begin();ip!=allzueh_people.end();ip++)
{
ih = House_list.begin();//首先初始化房子的索引
for(list<People>::const_iterator it = (*ip).begin(); it != (*ip).end();it++,ih++)
{
(*ih).person = (*it);
}
//一组房子初始化完毕
allzuhe_house.push_back(House_list);//加载数据
}
/*
//房子颜色和地址初始化完毕
for(list<list<int>>::iterator ii = color_list.begin();ii !=color_list.end();ii++)
{ cout<<"进入颜色组赋值"<<endl;
// ih = House_list.begin();//首先初始化房子的索引
// for(list<int>::iterator ic=(*ii).begin();ic !=(*ii).end();ic++,ih++)
// {
// (*ih).color = (*ic);
// }
for(list<list<People>>::const_iterator ip = allzueh_people.begin();ip!=allzueh_people.end();ip++)
{
ih = House_list.begin();//首先初始化房子的索引
for(list<People>::const_iterator it = (*ip).begin(); it != (*ip).end();it++,ih++)
{
(*ih).person = (*it);
}
//一组房子初始化完毕
allzuhe_house.push_back(House_list);//加载数据
}
}
*/
}
//验证命题合式公式A
void check_A(list<list<House>> & result_zuhe_house)
{
list<list<House>>::size_type n = result_zuhe_house.size();
int m=0;
for(list<list<House>>::iterator it = result_zuhe_house.begin();it !=result_zuhe_house.end();)
{
list<House>::const_iterator i = (*it).begin();
//
list<list<House>>::iterator init ;
bool is_begin = false;
if(it == result_zuhe_house.begin())
{
is_begin = true;
}
else{
list<list<House>>::iterator tt = it;
init = --tt;
}
//
for(;i!=(*it).end();i++)
{
if(2==(*i).person.countrty)//先找到国家为2的房子
{ //cout<<"找到国家为2的房子了"<<endl;
break;}
}
if((*i).person.pet!=1)
{ // cout<<"删除不符合条件的房子组合"<<endl;
result_zuhe_house.erase(it);//如果不符合则删除
//
if(is_begin)
{
it = result_zuhe_house.begin();
}
else
{
it = init;
++it;
}
//
//cout<<"删除成功！"<<endl;
}
else
{
// cout<<"OK"<<endl;
++it;
}
// cout<<m<<"次"<<n<<endl;
m++;
}
}
//验证命题合式公式B
void check_B(list<list<House>> & result_zuhe_house)
{
for(list<list<House>>::iterator it = result_zuhe_house.begin();it !=result_zuhe_house.end();)
{
list<House>::const_iterator i1 = (*it).begin();
list<House>::const_iterator i2 = (*it).begin();
//
list<list<House>>::iterator init = it;
bool is_begin = false;
if(it == result_zuhe_house.begin())
{
is_begin = true;
}
else{
list<list<House>>::iterator tt = it;
init = --tt;
}
//
for(;i1!=(*it).end();i1++)
{
if((*i1).person.smoke==2)//先找到烟牌为2的房子
break;
}
for(;i2!=(*it).end();i2++)
{
if((*i2).person.pet==2)//先找到宠物为2的房子
break;
}
int i1addr = (*i1).addr;
int i2addr = (*i2).addr;
int a = i1addr-i2addr;
int abs = labs(a);
if(abs != 1)
{
result_zuhe_house.erase(it);
//
if(is_begin)
{
it = result_zuhe_house.begin();
}
else
{
it = init;
++it;
}
//
}
else{
++it;
}
}
}
//验证命题合式公式C
void check_C(list<list<House>> & result_zuhe_house)
{
for(list<list<House>>::iterator it = result_zuhe_house.begin();it !=result_zuhe_house.end();)
{
list<House>::const_iterator i = (*it).begin();
//
list<list<House>>::iterator init = it;
bool is_begin = false;
if(it == result_zuhe_house.begin())
{
is_begin = true;
}
else{
list<list<House>>::iterator tt = it;
init = --tt;
}
//
for(;i!=(*it).end();i++)
{
if((*i).person.smoke==3)//先找到烟牌为3的房子
break;
}
if((*i).person.pet!=3)
{
result_zuhe_house.erase(it);//如果不符合则删除
//
if(is_begin)
{
it = result_zuhe_house.begin();
}
else
{
it = init;
++it;
}
//
}
else{
++it;
}
}
}
//验证命题合式公式D
void check_D(list<list<House>> & result_zuhe_house)
{
for(list<list<House>>::iterator it = result_zuhe_house.begin();it !=result_zuhe_house.end();)
{
list<House>::const_iterator i = (*it).begin();
//
list<list<House>>::iterator init = it;
bool is_begin = false;
if(it == result_zuhe_house.begin())
{
is_begin = true;
}
else{
list<list<House>>::iterator tt = it;
init = --tt;
}
//
for(;i!=(*it).end();i++)
{
if((*i).person.smoke==4)//先找到烟牌为4的房子
break;
}
if((*i).person.drink!=1)
{
result_zuhe_house.erase(it);//如果不符合则删除
//
if(is_begin)
{
it = result_zuhe_house.begin();
}
else
{
it = init;
++it;
}
//
}
else{
++it;
}
}
}
//验证命题合式公式E
void check_E(list<list<House>> & result_zuhe_house)
{
for(list<list<House>>::iterator it = result_zuhe_house.begin();it !=result_zuhe_house.end();)
{
list<House>::const_iterator i = (*it).begin();
//
list<list<House>>::iterator init = it;
bool is_begin = false;
if(it == result_zuhe_house.begin())
{
is_begin = true;
}
else{
list<list<House>>::iterator tt = it;
init = --tt;
}
//
for(;i!=(*it).end();i++)
{
if((*i).person.countrty==4)//先找到国籍为4的房子
break;
}
if((*i).person.drink!=2)
{
result_zuhe_house.erase(it);//如果不符合则删除
//
if(is_begin)
{
it = result_zuhe_house.begin();
}
else
{
it = init;
++it;
}
//
}
else{
++it;
}
}
}
//验证命题合式公式F
void check_F(list<list<House>> & result_zuhe_house)
{
for(list<list<House>>::iterator it = result_zuhe_house.begin();it !=result_zuhe_house.end();)
{
list<House>::iterator i = (*it).begin();
//
list<list<House>>::iterator init = it;
bool is_begin = false;
if(it == result_zuhe_house.begin())
{
is_begin = true;
}
else{
list<list<House>>::iterator tt = it;
init = --tt;
}
//
for(;i!=(*it).end();i++)
{
if((*i).person.countrty==5)//先找到国籍为5的房子
break;
}
if((*i).person.smoke !=5)
{
result_zuhe_house.erase(it);//如果不符合则删除
//
if(is_begin)
{
it = result_zuhe_house.begin();
}
else
{
it = init;
++it;
}
//
}
else{
++it;
}
}
}
//验证命题合式公式G
void check_G(list<list<House>> & result_zuhe_house)
{
for(list<list<House>>::iterator it = result_zuhe_house.begin();it !=result_zuhe_house.end();)
{
list<House>::iterator i = (*it).begin();
//
list<list<House>>::iterator init = it;
bool is_begin = false;
if(it == result_zuhe_house.begin())
{
is_begin = true;
}
else{
list<list<House>>::iterator tt = it;
init = --tt;
}
//
for(;i!=(*it).end();i++)
{
if((*i).person.countrty==1)//先找到国籍为5的房子
break;
}
if((*i).color !=1)
{
result_zuhe_house.erase(it);//如果不符合则删除
//
if(is_begin)
{
it = result_zuhe_house.begin();
}
else
{
it = init;
++it;
}
//
}
else{
++it;
}
}
}
//验证命题合式公式H
void check_H(list<list<House>> & result_zuhe_house)
{
for(list<list<House>>::iterator it = result_zuhe_house.begin();it !=result_zuhe_house.end();)
{
list<House>::iterator i = (*it).begin();
//
list<list<House>>::iterator init = it;
bool is_begin = false;
if(it == result_zuhe_house.begin())
{
is_begin = true;
}
else{
list<list<House>>::iterator tt = it;
init = --tt;
}
//
for(;i!=(*it).end();i++)
{
if((*i).person.smoke==1)
break;
}
if((*i).color !=2)
{
result_zuhe_house.erase(it);//如果不符合则删除
//
if(is_begin)
{
it = result_zuhe_house.begin();
}
else
{
it = init;
++it;
}
//
}
else{
++it;
}
}
}
//验证命题合式公式I
void check_I(list<list<House>> & result_zuhe_house)
{
for(list<list<House>>::iterator it = result_zuhe_house.begin();it !=result_zuhe_house.end();)
{
list<House>::const_iterator i1 = (*it).begin();
list<House>::const_iterator i2 = (*it).begin();
//
list<list<House>>::iterator init = it;
bool is_begin = false;
if(it == result_zuhe_house.begin())
{
is_begin = true;
}
else{
list<list<House>>::iterator tt = it;
init = --tt;
}
//
for(;i1!=(*it).end();i1++)
{
if((*i1).person.smoke==1)//先找到烟牌为2的房子
break;
}
for(;i2!=(*it).end();i2++)
{
if((*i2).person.pet==4)//先找到宠物为2的房子
break;
}
int i1addr = (*i1).addr;
int i2addr = (*i2).addr;
int a = i1addr-i2addr;
int abs = labs(a);
if(abs != 1)
{
result_zuhe_house.erase(it);
//
if(is_begin)
{
it = result_zuhe_house.begin();
}
else
{
it = init;
++it;
}
//
}
else{
++it;
}
}
}
//验证命题合式公式J
void check_J(list<list<House>> & result_zuhe_house)
{
for(list<list<House>>::iterator it = result_zuhe_house.begin();it !=result_zuhe_house.end();)
{
list<House>::iterator i = (*it).begin();
//
list<list<House>>::iterator init = it;
bool is_begin = false;
if(it == result_zuhe_house.begin())
{
is_begin = true;
}
else{
list<list<House>>::iterator tt = it;
init = --tt;
}
//
for(;i!=(*it).end();i++)
{
if((*i).person.drink==3)
break;
}
if((*i).color !=4)
{
result_zuhe_house.erase(it);//如果不符合则删除
//
if(is_begin)
{
it = result_zuhe_house.begin();
}
else
{
it = init;
++it;
}
//
}
else{
++it;
}
}
}
//验证命题合式公式K
void check_K(list<list<House>> & result_zuhe_house)
{
for(list<list<House>>::iterator it = result_zuhe_house.begin();it !=result_zuhe_house.end();)
{
list<House>::const_iterator i1 = (*it).begin();
list<House>::const_iterator i2 = (*it).begin();
//
list<list<House>>::iterator init = it;
bool is_begin = false;
if(it == result_zuhe_house.begin())
{
is_begin = true;
}
else{
list<list<House>>::iterator tt = it;
init = --tt;
}
//
for(;i1!=(*it).end();i1++)
{
if((*i1).color==4)//先找到烟牌为2的房子
break;
}
for(;i2!=(*it).end();i2++)
{
if((*i2).color==5)//先找到宠物为2的房子
break;
}
int i1addr = (*i1).addr;
int i2addr = (*i2).addr;
int a = i1addr-i2addr;
if(a != 1)
{
result_zuhe_house.erase(it);
//
if(is_begin)
{
it = result_zuhe_house.begin();
}
else
{
it = init;
++it;
}
//
}
else{
++it;
}
}
}
string print_color(int a)//打印房子颜色
{ string str;
switch(a)
{
case 1:
str= "红色 ";
break;
case 2:
str= "黄色 ";
break;
case 3:
str= "蓝色 ";
break;
case 4:
str= "绿色 ";
break;
case 5:
str= "象白牙色";
break;
}
return str;
}
string print_country(int a)//打印国籍
{ string str;
switch(a)
{
case 1:
str= "英国人 ";
break;
case 2:
str= "西班牙人";
break;
case 3:
str= "挪威人 ";
break;
case 4:
str= "乌克兰人";
break;
case 5:
str= "日本人 ";
break;
}
return str;
}
string print_pet(int a)//打印宠物
{ string str;
switch(a)
{
case 1:
str= "狗 ";
break;
case 2:
str= "狐狸";
break;
case 3:
str= "蜗牛";
break;
case 4:
str= "马 ";
break;
case 5:
str= "斑马";
break;
}
return str;
}
string print_drink(int a)//打印饮料
{ string str;
switch(a)
{
case 1:
str= "橙子汁 ";
break;
case 2:
str= "茶 ";
break;
case 3:
str= "咖啡 ";
break;
case 4:
str= "牛奶 ";
break;
case 5:
str= "水 ";
break;
}
return str;
}
string print_smoke(int a)//打印烟牌
{ string str;
switch(a)
{
case 1:
str= "kools ";
break;
case 2:
str= "chesterfields";
break;
case 3:
str= "winston ";
break;
case 4:
str= "lucky strike ";
break;
case 5:
str= "parlianments ";
break;
}
return str;
}
int main()
{
int array[] = {1, 2, 3,4,5};
permute(array, 0, 4);//求出｛1、2、3、4、5｝的全排列
//验证排列的正确性
for(list<list<int>>::const_iterator it = ou_quanpailie.begin();it!=ou_quanpailie.end();it++)
{
for(list<int>::const_iterator ii = (*it).begin();ii !=(*it).end();ii++)
{
cout<<(*ii)<<" ";
}
cout<<endl;
}
cout<<"1到5排列验证完毕！"<<endl;
find_country_list();//找出国籍的排序列
cout<<"国籍的排序列完毕！"<<endl;
find_drink_list();//找出饮料的排序列
cout<<"饮料的排序列完毕！"<<endl;
find_pet_list();//找出宠物的排序列
cout<<"宠物的排序列完毕！"<<endl;
find_smoke_list();//找出烟牌的排序列
cout<<"烟牌的排序列完毕！"<<endl;
find_color();//找出房子颜色的排列
cout<<"房子的排序列完毕！"<<endl;
int nn = color_list.size();
if(nn==0)
{
cout<<"color_list为空"<<endl;
}
else
{
cout<<"color_list不为空"<<endl;
cout<<"大小为："<<nn<<endl;
}
list<list<People>> allzueh_people; //求people类对象的排列组合
per_people(allzueh_people);
cout<<"people排列完毕！"<<endl;
bool isoke = false;
list<list<House>> allzuhe_house;//全部房子的排列组合
// list<list<House>> result_zuhe_house;//最后结果的房子排列组合
cout<<"开始房子排序"<<endl;
per_house(allzuhe_house,allzueh_people);
cout<<"房子排序结束"<<endl;
//检查命题公式
cout<<"开始A条件检查"<<endl;
check_A(allzuhe_house);
cout<<"开始B条件检查"<<endl;
check_B(allzuhe_house);
cout<<"开始C条件检查"<<endl;
check_C(allzuhe_house);
cout<<"开始D条件检查"<<endl;
check_D(allzuhe_house);
cout<<"开始E条件检查"<<endl;
check_E(allzuhe_house);
cout<<"开始F条件检查"<<endl;
check_F(allzuhe_house);
check_G(allzuhe_house);
check_H(allzuhe_house);
check_I(allzuhe_house);
check_J(allzuhe_house);
check_K(allzuhe_house);
list<list<House>>::size_type Ler = allzuhe_house.size();
if(Ler==0)
{
cout<<"无解"<<endl;
}
else
{
for(list<list<House>>::iterator rei = allzuhe_house.begin();rei != allzuhe_house.end();rei++)
{
cout<<"结果是："<<endl;
cout<<"颜色"<<" "<<"国籍"<<" "<<"饮料"<<" "<<"宠物"<<" "<<"烟牌"<<endl;;
for(list<House>::const_iterator ri = (*rei).begin();ri !=(*rei).end();ri++)
{
cout<<print_color((*ri).color)<<" "<<print_country((*ri).person.countrty)<<" "<<print_drink((*ri).person.drink)<<" "<<print_pet((*ri).person.pet)<<" "<<print_smoke((*ri).person.smoke)<<endl;
}
}
}
}