wikipediaサーフィンしてたらコラッツの問題ってのを見つけました。
擬似コード
def collatz(n)
show n
if n.odd? and n > 1
collatz(3n + 1)
else if n.even?
collatz(n / 2)
Go
実際に動かしてみたくなって最近はgoにハマっているのでgoで書いてみた。
工夫した所は
・引数で最初の値を取れるようにした。
・大きい値が処理できるようにuint64で処理するようにした。
・一個一個の答えが見られるように0.5秒のsleepを入れた。
package main
import (
"flag"
"fmt"
"time"
)
func main() {
n := flag.Uint64("n", 1, "collatz start num")
flag.Parse()
num := *n
if num < 1 {
fmt.Println("Invalid value:", num)
return
}
collatz(num)
}
func collatz(num uint64) {
fmt.Println(num)
time.Sleep(time.Second / 2)
if num%2 == 1 && num > 1 {
collatz(3*num + 1)
} else if num%2 == 0 {
collatz(num / 2)
}
}
書いてみて思ったんですが、hello world書くよりいろいろ学べそうじゃないですか？
標準出力はもちろん、関数の作り方呼び方、比較演算子、算術演算子、if
なので今後新しい言語でhello worldしたら次はコラッツの問題を書いていこうかな〜って思った次第です。
修正版(2015/06/07追記)
コメントを頂いたので指摘された点を直してみました。
コードが長くなったので、hello worldの代わりに軽く言語を試したいレベルの時はここまではしなくていいかも。
追加機能は
・答えが1以外になった時に終了ステータスが1で終了するように修正
・無限ループで答えが1以外になるかエラーで落ちるまで終わらない機能を追加
・ターゲット数までループする機能を追加
・スリープしないフラグを追加
くらい
package main
import (
"flag"
"fmt"
"os"
"time"
)
var isSleep bool
func main() {
n := flag.Uint64("n", 1, "collatz target num. infinite loop if it was the this flag is 1 and l flag is true.")
l := flag.Bool("l", false, "loop from 1 to the target. infinite loop if it was the this flag is true and n flag is 1.")
s := flag.Bool("s", false, "0.5 seconds sleep every calculation.")
flag.Parse()
num := *n
isSleep = *s
loop := *l
if num < 1 {
fmt.Println("invalid value:", num)
os.Exit(1)
}
if loop {
if num == 1 {
for i := uint64(1); ; i++ {
loopCollatz(i)
}
} else {
for i := uint64(1); i <= num; i++ {
loopCollatz(i)
}
}
} else {
ret := collatz(num)
retCheck(ret)
}
}
func loopCollatz(i uint64) {
ret := collatz(i)
fmt.Println("----------")
retCheck(ret)
}
func collatz(num uint64) (ret uint64) {
fmt.Println(num)
if isSleep {
time.Sleep(time.Second / 2)
}
if num > 1 {
if num%2 == 1 {
ret = collatz(3*num + 1)
} else if num%2 == 0 {
ret = collatz(num / 2)
}
} else {
ret = num
}
return
}
func retCheck(ret uint64) {
if ret != 1 {
fmt.Println("invalid collatz return:", ret)
os.Exit(1)
}
}
ShellScript
さっそくシェルスクリプトで書いてみました。
計算にはbcコマンドだと大きい値が使えるらしいのでbcコマンド使いました。
#!/bin/sh
collatz() {
n=$1
echo $n
sleep 0.5s
if [ `echo "$n % 2" | bc` -eq 1 ] && [ $n != "1" ]; then
collatz `echo "3 * $n + 1" | bc`
elif [ `echo $n % 2 | bc` -eq 0 ]; then
collatz `echo $n / 2 | bc`
fi
}
collatz $1
ifの書き方とか引数の指定とかでけっこう引っかかりました。
でもこれで99999999999999999999999999999999999999999999999999999999999999995まで計算出来ました。
それ以上はエラーが出ました。
エラー詳細→bcコマンドの限界は68桁？(回避方法あり
wikipediaには
この予想は、初期値が 5 × 2^60 = 5,764,607,523,034,234,880までは成り立つことがコンピュータでチェックされている。
と書いてありましたがまさか新記録！？
・・・なわけないとは思いますがｗ
Dart
Goが好きなのでGoogle繋がりでDart触ってみました。
※DartEditorで書いてます。
import 'package:collatz/collatz.dart' as collatz;
import 'package:args/args.dart';
import 'dart:io';
main(List<String> arguments) {
final parser = new ArgParser()..addOption('num', defaultsTo: '1', abbr: 'n');
ArgResults arg = parser.parse(arguments);
int num = int.parse(arg['num']);
if (num < 1) {
print('invalid value:' + arg['num']);
exit(1);
}
collatz.collatz(num);
}
library collatz;
collatz(int n) {
print(n.toString());
if (n > 1) {
if (n % 2 == 1) {
collatz(3 * n + 1);
} else {
collatz((n / 2).round());
}
}
}
- Dartエディタで新規プロジェクトを追加すると、bin/main.dartとlib/collatz.dartが別々に作られたのでその構成のまま書いてみました。
- 「n / 2」の計算が勝手にdoubleに変換されてしまい、警告が出たので「.round()」を使用しています。
- フラグ関数の戻り値で型が決まっているGoと違い、フラグはすべてString型なので自分で変換するのがちょい面倒。
- フラグ関数で正式名と省略名を定義できるのは良いと思った。(abbrで定義しているのが短縮名。短縮名は-で、正式名は--で指定できる。)
- メソッドカスケード(「..addOption」の..)が初めは何なのかわからなかったです。