ソースプログラムAを書いて、それをコンパイルして実行可能なプログラムBができあがる。プログラムBを実行したら、画面上の表示内容がAそのものになっている。

そういうソースプログラムAを自己印刷プログラムという。英語ではQuineという。

自己印刷プログラムはふつう、入力を使わない。入力ファイルを画面表示するだけなら簡単に作れるから。

C言語で作られている自己印刷プログラムに以下のようなもの2つがよく知られている。

main(a){printf(a,34,a="main(a){printf(a,34,a=0`,34);}",34);}

 

char*f="char*f=0`;main(){printf(f,34,f,34,10);} ";main(){printf(f,34,f,34,10);}

以下のものは多少長いが、いろいろ応用利きそう。

char*lines[]={
    "char*lines[]={",
    "0` ",
    "0};",
    "main(){",
    "int idx;",
    "puts(lines[0]);",
    "for(idx=0;lines[idx]!=0;idx++){",
    "printf(lines[1],34,lines[idx],34,',',10);",
    "}",
    "puts(lines[2]);",
    "for(idx=3;lines[idx]!=0;idx++){",
    "puts(lines[idx]);",
    "}",
    "}",
    0};
main(){
    int idx;
    puts(lines[0]);
    for(idx=0;lines[idx]!=0;idx++){
        printf(lines[1],34,lines[idx],34,',',10);
    }
    puts(lines[2]);
    for(idx=3;lines[idx]!=0;idx++){
        puts(lines[idx]);
    }
}

自分自身を表示する。哲学的な要素が含まれ、なかなか奥深い。

1974年度のチューリング賞を受賞したクヌースの受賞講演「芸術としてのプログラミング」にも、

 数年前、Stanford大学の学生たちは、自分自身を印刷する最短のFORTRANプログラムを見つけようとはりきったこともあります。

とわざわざ紹介してある。

最近のUVa問題集に,約数関連の問題がいくつも出ていました.いままであまり深く考えなかったことだけに,なんとなく嬉しく思ってしまいます.まだまだ身近に色々な面白い問題が残っていることだと.

#10858 Unique Factorization 素因数分解
#10879 Code Refactoring 素因数分解
#10892 LCM Cardinality 最小公倍数

図書館が身近にあって,普段よく利用していますが,約数の求め方についての解説では,除数として2からの整数で割ってみて,割り切れるかどうかを確かめればいい,という書物もあって.びっくりしました.その本に,おまけにBASIC言語のソースプログラムリストが付いたりしています.

そんな方法は数学的解法に過ぎません.計算時間という大事な観点が欠落しています.整数を2からひとつずつ割ってみるというやり方にすると,計算時間は整数1つにつき,その大きさに比例してしまいます.整数の最大値をM,整数の個数をNとすると,全体の計算時間は最悪 O(MN) になります.

時間的速いやり方としては,一旦素因数分解して,個々の素因数のあらゆる組合せから約数を合成するという方法だと思います.問題が簡単過ぎて,約数の求め方を真剣に言及する書物やネット情報はなかなかなく,約数の一覧表をもっとも速い方法で作り出すアルゴリズムを目下考えているところ.

頼りにしているのはつぎの数学定理.

整数 M = paqbrc… と素因数分解できれば,M のすべての約数は
   0 <= x <= a, 0 <= y <= b, 0 <= z <= c, ...
とすることによって漏れなくまた重複なく得られる.

なお,約数の数については,昔の記事にも書きましたが, (1+a)*(1+b)*(1+c)* … というものです.

また,最小公倍数の問題とは,最小公倍数を求めるものではありません.2つの整数 a, b の最小公倍数を LCM(a, b) で表すと,a と b の最大公約数 GCD(a, b) を Euclid 互除法で求めれば,LCM(a, b) = a*b/GCD(a, b) で簡単に求まるからです.

問題にしているのは,最小公倍数の値を N として与えられると,LCM(a, b) = N の a, b ペアの組合せをすべて求めることです.

例えば,最小公倍数が 12 となる整数ペアの組合せは

  (1,12) (2,12) (3,4) (3,12) (4,6) (4,12) (6,12) (12,12)

の8ペアです.なお,a と b の入れ替わったペア,例えば (12,1) はカウントされません.組合せですので.

最小公倍数の値が大きくなると,そのペア数は簡単に求められるかどうか,考えてみたいものです.

円盤の移動回数と各塔の状態との関係についてのメモです.

3本ある塔を, 左から 0, 1, 2 と番号づけます.
円盤の枚数は n 枚です. 小さいほうから 1, 2, 3, … n と番号づけます.
初期状態 (n枚の円盤が塔番号 0 に置かれていた状態)から, m回目の移動が終わった時点において, 各塔に置かれる円盤の状態は以下のとおりです.

  xi ≡ xi+1 + (-1)n-i(bi – bi+1)   (mod 3)   ( i は 1~n )

 xi: 円盤 i ( i は 1 から n) が置かれた塔の番号. つまり, 0, 1, 2 のどれか. ただし, xn+1は 0 とする.
 bi: m の 2進数表示 bnbn-1 … b1. ただし, bn+1は 0 とする.

<例>円盤が3枚ある. 5回目の移動が終了した時点での各円盤の置かれた位置を算出してみよう.
  5の 2進数表現は 101 なので, b3=1, b2=0, b1=1.
  決まりから, x4 = 0, b4 = 0.
  x3 ≡ x4 + (-1)3-3( b3-b4) ≡0 + (1-0) ≡ 1
  x2 ≡ x3 + (-1)3-2( b2-b3) ≡1 – (0-1) ≡ 2
  x1 ≡ x2 + (-1)3-1( b1-b2) ≡2 + (1-0) ≡ 3 ≡ 0

つまり, x1 = 0, x2 = 2, x3 = 1
円盤1が塔0に置かれ, 円盤2が塔2に置かれ, 円盤3が塔1に置かれている.

計算量は当然 O(n) . n: 円盤の枚数

省略しますが, 円盤の置かれた途中状態 xi から, スタートからの移動回数 m の2進数表現 bi も簡単に計算できる.

以上で判るように, 少なくとも塔3本のケースにおいては, 移動回数と円盤の状態が完全に数式で判ります.

練習となるACM問題
 #254 Towers of Hanoi