↓下の記事で「循環節」の話をしました。
http://yamada-kuebiko.cocolog-nifty.com/blog/2016/04/post-9c1b.html
2016年4月 7日 (木)「1÷9801のふしぎ」
循環節の長さは198でした。
よく知られているように、
1/7=0.14285714285714285714285714285714…
ですが、分母が7だと循環節は最長で6までです。
分母が9801ですから、循環節は最大で9800ですが、まさかね、とは思いましたけど
198というのは長い。
この記事中では、自分の手で50桁ごとに切って、循環節が198であることを調べたのですが、こういうのはプログラムにやらせたい。
思えば今から40年くらいも昔。BASIC電卓というのを購入して、いろいろ遊んだ中で、循環節の長さを求めるプログラムを書いた記憶があります。確か「355/113」の循環節の長さを調べようと思ったのではなかったか。授業に行く前にプログラムをスタートさせ、授業から戻ってきてもまだ実行途中だった、というような記憶があります。どんなアルゴリズムを作ったのかはもう忘れました。
★今回、再チャレンジ。
「1÷7」の計算をエクセルの表の上で表現してみました。
●右に筆算風に。
●左には割り算の実行過程を分解して表現。
・まず:割られる数1と、割る数7を書きます。その隣C列に割り算の整数部分を求める関数を書き、D列に割り算の余りを求める関数を書きます。
・余りを10倍して割られる数とします。割る数は同じ。C列に割り算の整数部分、D列に余り。
・以下同文
単純ですね。式で簡単に表現できます。
これです。
1行目はちゃんと入力。
INT()という関数は整数部を取り出す関数。MOD()という関数は余りを取り出す関数です。
2行目は1行目のA~D列をまとめてセレクトして下へ引っ張ってコピーすればいい。
以下も同じくコピーで済みます。
ただ、循環状態になったかどうかは目で人間が判断する必要があります。
適当に長く引っ張ってコピーして、循環節を見つけてください。
一旦、できてしまうと、最初の1と7の部分の数を書きかえれば、自動的に計算が実行されますので、いろいろ試すことができますよ。
★上で分析した考え方でプログラムを作りました。
その際の問題点は、同じ余りが出て循環に入ったことを検知して割り算を停止し、結果を表示することです。
停止しないものはプログラムとは言いません。プログラムは必ず停止しなければならないのです。
割る数をmとしましょう。循環部分の長さは最大でm-1です。
そこで、配列という番号付きの変数を(m-1)個用意します。
{無駄といえば無駄です。ほとんどの場合(m-1)個も使いません。}
初め、これを全部0にします。
割り算を実行したときの余りが例えば4としましょうか。そうしたら4番の変数を1にします。
つまり変数の値が0ならまだこの余りは出ていない、1なら既に出た、という状態を示す「旗=フラグ」という使用法です。
こうやって、余りが繰り返されるまで割り算を実行し、同じ余りが出たらそこで割り算を停止し、割り算の整数部として保存しておいたものを表示してプログラムは終了。
これ、うまくいったのです。「純循環小数」についてはね。
★ふと思った。割り切れたらどうなるんだ?
やってみると、プログラムを書いた者としてはプログラムの動作がわかっていますから、不自然ですが答えは出ます。
でもなぁ、プログラムは他人が使うことを前提に書くべきものです。
それはちょっと恥ずかしい。
★手直ししながら。
「混循環」というのもあったよなぁ。あれはどうなる?
混循環についても、プログラムを書いた者にはどういう答えを返してきたのかわかりますが、かなりひどいことになった。
1/56=0.01785714285714285714285714285714・・・
これ、循環節は「857142」で、その長さは6ですが。
私のプログラムでは「0.017857142」を表示して停止しして、あたかも小数点以下の9桁が繰り返すように見えてしまうんですね。
これはマズイ。
で、接ぎ(パッチ)を当てるように修正していって最終的なプログラムにたどり着きました。
↓解説しません。アルゴリズムの根幹は上の述べたようなものです。細部で、割り切れや混循環に対応しています。
「Junkanshosu.txt」をダウンロード
★結果の例をいくつか。
calc m / n
m = 1
n = 7
0 .{142857}
6
「calc m / n」と表示し、mとnの入力要求が出ます。
{ }にくくられた部分が循環節です。その長さが最後の行に表示されます。
calc m / n
m = 100
n = 7
14 .{285714}
6
100/7にしても大丈夫。
calc m / n
m = 22
n = 7
3 .{142857}
6
有名なπの近似分数です。
calc m / n
m = 1
n = 17
0 .{0588235294117647}
16
循環節が長い例。n=17の時、循環節の長さはn-1=16。正しい。
calc m / n
m = 1
n = 9
0 .{1}
1
あまり循環と思わない例。小数点以下1だけがずっと続く例。
calc m / n
m = 1
n = 9801
0 .{00010203040506070809101112131415161718192021222324
25262728293031323334353637383940414243444546474849
50515253545556575859606162636465666768697071727374
757677787980818283848586878889909192939495969799}
198
例の循環節の長い話。ちゃんと長さ198が得られました。ヨカッタ。
calc m / n
m = 1
n = 113
0 .{00884955752212389380530973451327433628318584070796
46017699115044247787610619469026548672566371681415
929203539823}
112
πの近似分数「355/113」に出てくる「1/113」
循環節の長さ112でした。
calc m / n
m = 355
n = 113
3 .{14159292035398230088495575221238938053097345132743
36283185840707964601769911504424778761061946902654
867256637168}
112
πの近似分数そのもの。
calc m / n
m = 1
n = 2
0 .5
割り切れた場合
calc m / n
m = 1
n = 8
0 .125
ちゃんと表示されています。
calc m / n
m = 1
n = 56
0 .017{857142}
6
混循環の例。
循環節もその長さも正しく表示されています。
calc m / n
m = 1
n = 152
0 .006{578947368421052631}
18
メデタシ、メデタシ。なのでした。ウレシイ。
ここで作成したアルゴリズムは自由にお使いください。
著作権は主張しません。
ただし「完璧」なプログラムなんてものを保証はできませんので、変な結果が出ても責任は負いかねます。工夫して改良してください。{こんなプログラムで商売しようという人もいないでしょうけど。}