締切済み

ある夫婦３組が２人乗りのボートで対岸に渡るという縦型探索アルゴリズムを

2010/07/06 14:46

ある夫婦３組が２人乗りのボートで対岸に渡るという縦型探索アルゴリズムをC言語でプログラミングしたいのですが、どのようなプログラミングをすればよいのでしょうか？ルールは、１、夫婦の妻は一人では対岸に渡ることができない。（一人で戻るのは可能）２、妻は、自分の旦那以外とは一緒に渡れないです。縦型探索なので、OpenListやClosedListを使うのですが、わかりません。回答でもヒントでもよいのでよろしくお願いします。またなにか、わからないことやくわしいことが聞きたいなどもどんどんかきこんでください。お願いします。

kei114477
お礼率25% (7/27)

C・C++・C#
回答数3
ありがとう数2

みんなの回答 （3）
専門家の回答

みんなの回答

emu0202
ベストアンサー率35% (5/14)

2010/07/07 12:41 回答No.3

Ｃ言語で実装するという話だと、情報系の大学生のレベルを超えていると思います。Ｃ言語はあきらめて、Promelaという言語、SPIN model checkerというツールを用いて解くことをオススメします。

nak777r
ベストアンサー率36% (49/136)

2010/07/07 12:17 回答No.2

A=夫 a=妻 B=夫 b=妻 C=夫 c=妻移動可能なパターン 1=A 2=Aa 3=AB 4=AC 5=B 6=Bb 7=BC 8=C 9=Cc こっち　あっち AaBbCc　AaBbCc　回　可能パターン　 111111　000000　01　123456789　回が奇数ならこっちからあっちに行くターン回が偶数ならあっちからこっちに行くターン可能パターンの内数字の小さい方からやっていく事にする AaBbCc　AaBbCc　回　可能パターン　試行パターン 111111　000000　01　123456789　1 011111　100000　02　-00000000　- 行きと同じ状態で帰る事になる可能パターンの項目は '-'で記載すると、２回目で手詰まりとなる試行パターン 1が手詰まりだったので１個戻し試行パターン2でやってみる AaBbCc　AaBbCc　回　可能パターン　試行パターン 111111　000000　01　123456789　2 001111　110000　02　1-0000000　1 行きと同じとなる試行パターン2 を '-' とすると、他に可能なパターンは 1のみ AaBbCc　AaBbCc　回　可能パターン　試行パターン 111111　000000　01　123456789　2 001111　110000　02　1-0000000　1 101111　010000　03　-03456789　3 前回と同じになる試行パターン1 を '-' また a は居ないため可能パターン2は成立しないため '0' で記載した、すると次は試行パターン 3（AB)となる AaBbCc　AaBbCc　回　可能パターン　試行パターン 111111　000000　01　123456789　2 001111　110000　02　1-0000000　1 101111　010000　03　-03456789　3 000111　111000　04　12-000000　1 同様に続けていくと AaBbCc　AaBbCc　回　可能パターン　試行パターン 111111　000000　01　123456789　2 001111　110000　02　1-0000000　1 101111　010000　03　-03456789　3 000111　111000　04　12-000000　1 100111　011000　05　-00400089　4 000101　111010　06　123-50780　1 100101　011010　07　-00000000　- ７回目で手詰まりになったので、１つ前の試行パターンを次に可能な2にする AaBbCc　AaBbCc　回　可能パターン　試行パターン 111111　000000　01　123456789　2 001111　110000　02　1-0000000　1 101111　010000　03　-03456789　3 000111　111000　04　12-000000　1 100111　011000　05　-00400089　4 000101　111010　06　123-50780　2 110101　001010　07　1-0000000　1 010101　101010　06　-03450780　3 　：　　　：　　：　　：イメージとしてはこんな感じになっていくんじゃないかな

tatsu99
ベストアンサー率52% (391/751)

2010/07/06 18:12 回答No.1

プログラムは別として、徳川さん夫婦織田さん夫婦豊臣さん夫婦がいたとして、１．徳川さん夫婦が二人で渡り、旦那が戻る。２．織田さん夫婦が二人で渡り、旦那が戻る。３．豊臣さん夫婦が二人で渡り、旦那が戻る。４．徳川さんと織田さんの旦那同士でわたり、徳川さんが戻る。５．徳川さんと豊臣さんの旦那同士でわたり、おしまい。というのはＯＫですか。