娱乐 奇怪的算法挑战【第②期？】寻找宝物

[Muriya Tensei]

一座奇怪的地牢中有一件宝物，宝物存在于宝箱之中，而在这个地牢中有着无数外观相同的宝箱，你的手中却只有一把一次性的钥匙可以打开其中一个宝箱。并且一旦进入地牢，就会触发机关，如果宝物没有被拿到，那么地牢将在一定时间后重置，可能没有充足的时间来尝试检查宝箱。

万幸的是，你的巫师朋友告诉你，他能为你制作一种卷轴若干，卷轴可以花费一些时间，来探测宝物，一个卷轴可以同时探测许多的宝箱，并不会耗费更多的时间，当探测到有宝物存在时，卷轴就会碎裂，也许你就能知道宝物所在的位置了。（ps：如果没检测到的话，卷轴还能继续使用，但是每张卷轴每次检测都需要花费一定的时间）

你思维十分敏锐，选择用哪些卷轴来探测哪些宝箱并不会花费时间，并且发现宝箱之后可以瞬间将其打开拿到宝物，这样。朋友为你准备了充足的卷轴，但是告诉你，在一个地牢使用过的卷轴就没办法在其他地方使用了，因此只要你每动用了一个卷轴就给他一颗魔晶石。

已知：地牢经过 t 时间就会重置，而你的卷轴检测需要花费 c 的时间，在你进入地牢之后发现，其中有 n 个宝箱。

那么你最少需要多少魔晶石才能找到宝物呢？

 

例如：2个宝箱，1分钟后地牢重置，卷轴检测花费1分钟。

你需要 1 颗魔晶石即可。

解释：你只需要用一个卷轴就能够发现一个宝箱中是否有宝物，那么你瞬间就能知道宝物的位置并拿到，因此你只需要1颗魔晶石。

 

又如：4个宝箱，10分钟后地牢重置，卷轴检测花费7分钟。

你需要 2 颗魔晶石。

 

[子之半]

天平？次数最少？

重置啥意思？

具体重置什么，宝箱内容物的位置会不被因重置

[mamamama]

8 小时前, 子之半 说道:

天平？次数最少？

重置啥意思？

具体重置什么，宝箱内容物的位置会不被因重置

我读出来的意思是要在 t 时间内完成解谜，t/c 限制了一张卷轴一直失败的最大使用次数

[Muriya Tensei]

12 分钟前, mamamama 说道:

我读出来的意思是要在 t 时间内完成解谜，t/c 限制了一张卷轴一直失败的最大使用次数

是这个意思没有错

8 小时前, 子之半 说道:

天平？次数最少？

重置啥意思？

具体重置什么，宝箱内容物的位置会不被因重置

就是理解成一个限时任务就行，只能在规定时间内完成

[Caster库丘林]

大致理解了一下

卷轴适量的情况下需要合理规划使用

[t/c]代表的是步数，在[t/c]足够大的时候，显然最优解是二分法，对应的检查次数为[log₂n]或者[log₂n]+1

但当步数受到限制的时候，就需要考虑如何一步完成判断

一次对n个宝箱进行区分，本质上就是n个良品里找一个赝品的模型

目标是保证一次找出的同时使用的卷轴尽量少，此时对应的检查次数为n-[n/2]

综上，在步数富余的情况下缩小n的范围，再一次锁定，这样是消耗卷轴最少的方法

考虑到同一地牢内卷轴可以重复使用，那么最少的卷轴损耗就是max(x,y-[y/2])，其中x=[log₂n],y=[n/(2^x)]

而非酋的损耗甚至会高达x'+y'-[y'/2]，其中x'=[log₂n]+1,y'=[n/(2^x')]+1，可以说非常让人痛心了

十二月 16, 2021，由Caster库丘林修改

[fangaa]

二进制验证法吧。

[mamamama]

3 小时前, Caster库丘林 说道:

[t/c]代表的是步数，在[t/c]足够大的时候，显然最优解是二分法，对应的检查次数为[log₂n]或者[log₂n]+1

优化目标是最少卷轴数，应该是 t/c=1 的时候采用二进制分组，需要卷轴个数为 log₂n 上取整。而当 t/c>=n-1 的时候可以用一个卷轴一路试过去。

再后面的我没看懂了

 

盲猜答案应该是 t/c+1 进制分组，要 n 开 t/c+1 次方根个

UPD：对数对数对数……写错了

这就是做题每次见到数学题就不看的报应吗

十二月 16, 2021，由mamamama修改

[Muriya Tensei]

22 分钟前, mamamama 说道:

优化目标是最少卷轴数，应该是 t/c=1 的时候采用二进制分组，需要卷轴个数为 log₂n 上取整。而当 t/c>=n-1 的时候可以用一个卷轴一路试过去。

再后面的我没看懂了

 

盲猜答案应该是 t/c+1 进制分组，要 n 开 t/c+1 次方根个

有东西的.jpg，那么可以不盲猜来提供一下具体方法或者思路吗

十二月 16, 2021，由Muriya Tensei修改

[mamamama]

13 分钟前, Muriya Tensei 说道:

有东西的.jpg，那么可以不盲猜来提供一下具体方法或者思路吗

方法就是

35 分钟前, mamamama 说道:

t/c+1 进制分组

把 n 个箱子按 0 到 n-1 编号，把它们写成 t/c+1 进制的形式，需要的卷轴数就等于最大位数

第 0 轮（为了方便从 0 开始了）的时候第 k 个卷轴就去验所有第 k 位为 0 的箱子

第 1 轮的时候每个卷轴去验对应位为 1 的箱子

这样验 t/c 轮之后，就可以确定每一位是 0 到 t/c 中的哪个数了，也就确定了答案的编号

 

大概……应该……（小声），信息和次数全用满了

[Muriya Tensei]

45 分钟前, mamamama 说道:

方法就是

把 n 个箱子按 0 到 n-1 编号，把它们写成 t/c+1 进制的形式，需要的卷轴数就等于最大位数

第 0 轮（为了方便从 0 开始了）的时候第 k 个卷轴就去验所有第 k 位为 0 的箱子

第 1 轮的时候每个卷轴去验对应位为 1 的箱子

这样验 t/c 轮之后，就可以确定每一位是 0 到 t/c 中的哪个数了，也就确定了答案的编号

 

大概……应该……（小声），信息和次数全用满了

可以说是相当完善了，用信息熵可以确认m≥⌈log(t/c+1) n⌉，并且用进制表示的方法很简单的也能描述出m=⌈log(t/c+1) n⌉的实现方法