以下のA〜Gの位置にイカ,タコ,カブトムシ,スズメ,ヘビを1匹,ネズミを2匹の合計7匹を配置する。
どの直線上の足の数も一致するように配置するにはどうすれば良いか。
問題にはそれぞれの動物の足の数は書いていないが,イカ:10,タコ:8,カブトムシ:6,スズメ:2,ヘビ:0,ネズミ:4で問題を解くことにする。
イカは足が8本,手が2本とかひねくれたことは考えないことにする。ちなみにイカの足を8本とすると解は見つからない。
7箇所に10,8,6,2,0,4,4の数字を配置する虱潰し問題。数字割り当て問題を修正して作成する。
足の数をnleg[ ] で定義する。
int nleg[7] = { 10, 8, 6, 2, 0, 4, 4 }; // イカ,蛸(タコ),甲虫(カブトムシ),雀(スズメ),蛇(ヘビ),鼠(ネズミ),鼠(ネズミ)の足の数
7個の数字の配置なので,数字の割り当て問題の10を7に変更する。
ループの真ん中で以下のような判定文を入れる。
int n1 = nleg[a] + nleg[d]; int n2 = nleg[b] + nleg[d] + nleg[f] ; int n3 = nleg[f] + nleg[g] ; int n4 = nleg[b] + nleg[e] + nleg[g] ; int n5 = nleg[c] + nleg[e] ; if( n1 == n2 && n2 == n3 && n3 == n4 && n4 == n5) { ps( "Find A:%2d, B:%2d, C:%2d, D:%2d, E:%2d, F:%2d, G:%2d\n", nleg[a], nleg[b], nleg[c], nleg[d], nleg[e], nleg[f], nleg[g]); }
答えは4件出力されるが,左右対称分とネズミの4足があるので,実質1件。
見れば直ぐに判るので重複除去の処理は入れなかった。
解速度
即 (2004.11.27 「足」って書いてあった,恥ずかしい)