C言語・雑談 – C言語とPC

238月 2008

自己印刷プログラム

by admin

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

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

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

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

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

1	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);}

1	charf="charf=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]);
    }
}

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プログラムを見つけようとはりきったこともあります。

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

128月 2005

約数、最小公倍数

by admin

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

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

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

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

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

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

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

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

また，最小公倍数の問題とは，最小公倍数を求めるものではありません．２つの整数 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) はカウントされません．組合せですので．

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

078月 2005

ハノイの塔に関するメモ

by admin

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

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

　　x_i ≡ x_i+1 + (-1)^n-i(b_i - b_i+1) 　 (mod 3)　　　( i は 1～n )

　x_i: 円盤 i ( i は 1 から n) が置かれた塔の番号. つまり, 0, 1, 2 のどれか. ただし, x_n+1は 0 とする.
　b_i: m の 2進数表示 b_nb_n-1 ... b₁. ただし, b_n+1は 0 とする.

＜例＞円盤が3枚ある. 5回目の移動が終了した時点での各円盤の置かれた位置を算出してみよう.
　　5の 2進数表現は 101 なので, b₃=1, b₂=0, b₁=1.
　　決まりから, x₄ = 0, b₄ = 0.
　　x₃ ≡ x₄ + (-1)^3-3( b₃-b₄) ≡0 + (1-0) ≡ 1
　　x₂ ≡ x₃ + (-1)^3-2( b₂-b₃) ≡1 - (0-1) ≡ 2
　　x₁ ≡ x₂ + (-1)^3-1( b₁-b₂) ≡2 + (1-0) ≡ 3 ≡ 0

つまり, x₁ = 0, x₂ = 2, x₃ = 1
円盤１が塔０に置かれ, 円盤２が塔２に置かれ, 円盤3が塔１に置かれている.

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

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

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

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

Category Archives: C言語・雑談

自己印刷プログラム

約数、最小公倍数

ハノイの塔に関するメモ