アルゴリズムの解説がわからない

質問

http://www.itmedia.co.jp/enterprise/articles/0908/22/news001_3.html
この記事で書かれているコードで

for (int j = Math.Max(0, K - (A + B - i)); j <= Math.Min(i, K); j++) //jは0をひっくり返す数
なぜこのような式になるのか分かりません。

解説お願いできないでしょうか

回答No.2

hirotn · ベストアンサー

いくつ0から1にすれば（ひっくり返せば）解が得られるかを、探索によって求めているプログラムですね。
0か1どちらかに着目すれば、もう一方の数字は計算できるからです。

定義
ひっくり返す：0は1に、1は0にすること。上記URLの2ページ目のカードをイメージしてください。

前提
1)プログラム上は、何枚ひっくり返すか、ということしかプログラミングされていません。A+B枚のカードの状態をシミュレートしたプログラムではありません。

2)Math.Max(a,b) a,bいずれかの大きなほうの値を返す
　Math.Min(a,b)いずれか小さなほうの値を返す

変数ｊの初期値：
int j = Math.Max(0, K - (A + B - i))
基本は0から探索を始めますが、場に出ているカードが0に偏っている場合は0を優先して多くひっくり返したいという意図があります。
A + B < Kの場合-1でreturnする処理が入っているので、iが小さければマイナスの値になるのがわかるかと思います。変数iが大きくなるとプラスすなわち0より大きくなるタイミングが生じて、その値から探索を始めるようになります。

変数ｊのループ終了条件：
現状その場に出ている0（変数i）のカードより多くの枚数あるいはルール上K枚以上のカードをひっくり返すことはできないので、このような定義になります。

nextzero = i + (K - 2 * j)について：
カードをひっくり返し終わったあとの0のカードの枚数です。これが0になるまで探索を続けているということになります。数式に引っ掛かりますが、j<Kのとき、K-j分の場に出ている0のカードは1になるため、その考慮がされているということになります。
小さな数字を代入して、計算してみれば整理できると思います。

お礼

回答して頂きありがとうございます。
何度も読み返し、実際にループ毎に変数の値を出力し
幅優先探索をつかって求めていること理解できました。
ただ、計算方法は頭の良い人でないと閃かないのかなとも感じました。
本当にありがとうございました。

回答No.1

mekuriya

分からないというだけでは赤ん坊と同じ。何がどうわからないのかを解説お願いできないでしょうか

お礼

返事が遅れまして申し訳ございません。
そうですね、質問をするにしても読み手に
伝わるように文章を書くことも重要ですよね。
今後気を付けたいと思います。