データ構造,アルゴリズム,デザインパターン総合ｽﾚ 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/06/20(月) 00:15:53.04

>>12
マジかよ

**デフォルトの名無しさん** · 2016/06/20(月) 00:57:04.30

>>12
> ライブラリ駆使して、なんとかすることが求められている人間にはこんなものは不要

ライブラリを駆使するのが今のプログラマに求められている技術だからな。

MITがSICPを教えなくなった理由
https://ezoeryou.github.io/blog/article/2016-05-05-sicp.html
> 今日では、状況が変わっている。今のエンジニアは、自分が完全に理解していない複雑なハードウェアの
> ためのコードを日常的に書いている（そして、大抵の場合、企業秘密により完全に理解するのは不可能である）。
> ソフトウェアでも状況は同じだ。プログラミング環境は、多大な機能を提供する巨大なライブラリ群の集合として存在している。
> Sussmanの今日の生徒は、その時間の大半を、ライブラリのマニュアルを読み、どのように組み合わせれば目的が
> 達成できるのかを把握することに費やしている。Sussman曰く、今日のプログラミングは、「より科学に近い。
> ライブラリを持ち寄って、つっつき回すのだ。プログラムを書くには、突っつき回して、どのように動作するかを観察する。
> そして、「目的を達成するために改造できるか」と考えるのだ」。SICPの「合成による解析」という物の見方である、
> 小さな、単純な部品を組み合わせて大きなシステムを作るということは、もはや今日の状況にそぐわなくなった。
> 今や、我々のプログラミングはつっつき回すことで行われている。
>
> なぜPythonを選んだかということについて、Sussmanは、"late binding"に決定したと冗談を飛ばした。
> Pythonには大量のライブラリがあり、教育者の様々な実習に使いやすい（たとえば、ロボットを制御するソフトウェアを書くなど）

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

HaskellやSchemeの利点は？
少なくとも、分かりにくいよね。

**デフォルトの名無しさん** · 2016/06/20(月) 08:05:44.62

オブジェクト指向程ではないけどな

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

エンジニアの選定時の足切りにちょうどいいよ

**デフォルトの名無しさん** · 2016/06/20(月) 18:11:51.85

その基準で剪定できるのはかなり恵まれてる気が

**デフォルトの名無しさん** · 2016/06/20(月) 18:23:24.04

>>14
>今日のプログラミングは、「より科学に近い。

ここは変だな
「より工学に近い。」
というなら判るが

**デフォルトの名無しさん** · 2016/06/20(月) 18:31:26.30

SICPをプログラミング初学者に教えるというのは確かに異様だよね。

やっとまともになったというだけの話。

**デフォルトの名無しさん** · 2016/06/20(月) 18:35:05.72

コンピュータサイエンスの中でアルゴリズムとデータ構造ってどれくらい重要な科目なの？

**デフォルトの名無しさん** · 2016/06/20(月) 18:50:31.57

アルゴリズム + データ構造 = プログラム。
ということは。
プログラムの占める割合と等価なのでは。

**デフォルトの名無しさん** · 2016/06/20(月) 18:52:50.90

なんか計算の理論とかのほうが上みたいな感じじゃない？

**デフォルトの名無しさん** · 2016/06/20(月) 18:53:47.25

コンピュータサイエンスで最も重要な科目は、コンパイラとかOS？

**デフォルトの名無しさん** · 2016/06/20(月) 18:53:55.59

自演乙

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

>>18
この道３０年の修業でようやく一人前

**デフォルトの名無しさん** · 2016/06/20(月) 20:44:30.75

寿司職人乙

**デフォルトの名無しさん** · 2016/06/20(月) 20:58:16.94

schemeやらないとアルゴリズムとデータ構造を組み立てるってことがどういうことなのか、コードでわからないだろうな

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

>>28
javaでよくない？

**デフォルトの名無しさん** · 2016/06/20(月) 21:24:25.76

javaでconsを表現するときにどうすればいいか知ってますか?

**デフォルトの名無しさん** · 2016/06/20(月) 21:29:28.84

>>28

アルゴリズムとデータ構造の本に疑似コードが載っていることがあるけど、
Scheme風に書かれていることなど決してない。

**デフォルトの名無しさん** · 2016/06/20(月) 21:47:01.99

>>27
植木職人

**デフォルトの名無しさん** · 2016/06/20(月) 22:10:02.53

>>18
未経験でも理解出来るならとりあえず地雷の可能性は下がる

**デフォルトの名無しさん** · 2016/06/20(月) 22:22:55.57

恵まれてない会社だと全員切る羽目になるって話だろｗ

**デフォルトの名無しさん** · 2016/06/20(月) 22:43:48.30

31
そのSICPはschemeでかかれているわけで
昨今のライブラリ重視の観点からいえば、javaがいいっていうのはとおるけど、アルゴリズムかくのにjavaがいいってのは、センスないというか、お手入れ大好きなんだろうな

**デフォルトの名無しさん** · 2016/06/20(月) 22:49:30.47

引用できないやつに言われると

**デフォルトの名無しさん** · 2016/06/20(月) 22:50:33.93

スマホで>>うつのめんどいんだよ

**デフォルトの名無しさん** · 2016/06/22(水) 04:43:48.40

日立、新型半導体コンピュータの実用化に向けた前処理アルゴリズムを開発
http://news.mynavi.jp/news/2016/06/21/172/

新型半導体コンピュータの実用化に向けて、
要素間の複雑なつながりを規則的な構造に自動変換する前処理アルゴリズムを開発
http://www.hitachi.co.jp/New/cnews/month/2016/06/0621a.html

関連記事
日立、量子コンピュータに匹敵する性能の室温動作の新型コンピュータを試作
http://news.mynavi.jp/news/2015/02/23/121/

**デフォルトの名無しさん** · 2016/06/22(水) 07:14:40.76

日本人の書いたアルゴリズムとデータ構造の本でまともなのって1冊もないの？

**デフォルトの名無しさん** · 2016/06/22(水) 07:53:05.39

>>39
まともとは？

**デフォルトの名無しさん** · 2016/06/22(水) 07:59:50.23

日本人の書いた本は薄っぺらくて説明も十分ではなく厳密でもなく網羅性もない本ばかりに思う。

**デフォルトの名無しさん** · 2016/06/22(水) 08:00:26.15

杉原厚吉の本は特にひどいと思った。

**デフォルトの名無しさん** · 2016/06/22(水) 11:07:15.76

>>39
そのものズバリでアルゴリズムとデータ構造という本が岩波から出てる

**デフォルトの名無しさん** · 2016/06/22(水) 12:53:15.55

まともな本とは?
argolythm introduction?
knuth本?
どっちも使い物にならないが

**デフォルトの名無しさん** · 2016/06/22(水) 13:50:41.86

>>44
1単語に3箇所もミス入れるなよ

**デフォルトの名無しさん** · 2016/06/22(水) 14:13:53.39

根幹のタームの綴りも知らん半可通に何を教われというのか

**デフォルトの名無しさん** · 2016/06/22(水) 14:17:48.79

3ヶ所もあると誤り訂正も利かないんじゃまいか

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

バースト発生させんな

**デフォルトの名無しさん** · 2016/06/22(水) 15:16:40.79

????????????

**デフォルトの名無しさん** · 2016/06/22(水) 21:44:16.49

>>44
そんな頭じゃ使いものにならんのも頷けるわ

**デフォルトの名無しさん** · 2016/06/22(水) 22:23:26.91

こんな揚げ足とりの老害から何を学べと?

**デフォルトの名無しさん** · 2016/06/22(水) 22:52:24.12

馬鹿の自己紹介されても困る

**デフォルトの名無しさん** · 2016/06/24(金) 11:47:43.21

>>19
は？変なのはお前だ
プログラミングは最初から工学的だろ何言ってんだ？

そもそもお前は工学と科学を理解してないから可笑しなことを言うんだ

**デフォルトの名無しさん** · 2016/07/15(金) 12:10:18.78

何ヶ月か前に近代科学社に電話でセジウィックアルゴリズムの第四版の翻訳の予定はありますか、と訊いてみたが無いって返事だったんだよな
書いて欲しいんだがな

**デフォルトの名無しさん** · 2016/07/16(土) 08:00:53.05

アルゴリズムさえ知ってりゃ動くプログラムは書けるから他は優先度低いと考えてた結果
データ構造すら分からない化石プログラマになってしまった

今必死にデータ構造とデザインパターン勉強中だけど、わかってくると楽しいね

アルゴリズムみたいにオーダー詰める楽しみはないけど…

**デフォルトの名無しさん** · 2016/07/18(月) 09:37:52.19

両方大事だろ。
データ構造が整理されてないとアルゴリズムも煩雑になるし。

**デフォルトの名無しさん** · 2016/07/21(木) 23:06:49.37

vEB木の「僕の考えた最強のデータ構造」感が大好きなんだが誰か共感してくれる人いる？

**デフォルトの名無しさん** · 2016/07/22(金) 07:32:19.08

データ構造の基本は、以下の2つと、他にはハッシュがある

A → B → C → D
のように、メモリ上の位置がバラバラなオブジェクトを、リンクでつないでいくものと、
(シーケンシャルアクセス)

ABCD
のように、連続したメモリ位置に、オブジェクトやオブジェクトの参照が確保されていて、
単純な計算式で、各オブジェクトにアクセスできるもの(ランダムアクセス)

シーケンシャルは、リンクをたどるから、アクセスには時間がかかるけど、
要素の追加・削除では、リンクを付け替えるだけで、要素をずらさないから速い

**デフォルトの名無しさん** · 2016/07/26(火) 06:56:53.95

letの時代がもうすぐそこまで来ているよね

**デフォルトの名無しさん** · 2016/07/26(火) 14:27:18.12

let
-------
　λ

**スモモンガー** · 2016/09/23(金) 22:08:49.88

どうも、お久しぶりです。スモモンガーです。（誰って感じだと思いますがそれで結構です）
以前紹介したアルゴリズムですが、結局全然応用分野は見つかっておりません。
前回は画像処理分野を中心に解説しましたが今回はより簡単に実装ができる
探索分野に絞って動画を作ってみました。つたない動画で大変申し訳ございませんが
見てみていただけたら幸いです。特許などは取得しておりませんのでどうかご自由に
お使いください。長文失礼いたします。痛いのは承知なのですが応用分野を必死に
探しているのでどうかご協力よろしくお願いします。

https://youtu.be/5m3kPHO2w98

以上、どうぞよろしくお願いします

**デフォルトの名無しさん** · 2016/09/23(金) 22:16:41.76

誰だ

**デフォルトの名無しさん** · 2016/09/23(金) 22:42:52.63

帰れ

**デフォルトの名無しさん** · 2016/09/24(土) 09:14:59.70

>>61
最初の数分見ましたが..

1) 何の探索なの？最初は「探索」と聞いて「グラフかな？」とか思ったけど配列みたいだし、最初に想定される入力を明確にした方がいいですね

2) プレゼンが文章を読み上げてるだけでイメージが湧きにくい
1,4,10,20,25 …
の例ではイラストを用いた方がわかりやすいと思います

3) Kangaroo Method とはのスライドでデータがソートされていて、キーの差が (中略) バイナリサーチと同等の効率を .. とありますが、例では入力が完全にソートされているようです。これなら最初からバイナリサーチを使います

また、11m10s くらいのところで「Sinカーブは整ってる」とありますが、「整っている」の定義がよくわかりません。その後の例も見ましたが、どのくらいまで途中に想定されていないデータが混じっていても許容範囲なのかが不明です

4) 先に長所短所のスライドを持ってきて、擬似コードとオーダーも明記し、「一部ソートされてなくても O(logn) で探索できます」みたいなのを書いて、見ている人を「それならもうちょっと続きを見てみようか」みたいな気にさせられればもっといいですね

以上、感想でした

**デフォルトの名無しさん** · 2016/09/24(土) 09:32:41.92

64さん。ありがとうございます。私はこういうスライドを作る機会があまりないのでこんな形になってしまいました。
実は整っているという抽象的な単語を使っていますが、実は定量的にこれを測る方法はまだ思いついていません。
そのほかのご指摘はその通りだと思います。
貴重なご意見ありがとうございます

**デフォルトの名無しさん** · 2016/09/24(土) 09:49:16.96

動画見るの面倒だから3行で説明して

**デフォルトの名無しさん** · 2016/09/24(土) 09:53:53.39

ご
み
だ

**デフォルトの名無しさん** · 2016/09/24(土) 09:55:26.18

>>66
まず目的のキーと現在探索中のキーの差をとる。
それを隣接するキーの最大値で割る。
その値だけ進む。

まあ、原理は単純なアルゴリズムです

**デフォルトの名無しさん** · 2016/09/24(土) 10:46:59.06

>隣接するキーの最大値

これをあらかじめ求めておかなきゃならんってのが一番のネックだな。
一般のデータに対する探索だと、バイナリサーチと比較したメリットと言っていたものの大半が消し飛んでしまう。

**デフォルトの名無しさん** · 2016/09/24(土) 10:49:01.89

>>61
印象としては
1. 要素間の差の最大値を求めるのに線形時間
2. 各要素の値の差が一定でないと性能を発揮しない（最大値を求めるのも含め）
3. 探索の最悪時間が線形時間、恐らく平均も線形時間
4. ソートされていなくても探索可能な条件が不明瞭
5. データの内容に探索コストが大きく左右される

例えば
1 2 4 9 15 24 100 120 1002 1225
とあった時、差の最大値は
1002-120=882
1002を探索すると
1002-1=1001, 1001/882=1
1002-2=1000, 1000/882=1
1002-4=998, 998/882=1
1002-9=993, 993/882=1
...
と線形時間になる（やり方あってるよね？）
演算している分、比較だけの線形探索より処理速度が遅くなる

**デフォルトの名無しさん** · 2016/09/24(土) 11:09:23.58

>>69
>>70
確かにキーの最大値を求めるのは線形時間かかります。なのであらかじめ、隣接するキーの最大値が分かっているデータに使用可能です。
探索の最悪時間は線形時間ですが、平均時間はlogのオーダーになるのではないでしょうか。私が不勉強なもので理論的には、示めせませんが多分logのオーダーになると思います。
ソートしなくても探索できるのは差の絶対値を取るからです。動画に入れるのを忘れました。すいません。
計算についてはそれであっています。わざわざご指摘ありがとうございます

**デフォルトの名無しさん** · 2016/09/25(日) 01:17:16.51

>>71
上でも指摘されているが整っているの定義が不明
二分探査の場合は、存在しないこともlog n で確認可能だが、この手法は整っているの定義次第では存在しない者の確認が非常に時間かかる（ソートされている場合は存在するものと同等だが、そうすると二分探索よりも利点が少なくなる）
平均計算量を求めるのはちと難しそうだけど、格納される値の値域に依存するかな
たぶん、log n 程良くはないと思う

**デフォルトの名無しさん** · 2016/09/25(日) 09:29:52.06

>>72
ご指摘ありがとうございます。確かに整っているの定義ができていないのが一番の難点ですよね。いつか勉強して考えたいと思います

**デフォルトの名無しさん** · 2016/09/25(日) 12:26:29.96

>>67
ごめん
みたけど
だめだこりゃ

**デフォルトの名無しさん** · 2016/09/25(日) 12:52:11.14

>>71
各要素間の差が一定であればO(1)、当たり前だけど、これは計算で求まる
各要素間の差の分布数が要素数に近づき、尚且つその落差が激しい場合
著しく線形時間になる

で、探索したい数値と差の最大値の商が1だった場合
その探索したい数値がある位置以下の数値探索はO(n)になる
データ列の後半に行くほど1回の演算で要素をステップする数が増えるけど
その移動は微々たるもの
データ列の内容に左右されることを差っ引いても、O(log n)からは程遠いと思う
詳しい計算は出来ないが、これを線形時間としても無理はないと思う

参考として
0 1 3 6 10 15 21 28 36 45
このデータ列では、15以下の探索はO(n)、
21は5回、28は4回、36は4回、45は3回の演算

結論として
このアルゴリズムの最大の欠点は差の最大値が必要な事を含めて
データ列の内容に左右されてしまうことだな
この手のアルゴリズムはデータの外側にあるべきだな

**デフォルトの名無しさん** · 2016/09/25(日) 14:20:01.83

>>74
８８

**デフォルトの名無しさん** · 2016/09/26(月) 13:42:01.27

>>61
すもモンがnewton法をガチで知らないのであればnewton法をまず勉強するべき
カンガルーの敵はバイナリではなくnewtonだ

**スモモンガー** · 2016/09/26(月) 20:32:40.67

確かにデータ間の差に一様離散分布を使ったのは公平ではなかったです。
なので、データを完全にランダムにして調べてみました。
データはCのrand()%1000000で10000個生成しソートして、
探索の時配列のうちランダムな値を探すキーとし間を線形探索、カンガルー法
バイナリサーチで100回比べてみました。
その結果線形探索では平均比較回数約4963回最大比較回数は9972回でした
カンガルー法は平均比較回数約70回　最大比較回数は111回でした。
バイナリーサーチはやはり一番はやく、平均比較回数約12回、最大比較回数は14回でした
皆さんがご指摘の通りやはりバイナリーサーチが一番はやいようです。
ただ、例えばKMP法が逆行がないから使われているようにカンガルー法も逆行がないので
使うことはできないでしょうか？もし、とんちんかんなこと言ってたらすいません。

**デフォルトの名無しさん** · 2016/09/26(月) 20:37:55.45

>>74
www確かにそうかもしれませんね。
>>77
一応私はニュートン法については知っています。Newton法は求める関数の微分した値を
しっていなければならないとおもうのですが、現実の探索だと関数が微分できないことも
多いかと思います。ちょっと、私が使った例が悪くてsinカーブや円を使ったのがよく
なかったのかもしれません。整っていてソートされていないデータとして扱いやすかったので
sin関数を使ったのであってとくにデータが微分可能である必要はありません。円と
Y切片の交点も中学生でも二次方程式ときゃいいのでもっと簡単にできますが、本来は
多角形とさまざまな図形の交点を探るアルゴリズムです。円を使ったのは例をわかりやすく
したかったからです。

**デフォルトの名無しさん** · 2016/10/16(日) 18:51:48.49

状態遷移ってどういうステータス持てばいいの？

A と B のステータスがあって、お互いが切り替わるのに n秒かかる
切り替わりに失敗したら切り替えをリトライする
AはBになろうとし、BはAになろうとする

というとき、A と B のほかに AからBになるのを待ってる状態と
BからAになるを待ってる状態の 2つがさらに状態として必要？
過渡状態も状態？

**デフォルトの名無しさん** · 2016/10/17(月) 07:56:46.27

>>80
システムの設計次第。
切り替え中、待ち中が状態として存在するのならプログラムでも状態にすればいい

**デフォルトの名無しさん** · 2016/10/17(月) 15:43:18.44

>>81
そりゃそうだけど
状態がn個あると過渡状態がたくさんになるのは
辛い

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

現在の状態と次の状態のペアにすれば？

**デフォルトの名無しさん** · 2016/10/17(月) 21:23:44.83

辛かろうが状態が存在するのならしょうがあるまい。
あるいは遷移をアトミックにして遷移中状態そのものを無くすか、遷移中の動作を共通化
できるなら遷移先をパラメータ化して「*への遷移中」という1状態にしてしまうとか。

**デフォルトの名無しさん** · 2016/10/17(月) 23:34:18.88

>>82には無理ということで

**デフォルトの名無しさん** · 2016/11/05(土) 20:41:10.12

ポリモーフィックなクラスの相互作用において特定の型の組み合わせの場合のみ処理を特殊化したい場合はどうすればいいのだろう？

x = xFactory.create(...);
y = yFactory.create(...);

if(x.typeCode() == X.Foo && y.typeCode() == Y.Hoge)
executeSpecial((Foo) x, (Hoge) y);
else if (...)
...
else
executeNormal(x, y);

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

デザインパターンを使って実装すると、年長プログラマーから、またこんなことしやがって的な拒否反応が帰ってくるんだがどうすれば

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

排除する他道は無い。

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

転職しろ

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

若者で組合(または派閥)を創る

**デフォルトの名無しさん** · 2016/12/13(火) 08:14:05.45

>>87 がどんなコードを書いたかも分からんのに

**デフォルトの名無しさん** · 2016/12/13(火) 18:53:42.04

下手くそがデザインパターンとか使うと逆にこんがらがるからなぁ
老害とどっこいどっこいだろ

**デフォルトの名無しさん** · 2016/12/13(火) 21:32:18.83

マルチスレッドで、なんの考えもなくオブザーバー使いまくられて、データ破壊しまくられた時には、本気で殺意を抱いたよ

**デフォルトの名無しさん** · 2016/12/16(金) 15:12:11.72

『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』

の優先度付きキューについてのプログラムについて質問です。

p.241の heapIncreaseKey(A, i, key) という関数内で、

「if key < A[i] エラー：新しいキーは現在のキーより小さい」

というのがあります。

これがなぜ必要なのかが分かりません。

insert(key) を見れば分かるように、この本の使われ方では、
key < A[i] になることは決してありません。

よろしくお願いします。

**デフォルトの名無しさん** · 2016/12/16(金) 15:34:53.22

assertionじゃね

**デフォルトの名無しさん** · 2016/12/17(土) 16:05:18.68

完成形をいきなり見てると不思議に思うよね。
でも実際には作成中のバグを考慮して、最初にチェックを入れておくもんなんだよね。
まあ、一言で言えばassertなんだけど。

ただ、作業やデバッグ用には必須であっても、その本の例示として必要か？と言われれば、確かにいらない気がする。

**デフォルトの名無しさん** · 2016/12/17(土) 16:09:26.93

>>95-96

『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』の参考文献に
挙げられている『アルゴリズムイントロダクション』を見てみたら、全く同じプログラム
が載っていました。

完全にパクっていますね。

>>96
デバッグ用にどうして必要なのかが分かりません。

『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』はお持ちでしょうか？
もし、お持ちでないようでしたら該当箇所の画像をアップロードします。

**デフォルトの名無しさん** · 2016/12/17(土) 16:23:27.88

>>94

念のため、該当箇所の画像をアップロードさせていただきます。
読めば読むほど意味不明です。

http://imgur.com/zKVWzAJ.jpg
http://imgur.com/owa8NkX.jpg
http://imgur.com/NmCczss.jpg

**デフォルトの名無しさん** · 2016/12/17(土) 16:42:25.50

>>97
参考文献ならパクってるとは言わない

**デフォルトの名無しさん** · 2016/12/17(土) 16:43:27.67

>>98
こういうのが本当のパクり
訴えられたら負ける

**デフォルトの名無しさん** · 2016/12/17(土) 18:12:28.79

>>97
他の本も読んでみるとわかると思うけど、プライオリティキューを二分木ヒープで実装するのは定番で、どの本でも大体同じことが書いてある

**デフォルトの名無しさん** · 2016/12/17(土) 19:29:55.59

>>98

「if key < A[i] エラー：新しいキーは現在のキーより小さい」

というのが、デバッグ用であるとは思えないのですが、これは一体何なんでしょうか？

heapIncreaseKey(A, i, key) を何か別の用途に使う場合があって、そのときに必要に
なるのならば納得しますが。

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

>>101

「if key < A[i] エラー：新しいキーは現在のキーより小さい」

という意味不明のコードも『アルゴリズムイントロダクション』のプログラムには
書いてあります。

こんな余計なコードは普通は入れないと思います。

完全にパクりだと思います。

**デフォルトの名無しさん** · 2016/12/17(土) 19:35:00.61

>>103
参考文献に書いてあるんだからパクリも糞も無い罠
参考文献に書き漏れたら小保方さんみたいに突っ込まれるが

**デフォルトの名無しさん** · 2016/12/17(土) 19:35:29.11

『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』の
他のプログラムもおそらくすべて『アルゴリズムイントロダクション』の
プログラムをそのまま使っています。

恥を知れと言いたいです。

**デフォルトの名無しさん** · 2016/12/17(土) 19:36:34.73

参考文献に文献を挙げれば何でも許されるということはないと思いますが。

**デフォルトの名無しさん** · 2016/12/17(土) 19:39:42.80

『アルゴリズムイントロダクション』のほうをよく読んでいませんが、

「if key < A[i] エラー：新しいキーは現在のキーより小さい」

というのも『アルゴリズムイントロダクション』のほうでは意味があるのかもしれません。

それをそのまま何も考えずにコピペしたために、意味不明なことになっているのかも
しれません。

>>98

を見て、誰か納得のいく説明ができるでしょうか？

意味不明としか言えないかと思います。

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

『アルゴリズムイントロダクション』のほうをよく読んでいませんが、
『アルゴリズムイントロダクション』のほうもまたどっか別の本からのパクリの悪寒。

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

"error: heap underflow" でググるといっぱい出てくる

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

ID:GDWdcO6h は何をそんなに怒ってるの？
問題が解けなくてイライラしてるだけ？

どんな本も参考文献があり、どんなアルゴリズム、データ構造も元をたどれば最初に「ヒープで実装すればうまく行くぞ！」と発見した人の論文があるはず

新しい本を書くときは参考文献よりもわかりやすくなるように、説明やイラスト、擬似コードを変えたり、あるいは同じものを流用することもあるだろう

**デフォルトの名無しさん** · 2016/12/17(土) 20:55:04.47

disるのがはやってるらしい

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

プログラミングコンテスト攻略のための、
アルゴリズムとデータ構造、渡部有隆(わたのべゆたか)、2015
Ozy(協力), 秋葉拓哉(協力)

Aizu Online Judge(AOJ、会津大学)

プログラミング・コンテスト・チャレンジブック、第2版、2012
秋葉拓哉, 岩田陽一, 北川宜稔

元々は、3人の東大大学院生が作った、チャレンジブックが大ヒットした。
今までは、こういうコンテストの問題を研究した本が無かった

一方、すでに海外では、TopCoder, Google Code Jam などが、
プログラマーの主戦場となっていて、日本では、AOJ が後を追っている状態

渡部有隆の本は、チャレンジブックの後に出した。
協力に、秋葉拓哉の名前もある

プログラマ脳を鍛える数学パズル
シンプルで高速なコードが書けるようになる70問、増井敏克、2015

一方、増井は、Rubyで解く、このパズル本で、
「ITエンジニアに読んでほしい！技術書・ビジネス書大賞（ITエンジニア本大賞）」を受賞している