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

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

**デフォルトの名無しさん** · 2017/11/06(月) 23:54:10.39

シングルトンがいけないとかたまに聞くんだけど
シングルトンなしでどうやるのか誰か教えて

シングルトン使わないで済むならシングルトン辞めることには吝かではないんだが
どうやるのかが分からない

HolderとかRepository作るとどうしてもシングルトンになっちゃう
誰か助けて

**デフォルトの名無しさん** · 2017/11/07(火) 08:06:23.75

シングルトンの何がいけないのかをわかっていれば別に使ってもいいんじゃないか？
と思うんだが

**デフォルトの名無しさん** · 2017/11/08(水) 03:27:16.05

staticでおk

**デフォルトの名無しさん** · 2017/11/10(金) 09:56:08.91

内部ノード数 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)) と書くのはおかしいのではないでしょうか？

**デフォルトの名無しさん** · 2017/11/10(金) 12:02:03.17

メッセージキューイングって
Commandパターンで実装するで合ってる？

**デフォルトの名無しさん** · 2017/11/12(日) 17:56:18.04

>>686
>>2^(h-1) - 1 ≦ n ≦ 2^(2*h-1) - 1 ・・・(1)
>>よって、 h = O(log(n)) ・・・(2)

一見すると正しそうに見えるけど、どっちがどうおかしいと？

**デフォルトの名無しさん** · 2017/11/12(日) 19:28:20.81

h が n の関数ではないにもかかわらず

h ∈ O(log(n))

と書いているのがナンセンスです。

**デフォルトの名無しさん** · 2017/11/12(日) 19:46:50.82

>>689
nとhの関係は(1)で示されているんじゃね？
不等式を変形すれば良いのでは？

**デフォルトの名無しさん** · 2017/11/12(日) 20:23:32.92

n から h は一意的に決まりません。

よって、

h は n の関数ではありません。

**デフォルトの名無しさん** · 2017/11/12(日) 21:38:49.52

>>691
(1)より一意に決まらなくても計算量は同じでしょ？

**デフォルトの名無しさん** · 2017/11/13(月) 18:01:47.14

＞もちろん、　O(log(n)) の左辺には n の関数が来るきまりです。
ここの時点でおかしい

**デフォルトの名無しさん** · 2017/11/13(月) 18:49:03.12

>>693

何がおかしいのでしょうか？

**デフォルトの名無しさん** · 2017/11/14(火) 16:22:50.14

抽象メソッドしか定義されない型のことを
「インタフェース」ってネーミングセンスは頭おかしいんじゃないの？
インタフェースって言ったら通常「UI」とか外部の窓口になったり、
外部デバイスとの接続ポイントになるコネクタのことを言うじゃん。
オブジェクトの型のことを「インタフェース」なんて言ったら誤解を招くだろ。

**デフォルトの名無しさん** · 2017/11/14(火) 16:49:12.95

>>695
interfaceには境界面とか接点の意味がある

クラスが持つ他との接点の意味で合ってる

**デフォルトの名無しさん** · 2017/11/14(火) 18:46:26.43

外部の窓口になったり、外部デバイスとの接続ポイントになるのが抽象メソッドだから。
つまりそれしか定義されてないということは、インターフェースそのものと言っていいだろう。

**デフォルトの名無しさん** · 2017/11/14(火) 20:12:16.44

デザパタスキル、エンベッデイドスキルなんやかや言うが、みんな大事な部分は閃きなんだがなぁ・・・
作曲と同じ。　閃き・・・　とどのつまり、神が書かせているという事。
そこを理解できない限り、そのプログラマーは聖職では無い。

**デフォルトの名無しさん** · 2017/11/15(水) 13:14:29.24

神などと妄想するようになったら科学の全否定の始まり。無知が故の過ち。

**デフォルトの名無しさん** · 2017/11/18(土) 18:23:02.44

神「共通化せよ――」
僕「はい」
神「ごめん間違えた――」
僕「うわぁぁああぁああ！！！」

**デフォルトの名無しさん** · 2017/11/18(土) 18:29:25.85

神とは強いて言えば可能性

**デフォルトの名無しさん** · 2017/11/19(日) 23:12:44.83

以下で定義される写像 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 関数の逆関数と呼ぶのでしょうか？

**デフォルトの名無しさん** · 2017/11/20(月) 20:37:12.88

courseraのセジウィックとウエインの講義を受講しています。

プログラミングの課題のチェックが超厳しいですね。

'if' is not followed by whitespace.

「if」の後ろにスペースを入れないといけないなんて初めて聞きました。
そんなことまで強制されたらたまりませんね。

**デフォルトの名無しさん** · 2017/11/20(月) 20:40:14.03

大概のプロジェクトで採用されてるスタイルだから従っとけ
スペース軽視するやつ多すぎ

**デフォルトの名無しさん** · 2017/11/20(月) 20:43:51.90

>>703
K&R2 に従っておけば文句が来ることはない
if ()
while ()
for ()

**デフォルトの名無しさん** · 2017/11/20(月) 20:54:20.19

フオーマッタの設定の指定とか無いの？

**デフォルトの名無しさん** · 2017/11/20(月) 23:10:14.23

一般的なコーディングルールには従ったほうがよい
最近の言語環境では放っておいてもツッコミ入れてくれたりもするが

**デフォルトの名無しさん** · 2017/11/21(火) 07:03:23.42

業務システムでオブジェクト指向不要って意見はどう思いますか
大抵スパゲティークエリになってる印象ですが

**デフォルトの名無しさん** · 2017/11/21(火) 07:13:27.16

途中からオブジェクト指向混ぜられても困るだろ
実行効率や記述効率は悪くたって別に構わないのだから（ここわかってない人多し）、プロジェクトに来た全員が理解利用できる書き方が最優先

無論技術的にも業務的にもうんこだが、そこを追求すべき場所ではないところで勝手に追及を始めるのはそれこそうんこのやること
ゼロからオーバーホールを提案してもよいが最後まで自己責任で看取れ

**デフォルトの名無しさん** · 2017/11/21(火) 17:43:16.86

>>709
サブクエリ五重の塔を見て上長にキツいと報告したら世界にはバベルの塔がいっぱいあるのに根をあげるなと叱られました

せめて何をしたいのかドキュメント欲しいと言ったらコードが全てだとも言われました

IT業界の厳しさを知りました

**デフォルトの名無しさん** · 2017/11/21(火) 18:14:34.60

>>710
マ板にどうぞ

**デフォルトの名無しさん** · 2017/11/22(水) 09:23:31.55

courseraのセジウィックとウエインの講義の最初の課題であるパーコレーションだけど
backwashを防ぐにはどうすればいいんですか？

**デフォルトの名無しさん** · 2017/11/22(水) 10:42:20.23

あ、分かりました。

virtual topにはつなぐがvirtual bottomにはつながないUF
virtual topにもvirtual bottomにもつなぐUF

を使えばいいんですね。

**デフォルトの名無しさん** · 2017/11/22(水) 10:51:20.09

成績が100点満点中97点になりました。

**デフォルトの名無しさん** · 2017/11/22(水) 10:52:40.54

成績が100点満点中98点になりました。

**デフォルトの名無しさん** · 2017/11/22(水) 11:48:25.03

今日のNG ID:milfaijK

**デフォルトの名無しさん** · 2017/11/22(水) 15:34:31.81

ついに、成績が100点満点中100点になりました。

https://imgur.com/apwKZnf.jpg

**デフォルトの名無しさん** · 2017/11/22(水) 15:35:42.67

快挙ですね。

**デフォルトの名無しさん** · 2017/11/23(木) 12:04:48.38

デザインパターンで規定されるいろいろなクラスがあるけど
これらのクラスはそれぞれレイヤー化アーキテクチャのどこに
属すのか知りたい。
たとえばStateパターンがあった場合に、
・<<interface>>State
・ConcreteState x n
・Context
があったとき、

これらは、クラスを配置する場所的に
・プレゼンテーション層(UI層)
・App層
・サービス層
・ビジネスロジック層
・パーシステンス層
のどこの層として配置すればいいのか

**デフォルトの名無しさん** · 2017/11/23(木) 12:18:16.35

> デザインパターンで規定されるいろいろなクラスがあるけど
> これらのクラスはそれぞれレイヤー化アーキテクチャのどこに
> 属すのか知りたい。

デザパタはレイヤ化アーキテクチャに属すものだという考え方が謎なんだけど

**デフォルトの名無しさん** · 2017/11/23(木) 12:18:26.01

>>719
どの層にも配置していいんじゃね

その層の機能とかを実現するのにそのデザインパターンが必要なら使えばいいのではないか

レイヤーとデザインパターンは独立に組み合わせ可能と思う

**デフォルトの名無しさん** · 2017/11/23(木) 13:43:59.34

>>719
これでも読めよ

J2EEデザインパターン
https://www.amazon.co.jp/dp/4873111781/

**デフォルトの名無しさん** · 2017/11/25(土) 15:28:17.03

java用語発表されてもなー

**デフォルトの名無しさん** · 2017/11/27(月) 07:16:56.92

デザパタを適用したクラスがどのレイヤにあっても構わんのじゃ無いか
定石があってもフレームワークごと違うから説明無理だと思う

**デフォルトの名無しさん** · 2017/11/28(火) 09:02:37.93

1以上1000以下の整数からなる集合の部分集合で、
その任意の異なる2元 x, y をとったとき、
「x は y を割り切らず、 y も x を割り切らない」
という性質をもつものを考える。

そのような部分集合の中で元の数が最大になるような
集合の元の数を求めよ。

**デフォルトの名無しさん** · 2017/11/28(火) 09:32:48.27

めっちゃ勘だが、334から666と、667以上の奇数でどうだろうか

**デフォルトの名無しさん** · 2017/11/28(火) 11:34:19.17

答えは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)

という二つの整数が含まれる。

この二つの整数は一方が他方を割り切る。

**デフォルトの名無しさん** · 2017/11/28(火) 12:05:52.85

どっかから問題と回答を拾ってきてドヤ顔してる人ってなんなの？

**デフォルトの名無しさん** · 2017/11/28(火) 14:07:31.97

>>727
何をしているのかちゃんと理解したいのですが、
m や n は実数ですか？

**デフォルトの名無しさん** · 2017/11/28(火) 15:55:11.56

>>729
>>727が言葉が足りてないのは確かだが、もうちょっと数学のセンス磨こうぜ

**デフォルトの名無しさん** · 2017/11/28(火) 17:12:15.85

>>730
n=0 にして、m=0, 1, 2 ...
n=1 にして、m=0, 1, 2 ...
...
とやって確かめたら、なんとなく自然数を網羅できそうなのは確認できました。

ただ、本当に網羅できるのか証明はまだできてません。

これ以上はスレチも甚だしいので、独りで頑張ってみます。

流れぶった切ってすみません。
>>725 さん、どうぞ続けてください。

**デフォルトの名無しさん** · 2017/11/28(火) 17:15:22.43

>>729

整数を 2 で割れるだけ割ると 2^n * (2*m + 1) の形になります。

例：

120 = 2^3 * 15 = 2^3 * (2*7 + 1)

この場合、 n = 3, m = 7 です。

**デフォルトの名無しさん** · 2017/11/28(火) 17:16:45.10

2^n * 奇数

です。

**デフォルトの名無しさん** · 2017/11/28(火) 17:26:27.93

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)

**デフォルトの名無しさん** · 2017/11/28(火) 17:58:11.47

500以下なのはわかった。500ある例>>726も見つかった。
で、一般に1からNのとき、何個になるのよ？

**デフォルトの名無しさん** · 2017/11/28(火) 19:31:53.85

>>726

{501, 502, …, 1000} でもOKですね。

**デフォルトの名無しさん** · 2017/11/28(火) 19:37:23.97

>>735

ceiling(n/2)

ではないでしょうか？

**デフォルトの名無しさん** · 2017/11/28(火) 19:54:30.86

あんまり面白くない結果だね

**デフォルトの名無しさん** · 2017/11/30(木) 18:59:28.31

セジウィックとウエインのcourseraのオンライン講義を聴講しています。

java.util.List
java.util.Stack
java.util.Queue

は最低だそうですね。

Best practices: Use our implementations of Stack, Queue, and Bag.

だそうです。

**デフォルトの名無しさん** · 2017/12/02(土) 11:57:41.11

最近傍探索で、最も近いものが複数個あった場合、どうするのが自然ですか？

また、k近傍探索でも、クエリからk番目に近いものが複数あった場合、どうするのが自然ですか？

**デフォルトの名無しさん** · 2017/12/02(土) 12:30:23.76

セジウィックとウエインのcourseraのオンライン講義を聴講しています。

なんかやけに課題が厳しくないですか？

**デフォルトの名無しさん** · 2017/12/02(土) 13:12:04.17

セジウィックとウエインのcourseraのオンライン講義Algorithms Part 1のWeek 2の課題、できた人いますか？

**デフォルトの名無しさん** · 2017/12/02(土) 17:04:18.29

今日のNG ID:LweVlrmz

**デフォルトの名無しさん** · 2017/12/02(土) 20:12:18.77

courseraのセジウィックとウエインの講義を聴講している人はいますか？

**デフォルトの名無しさん** · 2017/12/04(月) 13:54:02.89

>>740
好きなようにするのが自然

**デフォルトの名無しさん** · 2017/12/05(火) 09:10:03.39

↓この仕様の RandomizedQueue の実装できる人いますか？

http://coursera.cs.princeton.edu/algs4/assignments/queues.html

**デフォルトの名無しさん** · 2017/12/05(火) 09:40:42.14

>>746
宿題なら自分でやれ
そうでないなら読むのめんどくさいから要約しろ

**デフォルトの名無しさん** · 2017/12/05(火) 09:45:48.47

松坂君につきスルー推奨

**デフォルトの名無しさん** · 2017/12/05(火) 12:21:40.49

あ、仕様Memory量の見積を勘違いしていました。

できそうですね。

Item 型のデータを格納する Linked List
と
Linked List の各要素への参照を格納する Item[] 型の
配列を用意すれば実現できますね。

**デフォルトの名無しさん** · 2017/12/05(火) 12:25:30.33

あ、でも Item[] 型の配列を ResizingArray で実現したとしても、
常に、Memoryの制限である 48*n + 192 bytes というのを満たすのは
無理ですね。

どうすればいいんですかね？

もう少しだけメモリの制限が緩ければ実現可能ですが。

**デフォルトの名無しさん** · 2017/12/05(火) 12:30:24.08

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.

**デフォルトの名無しさん** · 2017/12/05(火) 13:24:03.96

あ、なんだ

簡単でしたね。

Item[] 型の Resizing Array を使えば、

メモリ使用量～ 8*n

だから、4倍くらいメモリを無駄に使っても

48*n を超えませんね。