#34488: 什麼? 調和級數也能公式解!!!!!


liaoweichen1024@gmail.com (M_SQRT)

School : 新北市立新莊高級中學
ID : 195452
IP address : [163.13.12.74]
Last Login :
2024-12-06 09:18:01
a625. 5. Overhanging Cards -- HP CodeWars2007 | From: [118.166.152.40] | Post Date : 2023-03-24 23:48

依題所述,我們可以整理出一條不等式:
1/2 + 1/3 + … + 1/n ≧ c
求出n的最小值。

1/1 + 1/2 + … + 1/n有一個專有名詞叫做「調和級數」(Harmonic Series),這個數列的和是發散的,也就是說n為∞時,k亦為∞。當n足夠大時,其值會接近ln(n) + γ,帶回原式可得:
ln(n) + γ- 1 ≧ c

經整理後可得:
f(c) = E^(c+1-γ)
f(c) = exp(c+1-γ)

註:
ln 是「自然對數」(Nature Logarithm) 是以E為底的log。
γ是「歐拉常數」(Euler's Constant) 約為0.5772156649015329,γ讀做「Gamma」。
E 是「自然常數」(Euler's number) 約為2.718281828459045。
E^n 的函式呼叫請不要用pow(E, n),請使用exp(n)。

 

不過ln(n) +γ是在極大時才較精確,題目的輸入僅為(0, 5.2),部分數字有誤差,這裡我幫各位整理出了一個誤差係數0.501,把f(c)減去0.501,再無條件捨去至整數,就能算對超過99%的問題了。

有三個狀況會算錯,當輸入值為0.5, 1.45, 2.18時,會算出錯的答案,只需針對這三個裝況去處理,剩下的就能帶入公式解決了。

while(cin>>c){
         if( c==0.5 ) cout<<(
自己找答案)<<endl;
         else if( c==1.45 ) cout<<(自己找答案)<<endl;
         else if( c==2.18 ) cout<<(自己找答案)<<endl;
         else cout<<(int)(exp(c+1-γ)-誤差係數)<<endl;
}

希望這篇解題報告能幫助到你^_^

 
ZeroJudge Forum