久々にJuliaです。
今回はコラッツ予想（3n+1問題とかコラッツの問題とか角谷の問題とかまぁ色々呼び名はあるらしい）をJuliaで計算してみようかと思います。
コラッツ予想って何？
そもそもまずはコラッツ予想についてまとめていきましょう。
コラッツ予想は、「整数ｎが奇数なら3倍して1を足す、偶数なら2で割るという操作を繰り返すとどんな数でも1になる」っていうものです。
例えば10だったら
10 > 5 > 16 > 8 > 4 > 2 > 1
という感じになるってことです。
今のところ\(2^68\)まで反例がないことは確かめられているそうです。
2011年のセンター試験の数ⅡBの大問6でもコラッツ予想を元にした問題が出題されたりしてます。
東進さんのページに過去問載ってたので、気になる方はリンクからどうぞ
コラッツ予想をJuliaで計算する
コラッツ予想を計算するアルゴリズムはかなり単純です
整数ｎに対してｎが奇数なら3倍して1を足す、偶数なら２で割る。これを1になるまで繰り返す。
コラッツ予想の計算は、再帰関数を使って計算するとかなりシンプルなコードを書くことができます。
ソースコードはこんな感じです。
function collatz(n)
println(n)
if n != 1
if n % 2 ==0
collatz(n/2)
else
collatz(3*n+1)
end
end
endこれで完成。
1まで計算だから、(if n != 1)っていう条件式で1以外の時に再帰するようにしてます。
juliaの場合はifや関数の終わりはendをつけるようになってるのでお忘れなく。
とっても見やすいですね。
あとはcollatz(10)とかって使えばですね。10からコラッツの問題の操作をして１に至るまでの数字がだ～っと表示されます。
標準入力を使って好きな数字からコラッツ予想を計算する
コラッツ予想を計算する関数を作ることができました。
標準入力などの機能をつけ足して一つのプログラムに仕上げましょう
標準入力などをプログラム全体の流れを動かすためにメイン関数を作って、そこからコラッツの計算関数を呼び出してみましょう
コラッツ関数を少し修正する
collatz関数も少し手を加えます。
先ほどのソースコードだと、整数の計算をしてるのに小数点が表示されたり、何回目の計算かわからなかったりするので、それを補うように書き換えます。
using Printf
function collatz(n,x)
@printf("%d:%d",x,n)
if n != 1
if n % 2 ==0
collatz(n/2,x+1)
else
collatz(3*n+1,x+1)
end
end
endxという引数を追加して、これで、何回目の計算かを求めていきます。
次の計算をする時にインクリメントした値を渡すだけですけどね。
次に@printfっていうフォーマット形式で表示するためのマクロを使って、表示を整えます。
メイン関数で標準入力を行う
メイン関数で標準入力を行いましょう。
readline()で入力を受け付けできるので、parseを使って整数型に変換しておきましょう。
あとは、それをコラッツ関数に渡します。
これで出来上がりです。
これは、コラッツ関数に限らず、入力の処理やプログラム全体の流れを作るのにメイン関数やそのほかの処理の関数を分けて書くことで、見通しがよくなりますね。
function main()
print("Enter the number:")
n = parse(Int,readline())
collatz(n,0)
end
main()まとめ
今回はコラッツ予想（コラッツの問題）を取り上げました。
Juliaは本当に手軽に書けて、そして計算スピードも速いので、ちょっとしたときに便利です。
とっても単純な計算ですが、再帰を使ってシンプルなアルゴリズムで書くことができました。
再帰といえば、フィボナッチ数列なんかも有名ですので、そちらも試してみてはいかがでしょうか？
ではまた
コメント