网页
资讯
视频
图片
知道
文库
贴吧
地图
采购
进入贴吧
全吧搜索
吧内搜索
搜贴
搜人
进吧
搜标签
日
一
二
三
四
五
六
签到排名:今日本吧第
个签到,
本吧因你更精彩,明天继续来努力!
本吧签到人数:0
一键签到
可签
7
级以上的吧
50
个
一键签到
本月漏签
0
次!
0
成为超级会员,赠送8张补签卡
如何使用?
点击日历上漏签日期,即可进行
补签
。
连续签到:
天 累计签到:
天
0
超级会员单次开通12个月以上,赠送连续签到卡3张
使用连续签到卡
07月17日
漏签
0
天
数学吧
关注:
912,032
贴子:
8,827,486
看贴
图片
吧主推荐
视频
游戏
1
2
3
4
下一页
尾页
251
回复贴,共
4
页
,跳到
页
确定
<返回数学吧
>0< 加载中...
生活中一道题亲人们求解
只看楼主
收藏
回复
zslj460
初级粉丝
1
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
一共10道判断题,全部答完才能提交答案,且只显示对了几道题,假设纯蒙的情况,最少蒙几次,能100%全部蒙对。
送TA礼物
IP属地:河北
1楼
2022-05-11 17:05
回复
不觉己是春归去
人气楷模
12
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
插眼,没思路
IP属地:陕西
来自
Android客户端
2楼
2022-05-11 17:27
回复(1)
收起回复
2025-07-17 19:34:23
广告
ybluebaby
意见领袖
15
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
最少蒙一次
IP属地:江苏
来自
iPhone客户端
3楼
2022-05-11 17:31
回复(14)
收起回复
(°A°`)想名难
铁杆吧友
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
最少一次,平均1024次,最多,无上限
IP属地:湖北
来自
Android客户端
4楼
2022-05-11 17:41
回复(7)
收起回复
sd1232
人气楷模
12
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
最少蒙一次
IP属地:重庆
来自
Android客户端
5楼
2022-05-11 17:50
回复(1)
收起回复
soul
凌雨
知名人士
10
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
感觉不简单...试10次一定可以:先全蒙对号,然后第1次蒙一个全对,你就知道答案里多少个对号。然后把第一个改成错号这样的,第2次只把第二个改成错号...第9次只把第9个改成错号
这样,比如说第一次改完了(第一个是错号其他的都对号)你发现正确答案数比全对号的时候多了一个,那你改掉的那你第一题答案肯定是错号,如果发现正确答案数少了一个,那你改的题答案肯定是对号。于是你蒙10次知道一共几个对号,以及前9题答案,就可以把第10题推出来。
来自
Android客户端
6楼
2022-05-11 20:42
回复(11)
收起回复
AlphB
人气楷模
13
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
先抛开问题不谈
但凡是这类“最少几次能保证XXX”的问题,永远有逆天回答答案是一次,不知道语文怎么学的
感觉正解是转化成二进制,再进行考虑;或者二分法,分组逐步迭代考虑。一题一题是答案显然是11了,不知道前两种方法能不能做出来,做到更少步数。
现在都凌晨了,先c个y,明天起来再想想
IP属地:上海
来自
Android客户端
7楼
2022-05-12 00:37
回复(6)
收起回复
换了七个用户名
初级粉丝
1
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
信息熵计算就行了
IP属地:四川
来自
Android客户端
10楼
2022-05-12 07:05
回复(2)
收起回复
2025-07-17 19:28:23
广告
逢部祝
初级粉丝
1
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
很遗憾,我算的答案是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
回复(13)
收起回复
苏氨酸
初级粉丝
1
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
穷举:第一次改完得到正确题数,依次改1题,2题...,每改一次正确数少一说明原来是对的,多一说明原来是错的,至多11次评判。这已经是最笨的方法了,不可能比这还多了
IP属地:吉林
来自
Android客户端
12楼
2022-05-12 10:47
回复(1)
收起回复
苏氨酸
初级粉丝
1
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
再少的话我想可以二分。平分成两部分,每一次部分都改反。比如10题就5个不动,5个改反,如果正确数多5或少5,同穷举。如果是其他数,就继续二分。过程同上,可以继续利用整体的信息。具体不想算了,你可以考虑一下是不是次数更少。要是证明出来真比上一种方法简单,那次数大概率是1+log(2,10)
IP属地:吉林
来自
Android客户端
13楼
2022-05-12 10:52
回复(1)
收起回复
AlphB
人气楷模
13
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
我的答案是5次(即第六次提交可以保证全对),但是我没有证明完全...
字太多了,写了一个小时,看图吧。。。
IP属地:上海
来自
Android客户端
14楼
2022-05-12 11:20
回复(13)
收起回复
XTU学生
知名人士
11
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
我能保证第十次一定蒙对。每次只改一个选项。感觉应该有更好的方案,不过想不到。可能几个几个分一组,然后一次性改变一组的值,就能知道这个组里几个对的几个错的。那答案应该小于10。
IP属地:日本
来自
Android客户端
15楼
2022-05-12 11:47
回复(5)
收起回复
HelloByBy
初级粉丝
1
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
最少1次,只要运气在线
IP属地:陕西
来自
Android客户端
16楼
2022-05-12 12:06
回复(7)
收起回复
2025-07-17 19:22:23
广告
西瓜滚键盘
初级粉丝
1
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
你问最少,那就1次
IP属地:浙江
来自
Android客户端
18楼
2022-05-12 12:10
回复(2)
收起回复
登录百度账号
扫二维码下载贴吧客户端
下载贴吧APP
看高清直播、视频!
贴吧热议榜
1
IG选手Jiejie不愿做替补解约离队
2673450
2
coser要恨死这位漫展原图哥了
2168388
3
唐尚珺拒做网红含泪宣布退网
1597568
4
郑钦文退赛世排名或暴跌
1173582
5
贴吧校草盲盒开出来个田栩宁
831090
6
孙颖莎教练让粉丝别骂了
726275
7
JDG辅助MISSING正式离队
584784
8
印航飞行员脑抽关燃油开关致坠机
436080
9
电诈园区诱骗高中生为何频频得逞
346544
10
吧友评姜文新片:不行别上
301539
贴吧页面意见反馈
违规贴吧举报反馈通道
贴吧违规信息处理公示