当前位置： 面试刷题>> 猜数游戏Ⅱ (经典算法题500道)
### 题目描述补充
**猜数游戏Ⅱ**：
你正在玩一个猜数字游戏。游戏规则如下：
- 我已经选好了一个范围在 1 到 n 之间的整数（包含 1 和 n）。
- 每次你可以问我一个问题，问题形式为：“在 [x, y] 这个范围内，是否包含我选好的数字？”（x 和 y 是整数，且 1 ≤ x ≤ y ≤ n）。
- 我会根据你的问题回答 "yes" 或 "no"。
- 你需要通过最少的询问次数猜出我选的那个数字是多少。
为了优化你的猜测策略，请编写一个函数来找出你需要的最少询问次数。注意，你不需要实际执行询问，只需要计算出最少需要多少次询问。
### 示例
假设 n = 100，一种可能的策略是：
1. 首先询问 [1, 50] 是否包含数字，如果包含，则缩小范围到 [1, 50]；如果不包含，则范围缩小到 [51, 100]。
2. 然后在新的范围内继续二分，比如若第一次回答是 "yes"，则第二次询问 [1, 25] 是否包含。
3. 通过不断二分，直到范围缩小到只有一个数字。
### 解题思路
这个问题可以转化为一个二叉树的最优搜索问题，其中每个节点代表一个询问的区间。对于每个区间 [x, y]，我们将其分为两个子区间 [x, mid] 和 [mid+1, y]，其中 mid = (x + y) / 2。为了找到最小的询问次数，我们可以使用动态规划（DP）来解决问题。
### PHP 示例代码
```php
function getMoneyAmount(int $n): int {
// 创建一个二维数组来保存子问题的解
$dp = array_fill(0, $n + 1, array_fill(0, $n + 1, 0));
// 遍历所有可能的区间长度
for ($len = 2; $len <= $n; $len++) {
// 遍历所有可能的起始点
for ($start = 1; $start <= $n - $len + 1; $start++) {
$end = $start + $len - 1;
$dp[$start][$end] = PHP_INT_MAX; // 初始化为最大整数
// 尝试所有可能的分割点
for ($mid = $start; $mid < $end; $mid++) {
// 当前分割点的最优解是左边和右边最优解的最大值加1（当前询问）
$dp[$start][$end] = min($dp[$start][$end], max($dp[$start][$mid], $dp[$mid + 1][$end]) + 1);
}
// 如果当前区间长度为2，则不需要分割，直接询问即可
if ($len == 2) {
$dp[$start][$end] = 1;
}
}
}
return $dp[1][$n];
}
// 示例调用
echo getMoneyAmount(100); // 输出最少询问次数
```
### Python 示例代码
```python
def getMoneyAmount(n: int) -> int:
dp = [[0] * (n + 1) for _ in range(n + 1)]
for length in range(2, n + 1):
for start in range(1, n - length + 2):
end = start + length - 1
dp[start][end] = float('inf')
for mid in range(start, end):
dp[start][end] = min(dp[start][end], max(dp[start][mid], dp[mid + 1][end]) + 1)
if length == 2:
dp[start][end] = 1
return dp[1][n]
# 示例调用
print(getMoneyAmount(100)) # 输出最少询问次数
```
### JavaScript 示例代码
```javascript
function getMoneyAmount(n) {
const dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));
for (let length = 2; length <= n; length++) {
for (let start = 1; start <= n - length + 1; start++) {
let end = start + length - 1;
dp[start][end] = Infinity;
for (let mid = start; mid < end; mid++) {
dp[start][end] = Math.min(dp[start][end], Math.max(dp[start][mid], dp[mid + 1][end]) + 1);
}
if (length === 2) {
dp[start][end] = 1;
}
}
}
return dp[1][n];
}
// 示例调用
console.log(getMoneyAmount(100)); // 输出最少询问次数
```
**码小课网站中有更多相关内容分享给大家学习**，这些内容包括但不限于算法基础、数据结构、面试技巧等，希望能对大家的学习有所帮助。