« June 2007 | Main | August 2007 »

July 03, 2007

スーパーコンピューティング・コンテストSuperConの予選問題

たまたまこちらで知ったのだが高校生がスーパーコンピューターを使って、プログラミングのアイデアを競う大会というものがあるそうで、SuperConというそうです。まあ、私は高校生ではないので参加はできないのだが、予選の問題をみて面白そうだったのでちょっとアルゴリズムを考えてみた。ただ、予選締め切りまでは問題の中身は議論しないで欲しいとのこと。まあ、今の時代ネットで情報を集めてそれをコピーアンドペーストして学校の宿題を済ませる学生も多いので仕方がないのだろう。できればネットで調べたらそれがわかってしまうような問題を考えて欲しいものだ。問題発表後にその内容について考察されたらどうしようもなことは分かるのだが。

それで、これを書いているのは締め切り前だが、公開するのは締め切り後になる。

問題なのだが、全部で3問あって、最初の2問で判定される。3問目は同点決勝用らしい。でその2問が以下である。前提の説明部分を省いているが、要するに与えれたら金額になる最小枚数のコインの組み合わせを考えるという問題。

問1.日本のコイン(K = 6,C0 = 1,C1 = 5,C2 = 10,C3 = 50,C4 = 100,C5 = 500) を使う。金額mを入力として、コインの総数ができるだけ少なくなる支払い方(各コインの枚数とコインの総数)を出力するプログラムを作れ。

問2. 10種類以下(K + 10) の任意の額面のコインがある場合を考える。金額m、コインの種類の数K、およびコインの額面C0 = 1,C1, . . . ,CK-1 を入力として、コインの総数ができるだけ少なくなる支払い方を出力するプログラムを作れ。

実はこれが書きたかっただけなのだが、問1は問題が間違っているので全問正解となる。日本のコインはここに書かれている6種類だけではないからだ。そもそもコインの定義を書いていない。
アルゴリズムを争うのだから重要ではないと考えているのだろうが、プロのプログラマとして客先と仕様を詰めるときにこのような仕様書を書いていては一人前のプロとはいえない。後でお客と仕様の不整合でもめる可能性がある。

日本にこだわるなら、最初の部分は「造幣局発行の日本で現在流通しているコイン」とくらいは書いて欲しい。しかし、単に「以下の6種類の場合」として出題すればいいと思う。これなどは先入観があるからミスを犯す典型のような気がする。

大学の先生達が主催している大会だと思うが、こうゆう基本的な部分もしっかり教育しておいて欲しいものだ。そうなれば少しはこちらも楽をできるのだが、まあ、現場経験があるプログラマで大学教育を行っている人は少ないからしかたがないのかもしれない。

これだけなら、締め切りまで待つ必要はないので、一応私の考えを述べてみる。問1について、単純な発想では、大きい金額のコインの額で順番に割っていって、あまりを次の金額のコインの額で割る。これを繰り返していけば最後は1円のコインなので割り切れて終わり。最高額が1000万円なのでこのアルゴリズムでもそれほど時間はかからないだろう。差がつくのかと思えるほどだ。

それでちょっと速くしようと考えて思いついたのが、また安易な発想で、表引きを使う方法。コインの最高額は500円なので、まず500円で割って枚数を出す。残りの組み合わせは499通りなのであらかじめその全ての組合せを計算して表にしておく、あまりの金額から表をみれば残りのコインの数の組み合わせは一発ででる。割り算は一回しか行われないのでかなり速いはずだ。

でも最初のアルゴリズムでも割り算の回数は最高6回。差がつくのかなあ。総数だけではなく種類が少ない方がよいとか条件がつくとちょっとは面白い気もする。それともなにか私が大きな勘違いをしていてこの方法では最小枚数を計算できないのだろうか。

順番に割っていくアルゴリズムでは問2でもそのまま使えるはず。出題例に大きい金額から割っていくと最小枚数が求められない例がでているので、こちらが本命なんだろか。コインの枚数がどちらも最小なら計算時間が速い方が勝ちなので、表示時間とかも意識したプログラムが必要だと思われるが、なんかそれもちょっと本題と違うような気がする。

問3はお釣りを許してコインの数を最小にする問題。例えば499円なら100円x4+50円+10円x4+5円+1円x4の14枚になるが500円を出して1円おつりをもらえば2枚と考えるわけ。

お釣りのコインの組み合わせ問題はアルゴリズムを考えさせるプログラムとしては定番で、今回との違いはお釣りの場合コイン切れがあった場合別のコインで代用してお釣りを出すアルゴリズムを考えるところ。まあこちらは定番なのでネットを探せばきっといろいろアルゴリズムが出てくるだろう。その当たりを参考にしたら減点されるというもの面白いが、そこまでオリジナリティにこだわるとも思えないなあ。

最後にこのような試み(高校生にスーパーコンピュータを使う機会を与える)は非常によいもので、教育効果も大きいと思います。ただこの手の催しで嫌だなと思うことがあるのは、参加者の選び方です。今回は予選の成績で選ぶので比較的公平でよいと思います。しかし、2~3名での参加なので近くに同好の志がいないとダメで学校のクラブなんかが有利そうです。それと本人達がプログラムを作ったかどうかの確認もないようです。プログラムの内容に関しての口頭試問程度のことはやるべきだと思います。
本当に多くの人に参加機会を与えるなら個人でも参加できるのがいいですね。まあ、個人参加者を当日組み合わせてグループにしてもあまりいい結果がでないのかもしれませんが、それはそれでよい経験になると思います。

書き終わってから時間があるんで、少し検索してみたところ順番に割っていくアルゴリズムは「欲張り法 (greedy strategy)」というものだそうでコインの組み合わせによっては最適解を求められないそうです。やっぱり問2が本命みたいです。

原稿を書くときに最初に検索を行ってから書けば内容はすこし違う結果になったと思います。しかし、この手の問題を見たときにすぐに検索とか参考書を調べるなどという行為を行うのはあまり奨励しません。まず、自分の頭で考えてみることが大切です。たとえ間違っていたり、出来の悪い結果であってもまず自分で考えることが意味があります。このあたりも学校の先生はしっかり教えて欲しいところですね。とくに最近はネットで検索するとすぐにそれらしい結果が得られるので安易に検索する習慣が付きやすいです。しかし、自分で考えてそれなりの結果を出してから調べる習慣をぜひ学生の内に身に着けておいて欲しいものです。
そうでないと創造的な仕事はできないですよ。

| | TrackBack (0)

« June 2007 | Main | August 2007 »