データ構造,アルゴリズム,デザインパターン総合ｽﾚ 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/18(日) 12:20:00.87

>>126

ライセンスとか書いてあっても一部だけコピペして利用したら、分からないですよね。

どうやって、だれかのコードを流用したか判定するのか、それに興味があります。

**デフォルトの名無しさん** · 2016/12/18(日) 12:30:54.60

アルゴリズムには著作権ないよ
あるのはそれをどう表現したか
簡単なアルゴリズムには表現バリエーションなんて限られてるから
ある程度似るのはどうしようもない

**デフォルトの名無しさん** · 2016/12/18(日) 12:37:57.44

特許ならありますよね。

**デフォルトの名無しさん** · 2016/12/18(日) 13:02:47.44

デザインパターンの本高い・・・
一冊持ってたけど引っ越しのごたごたでなくしちゃった
無料で網羅できるサイトありませんかね
一冊読んではあるので、さらっと構造や仕組みを紹介してくれていればいいし
英語もある程度は読めます

基本のデザインパターンだけでもありがたいし
マルチスレッド対応に踏み込んだサイトならなおありがたいです

**デフォルトの名無しさん** · 2016/12/18(日) 13:22:26.46

基本的な考え方覚えたら幾らでも応用できるだろ
カタログを後生大事にとっておく意味はない

**デフォルトの名無しさん** · 2016/12/18(日) 13:35:15.82

覚えてないんすよ
記憶力ないんで忘れちゃって、ぼんやりとしか覚えてないんです
だから概要をしっかり覚え直したいなと思って

**デフォルトの名無しさん** · 2016/12/18(日) 13:42:55.97

>>132
いや、デザパタ本こそ手元においておくべき
わけのわからん二次情報を見るとどんどんブレていくぞ

**デフォルトの名無しさん** · 2016/12/18(日) 13:45:05.00

リファレンスとしてはどの本がいい？

**デフォルトの名無しさん** · 2016/12/18(日) 13:45:12.43

ソフトウェア工学的な本って重要なんですか？

**デフォルトの名無しさん** · 2016/12/18(日) 13:45:59.00

学問的には全く面白くない分野ですよね。

**デフォルトの名無しさん** · 2016/12/18(日) 14:08:17.53

TECHSCOREのデザインパターンのページ見ることで自己解決しました

**デフォルトの名無しさん** · 2016/12/18(日) 15:45:37.97

デザパタカタログは便利だよね
煮詰まったときに、休憩がてらパターンを眺めてると、閃くときがある

**デフォルトの名無しさん** · 2016/12/18(日) 16:24:54.12

ねーわ、普通のコードが99.99%

**デフォルトの名無しさん** · 2016/12/18(日) 18:22:27.13

基本的な発想を学んだらカタログはポイ
パターンに執着してもデザインがぎこちなくなるだけ

**114** · 2016/12/18(日) 23:03:56.86

>>119
jsdo.it では、全員のソースコードが、サイト内に限り、MITになる

漏れが、わざわざ、MITと書いておいたのは、サイト外でも使ってほしいという意味。
学生が勉強することも多いから、コメントも一杯書いた

2分ヒープ、AVL、赤黒木など、アルゴリズムの実装は、どうしても汚いソースコードになる

**デフォルトの名無しさん** · 2016/12/18(日) 23:11:13.26

糞

**デフォルトの名無しさん** · 2016/12/18(日) 23:11:21.17

2分ヒープって簡単なアルゴリズムですよね。

汚くなりようがないように思うのですが。

**デフォルトの名無しさん** · 2016/12/18(日) 23:12:19.64

計算幾何学って難しい割に見返りが少ないように思います。

だからあんまり人気がないのかもしれないですね。

**デフォルトの名無しさん** · 2016/12/19(月) 00:01:07.57

漏れｗ

**デフォルトの名無しさん** · 2016/12/19(月) 01:06:56.52

流石に漏れは笑う

**デフォルトの名無しさん** · 2016/12/19(月) 08:08:43.72

>>144
全体的なリテラシの底上げがされるまではどうしてもね。

**デフォルトの名無しさん** · 2016/12/19(月) 12:42:11.26

>>144
理論的な上限値をあらかじめ計算することが出来て
無駄な努力や試行錯誤をしなくて済むというメリットがあるよ

**デフォルトの名無しさん** · 2016/12/19(月) 17:37:02.75

長さnの整数からなる列(a_1 ,a_2, ..., a_n) があるとして、列の大きさを
|a_1|+...+|a_n|で定義します。、
大きさがmの任意の列を大きさm-1の列の中の一つの値だけ1違う
列一つに対応させたいんですけど
対応のさせ方がわかりません、教えてください。
例えば n=3のとき(1, -1, 1)は大きさが3で、これに対応する長さ2の列は
(0 ,-1 ,1), (1,0,1),(1,-1,1),(1,-1,0)とかあるので一つには定まってません。
なのでその対応をする関数をおしえてください。

**間違ってたので直します** · 2016/12/19(月) 17:39:59.34

長さnの整数からなる列(a_1 ,a_2, ..., a_n) があるとして、列の大きさを
|a_1|+...+|a_n|で定義します。、
大きさがmの任意の列を大きさm-1の列の中の一つの値だけ1違う
列一つに対応させたいんですけど
対応のさせ方がわかりません、教えてください。
例えば n=3のとき(1, -1, 1)は大きさが3で、これに対応する大きさ2の列は
(0 ,-1 ,1), (1,0,1),(1,-1,0)とかあるので一つには定まってません。
なのでその対応をする関数をおしえてください。

**デフォルトの名無しさん** · 2016/12/19(月) 17:48:27.12

(1,-1,1)の長さが2?

**デフォルトの名無しさん** · 2016/12/19(月) 17:53:09.70

＞なのでその対応をする関数をおしえてください。

意味不明です。

**デフォルトの名無しさん** · 2016/12/19(月) 17:55:40.11

(a_1, a_2, ..., a_i, ..., a_n)

a_i > 0 のときには、

(a_1, a_2, ..., a_i-1, ..., a_n)

a_i < 0 のときには、

(a_1, a_2, ..., a_i+1, ..., a_n)

a_i = 0 のときには、

(a_1, a_2, ..., a_i±1, ..., a_n)

を返せばいいのでは？

**デフォルトの名無しさん** · 2016/12/19(月) 17:57:14.37

(a_1, a_2, ..., a_i, ..., a_n)

a_i > 0 のときには、

(a_1, a_2, ..., a_i-1, ..., a_n)

a_i < 0 のときには、

(a_1, a_2, ..., a_i+1, ..., a_n)

を返せばいいのでは？

a_i = 0 のときには、条件を満たす列は存在しないね。

**デフォルトの名無しさん** · 2016/12/19(月) 17:58:07.65

>>150

何がやりたいのかが不明確。

**デフォルトの名無しさん** · 2016/12/19(月) 17:58:17.41

>>149
列の最初の数字だけ1足すなり引くなりして返せばいいだけじゃないの？

**デフォルトの名無しさん** · 2016/12/19(月) 18:01:17.72

＞例えば n=3のとき(1, -1, 1)は大きさが3で、これに対応する大きさ2の列は
＞(0 ,-1 ,1), (1,0,1),(1,-1,0)とかあるので一つには定まってません。
＞なのでその対応をする関数をおしえてください。

一つに定まらないから、すべての結果を返したいのか、
任意の一つの結果を返したいのか？

**デフォルトの名無しさん** · 2016/12/19(月) 18:02:09.41

明らかに、

(0, 0, ..., 0) に対しては条件を満たす結果は存在しないね。

**デフォルトの名無しさん** · 2016/12/19(月) 18:50:37.10

０はスタート地点なので

**デフォルトの名無しさん** · 2016/12/19(月) 18:57:02.98

>>154
a_2を1としたとき(-1, 1)のとき(-1,0)を返し
a_1を-1としたとき　(-1,1)は(0,1)をかえすことになるので
一つに定まりません

**デフォルトの名無しさん** · 2016/12/19(月) 19:06:19.22

>>157
大きさn>0の任意の列aにたいしてf(a)=bでbがn-1の大きさでaと列の中の値が1だけ違う
列を出力する関数fを求めるということです。

**デフォルトの名無しさん** · 2016/12/19(月) 19:13:51.38

>>156
初めはそんな風に考えてる時期もありました
もう2か考えてるけれど全然わからないのでここで質問してみました

**デフォルトの名無しさん** · 2016/12/19(月) 19:16:05.63

>>161
問題文を鸚鵡返しするんじゃなくて、質問者の質問に答えたら？

**デフォルトの名無しさん** · 2016/12/19(月) 19:23:49.64

>>163
fの出力は列の集合じゃないから普通わかりますよね

**デフォルトの名無しさん** · 2016/12/19(月) 19:31:58.40

>>164
fが返すのは集合じゃないってのはどこに書いてある？

**デフォルトの名無しさん** · 2016/12/19(月) 19:34:42.99

>>165
14行上に書いてあります

**デフォルトの名無しさん** · 2016/12/19(月) 19:47:31.40

>>166
Mateだと>>156って書いてあるわ
自分の中ではこれは当然みたいな条件がいろいろあるんだろうけど、それを人に説明するのが下手なんじゃね

**デフォルトの名無しさん** · 2016/12/19(月) 20:02:25.40

改行コードの数を数えてますか？
文の折り返しと改行とは違いますよ？

**デフォルトの名無しさん** · 2016/12/19(月) 20:17:02.98

こりゃまたひどい質問者だな

**デフォルトの名無しさん** · 2016/12/19(月) 20:18:06.39

課題の丸投げ、しかも「日本語」が

**デフォルトの名無しさん** · 2016/12/19(月) 20:25:56.12

課題という証拠はありますか？
実際課題じゃなくプログラミングしていたら出てきた問題なので
全然課題じゃないです

**デフォルトの名無しさん** · 2016/12/19(月) 20:33:03.53

>>170
あなたには誤った文を訂正する能力がないんですか？
それでは人間ではなくコンパイラーと同じですよ

**デフォルトの名無しさん** · 2016/12/19(月) 20:37:51.17

>>169
面白い問題とつまらない問題を区別する能力が数学的推測には
一番必要なんんです
この問題がつまらないと思うのなら解かないでいいです

**デフォルトの名無しさん** · 2016/12/19(月) 20:50:46.99

問題をきちんと記述する能力に欠けている

**デフォルトの名無しさん** · 2016/12/19(月) 20:52:23.54

あと、面白い問題だと思うなら、それこそ自分で解くのが楽しいのでは
ここで聞かずに

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

>>175
楽しいものは独り占めるのではなく分け与えようと習わなかったのでは？

**デフォルトの名無しさん** · 2016/12/19(月) 21:44:43.60

>>174
今読み返してみましたがキチンと書かれてますよ
どこがキチンと書かれてないのか言ってくれたら
それは理解力の無さなので説明してもいいです

**デフォルトの名無しさん** · 2016/12/19(月) 22:34:08.82

十分楽しんだからあとは一人で楽しんでくれていいよ

**デフォルトの名無しさん** · 2016/12/19(月) 22:53:51.02

>>172
馬鹿乙

**デフォルトの名無しさん** · 2016/12/19(月) 23:04:39.12

先頭から非0を探して、はじめの要素が正なら1ひく、負なら1足す
これで終わりじゃないの？

**デフォルトの名無しさん** · 2016/12/19(月) 23:45:15.82

アルゴリズムは自分で考えるじゃ、ボケ

**デフォルトの名無しさん** · 2016/12/20(火) 13:05:59.52

>>171
茶か尿かもう判らんって意見があるけど
検出時のガスクロのデータ見直したら判るはずという話がある
仮にそれでお茶だとしてももう発表はないだろう

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

数列 1, 2, 3, …

すなわち、

数列 {a_n} = {n}

を考える。

{a_n} の任意の連続する有限部分列を a_k, a_(k+1), …, a_l（k ≦ l）とする。

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

「2^(b_i) は a_i を割り切るが、 2^(b_i+1) は a_i を割り切らない」

このとき、 #{m | k ≦ i ≦ l である任意の i に対して、 b_i ≦ b_m} = 1 であることを示せ。

また、有限部分列 a_k, a_(k+1), …, a_l（k ≦ l）が与えられたとき、 k ≦ i ≦ l である
任意の i に対して、 b_i ≦ b_m となるような m を求めるプログラムを作れ。

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

お断りいたします

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

俺も断るわ

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

早くも降参宣言か。

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

mなんていくらでもあるんじゃないの？
なんで#{m}=1？

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

>>187

一意的です。そこがちょっと面白いところです。

反例を作ろうと思ってもできないはずです。

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

>>183
分からない問題はここに書いてね421 [無断転載禁止]©2ch.net
http://rio2016.2ch.net/test/read.cgi/math/1480771004/493

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

k=1, l=2で、{m}={2,4,6,8,...}
k=l=1で、{m}=自然数の集合
じゃないの？

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

>>190

{a_n} の任意の＊連続する＊有限部分列を a_k, a_(k+1), …, a_l（k ≦ l）とする。

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

k=1, l=2で、{m}={2,4,6,8,...}
k=l=1で、{m}=自然数の集合
じゃないの？

a_1, a_2 = 1, 2

なので、 b_1, b_2 = 0, 1

です。

なので、 {m} = {2} です。

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

>>191
は勘違いです。

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

a_1 = 1

なので、

b_1 = 0

です。

なので、

{m} = {1}

です。

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

k=1, l=2も、k=l=1も、当然連続する部分列でしょ
{b_i}を10個ぐらい挙げてみてよ

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

mの条件が足りないんじゃないの？

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

b_i ≦ b_mさえ満たせばいいんならmなんていくらでもあるでしょ

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

b_m は b_i の最大値です。

その最大値となる b_m の m が一意的であるということです。

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

k≦m≦lという条件が抜けているっぽいね

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

テレンス・タオルベーグ積分入門
テレンスタオ
固定リンク: http://amzn.asia/8KaL6NK

「日本の理工系学部ではルベーグ積分は3年次程度の必修相当科目なので、」

↑これっておかしくないですか？

普通、ルベーグ積分なんてやるのは数学科かせいぜい物理学科くらいじゃないですか？

**デフォルトの名無しさん** · 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)!) とできますね。