[java]フィボナッチ数列
2006/05/05
2006/11/26
[フィボナッチ数列][その４]
再帰処理でキャッシュすることなんどについての
http://www.kmonos.net/wlog/52.php#_0308050827
僕の勉強不足だった。
これからちょっとリサーチしよう
[フィボナッチ数列][その３] 再帰に挑戦 キャッシュ版
fibo(x - 1) + fibo(x - 2)
がおそくなる理由は、単純に同じ計算を何度もさせているからのよう。
で、なにやらキャッシュ（この言い方は正しいのかな？）させて計算結果を再利用するとはやくなる。
コードはJDK1.5用。
public static BigDecimal fibo(int x) {
class Fibo {
Map m = new HashMap();
public BigDecimal fibo(int x) {
BigDecimal r = null;
if ((r = (BigDecimal) m.get(x)) != null)
return r;
switch (x) {
case 0:
case 1:
r = new BigDecimal(1);
break;
case 2:
r = new BigDecimal(2);
break;
default:
r = fibo(x - 1).add(fibo(x - 2));
}
m.put(x, r);
return r;
}
};
Fibo f = new Fibo();
return f.fibo(x);
}
いろいろな方法があるのだなぁ
スピードとしては最初の実装のほうが数がふえれば、はやい。
３０００で計ったら、
キャッシュ版２２秒
最初の実装５秒
でも
fibo(x - 1) + fibo(x - 2)
のほうが再帰させいるって感じがする。
３０００の結果
3000 664390460366960072280217847866028384244163512452783259405579765542621214161219257396449810982999820391132226802809465132446349331994409434926019045342723749188530316994678473551320635101099619382973181622585687336939784373527897555489486841726131733814340129175622450421605101025897173235990662770203756438786517530547101123748849140252686120104032647025145598956675902135010566909783124959436469825558314289701354227151784602865710780624675107056569822820542846660321813838896275819753281371491809004412219124856375121694811728724213667814577326618521478357661859018967313354840178403197559969056510791709859144173304364898001
[フィボナッチ数列][その２]
フィボナッチ数列 その２ 再帰に挑戦
再帰でフィボナッチ数列 を処理させるのがかっこいいらしい。
しかし、
fibo(x - 1) + fibo(x - 2)
とするとある程度の計算だとすごくCPUを使うっぽい。
fibo(x - 1) + fibo(x - 2)ではないやり方で再帰させてみた。
で、とにかく再帰させたいので、会社から帰宅途中、ノートとペンでロジックを考えてみた。
ここでは、
再帰の定義を自分自身から自分自身を呼び出せば、何でも再帰というふにした。
あとからプログラムをながめてみて、はじめ書いたfor文コードの焼き直しだなぁとわかった。
フィボナッチ数列のイメージを得るために、
a + b = c
b + c = d
c + d = e
d + e = f
e + f = g
という式をノートに書いた。これは上から順に値が移動していくイメージ
をつかむために。
それで、再帰的に処理をさせるために下から上にむかえばいいのだろうと単純に考えた。
結局下から上にむかってまた上から下に計算していくイメージ。
for文のものは上からダイレクトに計算させていくだけ。
public static BigInteger fibo(BigInteger[] bs, int x) {
if (bs == null)
bs = new BigInteger[1];
if (x == 1) {
bs[0] = new BigInteger("1");
return new BigInteger("1");
}
BigInteger r = fibo(bs, x - 1);
BigInteger R = r.add(bs[0]);
bs[0] = r;
return R;
}
使い方、
for(int i=1;i<=max;i++)System.out.println(i + " "+ fibo(null, i));
第一引数は実装上の副作用。
実行結果は以下
正しいと思うけど。。。。
1 1
2 2
3 3
4 5
5 8
6 13
7 21
8 34
9 55
10 89
11 144
12 233
13 377
14 610
15 987
16 1597
17 2584
18 4181
19 6765
20 10946
21 17711
22 28657
23 46368
24 75025
25 121393
26 196418
27 317811
28 514229
29 832040
30 1346269
31 2178309
32 3524578
33 5702887
34 9227465
35 14930352
36 24157817
37 39088169
38 63245986
39 102334155
40 165580141
41 267914296
42 433494437
43 701408733
44 1134903170
45 1836311903
46 2971215073
47 4807526976
48 7778742049
49 12586269025
50 20365011074
51 32951280099
52 53316291173
53 86267571272
54 139583862445
55 225851433717
56 365435296162
57 591286729879
58 956722026041
59 1548008755920
60 2504730781961
61 4052739537881
62 6557470319842
63 10610209857723
64 17167680177565
65 27777890035288
66 44945570212853
67 72723460248141
68 117669030460994
69 190392490709135
70 308061521170129
71 498454011879264
72 806515533049393
73 1304969544928657
74 2111485077978050
75 3416454622906707
76 5527939700884757
77 8944394323791464
78 14472334024676221
79 23416728348467685
80 37889062373143906
81 61305790721611591
82 99194853094755497
83 160500643816367088
84 259695496911122585
85 420196140727489673
86 679891637638612258
87 1100087778366101931
88 1779979416004714189
89 2880067194370816120
90 4660046610375530309
91 7540113804746346429
92 12200160415121876738
93 19740274219868223167
94 31940434634990099905
95 51680708854858323072
96 83621143489848422977
97 135301852344706746049
98 218922995834555169026
99 354224848179261915075
100 573147844013817084101
1000 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
再帰のこれって魔法みたい。
public static long fibo(long n) {
return (n == 0 || n == 1) ? 1 : fibo(n - 2) + fibo(n - 1);
}
[フィボナッチ数列][その１]
いまさらながら、算数、数学が苦手な僕は文系です。
で、プログラムを書くのは好きです。
苦手な、算数、数学にアプローチしてみました。
http://blog.livedoor.jp/dankogai/archives/50456147.html
http://www.hyuki.com/story/genfunc.html
フィボッナチッチ数列というようです。
計算はただしいと思う。。。
下記ジャヴァプログラム
package test.fib;
import java.math.BigInteger;
//ugo_ugo_ugoオリジナル
public class TestMain1 {
/**
* １から９９まで計算
*/
public static void main(String[] args) {
int max = 99;
for(int i=1;i<=max;i++){
System.out.println(i + " ==> "+ f(i));
}
}
/**
* 大きな値でも計算できると思う
*/
public static BigInteger f(int x){
BigInteger prepre = new BigInteger("1");
BigInteger pre = new BigInteger("0");
BigInteger result = new BigInteger("0");
for(int i=0;i<=x;i++){
result = prepre.add(pre);
prepre = pre;
pre = result;
}
return result;
}
}
計算結果
1 1
2 2
3 3
4 5
5 8
6 13
7 21
8 34
9 55
10 89
11 144
12 233
13 377
14 610
15 987
16 1597
17 2584
18 4181
19 6765
20 10946
21 17711
22 28657
23 46368
24 75025
25 121393
26 196418
27 317811
28 514229
29 832040
30 1346269
31 2178309
32 3524578
33 5702887
34 9227465
35 14930352
36 24157817
37 39088169
38 63245986
39 102334155
40 165580141
41 267914296
42 433494437
43 701408733
44 1134903170
45 1836311903
46 2971215073
47 4807526976
48 7778742049
49 12586269025
50 20365011074
51 32951280099
52 53316291173
53 86267571272
54 139583862445
55 225851433717
56 365435296162
57 591286729879
58 956722026041
59 1548008755920
60 2504730781961
61 4052739537881
62 6557470319842
63 10610209857723
64 17167680177565
65 27777890035288
66 44945570212853
67 72723460248141
68 117669030460994
69 190392490709135
70 308061521170129
71 498454011879264
72 806515533049393
73 1304969544928657
74 2111485077978050
75 3416454622906707
76 5527939700884757
77 8944394323791464
78 14472334024676221
79 23416728348467685
80 37889062373143906
81 61305790721611591
82 99194853094755497
83 160500643816367088
84 259695496911122585
85 420196140727489673
86 679891637638612258
87 1100087778366101931
88 1779979416004714189
89 2880067194370816120
90 4660046610375530309
91 7540113804746346429
92 12200160415121876738
93 19740274219868223167
94 31940434634990099905
95 51680708854858323072
96 83621143489848422977
97 135301852344706746049
98 218922995834555169026
99 354224848179261915075
正しいと思う。。。
で、メソッドの呼び出しを再帰させたほうがかっこいいらしい。
でも、上記のプログラムだと無駄な判定をしないで一気に計算させるからよいと思うのだけど。。。
インターネット上あがっているソースをちょこっとみると、swithcで1の場合、２の場合とわけたりしていた。
あとJavaだとBigDecimalがお手軽に使えるので大きな数字も大丈夫っぽい。
http://www.fobj.com/hisa/w/FibonacciNumbers.html
インターネット上にあがっていたソースをちょっこと自分用にして動かしてみた。
//改造
public class Fibo {
public static long fibo(long n) {
return (n == 0 || n == 1) ? 1 : fibo(n - 2) + fibo(n - 1);
}
public static void main(String[] args) {
int max = 40;
for (int i = 1; i < max; i++)
System.out.println(i + " " + fibo(i));
}
}
再帰を使ってシンプルなコードなのできれい。僕もこういうふうなシンプルなコードがかけたらいいなと思った。max値が増えるとちょっとおそくなるようだ。
ぐーぐるさんで調べたら、perlで書いた例があった。
http://www.namikilab.tuat.ac.jp/~sasada/prog/parrot-intro.html
再帰処理でキャッシュすることなんどについての
http://www.kmonos.net/wlog/52.php#_0308050827
僕の勉強不足だった。
これからちょっとリサーチしよう
[フィボナッチ数列][その３] 再帰に挑戦 キャッシュ版
fibo(x - 1) + fibo(x - 2)
がおそくなる理由は、単純に同じ計算を何度もさせているからのよう。
で、なにやらキャッシュ（この言い方は正しいのかな？）させて計算結果を再利用するとはやくなる。
コードはJDK1.5用。
public static BigDecimal fibo(int x) {
class Fibo {
Map m = new HashMap();
public BigDecimal fibo(int x) {
BigDecimal r = null;
if ((r = (BigDecimal) m.get(x)) != null)
return r;
switch (x) {
case 0:
case 1:
r = new BigDecimal(1);
break;
case 2:
r = new BigDecimal(2);
break;
default:
r = fibo(x - 1).add(fibo(x - 2));
}
m.put(x, r);
return r;
}
};
Fibo f = new Fibo();
return f.fibo(x);
}
いろいろな方法があるのだなぁ
スピードとしては最初の実装のほうが数がふえれば、はやい。
３０００で計ったら、
キャッシュ版２２秒
最初の実装５秒
でも
fibo(x - 1) + fibo(x - 2)
のほうが再帰させいるって感じがする。
３０００の結果
3000 664390460366960072280217847866028384244163512452783259405579765542621214161219257396449810982999820391132226802809465132446349331994409434926019045342723749188530316994678473551320635101099619382973181622585687336939784373527897555489486841726131733814340129175622450421605101025897173235990662770203756438786517530547101123748849140252686120104032647025145598956675902135010566909783124959436469825558314289701354227151784602865710780624675107056569822820542846660321813838896275819753281371491809004412219124856375121694811728724213667814577326618521478357661859018967313354840178403197559969056510791709859144173304364898001
[フィボナッチ数列][その２]
フィボナッチ数列 その２ 再帰に挑戦
再帰でフィボナッチ数列 を処理させるのがかっこいいらしい。
しかし、
fibo(x - 1) + fibo(x - 2)
とするとある程度の計算だとすごくCPUを使うっぽい。
fibo(x - 1) + fibo(x - 2)ではないやり方で再帰させてみた。
で、とにかく再帰させたいので、会社から帰宅途中、ノートとペンでロジックを考えてみた。
ここでは、
再帰の定義を自分自身から自分自身を呼び出せば、何でも再帰というふにした。
あとからプログラムをながめてみて、はじめ書いたfor文コードの焼き直しだなぁとわかった。
フィボナッチ数列のイメージを得るために、
a + b = c
b + c = d
c + d = e
d + e = f
e + f = g
という式をノートに書いた。これは上から順に値が移動していくイメージ
をつかむために。
それで、再帰的に処理をさせるために下から上にむかえばいいのだろうと単純に考えた。
結局下から上にむかってまた上から下に計算していくイメージ。
for文のものは上からダイレクトに計算させていくだけ。
public static BigInteger fibo(BigInteger[] bs, int x) {
if (bs == null)
bs = new BigInteger[1];
if (x == 1) {
bs[0] = new BigInteger("1");
return new BigInteger("1");
}
BigInteger r = fibo(bs, x - 1);
BigInteger R = r.add(bs[0]);
bs[0] = r;
return R;
}
使い方、
for(int i=1;i<=max;i++)System.out.println(i + " "+ fibo(null, i));
第一引数は実装上の副作用。
実行結果は以下
正しいと思うけど。。。。
1 1
2 2
3 3
4 5
5 8
6 13
7 21
8 34
9 55
10 89
11 144
12 233
13 377
14 610
15 987
16 1597
17 2584
18 4181
19 6765
20 10946
21 17711
22 28657
23 46368
24 75025
25 121393
26 196418
27 317811
28 514229
29 832040
30 1346269
31 2178309
32 3524578
33 5702887
34 9227465
35 14930352
36 24157817
37 39088169
38 63245986
39 102334155
40 165580141
41 267914296
42 433494437
43 701408733
44 1134903170
45 1836311903
46 2971215073
47 4807526976
48 7778742049
49 12586269025
50 20365011074
51 32951280099
52 53316291173
53 86267571272
54 139583862445
55 225851433717
56 365435296162
57 591286729879
58 956722026041
59 1548008755920
60 2504730781961
61 4052739537881
62 6557470319842
63 10610209857723
64 17167680177565
65 27777890035288
66 44945570212853
67 72723460248141
68 117669030460994
69 190392490709135
70 308061521170129
71 498454011879264
72 806515533049393
73 1304969544928657
74 2111485077978050
75 3416454622906707
76 5527939700884757
77 8944394323791464
78 14472334024676221
79 23416728348467685
80 37889062373143906
81 61305790721611591
82 99194853094755497
83 160500643816367088
84 259695496911122585
85 420196140727489673
86 679891637638612258
87 1100087778366101931
88 1779979416004714189
89 2880067194370816120
90 4660046610375530309
91 7540113804746346429
92 12200160415121876738
93 19740274219868223167
94 31940434634990099905
95 51680708854858323072
96 83621143489848422977
97 135301852344706746049
98 218922995834555169026
99 354224848179261915075
100 573147844013817084101
1000 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
再帰のこれって魔法みたい。
public static long fibo(long n) {
return (n == 0 || n == 1) ? 1 : fibo(n - 2) + fibo(n - 1);
}
[フィボナッチ数列][その１]
いまさらながら、算数、数学が苦手な僕は文系です。
で、プログラムを書くのは好きです。
苦手な、算数、数学にアプローチしてみました。
http://blog.livedoor.jp/dankogai/archives/50456147.html
http://www.hyuki.com/story/genfunc.html
フィボッナチッチ数列というようです。
計算はただしいと思う。。。
下記ジャヴァプログラム
package test.fib;
import java.math.BigInteger;
//ugo_ugo_ugoオリジナル
public class TestMain1 {
/**
* １から９９まで計算
*/
public static void main(String[] args) {
int max = 99;
for(int i=1;i<=max;i++){
System.out.println(i + " ==> "+ f(i));
}
}
/**
* 大きな値でも計算できると思う
*/
public static BigInteger f(int x){
BigInteger prepre = new BigInteger("1");
BigInteger pre = new BigInteger("0");
BigInteger result = new BigInteger("0");
for(int i=0;i<=x;i++){
result = prepre.add(pre);
prepre = pre;
pre = result;
}
return result;
}
}
計算結果
1 1
2 2
3 3
4 5
5 8
6 13
7 21
8 34
9 55
10 89
11 144
12 233
13 377
14 610
15 987
16 1597
17 2584
18 4181
19 6765
20 10946
21 17711
22 28657
23 46368
24 75025
25 121393
26 196418
27 317811
28 514229
29 832040
30 1346269
31 2178309
32 3524578
33 5702887
34 9227465
35 14930352
36 24157817
37 39088169
38 63245986
39 102334155
40 165580141
41 267914296
42 433494437
43 701408733
44 1134903170
45 1836311903
46 2971215073
47 4807526976
48 7778742049
49 12586269025
50 20365011074
51 32951280099
52 53316291173
53 86267571272
54 139583862445
55 225851433717
56 365435296162
57 591286729879
58 956722026041
59 1548008755920
60 2504730781961
61 4052739537881
62 6557470319842
63 10610209857723
64 17167680177565
65 27777890035288
66 44945570212853
67 72723460248141
68 117669030460994
69 190392490709135
70 308061521170129
71 498454011879264
72 806515533049393
73 1304969544928657
74 2111485077978050
75 3416454622906707
76 5527939700884757
77 8944394323791464
78 14472334024676221
79 23416728348467685
80 37889062373143906
81 61305790721611591
82 99194853094755497
83 160500643816367088
84 259695496911122585
85 420196140727489673
86 679891637638612258
87 1100087778366101931
88 1779979416004714189
89 2880067194370816120
90 4660046610375530309
91 7540113804746346429
92 12200160415121876738
93 19740274219868223167
94 31940434634990099905
95 51680708854858323072
96 83621143489848422977
97 135301852344706746049
98 218922995834555169026
99 354224848179261915075
正しいと思う。。。
で、メソッドの呼び出しを再帰させたほうがかっこいいらしい。
でも、上記のプログラムだと無駄な判定をしないで一気に計算させるからよいと思うのだけど。。。
インターネット上あがっているソースをちょこっとみると、swithcで1の場合、２の場合とわけたりしていた。
あとJavaだとBigDecimalがお手軽に使えるので大きな数字も大丈夫っぽい。
http://www.fobj.com/hisa/w/FibonacciNumbers.html
インターネット上にあがっていたソースをちょっこと自分用にして動かしてみた。
//改造
public class Fibo {
public static long fibo(long n) {
return (n == 0 || n == 1) ? 1 : fibo(n - 2) + fibo(n - 1);
}
public static void main(String[] args) {
int max = 40;
for (int i = 1; i < max; i++)
System.out.println(i + " " + fibo(i));
}
}
再帰を使ってシンプルなコードなのできれい。僕もこういうふうなシンプルなコードがかけたらいいなと思った。max値が増えるとちょっとおそくなるようだ。
ぐーぐるさんで調べたら、perlで書いた例があった。
http://www.namikilab.tuat.ac.jp/~sasada/prog/parrot-intro.html
: