推 tropical72:謝謝 y 大指導,說明很詳細,非常感謝！ 05/01 20:42
※ 引述《tropical72 (藍影)》之銘言：
: 試著化簡該公式：
: e = 1/1 + 1/1*1/2 + 1/1 * 1/2 * 1/3 + ...
: = 1* (1+1/2* (1+1/3* ....(1+1/n)))))
: 這麼做請問 recursive function 該如何撰？ (in c or c++ is better)
goto ......
: → bleed1979:http://codepad.org/fCx0Hoy6 05/01 19:2
: 先謝謝樓上二位的建議, e 我不是不會求，
: 大多求法都避不開另寫一個階層函式，
: 但發問重點是想借這題去探討另一 recursive 問題
: double euler2(int x)
: {
: double ans=1.0/x;
: while(x) ans = (ans+1)/x, --x;
: return ans+1;
: }
: 這是 non-recursive 版的，我比較好奇是 recursive how to ?
: 看過 bleed1979 給的 http://codepad.org/fCx0Hoy6 應是我想要的
: 我再研究一下是否有辦法變成單變數 recursive , 謝謝各位！
整理recursive的東西,基本方法是找對base case與recursive case.
像你整理的:
e = 1/1 + 1/1*1/2 + 1/1 * 1/2 * 1/3 + ...
= 1* (1+1/2* (1+1/3* ....(1+1/n)))))
Base case是 e(1) = 1/1, recursive case 是 e(n) 先求了 e(n-1) 式子,
然後在 e(n-1) 式子中最裡層的右項乘上一個新的乘數. 例子必須列舉來看:
e(2) = 1/1*(1+1/2),
1/1是e(1),e(1)式子最裡層是1/1,
新的乘數是e(1)最裡層右項的分母加一然後加一, 所以用同樣的道理看:
e(3) = 1/1*(1+1/2*(1+1/3))
^^^^^^^^
e(4) = 1/1*(1+1/2*(1+1/3*(1+1/4)))
^^^^^^^^
當然,這種遞迴方式在C/C++這種急著及早求值的語言中相當不容易寫.
而你推文的例子則是對同樣的化簡方式切換視點,讓程式好寫.
double euler2(int x)
{
double ans=1.0/x;
while(x) ans = (ans+1)/x, --x;
return ans+1;
}
程式是把式子反過來看: base case 是 1/n, recursive case 是將前項加一然後
除以一個新的除數.
e(n-1) = (1+1/n)/(n-1) 也就是 1/(n-1)*(1+1/n)
e(n-2) = (1+(1+1/n)/(n-1))/(n-2) 也就是 1/(n-2)*(1+1/(n-1)*(1+1/n))
具體的遞迴程式還是要把 e(0) 當作字面上的 base case, 但是實際上 base case 是
e(n). 可以用"介面-實作"技巧處理.
double euler2(int x) {
return euler2(x, 0.0);
}
double euler2(int x, double acc) {
if (x <= 0) return acc;
return euler2(x-1, (acc+1)/x);
}
--
/yau
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.112.226.35