1)課題
右側のパネルの数値に対し、素因数分解を行い、答えを右側に運んで下さい。
答えは昇順、すなわち小さい順に運んで下さい。
2)考え方
カーペットが25枚とかなり広いので, 素数表を作る方法も考えましたが, 地道に割り算していくことにします.
基本的な考え方として, 割るべき素数を2から始め, 割り切れれば割り算に使った素数を右のコンベアに運び, 割り算の結果の商を次の割られる数にします. 割り切れない場合は, 素数を1増やして割り切れるか試します.
素数に入る数字は4など合成数になる時がありますが, 4で割り切れるなら2でも割り切れているので, 結果には影響しません. 効率は悪いですけれども.
3)初期化
カーペットに名前を付けます.
- ZERO:カーペットに配置してある0をコードでも識別しやすいように名前を付けます.
- 入力:左のコンベアから取り出したパネルを保存しておきます. 素数で割り切れなかった時, 割り算をやり直すために使います.
- 余り:引き算を繰り返して割り算をしますが, 引いた残りの値を記録します. 余りが0になれば, 割り切れたと判断できます.
- 商:割り算の結果を記録します.
- 素数:素因数分解するための素数の候補を記録します.
カーペットに名前を付け, 値を配置します. 「素数」には2を設定します.
4)割り算
「素数」で「余り」を割っていきます.
「余り」から「素数」を引き, 結果が0になれば「素数」で割り切れたたことになりますので, 「われた」に進みます.
「余り」から「素数」を引いた結果がマイナスになった場合, 「素数」では割り切れなかったので, 次の素数で割ることを考えます.
5)割り切れなかった
割り切れなかった場合, 「素数」を1増やして割り算をやり直します.
「入力」に退避していた割られる数を「余」にコピーし, 8行目に戻ります. 8行目に戻る理由は, 「商」を0で初期化するためです.
6)割り切れた
割り切れた場合, 「素数」を右のコンベアに運び, 次の割り算に備えます.
割り切れた場合, 「素数」を右のコンベアに運びます. 忘れずに「商」を1増やしておきます.
24行目で「商」と「素数」の大小を比較しています.
「素数」の方が大きい場合は, 素因数分解が完了したと判断できるので, 先頭に戻ります. この時, 「商」は1になっているので, 1との比較をした方が良いのでしょうが, この実装で進めます.
「商」の方が大きければ, 5行目に戻り, 「商」の値を「余」と「入力」にコピーして, 「商」の素因数分解を試みます.
ここまでの内容を実行すると課題をクリアーできました. サイズ目標を達成できています. スピード目標はこの次に考えます.
0 件のコメント:
コメントを投稿