データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net

**デフォルトの名無しさん転載ダメ©2ch.net** · 2016/06/19(日) 14:47:29.63

このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。

　　　　　　　　　　　　　　　　　　京都大学霊長類研究所

データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
http://echo.2ch.net/test/read.cgi/tech/1362301811/

【関連スレ】
3Dアルゴリズム全般
http://toro.2ch.net/test/read.cgi/tech/1164171086/
＜集大成＞アルゴリズム大辞典
http://toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
http://toro.2ch.net/test/read.cgi/tech/1217773415/

アルゴリズムとデータ構造 - Kaneko Lab.
ttp://www.kkaneko.com/adp/algo/index.html
アルゴリズムとデータ構造 - ソースコード探険隊
ttp://www.codereading.com/algo_and_ds/
各種アルゴリズムの C++ による実装 - Spaghetti Source
ttp://www.prefield.com/algorithm/
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
ttp://vipprog.net/wiki/algo_and_data_const.html

**デフォルトの名無しさん** · 2016/12/21(水) 20:34:58.70

>>199

各 i（k ≦ i ≦ l）に対して、0以上の整数 b_i を以下で定義する：

**デフォルトの名無しさん** · 2016/12/21(水) 20:39:27.31

不完全な問題出しておいて>>186はないよね

**デフォルトの名無しさん** · 2016/12/21(水) 20:41:22.47

>>202

不完全なところはありません。
よく問題文を読んでください。

**デフォルトの名無しさん** · 2016/12/21(水) 20:42:06.97

>>200
力学･解析力学part2
http://rio2016.2ch.net/test/read.cgi/sci/1284697460/479

**デフォルトの名無しさん** · 2016/12/21(水) 20:43:41.56

マルチ小僧ｗ

**デフォルトの名無しさん** · 2016/12/21(水) 20:44:49.22

>>203
mがkからlの間なんて一言もないんだから不完全

**デフォルトの名無しさん** · 2016/12/21(水) 20:47:08.96

>>206

>>183
各 i（k ≦ i ≦ l）に対して、0以上の整数 b_i を以下で定義する

**デフォルトの名無しさん** · 2016/12/21(水) 20:52:23.64

そうだとして、わざと誤読を誘おうとしている悪問だね
でO(log k)のアルゴリズム思いついたから俺は降りるね

**デフォルトの名無しさん** · 2016/12/21(水) 20:53:06.55

O(log l)だった

**デフォルトの名無しさん** · 2016/12/21(水) 20:55:14.58

>>183

の解答は以下です。

http://imgur.com/rAnp3Ga.jpg

赤線を引いたところは「odd」が正しいですね。

**デフォルトの名無しさん** · 2016/12/21(水) 21:27:34.73

実は、この問題には続きがあります。

m, n を m < n を満たす正の整数とします。

このとき、

1/m + 1/(m+1) + … + 1/n

は整数にはならないことを証明せよ。

**デフォルトの名無しさん** · 2016/12/21(水) 21:29:28.61

ちょっとアルゴリズム的な問題からは離れますが。

**デフォルトの名無しさん** · 2016/12/21(水) 21:31:37.14

提出日はいつですか？

**デフォルトの名無しさん** · 2016/12/21(水) 22:14:54.89

またバカな質問者が暴れてるのか

**デフォルトの名無しさん** · 2016/12/21(水) 23:45:05.79

qiitaでやれ

**デフォルトの名無しさん** · 2016/12/23(金) 00:59:54.04

>>183
そのような m が 2 個ある
m1 < m2
とする

m1 の下位ビット 0 ～ n-1 までは 0で、ビット n が 1 とする
m2 も同様になる（すなわち b_m1 = b_m2 = n ）

m3 = m1 + ( 2 の n 乗 )

と定義すると
m1 < m3 <= m2 であるが、b_m3 > n となって矛盾

**デフォルトの名無しさん** · 2016/12/23(金) 01:37:11.09

>>211
1/m + 1/(m+1) + … + 1/n = P = 整数
だとする

L = ∏ r ; r = m…n
を両辺に掛ける

L/m + L/(m+1) + … + L/n = LP

すべての項は整数。

b_LP ( LP の連続する下位ビット 0 の個数 ) >= Σ b_r ; r = m…n

m <= x <= n は b_x を最大にするもの
左辺の L/x だけ連続する下位ビット 0 の個数は他より少ない
よって b_左辺 = b_x で矛盾

**デフォルトの名無しさん** · 2017/01/01(日) 00:15:18.27

ダイクストラのアルゴリズムの正しさの証明が載っている本で
一番分かりやすい本を教えてください。

**デフォルトの名無しさん** · 2017/01/02(月) 07:40:19.35

『アルゴリズムイントロダクション』について質問です。

この本での実数の集合には、 ∞, -∞ が含まれるのでしょうか？

最短路問題の説明で、

実数 a が a≠∞のとき、 a + -∞ = -∞
実数 a が a≠-∞のとき、 a + ∞ = ∞

という記述があるために質問します。

**デフォルトの名無しさん** · 2017/01/02(月) 08:09:15.65

実数 a が a≠∞のとき、 a + -∞ = -∞
実数 a が a≠-∞のとき、 a + ∞ = ∞

-∞ + -∞ = -∞
∞ + ∞ = ∞

という等式を含めたいからこのような書き方になったのでしょうか？

**デフォルトの名無しさん** · 2017/01/02(月) 09:29:22.45

それは実無限派の書き方だが，世の趨勢は可能無限
ほどほどに相手をするだけでいいよ

**デフォルトの名無しさん** · 2017/01/02(月) 11:22:57.42

>>221

ということは、『アルゴリズムイントロダクション』での実数の集合の定義には、
∞、-∞ が含まれるというk十ですね。

**デフォルトの名無しさん** · 2017/01/02(月) 11:23:39.72

頂点の数が n のグラフで、任意の頂点間に辺が存在するようなものを考える。

ある任意の頂点から別の任意の頂点への閉路をふくまない経路の数を求めよ。

**デフォルトの名無しさん** · 2017/01/02(月) 11:26:14.49

頂点の数が n（≧2）のグラフで、任意の頂点間に辺が存在するようなものを考える。

ある任意の頂点から別の任意の頂点への閉路をふくまない経路の数を a_n とする。

このとき、

(n-1)! ≧ a_n ≧ (n-2)!

が成り立つことを示せ。

**デフォルトの名無しさん** · 2017/01/02(月) 12:08:43.26

宿題は宿題スレへ

**デフォルトの名無しさん** · 2017/01/02(月) 12:09:56.00

宿題は宿題スレへ

**デフォルトの名無しさん** · 2017/01/02(月) 12:22:39.27

宿題ではないのです。

ある本に、頂点 s から t への最短経路を計算する方法として、
s からｔへのあらゆる経路の長さを考えて、最小の経路を選ぶとすると、
経路の数が O(n!) だから現実的ではない

という話が書いてあります。

ところが、計算してみると、 O(n!) は荒い評価であって、 O((n-1)!) とできますね。

**デフォルトの名無しさん** · 2017/01/02(月) 12:24:22.04

もっといい評価はありますでしょうか？

**デフォルトの名無しさん** · 2017/01/02(月) 12:28:36.72

判ってるなら効くな

**デフォルトの名無しさん** · 2017/01/02(月) 14:08:15.59

ダイクストラ法の正しさの証明で分かりやすい証明を思いつきました。

発表しましょうか？

**デフォルトの名無しさん** · 2017/01/02(月) 14:21:37.12

どうぞどうぞ

**デフォルトの名無しさん** · 2017/01/02(月) 14:27:23.53

>>227
オーダーについてあんま良くわかってないんだろうけどO((n-1)!) なんて書き方はないよ
もし書いたとして、それはO(n!)と同じもの

**デフォルトの名無しさん** · 2017/01/02(月) 17:55:38.72

>>222
実無限はいろいろ破綻するから可能無限にしておいたほうがいいよ
実数の定義に∞, -∞は入らない
というか，そもそも -∞ というのがおかしい存在

つリーマン球面

**デフォルトの名無しさん** · 2017/01/02(月) 19:04:30.86

なんか正しさの証明を書いてみると簡単なことなのに長くなりますね。
もし、間違っていたら指摘してください。

http://imgur.com/PDx2vmZ.jpg
http://imgur.com/DbMiSz5.jpg

ダイクストラのアルゴリズムは↑のものとします。

**デフォルトの名無しさん** · 2017/01/02(月) 19:05:18.10

節点 s から、ある節点 i への最短経路が存在するとき、その長さを td(i) で表わすことにする。
i への経路、したがって最短経路が存在しないときには、 td(i) = ∞ とする。

ステップ(1)で選ばれる節点 v ∈ V - S に対して、 d(v) = td(v) が成り立つことを数学的帰納法により、以下で証明する。

最初にステップ(1)が実行されるときを考える。
明らかに、 d(s) = td(s) = 0 が成り立つ。

k ≧ 1 とする。
第 1 回目から第 k 回目にステップ(1)が実行されるときに、いつもステップ(1)で選ばれる節点 v ∈ V - S に対して、
d(v) = td(v) が成り立つと仮定する。

**デフォルトの名無しさん** · 2017/01/02(月) 19:05:35.40

第 (k+1) 回目にステップ(1)が実行されるときを考える。
このとき、明らかに #S = k であり、 ∀i ∈ S に対して、 d(i) = td(i) が成り立つ。
第 (k+1) 回目にステップ(1)が実行されるときに選ばれる節点を v ∈ V - S とする。
d(v) = ∞ である場合と d(v) ≠ ∞ である場合で場合分けして考える。

(1) d(v) = ∞ である場合。
td(v) ≠ d(v) = ∞ と仮定して矛盾を導く。
td(v) ≠ ∞ であるから、節点 s から節点 v への経路 s = v_0 → v_1 → … → v_(l-1) → v_l = v が存在する。
明らかに、 td(v_0), td(v_1), …, td(v_(l-1)), td(v_l) ≠ ∞ である。
v_0 ∈ S, v_l ∈ V - S であるから、 v_i ∈ S, v_(i+1) ∈ V - S となるような i が存在する。
∀j ∈ V - S に対して、 d(j) = ∞ であるから、 d(v_(i+1)) = ∞ である。また、 v_i ∈ S であるから、
d(v_i) = td(v_i) ≠ ∞ が成り立つ。
v_i がステップ(2)で S に追加されたときのことを考えれば分かるように、 (v_i, v_(i+1)) ∈ E かつ v_(i+1) ∈ V - S であるから、
d(v_(i+1)) = ∞ ということはない。これは矛盾である。
よって、 d(v) = td(v) = ∞ が成り立つ。

**デフォルトの名無しさん** · 2017/01/02(月) 19:05:51.66

(2) d(v) ≠ ∞ である場合。
td(v) ≠ d(v) と仮定して矛盾を導く。
ステップ(2)を考えれば明らかなように、 d(v) ≠ ∞ であるから、節点 s から節点 v への
最短経路 s = v_0 → v_1 → … → v_(l-1) → v_l = v が存在する。
よって、 td(v) ≠ ∞ である。
仮定により、 td(v) ≠ d(v) であるから、 td(v) < d(v) が成り立つ。
v_0 ∈ S, v_l ∈ V - S であるから、 v_i ∈ S, v_(i+1) ∈ V - S となるような i が存在する。
td(v_(i+1)) < d(v_(i+1)) である。なぜなら、もし、そうでないと仮定すると、 d(v_(i+1)) = td(v_(i+1)) であるが、
td(v_(i+1)) ≦ td(v) < d(v) であるから、 d(v_(i+1)) < d(v) となってしまい、ステップ(1)での v の
選ばれ方に矛盾するからである。
v_i ∈ S であるから、 d(v_i) = td(v_i) である。
v_i がステップ(2)で S に追加されたときのことを考えれば分かるように、 (v_i, v_(i+1)) ∈ E かつ v_(i+1) ∈ V - S であるから、
d(v_i) + a_(v_i v_(i+1)) ≧ d(v_(i+1)) である。
一方、明らかに、 td(v_i) + a_(v_i v_(i+1)) = td(v_(i+1)) であるから、
td(v_(i+1)) = td(v_i) + a_(v_i v_(i+1)) = d(v_i) + a_(v_i v_(i+1)) ≧ d(v_(i+1)) となるが、これは矛盾である。
よって、 td(v) = d(v) が成り立つ。

**デフォルトの名無しさん** · 2017/01/02(月) 19:06:08.41

以上より、第 (k+1) 回目にステップ(1)が実行されるときにも、ステップ(1)で選ばれる節点 v ∈ V - S に対して、
d(v) = td(v) が成り立つ。

S に追加される節点はすべて、ステップ(1)で選ばれた節点 v ∈ V - S であり、一度 S に追加された節点 v の d(v) はそれ以後、
変更されないから、ステップ(1)でアルゴリズムが終了したとき、 ∀i ∈ S = V に対して、 d(i) = td(i) が成り立つ。

**デフォルトの名無しさん** · 2017/01/02(月) 19:26:36.14

>>232

ある本では、

正定数 c, n0 が存在して、 n ≧ n0 のとき、 T(n) ≦ c*f(n) であるなら、
T(n) は O(f(n)) であるという

と定義されています。

T(n) = n!
f(n) = n!
g(n) = (n-1)!

とします。

このとき、明らかに、
T(n) は O(f(n)) ですが、
T(n) は O(g(n)) ではありません。

**デフォルトの名無しさん** · 2017/01/02(月) 19:29:54.44

したがって、

O(f(n)) と O(g(n)) は異なります。

**デフォルトの名無しさん** · 2017/01/03(火) 08:33:06.09

この狂人ヤバいなｗ

**デフォルトの名無しさん** · 2017/01/03(火) 08:50:16.82

>>224
>>227

閉路を含まないから、各点を高々1回しか通らない。（端点も）

直通の経路が　１
途中でｋ個所を通過する経路が
　(n-2)(n-3)･････(n-k-1) = (n-2)!/(n-k-2)!
だけある。ただし、k≦n-2
よって
a_n = (n-2)!｛1 + 1/1! + 1/2! + … + 1/(n-2)!},

n ≧ 2 のとき、

(n-2)! ≦ (n-2)! * (1 + 1/1! + 1/2! + … + 1/(n-2)!) ≦ e * (n-2)!

したがって、

a_n = Θ((n-2)!)

である。

**デフォルトの名無しさん** · 2017/01/03(火) 08:52:54.04

>>234-238

のダイクストラのアルゴリズムの正しさの証明に間違いはないという
ことでOKですか？

**デフォルトの名無しさん** · 2017/01/03(火) 11:39:58.60

Erik DemaineはMITの歴史上最年少で教授になったという天才だそうですね。

今、そのErik Demaineの2005年のダイクストラのアルゴリズムについての講義を見ています。

見終わったら、講義の要約について書きます。

**デフォルトの名無しさん** · 2017/01/03(火) 13:47:58.01

ダイクストラのアルゴリズム：

01: d[s] ← 0
02: for each v ∈ V - {s}:
03: ■■d[v] ← ∞
04: S ← Φ
05: Q ← V
06: while Q ≠ Φ:
07: ■■u ← ExtractMin(Q)
08: S ← S ∪ {u}
09: for each v ∈ Adj[u]:
10: ■■if d[v] > d[u] + w(u, v):
11: ■■■■d[v] ← d[u] + w(u, v)

**デフォルトの名無しさん** · 2017/01/03(火) 13:49:29.21

Correctness I:

d[v] の初期化の直後、およびLine 11の直後において、
すべての v ∈ V に対して、 d[v] ≧ δ(s, v) が
成り立つ。

証明：
d[v] の初期化の直後には、
d[s] = 0 かつすべての v ∈ S - {v} に対して、d[v] = ∞
が成り立っている。
δ(s, s) = 0 かつすべての v ∈ S に対して、 δ(s, v) ≦ ∞
であるから、d[v] の初期化の直後には、
すべての v ∈ V に対して、 d[v] ≧ δ(s, v) が確かに
成り立っている。

**デフォルトの名無しさん** · 2017/01/03(火) 13:49:56.08

Line 11の直後において、すべての v ∈ V に対して、
d[v] ≧ δ(s, v) が成り立つことを背理法により示す。

Line 11の直後において、 d[v] ≧ δ(s, v) が
成り立たないような v ∈ V が存在するとする。
v をそのような点の中で、最初の点とする。

d[v] < δ(s, v)

d[v] < δ(s, v) ≦ ∞ であるから、
ダイクストラのアルゴリズムのLine 11は少なくとも1回は
実行されているはずである。そのような最後の実行を

d[v] ← d[u] + w(u, v)

とすると、

d[u] + w(u, v) = d[v] < δ(s, v)

が成り立つ。

一方、 d[u] ≧ δ(s, u) であるから、

d[u] + w(u, v) ≧ δ(s, u) + w(u, v)
≧ δ(s, u) + δ(u, v)
≧ δ(s, v)

が成り立つが、これは矛盾である。

**デフォルトの名無しさん** · 2017/01/03(火) 13:51:21.27

Correctness Lemma:
s → … → u → v を s から v への一つの最短路とする。
d[u] = δ(s, u) であるとする。

このとき、Line10-11を実行すると、

d[v] = δ(s, v)

が成り立つ。

証明：
δ(s, v) = w(s → … → u) + w(u, v)
= δ(s, u) + w(u, v)
Correctness Iより、 d[v] ≧ δ(s, v)

(1)Line10-11の実行前に、 d[v] = δ(s, v) である場合。
Line10-11の実行後も d[v] = δ(s, v) である。

(2)Line10-11の実行前に、 d[v] > δ(s, v) である場合。
d[v] > δ(s, v) = δ(s, u) + w(u, v) = d[u] + w(u, v)
Line10-11の実行後は、 d[v] = d[u] + w(u, v) = δ(s, v)
となる。

**デフォルトの名無しさん** · 2017/01/03(火) 13:52:06.64

Correctness II:
ダイクストラのアルゴリズムが終了したとき、
すべての v ∈ V に対して、 d[v] = δ(s, v) が成り立つ。

証明：
d[v] は v が S に追加された後は、不変である。
よって、 v が S に追加されたときに、
d[v] = δ(s, v) であることを示せばよい。

背理法で示す。
v が S に追加されたときに、 d[v] ≠ δ(s, v) であるような
v ∈ V が存在すると仮定する。
u をそのような点の中で、最初に S に追加された点とする：
d[u] ≠ δ(s, u)
Correctness Iより、
d[u] > δ(s, u)

**デフォルトの名無しさん** · 2017/01/03(火) 13:52:49.71

今、 u が S に追加される直前の状況を考えることにする。
u はまだ S に追加されていないから、 u ∈ Q である。
p を s から u への一つの最短路とすると、 w(p) = δ(s, u) である。
s ∈ S, u ∈ Q であるから、 p 上の辺 (x, y) で x ∈ S, y ∈ Q となる
ような辺が存在する。そのような辺の一つを (x, y) とする。
すると、 p は以下のようになる。
p : s → … → x → y → … → u
x ∈ S であるから、 u に関する仮定より、
d[x] = δ(s, x) が成り立つ。また、明らかに、
s → … → x → y は s から y への一つの最短路であるから、
Correctness Lemmaより、 d[y] = δ(s, y) が成り立つ。
明らかに、 δ(s, y) ≦ δ(s, u) であるから、
d[y] ≦ δ(s, y)
また、Line07を見れば分かるように、
d[u] ≦ d[y] である。
よって、

d[u] ≦ δ(s, u) となるが、これは矛盾である。

**デフォルトの名無しさん** · 2017/01/03(火) 13:55:46.21

Lec 17 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005
https://youtu.be/xhG2DyCX3uA

**デフォルトの名無しさん** · 2017/01/05(木) 09:16:14.40

アルゴリズムイントロダクションって自明なことをわざわざループ不変量を使ったりして、
証明していて、うざすぎますね。

**デフォルトの名無しさん** · 2017/01/05(木) 09:16:52.73

通常の数学の本なら自明で済ませるようなことをわざわざ証明している。

**デフォルトの名無しさん** · 2017/01/05(木) 09:57:50.61

このバカ、以前も全く同じこと言って暴れたな。

**デフォルトの名無しさん** · 2017/01/05(木) 10:02:39.43

http://hissi.org/read.php/tech/20160422/cGVtVmVaYUg.html
http://hissi.org/read.php/tech/20160612/YkttemlBQ3Y.html
こいつだ。

> って当たり前のことをループ不変とかを使って説明しているよね。はっきりいってくどい。
> ループ不変式とかいうのが出てくるけど、当たり前のことを形式的に証明しているだけで、つまらなすぎる。
> 馬鹿の一つ覚えみたいにループ不変式をつかって証明しようとしている。

これぞ「馬鹿の一つ覚え」である。

**デフォルトの名無しさん** · 2017/01/05(木) 10:44:28.31

数学とコンピュータ科学の区別がつかない厨房だろう

**デフォルトの名無しさん** · 2017/01/05(木) 11:01:45.09

クヌースの本なんかだと妙なくどさはない。

アルゴリズムイントロダクションはメリハリが全くない。
Trivialなこともそうでないことも平等に扱いすぎている。

要するに本を書くセンスがない。

**デフォルトの名無しさん** · 2017/01/05(木) 11:02:52.69

セジウィックとウエインの本のほうがずっとよい。

**デフォルトの名無しさん** · 2017/01/05(木) 11:07:44.54

日本語の本について言及しておく。
例えば、評判のよい茨木俊秀の本。

こんな薄いスカスカの本をよくも恥ずかしげもなく出版するものだとあきれる。

**デフォルトの名無しさん** · 2017/01/05(木) 11:19:31.17

アルゴリズムイントロダクションの悪口を書いたがいいところもある。

例えば、第29章線形計画法。

線形計画法に対しては、Trivialなこともそうでないことも平等に扱うという方針が
向いているように思う。

ただ、アルゴリズムの本に線形計画法を入れる理由が分からない。

整数論的アルゴリズムの章はあまりにも簡単すぎる。
高木貞治の本でも読んだ方がよい。

**デフォルトの名無しさん** · 2017/01/05(木) 11:28:06.54

結論として、ベストな本はクヌースが予定しているTAOCPの要約本ということになる。

**デフォルトの名無しさん** · 2017/01/05(木) 11:29:47.36

結論として4i7P3+nFはNG行き

**デフォルトの名無しさん** · 2017/01/05(木) 11:33:33.85

>>253
自明ほど危ういものは無いんだが

**デフォルトの名無しさん** · 2017/01/05(木) 11:40:35.14

例によって ID:4i7P3+nF が発狂しててﾜﾛﾀ

**デフォルトの名無しさん** · 2017/01/05(木) 11:44:36.30

>>263

では、なぜ、一般に、コンピュータ科学者よりも頭が良いとされる数学者が
自明で済ませることが多いのでしょうか？

もし危ういのなら頭のよい数学者は自明などと書かないはずです。

**デフォルトの名無しさん** · 2017/01/05(木) 11:52:58.57

そんな多くねえよちゃんと論文読め

**デフォルトの名無しさん** · 2017/01/05(木) 12:06:11.36

自明連発する方が馬鹿なのか

**デフォルトの名無しさん** · 2017/01/05(木) 13:09:24.25

>>265
馬鹿丸出し

**デフォルトの名無しさん** · 2017/01/05(木) 13:18:34.40

>一般に、コンピュータ科学者よりも頭が良いとされる数学者が
根拠は？
>自明で済ませることが多いのでしょうか？
数学のコンテキストの話

そもそも証明の意味もコンピュータ科学と数学では違うだろ

**デフォルトの名無しさん** · 2017/01/05(木) 14:56:52.93

なんでバカって本質に関係ないところでギャーギャー騒ぐの？

**デフォルトの名無しさん** · 2017/01/05(木) 14:58:54.44

うむ

**デフォルトの名無しさん** · 2017/01/05(木) 19:46:02.51

アルゴリズムイントロダクションについて、数学が出来る人向けの本だという人がいる。
そして、数学ができない人はセジウィック＆ウエインの本を読めという人がいる。

アルゴリズムイントロダクションが数学的な本だとは全く思わない。数学的な内容については
主に結果だけを書いている。

ただネチネチとアルゴリズムの正しさの証明が書かれているだけのこと。

クヌースの本のように、楽しい本ではない。

**デフォルトの名無しさん** · 2017/01/05(木) 20:37:39.99

>>272
>>270

**デフォルトの名無しさん** · 2017/01/05(木) 22:15:16.24

書評したければ別のところでやれ

**デフォルトの名無しさん** · 2017/01/06(金) 17:19:30.91

再帰の除去についてやり方が詳しく書いてある本を教えてください。

**デフォルトの名無しさん** · 2017/01/06(金) 17:43:03.36

プログラミングコンテストチャレンジブック第2版のp.35
Lake Counting(POJ No.2386)

の解答として、以下のプログラムはあっていますか？

void dfs(i, j, n){
if(i < 0 || i >= N || j < 0 || j >= M){
return;
}
if(field[i][j] != 'W'){
return;
}
if(visit[i][j] == true){
return;
}
visit[i][j] = true;
dfs(i-1, j-1, n+1);
dfs(i-1, j, n+1);
dfs(i-1, j+1, n+1);
dfs(i, j-1, n+1);
dfs(i, j+1, n+1);
dfs(i+1, j-1, n+1);
dfs(i+1, j, n+1);
dfs(i+1, j+1, n+1);

if(n == 0){
count++;
}
return;
}

**デフォルトの名無しさん** · 2017/01/06(金) 18:06:18.89

>>275
えっと
かぅですか？
http://nothingcosmos.blog52.fc2.com/blog-entry-170.html

**デフォルトの名無しさん** · 2017/01/06(金) 18:36:23.48

Wrong Answerになっちゃうんだけど。

**デフォルトの名無しさん** · 2017/01/06(金) 18:38:07.31

例題については正しい答えが計算されるんだけど。

**デフォルトの名無しさん** · 2017/01/06(金) 18:43:00.23

よかったね

**デフォルトの名無しさん** · 2017/01/06(金) 20:15:02.80

>>277

ソースレベルで再帰を除去する方法が知りたいんですが。

**デフォルトの名無しさん** · 2017/01/06(金) 20:22:33.43

秋葉らのプログラムでもWrong Answerになっていまします。

入出力の問題のようですね。

**デフォルトの名無しさん** · 2017/01/06(金) 20:27:59.50

入出力の問題ってやっかいですね。
出力がどうなっているかとかPOJでは調べられないんですか？

**デフォルトの名無しさん** · 2017/01/06(金) 20:41:27.59

なんなんだろう？

scanf,printfを使っていたらダメだったのが、cinとcoutにしたらOKになった。

**デフォルトの名無しさん** · 2017/01/08(日) 12:26:37.82

F(p, n, r) の計算量を教えてください。

n: 整数
p, r: 整数配列（インデックス0からn-1）

F(p, n, r):
■■if r[n] ≧ 0:
■■■■return r[n]
■■if n == 0:
■■■■q = 0
■■else:
■■■■q = -∞
■■■■for i = 1 to n:
■■■■■■q = max(q, p[i] + F(p, n-i, r))
■■r[n] = q
■■return q

**デフォルトの名無しさん** · 2017/01/08(日) 12:31:27.73

O(n^2)

**デフォルトの名無しさん** · 2017/01/08(日) 12:32:34.98

>>285
ここで解説されてる
http://echo.2ch.net/test/read.cgi/tech/1363854937/

**デフォルトの名無しさん** · 2017/01/08(日) 13:51:15.22

>>286-287

ありがとうございます。

でも解説されていませんね。

**デフォルトの名無しさん** · 2017/01/08(日) 13:57:19.77

どうやって計算量を見積もるんですか？

何を単位にするんですか？

**デフォルトの名無しさん** · 2017/01/08(日) 14:06:13.08

T(n)
=
c1 + c2 * n + T(n-1) + … + T(0)
=
c1 + c2 * n + T(n-1) + c3*(n-1)

と解けばいいんですかね？

**デフォルトの名無しさん** · 2017/01/08(日) 14:07:36.75

T(n) = c1 + c2*n + T(n-1)
T(0) = c3

この漸化式の解を求めればいいんですかね？

**デフォルトの名無しさん** · 2017/01/08(日) 14:12:15.21

T(n)
=
[T(n) - T(n-1)] + [T(n-2) - T(n-3)] + … + [T(1) - T(0)] + T(0)
=
[c1 + c2*n] + [c1 + c2*(n-1)] + … + [c1 + c2*1] + c3
=
c1*n + c2*(1/2)*n*(n+1) + c3
=
Θ(n^2)

おお、あってるっぽいですね。

**デフォルトの名無しさん** · 2017/01/08(日) 14:20:56.92

>>290-292
は我ながら明解な解答ですが、

教科書では、以下のように導出しています。
この導出がよく分からないのですが。

「以前に解かれている部分問題を解くための再帰は直ちに戻るので、Fは
各部分問題をただ1度だけ解く。この手続きはサイズが0,1,....,nの部分問題
を解く。サイズがnの部分問題を解くために、for文がn回繰り返される。したがって、
Fの再帰呼び出し全体における、このfor文の繰り返し回数は等差数列を形成し、
総繰り返し回数はΘ(n^2)となる。」

**デフォルトの名無しさん** · 2017/01/08(日) 14:26:56.39

あーあ、分かりました。

T(n)
=
c1 + c2 * n + T(n-1) + … + T(0)
=
c1 + c2 * n + T(n-1) + c3*(n-1)

このあたりのことを言っているんですね。

**デフォルトの名無しさん** · 2017/01/08(日) 14:27:53.04

馬鹿には無理

**デフォルトの名無しさん** · 2017/01/08(日) 14:28:32.97

>>289

for文の繰り返し回数＝計算量ですね。

**デフォルトの名無しさん** · 2017/01/08(日) 14:29:42.72

結局自分ですべて解決してしまいました。

**デフォルトの名無しさん** · 2017/01/08(日) 17:12:11.39

よくやった
褒美として自分専用のスレを立てる権利をやろう

**デフォルトの名無しさん** · 2017/01/08(日) 18:45:26.96

命名ID:E98VLsZは俺様

**デフォルトの名無しさん** · 2017/01/08(日) 20:55:21.87

プログラミングコンテストチャレンジブック

p.45 Best Cow Lineっていう問題の解答のプログラムって無駄がありますよね。

この本を難しいという人がいますが、そんなに難しいですかね？