週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

プログラミングの問題作成/問題解決におけるgnuplotの活用法について解説します。

先週末にACM-ICPC OB/OGの会による、ACM-ICPC World Finalsへ向けての冬合宿がありました。 私はスタッフとして、問題をいくつか担当していました。 そのうち、"the Phantom"という問題が厄介でした。 部屋に一人の人と二枚の鏡があり、人の座標と、鏡の端点の座標が与えられたときに、人が確認できる人の像の数を数えるプログラムを作れという話です。 想定解法はシミュレーションです。像の位置を計算して、その位置にある像が鏡を通して見えるかどうかを判定します。

評価するために、まず見本となるプログラムを作ってみました。 これ自体は比較的すぐにできました。 次にこのプログラムが本当に正しいかどうか検証しようとしましたが、 これがなかなか難しいのです。 適当な入力については、おそらく正しい値を返してきます。 しかし、鏡と人の配置についてすべてを想定しているわけではないので、 これで正しいとするわけにはいきません。 多くのデータを与えればかすかな間違いも見出せるかもしれません。 しかしそれら多くの値について正しい値は必ずしもわかりません。 こういうデータ生成・検証はプログラムがやればいいのですが、 そのために必要なプログラムはまさに今作っているプログラムです。

このジレンマを解決するために、可視化をしてみました。 与えられた入力に対して、 鏡と人の位置と、それから鏡の中の人の像と鏡の像をすべて二次元上に 画像として出力するのです。 画像を人が見れば、像が正しい位置に来ていること、 それから見える像がすべて列挙されていることが確認できます。 画像を出力するには、解答プログラムであるCやJavaで画像ファイルを出力してしまう、Metapostコマンドを吐き出すなどの方法が考えられますが、今回はgnuplotを使いました。gnuplotを使う利点は次のとおりです。

  1. 解答プログラムは座標情報だけを出力し、他のプログラムで見た目を制御したほうが、結果の図形が複雑になって見た目が損なわれたときに対処しやすい。また、図がおかしかったときに座標の値だけをテキストエディタ等で確認できる。
  2. gnuplotは縮尺を適当に設定し、座標軸を勝手に引いてくれる。
  3. eps形式で出力すればベクタ画像として出力されるため、構造が複雑になったとしても拡大すれば何とかなる
もちろん、私が慣れているということも利点の一つです。

長くなったので続きはWEBで次回.次回書きました。追補編も書きました。

スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/148-f69562c8
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。