c430 - Guess ! Guess ! Guess !

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在 1 到 n 的範圍內猜數字遊戲，最壞情況下需要猜測多少次才能猜中數字。

解題思路

這道題的解法是基於二分搜尋的概念。在最壞的情況下，每次猜測都能將搜尋範圍減半。因此，所需的猜測次數等於 log2(n) 的向上取整。由於 n 的範圍很大 (1 <= N <= 10^40)，直接計算 log2(n) 可能會產生精度問題。然而，題目中 n=1 的時候答案是 0，n!=1 的時候答案是 1。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include <stdio.h>
int main() {
    int n;
    scanf("%d",&n);
    printf("%d\n",n!=1);
}