１）課題
左側の数値に対し、それ自身を超える直前までのフィボナッチ数列を右側に運んで下さい。
例えば、入力が１０である場合、出力は１ １ ２ ３ ５ ８となります。
フィボナッチ数列に関する詳しい話は、そこで見ている上司にきいてみましょう。
２）アルゴリズム
問題文と上司に教えてもらったことから, フィボナッチ数は次のように計算できます.
１＋１＝２１＋２＝３２＋３＝５３＋５＝８５＋８＝１３
字下げを取り除いて表の形式にし, 各列にラベルを付けます.
Ａ Ｂ Ｃ１＋１＝２１＋２＝３２＋３＝５３＋５＝８５＋８＝１３
この結果から, カーペットに置いたパネルの動かし方が分かります.
次に, 上司に解答例を示してもらいます.
解答例では, 始めに「1, 1, 」と出力しています. これも考慮に入れて計算手順を見直します.
Ａ Ｂ Ｃ０＋１＝１１＋１＝２１＋２＝３２＋３＝５３＋５＝８５＋８＝１３
０と１を加えることから始めると, 「１」を出力する見通しが立ちました.
更にカーペットの初期状態も含めて考えます. 「＋」や「＝」の記号を取り除き, カーペットの数値の変化に注目できるようにします.
Ａ Ｂ Ｃ０ ０ １０ １ １１ １ ２１ ２ ３２ ３ ５３ ５ ８
１行目から２行目, ２行目から３行目へと移る時, 次の操作をします.
- 「C」を右のコンベアに運ぶ.
- 「B」から「A」にコピーする.
- 「C」から「B」にコピーする.
- 「A」と「B」を加えた結果を「C」にコピーする.
Cの値が左のコンベアから取り出したパネルの値を超えたところで終了です.
３）実装
上で考えたアルゴリズムを使ってプログラムを作ります.
始めに, カーペットを初期化します. カーペットに名前を付け, パネルを配置します.
プログラムの本体に取り掛かります. プログラムの流れは次のようになります.
- 「上限」と「C」を比較します.
- 「C」の方が大きければ先頭に戻ります.
- 「上限」の方が大きければ, 「C」を出力します. 続けて「B」を「A」に, 「C」を「B」にコピーし, コピー後の「A」と「B」を加えた結果を「C」にコピーします.
- 先頭に戻ります.
この流れに沿って, プログラムを作ります.
10行目のJUMP if negativeコマンドは, 「上限」から「C」を引いた値が負であれば先頭に戻っています. 11行目以降で, 「C」を右のコンベアに運び, 次のフィボナッチ数を求めるための処理を記述しています. これを実行すると課題をクリアーできます.
0 件のコメント:
コメントを投稿