算法系列之七：爱因斯坦的思考题（下）

ldb19890624

浏览: 243912 次
性别:
来自: 北京

最近访客更多访客>>

caizi12

missing1314521

u012363178

halfsking

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (632)

社区版块

存档分类

CheckGroupRelation（）函数需要根据当前组group的位置进行适当的处理，如果当前组是第一个组或最后一个组，则group的相邻组只有一个，就是最靠近group的组，其它情况下group的相邻组都是两个。CheckGroupRelation（）函数的实现如下：

162bool CheckGroupRelation(GROUP *groups, int groupIdx, ITEM_TYPE type, int value)
163{
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;
}
}
186
return true;
188}

最后是枚举算法部分的说明。前面系列文章中多次使用穷举法解决问题，但都是一维线性组合的枚举，本题则有些特殊，因为需要对不同类型的元素分别用穷举法进行枚举，因此不是简单的线性组合。本文算法采用的枚举方法是对不同类型的元素分别用穷举法进行枚举，然后再进行组合，这个组合不是线性关系的组合，而是类似阶乘的几何关系的组合。具体思路就是按照group中的元素顺序，首先对房子根据颜色组合进行穷举，每得到一组房子颜色组合后，就在此基础上对住在房子里的人的国籍进行穷举，在房子颜色和国籍的组合结果基础上，在对饮料类型进行穷举，依次类推，直到穷举完最后一种类型得到完整的穷举组合。

现在来具体推算一下穷举的过程，首先是对房子颜色进行穷举。因为是5种颜色的不重复组合，因此应该有5！= 120个颜色组合结果，但是根据线索4“绿房子紧挨着白房子，在白房子的左边”，相当于绿房子和白房子有稳定的绑定关系，实际就只有4！= 24个颜色组合结果。接下来对24个房子颜色组合结果中的每一个结果再进行住户国籍的穷举，理论上国籍也有5！= 120个结果，但是根据线索9“挪威人住在第一个房子里面”，相当于固定第一个房子住得人始终是挪威人，因此就只有4！= 24个国籍组合结果。穷举完房子颜色和国籍后就已经有24 x 24 = 576个组合结果了，接下来需要对这576个组合结果中的每一个结果再进行饮料类型的穷举，理论上饮料类型也有5！= 120个结果，但是根据线索8“住在中间那个房子里的人喝牛奶”，相当于固定了一个饮料类型，因此也只有4！= 24个饮料组合类型。穷举完饮料类型后就得到了576 x 24 = 13824个组合结果，接下来对13824个组合结果中的每一个结果再进行宠物种类的穷举，这一步没有线索可用，共有5！= 120个结果。穷举完宠物种类后就得到了13824 x 120 = 1658880个组合结果，最后对1658880个组合结果中的每一个结果再进行香烟品牌的穷举，这一步依然没有线索可用，共有5！= 120个结果。穷举完香烟品牌后就得到了全部组合共1658880 x 120 = 199065600个结果，剩下的事情就是对这将近2亿个结果进行判断。

以下就是对房子颜色进行穷举的算法实现：

369/* 遍历房子颜色*/
370void EnumHouseColors(GROUP *groups, int groupIdx)
371{
if(groupIdx == GROUPS_COUNT) /*递归终止条件*/
{
ArrangeHouseNations(groups);
return;
}
377
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;
 }
387
 EnumHouseColors(groups, groupIdx + 1);
}
}
395}

EnumHouseColors（）函数每得到一个房子颜色的穷举结果，就调用ArrangeHouseNations()函数进行进一步处理。ArrangeHouseNations() 函数做的事情就是继续枚举住在每个房子里的人的国籍，但是在这之前，先要根据已知条件进行预处理。比如已知规则(9)的描述：挪威人住在第一个房子里，就可以将group[0]的国籍锁定为NATION_NORWAY，从而减少一层遍历。

361void ArrangeHouseNations(GROUP *groups)
362{
363 /*应用规则(9)：挪威人住在第一个房子里面；*/
364 groups[0].itemValue[type_nation] = NATION_NORWAY;
365 EnumHouseNations(groups, 1); /*从第二个房子开始*/
366}

实际上，真正的遍历国籍过程是在EnumHouseNations()函数中完成。EnumHouseNations()函数每得到一个完整的房子与国籍关系，就调用ArrangePeopleDrinks()函数进一步遍历每个人喝的饮料类型。

341/*遍历国家*/
342void EnumHouseNations(GROUP *groups, int groupIdx)
343{
344 if(groupIdx == GROUPS_COUNT) /*递归终止条件*/
345 {
346  ArrangePeopleDrinks(groups);
347  return;
348 }
349
350 for(int i = NATION_NORWAY; i <= NATION_GERMANY; i++)
351 {
352  if(!IsGroupItemValueUsed(groups, groupIdx, type_nation, i))
353  {
354   groups[groupIdx].itemValue[type_nation] = i;
355
356   EnumHouseNations(groups, groupIdx + 1);
357  }
358 }
359}
360

在每一组房子颜色和（住房客）国籍的对应关系上（根据前面的分析，将会有24 x 24 = 576组对应关系），ArrangePeopleDrinks()函数负责进一步排定它们和饮料类型的关系。ArrangePeopleDrinks()函数直接调用EnumPeopleDrinks()函数进行饮料类型的枚举，规则(8)：“住在中间那个房子里的人和牛奶”直接体现在EnumPeopleDrinks()函数中：

313void EnumPeopleDrinks(GROUP *groups, int groupIdx)
314{
if(groupIdx == GROUPS_COUNT) /*递归终止条件*/
{
/*应用规则(8)：住在中间那个房子里的人喝牛奶；*/
if(groups[2].itemValue[type_drink] == DRINK_MILK)
{
 ArrangePeoplePet(groups);
}
return;
}
324
for(int i = DRINK_TEA; i <= DRINK_MILK; i++)
{
if(!IsGroupItemValueUsed(groups, groupIdx, type_drink, i))
{
 groups[groupIdx].itemValue[type_drink] = i;
 EnumPeopleDrinks(groups, groupIdx + 1);
}
}
333}

在确定完饮料类型后（根据前面的分析，将会得到576 x 24 = 13824组结果），就要进一步遍历每个人养的宠物（别忘了，鱼也算宠物）。题目没有对宠物提供更多的线索，因此ArrangePeoplePet()函数就是简单的遍历全部宠物组合，得到120种人和宠物的组合：

288void EnumPeoplePats(GROUP *groups, int groupIdx)
289{
if(groupIdx == GROUPS_COUNT) /*递'b5?归'b9?终'd6?止'd6?条'cc?件'bc?*/
{
ArrangePeopleCigert(groups);
return;
}
295
for(int i = PET_HORSE; i <= PET_DOG; i++)
{
if(!IsGroupItemValueUsed(groups, groupIdx, type_pet, i))
{
 groups[groupIdx].itemValue[type_pet] = i;
301
 EnumPeoplePats(groups, groupIdx + 1);
}
}
305}

人和宠物的关系也遍历完成以后（根据前面的分析，将会得到13824 x 120 = 1658880组结果），就要最后确定每个人抽的香烟类型。关于人和香烟的关系，题目中也没有给出更多的线索，因此ArrangePeopleCigert()函数仅仅是调用EnumPeopleCigerts()函数完成120种人和香烟的组合：

264void EnumPeopleCigerts(GROUP *groups, int groupIdx)
265{
if(groupIdx == GROUPS_COUNT) /*递归终止条件*/
{
DoGroupsfinalCheck(groups);
return;
}
271
for(int i = CIGARET_BLENDS; i <= CIGARET_BLUEMASTER; i++)
{
if(!IsGroupItemValueUsed(groups, groupIdx, type_cigaret, i))
{
 groups[groupIdx].itemValue[type_cigaret] = i;
277
 EnumPeopleCigerts(groups, groupIdx + 1);
}
}
281}

每当人和香烟的关系也遍历完成后，就调用DoGroupsfinalCheck()对完整的组合进行检查，检查主要是基于Bind和Relation两种类型的线索进行检查（另一种类型的线索已经在遍历的过程中体现）。根据本文前面给出的bind和Relation两种类型的数学模型，DoGroupsfinalCheck()函数的实现非常简单，就是逐个调用前面给出的CheckGroupRelation()函数和CheckGroupBind()函数对两类关系逐个对比检查，此处就不再列出代码。

图（3）演示了在每一轮穷举过程中正确结果组合出来的过程，在我的Intel P8600 CPU上，使用单核完成全部枚举和判断共耗时26秒，得到符合全部线索的答案只有一个，就是本文开始给出的示例。