データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。
アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。
京都大学霊長類研究所
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 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 ソートの決定木についてですが、葉の数が「少なくとも」 n! 個あると説明されることが多いですが、
ちょうど n! 個と書かない理由は何ですか？ 既に順序が決定されているにもかかわらず、さらに無駄な比較をするようなプログラムの
ことを想定しているのでしょうか？ そうだとすると、決定木のある部分木で、その葉がすべて同じ順序に対応するようなものが
存在することになります。 ソートの決定木について厳密に論じている本はありますか？ 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 最悪時にマージソートの半分の比較しか必要でないソートのアルゴリズムが存在しないこと
は証明できるのでしょうか？ あ、勘違いしました。
>>661
合っていますね。明らかに。 浅野孝夫著『アルゴリズムの基礎とデータ構造』を読んでいます。
以下の問題に対する浅野さんの解答が↓です。
「このとき根は葉ではないので左の子 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 個以下である。 >すべての葉の深さが d であるような二分木の葉の総数は明らかに 2^d 個である。
これ出しちゃったらそれで証明おしまいのような気がするが。 あ、問題文はおかしくないようです。
二分木において、深さ d までの葉の総数は 2^d 以下であることを示せ。
という問題でOKです。 二分木において、深さ d までの葉の総数が 2^d + 1 個以上である二分木が存在すると仮定する。
深さ d までの葉の総数が最多である二分木を T とする。
このとき、 T には深さ d 未満の葉が少なくとも一つ存在する。もしそうでないと仮定すると、 T の
すべての葉の深さは d 以上であるから、明らかに深さ d までの葉の総数は 2^d 個以下に
なってしまうが、これは矛盾である。
T の深さ d 未満の葉に子ノードを持たせれば、深さ d までの葉の総数が T よりも多い二分木が存在する
ことになってしまい矛盾が発生する。
よって、において、深さ d までの葉の総数は 2^d 個以下である。 二分木じゃなくて三分木なら2^d以下ではないわけだけど、>>669の証明を二分木から三分木に変えても
論理展開に違いが出ないから明らかにおかしいだろう。 三分木では、
「もしそうでないと仮定すると、 T のすべての葉の深さは d 以上であるから、明らかに深さ d までの葉の総数は 2^d 個以下に
なってしまう」
が成り立ちません。 三分木の場合の証明は以下のようになりますね。
三分木において、深さ d までの葉の総数が 3^d + 1 個以上である三分木が存在すると仮定する。
深さ d までの葉の総数が最多である三分木を T とする。
このとき、 T には深さ d 未満の葉が少なくとも一つ存在する。もしそうでないと仮定すると、 T の
すべての葉の深さは d 以上であるから、明らかに深さ d までの葉の総数は 3^d 個以下に
なってしまうが、これは矛盾である。
T の深さ d 未満の葉に子ノードを持たせれば、深さ d までの葉の総数が T よりも多い三分木が存在する
ことになってしまい矛盾が発生する。
よって、において、深さ d までの葉の総数は 3^d 個以下である。 >が成り立ちません。
成り立たないことがわかっているなら証明いらんだろうｗ
逆に言うと、それが成り立たないことが証明されていない。
>>673
3^dってどこから出てきたわけ？ 2分ヒープは完全二分木を使ったデータ構造ですが。
この完全二分木のことを半順序のついた木というのはなぜでしょうか？ %%%%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 バッチ処理, ジョブ制御に有効なデザインパターンって何? >>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 シングルトンがいけないとかたまに聞くんだけど
シングルトンなしでどうやるのか誰か教えて
シングルトン使わないで済むならシングルトン辞めることには吝かではないんだが
どうやるのかが分からない
HolderとかRepository作るとどうしてもシングルトンになっちゃう
誰か助けて シングルトンの何がいけないのかをわかっていれば別に使ってもいいんじゃないか？
と思うんだが 内部ノード数 n の 2色木の Black Height を h であらわすと以下の不等式が成り立つ。
2^(h-1) - 1 ≦ n ≦ 2^(2*h-1) - 1
よって、 h = O(log(n))
とある本に書いてあります。
これっておかしいですよね？
h は n の関数ではありません。内部ノード数から2色木の Black Height は一意的にはきまらないからです。
もちろん、 O(log(n)) の左辺には n の関数が来るきまりです。
ですので、 h = O(log(n)) と書くのはおかしいのではないでしょうか？ メッセージキューイングって
Commandパターンで実装するで合ってる？ >>686
>>2^(h-1) - 1 ≦ n ≦ 2^(2*h-1) - 1 ・・・(1)
>>よって、 h = O(log(n)) ・・・(2)
一見すると正しそうに見えるけど、どっちがどうおかしいと？ h が n の関数ではないにもかかわらず
h ∈ O(log(n))
と書いているのがナンセンスです。 >>689
nとhの関係は(1)で示されているんじゃね？
不等式を変形すれば良いのでは？ n から h は一意的に決まりません。
よって、
h は n の関数ではありません。 >>691
(1)より一意に決まらなくても計算量は同じでしょ？ ＞もちろん、 O(log(n)) の左辺には n の関数が来るきまりです。
ここの時点でおかしい 抽象メソッドしか定義されない型のことを
「インタフェース」ってネーミングセンスは頭おかしいんじゃないの？
インタフェースって言ったら通常「UI」とか外部の窓口になったり、
外部デバイスとの接続ポイントになるコネクタのことを言うじゃん。
オブジェクトの型のことを「インタフェース」なんて言ったら誤解を招くだろ。 >>695
interfaceには境界面とか接点の意味がある
クラスが持つ他との接点の意味で合ってる 外部の窓口になったり、外部デバイスとの接続ポイントになるのが抽象メソッドだから。
つまりそれしか定義されてないということは、インターフェースそのものと言っていいだろう。 デザパタスキル、エンベッデイドスキルなんやかや言うが、みんな大事な部分は閃きなんだがなぁ・・・
作曲と同じ。 閃き・・・ とどのつまり、神が書かせているという事。
そこを理解できない限り、そのプログラマーは聖職では無い。 神などと妄想するようになったら科学の全否定の始まり。無知が故の過ち。 神「共通化せよ――」
僕「はい」
神「ごめん間違えた――」
僕「うわぁぁああぁああ！！！」 以下で定義される写像 A : N × N → N を Ackermann 関数という。
A(1, j) = 2^j for j = 1, 2, 3, …
A(i, 1) = A(i-1, 2) for i = 2, 3, 4, …
A(i, j) = A(i-1, A(i, j-1)) for i = 2, 3, 4, … for j = 2, 3, 4, …
α(m, n) = min {i ≧ 1 | A(i, floor(m/n)) > log_2(n)}
で定義される写像 α : {(m, n) | m, n ∈ N, m ≧ n} → N を Ackermann 逆関数という。
なぜ、この α を Ackermann 関数の逆関数と呼ぶのでしょうか？ courseraのセジウィックとウエインの講義を受講しています。
プログラミングの課題のチェックが超厳しいですね。
'if' is not followed by whitespace.
「if」の後ろにスペースを入れないといけないなんて初めて聞きました。
そんなことまで強制されたらたまりませんね。 大概のプロジェクトで採用されてるスタイルだから従っとけ
スペース軽視するやつ多すぎ >>703
K&R2 に従っておけば文句が来ることはない
if ()
while ()
for () 一般的なコーディングルールには従ったほうがよい
最近の言語環境では放っておいてもツッコミ入れてくれたりもするが 業務システムでオブジェクト指向不要って意見はどう思いますか
大抵スパゲティークエリになってる印象ですが 途中からオブジェクト指向混ぜられても困るだろ
実行効率や記述効率は悪くたって別に構わないのだから（ここわかってない人多し）、プロジェクトに来た全員が理解利用できる書き方が最優先
無論技術的にも業務的にもうんこだが、そこを追求すべき場所ではないところで勝手に追及を始めるのはそれこそうんこのやること
ゼロからオーバーホールを提案してもよいが最後まで自己責任で看取れ >>709
サブクエリ五重の塔を見て上長にキツいと報告したら世界にはバベルの塔がいっぱいあるのに根をあげるなと叱られました
せめて何をしたいのかドキュメント欲しいと言ったらコードが全てだとも言われました
IT業界の厳しさを知りました courseraのセジウィックとウエインの講義の最初の課題であるパーコレーションだけど
backwashを防ぐにはどうすればいいんですか？ あ、分かりました。
virtual topにはつなぐがvirtual bottomにはつながないUF
virtual topにもvirtual bottomにもつなぐUF
を使えばいいんですね。 デザインパターンで規定されるいろいろなクラスがあるけど
これらのクラスはそれぞれレイヤー化アーキテクチャのどこに
属すのか知りたい。
たとえばStateパターンがあった場合に、
・<<interface>>State
・ConcreteState x n
・Context
があったとき、
これらは、クラスを配置する場所的に
・プレゼンテーション層(UI層)
・App層
・サービス層
・ビジネスロジック層
・パーシステンス層
のどこの層として配置すればいいのか > デザインパターンで規定されるいろいろなクラスがあるけど
> これらのクラスはそれぞれレイヤー化アーキテクチャのどこに
> 属すのか知りたい。
デザパタはレイヤ化アーキテクチャに属すものだという考え方が謎なんだけど >>719
どの層にも配置していいんじゃね
その層の機能とかを実現するのにそのデザインパターンが必要なら使えばいいのではないか
レイヤーとデザインパターンは独立に組み合わせ可能と思う デザパタを適用したクラスがどのレイヤにあっても構わんのじゃ無いか
定石があってもフレームワークごと違うから説明無理だと思う 1以上1000以下の整数からなる集合の部分集合で、
その任意の異なる2元 x, y をとったとき、
「x は y を割り切らず、 y も x を割り切らない」
という性質をもつものを考える。
そのような部分集合の中で元の数が最大になるような
集合の元の数を求めよ。 めっちゃ勘だが、334から666と、667以上の奇数でどうだろうか 答えは500以下です。
1 から 1000 までの整数を 2^n * (2*m + 1) の形で表す。
2*m + 1 の部分は、
2*0 + 1, 2*1 + 1, …, 2*499 + 1
の500個のパターンのいずれかに一致する。
よって、1 から 1000 までの整数の中から501個以上の異なる整数を選び出せば、
その中には、かならず、
2^n1 * (2*m + 1), 2^n2 * (2*m + 1)
という二つの整数が含まれる。
この二つの整数は一方が他方を割り切る。 どっかから問題と回答を拾ってきてドヤ顔してる人ってなんなの？ >>727
何をしているのかちゃんと理解したいのですが、
m や n は実数ですか？ >>729
>>727が言葉が足りてないのは確かだが、もうちょっと数学のセンス磨こうぜ >>730
n=0 にして、m=0, 1, 2 ...
n=1 にして、m=0, 1, 2 ...
...
とやって確かめたら、なんとなく自然数を網羅できそうなのは確認できました。
ただ、本当に網羅できるのか証明はまだできてません。
これ以上はスレチも甚だしいので、独りで頑張ってみます。
流れぶった切ってすみません。
>>725 さん、どうぞ続けてください。 >>729
整数を 2 で割れるだけ割ると 2^n * (2*m + 1) の形になります。
例：
120 = 2^3 * 15 = 2^3 * (2*7 + 1)
この場合、 n = 3, m = 7 です。 1 = 2^0 * (2*0 + 1)
2 = 2^1 * (2*0 + 1)
3 = 2^0 * (2*1 + 1)
…
999 = 2^0 * (2*499 + 1)
1000 = 2^3 * (2*62 + 1)
となります。
1, 2, …, 1000 をすべて
2^n * (2*m + 1)
という形に表します。
m は 0 から 499 までの 500 個の整数のどれかになります。
ですので、 1, 2, …, 1000 の中から 501 個以上の整数を取ってきて、それらすべてを
2^n * (2*m + 1)
という形に表すと、
2*m + 1
の部分が同じになるような異なる2つの整数があります。
2*m + 1 の部分は同じで、 2^n の部分が異なります。それら2つの整数は
2^n1 * (2*m + 1), 2^n2 * (2*m + 1) のようにあらわされます。 n1 < n2 と仮定して一般性を失いません。
2^n2 * (2*m + 1) は 2^n1 * (2*m + 1) で割り切れます。 2^n2 * (2*m + 1) ÷ 2^n1 * (2*m + 1) = 2^(n2-n1) 500以下なのはわかった。500ある例>>726も見つかった。
で、一般に1からNのとき、何個になるのよ？ >>726
{501, 502, …, 1000} でもOKですね。 >>735
ceiling(n/2)
ではないでしょうか？ セジウィックとウエインのcourseraのオンライン講義を聴講しています。
java.util.List
java.util.Stack
java.util.Queue
は最低だそうですね。
Best practices: Use our implementations of Stack, Queue, and Bag.
だそうです。 最近傍探索で、最も近いものが複数個あった場合、どうするのが自然ですか？
また、k近傍探索でも、クエリからk番目に近いものが複数あった場合、どうするのが自然ですか？ セジウィックとウエインのcourseraのオンライン講義を聴講しています。
なんかやけに課題が厳しくないですか？ セジウィックとウエインのcourseraのオンライン講義Algorithms Part 1のWeek 2の課題、できた人いますか？ courseraのセジウィックとウエインの講義を聴講している人はいますか？ >>746
宿題なら自分でやれ
そうでないなら読むのめんどくさいから要約しろ あ、仕様Memory量の見積を勘違いしていました。
できそうですね。
Item 型のデータを格納する Linked List
と
Linked List の各要素への参照を格納する Item[] 型の
配列を用意すれば実現できますね。 あ、でも Item[] 型の配列を ResizingArray で実現したとしても、
常に、Memoryの制限である 48*n + 192 bytes というのを満たすのは
無理ですね。
どうすればいいんですかね？
もう少しだけメモリの制限が緩ければ実現可能ですが。 Performance requirements.
Your randomized queue implementation must support each randomized queue
operation (besides creating an iterator) in constant amortized time.
That is, any sequence of m randomized queue operations (starting from an empty
queue) must take at most cm steps in the worst case, for some constant c.
↑これと↓を両立させることはできるのでしょうか？
A randomized queue containing n items must use at most 48n + 192 bytes of
memory. あ、なんだ
簡単でしたね。
Item[] 型の Resizing Array を使えば、
メモリ使用量 〜 8*n
だから、4倍くらいメモリを無駄に使っても
48*n を超えませんね。 あ、なんだ
簡単でしたね。
Item[] 型の Resizing Array を使えば、
無駄が全くないときのメモリ使用量 〜 8*n
だから、4倍くらいメモリを無駄に使っても
48*n を超えませんね。 これから実装しますが、また100点満点中100点になりそうです。 あ、やっぱりだめですね。
dequeue の計算量がネックになりますね。 あ、分かりました。
一様ランダムに選択された a[i] に a[N] を移せばいいんですね。 ■ このスレッドは過去ログ倉庫に格納されています
