c++逻辑判断

来源：百度知道 编辑：UC知道 时间：2024/05/17 06:57:55
[例题3] 逻辑判断（TOJ1130）
小卡卡从Pascal神庙附近的居民那里还了解到，远古时候的Pascal圣地居住着三种居民：永远说真话的神，永远说假话的恶魔和在白天说假话，在夜里说真话的Pascal人。小卡卡想，是否能根据远古居民的话来判断他们都是那种类型的居民。
有五个居民A，B，C，D，E。他们说的话只有3种：
1.I am [not] divine/evil/human.
2.X is [not] divine/evil/human.
3.It is day/night.
居民们说话的总数不超过50。你的任务就是通过居民们说的话来判断他们的种类以及现在是白天还是黑夜。

这道题目是一道经典的穷举题。在这道题目中，我们首先可以计算出，我们需要穷举的东西——人们的属性和白天或黑夜。显而易见，五个人的属性与白天黑夜至多需要穷举 3*3*3*3*3*2=486，因为人数可能不到 5 个。而我们又不能想出更好的方法。于是我们就采用了穷举，作为这道题的正确算法。在穷举上，我们有一个经典的“加一算法”来遍历。具体方法是这样的：我们设五个人的属性分别有 0/1/2 三种情况，则我们可以用“三进制”计算得到 243 种情况，具体方法我们列几个：具体方法说明五人状态
开始0 0 0 0 0
末位加一0 0 0 0 1
末位加一0 0 0 0 2
进位0 0 0 1 0
末位加一0 0 0 1 1
末位加一0 0 0 1 2
进位0 0 0 2 0
末位加一0 0 0 2 1
末位加一0 0 0 2 2
进位再进位0 0 1 0 0
依照这样的方法，可以穷举每个人的状态，并且判断是否与供词符合。