読者です 読者をやめる 読者になる 読者になる

せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【アルゴリズム】複合型n進数

 
■topic summary
study about how to hash "number of cases".

(2/2)やわらか頭でアルゴリズムを10倍生かす - 第2回 川渡り問題:ITpro
ここに載ってる、場合の数をハッシュ化する方法が目からウロコでした。

 

問題

3人の宣教師(うち2人は子供)と3人の先住民(同)が川岸にいます。川には2人まで乗れるボートが一艘(そう)あります。ボートを漕げるのは、大人だけで、子供はボートを漕ぐことが出来ません。また、どちらかの岸で、先住民の数が宣教師の数より多くなると、先住民は反旗を翻して宣教師に襲いかかってしまいます。全員が無事に対岸に渡るには、どうしたら良いでしょうか?

川渡り問題は以前から散々解いているところ

 
ポイントはここ↓

この問題において、存在し得る状態の数はいくつあるのでしょうか?・・・状態の総数が「2×2×3×3×2=72」通りであることがわかります。各状態に対して、0~71の番号をどのように対応付けましょうか。

ここで、2進数と3進数を複合した仕組みによって、0~71にそれぞれの場合を割り当てていくのです!
すごい!

各桁の基数を「とりうる場合の数」にする。
たとえば、
「ボートの状態」は「右」か「左」の2通りだから2進数。
「子供の状態」は「右1」「右2」「右0」の3通りあるから3進数。


解答では このhash関数は1箇所(ゴール判定)にしか使われておらず、
dehashして状態を判定する(食われるパターンだ、とか)訳ではなかったので
あまり有効活用している感じはしない。。

でもこの考え方は役に立ちそう!すごい!

※複合型n進数、というのは造語です。。ごめんね。