有七个颜色不同的方块,需要将它们放到各自的对应位置。每次放置一批方块后,系统会告知其中有多少个方块放错了位置(但不告知具体是哪些)。请问在最坏情况下,最少需要多少次试探才能确定每个方块的正确位置?请给出策略和次数。
考察说明
考察信息论与组合优化思维,以及最少探测次数上界的构造能力
回答思路
- 明确问题本质是组合排列确定问题,对应信息论下界
- 能给出系统化策略而非随机试探
- 构造最坏情况下可达的上界,并说明原因
- 讨论能否通过分组放置降低次数
- 说明如何利用每次反馈的计数信息排除排列
考察信息论与组合优化思维,以及最少探测次数上界的构造能力