再帰について 漸化式
解決VBはじめたばかりの初心者です。しょぼい質問で申し訳ございません。
再帰というものを知ってからなんでも再帰で試してみたくなってしまいました。
漸化式 nCrを解くプログラムをつくりたいのですが、再帰を使わないで解く
のは作れるのですが、 再帰版の理屈がいまいちわかりません。
private Function ncr(n as variant,r as variant) as variant
if r=0 or r=n then
ncr=1
else
ncr=ncr(n-1,r)+ncr(1-1,r-1)
end if
end function
だと思うのですが、動作の理屈がいまいちつかめません。他のシンプルな再帰は
分かるのですが・・・ガシガシとスタックに積まれる感じがイメージできないのです・・どなたかよろしくおねがいいたします。
ううー、ごめんなさい、再起とかはよくわかりませんっ(^^ゞ
ただ、関数を日本語になおせば…。少しはお役に立てる…かも。
まず、nとrですけど、Longとかの数値型ですね、
Variant型では、多分計算がとくに遅いと思うので…。
あと、もどりちも。
ええと、つづきですけど、
if r=0 or r=n then 'もし、rとnが0だったら
ncr=1'もどりちはⅠ
else'そうでなかったら
ncr=ncr(n-1,r)+ncr(1-1,r-1)'もどりちはn-1Crと、0Cr-1をたした答え
end if
ん…？ncrの答えに、またncrで計算してだいじょうぶなんでしょうか？
2,3回のループのあと"スタックが不足しています"のエラーのあと、強制終了しそうな気がします。
それと、0Cr-1はrがいくらであってもおかしな計算になるような…。
え、たしか実際には、nをr回1ずつ引きながらかけていって、
rもr回1ずつ引きながらかけていって、ふたつを割るんですよね？たしか。
(知ってそうたっていないというのに、なんと恥ずかしい…(--;)
なら
'変数は全てLong型
for i = n to n - r
ans = ans * i
next
for i = r to r - r
ansB = ansB * i
next
nCr = ans / ansB
(実際やってみないとちょっとわからないです^^;)
こんな風なほうが確実だと思うんですけど…。
(再帰の意味がよくわかっていないので、もしそうじゃないというのならごめんなさい
ただ、関数の中で同じ関数を呼び出すのは、
確実に同じルートをとおることがないという確信がない限り、できないです)
はじめての投稿で回答のご教授の書き込みがありとてもうれしいです。
回答ありがとうございました。
＞ncr=ncr(n-1,r)+ncr(1-1,r-1)'もどりちはn-1Crと、0Cr-1をたした答え
＞end if
＞ん…？ncrの答えに、またncrで計算してだいじょうぶなんでしょうか？
再帰を使うときはぼくは、関数の答えに再帰で呼び出した戻り値を代入して
いるのですが、これはただしくなかったのかも？？
最初の再帰版でも計算結果は出せるのですが・・・
もうちょっと考えてみます。
普通に再帰なしですと
priate Functioo ncr(n as long,r as long) as long
x=1
for i=1 to r
x=x*(n-i+1)/i
next i
ncr=x
end Function
でn=5 r=3 で10 と正しく計算できました。
いろいろ再帰で数学の計算のプログラムを作っているうちにカン??といいますか
なんとなく一般式のようなものが見えてきました。
今日、C言語アルゴリズム辞典という本を借りてきましたのでそちらで、
もう一度考えてみます。 しょぼい質問にお付き合いいただいてありがとうございます。はっきり分からないととっても気になってしまうのです。すみません。
こんにちはsinghさん。
よくわかりませんがこんな感じで如何でしょうか？
Public Answer As Double
Private Sub Command1_Click()
Call nCr(Text1.Text, Text2.Text)
End Sub
Private Function nCr(n As Variant, r As Variant) As Variant
If r = 0 Then
Text3.Text = Answer
Exit Function
Else
Answer = Answer * n / r
Text3.Text = Answer
Call nCr(n - 1, r - 1)
End If
End Function
Private Sub Form_Load()
Answer = 1
End Sub
{ てきすと１にＮ、てきすと２にＲ、てきすと３に答えを表示。
ぼたん１を押すと計算。}
言い忘れましたがエラートラップ書いてないのでこれをもしこのまま
実行する場合はＮとＲを自然数（Ｎ＞Ｒ）にして下さい。（空白も×）
皆様 ご指導ありがとうございました！再帰についてようやく分かりました。
はじめはまったく意味不明だなーとおもっていたのですが、慣れると理解できました。再帰でいろいろプログラムしていると再帰のほうが早い場合、遅い場合があるのですね。 今はフーリエ変換などのプログラムを作りたいと思っています
初心者まるだしのぼくに皆様ありがとうございました。
| ツイート |  |