データ構造,アルゴリズム,デザインパターン総合スレ 2
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
2013/03/03(日) 18:10:11.633Dアルゴリズム全般
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
0153デフォルトの名無しさん
2014/01/31(金) 21:30:32.04ただし、if 文で n 回の比較が発生するから、n があまりに大きい場合は >>152 のやり方がいいと思う。
最後の文字を削れない場合は for 文で a[n-2] まで ',' と一緒に出力して、追加で a[n-1] を出力するか。
>>150 は何の言語?
0154デフォルトの名無しさん
2014/01/31(金) 21:35:58.740155デフォルトの名無しさん
2014/01/31(金) 22:35:19.830156デフォルトの名無しさん
2014/01/31(金) 22:38:32.60puts a[0..n-1].join('.')
0157デフォルトの名無しさん
2014/01/31(金) 22:49:27.58join があるならそれを使うのが最もスマート
0158SD
2014/02/01(土) 15:47:33.85String r="";
for(String b:a){r+=d+b;d=",";}
0159デフォルトの名無しさん
2014/02/01(土) 16:20:22.09毎回同じ値で更新するのが美しくない
0160デフォルトの名無しさん
2014/02/01(土) 16:50:11.43for(int i=1;i<a.length;i++)print(','+a[i]);
0161デフォルトの名無しさん
2014/02/01(土) 17:23:17.66lengthが2回出てくる以外は殆ど無駄がない
0162デフォルトの名無しさん
2014/02/01(土) 17:47:07.99定数へのポインタを代入するだけなので効率も悪くない。
0163デフォルトの名無しさん
2014/02/01(土) 18:04:45.52コンマ部分だけ出力が別にあるのは構わないけど
str = a[i]; if (i < n - 1) {str += ','}
こうすれば一箇所
>>151とほぼ同じ
0164デフォルトの名無しさん
2014/02/01(土) 18:09:57.02for (int i = 0; i < a.size; i++) {
if (i != 0) print(,)
print(a[i])
}
0165デフォルトの名無しさん
2014/02/01(土) 18:53:19.100166デフォルトの名無しさん
2014/02/01(土) 19:42:53.65for (int i = 0; i < a.size; i++) {
print(a[i])
if (i < a.size - 1) print(,)
}
最初だけコンマを付けない、よりは最後だけコンマを付けない、の方が
人間が理解しやすいような
ただ、条件文が読みにくい
0167デフォルトの名無しさん
2014/02/01(土) 19:46:34.490168デフォルトの名無しさん
2014/02/01(土) 19:48:28.34しかも、ループごとの状態がたとえば[a, b, c]のとき、
0: a
1: a, b
2: a, b, cとなっておりどの状態も気持ちいい。
後カンマ方式だと、
0: a,
1: a, b,
2: a, b, cとなり、0と1の状態が気持ち悪い。
0169デフォルトの名無しさん
2014/02/01(土) 21:03:39.160170デフォルトの名無しさん
2014/02/01(土) 23:11:17.91(1) 最初は組み込みメソッド join を使って簡潔に書く(>>156,157)
puts xs[0..n-1].join(', ')
(2) joinの代わりに畳み込み(fold)であるメソッド inject で書き直す
puts xs[0..n-1].inject('') { |ys, x|
if ys.empty? then x.to_s else ys << ', ' + x.to_s end
}
# http://docs.ruby-lang.org/ja/2.1.0/class/Enumerable.html#I_INJECT
(3) これを命令型へ書き換えることを考える
まず(2)では先頭要素であるか否かを累積変数 ys が空か否かで判断している
この累積変数の代わりに、先頭か否かを表すフラグ is_first を使う
is_first = true
for x in xs[0..n]
if is_first
printf x.to_s
is_first = false
else
printf ", %s", x.to_s
end
end
printf "¥n"
ここまで展開すれば、これをたとえばC言語へ移植することも容易いだろう
0171デフォルトの名無しさん
2014/02/01(土) 23:18:11.99この考え方、感じ方は大事だね
例えば、これを範囲を指定してコンマ区切りの文字列を返す関数にしたら
前者ならすんなり行く
0172デフォルトの名無しさん
2014/02/02(日) 00:01:46.64どうしてもコンマが余ったり足りなかったりする
0173デフォルトの名無しさん
2014/02/02(日) 00:49:30.38for x in (xs[1..n])
print (", " + x)
では間違い?
0174デフォルトの名無しさん
2014/02/02(日) 01:00:24.64複数箇所のprintを直して回らないといけない
0175デフォルトの名無しさん
2014/02/02(日) 01:07:52.480176デフォルトの名無しさん
2014/02/02(日) 01:15:24.41もし言語がRubyであるならば、以下の問題がある
(1) 最後のendが抜けている(これは、おそらくtypoだと思う)
(2) メソッド print は実行のたびに改行するから、期待する結果とは一致しない
(3) (2)の対策として print の代わりに printf を使ったとしても、
もし xs が空であると xs[0] の値は nil になるから、
メソッド printf の実行が引数エラーになる
(メソッド仕様上、printf の第一引数は文字列であるべき)
0177デフォルトの名無しさん
2014/02/02(日) 01:21:27.650178デフォルトの名無しさん
2014/02/02(日) 01:34:06.21ネタにしてはつまらんし、素なら悲しい。
0179デフォルトの名無しさん
2014/02/02(日) 08:15:43.49または,
for(i=0;i<n;i++) printf("%s%d",(i==0)?"":",",a[i]);
int a[]; としてるけど.
0180デフォルトの名無しさん
2014/02/02(日) 08:40:42.33文字列に修飾子としてコンマの追加の条件文を書けるような言語なら綺麗に書ける筈
三項演算子はそれに一番近い
0181151
2014/02/02(日) 21:14:08.470182デフォルトの名無しさん
2014/02/03(月) 00:06:18.13完全に相対的なので、どっちでも等価
セパレータだと思えば前だし、エンドマークだと思えば後
文末のセミコロンが本当は行の区切りだと判ってる人には、
後にコンマが付くのが基本で、例外的に外しているという考えに近い筈
0183デフォルトの名無しさん
2014/02/03(月) 00:40:01.64例外的に外すという考えだぁ??
カンマは区切りっしょ。
CSV形式という文化はずーっと前からあるように。
Comma Separated Valuesだぞ?
0184デフォルトの名無しさん
2014/02/03(月) 00:55:38.640185デフォルトの名無しさん
2014/02/03(月) 19:57:58.390186デフォルトの名無しさん
2014/02/03(月) 20:21:35.730187デフォルトの名無しさん
2014/02/03(月) 21:22:48.710188デフォルトの名無しさん
2014/02/07(金) 11:44:16.710189デフォルトの名無しさん
2014/02/07(金) 12:49:17.86C言語のコンマのように、最後には付かないのがセパレータ。
ついでに言うと、C言語においてセミコロンは、式文やdo-while文みたいな、
「一部の文の」ターミネータ。あと for の頭部でセパレータとしても使われてる。
0190デフォルトの名無しさん
2014/02/07(金) 23:08:20.670191デフォルトの名無しさん
2014/02/08(土) 10:34:10.24C言語において「空文」は、「空文字列にセミコロンが付いたもの」だよ。
0192デフォルトの名無しさん
2014/02/10(月) 00:14:12.54C言語において「空文」は、「セミコロンだけの文」だよ。
0193デフォルトの名無しさん
2014/02/10(月) 17:16:31.68ばーかw
0194デフォルトの名無しさん
2014/02/10(月) 17:30:49.07どうでもいい。
0195デフォルトの名無しさん
2014/02/11(火) 08:40:29.35最後の","を'\0'で潰すのがはやい
0196デフォルトの名無しさん
2014/02/11(火) 09:17:01.180197デフォルトの名無しさん
2014/02/11(火) 16:18:25.250198デフォルトの名無しさん
2014/02/11(火) 16:31:18.090199デフォルトの名無しさん
2014/02/11(火) 19:16:39.02それとも \0 ターミネーション?
0200デフォルトの名無しさん
2014/02/13(木) 11:20:17.620201デフォルトの名無しさん
2014/02/13(木) 23:24:36.150202デフォルトの名無しさん
2014/02/13(木) 23:33:36.34前者はBSTR型とかね。
0203デフォルトの名無しさん
2014/02/13(木) 23:49:03.850204デフォルトの名無しさん
2014/02/14(金) 00:32:59.75256以上の長さの文字列どうするんだよ?
0205デフォルトの名無しさん
2014/02/14(金) 08:03:36.410206デフォルトの名無しさん
2014/02/14(金) 11:03:48.78可変長文字列を管理するデータ構造を考えるだけでも楽しそうだね。
0207デフォルトの名無しさん
2014/02/14(金) 19:07:04.660-127 のときは そのままの値
128-255 のときは (その値 - 127) x 128 + その次のバイトの値
ただしその次のバイトの値が 0-127 のときはその次のバイトの値をそのまま使うが
その次のバイトの値が 128-255 のときはさらに (上の値 - 127) x 128 + その次の次の値とする
とか
0208デフォルトの名無しさん
2014/02/14(金) 23:05:25.360209デフォルトの名無しさん
2014/02/17(月) 01:31:20.810210デフォルトの名無しさん
2014/03/05(水) 11:39:12.46たとえばxを任意の文字としてabxをbxに置き換えbxをxにおきかえるとしたら
abcをcに置き換えたいです。
この時、この置き換え操作は無限に続かないことを前提としています。
この例では一つのパターンでしたが、プログラムの入力としてパターンと
置き換える文字列、出力として置き換え後の文字列であるものの
作成方法が分かりたいです。
0211デフォルトの名無しさん
2014/03/05(水) 12:09:18.800212デフォルトの名無しさん
2014/03/09(日) 19:39:16.05ここで教えてくださる人はいますか?
0213デフォルトの名無しさん
2014/03/09(日) 20:01:44.88とりあえず質問内容を書いてみたら?
答えるかどうかは気分次第だけど。
0214デフォルトの名無しさん
2014/03/09(日) 20:20:18.06バックトラックとか動的計画法まで載ってる本で読みやすくてコードが書いてるやつ
何がいい?
はじめてのアルゴリズム 上原
とかエイホさんのとかっていいの?
0215デフォルトの名無しさん
2014/03/09(日) 20:44:41.370216デフォルトの名無しさん
2014/03/09(日) 23:15:50.810217デフォルトの名無しさん
2014/03/09(日) 23:31:43.52プログラミング・コンテスト・チャレンジブック、第2版、2012
グラフ理論など、ほとんど全てのアルゴリズムを網羅
問題数も多く、パズル感覚で楽しめる
AIやシミュレーションゲームの参考になる
TopCoder
ttp://toro.2ch.net/test/read.cgi/tech/1333159918/l50
0218デフォルトの名無しさん
2014/03/15(土) 20:50:18.83ID:3c5h2INRプログラミング・コンテスト・チャレンジブックを読もうと思ってるんですけど
その前にやっておくべき本とかってありますか?
アルゴリズムイントロダクション,データ構造とアルゴリズム(杉原)が候補にあります.
ちなみに,現在大学生で,CとPythonはある程度書けます.
0219デフォルトの名無しさん
2014/03/15(土) 21:05:18.35ID:LOPS9SpPプログラミング・コンテスト・チャレンジブックはひと通りアルゴリズムを学んだ人が腕試しにやるような本だから、候補に上げたような本を先に読むんでいいと思う。
杉原は知らないけど、アルゴリズムイントロダクションもちょっと数学的考察とか証明の割合が多いから、難しいようなら他の本を当たった方がいいかもしれない。一生使えるから、とりあえず買っちゃうのはいいと思うけど。
あとは大学(自分のとこでも、他所でも)のアルゴリズムとデータ構造の授業で使ってる教科書を見てみるのがいいと思う。
0220デフォルトの名無しさん
2014/03/15(土) 22:02:22.42ID:3c5h2INRありがとうございます.
数学的考察も欲しいのでアルゴリズムイントロダクションを買おうと思うのですが
初心者でも総合版を買うことをおすすめされますか?
鈍器としても使えるらしいので総合版にしようかと思っていたのですが
あまりにも重すぎて使いにくいという声など,もしありましたら教えていただきたいです.
0221デフォルトの名無しさん
2014/03/15(土) 22:06:32.24ID:tN8Ad5rRたしか総合版にしか無い箇所があるんじゃ?
0222デフォルトの名無しさん
2014/03/15(土) 23:56:04.39ID:LOPS9SpPへえー、総合版なんてのが出たのか。今度立ち読みしてみるわ。
1、2巻出してるから残りを3巻にすればいいのにね。
判断基準としては重さ、値段とあとは自分の勉強したいアルゴリズムが1、2巻で足りるかどうかじゃないかな?
大学の情報科の1、2年のアルゴリズムの授業で習う位の範囲なら1、2巻で足りるはず。
これが総合版だと含まれてるみたい。
27 Multithreaded Algorithms
28 Matrix Operations
29 Linear Programming
30 Polynomials and the FFT
31 Number-Theoretic Algorithms
32 String Matching <--- これも1, 2年で習うかな?
33 Computational Geometry
34 NP-Completeness
35 Approximation Algorithms
0223デフォルトの名無しさん
2014/03/16(日) 03:10:11.24ID:NcMQ7vHT0224Donald Knuth
2014/03/16(日) 03:15:08.58ID:BR331utC現在わたしは、Ph.D.(Doctor of Philosophy)をとらなければ
ならないようなプログラムを、みんなが書くべきと考えていません。
多くの理論がこれまで開発されてきましたが、そのほとんどは、
実際のプログラムではあまり使われないものなのです。
こうしたものは、ものごとを極限までつきつめるときぐらいしか、
役に立たない。これらの理論の値打ちは、
ユーザーに全体の構造を見渡せる視野を提供することにあるのです。
理論をたくさん知っていればいるほど、ユーザーは、
プログラムで実際に応用するほんのわずかなことが、
より楽に理解できるようになるというだけのことなわけです。
ユーザーは、自分が扱える範囲を広げるために、理論を必要とします。
たとえばリストでいえば、ユーザーがリストに関して、
より複雑な理論を知っていれば、プログラムにこうした理論を
使うことがなくても、プログラムの中の単純なリストの使い方は、
(理論を知らない人が書いたものと比べれば)
はるかに自然なものとなるのです。
0225デフォルトの名無しさん
2014/03/16(日) 03:27:49.15ID:NcMQ7vHT部屋の飾りにはいいかもしれないけれど
0226デフォルトの名無しさん
2014/03/16(日) 10:42:44.74ID:36W3tLYE0227デフォルトの名無しさん
2014/03/16(日) 10:50:16.89ID:JXH3psgq0228デフォルトの名無しさん
2014/03/16(日) 11:32:59.02ID:36W3tLYE0229デフォルトの名無しさん
2014/03/16(日) 12:49:26.13ID:AOFYs8Jm0230デフォルトの名無しさん
2014/03/16(日) 13:35:29.66ID:tRI7CXOm丁寧にありがとうございます!
追加されたのは比較的高学年で学ぶ範囲なのですかね.
大学院で学ぶ内容も網羅してくれているとありがたいので,総合版にしようと思います.
0231デフォルトの名無しさん
2014/03/16(日) 16:22:41.16ID:1gXwUEhj0232デフォルトの名無しさん
2014/03/16(日) 16:23:22.03ID:rHQmp5Mm0233デフォルトの名無しさん
2014/03/16(日) 18:58:01.80ID:NcMQ7vHT情報科卒業して、CSSやPHP弄ってる層に謝れよ。
0234デフォルトの名無しさん
2014/03/16(日) 19:00:27.81ID:rHQmp5Mmお前バカそうだな。
クイックソートやGoogleの検索エンジンの仕様も
アルゴリズムって呼ばれているわけだが、
お前が馬鹿にしているのが何かすらわかっていないだろう?
0235デフォルトの名無しさん
2014/03/16(日) 19:06:08.08ID:9d63KDz+アルゴリズムや数学をきちんと勉強しないから、人が考えたアルゴリズムをコードに起こす仕事になっちゃうんじゃ..
0236デフォルトの名無しさん
2014/03/16(日) 19:08:21.05ID:wQykVVMe0237デフォルトの名無しさん
2014/03/16(日) 19:15:10.66ID:NcMQ7vHTちょっと分厚い本をペラペラ捲ったら、アルゴリズム記述されてんのに、
そんなもの後で必要になってから調べて十分じゃないの?
頻出しそうなものなんて、木とネットワークフロー、DPぐらいしか思いつかないし、
BM法なんて、生涯にわたって使う機会が一度もない気がするわ
それよかPrologで出される制約問題でも解いた方が有意義じゃねぇの
0238デフォルトの名無しさん
2014/03/16(日) 19:16:09.34ID:rHQmp5Mm他人が考えたものを使うものとしか
考えてないんだろうな。
0239デフォルトの名無しさん
2014/03/16(日) 19:21:48.31ID:NcMQ7vHT若くて情熱が続くうちに、ページランクアルゴリズムでも再発明したらいいと思うよ
0240デフォルトの名無しさん
2014/03/16(日) 19:25:25.65ID:rHQmp5Mmアルゴリズムに期待したらいけなかったんじゃなかったのか?w
ページランクアルゴリズムを発明したGoogleは凄いことになりましたよね。
0241デフォルトの名無しさん
2014/03/16(日) 19:31:14.68ID:NcMQ7vHT0242デフォルトの名無しさん
2014/03/16(日) 19:36:16.50ID:rHQmp5Mmもうこれ以上レスしなければいい。
で、アルゴリズムをなにかわかってないから
そんなこと言ったんだよねw
0243デフォルトの名無しさん
2014/03/16(日) 19:36:24.56ID:9d63KDz+そりゃ、CSSやPHP弄ってるだけの場合はそんなもんだろ。お前の仕事に必要なければ勉強しなきゃいいさ。
ただ、人によって勉強する動機は異なるし、どんなアルゴリズムやデータ構造があるかを大雑把に知っておかないと、必要になった時に何をどう調べたらいいかもわからんだろ。
>>237 はもっと数学を勉強して、物事を合理的に考える力を養った方がいいな。
0244デフォルトの名無しさん
2014/03/16(日) 19:52:29.07ID:NcMQ7vHTだから、ペラペラ捲ってからで十分なんだって。
具体的な目標もなしに、アルゴリズムなんて勉強した所で身に付かないよ
そして、おまえらには目標がないので、ぺちぱーになる
0245デフォルトの名無しさん
2014/03/16(日) 19:55:39.38ID:LEh1TotOリファクタリングにしろ、デザパタにしろ、
OOPとはなんぞやの思想にしろ、
なんかしらのアルゴリズムにしろ、
必要になるまでまずその価値なんてわかんねえんだ。
0246デフォルトの名無しさん
2014/03/16(日) 20:02:22.78ID:rHQmp5Mmお前何言ってんだ?
アルゴリズムそのものの話だろ。
お前が言っているのは特定の場合の話であって
アルゴリズムそのもの話ではない。
0247デフォルトの名無しさん
2014/03/16(日) 20:14:21.59ID:NcMQ7vHTリファクタリング、デザパタの方が優先度上。
アルゴリズムの勉強なんてウンコしながらで良い
0248デフォルトの名無しさん
2014/03/16(日) 20:22:18.88ID:/mgBA8rW0249デフォルトの名無しさん
2014/03/16(日) 20:24:16.99ID:NcMQ7vHT皆、アルゴリズムの使い方と使う場面を知らないから講釈垂れてけよ
0250デフォルトの名無しさん
2014/03/16(日) 20:27:30.48ID:rHQmp5Mm俺、アルゴリズムの使い方と使う場面を知らないから教えてください。
返答例
だがことわるw
0251デフォルトの名無しさん
2014/03/16(日) 20:30:14.53ID:/mgBA8rW0252デフォルトの名無しさん
2014/03/16(日) 20:33:35.53ID:NcMQ7vHT■ このスレッドは過去ログ倉庫に格納されています