13/03/03 18:10:11.63 .net
【関連スレ】
3Dアルゴリズム全般
ｽﾚﾘﾝｸ(tech板)
＜集大成＞アルゴリズム大辞典
ｽﾚﾘﾝｸ(tech板)
アルゴリズム総合スレ in ム板
ｽﾚﾘﾝｸ(tech板)
アルゴリズムとデータ構造 - Kaneko Lab.
URLﾘﾝｸ(www.kkaneko.com)
アルゴリズムとデータ構造 - ソースコード探険隊
URLﾘﾝｸ(www.codereading.com)
各種アルゴリズムの C++ による実装 - Spaghetti Source
URLﾘﾝｸ(www.prefield.com)
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
URLﾘﾝｸ(vipprog.net)
2:デフォルトの名無しさん
13/03/03 19:34:43.55 .net
このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。
アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。
京都大学霊長類研究所
3:デフォルトの名無しさん
13/03/04 06:52:01.19 .net
>>2
アイ死ねw
4:デフォルトの名無しさん
13/03/04 09:31:25.12 .net
データ構造,アルゴリズムとデザインパターンは全然別のものだと
思っているのは私だけか。
5:デフォルトの名無しさん
13/03/04 18:21:16.78 .net
俺もそう思ってた。
6:デフォルトの名無しさん
13/03/16 20:52:01.53 .net
こっ…これは…
7:デフォルトの名無しさん
13/03/30 15:13:18.01 .net
どうでもいいが
8:デフォルトの名無しさん
13/03/31 03:27:52.92 .net
あげ
9:デフォルトの名無しさん
13/03/31 04:39:38.51 .net
デザパタとか言ってみたいお年頃なんだろ
10:デフォルトの名無しさん
13/03/31 04:58:49.37 .net
アルゴリズムって言ってみたいお年ごろと何が違うのかわからんが。
11:デフォルトの名無しさん
13/03/31 09:18:18.51 .net
デザパタはJavaのキツキツの制限を緩めるための苦し紛れの小細工
12:デフォルトの名無しさん
13/03/31 11:39:20.44 .net
アルゴリズムは科学
デザパタは工学
アルゴリズムは技術
デザパタは技能
アルゴリズムは理論
デザパタは療法
どれにしようか迷ったけど面倒だから全部書いた
13:デフォルトの名無しさん
13/03/31 11:57:47.66 .net
CTMCPすら読まずにオレ様定義を開陳し合う場となりました。
14:デフォルトの名無しさん
13/03/31 11:59:52.01 .net
デザパタは本来ならマクロ等で抽象化すべきところを
言語側の表現能力が低いために出来ず、結果として
似たパターンを繰り返し書く羽目になったパターンのカタログ集
15:デフォルトの名無しさん
13/03/31 14:04:01.24 .net
まぁ、確かに言語の補助が弱いのをプログラマの経験則から解決策として残されているものが多いわな。
現に、Javaなんかでは、singltonとかメンドクサイ事が必要だけど、C#とかでは、何のことも無かったりするし。
16:デフォルトの名無しさん
13/03/31 16:06:37.44 .net
それデザインパターンの考え方と
パターンの実装をごっちゃにしてるだろ。
アルゴリズムで言えば、C言語だとバブルソートは面倒くさい処理が必要だけど、
ある言語なら、bubble_sort関数呼ぶだけで済むしって言ってるようなもんだろ。
17:デフォルトの名無しさん
13/03/31 16:07:29.79 .net
デザインパターンって
データ構造とアルゴリズムを合わせたようなものだと思う。
18:デフォルトの名無しさん
13/03/31 18:44:57.28 .net
アルゴリズム＋データ構造＝プログラム
と昔から決まっておるのじゃ
19:デフォルトの名無しさん
13/03/31 19:19:48.54 .net
相変わらず知識に溺れたバカばっかりw
ウザウザw
20:デフォルトの名無しさん
13/03/31 20:12:11.44 .net
>>16
全然違う
なぜならC言語でもバブルソートは関数として抽象化できるから
一度書いたら何度も繰り返し書く必要は無い
21:デフォルトの名無しさん
13/03/31 20:18:39.62 .net
Strategyパターン
クロージャがある言語なら、ただ単にクロージャを渡すだけの普通のコードで、
名前を付ける必要すら感じない
どっかのゴミ言語ではこんな感じになってしまうが
URLﾘﾝｸ(ja.wikipedia.org)
22:デフォルトの名無しさん
13/03/31 20:28:53.41 .net
いや「特定のパターン」はそうだろうけど、
別のパターンはそうとは限らないだろ。
一つを語って、全てが無意味だとなんで思った？
23:デフォルトの名無しさん
13/03/31 20:34:45.76 .net
>>21
それ、クロージャがある言語でも大差ないと思う。
関数が第一級の言語だと、クラス図として関数も扱わないといけないはず。
で、クラス図に対応する、関数図は関数のシグネチャ。
明示的には継承とは書かないけど、決まった関数のシグネチャを継承した（同じに合わせた）
関数を作るから
[Strategy]
↑
[ConcreateStrategyA]
の代わりに、
[引数一つの関数]
↑
[実装関数]
こうなってるだけじゃないかな。
24:デフォルトの名無しさん
13/03/31 20:51:21.46 .net
そういう問題じゃない感
25:デフォルトの名無しさん
13/04/01 01:52:30.36 .net
URLﾘﾝｸ(www.amazon.co.jp)
定本 Cプログラマのためのアルゴリズムとデータ構造 近藤嘉雪著
この本もわかりやすいお
26:デフォルトの名無しさん
13/04/01 11:56:57.56 .net
データ構造とプログラミング（'13）
URLﾘﾝｸ(www.ouj.ac.jp)
27:デフォルトの名無しさん
13/04/02 07:33:33.68 .net
死んでしまえクズ共がw
28:デフォルトの名無しさん
13/04/03 07:33:59.54 .net
前スレの後半のような良スレになればいいなw
29:デフォルトの名無しさん
13/04/19 21:42:39.55 .net
Wordとかのエディタの「元に戻す」「Undo」機能ってどうやって実装されてるんですか？
Mementoパターンなるものをwikiで調べたんですが、Wordとかの大きな文書だと、
一つのstateのデータ量が多すぎて、すぐにメモリが足りなくなって破綻しそうな気がするんですが・・・
URLﾘﾝｸ(ja.wikipedia.org)
30:デフォルトの名無しさん
13/04/19 21:48:42.39 .net
全体のコピーじゃなくて差分と操作内容
31:デフォルトの名無しさん
13/04/19 21:58:43.00 .net
>>29
そこいらは腕の見せ所だから色々な実装がある。と言うのが
普通の答えだと思いまする。
結果データではなく、verbとパラメーターをリング状に記憶
させるという実装はしたことがある
32:デフォルトの名無しさん
13/04/19 23:38:59.62 .net
A→Bへの変化が起きるとき、B→Aへと戻る動作Δを登録していく。
Undo時に動作Δを呼び出す。
33:デフォルトの名無しさん
13/04/20 01:34:18.08 .net
wordの文書って画像いれなきゃ
数十キロしかないだろ？
34:デフォルトの名無しさん
13/04/20 07:13:11.67 .net
バカスレw
バカ共がまた知識ぶって騒いでやがるw
死ねゴミクズw
35:デフォルトの名無しさん
13/04/20 10:00:25.18 .net
リロケータブル形式で記憶しておけばメモリだけでなくファイル等も利用することが可能。
作業途中の状態保存にも使えて便利。
36:デフォルトの名無しさん
13/04/20 10:54:34.60 .net
stack.push(deflate(操作前のデータ xor 操作後のデータ))
とか思い付いたけどどうよ？
37:デフォルトの名無しさん
13/04/20 12:19:10.51 .net
簡単にジャーナルを取れるのに差分計算するとか
アホの極み
38:デフォルトの名無しさん
13/04/30 22:53:00.60 .net
C++でstateパターンを実装していたんだが、実はCライクに関数ポインタを使った実装のほうが短くて簡潔書けることがわかった。でも他人が見たら何をやっているのかわかりづらいかもしれないから、多少手間になっても決まったデザインパターンでやるほうがいいのかもしれない。
39:デフォルトの名無しさん
13/05/21 00:35:42.34 .net
>>29
UndoでMementoってのは、実は多くの場面で使いにくいんじゃないかなーって思ってる
Adobeのアンドゥは無限回じゃないけど、あれはこのパターン使ってるのかな
40:デフォルトの名無しさん
13/06/09 19:06:14.70 .net
WikipediaのクイックソートのC言語での実装で、
whileループの最後の i++; j--; はなぜ必要なんですか？
ｈｔｔｐ:／／ja．wikipedia．prg/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88#.E5.AE.9F.E8.A3.85.E4.BE.8B.EF.BC.91
全角．はリンク禁止回避
41:桃白白 ◆9Jro6YFwm650
13/06/09 19:26:26.73 .net
>>40
i++; j--;がないと仮定すると
a[i]がpivotと同じ値だったらiが進まない。
a[j]がpivotと同じ値だったらjが進まない。
効率が悪い、無限ループになる恐れがある。
なので、i++; j--;は無限ループを回避するために必要であるか、
または、効率を良くするために必要なのである。桃白白はそう思うのである。
42:デフォルトの名無しさん
13/06/09 19:48:02.69 .net
なくても問題ないが
43:デフォルトの名無しさん
13/06/10 09:15:30.73 .net
まだやってるw
さっさと死ねw
44:デフォルトの名無しさん
13/09/18 13:39:49.18 .net
入門 データ構造とアルゴリズム [大型本]
Narasimha Karumanchi (著), 黒川 利明 (翻訳), 木下 哲也 (翻訳)
この本はおすすめですか？
URLﾘﾝｸ(www.amazon.co.jp)
45:デフォルトの名無しさん
13/09/18 14:11:03.23 .net
>>44 が何者かによる。学生さんならいいんじゃない？プロならう～ん…個人的にはいらないかな(買わなかった)
46:デフォルトの名無しさん
13/09/18 19:27:36.43 .net
>600弱の練習問題とその解
・・・ｗ
47:デフォルトの名無しさん
13/09/18 23:07:49.85 .net
プログラミングの宝箱っていう本、誤りが多すぎる。
なんで売れているの？
48:デフォルトの名無しさん
13/09/21 16:31:47.20 .net
真の宝の周りにはたくさんの偽りの情報が紛れているものさ
49:デフォルトの名無しさん
13/09/21 16:58:27.85 .net
世の中、見た目で判断する人が多いから
50:デフォルトの名無しさん
13/09/22 10:28:15.10 .net
見た目は大事
51:デフォルトの名無しさん
13/09/22 20:22:12.39 .net
プログラミングの宝箱っていう本、見た目がいいの？
見た目がいいってどういうこと？
52:デフォルトの名無しさん
13/09/22 20:24:16.43 .net
杉原厚吉のデータ構造とアルゴリズムの本ってソートのプログラムも
載っていないんだね。だめだめ。
53:デフォルトの名無しさん
13/09/22 20:25:25.63 .net
セジウィックの本もどこがいいのか分からない。
プログラムが読みにくいし。
やっぱりクヌースの本が一番いいのかな。
54:デフォルトの名無しさん
13/09/22 20:27:01.59 .net
>>47
その本、クイックソートのプログラムが間違っているよね。
55:デフォルトの名無しさん
13/09/22 21:23:03.07 .net
>>47
そもそも売れてるの？
56:デフォルトの名無しさん
13/09/22 22:06:44.18 .net
ソフトバンククリエイティブの本っていい加減な本が多いような気がする。
57:デフォルトの名無しさん
13/09/22 22:11:29.25 .net
ところでアマゾンのランキングって何のランキングなの？
たとえば、アルゴリズムの本のランキングを見るとどう見ても売れていない
ような絶版の中古本がランクインしていたりする。
58:デフォルトの名無しさん
13/09/22 22:14:08.27 .net
ところで、MITのOpen Coursewareで勉強している人はいない？
59:デフォルトの名無しさん
13/09/22 22:16:07.27 .net
柴田望洋のアルゴリズムとデータ構造の本、レベル低すぎ。
なんなの望洋ってｗ
60:デフォルトの名無しさん
13/09/22 22:17:15.56 .net
>>58
どのコース？
61:デフォルトの名無しさん
13/09/22 22:17:59.43 .net
見慣れない本質不必要な単語が頻出するから
講義系のテキストは却下だな
62:デフォルトの名無しさん
13/09/22 22:29:45.56 .net
まだ下の上二つを見始めたところです。英語はよく分かりませんが、板書を見て大体
分かります。見ている（見た）人がいたら質問とか今後すると思うのでお願いします。
Pythonによるプログラミングの入門の講義。レベルが低い。
URLﾘﾝｸ(ocw.mit.edu)
コンピューターサイエンスのための数学。レイトン教授が最高に面白い。
URLﾘﾝｸ(ocw.mit.edu)
まだ見てないけど、和田英一が訳した有名な教科書の著者の講義。まだ見ていない。
URLﾘﾝｸ(ocw.mit.edu)
アルゴリズム入門2005年。まだ見ていない。リベストらの有名なアルゴリズムの教科書の著者が講義。
URLﾘﾝｸ(ocw.mit.edu)
アルゴリズム入門2011年
URLﾘﾝｸ(ocw.mit.edu)
63:デフォルトの名無しさん
13/09/22 22:49:56.98 .net
>>62
アルゴリズムの講義なら Coursera や Udacity あたりに新しいのがいっぱいあるぞ。セジウィックが講義してるのもあるし。
URLﾘﾝｸ(www.coursera.org)
そういう自分も Coursera の前は>>62の最後のコースでアルゴリズム勉強したわ。
古いからちょっと画面が小さいんだよねー。
64:デフォルトの名無しさん
13/09/22 22:54:12.17 .net
>>63
情報ありがとうございます。そっちも視野に入れたいと思います。
65:デフォルトの名無しさん
13/09/26 13:01:06.57 .net
死ねゴミ共がw
死ねゴミ共がw
66:デフォルトの名無しさん
13/09/28 06:46:14.59 .net
オライリーから出たインド人のアルゴリズムとデータ構造の本、最悪。
説明もほとんどなしにコードと問題が載っているだけ。
買ってはいけない。
67:デフォルトの名無しさん
13/09/28 16:59:53.64 .net
>>66
コードと問題が説明になっているのだろう。
68:デフォルトの名無しさん
13/09/28 17:57:20.08 .net
あれは演習問題集だから…
69:デフォルトの名無しさん
13/09/28 18:16:31.35 .net
資格勉強に役立つ？
70:デフォルトの名無しさん
13/09/28 18:28:54.24 .net
就職や昇級に反映されるなら役立つ
そうでなければ趣味
71:デフォルトの名無しさん
13/09/29 12:57:58.61 .net
アルゴリズムやデザインパターンって公式的に覚えてしまったら、
中身がどうなっているかどうか知っていようといまいと生産性は変わらない。
ただ中身を知っていると、何かトラブルが起きたり、
それらを組み合わせて新しいことを覚えなくてはいけないときに差が出てくる。
が、今時はそういうことはかなり稀なので、機械的に覚えてしまって、
さっさと人を使う立場になってしまう方が悩まなくていいかも。
72:デフォルトの名無しさん
13/09/29 15:55:56.14 .net
>>71
トンチンカンなこと言ってるぞ？ ライブラリレベルまで落とし込まれているような
アルゴリズムならともかく、デザインパターンは公式的に覚えて使えるもんじゃ
ないぞ。中身の実装方法はともかく、GoFのデザインパターンですら、複数
組み合わせて使うのが普通なのに。
73:デフォルトの名無しさん
13/09/29 15:59:49.30 .net
effective javaのいってんじゃねーの
俺ってやさしい
74:デフォルトの名無しさん
13/10/02 01:48:18.78 .net
>>66
君、アマゾンのレビューを書いた人？
星一つしかついてなかったｗ
75:デフォルトの名無しさん
13/10/02 06:46:43.90 .net
率直に言って、C++という言語はデータ構造を分からせるのには向かない。
内容は時間的/空間的計算量という評価に徹してデータ構造とその読み出し方を
解説したもので、むしろ優れた本だと思う。
76:デフォルトの名無しさん
13/10/02 08:06:05.95 .net
>>75
普通の大学で使うような教科書のほうがいいと思う。
エイホ・ホップクロフト・ウルマンのアルゴリズムとデータ構造とか
MITの教科書とか。
77:デフォルトの名無しさん
13/10/02 08:33:04.43 .net
Ahoの本は良いな
はずれがない
78:デフォルトの名無しさん
13/10/02 09:11:06.55 .net
クヌースの本も読んだほうがいい？
クヌースの本はプログラマ必読の書らしいけど
79:デフォルトの名無しさん
13/10/02 11:01:55.61 .net
>>78
全部読むのは難しいんじゃないですか？
アルゴリズムの解析の部分は難しいし、実益が少ない。
アルゴリズムの手順だけ読むくらいでいいのでは？
あと新しいアルゴリズムが書かれていないらしい。
80:デフォルトの名無しさん
13/10/02 11:55:09.13 .net
クヌース（ブルース風に）
81:デフォルトの名無しさん
13/10/02 19:03:31.81 .net
クヌースは古典だな
読むか読まないかなら、もちろん読んだ方がいいが
>>79
新しいアルゴリズムは論文読むしか
82:デフォルトの名無しさん
13/10/03 10:30:06.56 .net
クヌース ホシーイ ケレード
ゼパーン ニナーテ ルヨーネ
シカータ ナイカーラ エイーゴ
デヨンデール
83:デフォルトの名無しさん
13/10/03 14:33:48.67 .net
>>79
ところで新しいアルゴリズムてどんなの？
遺伝とかならいらないけど
84:デフォルトの名無しさん
13/10/03 19:57:54.46 .net
>>83
すみません。よく知りません。
擬似乱数を生成するメルセンヌツイスターが載っていないって、
考案者が文句言っていたのは知っています。
85:デフォルトの名無しさん
13/10/03 20:17:33.09 .net
クヌースの本は要約版が1冊になって出版される予定だけど、実現しないだろうね。
というかThe Art of Computer Programming自体が完成しないか。
既刊の第4巻はおもしろそう。
86:デフォルトの名無しさん
13/10/04 09:08:51.46 .net
わざと初等的な証明をつかってるから
無駄にめんどくさいね。
群とか環とか使えば良いのにっておもうよ。
87:デフォルトの名無しさん
13/10/04 09:12:18.81 .net
self containedになっているのだろう
88:デフォルトの名無しさん
13/10/07 09:07:45.97 .net
>>84
あの膨大な本の中の、たった一つのテーマだからね。
89:デフォルトの名無しさん
13/10/07 20:33:21.18 .net
C++のメソッドの呼び方で質問です。
サブクラスからサブクラスを呼ぶときに、スーパークラスを無視した以下の書き方はオブジェクト思考的には違反でしょうか？
void AppDerived::method(){
(static_cast<DetailDerived*>(ptr))->func();
}
スーパークラス(AppBase)のヘッダにmethod()を追加したり、なるべくさわりたくないので上記の方法を思いつきました。
クラスの繋がりは以下の通りです。
class AppBase{
DetailBase* ptr;
}
AppBase ◆－ DetailBase
AppBaseとDetailBaseはコンポジット関係です。
class AppDerived : public AppBase{
void method()
}
class DetailDerived : public DetailBase{
void func()
}
90:89
13/10/07 23:01:02.14 .net
補足です。
void AppDerived::method(){
ptr->func();
}
class DetailBase{
virtual void func(){ return; }
}
上記の方法を避けたいための方法です。
91:デフォルトの名無しさん
13/10/07 23:12:12.86 .net
>>89
>オブジェクト思考的
は関係ないね,、C++の実装としてだろう
92:デフォルトの名無しさん
13/10/08 00:52:45.41 .net
>>89
その派生クラス同士の関係性によってはアリな場合もあるんだけど、 一般的には無しだね。
基底クラスを触りたくないからと言うのは全く理由にならないと思うよ。
93:デフォルトの名無しさん
13/10/08 10:05:07.76 .net
>>89
AppBaseがコンポジションするDetailBaseはPublicやProtectedってことでしょ？
それなら派生クラスから弄られることを想定しているってことになるから
AppDerivedのMethod()で新しくDetailDerivedを保持し直したらいいんじゃないの？
Privateなら基底クラスでしかDetailBaseを弄らないのだから
AppDerivedのMethod()内でのみ使用するためにDetailDerivedのインスタンス生成すりゃいいんじゃないの？
>>90の方法を避けたいってのは、AppBaseがDetailBaseをコンポジションしてポリモーフィズムするのを
否定しちゃってんじゃないの？コンポジションしている意味が無くならない？
94:デフォルトの名無しさん
13/10/09 18:19:09.59 .net
ﾌﾟｯw
95:デフォルトの名無しさん
13/10/10 07:27:16.17 .net
ｸｻｯ
96:デフォルトの名無しさん
13/10/10 07:54:38.65 .net
すまん
97:デフォルトの名無しさん
13/10/10 08:38:38.27 .net
おまえかよ
98:デフォルトの名無しさん
13/10/10 18:02:10.65 .net
このように他人（主に女の子）の汚名を代わって受けるのがイケメンパターン
99:デフォルトの名無しさん
13/10/12 18:05:18.38 .net
死ねゴミ共がw
死ねゴミ共がw
100:デフォルトの名無しさん
13/10/12 21:43:22.30 .net
落ち着け
101:デフォルトの名無しさん
13/10/13 14:04:12.97 .net
ある順序列Aとそれに含まれる一部の要素からなる順序列Bがあるとき、
Bの順序を満たし、かつAから「変化が少ない」順序列Cを得たい。
A: [ 1 2 3 4 5 ]
B: [ 4 3 ]
C: [ 1 2 4 3 5 ]
「変化が少ない」の基準は必ずしも特定しないが、一例として「各要素の
移動距離の二乗和が小さい」などが考えられる。
ここで、近似解でよいので計算量の少ないアルゴリズムが欲しいのですが、
使えそうなアルゴリズムがあったら、ググるキーワードを教えてください。
102:デフォルトの名無しさん
13/10/13 14:24:30.97 .net
要素の重複とかあるの？
103:デフォルトの名無しさん
13/10/13 14:29:12.64 .net
>>101
> 「変化が少ない」の基準は必ずしも特定しないが、一例として「各要素の
> 移動距離の二乗和が小さい」などが考えられる。
これに激しく違和感を感じるけど、
> ここで、近似解でよいので計算量の少ないアルゴリズムが欲しいのですが、
近似解でいいならGAが楽じゃね？
104:デフォルトの名無しさん
13/10/13 15:28:06.54 .net
Aを走査していき、Bにも含まれる要素に当たったら、Bの要素順で置き換える
……だと変化が大きいのかもしれないのか
105:101
13/10/13 16:04:56.10 .net
>>102
重複はない前提です。
>>103
その基準のところも、なにか使えそうなものがあれば調べてみたいと思いますが。
ところで、どういうところで違和感を感じるでしょう？
>>104
Bの並びによっては団子になってしまいそうですが、確かに計算量は非常に
少なそうですね。
106:デフォルトの名無しさん
13/10/13 16:45:07.14 .net
>>105
順列と最小二乗って、同じ目的で使って嬉しくなる数学的根拠があるのかな、と思って。
置換の数で距離を測るのが一般的かな？とか。
感覚的な意見で申し訳ないけど。
107:デフォルトの名無しさん
13/10/13 17:11:59.64 .net
感覚的なものなのでそこはあまり根拠はないですが、移動距離が大きくなるにつれて
ペナルティは増大するほうがいいのかなと。
ただまぁ、ひとつの要素が移動すればその距離に応じて他の要素もずれるわけなんで、
移動距離の総和とかあるいは単純に移動した要素の数でもいいかもしれないですね。
順序の距離とか順列間の距離とかで探したらいくつか距離の定義が見つかりました。
108:デフォルトの名無しさん
13/10/14 09:57:46.64 .net
死ねゴミ共がw
109:デフォルトの名無しさん
13/10/14 10:21:17.60 .net
落ち着け
110:デフォルトの名無しさん
13/11/03 22:41:37.52 .net
グーグルのアルゴリズムコンテストとか受けてるやついる？
111:デフォルトの名無しさん
13/11/18 20:09:19.22 .net
全要素の値を0で初期化した要素数nの一次元配列にたいして、
ランダムに選んだm (< n) 個の要素のみ値を1にした配列を作りたいです。
次の方法を考えました。
1. 先頭からm個の要素の値を1に、残りの要素の値を0にした配列を用意する。
2. その配列に対して Fisher-Yates shuffle を施す。
これよりも実行速度において効率的な方法はあるでしょうか。
（並列化を利用して効率よくする方法もアリです）
ただ、できるだけ偏りは無くしたいです。
112:デフォルトの名無しさん
13/11/18 20:13:31.20 .net
nとmをどれくらいに想定してるのさ
113:デフォルトの名無しさん
13/11/18 20:56:55.33 .net
>>112
n は 1000000 くらい
m は 1000 log 1000 くらいなので、だいたい 7000 弱程度です
114:デフォルトの名無しさん
13/11/18 20:59:21.68 .net
（その程度だと、どんな馬鹿なアルゴリズムでも一瞬で終わる処理だと思うが、何らかの効率的アルゴリズムが欲しい理由でもあるのかも……）
115:デフォルトの名無しさん
13/11/18 21:24:13.39 .net
>>114
もっと巨大な配列なら、より効率的な方法があるのでしょうか。
どんな方法か知りたいです。
116:デフォルトの名無しさん
13/11/18 22:58:36.70 .net
>>115
くじ引きと同じ論法でO(N)で作れるだろ
117:デフォルトの名無しさん
13/11/19 07:10:30.69 .net
>>116
それって、1000000個の重複のない数列から7000個を取り出すんだろ？
重複のないくじを作るのに結局シャッフルがいるんじゃないのか？
だったら、やってることは>>111と同じだと思うが
というか、>>111だってシャッフルはO(N)なんだから、
そもそも質問の意図もよう分からんが
118:デフォルトの名無しさん
13/11/19 07:44:36.62 .net
>>117
シャッフルは要らない。n本のくじの中にm本の当たりがある場合と同じ。
それを配列番号1からn番まで引く。くじ引きは何番目に引こうが当たりが出る確率は等確率。
>>111も確かにO(N)だな。ソートと勘違いしてた。
だけどくじ方式の場合は逐一頭から取り出す場合は配列を用意する必要はないし、
必要な分だけ計算すればいい。
int array[n];
for (size_t i=0; i<n; ++i) {
bool hit = m/(n-i)の確率のrand;
if (hit) {
--m;
array[i] = 1;
} else {
array[i] = 0;
}
}
119:デフォルトの名無しさん
13/11/19 13:06:53.22 .net
偏りをなくしたいということは低周波成分をなくしたいということかな？
すなわち、1が連続したり、なかなか出なかったりするのを無くすということ。
だったら乱数を使うのは誤り。
120:デフォルトの名無しさん
13/11/19 20:29:44.62 .net
>>118
すごいですね、その発想は出てこなかったです。
簡単な例で図を描いて確かめてみましたが、みんな当たる確率は同じになりました。
Fisher-Yates shuffle でやるより断然スジがいいです。
採用させてもらいます。
>>119
たしかに、1 や 0 があまりに連続しているの好ましくないです。
その場合、乱数を使わずにどうやるのでしょうか。
1 か o かを選ぶのに乱数を使うのではなく、もっと別のところで使うという意味でしょうか。
それとも、全くどこにも使わないのでしょうか。
121:デフォルトの名無しさん
13/11/19 21:16:46.95 .net
>>120
乱数から低周波成分を除去した数列を使います。別名ブルーノイズ。
配列を参照するだけなので超高速で偏りの無いパターンを作ることができる。
100万個から7000個を選んでも１が連続する確率は0。規則性もなし。
ブルーノイズ数列の一部をとってもブルーノイズ数列。使い回しができる。
欠点として１回はブルーノイズ数列を作る必要があるが時間がかかる。100万個
の数列だと1時間くらいかかる。一回作ってファイルに保存しておけばOK。
122:デフォルトの名無しさん
13/11/19 21:23:07.46 .net
>>120
不思議に思ったんだがひょっとして
配列の全要素の初期値って不定扱いなのか？
なら>>118を採用する理由もわかるが
123:デフォルトの名無しさん
13/11/19 22:01:24.83 .net
言語にもよるけど、int 型なら多くの場合0じゃない？
で気づいたけど、1 か 0 しか入らないなら bool 型でいいんじゃないか？メモリもグッと節約できる。
124:デフォルトの名無しさん
13/11/19 22:12:20.58 .net
>>122
いえ、今回は、必ず何らかの値で初期化される、という種類のデータ構造（配列）を使っています。
（言語的は初期値として未定を表す値を指定できる配列も簡単に作れますが、
今回は意味ないので、そのような配列は使っていません）
>>118を採用しようと思ったのは、配列の頭から順に要素をトラバースしながら、
その要素のみを参照して値を設定していけるという点がシャッフルに比べて優れていると思ったからです。
要するに、データ構造そのものをどんどん大きくしながら作っていけます。
シャッフルも Fisher-Yates shuffle でしたら順にトラバースしますが、
その要素と、別のランダムに選んだ要素を参照しなければならず、
シャッフル処理をする前にデータ構造が完全に出来上がっていなければなりません。
その上で要素をスワップしていきます。
じつはプログラミング言語はCではなくHaskellを使っており、Haskellでは後者より前者のように、
値を入れた要素を次々と繋げながらデータ構造を（目的の規模まで）大きくしていく方が
プログラムしやすいんです。
>>123
すいません、0 と 1 を使ったのは単に質問をシンプルにするためでした。
本当は、質問で 1 を入れるところでは min < x < max のランダムな浮動小数点を入れます。
そもそもの目的をぶっちゃけますと、ランダムな重み付き有向グラフの隣接行列を作ることです。
125:デフォルトの名無しさん
13/11/19 22:14:23.54 .net
>>124
> >>118を採用しようと思ったのは、配列の頭から順に要素をトラバースしながら、
> その要素のみを参照して値を設定していけるという点がシャッフルに比べて優れていると思ったからです。
すいません、ちょっと言い方がおかしいですね。
配列の頭から順に要素をトラバースしながら、ではなくて、順に配列を大きくしながら、
とか、配列を組み上げながらと言うべきでした。
126:デフォルトの名無しさん
13/11/19 22:23:35.67 .net
>>121
申し訳ないです、そこまで強力なものは今回は求めていないです。
あまりに偏りすぎていると使えないな、という程度のことでした。
しかし、これはこれで大変興味深いです。
ホワイトノイズやピンクノイズなどは聞いたことがありますが、ブルーは初耳です。
調べてみます。
127:122
13/11/19 22:35:24.77 .net
なるほど納得
非零要素を一次元上（あるいは二次元とか）に並べて
それを仮想電子のようにみなし仮想クーロン斥力みたいなの計算して
要素番号補正したらとか考えてたんだが
それだと逆に傾向出ちゃうか
値を入れた同じ行、同じ列に対して再度選択を阻害するパラメーターを入れて
云々かんぬん…いかん、わけがわからくなってきた
逃走っ（しゅたたた…）
128:デフォルトの名無しさん
13/11/19 22:54:30.96 .net
やってみましたら、たとえ Haskell であっても、
>113 程度の規模ではシャッフルでもくじ引きでも、あっという間でした。
>>114 の指摘通りで、かなり恥ずかしいです。
憶測で遅いと決めつけず、質問する前に試すべきでした。
プログラムの見やすさが抜群に良いという点で、くじ引きの方法でやることにします。
みなさん、ありがとうございました。
129:デフォルトの名無しさん
13/11/27 04:14:03.66 .net
Edmonds's Blossom Algorithmを詳しく説明していただけないでしょうか
130:デフォルトの名無しさん
13/12/14 23:50:45.85 .net
二次元座標に、ラベル(高さ固定、横書き)を 重ならないように配置したいです。
現在は、y軸をラベル高さで分割して、
各領域で、ラベルが指定座標を含むように左側から詰めて配置しています。
この方法だと、3点以上集中すると、大きくずれてしまいます。
どのようなアルゴリズムがありますでしょうか？
また、動的生成なので、優先順位は コスト > 見栄え です。
131:デフォルトの名無しさん
13/12/15 02:57:49.26 .net
>>130
ある点を矢印で示すようなラベルなら多少点から離れてもいいよね
それなら幾らでもやり方はあると思うよ
例えば、点や四角（ラベル）の当たり判定で配置
132:デフォルトの名無しさん
13/12/15 12:12:29.22 .net
>>131
おっしゃる通り、多少離れるのはかまわないです。
>点や四角（ラベル）の当たり判定で配置
ラベルの矩形の判定はやってみたのですが、
どの方向にずらすべきかのところで詰ってしまいました。
結果、上記のx軸+方向のみ補正な方法になってしまいました。
何かヒントがいただけたらと思います。
133:デフォルトの名無しさん
13/12/15 15:32:28.35 .net
>>132
そういったアルゴリズムを組んだことはないけど
ラベルの矩形が重なった時
指し示す点とラベルの四隅の点との距離が一番短いラベルの点を選出し
最初に、2点間の傾きを保ちならがら、そのラベルが指し示す点との距離を縮めて
縮めた際に2点間の距離が0になっても矩形が重なっているなら2点間の傾きを変える
目安となる距離と傾きの初期値を設定しておけばいいかな
傾きの初期値はラベルの4隅それぞれ、回転して考える
判定する矩形の4隅の点を左下にのみ、指示す点の45度右上の傾きにラベルを固定してしまってもいいかもね
机上の空論だから上手くいくかどうか分からないのは許してね
難しく考えすぎているのかもしれないわ
134:デフォルトの名無しさん
13/12/16 00:06:30.24 .net
こういう事ができればいいんでしょ
URLﾘﾝｸ(ja.wikipedia.org)(%E3%82%B0%E3%83%A9%E3%83%95%E6%8F%8F%E7%94%BB%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)
キーとなるのはここ
＞グラフの頂点と辺に仮想的な力を割り当て、力学的エネルギーの低い安定状態を探す
＞それぞれの辺をフックの法則にしたがうばねとみなし、それぞれの頂点をクーロンの法則にしたがう電荷をもつ粒子とみなす。
自分が以前勉強した時はgrineditっていうオープンソースソフトが解りやすかった
135:デフォルトの名無しさん
13/12/16 21:53:44.96 .net
力学エネルギーに基づくグラフ描画が求めていたもののようです。
まとまった時間を作って、出ているアルゴリズムを読んでみます。
お付き合いしてくださった皆様ありがとうございました。
136:デフォルトの名無しさん
13/12/28 23:22:37.13 .net
グーグルの検索エンジンのアルゴリズム
URLﾘﾝｸ(webblogsakusei.main.jp)
137:デフォルトの名無しさん
14/01/17 16:44:24.77 .net
ふぇぇ」
138:デフォルトの名無しさん
14/01/19 15:03:35.30 .net
計算量のオーダーの考え方で質問です。
(a # b) を a の b 個の下降階乗冪を表す式とし、
(#) は除算 (/) よりも優先順位が高いとします。
x や y は m よりも十分大きい数とすると、
f(m) = x#m / y#m
この場合、計算量のオーダーは O(m) と考えていいでしょうか。
139:デフォルトの名無しさん
14/01/19 22:30:57.31 .net
ダーク構造、エルゴリズム、ディザインパクトに見えたマジで。
140:デフォルトの名無しさん
14/01/20 22:08:25.07 .net
下記の問題について、私が考えた方法では計算量が n 乗のオーダーになってしまい、
たいして大きくない数で試しても計算にかなり時間がかかるのですが、
みなさんならどのような解き方をするでしょうか。
[問題]
m 枚のカードの束からランダムに x 枚引き（x <= m）、引いたカードに印をつける。
引いたカードを元のカードの束に戻し、再度ランダムに先ほどと同数 x 枚引き、
印がついていなかったら印をつけ、また元の束に戻す。
このように x 枚カードを引いて印を付けて戻す行為を n 回繰り返した後、
m 枚のカードの束に印のついていないカードが p 枚ある確率を求める関数 F(m, x, n, p) を作れ。
141:140
14/01/20 22:09:20.78 .net
[私の考え]
全体の事象は、{C(m,x)}^n です。（関数 C(a,b) は組み合わせ aCb）
m 枚のカードから x 枚引く行為を n 回繰り返した後に結局
p 枚無印で残る引き方のパターン数を求める関数 R(m, x ,n, p) は漸化式で、
R(m, x ,n, p) = Σ[i=0..x]{ R(m, x, n-1, p+i) * A(m, x, p+i, p) }
ただし、
n = 1 かつ p = m-x ---> C(m, x)
(n = 1 かつ p ≠ m-x) または (n >= 2 かつ p > m-x) ---> 0
ここで関数 A(m, x, p, q) は、p 枚無印で残ってた状態を q 枚無印で残るようにするような、
m 枚のカードからの x 枚のカードの引き方のパターン数で（q <= p）、
A(m, x, p, q) = C(m-p, x+q-p) * C(p, p-q)
よって、F(m, x, n, p) = R(m, x ,n, p) / {C(m,x)}^n です。
これをこのまま素直にプログラムコードにしています。
[欠点]
関数 R の計算量がざっと O(x^n) です（本当は他の変数もオーダーに関わってますが）。
分割統治でやってるのだからマルチコア使って並列処理できるのですが、
もっと根本的にアルゴリズムを改善したいです。
142:デフォルトの名無しさん
14/01/20 22:18:46.73 .net
ちょいと質問だけど、有理数で計算してるの？
143:140
14/01/20 23:12:18.37 .net
>>142
私は、関数 R と D と {C(m,x)}^n の計算は任意精度整数で、
関数 F 内の割り算は有理数型で、
そして最後にそれを倍精度浮動小数点型にしています。
144:デフォルトの名無しさん
14/01/20 23:44:20.55 .net
これってアルゴリズムの問題じゃなくて数学の問題じゃね？
オイラーのガンマとか関係してそうだけど。数学できるやつならパパっと式が出てくるんだろうな。
残念ながら僕は数学ができたという過去形なので無理です。
145:デフォルトの名無しさん
14/01/21 00:23:40.46 .net
F(m,x,n,p)=C(m,p)*{C(m-p,x)/C(m,x)}^n ？
146:140
14/01/21 00:24:59.04 .net
>>144
わたしも、これを代数的に解く方法は知らないのでプログラムで解こうと思いました。
プログラムで解く場合に n 乗よりも低いオーダーのアルゴリズムが存在しないのなら諦めます。
今のところ私が挑戦した限りでは、n 乗のオーダーが限界でした。
147:140
14/01/21 00:42:19.10 .net
>>145
それは違います。
例えば F(4, 2, 2, 1) で計算してみてください。
つまり、4枚のカードから2枚ランダムに引くことを2回繰り返して、
一回も引かれなかったカードが1枚存在する確率です。
本当は 2/3 ≒ 66% です。
しかし >>145 で計算すると 1/1 = 100% になってしまいます。
148:デフォルトの名無しさん
14/01/21 01:34:30.52 .net
>>145
C(m,p) で選んだp枚に対し、m-p枚からx枚選ぶ過程が一意でなく重複が入ってるから×だな
149:デフォルトの名無しさん
14/01/31 19:15:00.72 .net
a[0]からa[n-1]までの配列があって、
その中身をコンマで区切って表示したい
print a[i] + ','
みたいなことをすると、最後の要素にもコンマが付くので、
これをうまく避けるアルゴリズムは無いものか
150:デフォルトの名無しさん
14/01/31 19:50:00.15 .net
if (a=next()) { push(a); while (a=next()) push(cat(",",a)); }
151:デフォルトの名無しさん
14/01/31 21:02:09.78 .net
for (int ic = 0; ic < n; ++ic) {std::cout << a[ic]; if (ic < n - 1) std::cout << ',';}
152:デフォルトの名無しさん
14/01/31 21:15:03.01 .net
出力してしまわずに一旦文字列に出して、
出来上がってから最後のコンマを1個削る
153:デフォルトの名無しさん
14/01/31 21:30:32.04 .net
n が小さければ >>151 の方法でOK。シンプルでわかりやすい。
ただし、if 文で n 回の比較が発生するから、n があまりに大きい場合は >>152 のやり方がいいと思う。
最後の文字を削れない場合は for 文で a[n-2] まで ',' と一緒に出力して、追加で a[n-1] を出力するか。
>>150 は何の言語？
154:デフォルトの名無しさん
14/01/31 21:35:58.74 .net
最初の要素と残りの配列に分ければいいだろと、Haskell なら考える
155:デフォルトの名無しさん
14/01/31 22:35:19.83 .net
分ければ簡単なんだけど、同じような処理を2回書く羽目になるんだよな
156:デフォルトの名無しさん
14/01/31 22:38:32.60 .net
>>149
puts a[0..n-1].join('.')
157:デフォルトの名無しさん
14/01/31 22:49:27.58 .net
結局、うまい方法が無いので言語側で join 機能を提供している
join があるならそれを使うのが最もスマート
158:SD
14/02/01 15:47:33.85 .net
String d=""
String r="";
for(String b:a){r+=d+b;d=",";}
159:デフォルトの名無しさん
14/02/01 16:20:22.09 .net
コンマが先にあると考えて、先頭のコンマを削除する方式だな
毎回同じ値で更新するのが美しくない
160:デフォルトの名無しさん
14/02/01 16:50:11.43 .net
if(0<a.length)print(a[0]);
for(int i=1;i<a.length;i++)print(','+a[i]);
161:デフォルトの名無しさん
14/02/01 17:23:17.66 .net
それが正解だろうな
lengthが2回出てくる以外は殆ど無駄がない
162:デフォルトの名無しさん
14/02/01 17:47:07.99 .net
printの部分が長いコードなど２つに分けたくない事情があるときは>>158の方がいい。
定数へのポインタを代入するだけなので効率も悪くない。
163:デフォルトの名無しさん
14/02/01 18:04:45.52 .net
長くなくても、似た出力が2箇所あるのは嫌だな
コンマ部分だけ出力が別にあるのは構わないけど
str = a[i]; if (i < n - 1) {str += ','}
こうすれば一箇所
>>151とほぼ同じ
164:デフォルトの名無しさん
14/02/01 18:09:57.02 .net
俺もかつては悩んだがあるとき以降はずっとこう書いてる。
for (int i = 0; i < a.size; i++) {
if (i != 0) print(,)
print(a[i])
}
165:デフォルトの名無しさん
14/02/01 18:53:19.10 .net
俺ならdo-whileの条件文にカンマ出力ねじ込んで軍事法廷に召喚される
166:デフォルトの名無しさん
14/02/01 19:42:53.65 .net
>>164
for (int i = 0; i < a.size; i++) {
print(a[i])
if (i < a.size - 1) print(,)
}
最初だけコンマを付けない、よりは最後だけコンマを付けない、の方が
人間が理解しやすいような
ただ、条件文が読みにくい
167:デフォルトの名無しさん
14/02/01 19:46:34.49 .net
は？
168:デフォルトの名無しさん
14/02/01 19:48:28.34 .net
二個目以降はカンマがつくよ、であり読みやすい。
しかも、ループごとの状態がたとえば[a, b, c]のとき、
0: a
1: a, b
2: a, b, cとなっておりどの状態も気持ちいい。
後カンマ方式だと、
0: a,
1: a, b,
2: a, b, cとなり、0と1の状態が気持ち悪い。
169:デフォルトの名無しさん
14/02/01 21:03:39.16 .net
それはただのバグだな
170:デフォルトの名無しさん
14/02/01 23:11:17.91 .net
関数型の発想で命令型のコードを導く手順
(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
}
# URLﾘﾝｸ(docs.ruby-lang.org)
(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言語へ移植することも容易いだろう
171:デフォルトの名無しさん
14/02/01 23:18:11.99 .net
>>168
この考え方、感じ方は大事だね
例えば、これを範囲を指定してコンマ区切りの文字列を返す関数にしたら
前者ならすんなり行く
172:デフォルトの名無しさん
14/02/02 00:01:46.64 .net
テキストエディタでコンマ区切りのデータを編集する時に、
どうしてもコンマが余ったり足りなかったりする
173:デフォルトの名無しさん
14/02/02 00:49:30.38 .net
print (xs[0])
for x in (xs[1..n])
print (", " + x)
では間違い？
174:デフォルトの名無しさん
14/02/02 01:00:24.64 .net
例えばファイルへの出力に変更した時に、
複数箇所のprintを直して回らないといけない
175:デフォルトの名無しさん
14/02/02 01:07:52.48 .net
バカ？
176:デフォルトの名無しさん
14/02/02 01:15:24.41 .net
>>173
もし言語がRubyであるならば、以下の問題がある
(1) 最後のendが抜けている（これは、おそらくtypoだと思う）
(2) メソッド print は実行のたびに改行するから、期待する結果とは一致しない
(3) (2)の対策として print の代わりに printf を使ったとしても、
もし xs が空であると xs[0] の値は nil になるから、
メソッド printf の実行が引数エラーになる
（メソッド仕様上、printf の第一引数は文字列であるべき）
177:デフォルトの名無しさん
14/02/02 01:21:27.65 .net
ぷーん
178:デフォルトの名無しさん
14/02/02 01:34:06.21 .net
>>176
ネタにしてはつまらんし、素なら悲しい。
179:デフォルトの名無しさん
14/02/02 08:15:43.49 .net
for(i=0;i<n;i++) printf((i==0)?"%d":",%d",a[i]);
または，
for(i=0;i<n;i++) printf("%s%d",(i==0)?"":",",a[i]);
int a[]; としてるけど．
180:デフォルトの名無しさん
14/02/02 08:40:42.33 .net
出力するぎりぎりまで判断を遅延するのが賢いので、
文字列に修飾子としてコンマの追加の条件文を書けるような言語なら綺麗に書ける筈
三項演算子はそれに一番近い
181:151
14/02/02 21:14:08.47 .net
for (int ic = 0; ic < n; ++ic) {if (ic > 0) std::cout << ','; std::cout << a[ic];} // 宗旨替え
182:デフォルトの名無しさん
14/02/03 00:06:18.13 .net
前にコンマが付いてると見るか後にコンマが付いてると見るかは、
完全に相対的なので、どっちでも等価
セパレータだと思えば前だし、エンドマークだと思えば後
文末のセミコロンが本当は行の区切りだと判ってる人には、
後にコンマが付くのが基本で、例外的に外しているという考えに近い筈
183:デフォルトの名無しさん
14/02/03 00:40:01.64 .net
エンドマークだぁ？？
例外的に外すという考えだぁ？？
カンマは区切りっしょ。
CSV形式という文化はずーっと前からあるように。
Comma Separated Valuesだぞ？
184:デフォルトの名無しさん
14/02/03 00:55:38.64 .net
イタリヤコンマ
185:デフォルトの名無しさん
14/02/03 19:57:58.39 .net
pascalで最後の行だけはセミコロン付けてはならんというルールに律儀に従っていればいい
186:デフォルトの名無しさん
14/02/03 20:21:35.73 .net
ターミネータとセパレータの違いだ
187:デフォルトの名無しさん
14/02/03 21:22:48.71 .net
コンマタレブー
188:デフォルトの名無しさん
14/02/07 11:44:16.71 .net
Cは最後のやつにもセパレータ付ける文化。
189:デフォルトの名無しさん
14/02/07 12:49:17.86 .net
じゃなくて、最後に(も)付くのがターミネータで、
C言語のコンマのように、最後には付かないのがセパレータ。
ついでに言うと、C言語においてセミコロンは、式文やdo-while文みたいな、
「一部の文の」ターミネータ。あと for の頭部でセパレータとしても使われてる。
190:デフォルトの名無しさん
14/02/07 23:08:20.67 .net
単に空文の存在を許容してるだけ
191:デフォルトの名無しさん
14/02/08 10:34:10.24 .net
違う。
C言語において「空文」は、「空文字列にセミコロンが付いたもの」だよ。
192:デフォルトの名無しさん
14/02/10 00:14:12.54 .net
違う。
C言語において「空文」は、「セミコロンだけの文」だよ。
193:デフォルトの名無しさん
14/02/10 17:16:31.68 .net
死ねゴミ共がw
ばーかw
194:デフォルトの名無しさん
14/02/10 17:30:49.07 .net
違う。
どうでもいい。
195:デフォルトの名無しさん
14/02/11 08:40:29.35 .net
>>149
最後の","を'\0'で潰すのがはやい
196:デフォルトの名無しさん
14/02/11 09:17:01.18 .net
そんなことできる言語もめっきり無くなったな
197:デフォルトの名無しさん
14/02/11 16:18:25.25 .net
C言語だって文字列定数とかを指してたらやっちゃダメだし
198:デフォルトの名無しさん
14/02/11 16:31:18.09 .net
どう考えてもバグの宝庫な仕様だよな
199:デフォルトの名無しさん
14/02/11 19:16:39.02 .net
文字列がイミュータブルなこととミュータブルなことのどっちが？
それとも \0 ターミネーション？
200:デフォルトの名無しさん
14/02/13 11:20:17.62 .net
文字列は文字数と文字データの構造体だったんだけどな
201:デフォルトの名無しさん
14/02/13 23:24:36.15 .net
lenで1バイト持っても末尾の00に1バイト持っても同じだしな
202:デフォルトの名無しさん
14/02/13 23:33:36.34 .net
最初にサイズが分かるか、辿っていかないとサイズが分からないかの違いは有る。
前者はBSTR型とかね。
203:デフォルトの名無しさん
14/02/13 23:49:03.85 .net
データチャンクだと、サイズ+データの繰り返しだな
204:デフォルトの名無しさん
14/02/14 00:32:59.75 .net
>>201
256以上の長さの文字列どうするんだよ？
205:デフォルトの名無しさん
14/02/14 08:03:36.41 .net
そんなもん、長さに4バイト取っても必ず有限だろ
206:デフォルトの名無しさん
14/02/14 11:03:48.78 .net
そう言えば、255バイト長のパケットを送れない通信プロトコルがあったな。尤もあれは長くても508バイト長までだけど。
可変長文字列を管理するデータ構造を考えるだけでも楽しそうだね。
207:デフォルトの名無しさん
14/02/14 19:07:04.66 .net
>>204
0-127 のときは そのままの値
128-255 のときは (その値 - 127) x 128 + その次のバイトの値
ただしその次のバイトの値が 0-127 のときはその次のバイトの値をそのまま使うが
その次のバイトの値が 128-255 のときはさらに (上の値 - 127) x 128 + その次の次の値とする
とか
208:デフォルトの名無しさん
14/02/14 23:05:25.36 .net
7bitのリトルエンディアンで格納して、最終バイトの8bit目を立てる
209:デフォルトの名無しさん
14/02/17 01:31:20.81 .net
BigInt
210:デフォルトの名無しさん
14/03/05 11:39:12.46 .net
文字列の中のパターンの置き換えをおしえてください。
たとえばxを任意の文字としてabxをbxに置き換えbxをxにおきかえるとしたら
abcをcに置き換えたいです。
この時、この置き換え操作は無限に続かないことを前提としています。
この例では一つのパターンでしたが、プログラムの入力としてパターンと
置き換える文字列、出力として置き換え後の文字列であるものの
作成方法が分かりたいです。
211:デフォルトの名無しさん
14/03/05 12:09:18.80 .net
正規表現ライブラリのソースでも読んでみたら
212:デフォルトの名無しさん
14/03/09 19:39:16.05 .net
再帰処理を使った順列のプログラム（JavaScript）について質問があるのですが、
ここで教えてくださる人はいますか？
213:デフォルトの名無しさん
14/03/09 20:01:44.88 .net
>>212
とりあえず質問内容を書いてみたら？
答えるかどうかは気分次第だけど。
214:デフォルトの名無しさん
14/03/09 20:20:18.06 .net
アルゴリズムとデータ構造の勉強に使える本で木構造やリストの実装、
バックトラックとか動的計画法まで載ってる本で読みやすくてコードが書いてるやつ
何がいい？
はじめてのアルゴリズム 上原
とかエイホさんのとかっていいの？
215:デフォルトの名無しさん
14/03/09 20:44:41.37 .net
アルゴリズムイントロダクションの総合版買っとけばいいよ
216:デフォルトの名無しさん
14/03/09 23:15:50.81 .net
あの巨大な枕か
217:デフォルトの名無しさん
14/03/09 23:31:43.52 .net
>>214
プログラミング・コンテスト・チャレンジブック、第2版、2012
グラフ理論など、ほとんど全てのアルゴリズムを網羅
問題数も多く、パズル感覚で楽しめる
AIやシミュレーションゲームの参考になる
TopCoder
ｽﾚﾘﾝｸ(tech板)l50
218:デフォルトの名無しさん
14/03/15 20:50:18.83 3c5h2INR.net
アルゴリズムを初歩から勉強をしたくて
プログラミング・コンテスト・チャレンジブックを読もうと思ってるんですけど
その前にやっておくべき本とかってありますか？
アルゴリズムイントロダクション，データ構造とアルゴリズム（杉原）が候補にあります．
ちなみに，現在大学生で，CとPythonはある程度書けます．
219:デフォルトの名無しさん
14/03/15 21:05:18.35 LOPS9SpP.net
>>218
プログラミング・コンテスト・チャレンジブックはひと通りアルゴリズムを学んだ人が腕試しにやるような本だから、候補に上げたような本を先に読むんでいいと思う。
杉原は知らないけど、アルゴリズムイントロダクションもちょっと数学的考察とか証明の割合が多いから、難しいようなら他の本を当たった方がいいかもしれない。一生使えるから、とりあえず買っちゃうのはいいと思うけど。
あとは大学(自分のとこでも、他所でも)のアルゴリズムとデータ構造の授業で使ってる教科書を見てみるのがいいと思う。
220:デフォルトの名無しさん
14/03/15 22:02:22.42 3c5h2INR.net
>>219
ありがとうございます．
数学的考察も欲しいのでアルゴリズムイントロダクションを買おうと思うのですが
初心者でも総合版を買うことをおすすめされますか？
鈍器としても使えるらしいので総合版にしようかと思っていたのですが
あまりにも重すぎて使いにくいという声など，もしありましたら教えていただきたいです．
221:デフォルトの名無しさん
14/03/15 22:06:32.24 tN8Ad5rR.net
間違ってたらごめんだけど、
たしか総合版にしか無い箇所があるんじゃ？
222:デフォルトの名無しさん
14/03/15 23:56:04.39 LOPS9SpP.net
>>220
へえー、総合版なんてのが出たのか。今度立ち読みしてみるわ。
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
223:デフォルトの名無しさん
14/03/16 03:10:11.24 NcMQ7vHT.net
おまえら、そんなもん学んで何に使うの？
224:Donald Knuth
14/03/16 03:15:08.58 BR331utC.net
>>223
現在わたしは、Ph.D.(Doctor of Philosophy)をとらなければ
ならないようなプログラムを、みんなが書くべきと考えていません。
多くの理論がこれまで開発されてきましたが、そのほとんどは、
実際のプログラムではあまり使われないものなのです。
こうしたものは、ものごとを極限までつきつめるときぐらいしか、
役に立たない。これらの理論の値打ちは、
ユーザーに全体の構造を見渡せる視野を提供することにあるのです。
理論をたくさん知っていればいるほど、ユーザーは、
プログラムで実際に応用するほんのわずかなことが、
より楽に理解できるようになるというだけのことなわけです。
ユーザーは、自分が扱える範囲を広げるために、理論を必要とします。
たとえばリストでいえば、ユーザーがリストに関して、
より複雑な理論を知っていれば、プログラムにこうした理論を
使うことがなくても、プログラムの中の単純なリストの使い方は、
(理論を知らない人が書いたものと比べれば)
はるかに自然なものとなるのです。
225:デフォルトの名無しさん
14/03/16 03:27:49.15 NcMQ7vHT.net
その全文が書かれたのって、おまえが生まれる前じゃないの？
部屋の飾りにはいいかもしれないけれど
226:デフォルトの名無しさん
14/03/16 10:42:44.74 36W3tLYE.net
アルゴリズムは盆栽
227:デフォルトの名無しさん
14/03/16 10:50:16.89 JXH3psgq.net
このツリーの曲がり方はいいね
228:デフォルトの名無しさん
14/03/16 11:32:59.02 36W3tLYE.net
ごめん、この枝間違って切っちゃった。
229:デフォルトの名無しさん
14/03/16 12:49:26.13 AOFYs8Jm.net
平衡木って盆栽的には美しくなさそう
230:デフォルトの名無しさん
14/03/16 13:35:29.66 tRI7CXOm.net
>>221 >>222
丁寧にありがとうございます！
追加されたのは比較的高学年で学ぶ範囲なのですかね．
大学院で学ぶ内容も網羅してくれているとありがたいので，総合版にしようと思います．
231:デフォルトの名無しさん
14/03/16 16:22:41.16 1gXwUEhj.net
アルゴリズムって一回は言ってみたいかっこいい言葉だよね
232:デフォルトの名無しさん
14/03/16 16:23:22.03 rHQmp5Mm.net
アルゴリズムたいそう
233:デフォルトの名無しさん
14/03/16 18:58:01.80 NcMQ7vHT.net
アルゴリズムに期待するのって、高卒とか文系SE?
情報科卒業して、CSSやPHP弄ってる層に謝れよ。
234:デフォルトの名無しさん
14/03/16 19:00:27.81 rHQmp5Mm.net
>>233
お前バカそうだな。
クイックソートやGoogleの検索エンジンの仕様も
アルゴリズムって呼ばれているわけだが、
お前が馬鹿にしているのが何かすらわかっていないだろう？
235:デフォルトの名無しさん
14/03/16 19:06:08.08 9d63KDz+.net
>>233
アルゴリズムや数学をきちんと勉強しないから、人が考えたアルゴリズムをコードに起こす仕事になっちゃうんじゃ..
236:デフォルトの名無しさん
14/03/16 19:08:21.05 wQykVVMe.net
アルゴリズムおもろいやん
237:デフォルトの名無しさん
14/03/16 19:15:10.66 NcMQ7vHT.net
>>235
ちょっと分厚い本をペラペラ捲ったら、アルゴリズム記述されてんのに、
そんなもの後で必要になってから調べて十分じゃないの?
頻出しそうなものなんて、木とネットワークフロー、DPぐらいしか思いつかないし、
BM法なんて、生涯にわたって使う機会が一度もない気がするわ
それよかPrologで出される制約問題でも解いた方が有意義じゃねぇの
238:デフォルトの名無しさん
14/03/16 19:16:09.34 rHQmp5Mm.net
たぶん、アルゴリズムを
他人が考えたものを使うものとしか
考えてないんだろうな。
239:デフォルトの名無しさん
14/03/16 19:21:48.31 NcMQ7vHT.net
>>238
若くて情熱が続くうちに、ページランクアルゴリズムでも再発明したらいいと思うよ
240:デフォルトの名無しさん
14/03/16 19:25:25.65 rHQmp5Mm.net
>>239
アルゴリズムに期待したらいけなかったんじゃなかったのか？ｗ
ページランクアルゴリズムを発明したGoogleは凄いことになりましたよね。
241:デフォルトの名無しさん
14/03/16 19:31:14.68 NcMQ7vHT.net
皮肉を理解できないアスペと話するほど心は広くないんだ
242:デフォルトの名無しさん
14/03/16 19:36:16.50 rHQmp5Mm.net
じゃあ話をしなければいいじゃないかｗ
もうこれ以上レスしなければいい。
で、アルゴリズムをなにかわかってないから
そんなこと言ったんだよねｗ
243:デフォルトの名無しさん
14/03/16 19:36:24.56 9d63KDz+.net
>>237
そりゃ、CSSやPHP弄ってるだけの場合はそんなもんだろ。お前の仕事に必要なければ勉強しなきゃいいさ。
ただ、人によって勉強する動機は異なるし、どんなアルゴリズムやデータ構造があるかを大雑把に知っておかないと、必要になった時に何をどう調べたらいいかもわからんだろ。
>>237 はもっと数学を勉強して、物事を合理的に考える力を養った方がいいな。
244:デフォルトの名無しさん
14/03/16 19:52:29.07 NcMQ7vHT.net
>大雑把にしっておかないと
だから、ペラペラ捲ってからで十分なんだって。
具体的な目標もなしに、アルゴリズムなんて勉強した所で身に付かないよ
そして、おまえらには目標がないので、ぺちぱーになる
245:デフォルトの名無しさん
14/03/16 19:55:39.38 LEh1TotO.net
>>244の意見のほうが信用できるな。
リファクタリングにしろ、デザパタにしろ、
OOPとはなんぞやの思想にしろ、
なんかしらのアルゴリズムにしろ、
必要になるまでまずその価値なんてわかんねえんだ。
246:デフォルトの名無しさん
14/03/16 20:02:22.78 rHQmp5Mm.net
>>244
お前何言ってんだ？
アルゴリズムそのものの話だろ。
お前が言っているのは特定の場合の話であって
アルゴリズムそのもの話ではない。
247:デフォルトの名無しさん
14/03/16 20:14:21.59 NcMQ7vHT.net
>>245
リファクタリング、デザパタの方が優先度上。
アルゴリズムの勉強なんてウンコしながらで良い
248:デフォルトの名無しさん
14/03/16 20:22:18.88 /mgBA8rW.net
寝言は寝て言え。
249:デフォルトの名無しさん
14/03/16 20:24:16.99 NcMQ7vHT.net
>>248
皆、アルゴリズムの使い方と使う場面を知らないから講釈垂れてけよ
250:デフォルトの名無しさん
14/03/16 20:27:30.48 rHQmp5Mm.net
意訳
俺、アルゴリズムの使い方と使う場面を知らないから教えてください。
返答例
だがことわるｗ
251:デフォルトの名無しさん
14/03/16 20:30:14.53 /mgBA8rW.net
死ぬまで10万件のバブルソートしてろカス、ってのもアリかなw
252:デフォルトの名無しさん
14/03/16 20:33:35.53 NcMQ7vHT.net
ほとんどの場合、組込関数が問題領域に大して最適化されたもの提供してくれるよね？
253:デフォルトの名無しさん
14/03/16 20:36:19.25 /mgBA8rW.net
それを適用しようとしている問題に対して最適だと判断できないバカが何か言ってるw
254:デフォルトの名無しさん
14/03/16 20:45:10.96 NcMQ7vHT.net
大体、大学生が講義で学ぶソートや文字列操作って、普通は勉強しても使わないから必要になるまで放置するよ
本当に正しいか確認するために書籍を引っ張り出すけど、
実際に調べてみるとデータベースや言語の組込み関数が問題に対して最適化されたもの提供している
少なくともソートや文字列周りのアルゴリズムは頭に入れておくだけ時間のムダ
詳細に頭に留めておくべきデータ構造もB+木ぐらいしか思い浮かばない
255:デフォルトの名無しさん
14/03/16 20:49:59.68 rHQmp5Mm.net
話がすり替わってるな。
頭にいれるのが無駄というだけで、
アルゴリズムそのものが悪いわけじゃないだろ。
クイックソートとか、多くの言語のソート機能に
使われてるアルゴリズムだし、
ソフトウェア工学の基礎だぞ。
アルゴリズムの勉強から学べることも多い。
基礎をないがしろにするもんじゃない。
優れたアルゴリズムは、今でも優れているし、
そういうのを知って、そして自分で
考えるのがプログラマってもんだろ。
256:デフォルトの名無しさん
14/03/16 20:50:55.37 NcMQ7vHT.net
NGID:rHQmp5Mm
257:デフォルトの名無しさん
14/03/16 20:54:38.91 rHQmp5Mm.net
NGしたってことはもうレス（反論？）してこないってことか。
それは嬉しいね。
この俺のレスも見えてないはずだよね。
レス番飛んでるから書き込みしているのはわかっても
内容はわからない。レスしようがないよねｗ
さて、この馬鹿どうしようか。
アルゴリズムの重要さを理解してないなんて痛すぎるね。
必要になったら意味もわからずコピペしてすませそうだね。
258:デフォルトの名無しさん
14/03/16 20:56:16.49 NcMQ7vHT.net
さっきから、あぼーんが酷いわ
童貞がセックスでも語ってるのかな
259:デフォルトの名無しさん
14/03/16 20:56:57.35 /mgBA8rW.net
>>258 死ねや屑
260:デフォルトの名無しさん
14/03/16 20:58:04.50 rHQmp5Mm.net
さっそく、レス番飛んでるのを見つけてレスしてきたかｗ
NGしたんだからID:NcMQ7vHTには内容は見えてないはず。
ID:NcMQ7vHTってホント馬鹿だよねｗ
自分から見えなくするとか。
頭悪すぎるｗ
261:デフォルトの名無しさん
14/03/16 21:00:43.22 NcMQ7vHT.net
>>259
君ら本当にアルゴリズム一通り勉強したの？
262:デフォルトの名無しさん
14/03/16 21:03:32.02 /mgBA8rW.net
アルゴリズムについて一切勉強せず、
「組込関数が問題領域に大して最適化されたもの提供してくれる」って信じて自爆すればいいんだよ君は。
だからもうこのスレに居る必要は無いから、消えようね。
263:デフォルトの名無しさん
14/03/16 21:04:06.75 rHQmp5Mm.net
>>261
そりゃメジャーなのはするでしょｗ
やってなきゃモグリだよ。
264:デフォルトの名無しさん
14/03/16 21:10:11.16 NcMQ7vHT.net
>>262
反例はよ?
265:デフォルトの名無しさん
14/03/16 21:10:52.74 x79H7Bla.net
＞高卒とか文系SE?
これでおこっちゃったんだろうなｗ
266:デフォルトの名無しさん
14/03/16 21:11:05.83 NcMQ7vHT.net
>>262
必要になってから本を開くで十分だから
267:デフォルトの名無しさん
14/03/16 21:12:49.53 rHQmp5Mm.net
>>266
だから必要になる時点で、
アルゴリズムに期待してるってことだよね。
自分で矛盾しているのわかってないんだろうね。
反論あるかい？
268:デフォルトの名無しさん
14/03/16 21:15:50.63 NcMQ7vHT.net
まぁ、ここのバカ共は、シコシコとsortやBM法を実装する経験を積んで、
その費用対効果の悪さを実感してもらいたいね
269:デフォルトの名無しさん
14/03/16 21:17:13.06 rHQmp5Mm.net
おやおや、反論はどうしたんだい？
しないのかい？ｗ
270:デフォルトの名無しさん
14/03/16 21:18:38.78 PaEO6HwD.net
○○ソートを実装して嬉しげな子は、写経に価値を見出す子。
○○ソート実装しますた！つっても結局はそれは発明するわけじゃないんだから、
誰かが書いたソースや、手順の解説をみて、本質的には書き写してるだけ。
それで満足できるんだからほほえましい。
271:デフォルトの名無しさん
14/03/16 21:21:39.00 rHQmp5Mm.net
>>270
勉強っていうのはだいたいそんなもんだよ。
数学の勉強なんて、殆どが誰かが発明したものでしょ？
だからって数学に意味が無いことにはならないし、
もちろん勉強することに意味が無いことにもならない。
それが基礎ってもん。基礎が出来てこそ、その先がある。
ID:NcMQ7vHTはそれをわかってないんだよ。
だからみんなに馬鹿にされてる。
272:デフォルトの名無しさん
14/03/16 21:25:15.25 KN/i/crH.net
NcMQ7vHTの言っていることは一理あるよ
どういったものがあるか程度に知識として持つってのが前提の話だろ？
必要に迫られたら、そのインデックスを頼りに勉強すればいい
知識は使わないと直ぐに忘れるから、あれこれ頭に詰め込んでもあんまり意味ない
外部記憶装置に連想配列としてデータを置いてハッシュ値で情報を取り出す方が効率が良い
ひと通り勉強するって捉え方の相違って感じ
273:デフォルトの名無しさん
14/03/16 21:27:42.49 9d63KDz+.net
>>272
それ、俺が言ってることじゃん。
NcMQ7vHT はそれすら無駄って否定してたけど。
274:デフォルトの名無しさん
14/03/16 21:27:46.19 rHQmp5Mm.net
>>272
いや、そういうことじゃなくて、
NcMQ7vHTはアルゴリズムそのものに
価値がないと言ってる。
下記参照
> 223 名前：デフォルトの名無しさん[sage] 投稿日：2014/03/16(日) 03:10:11.24 ID:NcMQ7vHT
> おまえら、そんなもん学んで何に使うの？
> 233 名前：デフォルトの名無しさん[sage] 投稿日：2014/03/16(日) 18:58:01.80 ID:NcMQ7vHT
> アルゴリズムに期待するのって、高卒とか文系SE?
> 情報科卒業して、CSSやPHP弄ってる層に謝れよ。
275:デフォルトの名無しさん
14/03/16 21:27:55.33 NcMQ7vHT.net
>>270
5分以内に挿入ソートを書かないと、お前の娘がどうなっても知らないぞ
なんて、偉い人に脅されたらどうするんだ?娘の純潔が君の手に掛かっているんだぞ
コーディングが不要って考え自体は、医師免許もってる人にお腹を切開させるぐらい怪しい考え
276:デフォルトの名無しさん
14/03/16 21:32:02.43 rHQmp5Mm.net
反論できない奴に対してのワンサイドゲームって楽しいわｗ
どうせ見てるんだろうけどさｗ
277:デフォルトの名無しさん
14/03/16 21:32:14.46 KN/i/crH.net
>>273
うん、君の>>235のレスに対して>>237の返答があるけど
言っていることは同じだよ
どういったものがあるか知らなきゃ、調べようがないもの
278:デフォルトの名無しさん
14/03/16 21:37:04.12 KN/i/crH.net
>>274
必要のないアルゴリズムを
親父のラジオを分解してまた組み直すように
分析しまくっても、満足はするけど、さほど身にならないよ
必要なければ物語のあらすじを知っておく程度でいいんだよ
NcMQ7vHTはそう言っていると捉えたけど
279:デフォルトの名無しさん
14/03/16 21:40:44.74 wQykVVMe.net
アルゴリズムを勉強する意味としては、
優れたアルゴリズムをつかうことによって、
計算量が劇的に減るってことを簡単に体感出来るやん
それだけでも楽しくね？
280:デフォルトの名無しさん
14/03/16 21:42:27.17 NcMQ7vHT.net
アルゴリズムの理解に対して、競技コーダーレベルを目指すか未満でいいか
のどちらかで、んなもん目指さなくて良いなら本開いてからかウンコしながらで十分
このスレの人たちはアルゴリズムが重要だってわりに、何がどう重要なのか、
そもそも何に使うのかの具体性すらないのにアルゴリズムが重要っていう。不思議。
281:デフォルトの名無しさん
14/03/16 21:44:03.69 rHQmp5Mm.net
具体性があれば、アルゴリズムは重要って言ってるんだよ、こいつは。
みんな気づいているよね？
282:デフォルトの名無しさん
14/03/16 21:49:30.77 NcMQ7vHT.net
童貞って使いもしない性知識や性技について、やたら詳しいよね
それも何か過度の期待をして悶々とムラムラしている。
あぼーんした箇所から我慢汁が垂れてきそうだ。
283:デフォルトの名無しさん
14/03/16 21:59:57.76 rHQmp5Mm.net
自己紹介乙ｗ
284:デフォルトの名無しさん
14/03/16 22:08:16.80 jBVIil7i.net
>>271
なんか話がねじれてるのを感じるが一点だけ。
…と思ったけどやっぱいいわｗ やめとく。
>>275
わろたｗ
285:デフォルトの名無しさん
14/03/16 22:09:25.28 8TdIOMC6.net
アルゴリズムに興味ある人はトップコーダへ ステマ
286:デフォルトの名無しさん
14/03/16 22:22:14.08 NcMQ7vHT.net
php.iniを笑うものはphp.iniに泣く
287:デフォルトの名無しさん
14/03/17 02:29:24.68 4lFteqPu.net
漏れは今、6マスタイプの大戦略のAIを考えている
首都からすべてのセルへの、最小移動コストと、
その経路をたどるパス
すべてのセルへ、ランダムな移動コストを与えて、
シミュレートしようと思っている
ダイクストラで、優先度キューを使うか？
隣接行列か隣接リストか？
こういう知識も、
プログラミング・コンテスト・チャレンジブックから得た
3人の大学院生が書いた本だが、冒頭から度肝を抜かれる
千枚ある紙の中から、4枚引いて、
それらの合計が、mとなるかどうかを確かめろ、
という問題があるが、
a+b+c+d = mで、一般的にO(n^4)だが、
a+b = m-c-dとして、a+bでソートすると、
O(n^2 log n)となる。これぞ、Art!
288:デフォルトの名無しさん
14/03/17 05:24:43.74 P8Lohybr.net
蟻本いいよね。大学生のうちに熟読したかったわ
289:デフォルトの名無しさん
14/03/17 07:07:20.60 s3V0Rhfq.net
スレが進んでると思ったら、狂人が二人居ていちゃいちゃしてたのか
290:デフォルトの名無しさん
14/03/17 10:20:45.42 QW4CmNA1.net
どう見ても一人
291:デフォルトの名無しさん
14/03/18 00:46:44.67 tPzh9EEu.net
アルゴリズムとデータ構造ならやっぱこれが今でもベストだと思う
URLﾘﾝｸ(www.amazon.co.jp)
日本人だから意味不明の翻訳調の文章に悩まされることもない。
説明が丁寧。ひっかかりやすいミスもあれこれ解説しているのが親切。
もっと評価されてもいいと思う。
292:デフォルトの名無しさん
14/03/18 00:55:01.62 6BNvI/8X.net
ベストと言い切る自信は無いが、確実に名著だね。
293:デフォルトの名無しさん
14/03/18 02:31:41.71 D2G7mMpQ.net
0-9の数字をランダムに並べ替える、
トランプのシャッフルなど、
重複しない乱数列を作るのは、
どんなアルゴリズムがありますか？
Webにあって良さそうなのは、
最初に配列に、0-9を入れておく
1. 0-9から1つの乱数aを得て、配列[a]と[9]の要素を入れ替える
2. 0-8から1つの乱数bを得て、配列[b]と[8]の要素を入れ替える
以下同じ
294:デフォルトの名無しさん
14/03/18 05:08:07.94 8D/uPICD.net
>>293
それでいいんじゃないの？
O(n)で乱数配列作れるから一番速そうだし
c++STLのrandom_shuffleだっけ
これもそれ使ってたと思う
295:335
14/03/22 22:06:03.42 h08U7EZc.net
アルゴリズムの検証に使えそうなある程度大きなデータのサンプルが置いてあるサイトってないかな？
今は特に重み付き有向グラフのデータが欲しいんだけど。
なんなら、有料でもいい。
296:デフォルトの名無しさん
14/03/22 22:16:38.65 +XA3shYN.net
Wikipediaの全データ落として、リンクをエッジ、文の長さを重みにでもすれば
297:デフォルトの名無しさん
14/03/22 22:46:49.83 ZVkXLvMB.net
>>295
URLﾘﾝｸ(algs4.cs.princeton.edu)
の largeEWG.txt とかはどう?
298:デフォルトの名無しさん
14/03/22 23:29:33.56 p0VQZyPj.net
>>295
URLﾘﾝｸ(elib.zib.de)
299:デフォルトの名無しさん
14/03/23 09:35:14.62 hof0CNNK.net
>>296
アドバイスはありがたいが、申し訳ないが今はちょっと非現実的かも。
面白そうではあるから、暇ができたらトライしてみるよ。
>>297 >>298
使えそうだ、助かった。
ありがと。
300:デフォルトの名無しさん
14/03/23 18:56:42.11 +Lw9q3Jk.net
一括データをまとめて落とせるんだよ。URLﾘﾝｸ(ja.wikipedia.org)
301:デフォルトの名無しさん
14/03/23 19:14:01.71 0P0DcJxO.net
>>300
これは凄い。知らんかった。
302:デフォルトの名無しさん
14/03/26 03:06:58.26 r7VC3H2x.net
２Ｄ上の多角形を検出するアルゴリズムで詰まりました。助けてください。
各ラインを 56,80-120,100 という２頂点のデータで複数持っています。
とある２Ｄの座標が多角形を構成しているラインの中か外かをチェックする必要があります。
中か外かをチェックする処理は作成したのですが、そもそも多角形を構成しているのかどうなのかという処理で、
良いアルゴリズムが浮かびません。
多角形の頂点数は３点以上です。
何か良いアルゴリズムは無いでしょうか？
303:302
14/03/26 03:24:55.09 r7VC3H2x.net
追加です。
各ラインの交差はありません。
304:デフォルトの名無しさん
14/03/26 04:23:33.08 2pJmwYuc.net
共通する頂点を探して辿るとかじゃだめなの？
305:302
14/03/26 05:36:23.23 r7VC3H2x.net
>>304
ありがとうございます。
頂点ＡＢＣＤＥＦＧと頂点ＢＣＤＥＦＧＡは同じなのですが、チェックがめんどくさくて、、、
閉じているかチェックしたいだけなので、力技ではなく何かテクニックがあったら教えていただきたいです。
306:デフォルトの名無しさん
14/03/26 06:24:33.03 2pJmwYuc.net
どんどん条件後出ししていきそうな質問者
307:302
14/03/26 06:56:33.51 r7VC3H2x.net
条件出さないんで、助けてください＞＜
あえて出すとすれば、同じ頂点を共有した別の多角形が存在するという条件でしょうか。
条件出しちゃいました。。。
308:デフォルトの名無しさん
14/03/26 07:05:35.73 R7T8IoJH.net
頂点データを持っているオブジェクトが必ず多角形になるなら
そういうデータ構造にしたらいいんじゃないの？
三角形なら頂点a、b、cのデータを持って、一筆書きみたいにa-b、b-c、c-aのライン判定する
ラインデータじゃなく単純な頂点データとして持てばデータ量も減るし
多角形にならない場合があるならフラグでも設けて
最後のc-aが閉じていないってすればいいんじゃないの
どのラインも独立しているのが必要ならそれぞれオブジェクト生成したらいいんじゃない？
309:302
14/03/26 09:04:50.88 r7VC3H2x.net
>>308
ありがとうございます。
難しそうですね。。。
実装時間に制約があるので、１頂点から２線以上出せないという仕様を一つ追加して乗り切りたいと思います。
310:デフォルトの名無しさん
14/03/26 10:28:25.10 R7T8IoJH.net
>>309
多角形は結局のところ多角形の集合なのだから
最低単位の多角形をグループ化するクラスでも作ったらいいんじゃない？
例えば、正六角形は正三角形が6つ集まっているよね
最小単位の正三角形のオブジェクトを6つ持つ正六角形クラスがあればいいよね
当たり判定はそれぞれの正三角形で行なえばいいよね
それを一般化してしまえば、1頂点から2線以上出る多角形も作ることが可能だよね
それが3Dとかで使われるポリゴンだと解釈しているけど
311:デフォルトの名無しさん
14/03/26 13:13:57.81 oWOUaPIh.net
多角形はワイヤーフレーム型？
多角形が単一色、または背景が単一色で多角形部分が色付きなら楽だけど、たぶんそれじゃあ駄目なんだろな
ワイヤーフレームなら、指定座標から画面外枠に向かって上下左右に1ドットづつ色検知して、上下どちらも、または左右どちらも画面外に出る前にに多角形枠色に引っかかったら内側判定…とかは？
312:デフォルトの名無しさん
14/03/26 13:16:09.06 oWOUaPIh.net
あ、内側判定は終わってるんだな
ごめん、忘れてorz
313:デフォルトの名無しさん
14/04/01 20:07:56.78 m1CmrLTr.net
URLﾘﾝｸ(ocw.mit.edu)
↑のMITの講義で、スキップリストと呼ばれる1989年に考えられたデータ構造の
計算量を見積もるときに以下の問題を解く必要があります。
講義では明らかみたいなことを言っていますが、そんなに明らかでしょうか？
Aを正の実数とする。
f(x_1, x_2, ..., x_n) = x_1 + x_2/x_1 + ... + x_n/x_(n-1) + A/x_n
とする。
fの値を最小にする正の実数x_1, x_2, ..., x_nを求めよ。
314: ◆QZaw55cn4c
14/04/01 21:02:41.83 Xl1FJm59.net
>>313
各項をかけるとx(n)がいかなる値であろうとも常にA
積が一定のとき、各項がすべて等しければ最小
とかいう問題ですか？英語よめないからよくわかりません
315:デフォルトの名無しさん
14/04/01 21:31:37.80 wNI+pTPk.net
So, I want to minimize L_1 plus n over L_1. And I get to choose L_1. Now, I could
differentiate this, set it to zero, and go crazy. Or, I could realize that, I mean, that's
not hard. But, that's a little bit too fancy for me. So, I could say, well, this is clearly
best when L_1 is small. And this is clearly best when L_1 is large. So, there's a
trade-off there. And, the trade-off will be roughly minimized up to constant factors
when these two terms are equal. That's when I have pretty good balance between
the two ends of the trade-off. So, this is up to constant factors. I can let L_1 equal n
over L_1, OK, because at most I'm losing a factor of two there when they happen to
be equal.
316:デフォルトの名無しさん
14/04/02 00:00:27.81 wKQIA80W.net
>>313
どこが分からないの? >>315 のところ？
317:デフォルトの名無しさん
14/04/02 06:26:11.63 ueE6QFcL.net
相加相乗平均の定理
318:デフォルトの名無しさん
14/04/06 00:40:03.37 tyVsXbcn.net
アルゴリズムの勉強は本当に疲れる
センスのある人はアルゴリズムがスラスラ理解できるらしいが、俺は頭が悪いのでウンウン唸りながらじゃないと理解できん
319:デフォルトの名無しさん
14/04/06 01:14:46.49 v5F7vKVc.net
それでいいと思う‥‥
320:デフォルトの名無しさん
14/04/06 01:47:58.09 rc99+CA1.net
俺ハノイの塔とか未だにわからんわ
追っていると頭が混乱しちゃう
321:デフォルトの名無しさん
14/04/06 08:05:50.25 B8PUb7p+.net
センスというものなのかどうかはわからんが、
機械の「機械のように正確な」動作を追うことができるかどうかは、
デバッグの効率には影響すると思う。この仕事に対する向き不向きとして。
322:デフォルトの名無しさん
14/04/06 08:33:13.34 uLJ3NzvJ.net
再帰をわかってる人は、大半のアルゴリズムに強い気がする
323:デフォルトの名無しさん
14/04/06 10:39:51.62 tUu4o0lA.net
再帰は確実に終了する根拠がないと使いにくいんだよな。
324:デフォルトの名無しさん
14/04/06 12:54:38.12 rc99+CA1.net
ループは確実に終了する根拠がないと使いにくいんだよな。
チューリング完全は確実に終了する根拠が無いと主張できないよな。
325:デフォルトの名無しさん
14/04/06 14:01:26.03 mKLMCJ7D.net
>>323
再帰を使う上でその根拠を決めるのは自分でしょ
326:デフォルトの名無しさん
14/04/06 17:47:49.59 v5F7vKVc.net
>>323
再帰の頭に終了条件を書くでしょ、そのときに否が応でも自分で決めざるを得ない
327:デフォルトの名無しさん
14/04/06 17:55:05.95 /BRp7uTK.net
再帰の頭に書くのは終了条件じゃないよ
328:デフォルトの名無しさん
14/04/06 18:32:11.06 v5F7vKVc.net
>>327
ありえない、お前は再帰をもういちど勉強したほうがいい
329:デフォルトの名無しさん
14/04/06 18:42:52.70 N5LDc9gS.net
多額な借金で人生つんでるヤシたちw
URLﾘﾝｸ(manta.blog.jp)<)
URLﾘﾝｸ(sisutore.blog.jp)
330:デフォルトの名無しさん
14/04/06 18:48:53.18 1V1mpQ2/.net
>>327
じゃあ、今日からは、再帰を書くときは真っ先に再帰を終了させる条件を定義するようにしましょうよ。
331:デフォルトの名無しさん
14/04/07 01:56:22.46 d0TT8Xyg.net
再帰は、内部的にはどーなってるんだ？
アーキテクチャの本を読んでも理解できなかったわ
332:デフォルトの名無しさん
14/04/07 03:42:51.76 X0/QJ0Bz.net
>>331
マシン語勉強すれば？
333:デフォルトの名無しさん
14/04/07 05:20:02.79 EBZlvC1X.net
再帰とマシン語はあんまり関連性ないだろ。
334:デフォルトの名無しさん
14/04/07 05:21:46.96 EBZlvC1X.net
つーか終了条件が成立するまで自分自身を呼び出すだけ。
たったこれだけ。単にループを再帰で置き換えるだけなら
簡単。データ量が不定だったりする場合は一定の量だけを
切り出して、そのブロックに対して再帰にすればいい。
335:デフォルトの名無しさん
14/04/07 09:20:18.42 X0/QJ0Bz.net
内部的にどうなってるか知りたいってことは、引数やローカル変数が上書きされないかとか、どうやって元の場所に戻るんだろうとかが疑問だってことでしょ。
自分は、関数呼び出しがマシン語では引数や戻りアドレスをスタックに積んで関数の先頭アドレスにジャンプするコードになるのを知ってたから理解できたけど、そんなのは老害だって言うなら黙るよ。
336:デフォルトの名無しさん
14/04/07 09:25:29.71 2J/E/BiW.net
実装の話だろ、あってんじゃん
337:デフォルトの名無しさん
14/04/07 09:29:04.52 5wZ1j6dN.net
この関数が老害ってどういうことなんでしょう
338:デフォルトの名無しさん
14/04/07 10:06:25.41 Azn2Ag2H.net
mkdir himitsu
cd himitsu
ln -s . himitsu
339:デフォルトの名無しさん
14/04/07 10:40:46.86 2J/E/BiW.net
chown oh:oh himitu
340:デフォルトの名無しさん
14/04/07 19:44:06.53 07lAy1km.net
・ポインタ
・再帰
・リンクリスト
辺りがダメな人は本当にわからないらしい。
数学科でもダメな奴がいると聞いた。
341:デフォルトの名無しさん
14/04/07 19:54:04.79 WXfYbNCh.net
どう突っ込めばいいんだ？
342:デフォルトの名無しさん
14/04/07 19:54:31.72 jH/0whnp.net
ほんとだよなｗ
343:デフォルトの名無しさん
14/04/07 20:03:59.61 Yv3nxM4P.net
ねじ込むように突っ込む
344:デフォルトの名無しさん
14/04/07 21:57:36.22 cPHU7Y9F.net
そんな奴等はメモリモデルとかアドレス空間から教えないと
345:デフォルトの名無しさん
14/04/07 22:44:41.34 aZ3ao3+q.net
還元的な方法以外でも理解可能です。
346:デフォルトの名無しさん
14/04/07 23:03:10.48 R8X8CMOs.net
>>344
チューリングの計算可能の話にまで遡るのか・・・
大学レベルだけど、講義でもないのに教えるの面倒くさいなあ
347:デフォルトの名無しさん
14/04/07 23:13:47.29 9xD+wUOX.net
なんでやねん
348:デフォルトの名無しさん
14/04/08 17:07:35.17 h+V2EGQg.net
数学科って、cでプログラム書くようなことあるのか?
6年ぐらい入門して、最終的に触る機会なんてなかったぞ
349:デフォルトの名無しさん
14/04/08 17:21:28.77 mk0uQXXd.net
まず日本語を勉強してだな
350:デフォルトの名無しさん
14/04/08 17:31:13.57 h+V2EGQg.net
>>349
サクラ鯖に、なでしこでCGIでしょうか?
351:デフォルトの名無しさん
14/04/08 17:44:56.41 q/1QB78S.net
↑のレスは天才チンパンジー「アイちゃん」が
言語訓練のために書き込んだものです。
352:デフォルトの名無しさん
14/04/24 11:33:00.99 V7HoJaA9.net
初級アルゴリズムならそうかもな
353:デフォルトの名無しさん
14/04/24 11:55:31.38 1XlNsioB.net
中級・上級アルゴリストにはどんなことができるの？
354:デフォルトの名無しさん
14/04/24 12:31:07.16 mnsZs1hI.net
実際に何か作ってるときに「こういうアルゴリズムがあるはずだ」と察知して
探せるようになればおｋ
355:デフォルトの名無しさん
14/04/24 14:05:02.62 E/S2XTBi.net
中級は学部・院生レベルくらいかな
既存のアルゴリズムの改良をしたり、
目的に沿ったアルゴリズムを開発したり、
その計算量やメモリ量を算出・証明したり、
実装したり、論文で発表したりする
356:デフォルトの名無しさん
14/04/24 17:22:35.13 CrNHZjbB.net
アルゴリズムはデザインがすべて
357:デフォルトの名無しさん
14/04/24 20:31:22.55 RrLorudN.net
>>352
違う。
それを勉強し始めた時に思い描いた未来の自分になれば完成だ。
目標もなくただなんとなく勉強しているのなら、完成なんて永遠にこない。
あと、「一応」なんてものも無い。
358:デフォルトの名無しさん
14/04/24 21:05:08.96 29x10p2Y.net
algorithmの問題に関する作業能率を最大まで上げたら、
らいなっくすやれいるずを作れるようなすーぱーはっかーになれますか？
359:デフォルトの名無しさん
14/04/24 21:07:30.43 29x10p2Y.net
>>352
蟻本嫁
360:デフォルトの名無しさん
14/04/24 21:50:29.46 RrLorudN.net
>>358
なれるわけがない。
ウソだと思うなら、実際に効率最大まで上げてみればいい。
361:デフォルトの名無しさん
14/04/25 01:31:40.05 J0O0+fbt.net
>>331
末尾再帰最適化、継続あたりで検索。
362:デフォルトの名無しさん
14/04/25 22:30:20.43 k5QgmFyd.net
>>355
高卒なのか?
363:デフォルトの名無しさん
14/04/26 00:12:34.02 4Xi6PaOs.net
>>153
>ただし、if 文で n 回の比較が発生するから、n があまりに大きい場合は >>152 のやり方がいいと思う。
元のお題がI/Oなんで、この程度の比較命令は全く問題にならない。
わかりやすく書くのがいい。
364:デフォルトの名無しさん
14/04/26 16:51:03.49 LWRQ8Tqr.net
最近はCPU速いんでネイティブじゃなくてjavascriptが流行ったり
最適なアルゴリズムより線形検索とかでも充分だったり
365:デフォルトの名無しさん
14/04/26 17:09:52.91 ztOmzoR+.net
うむ。今個人のPCで使われているDDR3-1600だと
転送速度12.8GB/sだからね。
0.01秒だと人間が知覚できるかどうかの世界だけど
その時間があれば100MBのデータを探索できるわけだからね。
366:デフォルトの名無しさん
14/04/27 18:18:02.68 dkXr/W0v.net
最近のJavascript JITはネイティブより速いことも多々ある。
367:デフォルトの名無しさん
14/04/29 16:58:26.39 pvgpWpOe.net
涙ぐましい努力をするより富豪的プログラミングが流行る時代だしね
368:デフォルトの名無しさん
14/04/29 19:48:18.31 gkPlm+Vx.net
それでもリソースに限りはあるわけで、大きいのだとどっかで破産するんだよな。
富豪的プログラミングじゃなくて、成金的プログラミングだと思うよ。富豪ってのは
周りが無駄に無計画に使っているように見えても、実際は締めるところは締め、
使うところは使うっていうのだからな。
369:デフォルトの名無しさん
14/04/29 19:50:52.99 rRRSFl+L.net
リソースがショートしちゃうもんな
370:デフォルトの名無しさん
14/04/29 20:17:40.02 8B6X7USU.net
どこがどう大きくなるのかを見積もって、必要なとこを必要なだけ節約する、って形が有効。
必要以上の節約は労力の無駄使い。
371:デフォルトの名無しさん
14/04/30 03:59:01.72 RSryIHGR.net
firefoxで動画再生してると
メモリ解放されなくてそのうち死ぬ
成金の糞flushのせい
372:デフォルトの名無しさん
14/04/30 17:31:12.56 8H1kM5Z6.net
UFC 128 - エリック・コク vs. ハファエル・アスンサオ
URLﾘﾝｸ(www.youtube.com)
373:デフォルトの名無しさん
14/05/01 08:04:28.79 9zM4+Fav.net
>>371
一般的に、I/Oなどは、1MBほどのバッファを確保して、
バッファに読み込んで、再生などの処理をしたら、
処理したデータを捨てて、次のデータを読み込む、
シーケンシャル・アクセスで、バッファのサイズは大きくならない
そのブラウザは、もう一度再生するときに、
ネット回線からダウンロードせずに再生するために、
データをローカルのメモリかディスクに保存しているんだな
データを捨ててないから、最後にはメモリが確保できなくなるので、
もう一度見ないものは、タブを閉じたらいいのでは？
374:デフォルトの名無しさん
14/05/03 00:51:05.80 pJ23Zgdt.net
１．中置記法を入力すると逆ポーランドに変換し出力する
２．逆ポーランド記法で入力するとそのまま逆ポーランドで出力する
の両方できるアルゴリズムはありませんか？
１．は操車場アルゴリズムでできるようですが、
操車場アルゴリズムだと２ができません。
375:デフォルトの名無しさん
14/05/03 01:02:13.43 nIlg1A2j.net
>>374
中値記法と逆ポーランド記法を識別する方法が知りたいって事？
376:デフォルトの名無しさん
14/05/03 08:21:56.99 pJ23Zgdt.net
>>375
はい、そうです
識別方法はありますか？
377:デフォルトの名無しさん
14/05/03 08:39:02.09 ci/X6yFn.net
>>376
末尾だけを最初に見れば良いんじゃね？
逆ポーランド記法の場合、必ず最後は演算子で終わるから。
但し、一番外側にカッコがある場合は、一度取り除いてから末尾を見ないといけないね。
378:デフォルトの名無しさん
14/05/03 08:41:32.32 ci/X6yFn.net
俺がやるなら、まず末尾から文字を順に見ていくかな。
カッコだったら次の文字に移動。
数字が先に現れれば中値記法。
演算子なら逆ポーランド記法。
379:デフォルトの名無しさん
14/05/03 10:33:17.49 pJ23Zgdt.net
ありがとうございます
末尾判断でやってみます
380:デフォルトの名無しさん
14/05/03 10:44:34.36 BYcmF+is.net
f
381:デフォルトの名無しさん
14/05/03 11:56:43.41 1SJdCv6F.net
俺は頭からやりたい
382:デフォルトの名無しさん
14/05/03 13:34:57.97 gqLjB/uh.net
頭で再帰しちゃったら無限再帰で _|_ やぞ
383:デフォルトの名無しさん
14/05/03 14:00:37.70 SFocP469.net
どして？
いま旅行中だから帰ったらやる
384:デフォルトの名無しさん
14/05/04 00:30:58.09 /8HFkyur.net
URLﾘﾝｸ(www.younganimal.com)
URLﾘﾝｸ(www.younganimal.com)
URLﾘﾝｸ(www.younganimal.com)
URLﾘﾝｸ(www.younganimal.com)
URLﾘﾝｸ(www.younganimal.com)
URLﾘﾝｸ(www.younganimal.com)
URLﾘﾝｸ(www.younganimal.com)
URLﾘﾝｸ(www.younganimal.com)
URLﾘﾝｸ(www.younganimal.com)
URLﾘﾝｸ(www.younganimal.com)
385:デフォルトの名無しさん
14/05/04 01:21:41.85 LoW5JUMG.net
続きはよ
386:デフォルトの名無しさん
14/05/04 01:23:49.16 tByDu0vN.net
続き見てきたけど、デザインパターンが分かって書いているとは思えないところがなんとも。
387:デフォルトの名無しさん
14/05/04 01:57:49.42 mBc+6kiF.net
続き読んでないけど、オカマなんか？
388:デフォルトの名無しさん
14/05/04 10:08:06.94 tByDu0vN.net
いや、オナホのソフトを作っている会社の社長。
ハードの話をすっ飛ばしていきなりオナホ界のジョブズだとかw
389:デフォルトの名無しさん
14/05/04 11:55:06.72 2wcEJRw7.net
さて、短い旅から帰ってきた
頭からの再帰、明日にでもやろう
その前に
頭からとか、末尾からとか
末尾再帰に関わる意味で言ってるんか？
おれは算術式の頭から見ていく
という意味で言っていたが
それにしてもなんでこんな簡単な問題が！
初心者の俺は根本的に問題を誤解してるのか？
ま、いいや、明日には書いておく
390:デフォルトの名無しさん
14/05/04 14:05:33.54 n8bRVLF6.net
>>389
少なくとも>>377で言ってる末尾は、再帰の話なんて一切してないよ。
単純に数式文字列の最後の文字と言う意味ね。
391:デフォルトの名無しさん
14/05/04 20:22:58.60 peygn8xB.net
>>374
課題では中置を逆ポーランドにだったけど、アルゴリズムの都合上、
中置もポーランドも逆ポーランドに変換(無論、逆ポーランドはそのまま)
また、各種記法の混在を認める
((1 + (* 3 5)) (8 - 2) (2 5 expt) +)
でもよし
方針 式の頭からワンパスで変換を終了する
使用言語 Scheme
URLﾘﾝｸ(codepad.org)
392:デフォルトの名無しさん
14/05/04 20:41:37.31 2wcEJRw7.net
>>391
どひゃ！
>>391は変数と演算子を区別していない！
式の計算ではなく
式の変換だけの課題だった！
もう、変換だけでなく計算してしまう過大なら楽なのに！
（今日は寝る）
393:デフォルトの名無しさん
14/05/04 20:44:47.52 2wcEJRw7.net
(number? x)のところを
(number (eval x ()) )にすりゃいいな
394:デフォルトの名無しさん
14/05/05 08:05:58.63 wP+UVhzo.net
>>391
式に変数も認めるバージョン
演算子情報はは演算子データベースに保持
URLﾘﾝｸ(codepad.org)
395:デフォルトの名無しさん
14/05/05 09:00:44.75 ZPrSoRKy.net
気持ち悪い
396:デフォルトの名無しさん
14/05/05 09:23:14.89 wP+UVhzo.net
あはは
ゲロはいてろ
397:デフォルトの名無しさん
14/05/16 17:36:11.48 SXeDLzrE.net
再帰プログラムを非再帰プログラムに変換する方法が理解できません。
たとえば、フィボナッチ数列を再帰的に計算するプログラムを
スタックを使って非再帰的に計算するプログラムが野崎昭弘さんの
本に載っているのですが、何度読んでも理解できません。
どうすれば理解できるようになりますか？
398:デフォルトの名無しさん
14/05/16 18:03:16.22 lP/gHzU8.net
たまたまそのコードと自分の相性が悪い、といったようなことはあるから、
他の例をさがしてみたら？
399:デフォルトの名無しさん
14/05/16 18:38:21.93 rkx/vo/u.net
>>397
fibonacchi数列の非再帰表現をするにはごく普通にwhileループを使って実現できる
f(n) = f(n-2) + f(n-1)
のf(n-2)の値を例えば変数prev2に保存し
f(n--1)の値を例えば変数prev1に保存すれば
f(n) はprev2 + prev1で求められる
それを変数ansに格納すれば
while ループごとに
ans = prev2 + prev1
prev2 = prev1
prev1 = ans
と更新していけばよい
また、f(1)=f(2)=1なのでそれはwhileループで処理しない。逆に
f(3)以上の値をwhileループで求めればよい
具体的には、これを見ろ
URLﾘﾝｸ(codepad.org)
400:デフォルトの名無しさん
14/05/16 18:41:31.99 lP/gHzU8.net
フィボナッチを再帰的じゃなく求める方法についてじゃなくて、
再帰的なコードのループへの変換がわからない、ということでしょ。
401:デフォルトの名無しさん
14/05/16 18:42:59.47 rkx/vo/u.net
ん？スタックを使いたい？プッシュしてな、いきついたら、ポップするんだよ
402:デフォルトの名無しさん
14/05/16 19:13:51.53 a2G3KqVr.net
>>399
まあ再帰は基本的に遅いけど、メモ化すればずっとマシになるし(震え声)
C++で書いてみたサンプル↓
URLﾘﾝｸ(codepad.org)