数学研发论坛

 找回密码
 欢迎注册
查看: 224|回复: 2

[原创] 无界的有大小提示的猜数游戏

[复制链接]
发表于 2022-5-1 09:45:15 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
有界有大小提示的猜数游戏,结论和策略都很简单:

结论是最坏情况下要猜$(\lfloor\log_2(n)\rfloor+1)$次,$n$表示要猜的整数在$1$到$n$之间,

策略是二分法,先猜最中间,然后根据提示不断地猜剩余区间的最中间,直到猜对为止。

我现在遇到了一个无界的有大小提示的猜数游戏,只知道要猜的整数$x$最小是$1$,不知道最大是几。

我想在最坏情况下,猜对所需次数 减去 $(\lfloor\log_2(x)\rfloor+1)$ 的值要达到最小,$x$表示要猜的数。

我目前能想到的策略,猜对所需次数 减去 $(\lfloor\log_2(x)\rfloor+1)$ 的值大约是 ($2\sqrt{2\lfloor\log_2(x)\rfloor}+$常数),

还有没有更优的策略呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-5-1 15:00:42 | 显示全部楼层
第一次取$a_0=2=2^{2^0}$,
如果第k次和$a_{k-1}$比较,提示大于$a_{k-1}$,取$a_k=a_{k-1}^2$,直到某个$a_n=2^{2^n}$使得$a^{n-1}<x<a_n$
这个步骤共花费不超过$\log_2\log_2(x)+1$次。
然后设$2^{u_1}<x<2^{v_1}$
我们选择$m_1=\lfloor{u_1+v_1}/2\rfloor$,然后将x和$2^{m_1}$进行比较,如果$x<m_1$选择$u_2=u_1,v_2=m_1$;不然选择$u_2=m_1,v_2=v_1$, 依次下去,直到$v_h=u_h+1$.
这个步骤花费$\log_2(v_1-u_1)=\log_2 2^{n-1}=n-1 ~= \log_2\log_2(x)$
所以我们大概经过$2\log_2\log_2(x)$找到$u_h$使得,$2^u_h\le x\lt 2^{u_h+1}$
后面通过二分法,最多再经过$\log_2 2^{u_h}\lt log_2 x$步可得
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-5-1 21:19:55 | 显示全部楼层
额外的猜数次数,我要$O(\sqrt{\log(x)})$次,

你竟然只需 ($2\log_2\log_2(x)$+常数) 次,太厉害了吧?

按照你这种思路,总猜数次数最终是不是可以优化成

常数 $+\log_2(x)+\log_2\log_2(x)+\log_2\log_2\log_2(x)+\log_2\log_2\log_2\log_2(x)+$......

呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2022-5-22 12:48 , Processed in 0.072919 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表