Re: [問題] recursive Eule
其實用內建型別再怎麼逼近都太無趣了，能顯示多少。
使用大數計算，我們來逼近e的小數點以下精確1000位以上。
在公式e^x = 1 + x + x^2/2! + x^3/3! + x^3/3! + x^n/n!
x代1得到 e = 1 + 1/1! + 1/2! + 1/3! + ... + 1/n!
如果n = 4，
則整理一下會發現 e = (1 + 1/1 * (1 + 1/2 * (1 + 1/3 * (1 + 1/4))))
所以只要能算出1/n，使用遞迴就可以解決。
動手之前，先想想：
這裡有兩個變動的數字，一個是精確度p，一個是n要算多少才能達到精確度p
可以知道的是n越大越能逼近精確度p（廢話!）。
姑且視n = p來計算，程式運算要越快越好。
程式寫法套用上面的公式，遞迴仍然使用雙變數，
先算出1/n，然後乘上一次遞迴結果，乘完後加上1，當作這一次的結果。
乘法部分，overload operator *，並且以變數unit的數值為單位相乘。
也就是說123456789 * 987654321，在unit = 5時，
採取1234 56789 * 9876 54321的方式，最後再一次進位。
程式結果：
如果輸入精確度p，精確位數要扣掉最前面的2的這一個位數，
所以精確小數點以下p - 1位。
（應該吧，只抓最前面和最後面的數字比對，無一一比對）
輸出的數字排列僅是方便我自己對答案。
精確1000位，運算時間3秒內，2000位差不多10秒。
還有很大的進步空間。
程式連結：http://codepad.org/K4d45BU3
※ 引述《tropical72 (藍影)》之銘言：
: 標題: [問題] recursive Eule
: 時間: Sun May 1 18:40:13 2011
:
: ※ [本文轉錄自 Programming 看板 #1DlJTBzo ]
:
: 作者: tropical72 (藍影) 站內: Programming
: 標題: [問題] recursive Eule
: 時間: Sun May 1 18:34:48 2011
:
: e = 1/1!+1/2!+...+1/n!
:
: 欲以一個 recursive 解之
:
: 目前必須用到的是 recursive_sum + recursive_fact，
:
: 試著化簡該公式：
:
: 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)
:
: 或能給我一份通式嗎？
:
: 謝謝各位不吝指教！
:
: ---- 分隔線 ---- my try ---
:
: double f(int x)
: {
: return (x==0 || x==1) ? 1 : ( (1.0/n+1)*f(x-1) );
: }
:
: 我知道這份是有問題的，展開會變成 (1/4+1)*(1/3+1)*(1/2+1)*1
: 不過想不透該如何改
:
: --
: YouLoveMe() ? LetItBe() : LetMeFree();
:
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 180.177.73.222
: ※ 編輯: tropical72 來自: 180.177.73.222 (05/01 18:38)
:
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 180.177.73.222
: → TsinTa:f(n)=f(n-1)+1/n! <---是這樣嗎?還是要用你化簡的式子? 05/01 19:01
: → bleed1979:如果是2個recursive，我可以幫你。 05/01 19:03
: → bleed1979:http://codepad.org/klyb8ZxS 或 05/01 19:04
: → bleed1979:http://pastie.org/1853074 05/01 19:04
: → bleed1979:有點作弊的寫法如下，一個recursive。 05/01 19:19
: → bleed1979:http://codepad.org/fCx0Hoy6 05/01 19:20
:
: 先謝謝樓上二位的建議, 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 , 謝謝各位！
: ※ 編輯: tropical72 來自: 180.177.73.222 (05/01 19:43)
: → tropical72:補上,bleed1979 第三個 link 似乎有些誤. 05/01 19:47
: → firejox:假如你要避開階乘 可以用連分數去做~~ 05/01 20:03
: → tropical72:@firefox: 我想我提出的 subfunc 就是連分數 05/01 20:07
: → firejox:http://codepad.org/Nlsi52T7 05/01 20:16
: → firejox:http://en.wikipedia.org/wiki/Continued_fraction 05/01 20:16
: → bleed1979:原po給的公式是否少1？ 05/01 20:24
: → bleed1979:e^x =1+x+x^2/2!+x^3/3!+x^3/3!+x^n/n! x代1 05/01 20:31
: → firejox:另一種 http://codepad.org/2K0jDqS7 05/01 20:48
: → firejox:這是用 e^x=1+x+x^2/2!+...+x^n/n! 導的... 05/01 20:54
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.25.251.97
推
05/02 10:27, , 1F
05/02 10:27, 1F
→
05/02 11:12, , 2F
05/02 11:12, 2F
推
05/02 14:24, , 3F
05/02 14:24, 3F
→
05/02 19:36, , 4F
05/02 19:36, 4F
→
05/02 19:36, , 5F
05/02 19:36, 5F
→
05/02 19:37, , 6F
05/02 19:37, 6F
討論串 (同標題文章)