首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图

发个算法题解决方案

2014-06-17 来源:读书人网 【读书人网(Reader8.cn):综合教育门户网站】
发个算法题游戏规则:本游戏人物有:杀手、平民、警察。无论几人游戏只有一个杀手,一个警察,剩下的都是平民。杀

发个算法题
游戏规则:
本游戏人物有:杀手、平民、警察。
无论几人游戏只有一个杀手,一个警察,剩下的都是平民。

杀手永远说假话
警察说话半真半假
平民永远说真话

玩家根据每个人的言语判定某人为凶手。当玩家判断正确时,则游戏结束;如果不正确,则凶手将此人杀掉,玩家少一人,游戏继续,直至最后,则剩凶手和另外一个人时,则玩家为输。

例:5人
1
A:B不是凶手
B:D是平民
C:E和B不都是平民
D:C不是警察
E:A和D都是平民

[解决办法]
根据说的话扫描出逻辑推理式,然后循环假设杀手和警察.进行归并,矛盾的话下一循环,可找到一个答案就返回,也可找到全部答案(即循环结束)再返回. 用0 1 2 分别表示三种状态,同时表示对应的真命题 半假命题 假命题.
复杂度 O(N^2), 可以剪枝优化.