ページ 1 / 1
火曜までの宿題ですが
Posted: 2007年6月23日(土) 23:58
by まろん
どうしたら良いかわからず、焦っています。
構造体等を使うのですがどうしたら良いでしょうか。
ちなみに構造体等初めてです
10リットル、8リットル、3リットルの容器があり、10リットルの容器に水がいっぱい入っている。この3つの容器を用い、3リットルの容器に1リットルの水を取り出す最小の手順を答えよ。ただし、水を移す時は、移す側が空になるか、移す側がいっぱいになってときとする。
幅優先探索と言うのを用いるそうです。
急ですがよろしくお願いします
Re:火曜までの宿題ですが
Posted: 2007年6月24日(日) 00:32
by box
幅優先探索の考え方は理解していますか?
また、このアルゴリズムと相性のいいデータ構造は
キュー(FIFO:First In First Out)です。
キューについてはどのくらいご存じですか?
早速、返答ありがとうございます
Posted: 2007年6月24日(日) 00:42
by まろん
概念が、少しわかる程度で、ほとんど理解していません。
キューはどういう構造なのかがわかる程度です
Re:早速、返答ありがとうございます
Posted: 2007年6月24日(日) 08:26
by box
Xリットルの容器に水がYリットル入っている状態をX(Y)と表わすことにします。
すると、この問題の初期状態は「10(10),8(0),3(0)」と表わせます。
また、終了状態は、とにかく3リットルの容器に1リットル入っていればよいので、
「10(1),8(8),(3(1)」~「10(8),8(1),3(1)」の8通りあります。
キューは、先の回答で書きましたとおり、「先入れ先出し」方式の構造を持っています。
ある程度大きめの要素を持つ(構造体の)配列で実現することができます。
このとき、ある時点で配列のどこからどこまでを有効な要素として使っているかを管理する必要があります。
幅優先探索の考え方の概要は、以下のとおりです。
・初期状態(ゼロ手目)をキューに格納する。
・キューからn手目の状態を1つ取り出す。
・取り出した状態からたどれる状態(n+1手目)をすべて求める。
・求めた状態が終了状態のいずれかに属していれば、初期状態から終了状態までの手順を表示(※)して、終了する。
・求めた状態が終了状態に属していなければ、キューに格納する。
・終了状態に至らないまま、新しい状態をキューに格納することができなければ、「答えが見つからなかった」として、終了する。
・無限ループに陥ることを防ぐため、前に登場した状態が再登場しないようにする。
つまり、初期状態から始めて、
・1手目に現われる状態をすべてキューで管理する。
・1手目の状態からたどれるすべての状態を2手目としてキューで管理する。
・2手目の状態からたどれるすべての状態を3手目としてキューで管理する。
ということを繰り返します。こういう風にすれば、終了状態が見つかったときの
手数が最小であることが保証できます。
また、上の(※)のところで書いた手順表示は、問題文に「最小の手順を答えよ」と
ありましたので、必須だと思います。
手順を表示するためには、キューを表わす構造体のメンバーに「直前の状態」というものを
加えておく必要があります。
このあたりまではよろしいですか?
PCの調子が悪くて
Posted: 2007年6月25日(月) 06:12
by まろん
返信、遅くなりました。
上記の解説で何をしたら良いか、イメージはつきました。