データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net

◆QZaw55cn4c · 2018/02/04(日) 00:44:42.44

ああ、でも C++ はテンプレートの世界観に移行してしまったので、デザパタ、今はあんまり使いません！

**デフォルトの名無しさん** · 2018/02/25(日) 14:54:54.10

>>793
アルゴリズムの話するときの共通語が必要になって
ついでに良し悪しもまとめておこうという話になった

**デフォルトの名無しさん** · 2018/02/25(日) 16:52:44.22

アルゴリズムとパターンて違うんじゃね？

**デフォルトの名無しさん** · 2018/02/25(日) 18:39:48.45

デザインパターンそこに至る考え方を身につけないと
というわけで、オブジェクト指向のこころをオススメしとく

**デフォルトの名無しさん** · 2018/02/25(日) 18:59:31.93

>>798
書評読んでもなかなかよさげだな

**デフォルトの名無しさん** · 2018/03/05(月) 21:38:39.67

『アルゴリズムイントロダクション』を読んでいます。

ヒープソートのところに、

「サイズ n のヒープ上の MAX-HEAPIFY の最悪実行時間が Ω(lg n) であることを示せ。」

という問題があります。

最悪実行時間が Θ(lg n) であることはすぐに分かります。
なぜ、 Ω(lg n) であることを示せという問題なのでしょうか？

最悪実行時間や最良実行時間については、 Θ 記法で書くのが自然だと思います。

**デフォルトの名無しさん** · 2018/03/06(火) 01:54:34.90

まるちんこ

**デフォルトの名無しさん** · 2018/03/07(水) 21:29:45.52

セジウィックさんはいい加減ですね。

近代科学社から出ている『アルゴリズムC』の最小全域木のところを読んでいますが、
同じ重みの辺が2つ以上あると議論が破綻するところがありますね。

Wayneさんと共著の『Algorithms』では、すべての重みが異なるという仮定をおいていますね。

いずれにしてもひどい本です。

**デフォルトの名無しさん** · 2018/03/07(水) 21:31:54.51

キミはまだアルゴリズムの勉強していたのか。

人には向き不向きというのがあってだな。

**デフォルトの名無しさん** · 2018/03/07(水) 21:33:49.91

すべての重みが異なるというのは異常な仮定ですよね。

**デフォルトの名無しさん** · 2018/03/07(水) 22:27:03.62

茨木俊秀著『アルゴリズムとデータ構造』を読んでいます。

この本のクラスカルのアルゴリズムの正しさの証明に使われる補題の証明ですが、
読んでも分からなかったのですが、やはりおかしかったんですね。

同じ著者の『Cによるアルゴリズムとデータ構造』を読むと補題の証明が修正されています。

この分野っていい加減な本が多いですよね。

**デフォルトの名無しさん** · 2018/03/08(木) 19:38:26.94

任意の連結無向グラフ G = (V, E) は |E| ≧ |V| - 1 を満たすことを示せ。

**デフォルトの名無しさん** · 2018/05/12(土) 10:59:28.10

共同ツール 1
https://seleck.cc/685

https://trello.com/
ボードのメニュー → Power-Upsから拡張可能 Slack DropBoxなど
Trello Chrome拡張機能　elegant
ttp://www.kikakulabo.com/service-eft/
trelloのオープンソースあり

共同ツール 2
https://www.google.com/intl/ja_jp/sheets/about/

共同ツール 3
https://slack.com/intl/ja-jp
https://www.dropbox.com/ja/
https://bitbucket.org/
https://ja.atlassian.com/software/sourcetree
https://sketchapp.com/extensions/plugins/
ttp://photoshopvip.net/103903

ttps://goodpatch.com/blog/sketch-plugins/

**デフォルトの名無しさん** · 2018/05/23(水) 20:11:35.70

僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法　モニアレフヌノ』

BU06O

**デフォルトの名無しさん** · 2018/06/24(日) 11:32:17.25

AVL木について詳しく載っている本は何ですか？

**デフォルトの名無しさん** · 2018/06/24(日) 14:42:02.78

詳しいと言えるかどうかは別にしてAVL木に関する説明が分かりやすいと思ったのは次の本の該当箇所（§6.3）だ

浅野哲夫『データ構造』、アルゴリズムシリーズ１、近代科学社 (1992)

**デフォルトの名無しさん** · 2018/06/24(日) 15:07:06.81

ステマ

**デフォルトの名無しさん** · 2018/07/04(水) 22:09:33.44

C5O

**デフォルトの名無しさん** · 2018/07/05(木) 16:33:38.42

C5O

**デフォルトの名無しさん** · 2018/07/21(土) 20:42:50.98

1つ言えるのはオブジェクト指向のなんかよりも
データ構造とアルゴリズムの方がよっぽど重要だということ。
昔はオブジェクト指向の勉強を頑張っていたけどそのときは
全然プログラミングがうまくならなかった。
現代の世の中はガチガチに設計されたライブラリを使って
コードを書くだけだから生半可なオブジェクト指向の知識なんて
ゴミ同然だよ。80年代90年代に考えられた思想とか、もうゴミに
なってしまった思想が多くて有害だよ。
結局現場でやることは「メソッドの使い方を求めてQiitaやStack OverFlowを
漁って成功するコードを見つけるまで疲れ果てる」ことに変わりはない。
せっかく勉強した内容が時代遅れで「裏切られる」ことのほうが多い。

**デフォルトの名無しさん** · 2018/07/21(土) 20:51:29.70

一方、データ構造とアルゴリズムをガッツリと勉強してから
様々なデータ構造の使い方、問題の解決がうまくなった。
ブロックチェーンのアルゴリズムの理解や
データ分析の数学的演算がコーディング
できるようになってプログラミングが格段に楽しくなった。
スマートにオブジェクト指向で設計する力なんかより
「ゴリゴリとアルゴリズムを書く力」の方がよっぽど重要。
「再利用性」？「変更の影響」だって？そんなものゴミだね。
それは自分以外の人間のメリットのための技術であって、
自分へ還元されるためのメリットではない。
再利用性は自分の書いたコードなら信頼できるしコピペして使えばいい。
自分の書いたコードのコピペは全然ありだと思う。
適したメソッドが見つからなかったらQiitaを漁ったりせずに
自分でゼロから実装したほうが速い。
その場で手っ取り早くコードを生成しているから、
どんな既存コードにも頼っていないから俺の実装したコードは
依存性は低い。

**デフォルトの名無しさん** · 2018/07/21(土) 21:29:45.12

ただし>>814-815は何かのアプリを作ったことはない

◆QZaw55cn4c · 2018/07/21(土) 21:58:56.02

>>815
一つ重要な視点を提供しましょうか
自分の記憶などあてになりません、3ヶ月前自分が書いたコードは、もはや他人が書いたコードとなんら変わりありません

**デフォルトの名無しさん** · 2018/07/21(土) 22:06:10.19

>>814-815はすでに解いたことのある問題なら
忘れたとしても、少し時間をかければ解けると考えている

つまり誰かが出した出題を解くという作業をしている

**デフォルトの名無しさん** · 2018/07/21(土) 22:34:33.64

>>>817, 818
自分のいつも使うアルゴリズムのパターンが身についていれば
そのパターンや命名規則から何をやっているかは解読できる。
読みにくくなるのは外部から取り込んだ機能の実行や
継承している部分。

**デフォルトの名無しさん** · 2018/07/21(土) 23:12:43.54

>>819
やっぱり「解読」してるんだｗ

すでに証明済みの問題を自分の力で証明するという
お勉強をやってるだけだね

**デフォルトの名無しさん** · 2018/07/21(土) 23:21:07.94

研究者で無い限り新しい証明考える必要ないっしょ

**デフォルトの名無しさん** · 2018/07/21(土) 23:22:28.87

解読の工程は業務でも必要であるし
遊びとしても面白い
それが勉強になるならとても有益じゃん

**デフォルトの名無しさん** · 2018/07/21(土) 23:34:47.51

「車輪」は大きさ、材質、シャフトの接合部の形、色…大まかな形や役割は似ているが微妙に違うものが無数にある。
ちょっとでもこれらの特徴がずれたものは他への転用を考えるとすぐに不具合となって使い物にならない。
車輪を最初に「発明」した人物はこれらの無数の車輪を全て発明したわけではない。
だから他の人が死ぬほど似たようなものを作っていたとしても自分で作る必要がある。
他人が作った車輪は無条件で役にたつわけがない、
手直しして組み込むより「自分の規格で」作った方が早い。

**デフォルトの名無しさん** · 2018/07/21(土) 23:43:56.82

車輪ってすごいな

**デフォルトの名無しさん** · 2018/07/22(日) 00:34:31.50

車輪が小さかったからゴム巻いたらなんとかなった
これがオブジェクト指向です

**デフォルトの名無しさん** · 2018/07/22(日) 02:15:34.77

時代が違うからな。アルゴリズム考えてうんうん唸る時代は終わってるんだよ
今はそういうアルゴリズムが実装されたライブラリを組み合わせて
アプリを作る時代だってMITも言ってる

MIT｢今は基礎よりﾗｲﾌﾞﾗﾘ組み合わせてｱﾌﾟﾘ作る時代｣ [無断転載禁止]©2ch.net
https://medaka.5ch.net/test/read.cgi/prog/1462443213/

MITがSICPを教えなくなった理由
http://cpplover.blogspot.jp/2016/05/mitsicp.html

今日では、状況が変わっている。

今のエンジニアは、自分が完全に理解していない複雑なハードウェアのための
コードを日常的に書いている（そして、大抵の場合、企業秘密により完全に理解するのは不可能である）。

ソフトウェアでも状況は同じだ。プログラミング環境は、多大な機能を提供する
巨大なライブラリ群の集合として存在している。

Sussmanの今日の生徒は、その時間の大半を、ライブラリのマニュアルを読み、
どのように組み合わせれば目的が達成できるのかを把握することに費やしている。

Sussman曰く、今日のプログラミングは、「より科学に近い。ライブラリを持ち寄って、
つっつき回すのだ。プログラムを書くには、突っつき回して、どのように動作するかを観察する。
そして、「目的を達成するために改造できるか」と考えるのだ」。

SICPの「合成による解析」という物の見方である、小さな、単純な部品を組み合わせて大きなシステムを作るということは、
もはや今日の状況にそぐわなくなった。今や、我々のプログラミングはつっつき回すことで行われている。

**デフォルトの名無しさん** · 2018/07/22(日) 06:06:47.04

車輪の再利用だけ考えて車輪職人が居なくなるって話かな？

**デフォルトの名無しさん** · 2018/07/22(日) 06:11:43.36

そうだね。そもそもソフトウェアは他の製品と違って
完全に同じものを複製するのに技術がいらないからね
コピーすればいいだけだし。

その点、何かを作る職人とはぜんぜん違うよね
そいういう寸分違わないものを作り出す職人は不要な業界

**デフォルトの名無しさん** · 2018/07/22(日) 09:02:23.96

>>825
そして、今は鉄道以外のほぼすべてのタイヤの接地面はゴムです。
そういうところもオブジェクト指向と、似てますね。

**デフォルトの名無しさん** · 2018/07/22(日) 09:20:35.56

以上、内容無し

**デフォルトの名無しさん** · 2018/07/22(日) 13:32:55.77

>>826
この論理は完全にお花畑。
完全無欠のライブラリがありそれが唯一無二なら
つつっつき回すだけでいいだろうさ。
だけど現実はほぼ似たような機能で構文が違う、
それに加え実行環境もバージョンも違うライブラリたちが乱立してるんだぜ、
それに加わりローカルで作られた野良ライブラリがある。
当然人によってそれらの使い方の認識に齟齬が生まれる。
信用できるのは、自身の即興のデータ構造定義能力と、
アルゴリズム構築能力だけだ。

**デフォルトの名無しさん** · 2018/07/22(日) 13:34:08.83

今必要なのは解読ではなくて解脱

**デフォルトの名無しさん** · 2018/07/22(日) 14:02:08.11

>>831
> だけど現実はほぼ似たような機能で構文が違う、
> それに加え実行環境もバージョンも違うライブラリたちが乱立してるんだぜ、

乱立しているからなんだっていうんだろう？
乱立してるから自分で作れってことにはならないよな？
何が言いたいんだろう

> それに加わりローカルで作られた野良ライブラリがある。

自分自身で作成したもの = 他人から見れば野良ライブラリだからね
野良ライブラリは作るべきじゃないね

だから乱立されている中のどれかを使うってことになるわけだけど
そういう結論を言いたかったんだよね？

**デフォルトの名無しさん** · 2018/07/22(日) 14:02:42.93

>>831
データ構造作るだけだと付加価値が低いというか
ただの作業員でしかなくない？
新しい仮想通貨作るとかだったらすごいけど

**デフォルトの名無しさん** · 2018/07/22(日) 14:06:57.17

まあ言えるのは、データ構造やアルゴリズムを作るだけの仕事なんて無いってことだな

やりたいからといって、それで金がもらえるわけじゃない
金を出す方がやってもらいたいことをやって金が出る

似たようなものを自作して、乱立させたって
そんなものに金を出す人はいない

**デフォルトの名無しさん** · 2018/07/22(日) 14:18:22.79

>>835
うむ

>>834
やったことないやつには判らんよ

**デフォルトの名無しさん** · 2018/07/22(日) 14:24:06.48

座禅だな

**デフォルトの名無しさん** · 2018/07/22(日) 17:42:32.79

>>827
いや、ちょっと違う
プログラマという職業が、車輪を一から設計できる職人群と
それを再利用する専門家へと二極化していくというお話だよ

この二極化は以前から言われていたことだけど、
それを天下のMITが言い切って行動に移したことに>>826の意義がある

◆QZaw55cn4c · 2018/07/22(日) 18:20:24.01

>>838
「職人」と「専門家」が逆ではないですか？

**デフォルトの名無しさん** · 2018/07/22(日) 19:59:44.17

いや、逆ではないよ

MITは計算機工学に特化しているわけでもなく、
機械工学、ロボティクス、生産工学、データ解析といった
あらゆる工学分野の専門家を養成し輩出している

そういった(計算機工学を除く)大半の「専門家」の卵達にとって、
優先すべきは(旧コースでSchemを使って学んでいた)計算機の動作原理ではなく、
計算機の利用方法である、という趣旨
彼ら「専門家」は決して計算機工学の専門家ではないが、
それぞれの分野に特化した高度な専門技術を有し、
与えられた問題を解決する道具として計算機を効果的に活用できる

**デフォルトの名無しさん** · 2018/07/22(日) 20:38:21.89

役割が細分化したからそのニーズに応じたという話？

**デフォルトの名無しさん** · 2018/07/22(日) 21:07:14.12

どんな仕事でも、その道の研究者ってのはいるだろう。
例えば数学者とかな。だけど世の中で必要とされてるのは
塾の数学の先生だったりするわけさ

もっとも大学に行った人の殆どは、大学で専攻していたものとは
関係のない仕事をしているわけだけどな

**デフォルトの名無しさん** · 2018/07/22(日) 21:23:40.76

数学とコンピュータを一緒にするなよｗ

**デフォルトの名無しさん** · 2018/07/22(日) 23:03:00.98

たとえばjsでオブジェクト構造をサーバに送りたいとする。
たったこれだけのことなのに邪魔くさい余計な機能が多すぎる。
わざわざ専用のクラスからインスタンス作って
専用の構文使ったりhttpヘッダー設定したりだ。
それでいてサーバ側では糞みたいな細かい仕様認識の違いでリクエストの内容が空だったりする。
サーバ側のコンフィグ見直したりjs側のコード見直したりするわけだ。
ログからライブラリのコード追っていくと大抵
過剰に技法使われてるから自ずと疑うべき探索
範囲は広くなる。
書き方はjQueryベースやangular typescriptなんかが混在してきて文法のちょっとした勘違いなんてのも生まれてくる。
だったらそんなライブラリ鼻っから信用しなけりゃいい。
ライブラリのインスタンスを介さずに多少原始的だが
文字列、数値 for文if文だけで大抵の問題は解決できる。
自力でJSON文字列に情報をぶち込んで送信してやれば、必ずサーバ側で取得できる。
サーバ側も下手なライブラリにパースさせないで自力でパースした方が慣れれば断然こちらの方が早い。
自力で作ったアルゴリズムは信用できるから
関数化しておいてまた似たような問題があったときに
使える。
俺が使うための自作ツールは他人は使わなくていいよ、どうせ価値観が違うんだからな。
自分で作ったもの以外はそりゃ不便だろうよ。

**デフォルトの名無しさん** · 2018/07/22(日) 23:31:00.85

> たとえばjsでオブジェクト構造をサーバに送りたいとする。

https://api.jquery.com/jquery.post/

$.post( "test.php", { name: "John", time: "2pm" } );

こうだね。で？

**デフォルトの名無しさん** · 2018/07/22(日) 23:37:38.62

それjqueryやんw

**デフォルトの名無しさん** · 2018/07/22(日) 23:58:50.05

はい。このように他人の成果を利用して
目的を達成するのが今は重要って話です。

**デフォルトの名無しさん** · 2018/07/23(月) 00:05:17.20

>>844
> だったらそんなライブラリ鼻っから信用しなけりゃいい。

とりあえずお前が自力で作ったライブラリは
鼻っから信用しててないよ

**デフォルトの名無しさん** · 2018/07/23(月) 00:19:04.74

>>844
> 俺が使うための自作ツールは他人は使わなくていいよ、どうせ価値観が違うんだからな。
> 自分で作ったもの以外はそりゃ不便だろうよ。

価値観の問題じゃない。単にお前が作ったコードに
バグがあるから使えないだけ。使わないんじゃない。使えない。

反論するならバグがない証拠を出すこと
テストコードをかけという話ね。

> だったらそんなライブラリ鼻っから信用しなけりゃいい。
お前が書いたコードは鼻っから信用できない。するしないじゃない。できない。

**デフォルトの名無しさん** · 2018/07/23(月) 06:43:27.98

みなさんお気づきだろうか
>>844と>>849は同じことを言っている

**デフォルトの名無しさん** · 2018/07/23(月) 07:32:08.19

jQueryはブラウザの差異を吸収するからね
同等のもの作ろうとしたら大変だよ

自前のコードを実装するのが汎用ライブラリを使うよりも早いとするなら
自前のコードは汎用ライブラリよりも機能が少ないものになる

要件がシンプルなら自作するのは効率が良いかもしれないね

システムをユーザのニーズに合わせてたら要件が複雑になり自作するメリットが得られない
ユーザがシステムの都合を忖度するならうまくいく
開発者にとっては桃源郷

開発者の幸せか、ユーザの幸せか
ぼくらはその選択を迫られてるんだ

**デフォルトの名無しさん** · 2018/07/23(月) 09:47:19.69

役所が作る神エクセルなんてのはユーザがシステムの都合に合わせてる典型例じゃないか、自作コードに拘るのは神エクセルを作るのと変わらぬよ

**デフォルトの名無しさん** · 2018/07/23(月) 11:01:38.63

>>842
自己紹介ですね

**デフォルトの名無しさん** · 2018/07/23(月) 12:24:24.98

>>851
> 要件がシンプルなら自作するのは効率が良いかもしれないね
それは正しくない。要件はシンプルでも実装が大変なことがある。
そもそも「ライブラリの一機能の独自実装」などという要件は
実際には発生しない。これらは単に道具

要件を実装するのに、道具を使うか使わないかの問題
シンプルな要件でも、道具は使ったほうが効率は良いよ

もちろん道具を使えない人であれば、道具を使えるようになるまで時間が
かかるけど、それは素人がプロに速度でかなわないという人間の問題にすぎない
そう道具を使えないなら素人なんだよ。

**デフォルトの名無しさん** · 2018/07/23(月) 12:29:27.63

>>850
ヒント：バカは皆がオンリーワン

**デフォルトの名無しさん** · 2018/07/23(月) 12:36:13.41

>>850
同じことは言ってないな

>>844はよくわからないのはライブラリのせいだ
自分で作れば、そのライブラリよりもわかりやすくなるはずだ
って机上の空論を言ってるだけ

**デフォルトの名無しさん** · 2018/07/23(月) 13:54:17.34

PGの愚痴

**デフォルトの名無しさん** · 2018/07/23(月) 15:02:52.51

りんごをむくのにピーラーを使うのもいいが、一度ナイフで剥くのを試すのも重要だし、かじってみるのもいい。
道具が解決する問題がなんなのか、体験することは、多くの人にとって有益だと思う（経験主義者）

**デフォルトの名無しさん** · 2018/07/23(月) 15:32:18.18

そこでピーラーを作るのは大変だとか見当違いの所に流れていくやつがいる。

ピーラー（ライブラリ）を使うか、ナイフを使うかだ

ライブラリ？中見たけどわけのわからないことをしてる
理解できない。ナイフのほうが単純だ。ナイフなら作れる。
なぜか作る話になってしまっている。

**デフォルトの名無しさん** · 2018/07/23(月) 15:38:29.17

例え話では本質から遠ざかるばかりよ

**デフォルトの名無しさん** · 2018/07/23(月) 15:39:54.99

例え話は物事を理解してなくてもそれらしく見せるから知ったか振りが捗りますなあ

**デフォルトの名無しさん** · 2018/07/23(月) 15:41:15.55

ワシも神エクセルとか言ってた

**デフォルトの名無しさん** · 2018/07/24(火) 18:13:24.95

全部やれ

**デフォルトの名無しさん** · 2018/07/24(火) 18:20:36.91

最後までやれ

**デフォルトの名無しさん** · 2018/07/24(火) 20:40:39.40

例えがドラゴンボールではないからだろ

**デフォルトの名無しさん** · 2018/07/27(金) 22:10:24.05

MVC, DAO, O/Rマッピングの発展形として、
俺は「R/Rマッピング(リクエスト/リレーショナルマッピング)」を
提唱したい。
そもそもDB上のカラムと本当に対応付けたいのは画面上のname属性
なんだよなぁ。
オブジェクトを必ず介する必要はない。
(処理が込み入ってきたら定義してもいい程度。)
まず前提として、DBのカラム名とHTML上のname属性を
必ず同じキーにすることを前提とする。(HTML上に関係ない
キーがあっても問題はない。)
その前提の上でDBのカラム名一覧を先に取得しておき、
カラム名リストと、受信したname属性のキーをマッチングして、
マッチングした時にそのキーから取得した値をSQLに突っ込んで
クエリを行う。
こうすることによって、プログラミング言語処理の中で
具体的な「項目名」をほとんど登場させずに処理することができる。
自分でやったらすごく便利だった。
こうなるとそもそもモデルとかDAOとかいらなくね?
ってなって来たよ。
項目数がどんなに二十, 三十と並んでいようがダラダラと羅列しない。
特別な処理を入れたいときだけその項目のカラム名を使って
ifで分岐して日付変換とかをおこなう。
その特別な処理も日付,範囲系、選択肢系などパターンを押さえれば、
めちゃめちゃ簡素化できる。

**デフォルトの名無しさん** · 2018/07/27(金) 22:35:03.11

あ、はい、4行ぐらいしか読んでないけど、
そのリクエストに含まれる名前 = オブジェクトのフィールド名なんだから
あんたが言ってるリクエスト = オブジェクトってこと

あとはストレージをなんにするかの話。
ODBMS（オブジェクトデータベース）を使えばそのまま読み書きできる
だけど、なんやかんやでリレーショナルデータベースを使わないといかんから
O/Rマッピングが必要になる

**デフォルトの名無しさん** · 2018/07/27(金) 22:38:45.06

>>886
あとRailsでも勉強しようね
普通は画面のname属性 = データーベースのフィールド名になってるから
（もちろん必要なら対応してないものも作れるけど）

**デフォルトの名無しさん** · 2018/07/27(金) 22:58:52.80

二層CRUDオモチャ
昔から誰もが一回は考えるアイデアだよ

画面起点だとどうしてもアプリケーションロジックの居場所がないから簡単に作れてもアプリとしての価値が無い
DB起点だとSQLにアプリケーションロジックを埋め込んんで最低限のアプリの体裁は保てるけど保守性が最悪で使い物にならない
という理由から廃れた

なので今はオブジェクト指向の言語でモデルを書いてモデルから画面やDBを生成して微調整しようってのがスタンダード
これなら労力をかけずに豊かな振る舞いを持つアプリケーションを作れるしロジックがモデルに集まるから保守性も高い

**デフォルトの名無しさん** · 2018/07/27(金) 23:43:33.59

>>869
モデルを作るとしても処理が複雑になる部分だけ
部分的でいいんじゃないか？
全ての要素に対して網羅的にモデルつくって
セッター/ゲッター定義して...ってのは肥大化して馬鹿げてる
気がするんだが。
なにせ機能を複製する時にこれらのずらずら並んだモデルオブジェクト名や
キーの名前をを置換しなけりゃならない。
ならない。

**デフォルトの名無しさん** · 2018/07/27(金) 23:51:45.25

> セッター/ゲッター定義して...ってのは肥大化して馬鹿げてる
それはJavaだけ
Javaが馬鹿げているだけ

**デフォルトの名無しさん** · 2018/07/27(金) 23:52:00.90

だからいい加減Railsとかを勉強しろと

**デフォルトの名無しさん** · 2018/07/27(金) 23:55:06.84

.NET Coreにしとけ

**デフォルトの名無しさん** · 2018/07/28(土) 02:15:45.58

>>859
さてリンゴをむくか、
ピーラーがないと剥けないから探すか、
あれ、どこにしまったかな？
この引き出しにもこの棚にもない。
道具だらけで見つからない。
店に買いに行こう、たくさんのピーラーが並
んでいてどれを選ぼうか？
ようやく買ってきて構築しているけど、
どうや刃が付け替え式で色々な刃が付け替えられる
ようだ。
刃を買い忘れたからまた買いに行くか…
はぁはぁ…すごい刃を買ったぞ！今構築中だ。
おや？この刃はリンゴを剥く用途には対応して
ないようだ。もう疲れたしこれ無理だろ。
ピーラーが無いから俺にはリンゴを剥くのは
無理だ。前は引き出しにあったからむけたけど
今はできなくなった。

一方、いつも愛用のナイフで剥いてるならそう
はならない。
いつもポッケに入れているからなくさないし、
最悪自作で調達できる。
使い慣れてるからピーラー使うやつと遜色ないスピードで剥けるし形も綺麗に剥ける。

**デフォルトの名無しさん** · 2018/07/28(土) 02:38:56.80

Rails なんか、全自動！

DB の表の構造が定義された、メタテーブルを参照して、
表の列名なども自動的に取得する

◆QZaw55cn4c · 2018/07/28(土) 03:14:15.05

>>873
Windows 上で構築できますか？

**デフォルトの名無しさん** · 2018/07/28(土) 07:06:05.64

>>870
それでずらずら並んで嫌だというなら、おまえのやり方だと画面定義もずらずらならぶし、テーブル定義やSQLがずらずら並んで更にわけわからなくなるだろ

**デフォルトの名無しさん** · 2018/07/28(土) 09:41:18.41

>>876
できる

◆QZaw55cn4c · 2018/08/11(土) 11:14:19.06

>>878
やりかたは？

**デフォルトの名無しさん** · 2018/08/11(土) 11:16:30.51

>>879
住民税納めてる？

**デフォルトの名無しさん** · 2018/08/11(土) 11:20:01.67

>>879
https://www.microsoft.com/net/learn/get-started-with-dotnet-tutorial

◆QZaw55cn4c · 2018/08/11(土) 11:23:26.77

>>880
固定資産税なら5月に収めました

**デフォルトの名無しさん** · 2018/08/11(土) 13:12:12.75

>>882
固定資産もってるんだスゲー（笑）

**デフォルトの名無しさん** · 2018/08/16(木) 01:50:12.60

最も重要ななのはアルゴリズムとデータ構造
次にI/O
つぎに無名関数やハンドラ、イベント駆動
つぎに並列、非同期処理
その次は画像処理とか3Dとか
ディジタル信号処理またいな各ドメインの専門
技術。
オブジェクトやクラスなんてこれらを達成する
上での手段でしかない。
それ以上のオブジェクト指向の設計思想は
もはや宗教。
唯一絶対に正しいわけでもないし
概念を余計に複雑にするだけ。
SQLやHTML XMLやJavaScript シェルスクリプト
URLなんかが絡んでくるとグダグダに崩壊
するものばかり。
そして現代のアプリケーションはこれら無しで
作るのは無理だからオブジェクト指向の高度な
技法はほどんど不要。

**デフォルトの名無しさん** · 2018/08/16(木) 10:35:20.66

NoSQLω

**デフォルトの名無しさん** · 2018/08/16(木) 14:12:13.61

NoSQL db って、Redis以外はわりと滅びた感じ。
RDBでもスキーマレスなデータ扱えるようになったし、
トランザクションあった方が便利なことやっぱり多いし、
SQLってなんだかんだ言って表現力高いし。

**デフォルトの名無しさん** · 2018/08/16(木) 21:39:02.86

pythonスレにも書いたのですが、pandasのMultiIndexにしたデータのままで、データを追加したり、値を更新したり、csvに入出力する方法をご存知の方はいませんか？

**デフォルトの名無しさん** · 2018/08/17(金) 05:33:12.57

マルチ

**デフォルトの名無しさん** · 2018/08/18(土) 16:47:45.36

マルチインデックスだけに

**デフォルトの名無しさん** · 2018/08/22(水) 13:56:25.55

>>886
その辺はクラウドに吸収されたよ

**デフォルトの名無しさん** · 2018/08/22(水) 14:04:12.93

クラウドだけに雲散霧消

**デフォルトの名無しさん** · 2018/08/26(日) 08:51:55.17

クラウドってなんだっけ？

**デフォルトの名無しさん** · 2018/08/26(日) 11:43:20.70

興味ないね

**デフォルトの名無しさん** · 2018/08/26(日) 12:02:43.50

雲の中にトレーラーがいっぱいあること

**デフォルトの名無しさん** · 2018/08/29(水) 11:59:51.59

>>893
チリチリしてろ

**デフォルトの名無しさん** · 2018/08/30(木) 11:36:30.01

AOJ の「DPL_1_I: Knapsack Problem with Limitations II」が分からん。

個数制限付きナップサック問題の
・ある品物の重さと個数制限
・ナップサック容量
が極めて大きいバージョン。

例えば解法
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2856557#1
を見ると、品物の価値の総和が i であるときの最大容量を記録した動的計画法テーブルを作った後に貪欲法で答えを出してるんだが
・なぜこの方法で上手くいくのか
・前半の動的計画法で、品物の個数を min(m[i], MAX_V) としている (できる) 理由が分からない。

誰か知恵を貸してください。
僕としてはこの解法が理解できれば満足です。

**デフォルトの名無しさん** · 2018/08/30(木) 16:30:03.75

>>896
数学からやり直したほうがいい

**デフォルトの名無しさん** · 2018/08/30(木) 16:38:34.35

>>897
どういう意味？
「このアルゴリズムを理解するのに必要な数学の分野」というものがあるならそれを参照するが、そんなものはない (挙げられないでしょ？)

俺個人の専門は物理で、「数学の勉強」というものも一応してきたが、このごく具体的な問の一解法を理解することと「数学の勉強」は関係がない

単純に論理的思考力を上げよ、と言っているなら会話になっていないのでこれ以上は結構

**デフォルトの名無しさん** · 2018/08/30(木) 16:59:47.21

論理的思考力を上げるために将棋をしなさい。数学など不要です。

**デフォルトの名無しさん** · 2018/08/30(木) 18:00:22.07

うむ

**デフォルトの名無しさん** · 2018/08/30(木) 18:13:22.55

>>898
DPは数学的に求まるよ

**デフォルトの名無しさん** · 2018/08/30(木) 18:43:47.20

>>898
数学科の数学と物理科の数学とコンピュータの数学は違う（笑）

**デフォルトの名無しさん** · 2018/08/30(木) 19:55:53.34

>>901
最適性の証明のことを言ってるの？
いずれにせよこの問題に限った話じゃないよね？
別に動的計画法が上手くいく理由が分からないと言っているのではなく、>>896の解法が分からないのだが。

>>902
違わない
算術、代数、幾何、解析だ全て

**デフォルトの名無しさん** · 2018/08/30(木) 19:59:32.89

例えば、バブルソートには
数学の、えっと、幾何？の知識が必要だろ？
え？

**デフォルトの名無しさん** · 2018/08/30(木) 20:02:00.51

フローチャートでも書けよバカ。

**デフォルトの名無しさん** · 2018/08/30(木) 20:07:14.70

>>905
無論書いたが分からん

**デフォルトの名無しさん** · 2018/08/30(木) 20:55:16.95

>>903
やったことないだろ（笑）

**デフォルトの名無しさん** · 2018/08/30(木) 20:58:00.20

単に頭が悪い見栄っ張り

**デフォルトの名無しさん** · 2018/08/30(木) 21:05:25.02

>>906
分からんと思っているだけでは進まない。

なにを目的にして、どのようなフローチャートを描いて、
その結果なにが理解できていて、なにがまだ理解できていないのか、
可能な限り事細かに洗い出して、自分の理解の最前線を特定してみるといい。

と言うことを、私は数学で学んだ。

**デフォルトの名無しさん** · 2018/08/30(木) 21:18:12.57

数I？数II？

**デフォルトの名無しさん** · 2018/08/30(木) 21:43:49.44

>>909
だからそれは>>896の時点で書いてるんだが
関係ないことしか言えないならレス不要です

>>907
何を？

**デフォルトの名無しさん** · 2018/08/31(金) 00:40:53.58

俺の周りで物理やってる人はとんでもなく数学ができる人ばかりなのに

**デフォルトの名無しさん** · 2018/08/31(金) 00:57:19.27

まあゲームじゃない限り物理なんて使わないよね
本格的な物理系シミュレーションとかだと
専門家が担当するだろうし

**デフォルトの名無しさん** · 2018/08/31(金) 01:02:18.59

この程度の問題で数学数学言ってるアホ多過ぎて呆れる

多分>>910みたいな感じで高校の算数基準で話してるんだろうな

**デフォルトの名無しさん** · 2018/08/31(金) 01:09:41.75

そんなに言うのなら、具体的に数学のどの分野なのか
それが具体的に何と同じなのか言えって。
どうせ論理的思考力がーみたいな精神論しか言えないんだろ

**デフォルトの名無しさん** · 2018/08/31(金) 07:21:05.29

数列、非線形解析学
はい言いました
論理的思考力が無いのはあなたですね

**デフォルトの名無しさん** · 2018/08/31(金) 07:23:04.73

どうしてこうなった

**デフォルトの名無しさん** · 2018/08/31(金) 09:04:32.63

>>916
では、数列、非線形解析学を利用した
アルゴリズムを答えてください

**デフォルトの名無しさん** · 2018/08/31(金) 09:05:36.36

ちなみに、数列は高校数学である

**デフォルトの名無しさん** · 2018/08/31(金) 11:52:41.02

>>918
>>896

**デフォルトの名無しさん** · 2018/08/31(金) 12:44:50.11

>>920
数学の問題をコンピュータで解決するってのはわかる、
だが数学・物理特有の問題以外をコンピュータで解決するのに
数学はいらねーだろって話

**デフォルトの名無しさん** · 2018/08/31(金) 14:32:18.54

>>921
微分積分も理解せずにコンピュータに信号処理をやらせるの？
そういうレベルの質問

**デフォルトの名無しさん** · 2018/08/31(金) 14:39:40.99

信号処理なんて、誰がやっても同じなんだから
一度ライブラリ作って、他の人はそれ使うだけだろ・・・

**デフォルトの名無しさん** · 2018/08/31(金) 16:28:19.03

>>923
それじゃあ初音ミクは生まれないね
こういうやつが技術を停滞させる

**デフォルトの名無しさん** · 2018/08/31(金) 18:49:37.43

>>924
だからそういうのは専門家に任せたほうが良くね？

音声合成をやる人は、そういう専門家に任せて
他の人は便利なインターフェースを作るとかさ、
なんでも1人でやるもんじゃないよ？

**デフォルトの名無しさん** · 2018/08/31(金) 19:18:52.92

別にそういう原理を知りたくないんなら勉強しなくて良いんじゃない
表面的なものしか作りたくないなら勉強しないことをおすすめします

**デフォルトの名無しさん** · 2018/08/31(金) 19:24:24.23

>>926
だから作る層が違うって言ってんの
水道局で働いてる人全員が
工事技師じゃないんだよ

**デフォルトの名無しさん** · 2018/08/31(金) 19:27:43.29

>>927
つまり君はそういう層にはなるのを拒む側ってだけだ

**デフォルトの名無しさん** · 2018/08/31(金) 20:05:55.05

>>928
その理屈で言えば、君がそういう層になりたいだけでは？

残念だけど、自分がやりたいことと、他人がやってもらいたいこと
っていうのは同じじゃないんだよね

そして給料っていうのは、他人がやって欲しいことをやった対価として
もらえるものなので、いくら自分がすごいことができるって言ったからって
給料は高くならないんだよね。

**デフォルトの名無しさん** · 2018/09/01(土) 00:41:52.18

>>929
作りたいものがあるから勉強する、それだけ

**デフォルトの名無しさん** · 2018/09/01(土) 09:56:42.06

うむ

**デフォルトの名無しさん** · 2018/09/01(土) 10:48:54.59

自分一人で作るような小さいアプリとかなら、
全部を知っておかなければいけない、って思いたくなるのもわかる。

が、通常は数学の専門家でも無い人間を数学で信用する事は無いし、
プログラムの専門家でも無い人間をプログラムで信用する事は無い。

付け焼き刃は事故の元。
大きな仕事になればなるほど役割や責任が細分化される。

**デフォルトの名無しさん** · 2018/09/01(土) 12:24:44.93

ぼやっとして結局何を言いたいのか良くわからんが
何か良い事を言いってみたい必死さは伝わった

**デフォルトの名無しさん** · 2018/09/01(土) 12:52:20.45

え？言いたいことがわからんの？

**デフォルトの名無しさん** · 2018/09/01(土) 13:01:11.42

そりゃあ馬鹿の言ってることは分からんだろ

**デフォルトの名無しさん** · 2018/09/01(土) 13:13:44.90

言ってることがわからんから、言ってるほうが馬鹿だと思ってるだけじゃないの？
俺に言わせれば、馬鹿だから言ってることがわからないんだと思うが？

**デフォルトの名無しさん** · 2018/09/01(土) 13:42:02.18

俺に言わせれば世界はお前を中心に回ってないってこと

**デフォルトの名無しさん** · 2018/09/01(土) 13:47:09.53

>>937
お前を中心に回ってるといいたいのかな？

**デフォルトの名無しさん** · 2018/09/01(土) 14:37:08.16

>>938
>>936

**デフォルトの名無しさん** · 2018/09/01(土) 14:47:05.92

>>939
俺のレスがどうした？

**デフォルトの名無しさん** · 2018/09/04(火) 02:27:34.18

アルゴリズム辞典みたいなものを手元に置いときたいんだが、最も支持されてるのってどれ？

・網羅性が高い
・支持されている（売れている）
・日本語版がある
・コード例はあってもなくても良くて、あるとしたら C/C++ か擬似コードで
という条件で
テーマ別に「どれとどれとどれを持っとけばまず問題ない」という言い方でもありがたい
とにかく網羅性を重視してる

**デフォルトの名無しさん** · 2018/09/04(火) 07:04:17.98

英語は知らんけど、日本語なら
[改訂新版]C言語による標準アルゴリズム事典 (Software Technology)
奥村晴彦
http://amzn.asia/d/bAqY5Be
が網羅性は随一じゃないかな。
改訂だけど初版が1991年で、収録アルゴリズムは増えてないらしいので、
機械学習とかここ25年の新分野は当然入っていない。

**デフォルトの名無しさん** · 2018/09/04(火) 07:32:26.75

機械学習の何をアルゴリズム辞典に入れるべきだというのか

Amazonレビューかよテメェは

**デフォルトの名無しさん** · 2018/09/04(火) 07:36:36.34

>>942
この本はBoyer-Moore法が簡易版しか載っていないし、Aho-Corasick法も載ってないから弱い

**デフォルトの名無しさん** · 2018/09/04(火) 08:37:54.35

より網羅的な対案示してからでないと批判にならないよ。

共立のアルゴリズム辞典が現存すればこっちも挙げてたかもしれん。
BM法に関してはコード例は簡略版のみだが。

個別のアルゴリズムについてどこまで踏み込むかは、
辞典の物理的な性質上取捨があるのはしかたないでしょ。

**デフォルトの名無しさん** · 2018/09/04(火) 10:34:21.16

>>943
+1

**デフォルトの名無しさん** · 2018/09/04(火) 10:36:29.76

名前がついていて解放も明らかになってるアルゴリズムに興味はない
そんなのいくらやっても新しいものは生み出されない

**デフォルトの名無しさん** · 2018/09/04(火) 14:25:14.21

>>947
先輩、かっけぇっす

**デフォルトの名無しさん** · 2018/09/11(火) 14:44:06.44

質問させてください。
マイコンからAD変換で入力したサイン波を配列に格納し、周波数を求めたいと思います。
ゼロクロスの位置を求めれば正確に周波数を求められそうですが、教えてください。
https://i.imgur.com/FC5XP0K.png

**デフォルトの名無しさん** · 2018/09/11(火) 16:27:37.38

質問が不完全だけど、そのためのアルゴリズムを教えてほしいということでよい？

前提として、各周期で確実に2回だけゼロクロスすると保証できるのなら、
前回の値を覚えておいて、今回との積が0以下になったらゼロクロス。

この保証がないのなら十分長く波形をとってFFTしてピークを探す。

**デフォルトの名無しさん** · 2018/09/11(火) 22:09:31.90

♀だったらｾｸﾛｽ教えてやる

**デフォルトの名無しさん** · 2018/09/11(火) 22:11:28.88

え！？童貞なのにセクロスを！？

**デフォルトの名無しさん** · 2018/09/12(水) 03:44:12.77

できらあ！

**デフォルトの名無しさん** · 2018/09/12(水) 07:05:35.15

それページ逆だぞ

**デフォルトの名無しさん** · 2018/11/05(月) 18:00:44.74

有向グラフの有向閉路を求める問題です。

深さ優先探索を実行したときに、 Backward Edge が存在する。

⇔

有向閉路をもつ

⇒は自明ですが、逆はどう証明するのでしょうか？

**デフォルトの名無しさん** · 2018/12/03(月) 20:50:16.30

深さ優先、幅優先探索を理解するのにオススメの本ってありますか？(コードサンプル付きでできればC)

**デフォルトの名無しさん** · 2018/12/04(火) 09:57:38.19

https://www.amazon.co.jp/dp/4874084141

**デフォルトの名無しさん** · 2018/12/04(火) 10:14:50.08

>>957

全くおすすめできません。その本。

**デフォルトの名無しさん** · 2018/12/04(火) 10:27:11.51

>>956

グラフ・ネットワークアルゴリズムの基礎: 数理とCプログラム
浅野孝夫
固定リンク: http://amzn.asia/d/2MetXvf

**デフォルトの名無しさん** · 2018/12/04(火) 11:20:17.46

馬鹿アスペの推奨ｗ

**デフォルトの名無しさん** · 2018/12/04(火) 14:19:52.12

学ぶ目的には全くお勧めできないってのはその通りだけど、
手元に置いておいて使う分には便利な本ではあるような。
あ、浅野先生の本も待ってます。
(この分野、浅野先生が2人いて紛らわしい)

**デフォルトの名無しさん** · 2018/12/04(火) 14:28:35.23

>>956

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
渡部有隆
固定リンク: http://amzn.asia/d/g8qmfS6

↑この本にも、 BFS、DFS共に書いてあります。

解説は非常に雑ですが。

**デフォルトの名無しさん** · 2018/12/04(火) 14:33:05.75

>>959

の本には、再帰を使う DFS プログラムが書いてあります。（スタックを使う DFS プログラムは演習問題にあり、コードをダウンロードできます。）

**デフォルトの名無しさん** · 2018/12/04(火) 14:34:21.14

>>963

スタックを使う DFS プログラムは演習問題にあり、コードをダウンロードできますし、本にも解答のところにコードが載っています。）

**デフォルトの名無しさん** · 2018/12/04(火) 14:39:02.72

前置記法（ポーランド記法） + 1 2
後置記法（逆ポーランド記法） 1 2 +
中置記法 1 + 2

確か、構文木をたどる時に、どれかが幅優先で、どれかが深さ優先探索になると、記憶している

**デフォルトの名無しさん** · 2018/12/05(水) 13:24:47.73

shaderって何回書き換えてもメモリ壊れない？

**デフォルトの名無しさん** · 2018/12/05(水) 21:47:02.62

テンプレのソース探検なんちゃらのサイトいいね
pdf買えはうざいけど

ソートはクイックマージヒープの特性くらい押さえとけば良さそうな感じだな
そこら中に実装あるしまあ
バケットソートは聞いたこと無かったけど、これは局所で凄い威力発揮しそうだ
覚えとく価値ありそう

**デフォルトの名無しさん** · 2019/06/19(水) 04:49:26.98

【出資】松本卓朗人工知能詐欺【注意】
https://rio2016.5ch.net/test/read.cgi/rikei/1560859403/

**デフォルトの名無しさん** · 2020/01/03(金) 12:48:16.96

O(n)で中央値を求めるアルゴリズムを思いついた

**デフォルトの名無しさん** · 2020/01/04(土) 01:21:11.30

クイックセレクトのこと？

**デフォルトの名無しさん** · 2020/01/13(月) 02:33:48.51

こんにちは、初質問させていただきます、グラフアルゴリズム初心者です

・無向グラフGが入力として与えられる(ファイルからでも、コード内での手打ちでも、どちらも良い)
・Gがサイクルを持てばGの中の最小サイクル(長さが最も短いサイクル)とそのコストを出力する
・各辺、頂点の重みは考えなくても良い(つまり辺のコストは1とする)
といったアルゴリズムを実装したいです。
できればC言語もしくはC系統の言語でコーディングしたいです。

考え方と共に、コーディング例をご教授いただけると幸いです。

浅い知識ではありますが、この実装に必要そうである
・DFS,BFS
・ダイクストラ、ベルマンフォード
に関しては、基礎レベルは把握しています。

お手数おかけしますが、ご助力いただけると幸いです。

**デフォルトの名無しさん** · 2020/01/13(月) 04:31:10.60

適当に言うけど、

すべての辺を1回だけ通りながら、通った頂点を記録していく
それで同じ頂点を、2回以上通ったら、閉路がある？

**デフォルトの名無しさん** · 2020/01/13(月) 12:21:39.99

>>971
グラフのサイズが書いてないと答えられないな

**デフォルトの名無しさん** · 2020/01/13(月) 13:32:08.60

>>973
条件不足で申し訳ございません

グラフサイズの制約は特に設けないものとしています。
とりあえずは最大でも100頂点程度で考えています。

お手数お掛け致しますが、よろしくお願いします。

**デフォルトの名無しさん** · 2020/01/13(月) 13:32:16.76

>>973
条件不足で申し訳ございません

グラフサイズの制約は特に設けないものとしています。
とりあえずは最大でも100頂点程度で考えています。

お手数お掛け致しますが、よろしくお願いします。

**デフォルトの名無しさん** · 2020/01/13(月) 17:13:44.37

>>975
頂点数をn，辺数をmとする
ある頂点uを含んだ最小閉路は頂点uからbfsをすればO(n+m)で求められる（最初にuに戻ってきたときの経路が最小）
あとはすべての頂点に対してこれをして，その中から一番短いものを選べばいいので，全体でO(n(n+m))で求められる

**デフォルトの名無しさん** · 2020/01/13(月) 22:42:08.62

>>976
ありがとうございます。

つまり、例えば
各頂点を始点-終点とするダイクストラアルゴリズム処理を行えば良い
ということでしょうか。

**デフォルトの名無しさん** · 2020/01/13(月) 23:30:01.64

>>977
イメージとしてはそんな感じです
辺を考えたほうがわかりやすいかもしれないです

ある辺(u-v)を含むようなサイクルの中で最小のものを求めたいとします
まずグラフから辺(u-v)を除去します．このグラフ上でuからvの最短距離dを求めます
すると，d + 辺(u-v)が辺(u-v)を含むサイクルの中で最小のものとなります

グラフの中で一番短いサイクルは辺(u-v)を含んでいるかはわからないので，すべての辺に対して上の操作を実行します
その中から一番短いものを選べば，それがグラフの中で一番短いサイクルです
この場合だとO(m(n+m))です

**デフォルトの名無しさん** · 2020/01/15(水) 13:45:14.74

>>978
ありがとうございます。
ご教授いただいた考えをもとに、ダイクストラ法を用いて実装してみました。
・ダイクストラ(グラフは頂点とコストで表現)
https://ideone.com/bXF0iQ

また、以前似たものを実装したのですが、これはダイクストラ(もしくはBFS)の考えに則れていますでしょうか・・・？
(グラフは隣接行列で表現)
https://ideone.com/snxvav

どちらにしても、始点と終点が同一でない場合はうまくいくのですが、
始点と終点を同一として閉路で求めようとすると、うまくいきません。
自己ループ辺のコストが0であるから、と思い9999などにしてみましたが、うまくいきませんでした。

すごく単純なミスなのでしょうが、詰まってしまっている状態です。
修正等いただけると幸いです。

一応、(可能であれば)望む仕様と結果としては
・グラフは隣接行列で表現
・辺の重みは非負である(今回、簡易化のために辺の重みは1~9)
・グラフサイズは制限しない(今回、簡易化のために10頂点程度)
・ダイクストラを用いて自分自身を始点かつ終点とする最短経路を求める
・各頂点に対して上のダイクストラを行い、中でも最短の閉路の経路とそのコストを表示する

です。

お手数をおかけしますが、よろしくお願いします。

**デフォルトの名無しさん** · 2020/01/15(水) 16:39:42.37

>>979
>>971だと辺のコストは1となっているが，実際は辺に1以外のコストがある？
求めたい最小サイクルというのは，使う辺の本数が最小という意味なのか，使う辺の合計コストが最小という意味のどちらなのか

**デフォルトの名無しさん** · 2020/01/15(水) 21:49:25.61

>>980
コストは1だと申し上げましたが、
ダイクストラなので非負であれば求まると思い、汎用性を考えて1以外のコストも付与してみました。
説明不足で申し訳ございません。

**デフォルトの名無しさん** · 2020/01/15(水) 23:25:41.19

>>981
無向グラフだと面倒くさくて，uからvにいったあとvからuにいくような場合がでてくるのでこれを除かないといけない
そのような経路を除いたうえで始点に戻ってきたものが最短になる
ある辺が2回使われることはないので，辺は1度しか使えないようにすればいいと思う

**デフォルトの名無しさん** · 2020/01/15(水) 23:28:15.13

https://www.geeksforgeeks.org/shortest-cycle-in-an-undirected-unweighted-graph/
これとかわりとそのままだな　重みなしだけど

**デフォルトの名無しさん** · 2020/01/15(水) 23:56:14.28

https://www.geeksforgeeks.org/find-minimum-weight-cycle-undirected-graph/
こっちは重み付きのやつ

**デフォルトの名無しさん** · 2020/01/18(土) 22:58:37.26

>>983
>>984

ありがとうございます。
コストだけでなく、経路も出力したいのですが、弄ってみてもなかなかうまくいきません...。

**デフォルトの名無しさん** · 2020/01/19(日) 12:55:00.98

CLRSのダイクストラのアルゴリズムの正しさの証明を読み終わりました。
行間が全くなく、確かに、正しいことは分かりますが、あまりイメージのわかない証明ですね。

CLRSって他の本と比べると異常に行間がないですよね。

**デフォルトの名無しさん** · 2020/01/20(月) 15:11:46.01

巨大なsparce行列（ゼロ要素が多い行列）で行列演算やるときデータ構造考えるよね

**デフォルトの名無しさん** · 2020/01/20(月) 17:27:30.27

>>985
どのへんがわからないか言ってくれ
Find minimum weight cycle in an undirected graphは
int Graph :: ShortestPathでu-vを削除したときの最短経路を求めてる
このときdist[v]が更新されるたびにvにきたノードをメモしておけば最後にvからprevをたどって復元できる
このときの経路をvector

楽な実装方法は，グローバル変数にこれまでの最短経路の距離とルートをもっておいて
常に最短のものを保存しておけばいい

**デフォルトの名無しさん** · 2020/01/20(月) 17:28:22.60

途中で送信してしまった
このときの経路をvetorにいれておけばいい

**デフォルトの名無しさん** · 2020/01/25(土) 23:49:17.89

>>988
正直、C++の知識不足で勉強を頑張ってはいるのですがVectorの使い方がまだ、慣れていません。。。

厚かましいのは重々理解しているのですが、可能であればFind minimum weight cycle in an undirected graphのプログラムを>>988さんなりに改変したものをお教えいただけると幸いです。。。

悪い勉強法とは分かっているのですが、答えというか実装例が無いとなかなか理解できなくて。。。

**デフォルトの名無しさん** · 2020/01/26(日) 01:32:16.02

言語の基本的な部分はさすがによそでやろうや・・・

**デフォルトの名無しさん** · 2020/01/26(日) 13:25:18.52

>>990

https://ideone.com/pShuim

↑一応動きました。
piという変数に経路を覚えさせています。

**デフォルトの名無しさん** · 2020/01/26(日) 13:32:46.65

>>990

piについては、

Cormen, Leiserson, Rivest, Stein著『Introduction to Algorithms 3rd Edition』の最短路の章を見ると、

書いてあります。

**デフォルトの名無しさん** · 2020/01/26(日) 13:47:50.10

アルゴリズムとデータ構造ってコンピューターサイエンスの分野で人気ないんですか？