140文字プログラム集（5） - プチコンで遊ぼう！ (はてなブログ版)

Twitterアカウント(@eida_s)上でつぶやいた、140文字以内でできているプログラムのまとめ(5)です。

なお、まとめ(1)から(5)のリンクは以下の通り。
140文字プログラム集（1）
140文字プログラム集（2）
140文字プログラム集（3）
140文字プログラム集（4）

■140文字プログラムNo.14　140STAR (2012.03.15)

FOR I=0 TO 1:GCOPY 0,0,255,190,0,1,1:GLINE 0,0,255,0,0:GPSET RND(256),I,RND(12)+2:VSYNC 1:I=0:NEXT

(98文字)

【遊び方】
星がスクロールで流れます。ギャラクシアンの背景のイメージですね。

【プログラムの解説】
今回から、プチコンmkIIの機能を使っています。
mkIIから追加されたGCOPYを使ってグラフィック面のスクロールを実現しています。
速度が気にならなければ、これを使ってゲームも作れそうです。

■140文字プログラムNo.15　140PAI (2012.06.04)

C=999DIM A(C)F=100↓
@1↓
E=D%F:D=E↓
FOR B=C-1TO 1STEP -1G=B*2-1D=D*B+F*(A(B)+!P*20)A(B)=D%G↓
D=0OR(D/G)NEXT↓
P=0OR E+D/F?"0"*(P<10);P;↓
C=C-9GOTO@1

(140文字)

【遊び方】
ただ単に実行してください。円周率を表示します。
ちょうど140文字のプログラムで円周率222桁を出力することができました。
（エラーで停止するようになっています。ちゃんと停止するバージョンもありますが、140文字では収まりませんでした。）

このプログラムはプチコン起動直後に入力、RUNしてください。（またはCLEARの実行後にRUNしてください。）
↓実行した時の様子。

【プログラムの解説】
今回はかなり苦労しましたが、その代わりに新たに開発できたテクニックが２つほどある。

C言語における三項演算子(A?B:C)っぽい記述方法

　Aは真偽値が入るものとし、1または0が入っているとする。この時にBかCの結果を得たい。
　この時、X=A*B+!A*C
　上記ではさらに変形して利用している。これはNo.16の方が素直なかたちで使われているのでNo.16も参照のこと。

桁揃えをmkIIの新機能を使い短く記述する方法

　?"0"*(P<10);P
　これは2桁の例。
　Pが9以下の時は、()内の式が1の値をとるので、"0"*1 となって、これは "0" となる。
　Pが10以上の時は、()内の式が0の値をとるので、 "0"*0 となって、これは "" となる。
　後者の事実が非常に重要で、これにより桁揃えを短く記述できた。

【円周率の計算アルゴリズムに関わる参考資料】
以下のページのソースコードを下敷きにして作りました。
こつこつアルゴリズム(Spigot Algorithm)

この計算方法はSpigotアルゴリズムというものです。
以下の論文（英語）のPDFに詳しく書かれています。
A Spigot Algorithm for the Digits of Pi

また、以下のサイトはプログラムの解説が詳しく書かれています。
円周率.jp Spigot アルゴリズム

検証は、東京大学金田研究室のSUPERπ WiNDOWS版の出力との比較によって行いました。

■140文字プログラムNo.16　140コラッツ (2012.06.15)

ACLS:I=0INPUT X:Z=X*3/256↓
@T↓
?X;:GBOX 0,I,X/Z,I,2I=I+1IF X==1THEN LINPUT A$:END ELSE P=X%2X=P*(X*3+1)+!P*X/2?",";:GOTO@T

(120文字)

【遊び方】
コラッツ予想(任意の正の整数Nに対し、(1)奇数ならばN*3+1,(2)偶数の時N/2、を繰り返すと最後には1になる)を体験するプログラムです。
正の整数を入力してください。結果は自動で表示されます。
ただし、5桁の数を入力するとオーバーフローすることがあります。
数字だけでなく、ついでに棒グラフで数値の動きをグラフ化してみました。
負数や小数も入力できてしまいますが、元の定義上は意味がないので、残念ながら対応していません。

【プログラムの解説】
No.15でも書いた、三項演算子相当の演算を入れています。

P=X%2
X=P*(X*3+1)+!P*X/2

により、奇数ならば３倍して１を足す、偶数ならば２で割る、を実現しています。
どんな仕組みかはそれぞれの場合に具体的な値を入れて考えてみていただければ、理解可能かと思います。

【コラッツ予想について】
20世紀前半に数学者コラッツが提出した問題で、コラッツ自身は全ての正の整数に対して成り立つのではないかと予想しました。
こんな簡単そうな問題なのに、現在に至るまでその証明は確認されていません。
16桁くらいまでの正の整数すべてに成り立つことは確認されているので、プチコンの精度の範囲の数はすべて成り立つのですが、自分で数字を入力してみて不思議さを体感するのが今回のプログラムの目的。

一見簡単そうなので、証明した！という報告は数知れずありますが、実際に数学界で認められたものはありません。
そういう意味では、角の三等分問題などと似ていますが、角の三等分は元の条件であるコンパスと定規の作図だけでは不可能であることが証明されているのに対し、コラッツ予想はまだ可能か不可能か自体証明されていないので、まだ見込みはあります。
興味を持った方はインターネットなどで調べてみては？
コラッツの問題 - Wikipedia

■キーワード達成率
2012/06/15現在、55/172　３２．０％