データ構造,アルゴリズム,デザインパターン総合ｽﾚ 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

**デフォルトの名無しさん** · 2017/07/24(月) 01:46:14.40

もっと本質的な勘違いか。
AならばBはA=Bではないし、AならばBは、BならばAでもないぞ。
言ってるのはthe value, taking on all values in between だけだからな。

**デフォルトの名無しさん** · 2017/07/24(月) 03:48:35.95

>>582

n については何も記述がありません。

そもそも、普通なら関数について書くときには、定義域を書くはずですが、
書いてありません。

習慣として、 n と書けば自然数の集合を動く変数ということになりますので、
そう解釈するのが妥当です。

1 + sin(n) が 0 と 2　の間のすべての値をとるのであれば、当然、

0 < 1 + 1/sqrt(2) < 2 ですので、値 1 + 1/sqrt(2) もとります。

**デフォルトの名無しさん** · 2017/07/24(月) 03:58:43.71

念のため、公式ページの正誤表を見てみましたが、書いてありませんでした。

かなり売れている本だと思いますが、飛ばし読みしている人ばかりなのでしょうか？

**デフォルトの名無しさん** · 2017/07/24(月) 04:32:03.26

数学の世界ならそうだろうが、数学本じゃなくてプログラミングの本なんだろ？
sin(n)　と書いてあればプログラマはたいてい n をfloat型かdouble型の変数だと解釈する。
=　一つとっても大抵のプログラミング言語は等式ではなく、代入演算子と定義している。
分野が違うのだから論理的におかしいと思ったらまずは定義を疑う。数学だってブール代数で1+1=1って書く場合もあるだろう。
今のプログラミング言語は+や-の演算子すら再定義できるのだ。

仮に自然数だとしても、次に本質的な論理問題。>>583 これ。

> 0 と 2　の間のすべての値をとる

これも怪しい。take on All Value なので、on　～の上にという意味で、日本語にするならば結果がその範囲内に収まるだろう。
All values in between take the valueではないのだ。AはBのとき、BはAか？もちろん偽。
つまり1 + sin(n) = 1 + 1/sqrt(2)を保証する記述ではない。

**デフォルトの名無しさん** · 2017/07/24(月) 09:36:19.03

馬鹿のアスペにかまうな

**デフォルトの名無しさん** · 2017/07/24(月) 15:13:09.34

>>569
>「関数 n^(1 + sin(n)) の指数部の値は 0 と 2 の間で振動し、その中間にあるすべての値をとる」

指数部の値は 0 と 2 の間で振動し、その中間にあるすべての値をとるんじゃね？

**デフォルトの名無しさん** · 2017/07/25(火) 00:02:25.50

nが自然数か何かも書いてないのに勝手に自然数だと勘違いして発狂するとか何考えてんでしょうね

**デフォルトの名無しさん** · 2017/07/25(火) 08:35:49.61

sin(n) = 1/sqrt(2) のとき n = 約0.785。 degだと45度。
って、そういう話じゃなくて？

**デフォルトの名無しさん** · 2017/07/25(火) 16:29:58.97

nが自然数でも問題ない

**デフォルトの名無しさん** · 2017/07/25(火) 16:30:50.54

そもそも指数部(1 + sin(n))の話しかしてないんだから

**デフォルトの名無しさん** · 2017/07/26(水) 01:18:42.44

え？

**デフォルトの名無しさん** · 2017/07/26(水) 09:54:26.90

お

**デフォルトの名無しさん** · 2017/07/28(金) 14:53:29.74

凄いことにきずいたぜ！
「ポリモーフィズム」と「ラッパー」は反対の関係にあるんだ。
これによって「メソッド名」と「中身」が多対多の関係にできるってことだぜ。

**デフォルトの名無しさん** · 2017/07/29(土) 09:28:33.20

ライブラリってログを吐いてもいいの？

**デフォルトの名無しさん** · 2017/08/06(日) 03:45:40.20

シーケンス図とかスタックトレースって都庁なんだな。
おれの言いたいことが分かるか？「東京都庁」なんだよ。

**デフォルトの名無しさん** · 2017/08/06(日) 03:55:13.24

待てよ・・・ピラミッドやサクラダファミリアも同じ形をしてるじゃないか！
この世界の真実を見たぞ・・・

**デフォルトの名無しさん** · 2017/08/06(日) 16:19:04.74

ムーの読みすぎ

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

つかオブジェクト名繋げないでいきなり関数とは変数とか
呼ぶやつまじでやめて。
継承した変数や関数なのか、このクラスで定義した変数や関数
のかわからないじゃん。
このクラスで定義したものだったら thisつけろよ。

**デフォルトの名無しさん** · 2017/08/09(水) 01:40:35.40

>>600
ちょっと何言ってるかよくわからない

**デフォルトの名無しさん** · 2017/08/09(水) 06:04:34.33

言語なによ

**デフォルトの名無しさん** · 2017/08/09(水) 16:52:44.18

javascriptωじゃね

**デフォルトの名無しさん** · 2017/08/11(金) 13:57:12.96

デザパタは覚えたし、クラス図やシーケンス図も読める、クラス図の通り
にコーディングもできるし、だいたい何らかのパターンに当てはめ
ればなんとか動く。
命名規則も全部決めてるからその規則通りに書けば自動的に動く
でも「なんでそうなるの？」って質問されるとさっぱりわからないんだよなぁ…
デザパタに則っていないコードとか、俺と違う命名規則の人が書いた
コードも一切理解不能(無能)。

**デフォルトの名無しさん** · 2017/08/11(金) 14:22:23.73

>>604
ただの作業員じゃん(笑)

**デフォルトの名無しさん** · 2017/08/11(金) 16:40:01.48

>>604
なんとなくだけど、将棋弱そう

**デフォルトの名無しさん** · 2017/08/11(金) 16:48:21.14

>>604
なんとなくだけど、頭弱そう

**デフォルトの名無しさん** · 2017/08/11(金) 17:03:34.23

IQ90くらいだろ

**デフォルトの名無しさん** · 2017/08/11(金) 17:12:35.31

そんなに煽ってやるなよ

**デフォルトの名無しさん** · 2017/08/11(金) 17:20:22.56

372仕様書無しさん2017/08/11(金) 10:31:43.41
フリーランスで検索すると引っかかる零細ITがやっているサイトはだめだ。
高額に見せているけど実際は50万前後
JIET加入した方がいいよ。案件は毎日千件以上末端価格は60万円　平凡な稼働時間の80万円の案件もある。
ユー子が求人をだしてる。名刺も渡せる。ユー子に名刺が渡せるんだぞ。夢のようだ

それらの案件まさぐってHPで転売していたのが零細ITがやるフリーランスサイト

自称エージェントはJIETから流れてくる案件を転売してるだけだった。
JIETに加入すれば誰でも案件に応募することができた。収入が40万50万台にならなくて済む

473非決定性名無しさん2017/08/03(木) 15:21:30.71

JIETに加入すれば誰でも3次60万からスタートだ。フリーランスのサイトをやってる
自称エージェントもそこから案件情報を取得しきてる。サイトで60万で釣って40万から55万の
間でやらしている。

**デフォルトの名無しさん** · 2017/08/11(金) 22:22:00.80

>>604
キミは理想のPGだよ。

**デフォルトの名無しさん** · 2017/08/11(金) 23:53:53.43

>>604
いまどきデザインパターン？

**デフォルトの名無しさん** · 2017/08/12(土) 05:31:45.11

オートマ限定免許だな

**デフォルトの名無しさん** · 2017/08/12(土) 11:21:25.45

ちょｗｗ俺煽られすぎｗｗｗ
でも、モノは完成するようになったぜ。
要求、仕様から動作原理すっ飛ばして、命名規則だけで
モノが完成するから結構職場では役立ってるぜ。
他のプログラマはフレームワークの使い方がやっとだし
一人だけ技術力があるゴリラ野郎は人望がなくて自分の技術力が
人に盗まれるのを極力恐れているから基本的に部下に意地悪して
教えてあげれば済むことも何も教えてくれない。
社長はどんどん仕事取ってきて、だいたい半数のプロジェクトが進まずに凍結状態に
なり、ブチ切れた客をなんとかかわし続ける日々だ。
そんな状況で俺の場合動くモノを比較的完成する方だからゴリラには結構
気に入られて給料は上がったよ。会社がいつまで持つかは分からんが。

**デフォルトの名無しさん** · 2017/08/12(土) 11:28:43.73

このスレは初心者スレだったな。

**デフォルトの名無しさん** · 2017/08/12(土) 11:55:15.14

>>614
どこを縦読み？

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

戦隊もので言えばブラックじゃないですか！

**デフォルトの名無しさん** · 2017/09/01(金) 03:15:32.30

状態遷移のように汎用的に使える技術って他にも何かありますか？

**デフォルトの名無しさん** · 2017/09/01(金) 09:04:39.07

ストラテジーが最強

**デフォルトの名無しさん** · 2017/09/01(金) 15:05:22.49

デザインパターンですか？汎用性ありますかね

**デフォルトの名無しさん** · 2017/09/03(日) 14:32:35.28

>>620
概念と用語だけマスターすれば良い。

あとは実務に合わせて使えるところは利用するし、合わない部分は気にしない。

**デフォルトの名無しさん** · 2017/09/03(日) 15:06:35.15

>>621
なるほど
ありがとうございます

**デフォルトの名無しさん** · 2017/09/03(日) 17:00:04.12

>>622
>>621みたいに、わかったような口を叩くけど実際にやらせてみたら手が動かないカスになったらダメ
自分でどんどん適用してみて、メリットもデメリットも自分の体験として語れるようになった方がいい

**デフォルトの名無しさん** · 2017/09/03(日) 21:20:14.64

>>623
なるほど
ありがとうございます

**デフォルトの名無しさん** · 2017/09/03(日) 22:05:38.94

https://ideone.com/mWu6mC
写経してみたけどどんな時に使えるのかいまいちわかりませんでした・・・

**デフォルトの名無しさん** · 2017/09/03(日) 23:18:58.10

正解です。

**デフォルトの名無しさん** · 2017/09/04(月) 23:07:19.92

>>625
さらっと読んで写経したぐらいで理解できると思わない方がいい
そのうちわかってくるから、とにかく手を動かしコードを動かす経験を積み重ね続けるんだ

**デフォルトの名無しさん** · 2017/09/14(木) 20:19:04.82

Introduction to Algorithms 3rd Editionを読むスレ [無断転載禁止]©2ch.net
http://mevius.2ch.net/test/read.cgi/tech/1505387171/

**デフォルトの名無しさん** · 2017/09/15(金) 07:54:04.88

>>618
＞汎用的に使える技術
良い質問だなこれ
遅レスだけど考えたい

地味だけど基礎的なデータ構造が
一番汎用的なんじゃないか？
連結リストとか二分木とかそういうの

**デフォルトの名無しさん** · 2017/09/15(金) 11:43:47.38

隣接行列とか

**デフォルトの名無しさん** · 2017/09/16(土) 07:20:33.50

>>629
それは言えてるかもしれない
汎用的=基礎的

**デフォルトの名無しさん** · 2017/09/16(土) 09:24:14.80

consセル？

**デフォルトの名無しさん** · 2017/09/17(日) 17:09:50.02

Kleinberg & Tardosの本に以下のような内容の記述があります。
でも、 n > 1 のとき、 H が universal になることは決してないですよね。
u = v のとき、常に、 h(u) = h(v) なので、問題の確率は 1 ですから。

--------------------------------------------------
U を要素数の非常に多い有限集合とする。

H を U から {0, 1, ..., n-1} へのすべての写像の集合のある部分集合とする。

u, v ∈ U に対して、ランダムに選んだ h ∈ H が h(u) = h(v) を満たす確率はたかだか 1/n であるとき、
H は universal であるという。

**デフォルトの名無しさん** · 2017/09/17(日) 17:30:37.45

S を #S ≦ n であるような任意の U の部分集合とする。
u を U の任意の要素とする。
X をランダムな選択 h ∈ H に対して、値 #{s ∈ S | h(s) = h(u)} をとるようなランダム変数とする。

このとき、

E[X] ≦ 1

である。

証明：

s ∈ S に対し、
h(s) = h(u) であるならば、 1
h(s) ≠ h(u) であるならば、 0
となるようなランダム変数を X_s とする。

仮定により、 H は universal であるから、
E[X_s] = Pr[Xs = 1] ≦ 1/n

X = Σ X_s だから期待値の線形性により、

E[X] = ΣE[X_s] ≦ #S * (1/n) ≦ 1

**デフォルトの名無しさん** · 2017/09/17(日) 17:32:48.13

この証明は、

u ∈ S であるとき、破綻しますよね。

**デフォルトの名無しさん** · 2017/09/17(日) 17:37:20.77

Kleinbergはネヴァンリンナ賞を受賞した人だそうですが、大丈夫な人なのでしょうか？

**デフォルトの名無しさん** · 2017/09/17(日) 18:52:52.16

ID:7slIJ8syは馬鹿アスペの松坂君

**デフォルトの名無しさん** · 2017/09/17(日) 23:18:40.22

> u = v のとき、常に、

また勝手におれ条件を付け加えてるな。

**デフォルトの名無しさん** · 2017/10/06(金) 23:28:50.73

T(n) = Ω(g(n))

⇔

T(n) ≧ c*g(n) となる n が無限に多く存在するような定数 c が存在する。

という定義がありますが、なぜ、ほとんどすべての n ではないのでしょうか？

**デフォルトの名無しさん** · 2017/10/07(土) 08:08:49.02

「B木」の「B」の由来って謎なのかよ。

**デフォルトの名無しさん** · 2017/10/07(土) 08:55:33.93

>>639

Knuthは、

T(n) = Ω(g(n))

⇔

ほとんどすべての n に対して、 T(n) ≧ c*g(n) が成り立つ。

と定義するのがいいと書いていますが。

**デフォルトの名無しさん** · 2017/10/07(土) 10:32:49.92

Binary(嘘)
Balance(へ？)

**デフォルトの名無しさん** · 2017/10/07(土) 14:37:48.61

Boeing

**デフォルトの名無しさん** · 2017/10/07(土) 19:13:27.20

バランスだろ

**デフォルトの名無しさん** · 2017/10/08(日) 09:18:29.57

A木があるだから、その次ってことでB木だろ

**デフォルトの名無しさん** · 2017/10/08(日) 10:08:31.18

C木、D木、・・・、Z木

**デフォルトの名無しさん** · 2017/10/08(日) 11:43:33.94

乃木、高木、猪木

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

Θ(f(n)) を使うべきところで、 O(f(n)) を使っているという批判をする人がいますが、
具体的にはどういう状況でしょうか？

**デフォルトの名無しさん** · 2017/10/08(日) 19:44:09.13

シータオメガなんて数学以外で使ったことない

**デフォルトの名無しさん** · 2017/10/08(日) 20:36:16.81

FFでよく使う

**デフォルトの名無しさん** · 2017/10/08(日) 20:44:05.42

AAでまれに使う

**デフォルトの名無しさん** · 2017/10/09(月) 18:34:06.40

浅野孝夫著『アルゴリズムの基礎とデータ構造』を読んでいます。

「上の挿入ソートの例のように、基本演算回数（比較回数）は入力サイズ n にのみ
依存するとは言えない。そこで、入力サイズ n の入力のうちでアルゴリズムが最も
多くの基本演算を必要とする入力を考えて、それに対する基本演算回数を、本書ではん、
サイズ n の入力に対するアルゴリズムの計算量（time complexity of an algorithm）と
呼ぶ。すなわち、最悪の場合を想定してアルゴリズムの計算量を定めていることになる。
このようにして定められたアルゴリズムの計算量 T はもちろん n にのみ依存する関数で
あるので T(n) と書ける。上の挿入ソートの例では T(n) = n*(n-1)/2 である。」

と書いてあります。

その後、マージソートのところには、

「マージソートの計算量は T(n) = O(n*log(n)) である」

と書いてあります。

T(n) は最悪の場合の計算量ですから、

T(n) = Θ(n*log(n)) が正しいのではないでしょうか？

ちなみに、浅野さんは、この本の最初のほうで O, Ω, Θ を定義しています。

**デフォルトの名無しさん** · 2017/10/09(月) 18:35:57.26

もちろん、 f(n) ∈ Θ(n*log(n)) ⇒ f(n) ∈ O(n*log(n)) ですが。

**デフォルトの名無しさん** · 2017/10/09(月) 18:51:59.25

浅野さんは、挿入ソートの計算量を

O(n^2)

と書いています。

これも

Θ(n^2)

と書くべきですよね。

>>652

に引用したように、

「上の挿入ソートの例では T(n) = n*(n-1)/2」

ですから。

**デフォルトの名無しさん** · 2017/10/09(月) 20:59:07.08

馬鹿アスペの連投

**デフォルトの名無しさん** · 2017/10/09(月) 21:39:35.32

ID:vbK8I5kP くらいの基地外になれば、100連投だって容易い。

**デフォルトの名無しさん** · 2017/10/15(日) 10:39:26.70

ソートの決定木についてですが、葉の数が「少なくとも」 n! 個あると説明されることが多いですが、
ちょうど n! 個と書かない理由は何ですか？

**デフォルトの名無しさん** · 2017/10/15(日) 10:46:56.72

既に順序が決定されているにもかかわらず、さらに無駄な比較をするようなプログラムの
ことを想定しているのでしょうか？

**デフォルトの名無しさん** · 2017/10/15(日) 10:48:49.83

そうだとすると、決定木のある部分木で、その葉がすべて同じ順序に対応するようなものが
存在することになります。

**デフォルトの名無しさん** · 2017/10/15(日) 10:49:46.78

ソートの決定木について厳密に論じている本はありますか？

**デフォルトの名無しさん** · 2017/10/15(日) 11:09:38.82

This result serves as a guide for us to know, when designing a sorting algorithm, how
well we can expect to do. For example, without such a result, one might set out to try
to design a compare-based sorting algorithm that uses half as many compares as does
mergesort, in the worst case. The lower bound in Proposition I says that such an effort
is futile?no such algorithm exists

**デフォルトの名無しさん** · 2017/10/15(日) 11:10:24.51

>>661

この説明は間違っていますよね？

**デフォルトの名無しさん** · 2017/10/15(日) 11:13:29.73

最悪時にマージソートの半分の比較しか必要でないソートのアルゴリズムが存在しないこと
は証明できるのでしょうか？

**デフォルトの名無しさん** · 2017/10/15(日) 11:54:45.59

あ、勘違いしました。

>>661

合っていますね。明らかに。

**デフォルトの名無しさん** · 2017/10/15(日) 13:42:57.88

馬鹿アスペの連投

**デフォルトの名無しさん** · 2017/10/21(土) 16:32:10.02

浅野孝夫著『アルゴリズムの基礎とデータ構造』を読んでいます。

以下の問題に対する浅野さんの解答が↓です。

「このとき根は葉ではないので左の子 v および右の子 w をもつ。」などと書いていますが、
深さ d > 0 の二分木で左の子もしくは右の子を持たないものも当然存在します。
おかしな解答ですね。

二分木において、深さ d までの葉の総数は 2^d 以下であることを示せ。

d に関する帰納法で証明できる。 d = 0 のときは根は葉になるので明らかに成立する。 d > 0 未満で
成立すると仮定し d のときを考える。このとき根は葉ではないので左の子 v および右の子 w をもつ。
v を根とする部分木の深さ d - 1 までの葉が元々の二分木の深さ d までの葉になるがそのような葉の
総数は帰納法の仮定より、 2^(d-1) 以下である。同様に w を根とする部分木の深さ d - 1 までの葉の
総数も 2^(d-1) 以下であり、したがって、元々の二分木の深さ d までの葉の総数は 2^d 以下であることが
言えた。

この問題文自体もおかしいです。

この問題の結果が本文中で使われていてそこを読めばわかるのですが、問題文の意味は、
「深さ d の二分木の葉の総数は 2^d 以下であることを示せ」です。以下のような解答が模範解答ですね。

深さ d の二分木でその葉の総数が 2^d + 1 個以上であるような二分木が存在すると仮定する。
そのような二分木のうち葉の総数が最多であるような二分木を T とする。
すべての葉の深さが d であるような二分木の葉の総数は明らかに 2^d 個である。
よって T の葉にはその深さが d 未満であるような葉が存在する。この葉に子ノードを持たせれば
深さ d の二分木で葉の総数が T の葉の総数よりも多い二分木を作ることができるがこれは矛盾である。
よって、深さ d の二分木の葉の総数は 2^d 個以下である。

**デフォルトの名無しさん** · 2017/10/21(土) 16:38:07.00

>すべての葉の深さが d であるような二分木の葉の総数は明らかに 2^d 個である。

これ出しちゃったらそれで証明おしまいのような気がするが。

**デフォルトの名無しさん** · 2017/10/21(土) 16:43:21.60

あ、問題文はおかしくないようです。

二分木において、深さ d までの葉の総数は 2^d 以下であることを示せ。

という問題でOKです。

**デフォルトの名無しさん** · 2017/10/21(土) 16:51:58.42

二分木において、深さ d までの葉の総数が 2^d + 1 個以上である二分木が存在すると仮定する。
深さ d までの葉の総数が最多である二分木を T とする。

このとき、 T には深さ d 未満の葉が少なくとも一つ存在する。もしそうでないと仮定すると、 T の
すべての葉の深さは d 以上であるから、明らかに深さ d までの葉の総数は 2^d 個以下に
なってしまうが、これは矛盾である。

T の深さ d 未満の葉に子ノードを持たせれば、深さ d までの葉の総数が T よりも多い二分木が存在する
ことになってしまい矛盾が発生する。

よって、において、深さ d までの葉の総数は 2^d 個以下である。

**デフォルトの名無しさん** · 2017/10/21(土) 18:35:04.55

馬鹿アスペの連投

**デフォルトの名無しさん** · 2017/10/21(土) 18:51:41.34

二分木じゃなくて三分木なら2^d以下ではないわけだけど、>>669の証明を二分木から三分木に変えても
論理展開に違いが出ないから明らかにおかしいだろう。

**デフォルトの名無しさん** · 2017/10/21(土) 19:21:45.75

三分木では、

「もしそうでないと仮定すると、 T のすべての葉の深さは d 以上であるから、明らかに深さ d までの葉の総数は 2^d 個以下に
なってしまう」

が成り立ちません。

**デフォルトの名無しさん** · 2017/10/21(土) 19:24:01.05

三分木の場合の証明は以下のようになりますね。

三分木において、深さ d までの葉の総数が 3^d + 1 個以上である三分木が存在すると仮定する。
深さ d までの葉の総数が最多である三分木を T とする。

このとき、 T には深さ d 未満の葉が少なくとも一つ存在する。もしそうでないと仮定すると、 T の
すべての葉の深さは d 以上であるから、明らかに深さ d までの葉の総数は 3^d 個以下に
なってしまうが、これは矛盾である。

T の深さ d 未満の葉に子ノードを持たせれば、深さ d までの葉の総数が T よりも多い三分木が存在する
ことになってしまい矛盾が発生する。

よって、において、深さ d までの葉の総数は 3^d 個以下である。

**デフォルトの名無しさん** · 2017/10/21(土) 19:33:58.53

>が成り立ちません。

成り立たないことがわかっているなら証明いらんだろうｗ
逆に言うと、それが成り立たないことが証明されていない。

>>673
3^dってどこから出てきたわけ？

2017/10/22(日) 15:43:58.38

2分ヒープは完全二分木を使ったデータ構造ですが。

この完全二分木のことを半順序のついた木というのはなぜでしょうか？

**デフォルトの名無しさん** · 2017/10/23(月) 05:47:03.23

%%%%1000%%%%

000-[HUM%58*73.1\%]/2I/3NM/61.3SNMK%?%3%51.22222222222221%
001-[[[%6/4$17.6135412α3]]]]+DOM+SIL+7%
002-UML7%[61.2[31.5[!%32∂LM17.36%!16.3!%<<<%!HSTOL7%!Q!S!=3m=<2TOL<3Q9A<2.1GHz%,DOK,HAOARA,
003-[[[HEMLOT47[<\41.2%Q,===>[MLS<DPNO<\2.3>#ESOLA!5%!3MLA!>LTOSA>7TONSA>%>%end

**デフォルトの名無しさん** · 2017/10/24(火) 00:30:44.81

バッチ処理, ジョブ制御に有効なデザインパターンって何?

**デフォルトの名無しさん** · 2017/10/24(火) 09:45:11.29

バッジパターン

**デフォルトの名無しさん** · 2017/11/05(日) 08:35:59.08

ヤフーブログの　https://blogs.yahoo.co.jp/kamyu_2010　にデザパタ解説を発見した。

**デフォルトの名無しさん** · 2017/11/05(日) 13:49:09.49

>>675
再帰的に、親は両方の子以下の数値をもつ。
左右の子の大小関係は考慮しない

ここでは説明しやすいように、配列の[0]は使わない。
[1]から始めると計算が楽。
親1, 左右の子は2, 3で、法則は、親n, 子2n, 2n+1

もし[0]から始めると、
親0, 左右の子は1, 2で、親1, 左右の子は3, 4で、
法則は、親n, 子2n+1, 2n+2、となり複雑

親[1] → 子[2, 3]
[1]3, [2]10, [3]30

[2] → [4, 5]
[4]100, [5]20

[3] → [6, 7]
[6]70, [7]200

JavaScript で、漏れが作った、2分ヒープ
http://jsdo.it/michihito/bGH5

**デフォルトの名無しさん** · 2017/11/05(日) 13:58:55.54

で、半順序はどこに登場するんですか？

**デフォルトの名無しさん** · 2017/11/05(日) 19:58:31.80

>左右の子の大小関係は考慮しない