也是100个囚犯问题

sheng_jianguo

一百个犯人站成一纵列，每人头上都带上写有一个数字的帽子，数字是1至N之中随机的一个。
各人不知道自己帽子上的数字，但是只能看见自己前面所有人帽子上的数字。
然后从最后一个犯人开始，每人只能用同一种声调和音量说出1至N之中的一个数字.如果说中了自己帽子上的数字，就存活，说错了就拉出去枪毙，
犯人说的数字所有犯人都能听见，是否说对，其他犯人不知道， 在这之前，所有犯人可以聚在一起商量策略。
问如果犯人都足够聪明而且反应足够快，这100个犯人中最多保证存活（肯定不死）的有多少人？具体策略是什么？

sheng_jianguo

是题目还是问题提的不妥，为什么没人参与讨论？
N=1结论是很显然的。
N=2结论也是很简单的。
由此得出一般的N应该不是很难的。

东邪

可能是大家都知道答案吧。

当n<=100时，99个肯定可以知道自己的数字。

东邪

如果知道n，或者知道n小于某个数。
应该99个人都能说对。

sheng_jianguo

答案是99个人都能说对。
但我想要在这里讨论的是有什么较好的具体策略。

东邪

最后一个人报前面所以人之和除以N后的余数。
第99人计算前面98人之和除以N后的余数，再根据最后一个报出的数，计算出自己的数。这个数肯定正确。
第98人计算前面97人之和除以N后的余数，再根据最后两个报出的数，计算出自己的数。这个数肯定正确。
。。。。。。

第1到第99个人都是对的。
当然，如果知道n，比如n=345，可以用1000来代替n，计算可以快一点。

还能有其他方法？

sheng_jianguo

6#的思路是对的。我的解法也基本相同（稍简单些）。
但需要考虑的是，最后一个人前面所有人数字之和除以N后的余数=0时，不能报0（只能报1至N之中的一个数字）。

sheng_jianguo

我的解法是：每个犯人报的数为，N减去[前面所有人帽子上的数字及后面人报的数之和除以N后的余数]后的数。
当然，为了计算方便，可以用一个较大的数代替N，但带来的后果是，最后一个犯人被杀的可能性增大。
不知是否有更好的解法，请大家继续讨论。

mathe

题目没有说清楚.这N个人之间的号码是不是保证都是不相同的呢?题目好像没有这个保证

gxqcn

我开始也没弄明白题意：每个人是说的那个数字，是指自己帽子上的数字吗？
感觉应该是：每人要说一个数（广播给所有人听），而写出自己帽子上的数字（仅给审判员看）。
不知对否？