患有过敏的朋友们

来自计算思维百科
跳转至: 导航搜索
患有过敏的朋友们1.jpg

恰逢乔迁之喜,想请4名朋友到新家吃饭。主人会做的四种菜肴中,有些朋友们吃了会过敏。下表列出了主人会做的菜肴种类和朋友们对各个菜肴产生过敏的具体情况,○表示不过敏,×表示过敏。现在至少要让每个朋友都能吃到一种不会过敏的菜肴,最少要做几道呢?

 

披萨

炒杂菜

锅包肉

炸鸡块

佩奕

×

×

芷雅

×

×

小敏

×

×

秀芝

×

×

解决方案——蛮力法

运用蛮力法,我们从菜的数量出发,由少到多地将所有可能的做菜方式列出,依次检查看是否符合要求。

准备一道菜:

我们从表中可以看出,不存在每个朋友都能享用的菜肴,所以一道菜的情况我们不需要再一一检查。

 

披萨

炒杂菜

锅包肉

炸鸡块

佩奕

×

×

芷雅

×

×

小敏

×

×

秀芝

×

×

准备两道菜:

主人会做的四种菜肴中两两组合有6种情况,

披萨+炒杂菜

 

披萨

炒杂菜

佩奕

  芷雅  

  ×  

  ×  

小敏

×

秀芝

×

披萨+锅包肉

 

披萨

锅包肉

佩奕

×

芷雅

×

小敏

×

秀芝

×

披萨+炸鸡块

 

披萨

炸鸡块

佩奕

×

芷雅

×

  小敏  

  ×  

  ×  

秀芝

炒杂菜+锅包肉

 

炒杂菜

锅包肉

佩奕

×

芷雅

×

小敏

  秀芝  

  ×  

  ×  

炒杂菜+炸鸡块

 

炒杂菜

炸鸡块

佩奕

×

芷雅

×

小敏

×

秀芝

×

锅包肉+炸鸡块

 

锅包肉

炸鸡块

  佩奕  

  ×  

  ×  

芷雅

小敏

×

秀芝

×

所以,只有披萨+锅包肉或者炒杂菜+炸鸡块符合要求。

我们可以从第一道菜出发,考虑是否要做此道菜,对不同的情况接着对第二道菜进行同样的考虑,如此往下,我们可以建立出如下的搜索树,该搜索树中包含了所有的做菜情况,因此我们只需要对每种情况进行检测即可得到做菜方法。

患有过敏的朋友们2.png

运用的计算思维

蛮力法的思路是将从问题的一个方面出发,列出所有的解,再对解进行筛查,运用的是机械化的计算思维。

参考文献

[1]具宗万.算法问题实战策略[M].崔盛一,译.北京:人民邮电出版社,2015