題目連結:
題目大意:
輸入有多列,每列給定一浮點數 c(0.01 ≦ c ≦ 5.20,且 c 為兩位小數),代表著目標值。試問滿足
1 / 2 + 1 / 3 + 1 / 4 + …… + 1 / (n + 1) ≧ c
最小正整數 n 值為何?輸出格式參見範例輸出。
範例輸入:
1.00
3.71
0.04
5.19
範例輸出:
3 card(s)
61 card(s)
1 card(s)
273 card(s)
解題思維:
從範例輸入的 c = 5.19 時 n 值為 273,可以看到其 n 值並不會太大(即使極限的測資 c = 5.20,n 值實際上也只到 276)。因此我們可以直接對 n 值建表——對每個 n 值求出
1 / 2 + 1 / 3 + 1 / 4 + …… + 1 / (n + 1)
之值為何並儲存起來。
最後對於每個 c 值線性(或是二分搜尋法(Binary Search)也行)去找最小的、符合題意的 n 值即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。