[原创]青蛙的死法(已解)

漆黑之王 2019-7-4 6458

题目为本人原创的(其实就是用了一样的原理,换汤不换药)

题目:

一共有1~100号的笼子,其中有两种笼子,一种是空笼子,一种是有蛇的笼子

笼子的摆放方式,有一种特点,假如说50号的笼子是蛇笼子,那么50号以下到1号就一定是空笼子,50号以上到100号就一定是蛇笼子

你手里有两只青蛙,如果投放到空笼子里,青蛙会快速的自己爬出来,如果投放到蛇笼子里,青蛙就会被吃掉,没有被吃掉的青蛙可以反复利用

如何用最效率的方法测出有多少空笼子呢

最后于 2019-7-12 被漆黑之王编辑 ,原因:
拖入深渊吧!!!
最新回复 (32)
  • 幻梦丷 2019-7-4
    0 2
    直接丢到50号笼子,如果青蛙死了,那就从100号开始往前丢青蛙,如果青蛙没死,就再把青蛙丢到25号看看死没死,没死就继续对半丢,丢到12号,6号。。。以此类推直到出现青蛙死了,然后另一只就从上一个没死的那个笼子编号往前一个一个丢直到最后一个青蛙死掉
    我才是最最最最萌的萌新~
  • 漆黑之王 2019-7-4
    0 3
    幻梦丷 直接丢到50号笼子,如果青蛙死了,那就从100号开始往前丢青蛙,如果青蛙没死,就再把青蛙丢到25号看看死没死,没死就继续对半丢,丢到12号,6号。。。以此类推直到出现青蛙死了,然后另一只就从上一个没死 ...
    确实可以这样解答,但是如果是限制你只能用两只青蛙,你这种方法只能算半猜,可能会消耗掉很多青蛙,所以不算是最效率的
    拖入深渊吧!!!
  • 漆黑之王 2019-7-4
    0 4
    幻梦丷 直接丢到50号笼子,如果青蛙死了,那就从100号开始往前丢青蛙,如果青蛙没死,就再把青蛙丢到25号看看死没死,没死就继续对半丢,丢到12号,6号。。。以此类推直到出现青蛙死了,然后另一只就从上一个没死 ...
    还有,虽然我理解你说的,但是你说的和我题目有点不一样
    拖入深渊吧!!!
  • 幻梦丷 2019-7-4
    1 5
    漆黑之王 确实可以这样解答,但是如果是限制你只能用两只青蛙,你这种方法只能算半猜,可能会消耗掉很多青蛙,所以不算是最效率的
    的确限制了两个青蛙啊,假设青蛙为1和2号,先把1号丢进50号笼子,1号没死,那就把1号丢到75号笼子,还没死就丢到87号笼子,直到1号青蛙死了,然后如果1号青蛙死在了93号笼子,那就把2号青蛙从75号笼子一个一个往后丢,直到2号青蛙也死了,死的那个笼子往后就全是有蛇的了,同理,如果50号笼子的1号青蛙一开始就死了,那就把2号青蛙从1号笼子开始一个一个往前丢,直到2号青蛙也死了,死的那个笼子编号往后就是有蛇的
    我才是最最最最萌的萌新~
  • 漆黑之王 2019-7-4
    0 6
    幻梦丷 的确限制了两个青蛙啊,假设青蛙为1和2号,先把1号丢进50号笼子,1号没死,那就把1号丢到75号笼子,还没死就丢到87号笼子,直到1号青蛙死了,然后如果1号青蛙死在了93号笼子,那就把2号青蛙从75号 ...
    那如果是从24号开始有蛇呢,你的方法从50号开始测,如果死了就要到25号,那么如果从24开始,就会被直接被消耗掉两只,且还不一定能测出来
    拖入深渊吧!!!
  • 漆黑之王 2019-7-4
    0 7
    漆黑之王 那如果是从24号开始有蛇呢,你的方法从50号开始测,如果死了就要到25号,那么如果从24开始,就会被直接被消耗掉两只,且还不一定能测出来
    那么你的方法并不一定能测出来,也不一定能用两只青蛙就肯定能够测试出结果,所以不是最效率的
    拖入深渊吧!!!
  • 幻梦丷 2019-7-4
    0 8
    漆黑之王 那如果是从24号开始有蛇呢,你的方法从50号开始测,如果死了就要到25号,那么如果从24开始,就会被直接被消耗掉两只,且还不一定能测出来
    我说的是50号如果死了,就从1号开始
    我才是最最最最萌的萌新~
  • 幻梦丷 2019-7-4
    0 9
    看清楚哦
    我才是最最最最萌的萌新~
  • 漆黑之王 2019-7-4
    0 10
    幻梦丷 我说的是50号如果死了,就从1号开始
    那显然不是最优解啊,一个个笼子往上丢,的确可以不消耗掉最后一个,但是如果是49号,你就试49次才能试出来,一个个往上丢也显然不是最优解
    拖入深渊吧!!!
  • Roogle 2019-7-4
    2 11

    问题逆推:要想测出空笼子必须保证每次投放时青蛙活着,要想最大效率必须保证投放青蛙次数最少

    @幻梦 给出的答案其实在日常生活中算是比较效率的一种解法了,它属于二分法,也是我们日常可用的比较多的一种思路。不过这里可以稍微优化一下,青蛙活着的概率为1/2,不考虑2只A,B青蛙同时投放,那么将1-100按照二分法分为1-50和50-100两段,A青蛙在1-50范围内继续二分,那就首先将A投入25内,因为按照笼子排放规律25号肯定比50号青蛙生存的概率更高,号越大青蛙生存概率越低,如果A在25号死了,那么B就投放13号,依此类推,如果A在25号没死,那么继续将A投放在(25+100)/2 =62.5的位置,选则投放62号,依此类推,这种方法即使最终得不出结果,那锁定的笼子范围相对来说也是比较小的范围了。

    🐏阳了
  • 联盟X 2019-7-4
    1 12
    楼上的人各种意义上很不得了
    匡扶汉室!
  • 漆黑之王 2019-7-4
    0 13
    Roogle 问题逆推:要想测出空笼子必须保证每次投放时青蛙活着,要想最大效率必须保证投放青蛙次数最少@幻梦 给出的答案其实在日常生活中算是比较效率的一种解法了,它属于二分法,也是我们日常可用的比 ...
    罗格说的思路上比梦梦要清楚不少呢,就效率上来说确实是蛮有效率的一种方法之一,但是一旦涉及一定要测出有几个空笼子这样的问题,虽然高效的,但也不是最优解,毕竟要求出空笼子的数量~
    拖入深渊吧!!!
  • 0 14
    由题可知,第一号笼子一定是空的。假设第1到第
    n-1号笼子都是空笼子(2≤n≤100,n是整数),那么称第n号笼子为“蛇头笼”。那么题目就变成找到蛇头笼的最佳方法。而由于蛇头笼第2到第100号笼子的可能性都相等,且青蛙数量有限,所以  的方法实际上就是最简单的方法了,即用青蛙A去探测出蛇头笼是位于2到50号还是51到100号,若A死了,则位于2到50号,再用B从2号开始往后一个一个试,最多试到49号;若A没死,则蛇头笼位于51到100号,继续用二分法,用A测,不断地缩小范围,直到A死了,再用B在已知的范围内从前往后一个一个试,不过要是第100号就是蛇头笼的话,则A永远不会死。
    我所期望的永恒
  • 0 15
    蛇头笼可能是2-100号中的任意一个笼子。在我们用青蛙对其进行探测前,蛇头笼的位置一直处于未知状态——它可能位于99个笼子中的任意一个。假设把笼子的出口堵住,不让青蛙出来,又因为笼子处于既可能有蛇,又可能没蛇的叠加状态,所以笼子里的青蛙处于既可能活着又可能死的叠加状态,这就是漆黑王的蛙。
    我所期望的永恒
  • 漆黑之王 2019-7-5
    0 16
    萌萌的creeper娘 蛇头笼可能是2-100号中的任意一个笼子。在我们用青蛙对其进行探测前,蛇头笼的位置一直处于未知状态——它可能位于99个笼子中的任意一个。假设把笼子的出口堵住,不让青蛙出来,又因为笼子处于既可能有蛇,又 ...
    你在玩梗吧,对吧,你一定在玩梗233
    拖入深渊吧!!!
  • 0 17
    漆黑之王 你在玩梗吧,对吧,你一定在玩梗233
    所以说你所认为的标准答案到底是什么啊
    我所期望的永恒
  • 云淡风清 2019-7-6
    0 18
    直接在1号和100号丢青蛙,不死的话,就一直往中间移,完美
    这个人很懒,什么也没有留下!
  • 漆黑之王 2019-7-6
    0 19
    云淡风清 直接在1号和100号丢青蛙,不死的话,就一直往中间移,完美
    如果手头只有一只青蛙,确实这样才能准确的测出来,但是如果手头有两只就不一样了,这就不是最效率的做法了
    拖入深渊吧!!!
  • 漆黑之王 2019-7-6
    0 20
    如果晚上还没有人答题的话,我就直接说了~
    拖入深渊吧!!!
  • 云淡风清 2019-7-6
    0 21
    漆黑之王 如果手头只有一只青蛙,确实这样才能准确的测出来,但是如果手头有两只就不一样了,这就不是最效率的做法了
    啊,我懂你题意思了,我理解成是中间有一段是蛇的,两端是空的了,我要再想想
    这个人很懒,什么也没有留下!
  • 漆黑之王 2019-7-6
    0 22
    云淡风清 啊,我懂你题意思了,我理解成是中间有一段是蛇的,两端是空的了,我要再想想
    不是啦,多看看题目啦,我用来误导理解的~
    拖入深渊吧!!!
  • 云淡风清 2019-7-6
    0 23
    漆黑之王 不是啦,多看看题目啦,我用来误导理解的~
    恭喜你成功误导我了。那就放在50号,死了就拿另一个从1号开始;不死就放到75号。如此循环
    这个人很懒,什么也没有留下!
  • 漆黑之王 2019-7-6
    0 24
    云淡风清 恭喜你成功误导我了。那就放在50号,死了就拿另一个从1号开始;不死就放到75号。如此循环
    你说的和上面的几位差不多哦,问题在于二分法的解答并不是这题,在我这里最效率的
    拖入深渊吧!!!
  • 云淡风清 2019-7-6
    0 25
    放弃算了
    这个人很懒,什么也没有留下!
  • 漆黑之王 2019-7-6
    0 26
    云淡风清 放弃算了
    没关系,摸摸头~
    拖入深渊吧!!!
  • Silence 2019-7-12
    0 27
    让第一只一直活下去直到试出笼子的期望,
    等于第一只死掉后第二只从头开始试的期望。
    未知笼子数×(1-x/未知笼子数)^x<1求极值,
    取整不是很方便,先试21或22,
    不知道对不对。
    一个莫得理智的方舟Doctor
  • 漆黑之王 2019-7-12
    0 28
    Silence 让第一只一直活下去直到试出笼子的期望, 等于第一只死掉后第二只从头开始试的期望。 未知笼子数×(1-x/未知笼子数)^x
    不对哦~~
    拖入深渊吧!!!
  • Chardream 2019-7-12
    1 29
    将笼子分为十组,从1开始测每组首笼,知道青蛙被吃了,在测试之前一组的每一个
    我要喝芽衣的妹汁
  • 漆黑之王 2019-7-12
    0 30
    Silence 让第一只一直活下去直到试出笼子的期望, 等于第一只死掉后第二只从头开始试的期望。 未知笼子数×(1-x/未知笼子数)^x
    其实没有那么复杂啦, 是个蛮简单的方法~
    拖入深渊吧!!!
  • 漆黑之王 2019-7-12
    0 31
    Chardream 将笼子分为十组,从1开始测每组首笼,知道青蛙被吃了,在测试之前一组的每一个
    猫猫头~~恭喜哦~
    拖入深渊吧!!!
  • 0 32
    为什么?原理是什么
    我所期望的永恒
  • 漆黑之王 2019-7-12
    0 33
    萌萌的creeper娘 为什么?原理是什么
    上面那个被猫头的,已经说了哦,可能说的不是很清楚吧~
    拖入深渊吧!!!
    • ACG里世界
      34
          
返回
发新帖