質問＜３６７１＞２００８年１月１６日from=RS「BASICのプログラム」

nには必ず自然数が入ります。そのとき、つぎのプログラムはなにをするものでしょうか？

100 LET a=0
110 LET b=1
120 INPUT n
130 FOR k=0 TO n
140    PRINT k,a
150    LET c=a+b
160    LET a=b
170    LET b=c
180 NEXT k
190 END

私は、まったくのコンピュータの素人です。テキストを見ながら各行で何を指示しているのかはわかるのですが、出力されるnとaの関係がまったく分かりません。
アドバイスをお願いします。

★希望★完全解答★

---

私は、まったくのコンピュータの素人です。

極端な話、全然構いませんがね(笑)。
まあ、ハッキリ言っておきますが、これはRSさんのせいじゃなくって、「プログラムの問題」として考えた場合、あんまり「良くない」問題だとは思います。どっちかと言うと純粋な「数学の」問題なんです(数学的にはそんなにレベルは高くないんですが)。
つまり「テキストを見ながら各行で何を指示しているのかはわかる」んならそれで結構です。しかし、「それが何の計算か?」と問われたら、それに答えるのには数学の知識が必要でしょう。ナゾナゾじゃないんだから(笑)、一体何のつもりなんだか(笑)?

普通は逆なんですよ。数学とプログラミングの親和性を説明したいんだったら、

数学では××とは△△と言う定義である。これをプログラミングしなさい。

ってのなら分かるんですが、逆に

あるプログラムがある。これを数学では何と言うか?

なんて言われても「知るか!!!」って事です(笑)。ふざけるのもいい加減にしろ、とか思いますね(笑)。
何か投稿見てるとBASICとかPASCALってこう言う「悪問」多いですよね。どう言う質問の仕方なんだか、とか思っちゃう。

ええと、一応断っておくと、この「プログラム」は確かに、再帰的定義を説明するには良く使われる例なんです。従って、ある程度プログラムの勉強してきた人にとっては初見じゃないんで、

「ああ、こんなの過去組んだ事があるなあ。」

ってんで分かるだけ、です。
逆に言うと、初見で数学の知識が無い場合、

「このプログラムは何をやってんでしょう?」

とか言われても分かるワケありません(笑)。足して変数交換して繰り返し計算してるんじゃないの?…としか言いようがありません(笑)。当たり前です。
だから出題者が悪いんですよ。優しくない。悪問の典型ですね。
と言うワケでRSさんが申し訳なく思う必要性はありません。

ええと、結論から言うと、これはフィボナッチ数列と言われる数列を出力するプログラムです。
一般に、フィボナッチ数列とは次の数式で表されます。

例えば、、なんで

ですね。同様に、、なんで、

となりますね。
下に、フィボナッチ数をaとして、数列の添字k(0≦k≦50)の範囲の一覧表を挙げておきます。




実際、BASICのプログラムを手元で走らせてみて、数値が上の表と一致しているかどうか確かめてみてください。
プログラム内では取りあえず

と置かれていて、kの値が一つづつ増えるに従ってそれぞれの変数が

と書き換えられるだけ(ズレて行ってる)、です。そう言うロジックで動いています。
(この辺は、「テキストを見ながら各行で何を指示しているのかはわかる」のでしたら、既に自明でしょう)

以上です。

---

ちなみに、Schemeと言う言語で書くと、次のようになるでしょう。

(define (fib)         ;関数fibを定義
(let ((n (read)))    ;入力を促す
  (let loop ((a 0)   ;aの初期値は0
             (b 1)  ;bの初期値は1
             (k 0)  ;kの初期値は0
             (ls '("k" " " "a" "\n"))) ;リストの初期値をラベルとする
    (if (> k n)                        ;kがnを越えた時
        (for-each display ls)          ;リスト(結果)を表示する
        (loop b                        ;aがbとなる
              (+ a b)                  ;bがa+bになる
              (+ k 1)                  ;kが1増える
              (append ls (list k " " a "\n"))))))) ;リストを合成する 

なお、\nと言うのは改行記号です。