-
- いいね！0
kinaba
@kinaba
にっきかいた。みんな二分探索どう書くの。http://t.co/qg7wvIbu ライブラリ化する際に引数と返値と関数名と引数名をどうするのという話としてもよいです。
2012-07-03 23:16:51
J. Kuroda
@Isa_rentacs
間違えやすいのは確かにその通りで、いつも線分図書いて、これが求めたい値、ここまでtrueでここからfalse、だからmedがtrueなら動かすのは…とか考えて書いてる
2012-07-03 23:24:13
J. Kuroda
@Isa_rentacs
「最大値の最小化」ってよく言われてるけど自分が問題によってはその形にうまく落とせないので、ある区間にただ1つ閾値があって、それを境にtrue/falseが変わる->にぶたん だと思ってます。
2012-07-03 23:26:21
しおしおた
@shioshiota
にぶたん、閉区間で差が２より小さくなるまでまわしてる。 得られた二つの候補について適切か毎回確認してから、より適切なものを返すようにしてる（無駄）
2012-07-03 23:25:28
tanzaku
@_tanzaku_
二部探は解の区間だけ意識してwhile(L <= R) { ... } return L - 1; みたいにやってるなー。
2012-07-03 23:26:57
hogeover30
@hogeover30
整数にぶたん昨日のSRMでは while(L<=R) { M=(L+R)/2; if (hoge) L=M+1; else R=M-1; } return L; で通った
2012-07-03 23:29:03
はまづ
@hama_du
@shioshiota 回数はだいたい100か200って書いちゃいますね。整数型の場合はそれで十分ですが、実数でにぶたんするときは回数のミスは怖いですね。
2012-07-03 23:31:12
白茶利休
@shiracha
loop invariantは普通、真偽の２値しかとらないが（なぜなら述語なので。）、あるループが開始してから、終了するまで、常に同じ値をとる関数を取って、それをloop invariantと看做した上で、ループ初期値に対する同値類を考えたらきっと楽しいんじゃないかなー。など思う
2012-07-03 23:36:55