知识卡片

普通读书笔记卡 · 1708.b.3.g · 生成模型:未记录

折半缩小候选需明确胜利条件

理解等级:中级

在有序候选中,每次猜中点并据高低反馈排除一半,可在对数次数内定位目标。书例一百万个候选在20次内可以猜中;这个数量级来自每步缩小候选区间。

“知道剩余数字”和“实际猜中数字”是不同计数规则。若每次必须明确猜中才能获胜,n=2时最坏需2猜,不能机械套ceil(log₂n)=1。对n个连续候选,标准中点猜测最坏可用ceil(log₂(n+1))描述;图03147在剩余至多三个候选时直接返回1+turns,是把一次反馈后推知答案计入结果,不一定等于要求最后再报出正确数字的猜测次数。示例也未处理mid=(low+high)/2的整数溢出。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      1 000 000的数字,然后你能够每次猜1个数字,共猜20次;每一次猜过之后,我将会告诉你高了,低了或者是你赢了。如果你能在20个问题之内赢,我给你10 000美元,否则你给我10 000美元。”你会打这个赌吗?你也许会,因为你可以一直赢下去。表2-1给了一个场景,不过候选数字是从1~10。问一系

    参考来源

    - 位置:《算法技术手册》第2章《讨论1:对数级算法的性能》(spine1467;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1431.html;u032-ch02-008)。 - 结论依据:32全文、03145–03146全表及03147完整Java代码实读;n=2与计数差异为静态推导,未运行Java。 - 原始内容:1 000 000的数字,然后你能够每次猜1个数字,共猜20次;每一次猜过之后,我将会告诉你高了,低了或者是你赢了。如果你能在20个问题之内赢,我给你10 000美元,否则你给我10 000美元。”你会打这个赌吗?你也许会,因为你可以一直赢下去。表2-1给了一个场景,不过候选数字是从1~10。问一系