300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | Русский珠玑妙算
游戏次数: 445808
数字个数 | 0 | ||
数位的范围 1.. | 0 | ||
一个数字可能出现的最大次数 | 0 | ||
最多可尝试次数 | 0 |
- 我们不说一个数字 "出现在答案中",而是说这个数字是 "热"的,不说它 "不在答案中",而是说它 是"冷"的。
- 一般普通的策略是找到
- 所有热数字和
- 它们的位置
- 在下面的指南中,我们将遵循两个原则,来尝试
- 通过每次猜测获得最大信息量,以及
- 通过每次猜测获得最大信息量,以及
- 这两个原则在某种程度上是相互矛盾的。例如,一个猜测的修改越少,提交下一个猜测就越容易解释结果,但需要的猜测就越多。以下指南将尝试遵循这两个原则。
有用的工具:
- 这个列表可以让我们划掉冷数字,并对热数字使用下划线。
- 如果答案有N个数字,并且可能出现 M 个数字(1,2,...,M),那么画一个排除表(例如用铅笔在纸上画)是很有帮助的,该表有 N 列(答案中的每个数字一列)和 M 行(每个可能的数字一行)。每当知道某个数字不在某个位置时,表格中的某个字段就被划掉。另一方面,如果一个数字已知在某一位置,那么该列中的所有其他字段都可以被划掉。如果每个数字只能出现一次,那么该行其他所有字段也可以被划掉。
-
- 如果结果是所有或大多数猜测的数字都是 "热"的,那很幸运,但如果两个返回的数字都是 0,我们也能获得很多信息,因为猜测的数字没有一个出现在答案中,也就是说所有猜测的数字都是"冷"的。在这种情况下,我们可以从可能的数字列表中划去 N 个数字,或者排除表中的 N 行。
-
- 假设答案有 4 个数字,数字 1,...,9 最多可能出现一次(否则修改后面3句)。对于包含 4 个数字的答案,我们将猜测 1,2,3,4,然后猜测 5,6,7,8,并通过计算 1,...,8 中有多少个数字是 "热"的,自动知道 9 的情况。如果有四个热数字,那么 9 就是"冷"的,否则就是 "热"的。如果我们很幸运,1,2,3,4 已经是 "热"的,那么我们就不用再尝试其他数字,因为它们是"冷"的。
- 假设我们做了几次猜测,比如7次,之后就知道每个数字是热还是冷。
- 猜测并知道所有的热数字或所有的冷数字似乎同样有用,因为知道一组数字,就能知道另一组数字。但事实并非如此。如果我们的猜测主要是包含热数字,那么我们还会收集到关于这些热数字正确或不正确位置的额外信息。如果我们的猜测主要是包含冷数字,就不会收集到这些信息。
-
- 原则 1 因为我们另外还会收集到有关位置的信息,这些信息在我们知道所有热数字位置时将会很有用。
-
- 为了遵循原则 2,我们可以进行一个猜测并修改,把其中一个数字拿出来,比如 5,再把另一个数字放进去,比如3。如果新的猜测热数字变少,那么5就是热数字,3是冷数字。如果新的猜测热数字变多,那么 5 是冷数字,3 是热数字。否则 5 和 3 同样都是热数字或都是冷数字。为了区分这两种情况,可以在下一个猜测中同时放 5 和 3。当决定哪一个猜测要修改一个数字时,我们遵循之前的提示,选择一个之前有最多热数字的猜测,来收集关于位置的信息并遵循原则 1 。
- 假设你按照前面的提示,提交了一个猜测,然后只交换一个数字,比如 7 换成 3,从结果中得知新的数字 3 是热数字,7 是冷数字。
-
- 不,你现在可以回到之前的猜测,利用 3 是热数字和 7 是冷数字的信息来从之前的猜测中推断出更多的信息。 例如,先前的猜测包括 3 并且只有一个热数字,然后该猜测中的其他数字就是冷数字。 它们是冷数字的事实可能会给你一个线索,能从其他猜测中知道其他哪些数字是热数字等等。
-
- 如果决定了下一次猜测中应该包含哪些数字,那么以什么顺序放置它们是否重要?
- 一旦我们知道了所有的热数字,也就知道了所有的冷数字,并且可以在排除表中划掉它们所在的行。
-
- 如果所有猜测的数字都在正确的位置,那么当然是我们很幸运解决了这个问题。另一个幸运的结果是,当猜到的数字都不在正确的位置时,我们也会得到很多信息,可以在排除表中划掉 N 个字段。
-
- 如果冷数字的所有行都被划掉,并且如果有一行或一列只有一个字段没有被划掉,那么这就告诉我们数字在答案中的具体位置,并且该列中剩余的空白字段也可以被划掉 。 如果每个数字只能出现一次,则该行中的其他字段也可以被划掉。
-
- 每个这样的数字序列称为一个排列组合。 所以问题可以理解为:N 个数字有多少种排列组合?
如果所有数字都不同,那么第一个数字就有 N 种排列组合。 对于这 N 个数字中的每一个,第二个数字都有 N-1 种排列组合。 对于这些 Nx(N-1) 组合中的每一个数字,第三个数字都有 N-2 种排列组合,依此类推,总共有 Nx(N-1x...x2x1 = N!(称为 N 阶乘)种排列组合。
如果不是所有数字都不同,那么我们可以有,例如,N=4,4 个热数字是 2,2,2,5。 然后 N! = 4! 必须除以3! 因为三个 2 之间的顺序一样。 我们将得到 4!/3! = 24/6 = 4(或 4!/3!= 4x3!/ 3!= 4)。 -
- 如果每个数字只出现一次,可以得到3!=3x2x1=6和4!=4x3! = 24个排列组合(序列)。排列方式并不是很多。
-
- 我们可以写下所有的数字(N 个热数字的排列组合),并根据先前的所有猜测逐一检验它们。通常情况下,这些数字中只有一两个是可能的,我们可以尝试将它们进行下一个猜测。
- 每个这样的数字序列称为一个排列组合。 所以问题可以理解为:N 个数字有多少种排列组合?
注意:经过猜测,我们可能知道答案一定是什么,但我们仍然需要提交答案来向计算机证明我们找到了答案。
- 下表显示了不同的 N(答案的数字位数),M(允许的位数),我们按照上面的提示,需要的平均猜测次数 G。你能与之相匹配,甚至在此基础上加以改进并更快地解决问题吗?
N | M | G |
---|---|---|
3 | 6 | 5 |
3 | 9 | 7 |
4 | 9 | 6 |
关注或订阅更新: