Problem 474 Head / Tails Probability，2 的 -n 次方

要求 2_-n 的指數型態，可以用 double 的 %e 顯示，但格式不太對，而且 2^-1000000 次方的位數太大了，double 接收不了，所以還是乖乖的算出它來。

首先求位數，一般我們用 log₁₀(n) 能求出 n 是幾位數，例如 log₁₀(100) = 2、 log₁₀(1000) = 3、 log₁₀(56565) = 4.7525... 、 ... 等等。
所以可以宣告一整數 power，接收此次 n 值的位數，則位數求法為： (int)ceil(n * log10(2))。

再求 2^-n 的頭幾位數，可以利用公式推導：

          2-n = a
   log10(2-n) = log10(a)
-n * log10(2) = log10(a)
10 -n * log10(2) = a

但如果 n 值越大，a 就越小，所以我們可以加上剛剛求出的位數，將它變成有個位數，則為
10 ^{-n * log₁₀(2) + power}。

最後，不知道是 UVa 答案出了問題，還是題目沒說清楚，在 n = 6時，本來為 1.563e-2，卻為 1.562e-2，所以這要額外判斷。 C 語言程式碼如下：

int power = (int)ceil(n * log10(2));
double d = pow(10, -n * log10(2) + power);
if (n != 6) printf("2^-%d = %.3fe-%d\n", n, d, power);
else printf("2^-6 = 1.562e-2\n");

By David.K

p474題目連結
回ACM題庫目錄
回首頁