板検索:
データ構造,アルゴリズム,デザインパターン総合スレ 3 (320)
まとめビュー
1
デフォルトの名無しさん[sageteoff]   投稿日:2016/06/19 14:47:29  ID:5KvSKdL/.net(2)
このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。

                  京都大学霊長類研究所

データ構造,アルゴリズム,デザインパターン総合スレ 2

【関連スレ】
3Dアルゴリズム全般
<集大成>アルゴリズム大辞典
アルゴリズム総合スレ in ム板

アルゴリズムとデータ構造 - Kaneko Lab.
http://www.kkaneko.com/adp/algo/index.html
アルゴリズムとデータ構造 - ソースコード探険隊
http://www.codereading.com/algo_and_ds/
各種アルゴリズムの C++ による実装 - Spaghetti Source
http://www.prefield.com/algorithm/
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
http://vipprog.net/wiki/algo_and_data_const.html


2
デフォルトの名無しさん[]   投稿日:2016/06/19 14:52:46  ID:5KvSKdL/.net(2)
http://hissi.org/read.php/tech/20160619/YW80V0xnZlg.html
へんなのが居着いたな

981 :デフォルトの名無しさん[sage]:2016/06/19(日) 12:16:06.94 ID:ao4WLgfX
>980
いつも思うんだけれども,この碁の勝負,棋譜は公開されているの?

985 :デフォルトの名無しさん[sage]:2016/06/19(日) 12:47:45.21 ID:ao4WLgfX
>982
どこに貼ってあるかな?たぶん公開されてないんじゃないかな

986 :デフォルトの名無しさん[sage]:2016/06/19(日) 12:59:15.60 ID:ao4WLgfX
http://blogs.yahoo.co.jp/ten_nan_91/35774553.html

988 :デフォルトの名無しさん[sage]:2016/06/19(日) 13:02:20.35 ID:ao4WLgfX
ありがとう

1000:デフォルトの名無しさん[sage]:2016/06/19(日) 14:49:22.87 ID:ao4WLgfX
0
コメント2件

3
デフォルトの名無しさん[sage]   投稿日:2016/06/19 15:04:05  ID:IRfn+3ke.net
>1 乙

4
デフォルトの名無しさん[sage]   投稿日:2016/06/19 16:13:42  ID:gP7jNw8f.net

5
デフォルトの名無しさん[sage]   投稿日:2016/06/19 17:17:34  ID:ao4WLgfX.net
ruby って変な人が多いんだね,俺も今 ruby をマスターしようと必死ではあるが

6
デフォルトの名無しさん[sage]   投稿日:2016/06/19 17:37:31  ID:X+E3gNs8.net
>2
盛大な自演だったってこと?

7
デフォルトの名無しさん[]   投稿日:2016/06/19 19:39:00  ID:iKM7Z0CI.net(3)
Haskellって勉強する意味ある?
実用性はないよね?

8
デフォルトの名無しさん[sage]   投稿日:2016/06/19 19:46:20  ID:0JS60cqV.net
雇われプログラマには不要

9
デフォルトの名無しさん[]   投稿日:2016/06/19 20:49:00  ID:iKM7Z0CI.net(3)
なぜ、HaskellやSchemeをありがたがる人がいるの?
どう考えてもC#とかのほうが生産性が高いのに。
単なるかっこつけ?

10
デフォルトの名無しさん[]   投稿日:2016/06/19 20:49:49  ID:iKM7Z0CI.net(3)
MITのコンピュータの入門書もSchemeを使っていたりする。

11
デフォルトの名無しさん[sage]   投稿日:2016/06/19 20:59:07  ID:Axw7zBsF.net
言語としてのlisp最強論は理解できるけどね。
実用的ではないのは言語自体の問題ではなくてシェアとかサポートする企業の存在とかコミュニティの問題。

12
デフォルトの名無しさん[sage]   投稿日:2016/06/19 23:46:31  ID:XG1Xog94.net
haskellやschemeは勉強したくない奴には不要
雇われには言語選択権はないので、かりにそれらがよいものであったとしたとしても、フラストレーションたまるだけだろ

一言でいうなら自分で一から十まで計算を構築するための言語だな
ライブラリ駆使して、なんとかすることが求められている人間にはこんなものは不要
コメント2件

13
デフォルトの名無しさん[]   投稿日:2016/06/20 00:15:53  ID:VsbhBHIt.net
>12
マジかよ

14
デフォルトの名無しさん[sage]   投稿日:2016/06/20 00:57:04  ID:rbqmVuz6.net
>12
> ライブラリ駆使して、なんとかすることが求められている人間にはこんなものは不要

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

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

15
デフォルトの名無しさん[]   投稿日:2016/06/20 06:52:18  ID:1vrQKLsp.net(6)
HaskellやSchemeの利点は?
少なくとも、分かりにくいよね。

16
デフォルトの名無しさん[sage]   投稿日:2016/06/20 08:05:44  ID:8yK3ULXk.net
オブジェクト指向程ではないけどな

17
デフォルトの名無しさん[sage]   投稿日:2016/06/20 12:30:23  ID:iz9OSKHh.net(2)
エンジニアの選定時の足切りにちょうどいいよ

18
デフォルトの名無しさん[sage]   投稿日:2016/06/20 18:11:51  ID:Z8Or5TTF.net
その基準で剪定できるのはかなり恵まれてる気が
コメント2件

19
デフォルトの名無しさん[sage]   投稿日:2016/06/20 18:23:24  ID:78XmmaUt.net
>14
>今日のプログラミングは、「より科学に近い。

ここは変だな
「より工学に近い。」
というなら判るが
コメント1件

20
デフォルトの名無しさん[]   投稿日:2016/06/20 18:31:26  ID:1vrQKLsp.net(6)
SICPをプログラミング初学者に教えるというのは確かに異様だよね。

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

21
デフォルトの名無しさん[]   投稿日:2016/06/20 18:35:05  ID:1vrQKLsp.net(6)
コンピュータサイエンスの中でアルゴリズムとデータ構造ってどれくらい重要な科目なの?

22
デフォルトの名無しさん[]   投稿日:2016/06/20 18:50:31  ID:FhfmjeRD.net
アルゴリズム + データ構造 = プログラム。
ということは。
プログラムの占める割合と等価なのでは。

23
デフォルトの名無しさん[]   投稿日:2016/06/20 18:52:50  ID:1vrQKLsp.net(6)
なんか計算の理論とかのほうが上みたいな感じじゃない?

24
デフォルトの名無しさん[]   投稿日:2016/06/20 18:53:47  ID:1vrQKLsp.net(6)
コンピュータサイエンスで最も重要な科目は、コンパイラとかOS?

25
デフォルトの名無しさん[sage]   投稿日:2016/06/20 18:53:55  ID:K++azvDQ.net
自演乙

26
デフォルトの名無しさん[sage]   投稿日:2016/06/20 19:14:10  ID:/YC1nkci.net
>18
この道30年の修業でようやく一人前

27
デフォルトの名無しさん[sage]   投稿日:2016/06/20 20:44:30  ID:EiR/M7I9.net
寿司職人乙
コメント1件

28
デフォルトの名無しさん[sage]   投稿日:2016/06/20 20:58:16  ID:amTC+NJd.net
schemeやらないとアルゴリズムとデータ構造を組み立てるってことがどういうことなのか、コードでわからないだろうな
コメント2件

29
デフォルトの名無しさん[]   投稿日:2016/06/20 21:06:41  ID:taQ4Dh1l.net
>28
javaでよくない?

30
デフォルトの名無しさん[sage]   投稿日:2016/06/20 21:24:25  ID:iSiyYjqf.net
javaでconsを表現するときにどうすればいいか知ってますか?

31
デフォルトの名無しさん[]   投稿日:2016/06/20 21:29:28  ID:1vrQKLsp.net(6)
>28

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


32
デフォルトの名無しさん[sage]   投稿日:2016/06/20 21:47:01  ID:eW3OX+fW.net(2)
>27
植木職人

33
デフォルトの名無しさん[sage]   投稿日:2016/06/20 22:10:02  ID:iz9OSKHh.net(2)
>18
未経験でも理解出来るならとりあえず地雷の可能性は下がる

34
デフォルトの名無しさん[sage]   投稿日:2016/06/20 22:22:55  ID:m9phkWTx.net
恵まれてない会社だと全員切る羽目になるって話だろw

35
デフォルトの名無しさん[sage]   投稿日:2016/06/20 22:43:48  ID:zvz85rzc.net(2)
31
そのSICPはschemeでかかれているわけで
昨今のライブラリ重視の観点からいえば、javaがいいっていうのはとおるけど、アルゴリズムかくのにjavaがいいってのは、センスないというか、お手入れ大好きなんだろうな

36
デフォルトの名無しさん[sage]   投稿日:2016/06/20 22:49:30  ID:eW3OX+fW.net(2)
引用できないやつに言われると

37
デフォルトの名無しさん[sage]   投稿日:2016/06/20 22:50:33  ID:zvz85rzc.net(2)
スマホで>>うつのめんどいんだよ

38
デフォルトの名無しさん[sage]   投稿日:2016/06/22 04:43:48  ID:W4spe1mc.net
日立、新型半導体コンピュータの実用化に向けた前処理アルゴリズムを開発
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/

39
デフォルトの名無しさん[]   投稿日:2016/06/22 07:14:40  ID:rmORGvIR.net(3)
日本人の書いたアルゴリズムとデータ構造の本でまともなのって1冊もないの?
コメント2件

40
デフォルトの名無しさん[sage]   投稿日:2016/06/22 07:53:05  ID:HSGRYDR8.net
>39
まともとは?

41
デフォルトの名無しさん[]   投稿日:2016/06/22 07:59:50  ID:rmORGvIR.net(3)
日本人の書いた本は薄っぺらくて説明も十分ではなく厳密でもなく網羅性もない本ばかりに思う。

42
デフォルトの名無しさん[]   投稿日:2016/06/22 08:00:26  ID:rmORGvIR.net(3)
杉原厚吉の本は特にひどいと思った。

43
デフォルトの名無しさん[sage]   投稿日:2016/06/22 11:07:15  ID:DmPvlaR4.net
>39
そのものズバリでアルゴリズムとデータ構造という本が岩波から出てる

44
デフォルトの名無しさん[sage]   投稿日:2016/06/22 12:53:15  ID:YevSrNYa.net
まともな本とは?
argolythm introduction?
knuth本?
どっちも使い物にならないが
コメント2件

45
デフォルトの名無しさん[sage]   投稿日:2016/06/22 13:50:41  ID:WHe3DbmR.net
>44
1単語に3箇所もミス入れるなよ

46
デフォルトの名無しさん[sage]   投稿日:2016/06/22 14:13:53  ID:sEqYA8cS.net
根幹のタームの綴りも知らん半可通に何を教われというのか

47
デフォルトの名無しさん[sage]   投稿日:2016/06/22 14:17:48  ID:yBOVYSwe.net
3ヶ所もあると誤り訂正も利かないんじゃまいか

48
デフォルトの名無しさん[sage]   投稿日:2016/06/22 14:22:16  ID:EwWgL4+X.net
バースト発生させんな

49
デフォルトの名無しさん[sage]   投稿日:2016/06/22 15:16:40  ID:2z7j8yec.net
????????????

50
デフォルトの名無しさん[sage]   投稿日:2016/06/22 21:44:16  ID:MWgF3eo3.net
>44
そんな頭じゃ使いものにならんのも頷けるわ

51
デフォルトの名無しさん[sage]   投稿日:2016/06/22 22:23:26  ID:Z2xvvdgM.net
こんな揚げ足とりの老害から何を学べと?

52
デフォルトの名無しさん[sage]   投稿日:2016/06/22 22:52:24  ID:X6XCfxlz.net
馬鹿の自己紹介されても困る

53
デフォルトの名無しさん[sage]   投稿日:2016/06/24 11:47:43  ID:hSLmnyaY.net
>19
は?変なのはお前だ
プログラミングは最初から工学的だろ何言ってんだ?

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

54
デフォルトの名無しさん[sage]   投稿日:2016/07/15 12:10:18  ID:P21uCIN+.net
何ヶ月か前に近代科学社に電話でセジウィックアルゴリズムの第四版の翻訳の予定はありますか、と訊いてみたが無いって返事だったんだよな
書いて欲しいんだがな

55
デフォルトの名無しさん[sage]   投稿日:2016/07/16 08:00:53  ID:Akpk7DL9.net
アルゴリズムさえ知ってりゃ動くプログラムは書けるから他は優先度低いと考えてた結果
データ構造すら分からない化石プログラマになってしまった

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

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

56
デフォルトの名無しさん[sage]   投稿日:2016/07/18 09:37:52  ID:YPoLSDg9.net
両方大事だろ。
データ構造が整理されてないとアルゴリズムも煩雑になるし。

57
デフォルトの名無しさん[]   投稿日:2016/07/21 23:06:49  ID:TpMXx+Na.net
vEB木の「僕の考えた最強のデータ構造」感が大好きなんだが誰か共感してくれる人いる?

58
デフォルトの名無しさん[sage]   投稿日:2016/07/22 07:32:19  ID:ot11jjQx.net
データ構造の基本は、以下の2つと、他にはハッシュがある

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

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

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

59
デフォルトの名無しさん[sage]   投稿日:2016/07/26 06:56:53  ID:HN1KCMsQ.net
letの時代がもうすぐそこまで来ているよね

60
デフォルトの名無しさん[sage]   投稿日:2016/07/26 14:27:18  ID:z5g/0KTZ.net
let
-------
 λ

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

https://youtu.be/5m3kPHO2w98

以上、どうぞよろしくお願いします
コメント3件

62
デフォルトの名無しさん[sage]   投稿日:2016/09/23 22:16:41  ID:xWgfj234.net
誰だ

63
デフォルトの名無しさん[sage]   投稿日:2016/09/23 22:42:52  ID:fJ2M8QeM.net
帰れ

64
デフォルトの名無しさん[sage]   投稿日:2016/09/24 09:14:59  ID:osPXZH57.net
>61
最初の数分見ましたが..

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

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

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

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

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

以上、感想でした

65
デフォルトの名無しさん[sage]   投稿日:2016/09/24 09:32:41  ID:n5/uj8Su.net(3)
64さん。ありがとうございます。私はこういうスライドを作る機会があまりないのでこんな形になってしまいました。
実は整っているという抽象的な単語を使っていますが、実は定量的にこれを測る方法はまだ思いついていません。
そのほかのご指摘はその通りだと思います。
貴重なご意見ありがとうございます

66
デフォルトの名無しさん[sage]   投稿日:2016/09/24 09:49:16  ID:B225F1SQ.net
動画見るの面倒だから3行で説明して
コメント1件


67
デフォルトの名無しさん[sage]   投稿日:2016/09/24 09:53:53  ID:trsNBxRI.net



コメント1件

68
デフォルトの名無しさん[sage]   投稿日:2016/09/24 09:55:26  ID:n5/uj8Su.net(3)
>66
まず目的のキーと現在探索中のキーの差をとる。
それを隣接するキーの最大値で割る。
その値だけ進む。

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

69
デフォルトの名無しさん[sage]   投稿日:2016/09/24 10:46:59  ID:iZTaxfZT.net
>隣接するキーの最大値

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

70
デフォルトの名無しさん[sage]   投稿日:2016/09/24 10:49:01  ID:9ZsTQHH6.net
>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
...
と線形時間になる(やり方あってるよね?)
演算している分、比較だけの線形探索より処理速度が遅くなる
コメント1件

71
デフォルトの名無しさん[sage]   投稿日:2016/09/24 11:09:23  ID:n5/uj8Su.net(3)
>69
>70
確かにキーの最大値を求めるのは線形時間かかります。なのであらかじめ、隣接するキーの最大値が分かっているデータに使用可能です。
探索の最悪時間は線形時間ですが、平均時間はlogのオーダーになるのではないでしょうか。私が不勉強なもので理論的には、示めせませんが多分logのオーダーになると思います。
ソートしなくても探索できるのは差の絶対値を取るからです。動画に入れるのを忘れました。すいません。
計算についてはそれであっています。わざわざご指摘ありがとうございます
コメント2件

72
デフォルトの名無しさん[sage]   投稿日:2016/09/25 01:17:16  ID:MeFnEkA4.net
>71
上でも指摘されているが整っているの定義が不明
二分探査の場合は、存在しないこともlog n で確認可能だが、この手法は整っているの定義次第では存在しない者の確認が非常に時間かかる(ソートされている場合は存在するものと同等だが、そうすると二分探索よりも利点が少なくなる)
平均計算量を求めるのはちと難しそうだけど、格納される値の値域に依存するかな
たぶん、log n 程良くはないと思う
コメント1件

73
デフォルトの名無しさん[sage]   投稿日:2016/09/25 09:29:52  ID:byM8xGto.net
>72
ご指摘ありがとうございます。確かに整っているの定義ができていないのが一番の難点ですよね。いつか勉強して考えたいと思います

74
デフォルトの名無しさん[]   投稿日:2016/09/25 12:26:29  ID:3wiQalb8.net
>67
ごめん
みたけど
だめだこりゃ
コメント2件

75
デフォルトの名無しさん[sage]   投稿日:2016/09/25 12:52:11  ID:NTqjAG/u.net
>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回の演算

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

76
デフォルトの名無しさん[sage]   投稿日:2016/09/25 14:20:01  ID:8PebKpFu.net
>74
88

77
デフォルトの名無しさん[sage]   投稿日:2016/09/26 13:42:01  ID:ymOrEJcI.net
>61
すもモンがnewton法をガチで知らないのであればnewton法をまず勉強するべき
カンガルーの敵はバイナリではなくnewtonだ
コメント1件

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

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

80
デフォルトの名無しさん[]   投稿日:2016/10/16 18:51:48  ID:LqkHCFhg.net
状態遷移ってどういうステータス持てばいいの?

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

というとき、A と B のほかに AからBになるのを待ってる状態と
BからAになるを待ってる状態の 2つがさらに状態として必要?
過渡状態も状態?
コメント1件

81
デフォルトの名無しさん[sage]   投稿日:2016/10/17 07:56:46  ID:TukeUWYl.net
>80
システムの設計次第。
切り替え中、待ち中が状態として存在するのならプログラムでも状態にすればいい
コメント1件

82
デフォルトの名無しさん[sage]   投稿日:2016/10/17 15:43:18  ID:srAFoI0L.net
>81
そりゃそうだけど
状態がn個あると過渡状態がたくさんになるのは
辛い
コメント1件

83
デフォルトの名無しさん[sage]   投稿日:2016/10/17 17:53:14  ID:75S5w4gh.net
現在の状態と次の状態のペアにすれば?

84
デフォルトの名無しさん[sage]   投稿日:2016/10/17 21:23:44  ID:sc7L52q+.net
辛かろうが状態が存在するのならしょうがあるまい。
あるいは遷移をアトミックにして遷移中状態そのものを無くすか、遷移中の動作を共通化
できるなら遷移先をパラメータ化して「*への遷移中」という1状態にしてしまうとか。

85
デフォルトの名無しさん[sage]   投稿日:2016/10/17 23:34:18  ID:WkWdUImM.net
>82には無理ということで

86
デフォルトの名無しさん[sage]   投稿日:2016/11/05 20:41:10  ID:PXYcOtjJ.net
ポリモーフィックなクラスの相互作用において特定の型の組み合わせの場合のみ処理を特殊化したい場合はどうすればいいのだろう?

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);

87
デフォルトの名無しさん[sage]   投稿日:2016/12/12 23:13:40  ID:IcWOSn01.net
デザインパターンを使って実装すると、年長プログラマーから、またこんなことしやがって的な拒否反応が帰ってくるんだがどうすれば
コメント1件

88
デフォルトの名無しさん[sage]   投稿日:2016/12/12 23:42:41  ID:bt79hYqC.net
排除する他道は無い。

89
デフォルトの名無しさん[sage]   投稿日:2016/12/12 23:50:03  ID:hGpJarHd.net
転職しろ

90
デフォルトの名無しさん[sage]   投稿日:2016/12/13 03:19:26  ID:neuXXcOh.net
若者で組合(または派閥)を創る

91
デフォルトの名無しさん[sage]   投稿日:2016/12/13 08:14:05  ID:5xcG7lRc.net
>87 がどんなコードを書いたかも分からんのに

92
デフォルトの名無しさん[sage]   投稿日:2016/12/13 18:53:42  ID:MUcELcjh.net
下手くそがデザインパターンとか使うと逆にこんがらがるからなぁ
老害とどっこいどっこいだろ

93
デフォルトの名無しさん[]   投稿日:2016/12/13 21:32:18  ID:lYWHr0pJ.net
マルチスレッドで、なんの考えもなくオブザーバー使いまくられて、データ破壊しまくられた時には、本気で殺意を抱いたよ

94
デフォルトの名無しさん[]   投稿日:2016/12/16 15:12:11  ID:kO0vFktz.net
『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』

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

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

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

というのがあります。

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

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

よろしくお願いします。
コメント1件

95
デフォルトの名無しさん[sage]   投稿日:2016/12/16 15:34:53  ID:n8JQ6xp/.net
assertionじゃね
コメント1件

96
デフォルトの名無しさん[]   投稿日:2016/12/17 16:05:18  ID:lvQHWty7.net
完成形をいきなり見てると不思議に思うよね。
でも実際には作成中のバグを考慮して、最初にチェックを入れておくもんなんだよね。
まあ、一言で言えばassertなんだけど。

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

97
デフォルトの名無しさん[]   投稿日:2016/12/17 16:09:26  ID:GDWdcO6h.net(7)
>95-96

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

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

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

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

98
デフォルトの名無しさん[]   投稿日:2016/12/17 16:23:27  ID:GDWdcO6h.net(7)
>94

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

http://imgur.com/zKVWzAJ.jpg
http://imgur.com/owa8NkX.jpg
http://imgur.com/NmCczss.jpg
コメント3件

99
デフォルトの名無しさん[sage]   投稿日:2016/12/17 16:42:25  ID:a9hyyPvt.net(3)
>97
参考文献ならパクってるとは言わない

100
デフォルトの名無しさん[sage]   投稿日:2016/12/17 16:43:27  ID:a9hyyPvt.net(3)
>98
こういうのが本当のパクり
訴えられたら負ける

101
デフォルトの名無しさん[sage]   投稿日:2016/12/17 18:12:28  ID:rDdwnYMe.net(2)
>97
他の本も読んでみるとわかると思うけど、プライオリティキューを二分木ヒープで実装するのは定番で、どの本でも大体同じことが書いてある
コメント1件

102
デフォルトの名無しさん[]   投稿日:2016/12/17 19:29:55  ID:GDWdcO6h.net(7)
>98

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

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

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

103
デフォルトの名無しさん[]   投稿日:2016/12/17 19:31:29  ID:GDWdcO6h.net(7)
>101

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

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

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

完全にパクりだと思います。
コメント1件

104
デフォルトの名無しさん[]   投稿日:2016/12/17 19:35:00  ID:a9hyyPvt.net(3)
>103
参考文献に書いてあるんだからパクリも糞も無い罠
参考文献に書き漏れたら小保方さんみたいに突っ込まれるが

105
デフォルトの名無しさん[]   投稿日:2016/12/17 19:35:29  ID:GDWdcO6h.net(7)
『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』の
他のプログラムもおそらくすべて『アルゴリズムイントロダクション』の
プログラムをそのまま使っています。

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

106
デフォルトの名無しさん[]   投稿日:2016/12/17 19:36:34  ID:GDWdcO6h.net(7)
参考文献に文献を挙げれば何でも許されるということはないと思いますが。

107
デフォルトの名無しさん[]   投稿日:2016/12/17 19:39:42  ID:GDWdcO6h.net(7)
『アルゴリズムイントロダクション』のほうをよく読んでいませんが、

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

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

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

>98

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

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

108
デフォルトの名無しさん[sage]   投稿日:2016/12/17 19:42:21  ID:C/wQAZQ3.net
『アルゴリズムイントロダクション』のほうをよく読んでいませんが、
『アルゴリズムイントロダクション』のほうもまたどっか別の本からのパクリの悪寒。

109
デフォルトの名無しさん[sage]   投稿日:2016/12/17 19:47:48  ID:YhK78PBA.net
"error: heap underflow" でググるといっぱい出てくる

110
デフォルトの名無しさん[sage]   投稿日:2016/12/17 19:57:50  ID:rDdwnYMe.net(2)
ID:GDWdcO6h は何をそんなに怒ってるの?
問題が解けなくてイライラしてるだけ?

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

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

111
デフォルトの名無しさん[sage]   投稿日:2016/12/17 20:55:04  ID:jmPH7DRp.net
disるのがはやってるらしい

112
デフォルトの名無しさん[sage]   投稿日:2016/12/18 00:45:20  ID:aCKcGLhu.net(4)
プログラミングコンテスト攻略のための、
アルゴリズムとデータ構造、渡部有隆(わたのべ ゆたか)、2015
Ozy(協力), 秋葉 拓哉(協力)

Aizu Online Judge(AOJ、会津大学)

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

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

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

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

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

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

113
デフォルトの名無しさん[]   投稿日:2016/12/18 00:49:54  ID:VFzWAIXP.net(2)
めんどくさ

114
デフォルトの名無しさん[sage]   投稿日:2016/12/18 01:14:58  ID:aCKcGLhu.net(4)
漏れも、JavaScriptで、2分ヒープ(BinaryHeap)を実装したので、参照して
http://jsdo.it/michihito/bGH5

2分ヒープは、優先度つきキュー (順位キュー、priority queue)や、
ダイクストラ法 (Dijkstra's Algorithm)で使う

配列の[0]は使わない。[1]から始めると計算が楽
親1, 左右の子は2, 3で、親n, 子2n, 2n+1

プログラミング・コンテスト・チャレンジブックでは、[0]から始めていますが、
もし[0]から始めると、
親0, 左右の子は1, 2で、
親1, 左右の子は3, 4で、
親n, 子2n+1, 2n+2、となり複雑だから
コメント2件

115
デフォルトの名無しさん[sage]   投稿日:2016/12/18 01:56:35  ID:05Ug+E6t.net(3)
>114
汚すぎるコードだ。なんだろう。初心者とも違うな。
まるで20年ぐらい前から成長してない人が書いたコードのようだ。
コメント1件

116
デフォルトの名無しさん[]   投稿日:2016/12/18 02:12:34  ID:KR24tnjc.net
>115
ド素人と丸出しの感想文だな

117
114[sage]   投稿日:2016/12/18 04:57:12  ID:aCKcGLhu.net(4)
すまぬ

JavaScriptも、よく知らずに書いたのだw
本当は、== ではなく、型も一致する厳密等価演算子、=== を使うべきだろう

まあ、JSなどで、とても開発はできない。
Haxe で書き直せばよいのだろうが

Kotlin, Electron やら何やら、最近の言語に、ついていけてないw

118
デフォルトの名無しさん[sage]   投稿日:2016/12/18 08:19:04  ID:05Ug+E6t.net(3)
> 本当は、== ではなく、型も一致する厳密等価演算子、=== を使うべきだろう
そういうレベルじゃない。

無駄なロジック、意味不明な変数名、多すぎるコメント、
コードの意味を何一つ分かってないとしか思えないといってんの

119
デフォルトの名無しさん[sage]   投稿日:2016/12/18 11:08:48  ID:7J/3tpZx.net
俺はむしろここ
> このソースコードのライセンスは、MIT License です
> Original Copyright (c) 2014 Michihito Seto All Rights Reserved.
残飯を神棚に飾るが如く宣言
ここにこそ初心者らしさが凝縮されてる
コメント1件

120
デフォルトの名無しさん[]   投稿日:2016/12/18 11:50:21  ID:5nrc1ooF.net(10)
>114

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

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

というのは意味があるのでしょうか?

121
デフォルトの名無しさん[sage]   投稿日:2016/12/18 11:50:54  ID:05Ug+E6t.net(3)
jsdo使ってるやつって汚いコードが多いよな。
素人が使いたくなる機能でもあんのか?
ブラウザだけで開発ができるとか?

122
デフォルトの名無しさん[]   投稿日:2016/12/18 11:53:36  ID:5nrc1ooF.net(10)
デバッグなど必要のないくらい簡単なコードなので、デバッグ用とは考えられないかと思います。

123
デフォルトの名無しさん[sage]   投稿日:2016/12/18 11:57:14  ID:0+9ctOie.net
馬鹿ほど自説に拘るw

124
デフォルトの名無しさん[]   投稿日:2016/12/18 12:12:58  ID:5nrc1ooF.net(10)
Introduction to AlgorithmsよりもAlgorithms(Sedgewick、赤い本)のほうがいい本ですね。

読んでいて楽しい。

125
デフォルトの名無しさん[]   投稿日:2016/12/18 12:18:23  ID:5nrc1ooF.net(10)
日本語のデータ構造とアルゴリズムの本だと、茨木の本が有名だけど、
どこがいいのかさっぱりわからない。

翻訳書ではない日本語の本でまともなのは、浅野孝夫の本くらいではないでしょうか?

126
デフォルトの名無しさん[sage]   投稿日:2016/12/18 12:18:30  ID:d5jVhhWj.net(3)
アルゴリズムやコードのライセンスってどの程度のものから付けていいんだ
あんまり簡単なものだと既出すぎてライセンス付けられるのか?って考えてしまう
かといってじゃあライセンス付けていい最低ラインは何なんだという話になる
コメント1件

127
デフォルトの名無しさん[]   投稿日:2016/12/18 12:20:00  ID:5nrc1ooF.net(10)
>126

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

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

128
デフォルトの名無しさん[sage]   投稿日:2016/12/18 12:30:54  ID:RB5DyRP2.net(2)
アルゴリズムには著作権ないよ
あるのはそれをどう表現したか
簡単なアルゴリズムには表現バリエーションなんて限られてるから
ある程度似るのはどうしようもない

129
デフォルトの名無しさん[]   投稿日:2016/12/18 12:37:57  ID:5nrc1ooF.net(10)
特許ならありますよね。

130
デフォルトの名無しさん[sage]   投稿日:2016/12/18 13:02:47  ID:PELrVlNw.net(3)
デザインパターンの本高い・・・
一冊持ってたけど引っ越しのごたごたでなくしちゃった
無料で網羅できるサイトありませんかね
一冊読んではあるので、さらっと構造や仕組みを紹介してくれていればいいし
英語もある程度は読めます

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

131
デフォルトの名無しさん[sage]   投稿日:2016/12/18 13:22:26  ID:d5jVhhWj.net(3)
基本的な考え方覚えたら幾らでも応用できるだろ
カタログを後生大事にとっておく意味はない

132
デフォルトの名無しさん[sage]   投稿日:2016/12/18 13:35:15  ID:PELrVlNw.net(3)
覚えてないんすよ
記憶力ないんで忘れちゃって、ぼんやりとしか覚えてないんです
だから概要をしっかり覚え直したいなと思って
コメント1件

133
デフォルトの名無しさん[sage]   投稿日:2016/12/18 13:42:55  ID:+dKTlaSP.net
>132
いや、デザパタ本こそ手元においておくべき
わけのわからん二次情報を見るとどんどんブレていくぞ

134
デフォルトの名無しさん[sage]   投稿日:2016/12/18 13:45:05  ID:RB5DyRP2.net(2)
リファレンスとしてはどの本がいい?

135
デフォルトの名無しさん[]   投稿日:2016/12/18 13:45:12  ID:5nrc1ooF.net(10)
ソフトウェア工学的な本って重要なんですか?

136
デフォルトの名無しさん[]   投稿日:2016/12/18 13:45:59  ID:5nrc1ooF.net(10)
学問的には全く面白くない分野ですよね。


137
デフォルトの名無しさん[sage]   投稿日:2016/12/18 14:08:17  ID:PELrVlNw.net(3)
TECHSCOREのデザインパターンのページ見ることで自己解決しました

138
デフォルトの名無しさん[]   投稿日:2016/12/18 15:45:37  ID:VFzWAIXP.net(2)
デザパタカタログは便利だよね
煮詰まったときに、休憩がてらパターンを眺めてると、閃くときがある

139
デフォルトの名無しさん[sage]   投稿日:2016/12/18 16:24:54  ID:+Ko1jSRc.net
ねーわ、普通のコードが99.99%

140
デフォルトの名無しさん[sage]   投稿日:2016/12/18 18:22:27  ID:d5jVhhWj.net(3)
基本的な発想を学んだらカタログはポイ
パターンに執着してもデザインがぎこちなくなるだけ

141
114[sage]   投稿日:2016/12/18 23:03:56  ID:aCKcGLhu.net(4)
>119
jsdo.it では、全員のソースコードが、サイト内に限り、MITになる

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

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

142
デフォルトの名無しさん[sage]   投稿日:2016/12/18 23:11:13  ID:f3M2Oqre.net

143
デフォルトの名無しさん[]   投稿日:2016/12/18 23:11:21  ID:5nrc1ooF.net(10)
2分ヒープって簡単なアルゴリズムですよね。

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

144
デフォルトの名無しさん[]   投稿日:2016/12/18 23:12:19  ID:5nrc1ooF.net(10)
計算幾何学って難しい割に見返りが少ないように思います。

だからあんまり人気がないのかもしれないですね。
コメント2件

145
デフォルトの名無しさん[sage]   投稿日:2016/12/19 00:01:07  ID:hSWjQy3F.net(5)
漏れw

146
デフォルトの名無しさん[sage]   投稿日:2016/12/19 01:06:56  ID:8cVREo5r.net
流石に漏れは笑う

147
デフォルトの名無しさん[sage]   投稿日:2016/12/19 08:08:43  ID:judB9f5Y.net
>144
全体的なリテラシの底上げがされるまではどうしてもね。

148
デフォルトの名無しさん[]   投稿日:2016/12/19 12:42:11  ID:z9XVuDpo.net(2)
>144
理論的な上限値をあらかじめ計算することが出来て
無駄な努力や試行錯誤をしなくて済むというメリットがあるよ

149
デフォルトの名無しさん[sage]   投稿日:2016/12/19 17:37:02  ID:ic0p/3Yf.net(14)
長さ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)とかあるので一つには定まってません。
なのでその対応をする関数をおしえてください。
コメント1件

150
間違ってたので直します[sage]   投稿日:2016/12/19 17:39:59  ID:ic0p/3Yf.net(14)
長さ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)とかあるので一つには定まってません。
なのでその対応をする関数をおしえてください。
コメント1件

151
デフォルトの名無しさん[sage]   投稿日:2016/12/19 17:48:27  ID:z9XVuDpo.net(2)
(1,-1,1)の長さが2?

152
デフォルトの名無しさん[]   投稿日:2016/12/19 17:53:09  ID:yHCszZUX.net(6)
>なのでその対応をする関数をおしえてください。

意味不明です。

153
デフォルトの名無しさん[]   投稿日:2016/12/19 17:55:40  ID:yHCszZUX.net(6)
(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)

を返せばいいのでは?

154
デフォルトの名無しさん[]   投稿日:2016/12/19 17:57:14  ID:yHCszZUX.net(6)
(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 のときには、条件を満たす列は存在しないね。
コメント1件

155
デフォルトの名無しさん[]   投稿日:2016/12/19 17:58:07  ID:yHCszZUX.net(6)
>150

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

156
デフォルトの名無しさん[sage]   投稿日:2016/12/19 17:58:17  ID:hSWjQy3F.net(5)
>149
列の最初の数字だけ1足すなり引くなりして返せばいいだけじゃないの?
コメント2件

157
デフォルトの名無しさん[]   投稿日:2016/12/19 18:01:17  ID:yHCszZUX.net(6)
>例えば n=3のとき(1, -1, 1)は大きさが3で、これに対応する大きさ2の列は
>(0 ,-1 ,1), (1,0,1),(1,-1,0)とかあるので一つには定まってません。
>なのでその対応をする関数をおしえてください。

一つに定まらないから、すべての結果を返したいのか、
任意の一つの結果を返したいのか?
コメント1件

158
デフォルトの名無しさん[]   投稿日:2016/12/19 18:02:09  ID:yHCszZUX.net(6)
明らかに、

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

159
デフォルトの名無しさん[sage]   投稿日:2016/12/19 18:50:37  ID:ic0p/3Yf.net(14)
0はスタート地点なので

160
デフォルトの名無しさん[sage]   投稿日:2016/12/19 18:57:02  ID:ic0p/3Yf.net(14)
>154
a_2を1としたとき(-1, 1)のとき(-1,0)を返し
a_1を-1としたとき (-1,1)は(0,1)をかえすことになるので
一つに定まりません

161
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:06:19  ID:ic0p/3Yf.net(14)
>157
大きさn>0の任意の列aにたいしてf(a)=bでbがn-1の大きさでaと列の中の値が1だけ違う
列を出力する関数fを求めるということです。
コメント1件

162
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:13:51  ID:ic0p/3Yf.net(14)
>156
初めはそんな風に考えてる時期もありました
もう2か考えてるけれど全然わからないのでここで質問してみました

163
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:16:05  ID:hSWjQy3F.net(5)
>161
問題文を鸚鵡返しするんじゃなくて、質問者の質問に答えたら?
コメント1件

164
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:23:49  ID:ic0p/3Yf.net(14)
>163
fの出力は列の集合じゃないから普通わかりますよね
コメント1件

165
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:31:58  ID:hSWjQy3F.net(5)
>164
fが返すのは集合じゃないってのはどこに書いてある?
コメント1件

166
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:34:42  ID:ic0p/3Yf.net(14)
>165
14行上に書いてあります
コメント1件

167
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:47:31  ID:hSWjQy3F.net(5)
>166
Mateだと>156って書いてあるわ
自分の中ではこれは当然みたいな条件がいろいろあるんだろうけど、それを人に説明するのが下手なんじゃね

168
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:02:25  ID:ic0p/3Yf.net(14)
改行コードの数を数えてますか?
文の折り返しと改行とは違いますよ?

169
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:17:02  ID:2q/Y95iw.net(4)
こりゃまたひどい質問者だな
コメント1件

170
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:18:06  ID:Xx/umGft.net(3)
課題の丸投げ、しかも「日本語」が
コメント1件

171
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:25:56  ID:ic0p/3Yf.net(14)
課題という証拠はありますか?
実際課題じゃなくプログラミングしていたら出てきた問題なので
全然課題じゃないです
コメント1件

172
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:33:03  ID:ic0p/3Yf.net(14)
>170
あなたには誤った文を訂正する能力がないんですか?
それでは人間ではなくコンパイラーと同じですよ
コメント1件

173
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:37:51  ID:ic0p/3Yf.net(14)
>169
面白い問題とつまらない問題を区別する能力が数学的推測には
一番必要なんんです
この問題がつまらないと思うのなら解かないでいいです

174
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:50:46  ID:2q/Y95iw.net(4)
問題をきちんと記述する能力に欠けている
コメント1件

175
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:52:23  ID:2q/Y95iw.net(4)
あと、面白い問題だと思うなら、それこそ自分で解くのが楽しいのでは
ここで聞かずに
コメント1件

176
デフォルトの名無しさん[sage]   投稿日:2016/12/19 21:27:51  ID:ic0p/3Yf.net(14)
>175
楽しいものは独り占めるのではなく分け与えようと習わなかったのでは?

177
デフォルトの名無しさん[sage]   投稿日:2016/12/19 21:44:43  ID:ic0p/3Yf.net(14)
>174
今読み返してみましたがキチンと書かれてますよ
どこがキチンと書かれてないのか言ってくれたら
それは理解力の無さなので説明してもいいです

178
デフォルトの名無しさん[sage]   投稿日:2016/12/19 22:34:08  ID:2q/Y95iw.net(4)
十分楽しんだからあとは一人で楽しんでくれていいよ

179
デフォルトの名無しさん[sage]   投稿日:2016/12/19 22:53:51  ID:Xx/umGft.net(3)
>172
馬鹿乙

180
デフォルトの名無しさん[sage]   投稿日:2016/12/19 23:04:39  ID:L2gIhLeK.net
先頭から非0を探して、はじめの要素が正なら1ひく、負なら1足す
これで終わりじゃないの?

181
デフォルトの名無しさん[sage]   投稿日:2016/12/19 23:45:15  ID:Xx/umGft.net(3)
アルゴリズムは自分で考えるじゃ、ボケ

182
デフォルトの名無しさん[sage]   投稿日:2016/12/20 13:05:59  ID:lAXr92yw.net
>171
茶か尿かもう判らんって意見があるけど
検出時のガスクロのデータ見直したら判るはずという話がある
仮にそれでお茶だとしてももう発表はないだろう

183
デフォルトの名無しさん[]   投稿日:2016/12/21 18:35:54  ID:UR5SKYPV.net(15)
数列 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 を求めるプログラムを作れ。
コメント4件

184
デフォルトの名無しさん[sage]   投稿日:2016/12/21 18:45:01  ID:trArLuj5.net(4)
お断りいたします

185
デフォルトの名無しさん[sage]   投稿日:2016/12/21 18:49:10  ID:IT3zLaEf.net
俺も断るわ

186
デフォルトの名無しさん[]   投稿日:2016/12/21 19:41:25  ID:UR5SKYPV.net(15)
早くも降参宣言か。
コメント1件

187
デフォルトの名無しさん[sage]   投稿日:2016/12/21 19:55:05  ID:RIWp4Ngq.net(9)
mなんていくらでもあるんじゃないの?
なんで#{m}=1?
コメント1件

188
デフォルトの名無しさん[]   投稿日:2016/12/21 20:06:55  ID:UR5SKYPV.net(15)
>187

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

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

189
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:09:57  ID:trArLuj5.net(4)
>183
分からない問題はここに書いてね421 [無断転載禁止]©2ch.net
分からない問題はここに書いてね421 /数学板

190
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:12:10  ID:RIWp4Ngq.net(9)
k=1, l=2で、{m}={2,4,6,8,...}
k=l=1で、{m}=自然数の集合
じゃないの?
コメント1件

191
デフォルトの名無しさん[]   投稿日:2016/12/21 20:16:47  ID:UR5SKYPV.net(15)
>190

{a_n} の任意の*連続する*有限部分列を a_k, a_(k+1), …, a_l(k ≦ l)とする。
コメント1件

192
デフォルトの名無しさん[]   投稿日:2016/12/21 20:18:48  ID:UR5SKYPV.net(15)
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} です。

193
デフォルトの名無しさん[]   投稿日:2016/12/21 20:19:15  ID:UR5SKYPV.net(15)
>191
は勘違いです。

194
デフォルトの名無しさん[]   投稿日:2016/12/21 20:20:14  ID:UR5SKYPV.net(15)
a_1 = 1

なので、

b_1 = 0

です。

なので、

{m} = {1}

です。

195
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:21:17  ID:RIWp4Ngq.net(9)
k=1, l=2も、k=l=1も、当然連続する部分列でしょ
{b_i}を10個ぐらい挙げてみてよ

196
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:22:42  ID:RIWp4Ngq.net(9)
mの条件が足りないんじゃないの?

197
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:24:46  ID:RIWp4Ngq.net(9)
b_i ≦ b_mさえ満たせばいいんならmなんていくらでもあるでしょ

198
デフォルトの名無しさん[]   投稿日:2016/12/21 20:32:03  ID:UR5SKYPV.net(15)
b_m は b_i の最大値です。

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

199
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:32:36  ID:El82f3CE.net
k≦m≦lという条件が抜けているっぽいね
コメント1件

200
デフォルトの名無しさん[]   投稿日:2016/12/21 20:34:06  ID:UR5SKYPV.net(15)
テレンス・タオ ルベーグ積分入門
テレンス タオ
固定リンク: http://amzn.asia/8KaL6NK

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

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

普通、ルベーグ積分なんてやるのは数学科かせいぜい物理学科くらいじゃないですか?
コメント1件

201
デフォルトの名無しさん[]   投稿日:2016/12/21 20:34:58  ID:UR5SKYPV.net(15)
>199

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

202
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:39:27  ID:RIWp4Ngq.net(9)
不完全な問題出しておいて>186はないよね
コメント1件

203
デフォルトの名無しさん[]   投稿日:2016/12/21 20:41:22  ID:UR5SKYPV.net(15)
>202

不完全なところはありません。
よく問題文を読んでください。
コメント1件

204
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:42:06  ID:trArLuj5.net(4)

205
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:43:41  ID:trArLuj5.net(4)
マルチ小僧w

206
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:44:49  ID:RIWp4Ngq.net(9)
>203
mがkからlの間なんて一言もないんだから不完全
コメント1件

207
デフォルトの名無しさん[]   投稿日:2016/12/21 20:47:08  ID:UR5SKYPV.net(15)
>206

>183
各 i(k ≦ i ≦ l)に対して、0以上の整数 b_i を以下で定義する

208
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:52:23  ID:RIWp4Ngq.net(9)
そうだとして、わざと誤読を誘おうとしている悪問だね
でO(log k)のアルゴリズム思いついたから俺は降りるね

209
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:53:06  ID:RIWp4Ngq.net(9)
O(log l)だった

210
デフォルトの名無しさん[]   投稿日:2016/12/21 20:55:14  ID:UR5SKYPV.net(15)
>183

の解答は以下です。

http://imgur.com/rAnp3Ga.jpg

赤線を引いたところは「odd」が正しいですね。

211
デフォルトの名無しさん[]   投稿日:2016/12/21 21:27:34  ID:UR5SKYPV.net(15)
実は、この問題には続きがあります。

m, n を m < n を満たす正の整数とします。

このとき、

1/m + 1/(m+1) + … + 1/n

は整数にはならないことを証明せよ。
コメント1件

212
デフォルトの名無しさん[]   投稿日:2016/12/21 21:29:28  ID:UR5SKYPV.net(15)
ちょっとアルゴリズム的な問題からは離れますが。

213
デフォルトの名無しさん[sage]   投稿日:2016/12/21 21:31:37  ID:xYX0mlO/.net
提出日はいつですか?

214
デフォルトの名無しさん[sage]   投稿日:2016/12/21 22:14:54  ID:auJA5Ak8.net
またバカな質問者が暴れてるのか

215
デフォルトの名無しさん[sage]   投稿日:2016/12/21 23:45:05  ID:mNaBBYjZ.net
qiitaでやれ

216
デフォルトの名無しさん[sage]   投稿日:2016/12/23 00:59:54  ID:gOElNe3R.net(2)
>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 となって矛盾

217
デフォルトの名無しさん[sage]   投稿日:2016/12/23 01:37:11  ID:gOElNe3R.net(2)
>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 で矛盾

218
デフォルトの名無しさん[]   投稿日:2017/01/01 00:15:18  ID:VtFWW7J2.net
ダイクストラのアルゴリズムの正しさの証明が載っている本で
一番分かりやすい本を教えてください。

219
デフォルトの名無しさん[]   投稿日:2017/01/02 07:40:19  ID:03PPbeGI.net(15)
『アルゴリズムイントロダクション』について質問です。

この本での実数の集合には、 ∞, -∞ が含まれるのでしょうか?

最短路問題の説明で、

実数 a が a≠∞のとき、 a + -∞ = -∞
実数 a が a≠-∞のとき、 a + ∞ = ∞

という記述があるために質問します。

220
デフォルトの名無しさん[]   投稿日:2017/01/02 08:09:15  ID:03PPbeGI.net(15)
実数 a が a≠∞のとき、 a + -∞ = -∞
実数 a が a≠-∞のとき、 a + ∞ = ∞

-∞ + -∞ = -∞
∞ + ∞ = ∞

という等式を含めたいからこのような書き方になったのでしょうか?

221
デフォルトの名無しさん[sage]   投稿日:2017/01/02 09:29:22  ID:J77W/v0L.net(2)
それは実無限派の書き方だが,世の趨勢は可能無限
ほどほどに相手をするだけでいいよ
コメント1件

222
デフォルトの名無しさん[]   投稿日:2017/01/02 11:22:57  ID:03PPbeGI.net(15)
>221

ということは、『アルゴリズムイントロダクション』での実数の集合の定義には、
∞、-∞ が含まれるというk十ですね。
コメント1件

223
デフォルトの名無しさん[]   投稿日:2017/01/02 11:23:39  ID:03PPbeGI.net(15)
頂点の数が n のグラフで、任意の頂点間に辺が存在するようなものを考える。

ある任意の頂点から別の任意の頂点への閉路をふくまない経路の数を求めよ。

224
デフォルトの名無しさん[]   投稿日:2017/01/02 11:26:14  ID:03PPbeGI.net(15)
頂点の数が n(≧2) のグラフで、任意の頂点間に辺が存在するようなものを考える。

ある任意の頂点から別の任意の頂点への閉路をふくまない経路の数を a_n とする。

このとき、

(n-1)! ≧ a_n ≧ (n-2)!

が成り立つことを示せ。
コメント1件

225
デフォルトの名無しさん[sage]   投稿日:2017/01/02 12:08:43  ID:GdcUHK9D.net(3)
宿題は宿題スレへ

226
デフォルトの名無しさん[sage]   投稿日:2017/01/02 12:09:56  ID:GdcUHK9D.net(3)
2重書き込みのため表示しません 内容を確認する

227
デフォルトの名無しさん[]   投稿日:2017/01/02 12:22:39  ID:03PPbeGI.net(15)
宿題ではないのです。

ある本に、頂点 s から t への最短経路を計算する方法として、
s から t へのあらゆる経路の長さを考えて、最小の経路を選ぶとすると、
経路の数が O(n!) だから現実的ではない

という話が書いてあります。

ところが、計算してみると、 O(n!) は荒い評価であって、 O((n-1)!) とできますね。
コメント2件

228
デフォルトの名無しさん[]   投稿日:2017/01/02 12:24:22  ID:03PPbeGI.net(15)
もっといい評価はありますでしょうか?

229
デフォルトの名無しさん[sage]   投稿日:2017/01/02 12:28:36  ID:GdcUHK9D.net(3)
判ってるなら効くな

230
デフォルトの名無しさん[]   投稿日:2017/01/02 14:08:15  ID:03PPbeGI.net(15)
ダイクストラ法の正しさの証明で分かりやすい証明を思いつきました。

発表しましょうか?

231
デフォルトの名無しさん[sage]   投稿日:2017/01/02 14:21:37  ID:w6ZCrhsc.net
どうぞどうぞ

232
デフォルトの名無しさん[sage]   投稿日:2017/01/02 14:27:23  ID:yIXUnWg3.net
>227
オーダーについてあんま良くわかってないんだろうけどO((n-1)!) なんて書き方はないよ
もし書いたとして、それはO(n!)と同じもの
コメント1件

233
デフォルトの名無しさん[sage]   投稿日:2017/01/02 17:55:38  ID:J77W/v0L.net(2)
>222
実無限はいろいろ破綻するから可能無限にしておいたほうがいいよ
実数の定義に∞, -∞は入らない
というか,そもそも -∞ というのがおかしい存在

つリーマン球面

234
デフォルトの名無しさん[]   投稿日:2017/01/02 19:04:30  ID:03PPbeGI.net(15)
なんか正しさの証明を書いてみると簡単なことなのに長くなりますね。
もし、間違っていたら指摘してください。

http://imgur.com/PDx2vmZ.jpg
http://imgur.com/DbMiSz5.jpg

ダイクストラのアルゴリズムは↑のものとします。
コメント1件

235
デフォルトの名無しさん[]   投稿日:2017/01/02 19:05:18  ID:03PPbeGI.net(15)
節点 s から、ある節点 i への最短経路が存在するとき、その長さを td(i) で表わすことにする。
i への経路、したがって最短経路が存在しないときには、 td(i) = ∞ とする。

ステップ(1)で選ばれる節点 v ∈ V - S に対して、 d(v) = td(v) が成り立つことを数学的帰納法により、以下で証明する。

最初にステップ(1)が実行されるときを考える。
明らかに、 d(s) = td(s) = 0 が成り立つ。

k ≧ 1 とする。
第 1 回目から第 k 回目にステップ(1)が実行されるときに、いつもステップ(1)で選ばれる節点 v ∈ V - S に対して、
d(v) = td(v) が成り立つと仮定する。

236
デフォルトの名無しさん[]   投稿日:2017/01/02 19:05:35  ID:03PPbeGI.net(15)
第 (k+1) 回目にステップ(1)が実行されるときを考える。
このとき、明らかに #S = k であり、 ∀i ∈ S に対して、 d(i) = td(i) が成り立つ。
第 (k+1) 回目にステップ(1)が実行されるときに選ばれる節点を v ∈ V - S とする。
d(v) = ∞ である場合と d(v) ≠ ∞ である場合で場合分けして考える。

(1) d(v) = ∞ である場合。
td(v) ≠ d(v) = ∞ と仮定して矛盾を導く。
td(v) ≠ ∞ であるから、節点 s から節点 v への経路 s = v_0 → v_1 → … → v_(l-1) → v_l = v が存在する。
明らかに、 td(v_0), td(v_1), …, td(v_(l-1)), td(v_l) ≠ ∞ である。
v_0 ∈ S, v_l ∈ V - S であるから、 v_i ∈ S, v_(i+1) ∈ V - S となるような i が存在する。
∀j ∈ V - S に対して、 d(j) = ∞ であるから、 d(v_(i+1)) = ∞ である。また、 v_i ∈ S であるから、
d(v_i) = td(v_i) ≠ ∞ が成り立つ。
v_i がステップ(2)で S に追加されたときのことを考えれば分かるように、 (v_i, v_(i+1)) ∈ E かつ v_(i+1) ∈ V - S であるから、
d(v_(i+1)) = ∞ ということはない。これは矛盾である。
よって、 d(v) = td(v) = ∞ が成り立つ。

237
デフォルトの名無しさん[]   投稿日:2017/01/02 19:05:51  ID:03PPbeGI.net(15)
(2) d(v) ≠ ∞ である場合。
td(v) ≠ d(v) と仮定して矛盾を導く。
ステップ(2)を考えれば明らかなように、 d(v) ≠ ∞ であるから、節点 s から節点 v への
最短経路 s = v_0 → v_1 → … → v_(l-1) → v_l = v が存在する。
よって、 td(v) ≠ ∞ である。
仮定により、 td(v) ≠ d(v) であるから、 td(v) < d(v) が成り立つ。
v_0 ∈ S, v_l ∈ V - S であるから、 v_i ∈ S, v_(i+1) ∈ V - S となるような i が存在する。
td(v_(i+1)) < d(v_(i+1)) である。なぜなら、もし、そうでないと仮定すると、 d(v_(i+1)) = td(v_(i+1)) であるが、
td(v_(i+1)) ≦ td(v) < d(v) であるから、 d(v_(i+1)) < d(v) となってしまい、ステップ(1)での v の
選ばれ方に矛盾するからである。
v_i ∈ S であるから、 d(v_i) = td(v_i) である。
v_i がステップ(2)で S に追加されたときのことを考えれば分かるように、 (v_i, v_(i+1)) ∈ E かつ v_(i+1) ∈ V - S であるから、
d(v_i) + a_(v_i v_(i+1)) ≧ d(v_(i+1)) である。
一方、明らかに、 td(v_i) + a_(v_i v_(i+1)) = td(v_(i+1)) であるから、
td(v_(i+1)) = td(v_i) + a_(v_i v_(i+1)) = d(v_i) + a_(v_i v_(i+1)) ≧ d(v_(i+1)) となるが、これは矛盾である。
よって、 td(v) = d(v) が成り立つ。

238
デフォルトの名無しさん[]   投稿日:2017/01/02 19:06:08  ID:03PPbeGI.net(15)
以上より、第 (k+1) 回目にステップ(1)が実行されるときにも、ステップ(1)で選ばれる節点 v ∈ V - S に対して、
d(v) = td(v) が成り立つ。

S に追加される節点はすべて、ステップ(1)で選ばれた 節点 v ∈ V - S であり、一度 S に追加された節点 v の d(v) はそれ以後、
変更されないから、ステップ(1)でアルゴリズムが終了したとき、 ∀i ∈ S = V に対して、 d(i) = td(i) が成り立つ。

239
デフォルトの名無しさん[]   投稿日:2017/01/02 19:26:36  ID:03PPbeGI.net(15)
>232

ある本では、

正定数 c, n0 が存在して、 n ≧ n0 のとき、 T(n) ≦ c*f(n) であるなら、
T(n) は O(f(n)) であるという

と定義されています。

T(n) = n!
f(n) = n!
g(n) = (n-1)!

とします。

このとき、明らかに、
T(n) は O(f(n)) ですが、
T(n) は O(g(n)) ではありません。

240
デフォルトの名無しさん[]   投稿日:2017/01/02 19:29:54  ID:03PPbeGI.net(15)
したがって、

O(f(n)) と O(g(n)) は異なります。

241
デフォルトの名無しさん[sage]   投稿日:2017/01/03 08:33:06  ID:3o9M4oho.net
この狂人ヤバいなw

242
デフォルトの名無しさん[]   投稿日:2017/01/03 08:50:16  ID:hCDXc7Qp.net(10)
>224
>227

閉路を含まないから、各点を高々1回しか通らない。(端点も)

直通の経路が 1
途中でk個所を通過する経路が
 (n-2)(n-3)・・・・・(n-k-1) = (n-2)!/(n-k-2)!
だけある。ただし、k≦n-2
よって
a_n = (n-2)!{1 + 1/1! + 1/2! + … + 1/(n-2)!},

n ≧ 2 のとき、

(n-2)! ≦ (n-2)! * (1 + 1/1! + 1/2! + … + 1/(n-2)!) ≦ e * (n-2)!

したがって、

a_n = Θ((n-2)!)

である。

243
デフォルトの名無しさん[]   投稿日:2017/01/03 08:52:54  ID:hCDXc7Qp.net(10)
>234-238

のダイクストラのアルゴリズムの正しさの証明に間違いはないという
ことでOKですか?

244
デフォルトの名無しさん[]   投稿日:2017/01/03 11:39:58  ID:hCDXc7Qp.net(10)
Erik DemaineはMITの歴史上最年少で教授になったという天才だそうですね。

今、そのErik Demaineの2005年のダイクストラのアルゴリズムについての講義を見ています。

見終わったら、講義の要約について書きます。

245
デフォルトの名無しさん[]   投稿日:2017/01/03 13:47:58  ID:hCDXc7Qp.net(10)
ダイクストラのアルゴリズム:

01: d[s] ← 0
02: for each v ∈ V - {s}:
03: ■■d[v] ← ∞
04: S ← Φ
05: Q ← V
06: while Q ≠ Φ:
07: ■■u ← ExtractMin(Q)
08: S ← S ∪ {u}
09: for each v ∈ Adj[u]:
10: ■■if d[v] > d[u] + w(u, v):
11: ■■■■d[v] ← d[u] + w(u, v)

246
デフォルトの名無しさん[]   投稿日:2017/01/03 13:49:29  ID:hCDXc7Qp.net(10)
Correctness I:

d[v] の初期化の直後、およびLine 11の直後において、
すべての v ∈ V に対して、 d[v] ≧ δ(s, v) が
成り立つ。

証明:
d[v] の初期化の直後には、
d[s] = 0 かつすべての v ∈ S - {v} に対して、d[v] = ∞
が成り立っている。
δ(s, s) = 0 かつすべての v ∈ S に対して、 δ(s, v) ≦ ∞
であるから、d[v] の初期化の直後には、
すべての v ∈ V に対して、 d[v] ≧ δ(s, v) が確かに
成り立っている。

247
デフォルトの名無しさん[]   投稿日:2017/01/03 13:49:56  ID:hCDXc7Qp.net(10)
Line 11の直後において、すべての v ∈ V に対して、
d[v] ≧ δ(s, v) が成り立つことを背理法により示す。

Line 11の直後において、 d[v] ≧ δ(s, v) が
成り立たないような v ∈ V が存在するとする。
v をそのような点の中で、最初の点とする。

d[v] < δ(s, v)

d[v] < δ(s, v) ≦ ∞ であるから、
ダイクストラのアルゴリズムのLine 11は少なくとも1回は
実行されているはずである。そのような最後の実行を

d[v] ← d[u] + w(u, v)

とすると、

d[u] + w(u, v) = d[v] < δ(s, v)

が成り立つ。

一方、 d[u] ≧ δ(s, u) であるから、

d[u] + w(u, v) ≧ δ(s, u) + w(u, v)
≧ δ(s, u) + δ(u, v)
≧ δ(s, v)

が成り立つが、これは矛盾である。

248
デフォルトの名無しさん[]   投稿日:2017/01/03 13:51:21  ID:hCDXc7Qp.net(10)
Correctness Lemma:
s → … → u → v を s から v への一つの最短路とする。
d[u] = δ(s, u) であるとする。

このとき、Line10-11を実行すると、

d[v] = δ(s, v)

が成り立つ。

証明:
δ(s, v) = w(s → … → u) + w(u, v)
= δ(s, u) + w(u, v)
Correctness Iより、 d[v] ≧ δ(s, v)

(1)Line10-11の実行前に、 d[v] = δ(s, v) である場合。
Line10-11の実行後も d[v] = δ(s, v) である。

(2)Line10-11の実行前に、 d[v] > δ(s, v) である場合。
d[v] > δ(s, v) = δ(s, u) + w(u, v) = d[u] + w(u, v)
Line10-11の実行後は、 d[v] = d[u] + w(u, v) = δ(s, v)
となる。

249
デフォルトの名無しさん[]   投稿日:2017/01/03 13:52:06  ID:hCDXc7Qp.net(10)
Correctness II:
ダイクストラのアルゴリズムが終了したとき、
すべての v ∈ V に対して、 d[v] = δ(s, v) が成り立つ。

証明:
d[v] は v が S に追加された後は、不変である。
よって、 v が S に追加されたときに、
d[v] = δ(s, v) であることを示せばよい。

背理法で示す。
v が S に追加されたときに、 d[v] ≠ δ(s, v) であるような
v ∈ V が存在すると仮定する。
u をそのような点の中で、最初に S に追加された点とする:
d[u] ≠ δ(s, u)
Correctness Iより、
d[u] > δ(s, u)

250
デフォルトの名無しさん[]   投稿日:2017/01/03 13:52:49  ID:hCDXc7Qp.net(10)
今、 u が S に追加される直前の状況を考えることにする。
u はまだ S に追加されていないから、 u ∈ Q である。
p を s から u への一つの最短路とすると、 w(p) = δ(s, u) である。
s ∈ S, u ∈ Q であるから、 p 上の辺 (x, y) で x ∈ S, y ∈ Q となる
ような辺が存在する。そのような辺の一つを (x, y) とする。
すると、 p は以下のようになる。
p : s → … → x → y → … → u
x ∈ S であるから、 u に関する仮定より、
d[x] = δ(s, x) が成り立つ。また、明らかに、
s → … → x → y は s から y への一つの最短路であるから、
Correctness Lemmaより、 d[y] = δ(s, y) が成り立つ。
明らかに、 δ(s, y) ≦ δ(s, u) であるから、
d[y] ≦ δ(s, y)
また、Line07を見れば分かるように、
d[u] ≦ d[y] である。
よって、

d[u] ≦ δ(s, u) となるが、これは矛盾である。

251
デフォルトの名無しさん[]   投稿日:2017/01/03 13:55:46  ID:hCDXc7Qp.net(10)
Lec 17 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005
https://youtu.be/xhG2DyCX3uA

252
デフォルトの名無しさん[]   投稿日:2017/01/05 09:16:14  ID:4i7P3+nF.net(9)
アルゴリズムイントロダクションって自明なことをわざわざループ不変量を使ったりして、
証明していて、うざすぎますね。

253
デフォルトの名無しさん[]   投稿日:2017/01/05 09:16:52  ID:4i7P3+nF.net(9)
通常の数学の本なら自明で済ませるようなことをわざわざ証明している。
コメント1件

254
デフォルトの名無しさん[sage]   投稿日:2017/01/05 09:57:50  ID:OZq8Y/OW.net(3)
このバカ、以前も全く同じこと言って暴れたな。

255
デフォルトの名無しさん[sage]   投稿日:2017/01/05 10:02:39  ID:OZq8Y/OW.net(3)
http://hissi.org/read.php/tech/20160422/cGVtVmVaYUg.html
http://hissi.org/read.php/tech/20160612/YkttemlBQ3Y.html
こいつだ。

> って当たり前のことをループ不変とかを使って説明しているよね。はっきりいってくどい。
> ループ不変式とかいうのが出てくるけど、当たり前のことを形式的に証明しているだけで、つまらなすぎる。
> 馬鹿の一つ覚えみたいにループ不変式をつかって証明しようとしている。

これぞ「馬鹿の一つ覚え」である。

256
デフォルトの名無しさん[sage]   投稿日:2017/01/05 10:44:28  ID:W/+CAQrH.net(2)
数学とコンピュータ科学の区別がつかない厨房だろう

257
デフォルトの名無しさん[]   投稿日:2017/01/05 11:01:45  ID:4i7P3+nF.net(9)
クヌースの本なんかだと妙なくどさはない。

アルゴリズムイントロダクションはメリハリが全くない。
Trivialなこともそうでないことも平等に扱いすぎている。

要するに本を書くセンスがない。

258
デフォルトの名無しさん[]   投稿日:2017/01/05 11:02:52  ID:4i7P3+nF.net(9)
セジウィックとウエインの本のほうがずっとよい。

259
デフォルトの名無しさん[]   投稿日:2017/01/05 11:07:44  ID:4i7P3+nF.net(9)
日本語の本について言及しておく。
例えば、評判のよい茨木俊秀の本。

こんな薄いスカスカの本をよくも恥ずかしげもなく出版するものだとあきれる。

260
デフォルトの名無しさん[]   投稿日:2017/01/05 11:19:31  ID:4i7P3+nF.net(9)
アルゴリズムイントロダクションの悪口を書いたがいいところもある。

例えば、第29章線形計画法。

線形計画法に対しては、Trivialなこともそうでないことも平等に扱うという方針が
向いているように思う。

ただ、アルゴリズムの本に線形計画法を入れる理由が分からない。

整数論的アルゴリズムの章はあまりにも簡単すぎる。
高木貞治の本でも読んだ方がよい。

261
デフォルトの名無しさん[]   投稿日:2017/01/05 11:28:06  ID:4i7P3+nF.net(9)
結論として、ベストな本はクヌースが予定しているTAOCPの要約本ということになる。

262
デフォルトの名無しさん[sage]   投稿日:2017/01/05 11:29:47  ID:W/+CAQrH.net(2)
結論として4i7P3+nFはNG行き

263
デフォルトの名無しさん[sage]   投稿日:2017/01/05 11:33:33  ID:2uA+A+xC.net(2)
>253
自明ほど危ういものは無いんだが
コメント1件

264
デフォルトの名無しさん[sage]   投稿日:2017/01/05 11:40:35  ID:OZq8Y/OW.net(3)
例によって ID:4i7P3+nF が発狂しててワロタ

265
デフォルトの名無しさん[]   投稿日:2017/01/05 11:44:36  ID:4i7P3+nF.net(9)
>263

では、なぜ、一般に、コンピュータ科学者よりも頭が良いとされる数学者が
自明で済ませることが多いのでしょうか?

もし危ういのなら頭のよい数学者は自明などと書かないはずです。
コメント1件

266
デフォルトの名無しさん[sage]   投稿日:2017/01/05 11:52:58  ID:r7KPx/TL.net
そんな多くねえよちゃんと論文読め

267
デフォルトの名無しさん[sage]   投稿日:2017/01/05 12:06:11  ID:2uA+A+xC.net(2)
自明連発する方が馬鹿なのか

268
デフォルトの名無しさん[sage]   投稿日:2017/01/05 13:09:24  ID:c6xYhHVb.net(2)
>265
馬鹿丸出し

269
デフォルトの名無しさん[sage]   投稿日:2017/01/05 13:18:34  ID:c6xYhHVb.net(2)
>一般に、コンピュータ科学者よりも頭が良いとされる数学者が
根拠は?
>自明で済ませることが多いのでしょうか?
数学のコンテキストの話

そもそも証明の意味もコンピュータ科学と数学では違うだろ

270
デフォルトの名無しさん[sage]   投稿日:2017/01/05 14:56:52  ID:jagWiFjG.net
なんでバカって本質に関係ないところでギャーギャー騒ぐの?
コメント1件

271
デフォルトの名無しさん[sage]   投稿日:2017/01/05 14:58:54  ID:YjTG1plI.net
うむ

272
デフォルトの名無しさん[]   投稿日:2017/01/05 19:46:02  ID:4i7P3+nF.net(9)
アルゴリズムイントロダクションについて、数学が出来る人向けの本だという人がいる。
そして、数学ができない人はセジウィック&ウエインの本を読めという人がいる。

アルゴリズムイントロダクションが数学的な本だとは全く思わない。数学的な内容については
主に結果だけを書いている。

ただネチネチとアルゴリズムの正しさの証明が書かれているだけのこと。

クヌースの本のように、楽しい本ではない。
コメント1件

273
デフォルトの名無しさん[sage]   投稿日:2017/01/05 20:37:39  ID:UiiKd7HR.net

274
デフォルトの名無しさん[sage]   投稿日:2017/01/05 22:15:16  ID:WPj32BYO.net
書評したければ別のところでやれ

275
デフォルトの名無しさん[]   投稿日:2017/01/06 17:19:30  ID:TSHa+AxL.net(8)
再帰の除去についてやり方が詳しく書いてある本を教えてください。
コメント1件

276
デフォルトの名無しさん[]   投稿日:2017/01/06 17:43:03  ID:TSHa+AxL.net(8)
プログラミングコンテストチャレンジブック第2版のp.35
Lake Counting(POJ No.2386)

の解答として、以下のプログラムはあっていますか?

void dfs(i, j, n){
if(i < 0 || i >= N || j < 0 || j >= M){
return;
}
if(field[i][j] != 'W'){
return;
}
if(visit[i][j] == true){
return;
}
visit[i][j] = true;
dfs(i-1, j-1, n+1);
dfs(i-1, j, n+1);
dfs(i-1, j+1, n+1);
dfs(i, j-1, n+1);
dfs(i, j+1, n+1);
dfs(i+1, j-1, n+1);
dfs(i+1, j, n+1);
dfs(i+1, j+1, n+1);

if(n == 0){
count++;
}
return;
}

277
デフォルトの名無しさん[sage]   投稿日:2017/01/06 18:06:18  ID:XtKi9eaG.net

278
デフォルトの名無しさん[]   投稿日:2017/01/06 18:36:23  ID:TSHa+AxL.net(8)
Wrong Answerになっちゃうんだけど。

279
デフォルトの名無しさん[]   投稿日:2017/01/06 18:38:07  ID:TSHa+AxL.net(8)
例題については正しい答えが計算されるんだけど。

280
デフォルトの名無しさん[sage]   投稿日:2017/01/06 18:43:00  ID:LxnclcVs.net
よかったね

281
デフォルトの名無しさん[]   投稿日:2017/01/06 20:15:02  ID:TSHa+AxL.net(8)
>277

ソースレベルで再帰を除去する方法が知りたいんですが。

282
デフォルトの名無しさん[]   投稿日:2017/01/06 20:22:33  ID:TSHa+AxL.net(8)
秋葉らのプログラムでもWrong Answerになっていまします。

入出力の問題のようですね。

283
デフォルトの名無しさん[]   投稿日:2017/01/06 20:27:59  ID:TSHa+AxL.net(8)
入出力の問題ってやっかいですね。
出力がどうなっているかとかPOJでは調べられないんですか?

284
デフォルトの名無しさん[]   投稿日:2017/01/06 20:41:27  ID:TSHa+AxL.net(8)
なんなんだろう?

scanf,printfを使っていたらダメだったのが、cinとcoutにしたらOKになった。

285
デフォルトの名無しさん[]   投稿日:2017/01/08 12:26:37  ID:E98VLsZL.net(13)
F(p, n, r) の計算量を教えてください。

n: 整数
p, r: 整数配列(インデックス0からn-1)

F(p, n, r):
■■if r[n] ≧ 0:
■■■■return r[n]
■■if n == 0:
■■■■q = 0
■■else:
■■■■q = -∞
■■■■for i = 1 to n:
■■■■■■q = max(q, p[i] + F(p, n-i, r))
■■r[n] = q
■■return q
コメント1件

286
デフォルトの名無しさん[sage]   投稿日:2017/01/08 12:31:27  ID:0mVP2hZ6.net(2)

287
デフォルトの名無しさん[sage]   投稿日:2017/01/08 12:32:34  ID:0mVP2hZ6.net(2)

288
デフォルトの名無しさん[]   投稿日:2017/01/08 13:51:15  ID:E98VLsZL.net(13)
>286-287

ありがとうございます。

でも解説されていませんね。

289
デフォルトの名無しさん[]   投稿日:2017/01/08 13:57:19  ID:E98VLsZL.net(13)
どうやって計算量を見積もるんですか?

何を単位にするんですか?
コメント1件

290
デフォルトの名無しさん[]   投稿日:2017/01/08 14:06:13  ID:E98VLsZL.net(13)
T(n)
=
c1 + c2 * n + T(n-1) + … + T(0)
=
c1 + c2 * n + T(n-1) + c3*(n-1)

と解けばいいんですかね?
コメント1件

291
デフォルトの名無しさん[]   投稿日:2017/01/08 14:07:36  ID:E98VLsZL.net(13)
T(n) = c1 + c2*n + T(n-1)
T(0) = c3

この漸化式の解を求めればいいんですかね?

292
デフォルトの名無しさん[]   投稿日:2017/01/08 14:12:15  ID:E98VLsZL.net(13)
T(n)
=
[T(n) - T(n-1)] + [T(n-2) - T(n-3)] + … + [T(1) - T(0)] + T(0)
=
[c1 + c2*n] + [c1 + c2*(n-1)] + … + [c1 + c2*1] + c3
=
c1*n + c2*(1/2)*n*(n+1) + c3
=
Θ(n^2)

おお、あってるっぽいですね。

293
デフォルトの名無しさん[]   投稿日:2017/01/08 14:20:56  ID:E98VLsZL.net(13)
>290-292
は我ながら明解な解答ですが、

教科書では、以下のように導出しています。
この導出がよく分からないのですが。

「以前に解かれている部分問題を解くための再帰は直ちに戻るので、Fは
各部分問題をただ1度だけ解く。この手続きはサイズが0,1,....,nの部分問題
を解く。サイズがnの部分問題を解くために、for文がn回繰り返される。したがって、
Fの再帰呼び出し全体における、このfor文の繰り返し回数は等差数列を形成し、
総繰り返し回数はΘ(n^2)となる。」

294
デフォルトの名無しさん[]   投稿日:2017/01/08 14:26:56  ID:E98VLsZL.net(13)
あーあ、分かりました。

T(n)
=
c1 + c2 * n + T(n-1) + … + T(0)
=
c1 + c2 * n + T(n-1) + c3*(n-1)

このあたりのことを言っているんですね。

295
デフォルトの名無しさん[sage]   投稿日:2017/01/08 14:27:53  ID:rSxBm0q1.net
馬鹿には無理

296
デフォルトの名無しさん[]   投稿日:2017/01/08 14:28:32  ID:E98VLsZL.net(13)
>289

for文の繰り返し回数=計算量ですね。

297
デフォルトの名無しさん[]   投稿日:2017/01/08 14:29:42  ID:E98VLsZL.net(13)
結局自分ですべて解決してしまいました。

298
デフォルトの名無しさん[sage]   投稿日:2017/01/08 17:12:11  ID:8OGZNgRf.net
よくやった
褒美として自分専用のスレを立てる権利をやろう

299
デフォルトの名無しさん[sage]   投稿日:2017/01/08 18:45:26  ID:KkEYpXLY.net
命名ID:E98VLsZは俺様

300
デフォルトの名無しさん[]   投稿日:2017/01/08 20:55:21  ID:E98VLsZL.net(13)
プログラミングコンテストチャレンジブック

p.45 Best Cow Lineっていう問題の解答のプログラムって無駄がありますよね。

この本を難しいという人がいますが、そんなに難しいですかね?

301
デフォルトの名無しさん[]   投稿日:2017/01/08 22:46:42  ID:E98VLsZL.net(13)
プログラミングコンテストチャレンジブック
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
最強最速アルゴリズマー養成講座

この3冊に共通していることですが、日本語が下手ですよね。

一番ひどいのが

最強最速アルゴリズマー養成講座

ですね。
コメント1件

302
デフォルトの名無しさん[]   投稿日:2017/01/08 22:50:51  ID:E98VLsZL.net(13)
一番面白いのは、

プログラミングコンテストチャレンジブック

だと思いますけど、例えば、貪欲法でなぜうまくいくのかの証明が書いてないですね。

303
デフォルトの名無しさん[sage]   投稿日:2017/01/08 22:51:13  ID:Qw43e7Zm.net
ここはプログラミング問題集書評のスレなの?

304
デフォルトの名無しさん[]   投稿日:2017/01/09 06:08:00  ID:JOAqSyBk.net
>301
うむ
日本語下手なのはもちろん英語も下手みたいだな

305
デフォルトの名無しさん[sage]   投稿日:2017/01/09 06:09:36  ID:cSodeH17.net
頭の使い方が下手というかそもそも頭が不自由なんだろう

306
デフォルトの名無しさん[]   投稿日:2017/01/09 10:59:50  ID:TqLncjlX.net(6)
アルゴリズムイントロダクションの練習問題15.1-3の解答って以下であっていますか?

BOTTOM-UP-CUT-ROD(p, c, n)
1 r[0..n] を新しい配列とする
2 r[0] = 0
3 for j = 1 to n
4 ■■q = -∞
5 ■■for i = 1 to j-1
6 ■■■■q = maxx(q, p[i] + r[j-i] - c)
7 ■■q = max(q, p[j])
8 ■■r[j] = q
9 return r[n]

307
デフォルトの名無しさん[]   投稿日:2017/01/09 11:02:45  ID:TqLncjlX.net(6)
15.1-2

反例

p[1] = 1
p[2] = 5
p[3] = 7

308
デフォルトの名無しさん[]   投稿日:2017/01/09 13:21:16  ID:TqLncjlX.net(6)
F_0 = 0
F_1 = 1
F_i = F_(i-1) + F_(i-2) (i≧2)

F_n を O(n) 時間で計算する動的計画アルゴリズムを設計せよ。
対応する部分問題グラフを描け。
このグラフにはいくつの頂点と辺が存在するか?


↑はアルゴリズムイントロダクションの練習問題15.1-5なんですけど、
なんか簡単すぎるようにみえるんですけど、落とし穴があるんですかね?

なんでΘ(n)じゃなくてO(n)と書いてあるんですかね?
コメント1件

309
デフォルトの名無しさん[]   投稿日:2017/01/09 13:34:48  ID:TqLncjlX.net(6)
配列を使わないとDPとは言えないですか?
配列いらないですよね。
でもi = 0〜nに対して、F[i]が求まるという意味はありますね。


F[0] = 0
F[1] = 1
for i = 2 to n
■■F[n] = F[n-1] + F[n-2]

明らかにΘ(n)ですよね。

部分問題グラフは以下ですよね:

http://imgur.com/WUQMG8R.jpg

#V = n + 1
#E = 2*(n - 1)

ですね。

310
デフォルトの名無しさん[]   投稿日:2017/01/09 13:37:23  ID:TqLncjlX.net(6)
あ、ひっかけがありましたね。
訂正します:

n > 0 のとき、

#V = n + 1
#E = 2*(n - 1)

n = 0 のとき

#V = n + 1
#E = 0

ですね。

311
デフォルトの名無しさん[]   投稿日:2017/01/09 15:27:31  ID:TqLncjlX.net(6)
アルゴリズムイントロダクションに、以下の事実を1955年にRobbinsが発見したと書いてあります。

--------------------------------------------
すべての n ≧ 1 に対して

n! = sqrt(2*π*n) * (n/e)^n * exp(α_n)

と書ける。

ただし、 1/(12*n+1) < α_n < 1/(12*n)
--------------------------------------------

本当にこんな比較的簡単にみえる結果が1955年という比較的最近になって発見された
のでしょうか?
コメント1件

312
デフォルトの名無しさん[]   投稿日:2017/01/09 15:37:47  ID:4OeNzyzM.net
>308
フィボナッチだろ
√5が出て来る公式
O(1)になるかも試練が

313
デフォルトの名無しさん[sage]   投稿日:2017/01/09 15:46:27  ID:FSSb8O2Z.net
>311
      r ‐、
      | ○ |         r‐‐、
     _,;ト - イ、      ∧l☆│∧  良い子の諸君!
    (⌒`    ⌒ヽ   /,、,,ト.-イ/,、 l  
    |ヽ   ~~⌒γ ⌒ ) r'⌒ `!´ `⌒) よく頭のおかしい数学者気取りのバカが
   │ ヽー―'^ー-'  ( ⌒γ ⌒~~ / 「誰も気付かなかった事を発見したことを発表」とほざくが
   │  〉    |│  |`ー^ー― r' | 大抵それは「先人が思いついたけどあえて発表しなかった」ことだ
   │ /───| |  |/ |  l  ト、 |  王道が何故面白いか理解できない人間に面白い話は
   |  irー-、 ー ,} |    /     i 作れないぞ!
   | /   `X´ ヽ    /   入  |

314
デフォルトの名無しさん[]   投稿日:2017/01/10 20:16:10  ID:Zd0v4023.net
アルゴリズムイントロダクションが難しいという人がいますけど、
この本は馬鹿丁寧に書かれていますよね。

いわゆる「書きすぎ」ですね。

「書きすぎ」れば分かりやすくなると思い込んでいますね、著者らは。

315
デフォルトの名無しさん[sage]   投稿日:2017/01/10 20:19:42  ID:kxFYGz06.net
http://hissi.org/read.php/tech/20160614/U2lCYS9zNTM.html

マジ基地だな。壊れたレコードかよ。

316
デフォルトの名無しさん[sage]   投稿日:2017/01/13 21:58:42  ID:wiy2qrIv.net
プログラミング言語のパーサーってどういう仕組みで動いてるんですか?
文字列をトークンの配列に分ける
特定のパターンにマッチするトークンの部分集合をひとまとめにして新しいトークンに置き換える
再帰的に同じ事を繰り返す
こんな感じ?
コメント1件

317
デフォルトの名無しさん[sage]   投稿日:2017/01/13 22:37:46  ID:+ExxsU2F.net

318
デフォルトの名無しさん[sage]   投稿日:2017/01/14 00:10:28  ID:H4kTcvBH.net
>317
これ考えた奴は天才だな

319
デフォルトの名無しさん[sage]   投稿日:2017/01/16 17:57:37  ID:YH2Bx58z.net
Lisperか
BNF

320
デフォルトの名無しさん[sage]   投稿日:2017/01/19 09:40:05  ID:uhfgjGGl.net
更新情報
・スレッド一覧ページで過去ログのタイトル検索・一覧表示ができるようになりました(2016/1/20)
NGワード登録
登録する
スレッド内検索

プログラム板 タイトル検索

このスレッドが人気です(実況系)
実況 ◆ TBSテレビ 26968 江藤愛は韓国の汚職事件より焼肉店の御食事券 (368)TBS実況
バイキングとグッディ★1 (625)フジ実況
実況 ◆ テレビ朝日 46571 大下さんの前スレ (949)テレ朝実況
羽鳥慎一モーニングショー★4 (979)テレ朝実況
実況 ◆ 日本テレビ 54018 (427)NTV実況
白熱ライブ ビビット★1 (659)TBS実況
実況 ◆ フジテレビ 82446 修正 (352)フジ実況
連続テレビ小説 ベっぴんさん★147 (506)NHK実況
このスレッドが人気です(ニュース系)
【東京】「降りま〜す」 乗客タックルでケンカ勃発 通勤時間帯の東急・田園都市線が大幅遅れ (468)ニュー速+
【歴史戦】「中国に負けるな」 アパホテル書籍、ネットで反響広がる★4 (1000)ニュー速+
【朝日新聞】アパホテル問題で「右翼ホテル」「日本の一部勢力が歴史を直視せず」と中国の意見を取上げて報道 (171)ニュー速+
【歴史戦】「中国に負けるな」 アパホテル書籍、ネットで反響広がる★3 (1000)ニュー速+
【政治】駐韓大使帰任に慎重 安倍首相「外務省は早く帰したがっているが、早く帰す必要はない。国民も納得しない」★25 (721)ニュー速+
【芸能】もう話題にもならず…のん、頼りは岩手だけの危機的状況 (514)音楽・芸能ニュース
【社会】AV出演拒否で女性に賠償請求の提訴をした弁護士に「懲戒審査相当」の日弁連異例の決定 (375)ニュー速+
【社会】「森のくまさん」作詞者(72)「替え歌で人格権を侵害された」 芸人のパーマ大佐らに慰謝料300万円請求★2 (479)ニュー速+
プログラム板の人気スレ
【統計分析】機械学習・データマイニング11 (926)
C++相談室 part129 (172)
Excel VBA 質問スレ Part45 (228)
C言語なら俺に聞け 138 (562)
Xamarin Part3 (241)
ふらっと C#,C♯,C#(初心者用) Part126 (246)
Visual Studio 2015 Part7 (987)
【PHP】下らねぇ質問はここに書き込みやがれ 7 (624)
Androidプログラミング質問スレ revision52 (549)
くだすれPython(超初心者用) その31 (821)
クラス名・変数名に迷ったら書き込むスレ。Part27 (740)
次世代言語議論スレ【Go Rust Haskell Scala Erlang Elixir】 (466)
推薦図書/必読書のためのスレッド 80 (950)
スレ立てるまでもない質問はここで 145匹目 (86)
+ JavaScript(ECMAScript)質問用スレッド vol.122 + (976)
☆★Java質問・相談スレッド179★★ (560)
Swift part9 (582)
Ruby 初心者スレッド Part 59 (551)
人工知能ディープラーニング機械学習のための数学 (105)
VRプログラム雑談【Unity/UnrealEngine】【HTC Vive/Oculus Rift/その他VR】 (347)
+ JavaScript の質問用スレッド vol.122 + (628)
プログラミング言語 Rust 2 (310)
Java入門・初心者質問スレ Part.2 (296)
【JavaScript】スクリプト バトルロワイヤル55【php,py,pl,rb】 (459)
Win32API質問箱 Build123 (332)
Swift part7 (1026)
テストしにくいコードをテストする方法 その2 (51)
【初心者歓迎】C/C++室 Ver.100【環境依存OK】 (234)
このサイトについて
このサイトは2ちゃんねるからデータを取得し、表示するサービスです。
画像のインライン表示機能について
画像のURLの後ろにある[画像をインライン表示]をクリックすると、URLの下に表示します。
表示される画像は横幅100pxに縮小されていて、クリックすると原寸で表示します。
このサイトの特徴
1)スレッド内検索ができます
2)レス(「>>1」など)のポップアップができます
3)不適切な言葉を含む投稿を表示しません
4)ページ内で画像を直接表示できます
5)2ch他スレッドへのリンクはタイトル・板名つきでリンクします
6)すっきりとしたデザインで表示します
7)最新スレや前スレをチェック・一覧表示します
8)NGワード機能の搭載でイヤな言葉が目に入りません
9)荒らしを自動チェックします
10)スレッド内・同一IDの書き込みだけ表示できます
11)レスの返事をレスされた発言の下に表示する「まとめビュー」が利用できます
12)シリーズ化したスレッドの一覧を表示します
13)最新のスレッドがある場合はお知らせします
削除について
こちらをご覧ください
機能要望について
現在機能要望受付中です。
問い合わせについて
こちらのページからどうぞ
Amazon


このサイトは2ch.scからデータを取得・表示しています。削除などについてはこちらをご覧ください。 アクセスモード:差分取得 - 正常取得 - 23件 - 取得完了