質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

2回答

1290閲覧

「もっとプログラマ脳を鍛える数学パズル」の Q39 がわかりません

pyxis

総合スコア16

Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

2クリップ

投稿2020/02/27 12:22

「もっとプログラマ脳を鍛える数学パズル」という本に載っている
「Q39 隣り合うと消えちゃうんです」の解答コードが理解できません。
どなたかコードのアルゴリズムを解説していただけないでしょうか?

問題は以下です。
イメージ説明
イメージ説明
解答コードは以下です

Ruby

1N = 11 2 3# unused:未使用の色の数 4# onetime : 一度だけ使った色 5# neighbor : 隣で使用した色 6@memo = {[0, 0, 0] => 1} 7def pair(unused, onetime, neighbor) 8 if @memo[[unused, onetime, neighbor]] 9 # すでに探索済みの場合、探索結果を再利用 10 return @memo[[unused, onetime, neighbor]] 11 end 12 cnt = 0 13 if unused > 0 # 未使用の色が残っている場合 14 cnt += pair(unused - 1, onetime + neighbor, 1) 15 end 16 if onetime > 0 # 一度だけ使った色が残っている場合 17 cnt += onetime * pair(unused, onetime - 1 + neighbor, 0) 18 end 19 @memo[[unused, onetime, neighbor]] = cnt 20end 21 22puts pair(N, 0, 0)

0と1のみをとる引数 neighbor は 隣で使用した色 と書いてありますがどういうことでしょうか?
また onetime + neighbor では何が行われているのでしょうか?

宜しくお願いします。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

左から塗っていくというイメージで

unuseは一度も塗られていない色の数。
onetimeは塗られているマスのうち一番右のマス以外のマスに塗られている一度だけ塗られている色の数。
neighborは塗られているマスのうち一番右のマスに塗られている一度だけ塗られている色の数と考えればいいでしょう。
※onetimeは一番右に塗られている一度だけ塗られた色は含まない、一番右のマスは一つしかないのでneighborは0か1しかとらない

ということなんでしょう。

onetime + neighborは新たに右側に色が塗られることで、今までneighborの塗られていたマスが右端ではなくなるのでonetimeに含まれるようになるということです。

一応補足ですが、一度使った色でもonetimeとneighborを分けて数えるのは、neighborに使った色を右端に塗ると同じ色を並べて塗れないという制約に違反するからです。

投稿2020/02/27 14:13

yudedako67

総合スコア2047

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

pyxis

2020/02/28 04:12 編集

ありがとうございました。コードが何をやっているのかは理解できました。 自分なりにまとめると以下のようになりました。 # unused:未使用の色の数 # onetime : 右端を除いた一度だけ使った色の数 # neighbor : 右端の一度だけ使った色の数(右端1つなので0か1のみ) ①if unused > 0 未使用の色を右端に使用する場合 <引数の説明> unused - 1 : 未使用が1つ使用されるのでその分を引く onetime + neighbor : 1つ前の右端が左に加わるのでその分を足す 1 : 右端は一度使用済みとなる為、その分の1 ②if onetime > 0 一度だけ使用した色を右端に使用する場合 <引数の説明> unused : 一度使用済みを使うので未使用の数は変化しない onetime - 1 + neighbor : 右端に使用した分が1減り、1つ前の右端が左に加わるのでその分を足す 0 : 右端は同色を2回使用したことになり、一度だけ使用済みではないので0 しかし、根本的な問題としてなぜ右から2番目と右端を比較することなしに、 右端を分けると同色が並ぶことをなぜ避けられるのでしょうか? 自分が考える右端を分けてうまくいく理由は ①N = 1 の時引数は [1, 0, 0] [0, 0, 1] と変化し、[0, 0, 0]にならず排除され、AAを避けられる。 これにより、N = 3 の時、色がABABになった時も引数が[1, 0, 0]となりABABCCのようなパターンが排除される。 (A,Bは色を表す) ②N = n の時、 初手は A [n - 1, 0, 1] 、2手目は AB [n - 2, 1, 1] となり必ず左端2マスが違う色で埋まって、 AA[n - 1, 0, 0] にはならない。 その後 N = 2 で [0, 1, 0] などABBとABAなど2通り考えられる場合はABAだと解釈する。 上記二点ですが、これは偶然そうなっているのでしょうか? それとも上記のような例を出すまでもなく右端を分ける=右端が同色にならない、 は必然なのでしょうか?
swordone

2020/02/28 04:33

前半で説明している動きがわかるのなら、自然と成り立つはずです。 右端の右に新規の色を使うなら当然右端と被らないし、一度使った色を使う場合もonetimeに右端の色はカウントされていませんから、被りようがありません。
pyxis

2020/02/28 04:59

「右端の右に新規の色を使うなら当然右端と被らない」はわかるのですが、 「一度使った色を使う場合もonetimeに右端の色はカウントされない」ことと「色が被らない」ことが 同値だとなぜいえるのでしょうか? 例として N = 2 の場合 ABBと色が被っている場合も [0, 1, 0] と表現できるので (ABAも [0, 1, 0] と表現できる) 無条件に同値(被りようがない)とは言えないと思うのですが。
swordone

2020/02/28 05:13 編集

ABまで塗られた段階で、[0,1,1]です。 onetimeの1はA、neighborの1はBです。 このBの右隣を塗ろうとする段階で、onetimeのAを塗る以外の選択肢がありません。 つまり、ABBはそもそも「起こり得ません」。
pyxis

2020/02/28 06:01

それは理解できるのですが 「onetimeの1はA、neighborの1はBです。」と言えるのは 「ABまで塗られた段階で、[0,1,1]です。」 のように実際に引数の動きを追ったからであり、 引数の動きを全く見ずに 「一度使った色を使う場合もonetimeに右端の色はカウントされない」をいきなり「色が被らない」 とするのはかなりの論理の飛躍があると思うのですが。 swordoneさんは 「ABまで塗られた段階で、[0,1,1]です。 onetimeの1はA、neighborの1はBです。 このBの右隣を塗ろうとする段階で、onetimeのAを塗る以外の選択肢がありません。」 のような具体例を考慮した上で 「一度使った色を使う場合もonetimeに右端の色はカウントされない」=「色が被らない」 と言われているのか、 それともそういうことは考えずとも 「一度使った色を使う場合もonetimeに右端の色はカウントされない」=「色が被らない」 といきなり確信されたのでしょうか? もしそのような場合、仮にこれが証明問題だとすれば論理の飛躍となり 説明不足にはならないでしょうか?
yudedako67

2020/02/28 10:52

別の回答になりますが、考え方が逆です。 もともとpairは同じ色を3回以上使ったり同じ色を隣り合うように使ったりする塗り方を含まない塗り方を返すようになっています。なので、「ABBと色が被っている場合も [0, 1, 0] と表現できる」とはなりません。 そしてABBの場合が[0, 1, 0]の場合に含まれるかどうかを証明するときに考えるべきなのは、[0, 1, 0]の次のpairの呼び出し[0, 0, 0]が正しく1(つまりABABのパターンだけ)を返したときに、[0, 1, 0]の結果にABBが含まれるかどうかということです。
pyxis

2020/02/28 11:45

>もともとpairは同じ色を3回以上使ったり同じ色を隣り合うように使ったりする塗り方を含まない塗り方を返すようになっています。 このコードにおいて「同じ色を3回以上を使わない」は自明で良いと思うのですが、 「同じ色を隣り合うように使わない」ことも自明だということでしょうか? もしそうならそれは自分が書いた ①N = 1 の時引数は [1, 0, 0] [0, 0, 1] と変化し、[0, 0, 0]にならず排除され、AAを避けられる。 これにより、N = 3 の時、色がABABになった時も引数が[1, 0, 0]となりABABCCのようなパターンが排除される。 (A,Bは色を表す) ②N = n の時、 初手は A [n - 1, 0, 1] 、2手目は AB [n - 2, 1, 1] となり必ず左端2マスが違う色で埋まって、 AA[n - 1, 0, 0] にはならない。 などが書くまでもなく当然のことなので自明なのか、 それとも上記のような場合分けなど必要としない別の論理がありそこから自明なのでしょうか?
yudedako67

2020/02/28 13:37

自明とかではなく、そうなってるという話です。 なんでそういう話が大事かというと、pair関数内でpair関数を呼び出してるからです。 pair関数が何をやってるのかを知らずにpair関数がどうしてちゃんと動くのかを理解することはできません。 その場合分けするような考え方も、左端以外でも同じ色を連続して塗る可能性があることやpair関数内でNが一度も参照されてないことを考えるとこのコードの理解には遠回りでしょう。 最終的に知りたいのはpair(N, 0, 0)が求めたい結果になることだけですが、その証明はpair関数が「同じ色を3回以上使ったり同じ色を隣り合うように使ったりする塗り方を含まない ”残りのマス" の塗り方を返す」関数であると証明するのが近道です。
pyxis

2020/02/28 13:57

わかりました。 非常に丁寧に解説していただきありがとうございました。
guest

0

onetime: 左隣を除いた 1度のみ使った色数
neighbor: 左隣の色が未使用色だったなら1、既存色だったなら0
onetime + neighbor: 左隣を含めた 1度のみ使った色数

投稿2020/02/27 14:12

asm

総合スコア15147

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

pyxis

2020/02/28 13:57

ありがとうございました
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問