challenge ソートするコードの生成

Meta-Loopless Sortsの改題です.

n個の整数をソートするプログラムを生成するプログラム gensort を 書いて下さい.条件は以下のとおり

  1. 生成するプログラム,生成されたプログラムは同じ言語にして下さい.
  2. 生成したプログラムはファイルに書き込んでください.
  3. 生成されたプログラムでは最初に n 個の整数を読み込んで, n個の変数を初期化してください.「可能なら」変数名は,アルファベット 一文字で a,b,c ... の順で使ってください.n = 5 なら 変数は a, b, c, d, e です.
  4. 生成されたプログラムでは,if 文あるいは if 式で2つの変数を比較して いって,変数の順が確定したら,その順で変数の値を出力するようにして 下さい.
  5. 生成される側のプログラムでのアルゴリズムやデータ構造を工夫する問題では ありません :)

gensort 3 で生成した Pascal のプログラム例は以下のとおりです.

program sort(input,output);
var
a,b,c : integer;
begin
  readln(a,b,c);
  if a < b then
    if b < c then
      writeln(a,b,c)
    else if a < c then
      writeln(a,c,b)
    else
      writeln(c,a,b)
  else
    if a < c then
      writeln(b,a,c)
    else if b < c then
      writeln(b,c,a)
    else
      writeln(c,b,a)
end.

n の値を 2 〜 10 くらいまで変化させて以下の処理時間を測定してください.

1. gensort n の処理
2. 生成したプログラムの処理
   2-1. コンパイル言語の場合は,コンパイル時間と実行時間
   2-2. インタプリタ言語の場合,可能ならロード時間と実行時間を別測定,
        分解できないなら実行時間
ごさっしのとおり,出力されたプログラムは n の値で急激に大きくなります. n が大きいと gensort n で文法的に正しいプログラムは生成できてもコンパ イル や実行ができないということもありえると思います.処理系ごとの限界がわか ると面白いのではないかと思います.オリジナルの問題は Pascal のプログラム コードを生成するプログラムを書けという問題でしたが,生成する側とされる側 の言語を同じにするほうが面白いですよね.
この問題はnobsunさんからの投稿です。ご投稿ありがとうございました。助かります。

Posted feedbacks

Number of comments:24 Nested Flatten
  1. 4 Common Lisp Haskell
  2. 2 Scheme Prolog
  3. 1 Other Ruby C C# D Java Scala Perl Python Smalltalk

Index

Feed

Other

Link

Pathtraq

loading...