数学吧 关注:912,032贴子:8,827,486

生活中一道题亲人们求解

只看楼主收藏回复

一共10道判断题,全部答完才能提交答案,且只显示对了几道题,假设纯蒙的情况,最少蒙几次,能100%全部蒙对。


IP属地:河北1楼2022-05-11 17:05回复
    插眼,没思路


    IP属地:陕西来自Android客户端2楼2022-05-11 17:27
    收起回复
      2025-07-17 19:34:23
      广告
      最少蒙一次


      IP属地:江苏来自iPhone客户端3楼2022-05-11 17:31
      收起回复
        最少一次,平均1024次,最多,无上限


        IP属地:湖北来自Android客户端4楼2022-05-11 17:41
        收起回复
          最少蒙一次


          IP属地:重庆来自Android客户端5楼2022-05-11 17:50
          收起回复
            感觉不简单...试10次一定可以:先全蒙对号,然后第1次蒙一个全对,你就知道答案里多少个对号。然后把第一个改成错号这样的,第2次只把第二个改成错号...第9次只把第9个改成错号
            这样,比如说第一次改完了(第一个是错号其他的都对号)你发现正确答案数比全对号的时候多了一个,那你改掉的那你第一题答案肯定是错号,如果发现正确答案数少了一个,那你改的题答案肯定是对号。于是你蒙10次知道一共几个对号,以及前9题答案,就可以把第10题推出来。


            来自Android客户端6楼2022-05-11 20:42
            收起回复
              先抛开问题不谈
              但凡是这类“最少几次能保证XXX”的问题,永远有逆天回答答案是一次,不知道语文怎么学的
              感觉正解是转化成二进制,再进行考虑;或者二分法,分组逐步迭代考虑。一题一题是答案显然是11了,不知道前两种方法能不能做出来,做到更少步数。
              现在都凌晨了,先c个y,明天起来再想想


              IP属地:上海来自Android客户端7楼2022-05-12 00:37
              收起回复
                信息熵计算就行了


                IP属地:四川来自Android客户端10楼2022-05-12 07:05
                收起回复
                  2025-07-17 19:28:23
                  广告
                  很遗憾,我算的答案是11。
                  解答有点长……嫌啰嗦的话对不住了,本意是想尽可能清楚地说明每个步骤。
                  说一个动态规划的思路,动态规划在编程领域很常见。
                  把问题的前提再规范一下。
                  楼主的问题应该是假定了每次回答的时候,这10道问题的题面和答案都是固定不变的;
                  判断题只有“对”和“错”两种选项,有且仅有一个是正确答案;
                  “猜一次”指的是一次性给出10道题的猜测,评分系统会给我们一个“有多少道题答对”的数字;
                  目标是通过“合理的”猜测方案,让我们以尽可能少的猜测次数,使得无论判断题的答案是什么情况(总共有2^10=1024种情况),都能保证最后猜出所有判断题的答案,即评分系统给出满分。
                  注意,在最后一次猜测之前,我们已经知道了全部的正确答案,但是为了评分系统给出满分,我们还需要最后将正确答案输入一次(其实也就是最后一次猜测已经没有“蒙”的成分了)
                  第一次猜的时候,猜任何答案本质上都是等价的,为了简单可以全猜“对”(这就是本方案的第一步),这样第一次猜完就可以知道10道题里面有多少个题正确答案是“对”。
                  第二次猜,全猜“错”是没有意义的,这跟全猜“对”的结果是相对于10“互补”的。所以需要一些题猜“对”,一些题猜“错”,而我们第一次猜的全“对”,对于题目的顺序是没有要求的,因此第二次猜,无论哪些题猜“对”,哪些猜“错”,都可以适当调整题目的顺序,让前面若干题都猜“对”,后面若干题都猜“错”
                  因此可以抽象出来一个动态规划的函数F[n][x],表示共有n道判断题,其中有x道答案是“对”,至少需要猜多少次才能保证猜对所有答案,其中n>=1, 0<=x<=n
                  可以看到F[n][0]=F[n][n]=1,也就是所有答案都是“对”或都是“错”的时候,只需要猜1次就可以保证猜对所有答案。楼主给出的问题就可以表示为求:
                  1+max(F[10][0],F[10][1], F[10][2],...,F[10][10])
                  最前面的+1表示第一次猜“全对”,后面对11种情况分类讨论,取最多的一种,从而保证最差情况下也能猜对所有答案。
                  下面讨论F[n][x]应该怎么求。以F[10][5]为例,也就是第一次猜完,告诉我们有5道题答案是“对”,接下来还要再猜几次才能猜出所有答案。
                  第二次猜,根据上面的讨论,任何方案都可以抽象为:前k道题猜“对”,后10-k道题猜“错”,其中1<=k<=9(因为不能全猜“对”或全猜“错”),在这种划分方案下,无论评分系统给我们的结果是什么,我们都可以判断前k道题有多少答案是“对”。
                  还是举例子,例如k=3,也就是第二次猜测,前3道题猜“对”,后7道题猜“错”。那么2分就对应了“前3道题有0道答案是对,后7道题有5道答案是对”,4分就对应了“前3道题有1道答案是对,后7道题有4道答案是对”,6分就对应了“前3道题有2道答案是对,后7道题有3道答案是对”,8分就对应了“前3道题有3道答案是对,后7道题有2道答案是对”。不同的得分可以将答案是“对”的题目的不同分布情况完全区分开,这对于任意的n,k以及合法的评分都是成立的。
                  按上面的例子,F[10][5]就可以这样计算:
                  F[10][5]=1+max(
                  F[3][0]+F[7][5]-1,
                  F[3][1],F[7][4]-1,
                  F[3][2],F[7][3]-1,
                  F[3][3],F[7][2]-1
                  )
                  外层的max较好理解,是因为每种得分都有可能出现,但我们要保证无论是哪种情况都要猜出所有答案。
                  内层是两个规模较小的问题答案相加再减1,是因为当规模较大的问题(10个判断题,5个是“对”的答案)分解为两个规模较小的问题之后,对这两个问题的猜测不能“并行”进行,必须控制一边的答案不变,改变另一边的猜测结果,才能推测有哪些题是回答正确了的。
                  本质上是因为我们一次只能输入10个问题的答案给评分系统,而不能只输入前3个问题或者后7个问题的答案。
                  最后的减1是因为任何一个规模较小的问题,它的最后一次猜测只是为了让评分系统给出满分,并没有猜测的成分,因此可以利用这一次来进行另一个规模较小问题的第一次猜测。
                  后面的公式会将前面的+1和max内的-1合并起来。
                  注意到,这只是对于k=3的情况,这种划分是否最优现在还不能确定,可能k=4结果会更好。把所有可能的划分方案考虑进来,就有
                  F[10][5]=min(
                  max
                  (
                  F[k][x]+F[10-k][5-x]
                  ))
                  其中1<=k<=9,x需要满足0<=x<=k并且0<=5-x<=10-k,内层的max是对所有的x来说的,外层的min是对所有的k来说的(取最优的划分方案)
                  如果是求解一般性的问题,例如n道题需要至少猜测f(n)次,则下面的这组公式给出了解:
                  f(n)=1+max(F[n][x]), 0<=x<=n
                  F[n][x]=min(max(F[k][y]+F[n-k][x-y])), 0<=y<=k,0<=x-y<=n-k,1<=k<=n-1
                  F[n][0]=F[n][n]=1
                  最后就是求解具体数值了,可以手算,但写程序求解会更快一些。经程序验证答案是11。
                  最差情况是第一次猜全对的时候,评分系统给出5分。其他情况都不需要这么多次,例如给出1分的时候,6次就够了
                  从答案来看,f(n)=n+1,也就是最简单的猜测方案:
                  第一次猜全对,之后每次固定后面的猜测,依次判断前面每道题的答案


                  IP属地:山东11楼2022-05-12 10:35
                  收起回复
                    穷举:第一次改完得到正确题数,依次改1题,2题...,每改一次正确数少一说明原来是对的,多一说明原来是错的,至多11次评判。这已经是最笨的方法了,不可能比这还多了


                    IP属地:吉林来自Android客户端12楼2022-05-12 10:47
                    收起回复
                      再少的话我想可以二分。平分成两部分,每一次部分都改反。比如10题就5个不动,5个改反,如果正确数多5或少5,同穷举。如果是其他数,就继续二分。过程同上,可以继续利用整体的信息。具体不想算了,你可以考虑一下是不是次数更少。要是证明出来真比上一种方法简单,那次数大概率是1+log(2,10)


                      IP属地:吉林来自Android客户端13楼2022-05-12 10:52
                      收起回复
                        我的答案是5次(即第六次提交可以保证全对),但是我没有证明完全...
                        字太多了,写了一个小时,看图吧。。。


                        IP属地:上海来自Android客户端14楼2022-05-12 11:20
                        收起回复
                          我能保证第十次一定蒙对。每次只改一个选项。感觉应该有更好的方案,不过想不到。可能几个几个分一组,然后一次性改变一组的值,就能知道这个组里几个对的几个错的。那答案应该小于10。


                          IP属地:日本来自Android客户端15楼2022-05-12 11:47
                          收起回复
                            最少1次,只要运气在线


                            IP属地:陕西来自Android客户端16楼2022-05-12 12:06
                            收起回复
                              2025-07-17 19:22:23
                              广告
                              你问最少,那就1次


                              IP属地:浙江来自Android客户端18楼2022-05-12 12:10
                              收起回复