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

【関連スレ】
3Dアルゴリズム全般
http://toro.2ch.net/test/read.cgi/tech/1164171086/
＜集大成＞アルゴリズム大辞典
http://toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
http://toro.2ch.net/test/read.cgi/tech/1217773415/

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

このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

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

　　　　　　　　　　　　　　　　　　京都大学霊長類研究所

>>2
アイ死ねw

データ構造,アルゴリズムとデザインパターンは全然別のものだと
思っているのは私だけか。

俺もそう思ってた。

こっ…これは…

どうでもいいが

あげ

デザパタとか言ってみたいお年頃なんだろ

アルゴリズムって言ってみたいお年ごろと何が違うのかわからんが。

デザパタはJavaのキツキツの制限を緩めるための苦し紛れの小細工

アルゴリズムは科学
デザパタは工学

アルゴリズムは技術
デザパタは技能

アルゴリズムは理論
デザパタは療法

どれにしようか迷ったけど面倒だから全部書いた

CTMCPすら読まずにオレ様定義を開陳し合う場となりました。

デザパタは本来ならマクロ等で抽象化すべきところを
言語側の表現能力が低いために出来ず、結果として
似たパターンを繰り返し書く羽目になったパターンのカタログ集

まぁ、確かに言語の補助が弱いのをプログラマの経験則から解決策として残されているものが多いわな。
現に、Javaなんかでは、singltonとかメンドクサイ事が必要だけど、C#とかでは、何のことも無かったりするし。

それデザインパターンの考え方と
パターンの実装をごっちゃにしてるだろ。

アルゴリズムで言えば、C言語だとバブルソートは面倒くさい処理が必要だけど、
ある言語なら、bubble_sort関数呼ぶだけで済むしって言ってるようなもんだろ。

デザインパターンって
データ構造とアルゴリズムを合わせたようなものだと思う。

アルゴリズム＋データ構造＝プログラム
と昔から決まっておるのじゃ

相変わらず知識に溺れたバカばっかりw
ウザウザw

>>16
全然違う
なぜならC言語でもバブルソートは関数として抽象化できるから
一度書いたら何度も繰り返し書く必要は無い

Strategyパターン

クロージャがある言語なら、ただ単にクロージャを渡すだけの普通のコードで、
名前を付ける必要すら感じない

どっかのゴミ言語ではこんな感じになってしまうが
http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:StrategyPatternClassDiagram.svg

いや「特定のパターン」はそうだろうけど、
別のパターンはそうとは限らないだろ。

一つを語って、全てが無意味だとなんで思った？

>>21
それ、クロージャがある言語でも大差ないと思う。

関数が第一級の言語だと、クラス図として関数も扱わないといけないはず。
で、クラス図に対応する、関数図は関数のシグネチャ。

明示的には継承とは書かないけど、決まった関数のシグネチャを継承した（同じに合わせた）
関数を作るから

[Strategy]
　　↑
[ConcreateStrategyA]

の代わりに、

[引数一つの関数]
　　↑
[実装関数]

こうなってるだけじゃないかな。

そういう問題じゃない感

http://www.amazon.co.jp/dp/4797304952/

定本 Cプログラマのためのアルゴリズムとデータ構造 近藤嘉雪著


この本もわかりやすいお

データ構造とプログラミング（'13）
http://www.ouj.ac.jp/hp/kamoku/H25/kyouyou/B/joho/s_1570048.html

死んでしまえクズ共がw

前スレの後半のような良スレになればいいなw

Wordとかのエディタの「元に戻す」「Undo」機能ってどうやって実装されてるんですか？
Mementoパターンなるものをwikiで調べたんですが、Wordとかの大きな文書だと、
一つのstateのデータ量が多すぎて、すぐにメモリが足りなくなって破綻しそうな気がするんですが・・・

http://ja.wikipedia.org/wiki/Memento_%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3

全体のコピーじゃなくて差分と操作内容

>>29
そこいらは腕の見せ所だから色々な実装がある。と言うのが
普通の答えだと思いまする。
結果データではなく、verbとパラメーターをリング状に記憶
させるという実装はしたことがある

A→Bへの変化が起きるとき、B→Aへと戻る動作Δを登録していく。
Undo時に動作Δを呼び出す。

wordの文書って画像いれなきゃ
数十キロしかないだろ？

バカスレw
バカ共がまた知識ぶって騒いでやがるw
死ねゴミクズw

リロケータブル形式で記憶しておけばメモリだけでなくファイル等も利用することが可能。
作業途中の状態保存にも使えて便利。

stack.push(deflate(操作前のデータ xor 操作後のデータ))

とか思い付いたけどどうよ？

簡単にジャーナルを取れるのに差分計算するとか
アホの極み

C++でstateパターンを実装していたんだが、実はCライクに関数ポインタを使った実装のほうが短くて簡潔書けることがわかった。でも他人が見たら何をやっているのかわかりづらいかもしれないから、多少手間になっても決まったデザインパターンでやるほうがいいのかもしれない。

>>29
UndoでMementoってのは、実は多くの場面で使いにくいんじゃないかなーって思ってる

Adobeのアンドゥは無限回じゃないけど、あれはこのパターン使ってるのかな

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
全角．はリンク禁止回避

>>40
i++; j--;がないと仮定すると
a[i]がpivotと同じ値だったらiが進まない。
a[j]がpivotと同じ値だったらjが進まない。
効率が悪い、無限ループになる恐れがある。
なので、i++; j--;は無限ループを回避するために必要であるか、
または、効率を良くするために必要なのである。桃白白はそう思うのである。

なくても問題ないが

まだやってるw
さっさと死ねw

入門 データ構造とアルゴリズム [大型本]
Narasimha Karumanchi (著), 黒川 利明 (翻訳), 木下 哲也 (翻訳)

この本はおすすめですか？

http://www.amazon.co.jp/dp/4873116341

>>44 が何者かによる。学生さんならいいんじゃない？プロならう〜ん…個人的にはいらないかな(買わなかった)

>600弱の練習問題とその解
・・・ｗ

プログラミングの宝箱っていう本、誤りが多すぎる。
なんで売れているの？

真の宝の周りにはたくさんの偽りの情報が紛れているものさ

世の中、見た目で判断する人が多いから

見た目は大事

プログラミングの宝箱っていう本、見た目がいいの？
見た目がいいってどういうこと？

杉原厚吉のデータ構造とアルゴリズムの本ってソートのプログラムも
載っていないんだね。だめだめ。

セジウィックの本もどこがいいのか分からない。
プログラムが読みにくいし。

やっぱりクヌースの本が一番いいのかな。

>>47
その本、クイックソートのプログラムが間違っているよね。

>>47
そもそも売れてるの？

ソフトバンククリエイティブの本っていい加減な本が多いような気がする。

ところでアマゾンのランキングって何のランキングなの？
たとえば、アルゴリズムの本のランキングを見るとどう見ても売れていない
ような絶版の中古本がランクインしていたりする。

ところで、MITのOpen Coursewareで勉強している人はいない？

柴田望洋のアルゴリズムとデータ構造の本、レベル低すぎ。
なんなの望洋ってｗ

>>58
どのコース？

見慣れない本質不必要な単語が頻出するから
講義系のテキストは却下だな

まだ下の上二つを見始めたところです。英語はよく分かりませんが、板書を見て大体
分かります。見ている（見た）人がいたら質問とか今後すると思うのでお願いします。

Pythonによるプログラミングの入門の講義。レベルが低い。
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/

コンピューターサイエンスのための数学。レイトン教授が最高に面白い。
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/

まだ見てないけど、和田英一が訳した有名な教科書の著者の講義。まだ見ていない。
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/

アルゴリズム入門2005年。まだ見ていない。リベストらの有名なアルゴリズムの教科書の著者が講義。
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/

アルゴリズム入門2011年
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/

>>62
アルゴリズムの講義なら Coursera や Udacity あたりに新しいのがいっぱいあるぞ。セジウィックが講義してるのもあるし。
https://www.coursera.org/courses?orderby=upcoming&search=algorithms

そういう自分も Coursera の前は>>62の最後のコースでアルゴリズム勉強したわ。
古いからちょっと画面が小さいんだよねー。

>>63
情報ありがとうございます。そっちも視野に入れたいと思います。

死ねゴミ共がw
死ねゴミ共がw

オライリーから出たインド人のアルゴリズムとデータ構造の本、最悪。

説明もほとんどなしにコードと問題が載っているだけ。

買ってはいけない。

>>66
コードと問題が説明になっているのだろう。

あれは演習問題集だから…

資格勉強に役立つ？

就職や昇級に反映されるなら役立つ
そうでなければ趣味

アルゴリズムやデザインパターンって公式的に覚えてしまったら、
中身がどうなっているかどうか知っていようといまいと生産性は変わらない。
ただ中身を知っていると、何かトラブルが起きたり、
それらを組み合わせて新しいことを覚えなくてはいけないときに差が出てくる。
が、今時はそういうことはかなり稀なので、機械的に覚えてしまって、
さっさと人を使う立場になってしまう方が悩まなくていいかも。

>>71
トンチンカンなこと言ってるぞ？ ライブラリレベルまで落とし込まれているような
アルゴリズムならともかく、デザインパターンは公式的に覚えて使えるもんじゃ
ないぞ。中身の実装方法はともかく、GoFのデザインパターンですら、複数
組み合わせて使うのが普通なのに。

effective javaのいってんじゃねーの
俺ってやさしい

>>66
君、アマゾンのレビューを書いた人？
星一つしかついてなかったｗ

率直に言って、C++という言語はデータ構造を分からせるのには向かない。
内容は時間的/空間的計算量という評価に徹してデータ構造とその読み出し方を
解説したもので、むしろ優れた本だと思う。

>>75
普通の大学で使うような教科書のほうがいいと思う。
エイホ・ホップクロフト・ウルマンのアルゴリズムとデータ構造とか
MITの教科書とか。

Ahoの本は良いな
はずれがない

クヌースの本も読んだほうがいい？
クヌースの本はプログラマ必読の書らしいけど

>>78
全部読むのは難しいんじゃないですか？
アルゴリズムの解析の部分は難しいし、実益が少ない。
アルゴリズムの手順だけ読むくらいでいいのでは？

あと新しいアルゴリズムが書かれていないらしい。

クヌース（ブルース風に）

クヌースは古典だな
読むか読まないかなら、もちろん読んだ方がいいが

>>79
新しいアルゴリズムは論文読むしか

クヌース　ホシーイ　ケレード
ゼパーン　ニナーテ　ルヨーネ
シカータ　ナイカーラ　エイーゴ
デヨンデール　

>>79
ところで新しいアルゴリズムてどんなの？
遺伝とかならいらないけど

>>83
すみません。よく知りません。

擬似乱数を生成するメルセンヌツイスターが載っていないって、
考案者が文句言っていたのは知っています。

クヌースの本は要約版が1冊になって出版される予定だけど、実現しないだろうね。
というかThe Art of Computer Programming自体が完成しないか。

既刊の第4巻はおもしろそう。

わざと初等的な証明をつかってるから
無駄にめんどくさいね。
群とか環とか使えば良いのにっておもうよ。

self containedになっているのだろう

>>84
あの膨大な本の中の、たった一つのテーマだからね。

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()
}

補足です。

void AppDerived::method(){
ptr->func();
}

class DetailBase{
virtual void func(){ return; }
}

上記の方法を避けたいための方法です。

>>89
>オブジェクト思考的
は関係ないね,、C++の実装としてだろう

>>89
その派生クラス同士の関係性によってはアリな場合もあるんだけど、 一般的には無しだね。
基底クラスを触りたくないからと言うのは全く理由にならないと思うよ。

>>89
AppBaseがコンポジションするDetailBaseはPublicやProtectedってことでしょ？
それなら派生クラスから弄られることを想定しているってことになるから
AppDerivedのMethod()で新しくDetailDerivedを保持し直したらいいんじゃないの？

Privateなら基底クラスでしかDetailBaseを弄らないのだから
AppDerivedのMethod()内でのみ使用するためにDetailDerivedのインスタンス生成すりゃいいんじゃないの？

>>90の方法を避けたいってのは、AppBaseがDetailBaseをコンポジションしてポリモーフィズムするのを
否定しちゃってんじゃないの？コンポジションしている意味が無くならない？

ﾌﾟｯw

ｸｻｯ

すまん

おまえかよ

このように他人（主に女の子）の汚名を代わって受けるのがイケメンパターン

死ねゴミ共がw
死ねゴミ共がw

落ち着け

ある順序列Aとそれに含まれる一部の要素からなる順序列Bがあるとき、
Bの順序を満たし、かつAから「変化が少ない」順序列Cを得たい。

A: [ 1 2 3 4 5 ]
B: [ 4 3 ]
C: [ 1 2 4 3 5 ]

「変化が少ない」の基準は必ずしも特定しないが、一例として「各要素の
移動距離の二乗和が小さい」などが考えられる。

ここで、近似解でよいので計算量の少ないアルゴリズムが欲しいのですが、
使えそうなアルゴリズムがあったら、ググるキーワードを教えてください。

要素の重複とかあるの？

>>101
> 「変化が少ない」の基準は必ずしも特定しないが、一例として「各要素の
> 移動距離の二乗和が小さい」などが考えられる。

これに激しく違和感を感じるけど、

> ここで、近似解でよいので計算量の少ないアルゴリズムが欲しいのですが、

近似解でいいならGAが楽じゃね？

Aを走査していき、Bにも含まれる要素に当たったら、Bの要素順で置き換える
……だと変化が大きいのかもしれないのか

>>102
重複はない前提です。

>>103
その基準のところも、なにか使えそうなものがあれば調べてみたいと思いますが。
ところで、どういうところで違和感を感じるでしょう？

>>104
Bの並びによっては団子になってしまいそうですが、確かに計算量は非常に
少なそうですね。

>>105
順列と最小二乗って、同じ目的で使って嬉しくなる数学的根拠があるのかな、と思って。
置換の数で距離を測るのが一般的かな？とか。
感覚的な意見で申し訳ないけど。

感覚的なものなのでそこはあまり根拠はないですが、移動距離が大きくなるにつれて
ペナルティは増大するほうがいいのかなと。
ただまぁ、ひとつの要素が移動すればその距離に応じて他の要素もずれるわけなんで、
移動距離の総和とかあるいは単純に移動した要素の数でもいいかもしれないですね。
順序の距離とか順列間の距離とかで探したらいくつか距離の定義が見つかりました。

死ねゴミ共がw

落ち着け

グーグルのアルゴリズムコンテストとか受けてるやついる？

全要素の値を0で初期化した要素数nの一次元配列にたいして、
ランダムに選んだm (< n) 個の要素のみ値を1にした配列を作りたいです。

次の方法を考えました。

1. 先頭からm個の要素の値を1に、残りの要素の値を0にした配列を用意する。
2. その配列に対して Fisher-Yates shuffle を施す。

これよりも実行速度において効率的な方法はあるでしょうか。
（並列化を利用して効率よくする方法もアリです）

ただ、できるだけ偏りは無くしたいです。

nとmをどれくらいに想定してるのさ

>>112
n は 1000000 くらい

m は 1000 log 1000 くらいなので、だいたい 7000 弱程度です

（その程度だと、どんな馬鹿なアルゴリズムでも一瞬で終わる処理だと思うが、何らかの効率的アルゴリズムが欲しい理由でもあるのかも……）

>>114
もっと巨大な配列なら、より効率的な方法があるのでしょうか。

どんな方法か知りたいです。

>>115
くじ引きと同じ論法でO(N)で作れるだろ

>>116
それって、1000000個の重複のない数列から7000個を取り出すんだろ？
重複のないくじを作るのに結局シャッフルがいるんじゃないのか？

だったら、やってることは>>111と同じだと思うが

というか、>>111だってシャッフルはO(N)なんだから、
そもそも質問の意図もよう分からんが

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

偏りをなくしたいということは低周波成分をなくしたいということかな？
すなわち、1が連続したり、なかなか出なかったりするのを無くすということ。
だったら乱数を使うのは誤り。

>>118
すごいですね、その発想は出てこなかったです。
簡単な例で図を描いて確かめてみましたが、みんな当たる確率は同じになりました。

Fisher-Yates shuffle でやるより断然スジがいいです。
採用させてもらいます。


>>119
たしかに、1 や 0 があまりに連続しているの好ましくないです。
その場合、乱数を使わずにどうやるのでしょうか。

1 か o かを選ぶのに乱数を使うのではなく、もっと別のところで使うという意味でしょうか。
それとも、全くどこにも使わないのでしょうか。

>>120
乱数から低周波成分を除去した数列を使います。別名ブルーノイズ。

配列を参照するだけなので超高速で偏りの無いパターンを作ることができる。
100万個から7000個を選んでも１が連続する確率は0。規則性もなし。
ブルーノイズ数列の一部をとってもブルーノイズ数列。使い回しができる。

欠点として１回はブルーノイズ数列を作る必要があるが時間がかかる。100万個
の数列だと1時間くらいかかる。一回作ってファイルに保存しておけばOK。

>>120
不思議に思ったんだがひょっとして
配列の全要素の初期値って不定扱いなのか？
なら>>118を採用する理由もわかるが

言語にもよるけど、int 型なら多くの場合0じゃない？
で気づいたけど、1 か 0 しか入らないなら bool 型でいいんじゃないか？メモリもグッと節約できる。

>>122
いえ、今回は、必ず何らかの値で初期化される、という種類のデータ構造（配列）を使っています。
（言語的は初期値として未定を表す値を指定できる配列も簡単に作れますが、
今回は意味ないので、そのような配列は使っていません）

>>118を採用しようと思ったのは、配列の頭から順に要素をトラバースしながら、
その要素のみを参照して値を設定していけるという点がシャッフルに比べて優れていると思ったからです。
要するに、データ構造そのものをどんどん大きくしながら作っていけます。

シャッフルも Fisher-Yates shuffle でしたら順にトラバースしますが、
その要素と、別のランダムに選んだ要素を参照しなければならず、
シャッフル処理をする前にデータ構造が完全に出来上がっていなければなりません。
その上で要素をスワップしていきます。

じつはプログラミング言語はCではなくHaskellを使っており、Haskellでは後者より前者のように、
値を入れた要素を次々と繋げながらデータ構造を（目的の規模まで）大きくしていく方が
プログラムしやすいんです。

>>123
すいません、0 と 1 を使ったのは単に質問をシンプルにするためでした。
本当は、質問で 1 を入れるところでは min < x < max のランダムな浮動小数点を入れます。

そもそもの目的をぶっちゃけますと、ランダムな重み付き有向グラフの隣接行列を作ることです。

>>124
> >>118を採用しようと思ったのは、配列の頭から順に要素をトラバースしながら、
> その要素のみを参照して値を設定していけるという点がシャッフルに比べて優れていると思ったからです。

すいません、ちょっと言い方がおかしいですね。

配列の頭から順に要素をトラバースしながら、ではなくて、順に配列を大きくしながら、
とか、配列を組み上げながらと言うべきでした。

>>121
申し訳ないです、そこまで強力なものは今回は求めていないです。
あまりに偏りすぎていると使えないな、という程度のことでした。

しかし、これはこれで大変興味深いです。
ホワイトノイズやピンクノイズなどは聞いたことがありますが、ブルーは初耳です。
調べてみます。

なるほど納得

非零要素を一次元上（あるいは二次元とか）に並べて
それを仮想電子のようにみなし仮想クーロン斥力みたいなの計算して
要素番号補正したらとか考えてたんだが
それだと逆に傾向出ちゃうか

値を入れた同じ行、同じ列に対して再度選択を阻害するパラメーターを入れて
云々かんぬん…いかん、わけがわからくなってきた
逃走っ（しゅたたた…）

やってみましたら、たとえ Haskell であっても、
>113 程度の規模ではシャッフルでもくじ引きでも、あっという間でした。

>>114 の指摘通りで、かなり恥ずかしいです。
憶測で遅いと決めつけず、質問する前に試すべきでした。

プログラムの見やすさが抜群に良いという点で、くじ引きの方法でやることにします。

みなさん、ありがとうございました。

Edmonds's Blossom Algorithmを詳しく説明していただけないでしょうか

二次元座標に、ラベル(高さ固定、横書き)を 重ならないように配置したいです。


現在は、y軸をラベル高さで分割して、
各領域で、ラベルが指定座標を含むように左側から詰めて配置しています。

この方法だと、3点以上集中すると、大きくずれてしまいます。


どのようなアルゴリズムがありますでしょうか？
また、動的生成なので、優先順位は コスト > 見栄え です。

>>130
ある点を矢印で示すようなラベルなら多少点から離れてもいいよね
それなら幾らでもやり方はあると思うよ
例えば、点や四角（ラベル）の当たり判定で配置

>>131
おっしゃる通り、多少離れるのはかまわないです。

>点や四角（ラベル）の当たり判定で配置
ラベルの矩形の判定はやってみたのですが、
どの方向にずらすべきかのところで詰ってしまいました。

結果、上記のx軸+方向のみ補正な方法になってしまいました。


何かヒントがいただけたらと思います。

>>132
そういったアルゴリズムを組んだことはないけど

ラベルの矩形が重なった時
指し示す点とラベルの四隅の点との距離が一番短いラベルの点を選出し
最初に、2点間の傾きを保ちならがら、そのラベルが指し示す点との距離を縮めて
縮めた際に2点間の距離が0になっても矩形が重なっているなら2点間の傾きを変える
目安となる距離と傾きの初期値を設定しておけばいいかな
傾きの初期値はラベルの4隅それぞれ、回転して考える

判定する矩形の4隅の点を左下にのみ、指示す点の45度右上の傾きにラベルを固定してしまってもいいかもね

机上の空論だから上手くいくかどうか分からないのは許してね
難しく考えすぎているのかもしれないわ

こういう事ができればいいんでしょ

http://ja.wikipedia.org/wiki/%E5%8A%9B%E5%AD%A6%E3%83%A2%E3%83%87%E3%83%AB_(%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っていうオープンソースソフトが解りやすかった

力学エネルギーに基づくグラフ描画が求めていたもののようです。

まとまった時間を作って、出ているアルゴリズムを読んでみます。

お付き合いしてくださった皆様ありがとうございました。

グーグルの検索エンジンのアルゴリズム
http://webblogsakusei.main.jp/seo_taisaku_syukyaku.html

ふぇぇ」

計算量のオーダーの考え方で質問です。

(a # b) を a の b 個の下降階乗冪を表す式とし、
(#) は除算 (/) よりも優先順位が高いとします。

x や y は m よりも十分大きい数とすると、

f(m) = x#m / y#m

この場合、計算量のオーダーは O(m) と考えていいでしょうか。

ダーク構造、エルゴリズム、ディザインパクトに見えたマジで。

下記の問題について、私が考えた方法では計算量が n 乗のオーダーになってしまい、
たいして大きくない数で試しても計算にかなり時間がかかるのですが、
みなさんならどのような解き方をするでしょうか。

[問題]
m 枚のカードの束からランダムに x 枚引き（x <= m）、引いたカードに印をつける。
引いたカードを元のカードの束に戻し、再度ランダムに先ほどと同数 x 枚引き、
印がついていなかったら印をつけ、また元の束に戻す。
このように x 枚カードを引いて印を付けて戻す行為を n 回繰り返した後、
m 枚のカードの束に印のついていないカードが p 枚ある確率を求める関数 F(m, x, n, p) を作れ。

[私の考え]
全体の事象は、{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
私は、関数 R と D と {C(m,x)}^n の計算は任意精度整数で、
関数 F 内の割り算は有理数型で、
そして最後にそれを倍精度浮動小数点型にしています。

これってアルゴリズムの問題じゃなくて数学の問題じゃね？
オイラーのガンマとか関係してそうだけど。数学できるやつならパパっと式が出てくるんだろうな。
残念ながら僕は数学ができたという過去形なので無理です。

F(m,x,n,p)=C(m,p)*{C(m-p,x)/C(m,x)}^n ？

>>144
わたしも、これを代数的に解く方法は知らないのでプログラムで解こうと思いました。

プログラムで解く場合に n 乗よりも低いオーダーのアルゴリズムが存在しないのなら諦めます。

今のところ私が挑戦した限りでは、n 乗のオーダーが限界でした。

>>145
それは違います。

例えば F(4, 2, 2, 1) で計算してみてください。
つまり、4枚のカードから2枚ランダムに引くことを2回繰り返して、
一回も引かれなかったカードが1枚存在する確率です。

本当は 2/3 ≒ 66% です。
しかし >>145 で計算すると 1/1 = 100% になってしまいます。

>>145
C(m,p) で選んだp枚に対し、m-p枚からx枚選ぶ過程が一意でなく重複が入ってるから×だな

a[0]からa[n-1]までの配列があって、
その中身をコンマで区切って表示したい

print a[i] + ','

みたいなことをすると、最後の要素にもコンマが付くので、
これをうまく避けるアルゴリズムは無いものか

if (a=next()) { push(a); while (a=next()) push(cat(",",a)); }

for (int ic = 0; ic < n; ++ic) {std::cout << a[ic]; if (ic < n - 1) std::cout << ',';}

出力してしまわずに一旦文字列に出して、
出来上がってから最後のコンマを1個削る

n が小さければ >>151 の方法でOK。シンプルでわかりやすい。
ただし、if 文で n 回の比較が発生するから、n があまりに大きい場合は >>152 のやり方がいいと思う。

最後の文字を削れない場合は for 文で a[n-2] まで ',' と一緒に出力して、追加で a[n-1] を出力するか。

>>150 は何の言語？

最初の要素と残りの配列に分ければいいだろと、Haskell なら考える

分ければ簡単なんだけど、同じような処理を2回書く羽目になるんだよな

>>149
puts a[0..n-1].join('.')

結局、うまい方法が無いので言語側で join 機能を提供している
join があるならそれを使うのが最もスマート

String d=""
String r="";
for(String b:a){r+=d+b;d=",";}

コンマが先にあると考えて、先頭のコンマを削除する方式だな
毎回同じ値で更新するのが美しくない

if(0<a.length)print(a[0]);
for(int i=1;i<a.length;i++)print(','+a[i]);

それが正解だろうな
lengthが2回出てくる以外は殆ど無駄がない

printの部分が長いコードなど２つに分けたくない事情があるときは>>158の方がいい。
定数へのポインタを代入するだけなので効率も悪くない。

長くなくても、似た出力が2箇所あるのは嫌だな
コンマ部分だけ出力が別にあるのは構わないけど

str = a[i]; if (i < n - 1) {str += ','}

こうすれば一箇所
>>151とほぼ同じ

俺もかつては悩んだがあるとき以降はずっとこう書いてる。
for (int i = 0; i < a.size; i++) {
if (i != 0) print(,)
print(a[i])
}

俺ならdo-whileの条件文にカンマ出力ねじ込んで軍事法廷に召喚される

>>164
for (int i = 0; i < a.size; i++) {
print(a[i])
if (i < a.size - 1) print(,)
}

最初だけコンマを付けない、よりは最後だけコンマを付けない、の方が
人間が理解しやすいような
ただ、条件文が読みにくい

は？

二個目以降はカンマがつくよ、であり読みやすい。
しかも、ループごとの状態がたとえば[a, b, c]のとき、
0: a
1: a, b
2: a, b, cとなっておりどの状態も気持ちいい。

後カンマ方式だと、
0: a,
1: a, b,
2: a, b, cとなり、0と1の状態が気持ち悪い。

それはただのバグだな

関数型の発想で命令型のコードを導く手順
(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 "&yen;n"
ここまで展開すれば、これをたとえばC言語へ移植することも容易いだろう

>>168
この考え方、感じ方は大事だね
例えば、これを範囲を指定してコンマ区切りの文字列を返す関数にしたら
前者ならすんなり行く

テキストエディタでコンマ区切りのデータを編集する時に、
どうしてもコンマが余ったり足りなかったりする

print (xs[0])
for x in (xs[1..n])
　print (", " + x)
では間違い？

例えばファイルへの出力に変更した時に、
複数箇所のprintを直して回らないといけない

バカ？

>>173
もし言語がRubyであるならば、以下の問題がある
(1) 最後のendが抜けている（これは、おそらくtypoだと思う）
(2) メソッド print は実行のたびに改行するから、期待する結果とは一致しない
(3) (2)の対策として print の代わりに printf を使ったとしても、
　もし xs が空であると xs[0] の値は nil になるから、
　メソッド printf の実行が引数エラーになる
　（メソッド仕様上、printf の第一引数は文字列であるべき）

ぷーん

>>176
ネタにしてはつまらんし、素なら悲しい。

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[]; としてるけど．

出力するぎりぎりまで判断を遅延するのが賢いので、
文字列に修飾子としてコンマの追加の条件文を書けるような言語なら綺麗に書ける筈
三項演算子はそれに一番近い

for (int ic = 0; ic < n; ++ic) {if (ic > 0) std::cout << ','; std::cout << a[ic];} // 宗旨替え

前にコンマが付いてると見るか後にコンマが付いてると見るかは、
完全に相対的なので、どっちでも等価

セパレータだと思えば前だし、エンドマークだと思えば後
文末のセミコロンが本当は行の区切りだと判ってる人には、
後にコンマが付くのが基本で、例外的に外しているという考えに近い筈

エンドマークだぁ？？
例外的に外すという考えだぁ？？

カンマは区切りっしょ。
CSV形式という文化はずーっと前からあるように。
Comma Separated Valuesだぞ？

イタリヤコンマ

pascalで最後の行だけはセミコロン付けてはならんというルールに律儀に従っていればいい

ターミネータとセパレータの違いだ

コンマタレブー

Cは最後のやつにもセパレータ付ける文化。

じゃなくて、最後に(も)付くのがターミネータで、
C言語のコンマのように、最後には付かないのがセパレータ。

ついでに言うと、C言語においてセミコロンは、式文やdo-while文みたいな、
「一部の文の」ターミネータ。あと for の頭部でセパレータとしても使われてる。

単に空文の存在を許容してるだけ

違う。

C言語において「空文」は、「空文字列にセミコロンが付いたもの」だよ。

違う。

C言語において「空文」は、「セミコロンだけの文」だよ。

死ねゴミ共がw
ばーかw

違う。

どうでもいい。

>>149
最後の","を'\0'で潰すのがはやい

そんなことできる言語もめっきり無くなったな

C言語だって文字列定数とかを指してたらやっちゃダメだし

どう考えてもバグの宝庫な仕様だよな

文字列がイミュータブルなこととミュータブルなことのどっちが？

それとも \0 ターミネーション？

文字列は文字数と文字データの構造体だったんだけどな

lenで1バイト持っても末尾の00に1バイト持っても同じだしな

最初にサイズが分かるか、辿っていかないとサイズが分からないかの違いは有る。
前者はBSTR型とかね。

データチャンクだと、サイズ+データの繰り返しだな

>>201
256以上の長さの文字列どうするんだよ？

そんなもん、長さに4バイト取っても必ず有限だろ

そう言えば、255バイト長のパケットを送れない通信プロトコルがあったな。尤もあれは長くても508バイト長までだけど。

可変長文字列を管理するデータ構造を考えるだけでも楽しそうだね。

>>204
0-127 のときは そのままの値
128-255 のときは (その値 - 127) x 128 + その次のバイトの値
ただしその次のバイトの値が 0-127 のときはその次のバイトの値をそのまま使うが
その次のバイトの値が 128-255 のときはさらに (上の値 - 127) x 128 + その次の次の値とする
とか

7bitのリトルエンディアンで格納して、最終バイトの8bit目を立てる

BigInt

文字列の中のパターンの置き換えをおしえてください。
たとえばxを任意の文字としてabxをbxに置き換えbxをxにおきかえるとしたら
abcをcに置き換えたいです。
この時、この置き換え操作は無限に続かないことを前提としています。
この例では一つのパターンでしたが、プログラムの入力としてパターンと
置き換える文字列、出力として置き換え後の文字列であるものの
作成方法が分かりたいです。

正規表現ライブラリのソースでも読んでみたら

再帰処理を使った順列のプログラム（JavaScript）について質問があるのですが、
ここで教えてくださる人はいますか？

>>212
とりあえず質問内容を書いてみたら？
答えるかどうかは気分次第だけど。

アルゴリズムとデータ構造の勉強に使える本で木構造やリストの実装、
バックトラックとか動的計画法まで載ってる本で読みやすくてコードが書いてるやつ
何がいい？
はじめてのアルゴリズム　上原
とかエイホさんのとかっていいの？

アルゴリズムイントロダクションの総合版買っとけばいいよ

あの巨大な枕か

>>214
プログラミング・コンテスト・チャレンジブック、第2版、2012
グラフ理論など、ほとんど全てのアルゴリズムを網羅
問題数も多く、パズル感覚で楽しめる
AIやシミュレーションゲームの参考になる

TopCoder
ttp://toro.2ch.net/test/read.cgi/tech/1333159918/l50

アルゴリズムを初歩から勉強をしたくて
プログラミング・コンテスト・チャレンジブックを読もうと思ってるんですけど
その前にやっておくべき本とかってありますか？
アルゴリズムイントロダクション，データ構造とアルゴリズム（杉原）が候補にあります．

ちなみに，現在大学生で，CとPythonはある程度書けます．

>>218
プログラミング・コンテスト・チャレンジブックはひと通りアルゴリズムを学んだ人が腕試しにやるような本だから、候補に上げたような本を先に読むんでいいと思う。

杉原は知らないけど、アルゴリズムイントロダクションもちょっと数学的考察とか証明の割合が多いから、難しいようなら他の本を当たった方がいいかもしれない。一生使えるから、とりあえず買っちゃうのはいいと思うけど。

あとは大学(自分のとこでも、他所でも)のアルゴリズムとデータ構造の授業で使ってる教科書を見てみるのがいいと思う。

>>219
ありがとうございます．

数学的考察も欲しいのでアルゴリズムイントロダクションを買おうと思うのですが
初心者でも総合版を買うことをおすすめされますか？

鈍器としても使えるらしいので総合版にしようかと思っていたのですが
あまりにも重すぎて使いにくいという声など，もしありましたら教えていただきたいです．

間違ってたらごめんだけど、
たしか総合版にしか無い箇所があるんじゃ？

>>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
現在わたしは、Ph.D.(Doctor of Philosophy)をとらなければ
ならないようなプログラムを、みんなが書くべきと考えていません。
多くの理論がこれまで開発されてきましたが、そのほとんどは、
実際のプログラムではあまり使われないものなのです。
こうしたものは、ものごとを極限までつきつめるときぐらいしか、
役に立たない。これらの理論の値打ちは、
ユーザーに全体の構造を見渡せる視野を提供することにあるのです。
理論をたくさん知っていればいるほど、ユーザーは、
プログラムで実際に応用するほんのわずかなことが、
より楽に理解できるようになるというだけのことなわけです。

ユーザーは、自分が扱える範囲を広げるために、理論を必要とします。
たとえばリストでいえば、ユーザーがリストに関して、
より複雑な理論を知っていれば、プログラムにこうした理論を
使うことがなくても、プログラムの中の単純なリストの使い方は、
(理論を知らない人が書いたものと比べれば)
はるかに自然なものとなるのです。

その全文が書かれたのって、おまえが生まれる前じゃないの？
部屋の飾りにはいいかもしれないけれど

アルゴリズムは盆栽

このツリーの曲がり方はいいね

ごめん、この枝間違って切っちゃった。

平衡木って盆栽的には美しくなさそう

>>221 >>222
丁寧にありがとうございます！
追加されたのは比較的高学年で学ぶ範囲なのですかね．

大学院で学ぶ内容も網羅してくれているとありがたいので，総合版にしようと思います．

アルゴリズムって一回は言ってみたいかっこいい言葉だよね

アルゴリズムたいそう

アルゴリズムに期待するのって、高卒とか文系SE?
情報科卒業して、CSSやPHP弄ってる層に謝れよ。

>>233
お前バカそうだな。

クイックソートやGoogleの検索エンジンの仕様も
アルゴリズムって呼ばれているわけだが、
お前が馬鹿にしているのが何かすらわかっていないだろう？

>>233
アルゴリズムや数学をきちんと勉強しないから、人が考えたアルゴリズムをコードに起こす仕事になっちゃうんじゃ..

アルゴリズムおもろいやん

>>235
ちょっと分厚い本をペラペラ捲ったら、アルゴリズム記述されてんのに、
そんなもの後で必要になってから調べて十分じゃないの?
頻出しそうなものなんて、木とネットワークフロー、DPぐらいしか思いつかないし、
BM法なんて、生涯にわたって使う機会が一度もない気がするわ
それよかPrologで出される制約問題でも解いた方が有意義じゃねぇの

たぶん、アルゴリズムを
他人が考えたものを使うものとしか
考えてないんだろうな。

>>238
若くて情熱が続くうちに、ページランクアルゴリズムでも再発明したらいいと思うよ

>>239
アルゴリズムに期待したらいけなかったんじゃなかったのか？ｗ
ページランクアルゴリズムを発明したGoogleは凄いことになりましたよね。

皮肉を理解できないアスペと話するほど心は広くないんだ

じゃあ話をしなければいいじゃないかｗ
もうこれ以上レスしなければいい。

で、アルゴリズムをなにかわかってないから
そんなこと言ったんだよねｗ

>>237
そりゃ、CSSやPHP弄ってるだけの場合はそんなもんだろ。お前の仕事に必要なければ勉強しなきゃいいさ。

ただ、人によって勉強する動機は異なるし、どんなアルゴリズムやデータ構造があるかを大雑把に知っておかないと、必要になった時に何をどう調べたらいいかもわからんだろ。

>>237 はもっと数学を勉強して、物事を合理的に考える力を養った方がいいな。

>大雑把にしっておかないと
だから、ペラペラ捲ってからで十分なんだって。
具体的な目標もなしに、アルゴリズムなんて勉強した所で身に付かないよ
そして、おまえらには目標がないので、ぺちぱーになる

>>244の意見のほうが信用できるな。
リファクタリングにしろ、デザパタにしろ、
OOPとはなんぞやの思想にしろ、
なんかしらのアルゴリズムにしろ、
必要になるまでまずその価値なんてわかんねえんだ。

>>244
お前何言ってんだ？

アルゴリズムそのものの話だろ。
お前が言っているのは特定の場合の話であって
アルゴリズムそのもの話ではない。

>>245
リファクタリング、デザパタの方が優先度上。
アルゴリズムの勉強なんてウンコしながらで良い

寝言は寝て言え。

>>248
皆、アルゴリズムの使い方と使う場面を知らないから講釈垂れてけよ

意訳

俺、アルゴリズムの使い方と使う場面を知らないから教えてください。


返答例

だがことわるｗ

死ぬまで10万件のバブルソートしてろカス、ってのもアリかなw

ほとんどの場合、組込関数が問題領域に大して最適化されたもの提供してくれるよね？

それを適用しようとしている問題に対して最適だと判断できないバカが何か言ってるw

大体、大学生が講義で学ぶソートや文字列操作って、普通は勉強しても使わないから必要になるまで放置するよ
本当に正しいか確認するために書籍を引っ張り出すけど、
実際に調べてみるとデータベースや言語の組込み関数が問題に対して最適化されたもの提供している
少なくともソートや文字列周りのアルゴリズムは頭に入れておくだけ時間のムダ
詳細に頭に留めておくべきデータ構造もB+木ぐらいしか思い浮かばない

話がすり替わってるな。

頭にいれるのが無駄というだけで、
アルゴリズムそのものが悪いわけじゃないだろ。

クイックソートとか、多くの言語のソート機能に
使われてるアルゴリズムだし、
ソフトウェア工学の基礎だぞ。

アルゴリズムの勉強から学べることも多い。
基礎をないがしろにするもんじゃない。

優れたアルゴリズムは、今でも優れているし、
そういうのを知って、そして自分で
考えるのがプログラマってもんだろ。

NGID:rHQmp5Mm

NGしたってことはもうレス（反論？）してこないってことか。
それは嬉しいね。

この俺のレスも見えてないはずだよね。
レス番飛んでるから書き込みしているのはわかっても
内容はわからない。レスしようがないよねｗ

さて、この馬鹿どうしようか。
アルゴリズムの重要さを理解してないなんて痛すぎるね。
必要になったら意味もわからずコピペしてすませそうだね。

さっきから、あぼーんが酷いわ
童貞がセックスでも語ってるのかな

>>258 死ねや屑

さっそく、レス番飛んでるのを見つけてレスしてきたかｗ
NGしたんだからID:NcMQ7vHTには内容は見えてないはず。

ID:NcMQ7vHTってホント馬鹿だよねｗ
自分から見えなくするとか。
頭悪すぎるｗ

>>259
君ら本当にアルゴリズム一通り勉強したの？

アルゴリズムについて一切勉強せず、
「組込関数が問題領域に大して最適化されたもの提供してくれる」って信じて自爆すればいいんだよ君は。
だからもうこのスレに居る必要は無いから、消えようね。

>>261
そりゃメジャーなのはするでしょｗ
やってなきゃモグリだよ。

>>262
反例はよ?

＞高卒とか文系SE?

これでおこっちゃったんだろうなｗ

>>262
必要になってから本を開くで十分だから

>>266
だから必要になる時点で、
アルゴリズムに期待してるってことだよね。
自分で矛盾しているのわかってないんだろうね。

反論あるかい？

まぁ、ここのバカ共は、シコシコとsortやBM法を実装する経験を積んで、
その費用対効果の悪さを実感してもらいたいね

おやおや、反論はどうしたんだい？
しないのかい？ｗ

○○ソートを実装して嬉しげな子は、写経に価値を見出す子。
○○ソート実装しますた！つっても結局はそれは発明するわけじゃないんだから、
誰かが書いたソースや、手順の解説をみて、本質的には書き写してるだけ。
それで満足できるんだからほほえましい。

>>270
勉強っていうのはだいたいそんなもんだよ。
数学の勉強なんて、殆どが誰かが発明したものでしょ？

だからって数学に意味が無いことにはならないし、
もちろん勉強することに意味が無いことにもならない。

それが基礎ってもん。基礎が出来てこそ、その先がある。
ID:NcMQ7vHTはそれをわかってないんだよ。

だからみんなに馬鹿にされてる。

NcMQ7vHTの言っていることは一理あるよ

どういったものがあるか程度に知識として持つってのが前提の話だろ？
必要に迫られたら、そのインデックスを頼りに勉強すればいい

知識は使わないと直ぐに忘れるから、あれこれ頭に詰め込んでもあんまり意味ない
外部記憶装置に連想配列としてデータを置いてハッシュ値で情報を取り出す方が効率が良い

ひと通り勉強するって捉え方の相違って感じ

>>272
それ、俺が言ってることじゃん。
NcMQ7vHT はそれすら無駄って否定してたけど。

>>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弄ってる層に謝れよ。

>>270
5分以内に挿入ソートを書かないと、お前の娘がどうなっても知らないぞ
なんて、偉い人に脅されたらどうするんだ?娘の純潔が君の手に掛かっているんだぞ
コーディングが不要って考え自体は、医師免許もってる人にお腹を切開させるぐらい怪しい考え

反論できない奴に対してのワンサイドゲームって楽しいわｗ

どうせ見てるんだろうけどさｗ

>>273
うん、君の>>235のレスに対して>>237の返答があるけど
言っていることは同じだよ
どういったものがあるか知らなきゃ、調べようがないもの

>>274
必要のないアルゴリズムを
親父のラジオを分解してまた組み直すように
分析しまくっても、満足はするけど、さほど身にならないよ

必要なければ物語のあらすじを知っておく程度でいいんだよ
NcMQ7vHTはそう言っていると捉えたけど

アルゴリズムを勉強する意味としては、
優れたアルゴリズムをつかうことによって、
計算量が劇的に減るってことを簡単に体感出来るやん
それだけでも楽しくね？

アルゴリズムの理解に対して、競技コーダーレベルを目指すか未満でいいか
のどちらかで、んなもん目指さなくて良いなら本開いてからかウンコしながらで十分
このスレの人たちはアルゴリズムが重要だってわりに、何がどう重要なのか、
そもそも何に使うのかの具体性すらないのにアルゴリズムが重要っていう。不思議。

具体性があれば、アルゴリズムは重要って言ってるんだよ、こいつは。
みんな気づいているよね？

童貞って使いもしない性知識や性技について、やたら詳しいよね
それも何か過度の期待をして悶々とムラムラしている。
あぼーんした箇所から我慢汁が垂れてきそうだ。

自己紹介乙ｗ

>>271
なんか話がねじれてるのを感じるが一点だけ。
…と思ったけどやっぱいいわｗ　やめとく。

>>275
わろたｗ

アルゴリズムに興味ある人はトップコーダへ　ステマ

php.iniを笑うものはphp.iniに泣く

漏れは今、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!

蟻本いいよね。大学生のうちに熟読したかったわ

スレが進んでると思ったら、狂人が二人居ていちゃいちゃしてたのか

どう見ても一人

アルゴリズムとデータ構造ならやっぱこれが今でもベストだと思う
http://www.amazon.co.jp/dp/4000103431/

日本人だから意味不明の翻訳調の文章に悩まされることもない。
説明が丁寧。ひっかかりやすいミスもあれこれ解説しているのが親切。
もっと評価されてもいいと思う。

ベストと言い切る自信は無いが、確実に名著だね。

0-9の数字をランダムに並べ替える、
トランプのシャッフルなど、
重複しない乱数列を作るのは、
どんなアルゴリズムがありますか？

Webにあって良さそうなのは、
最初に配列に、0-9を入れておく
1. 0-9から1つの乱数aを得て、配列[a]と[9]の要素を入れ替える
2. 0-8から1つの乱数bを得て、配列[b]と[8]の要素を入れ替える
以下同じ

>>293
それでいいんじゃないの？
O(n)で乱数配列作れるから一番速そうだし

c++STLのrandom_shuffleだっけ
これもそれ使ってたと思う

アルゴリズムの検証に使えそうなある程度大きなデータのサンプルが置いてあるサイトってないかな？
今は特に重み付き有向グラフのデータが欲しいんだけど。
なんなら、有料でもいい。

Wikipediaの全データ落として、リンクをエッジ、文の長さを重みにでもすれば

>>295
http://algs4.cs.princeton.edu/code/
の largeEWG.txt とかはどう?

>>295
http://elib.zib.de/pub/Packages/mp-testdata/tsp/tsplib/tsplib.html

>>296
アドバイスはありがたいが、申し訳ないが今はちょっと非現実的かも。
面白そうではあるから、暇ができたらトライしてみるよ。

>>297 >>298
使えそうだ、助かった。
ありがと。

一括データをまとめて落とせるんだよ。https://ja.wikipedia.org/wiki/Wikipedia:%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9%E3%83%80%E3%82%A6%E3%83%B3%E3%83%AD%E3%83%BC%E3%83%89

>>300
これは凄い。知らんかった。

２Ｄ上の多角形を検出するアルゴリズムで詰まりました。助けてください。
各ラインを　56,80-120,100　という２頂点のデータで複数持っています。
とある２Ｄの座標が多角形を構成しているラインの中か外かをチェックする必要があります。
中か外かをチェックする処理は作成したのですが、そもそも多角形を構成しているのかどうなのかという処理で、
良いアルゴリズムが浮かびません。
多角形の頂点数は３点以上です。
何か良いアルゴリズムは無いでしょうか？

追加です。
各ラインの交差はありません。

共通する頂点を探して辿るとかじゃだめなの？

>>304
ありがとうございます。
頂点ＡＢＣＤＥＦＧと頂点ＢＣＤＥＦＧＡは同じなのですが、チェックがめんどくさくて、、、
閉じているかチェックしたいだけなので、力技ではなく何かテクニックがあったら教えていただきたいです。

どんどん条件後出ししていきそうな質問者

条件出さないんで、助けてください＞＜
あえて出すとすれば、同じ頂点を共有した別の多角形が存在するという条件でしょうか。
条件出しちゃいました。。。

頂点データを持っているオブジェクトが必ず多角形になるなら
そういうデータ構造にしたらいいんじゃないの？
三角形なら頂点a、b、cのデータを持って、一筆書きみたいにa-b、b-c、c-aのライン判定する
ラインデータじゃなく単純な頂点データとして持てばデータ量も減るし

多角形にならない場合があるならフラグでも設けて
最後のc-aが閉じていないってすればいいんじゃないの
どのラインも独立しているのが必要ならそれぞれオブジェクト生成したらいいんじゃない？

>>308
ありがとうございます。
難しそうですね。。。
実装時間に制約があるので、１頂点から２線以上出せないという仕様を一つ追加して乗り切りたいと思います。

>>309
多角形は結局のところ多角形の集合なのだから
最低単位の多角形をグループ化するクラスでも作ったらいいんじゃない？

例えば、正六角形は正三角形が6つ集まっているよね
最小単位の正三角形のオブジェクトを6つ持つ正六角形クラスがあればいいよね
当たり判定はそれぞれの正三角形で行なえばいいよね

それを一般化してしまえば、1頂点から2線以上出る多角形も作ることが可能だよね
それが3Dとかで使われるポリゴンだと解釈しているけど

多角形はワイヤーフレーム型？
多角形が単一色、または背景が単一色で多角形部分が色付きなら楽だけど、たぶんそれじゃあ駄目なんだろな

ワイヤーフレームなら、指定座標から画面外枠に向かって上下左右に1ドットづつ色検知して、上下どちらも、または左右どちらも画面外に出る前にに多角形枠色に引っかかったら内側判定…とかは？

あ、内側判定は終わってるんだな
ごめん、忘れてorz

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-12-skip-lists/

↑の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を求めよ。

>>313
各項をかけるとx(n)がいかなる値であろうとも常にA
積が一定のとき、各項がすべて等しければ最小

とかいう問題ですか？英語よめないからよくわかりません

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.

>>313
どこが分からないの? >>315 のところ？

相加相乗平均の定理

アルゴリズムの勉強は本当に疲れる
センスのある人はアルゴリズムがスラスラ理解できるらしいが、俺は頭が悪いのでウンウン唸りながらじゃないと理解できん

それでいいと思う‥‥

俺ハノイの塔とか未だにわからんわ
追っていると頭が混乱しちゃう

センスというものなのかどうかはわからんが、
機械の「機械のように正確な」動作を追うことができるかどうかは、
デバッグの効率には影響すると思う。この仕事に対する向き不向きとして。

再帰をわかってる人は、大半のアルゴリズムに強い気がする

再帰は確実に終了する根拠がないと使いにくいんだよな。

ループは確実に終了する根拠がないと使いにくいんだよな。
チューリング完全は確実に終了する根拠が無いと主張できないよな。

>>323
再帰を使う上でその根拠を決めるのは自分でしょ

>>323
再帰の頭に終了条件を書くでしょ、そのときに否が応でも自分で決めざるを得ない

再帰の頭に書くのは終了条件じゃないよ

>>327
ありえない、お前は再帰をもういちど勉強したほうがいい

多額な借金で人生つんでるヤシたちw


http://manta.blog.jp


http://livedeaichat.blog.fc2.com/blog-entry-1.html


http://sisutore.blog.jp/archives/1000786211.html

>>327
じゃあ、今日からは、再帰を書くときは真っ先に再帰を終了させる条件を定義するようにしましょうよ。

再帰は、内部的にはどーなってるんだ？
アーキテクチャの本を読んでも理解できなかったわ

>>331
マシン語勉強すれば？

再帰とマシン語はあんまり関連性ないだろ。

つーか終了条件が成立するまで自分自身を呼び出すだけ。
たったこれだけ。単にループを再帰で置き換えるだけなら
簡単。データ量が不定だったりする場合は一定の量だけを
切り出して、そのブロックに対して再帰にすればいい。

内部的にどうなってるか知りたいってことは、引数やローカル変数が上書きされないかとか、どうやって元の場所に戻るんだろうとかが疑問だってことでしょ。
自分は、関数呼び出しがマシン語では引数や戻りアドレスをスタックに積んで関数の先頭アドレスにジャンプするコードになるのを知ってたから理解できたけど、そんなのは老害だって言うなら黙るよ。

実装の話だろ、あってんじゃん

この関数が老害ってどういうことなんでしょう

mkdir himitsu
cd himitsu
ln -s . himitsu

chown oh:oh himitu

・ポインタ
・再帰
・リンクリスト

辺りがダメな人は本当にわからないらしい。
数学科でもダメな奴がいると聞いた。

どう突っ込めばいいんだ？

ほんとだよなｗ

ねじ込むように突っ込む

そんな奴等はメモリモデルとかアドレス空間から教えないと

還元的な方法以外でも理解可能です。

>>344
チューリングの計算可能の話にまで遡るのか・・・
大学レベルだけど、講義でもないのに教えるの面倒くさいなあ

なんでやねん

数学科って、cでプログラム書くようなことあるのか?
6年ぐらい入門して、最終的に触る機会なんてなかったぞ

まず日本語を勉強してだな

>>349
サクラ鯖に、なでしこでCGIでしょうか?

↑のレスは天才チンパンジー「アイちゃん」が
言語訓練のために書き込んだものです。

アルゴリズムの勉強というのは、整列なり探索なり自分でキチンとコードが書けるように
なれば一応完成とみていいですか？

初級アルゴリズムならそうかもな

中級・上級アルゴリストにはどんなことができるの？

実際に何か作ってるときに「こういうアルゴリズムがあるはずだ」と察知して
探せるようになればおｋ

中級は学部・院生レベルくらいかな

既存のアルゴリズムの改良をしたり、
目的に沿ったアルゴリズムを開発したり、
その計算量やメモリ量を算出・証明したり、
実装したり、論文で発表したりする

アルゴリズムはデザインがすべて

>>352
違う。

それを勉強し始めた時に思い描いた未来の自分になれば完成だ。
目標もなくただなんとなく勉強しているのなら、完成なんて永遠にこない。

あと、「一応」なんてものも無い。

algorithmの問題に関する作業能率を最大まで上げたら、
らいなっくすやれいるずを作れるようなすーぱーはっかーになれますか？

>>352
蟻本嫁

>>359
なれるわけがない。

ウソだと思うなら、実際に効率最大まで上げてみればいい。

>>331
末尾再帰最適化、継続あたりで検索。

>>356
高卒なのか?

>>153
>ただし、if 文で n 回の比較が発生するから、n があまりに大きい場合は >>152 のやり方がいいと思う。

元のお題がI/Oなんで、この程度の比較命令は全く問題にならない。
わかりやすく書くのがいい。

最近はCPU速いんでネイティブじゃなくてjavascriptが流行ったり
最適なアルゴリズムより線形検索とかでも充分だったり

うむ。今個人のPCで使われているDDR3-1600だと
転送速度12.8GB/sだからね。

0.01秒だと人間が知覚できるかどうかの世界だけど
その時間があれば100MBのデータを探索できるわけだからね。

最近のJavascript JITはネイティブより速いことも多々ある。

涙ぐましい努力をするより富豪的プログラミングが流行る時代だしね

それでもリソースに限りはあるわけで、大きいのだとどっかで破産するんだよな。
富豪的プログラミングじゃなくて、成金的プログラミングだと思うよ。富豪ってのは
周りが無駄に無計画に使っているように見えても、実際は締めるところは締め、
使うところは使うっていうのだからな。

リソースがショートしちゃうもんな

どこがどう大きくなるのかを見積もって、必要なとこを必要なだけ節約する、って形が有効。
必要以上の節約は労力の無駄使い。

firefoxで動画再生してると
メモリ解放されなくてそのうち死ぬ
成金の糞flushのせい

UFC 128 - エリック・コク vs. ハファエル・アスンサオ
https://www.youtube.com/watch?v=n2CcU1A1i-0

>>372
一般的に、I/Oなどは、1MBほどのバッファを確保して、
バッファに読み込んで、再生などの処理をしたら、
処理したデータを捨てて、次のデータを読み込む、
シーケンシャル・アクセスで、バッファのサイズは大きくならない

そのブラウザは、もう一度再生するときに、
ネット回線からダウンロードせずに再生するために、
データをローカルのメモリかディスクに保存しているんだな

データを捨ててないから、最後にはメモリが確保できなくなるので、
もう一度見ないものは、タブを閉じたらいいのでは？

１．中置記法を入力すると逆ポーランドに変換し出力する
２．逆ポーランド記法で入力するとそのまま逆ポーランドで出力する

の両方できるアルゴリズムはありませんか？

１．は操車場アルゴリズムでできるようですが、
操車場アルゴリズムだと２ができません。

>>375
中値記法と逆ポーランド記法を識別する方法が知りたいって事？

>>376
はい、そうです
識別方法はありますか？

>>377
末尾だけを最初に見れば良いんじゃね？
逆ポーランド記法の場合、必ず最後は演算子で終わるから。
但し、一番外側にカッコがある場合は、一度取り除いてから末尾を見ないといけないね。

俺がやるなら、まず末尾から文字を順に見ていくかな。
カッコだったら次の文字に移動。
数字が先に現れれば中値記法。
演算子なら逆ポーランド記法。

ありがとうございます
末尾判断でやってみます

f

俺は頭からやりたい

頭で再帰しちゃったら無限再帰で _|_ やぞ

どして？
いま旅行中だから帰ったらやる

ttp://www.younganimal.com/se/img/02.jpg
ttp://www.younganimal.com/se/img/03.jpg
ttp://www.younganimal.com/se/img/04.jpg
ttp://www.younganimal.com/se/img/05.jpg
ttp://www.younganimal.com/se/img/06.jpg
ttp://www.younganimal.com/se/img/07.jpg
ttp://www.younganimal.com/se/img/08.jpg
ttp://www.younganimal.com/se/img/09.jpg
ttp://www.younganimal.com/se/img/10.jpg
ttp://www.younganimal.com/se/img/11.jpg

続きはよ

続き見てきたけど、デザインパターンが分かって書いているとは思えないところがなんとも。

続き読んでないけど、オカマなんか？

いや、オナホのソフトを作っている会社の社長。
ハードの話をすっ飛ばしていきなりオナホ界のジョブズだとかw

さて、短い旅から帰ってきた
頭からの再帰、明日にでもやろう
その前に
頭からとか、末尾からとか
末尾再帰に関わる意味で言ってるんか？
おれは算術式の頭から見ていく
という意味で言っていたが
それにしてもなんでこんな簡単な問題が！
初心者の俺は根本的に問題を誤解してるのか？
ま、いいや、明日には書いておく

>>390
少なくとも>>378で言ってる末尾は、再帰の話なんて一切してないよ。
単純に数式文字列の最後の文字と言う意味ね。

>>375
課題では中置を逆ポーランドにだったけど、アルゴリズムの都合上、
中置もポーランドも逆ポーランドに変換(無論、逆ポーランドはそのまま)

また、各種記法の混在を認める
((1 + (* 3 5)) (8 - 2) (2 5 expt) +)
でもよし

方針　式の頭からワンパスで変換を終了する

使用言語　Scheme

http://codepad.org/Ogp2Lzwh

>>392
どひゃ！
>>392は変数と演算子を区別していない！

式の計算ではなく
式の変換だけの課題だった！

もう、変換だけでなく計算してしまう過大なら楽なのに！
（今日は寝る）

(number? x)のところを
(number (eval x ()) )にすりゃいいな

>>392
式に変数も認めるバージョン
演算子情報はは演算子データベースに保持

http://codepad.org/c65AyXpd

気持ち悪い

あはは
ゲロはいてろ

再帰プログラムを非再帰プログラムに変換する方法が理解できません。

たとえば、フィボナッチ数列を再帰的に計算するプログラムを
スタックを使って非再帰的に計算するプログラムが野崎昭弘さんの
本に載っているのですが、何度読んでも理解できません。

どうすれば理解できるようになりますか？

たまたまそのコードと自分の相性が悪い、といったようなことはあるから、
他の例をさがしてみたら？

>>398
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ループで求めればよい

具体的には、これを見ろ
http://codepad.org/vdi9qyqK

フィボナッチを再帰的じゃなく求める方法についてじゃなくて、
再帰的なコードのループへの変換がわからない、ということでしょ。

ん？スタックを使いたい？プッシュしてな、いきついたら、ポップするんだよ

>>400
まあ再帰は基本的に遅いけど、メモ化すればずっとマシになるし(震え声)
C++で書いてみたサンプル↓
http://codepad.org/HgtP5slM

>>401
まあフィボナッチは末尾再帰(非再帰型にしやすいもの)の中では定番ですし……
そうでなくてもスタックが使えれば原理的にはなんだって非再帰にできるはずだが
http://ja.wikipedia.org/wiki/%E6%9C%AB%E5%B0%BE%E5%86%8D%E5%B8%B0
http://www.math.kobe-u.ac.jp/~taka/asir-book-html/main/node67.html

>>404
ではAVL木や赤黒木（二色木）を非再帰に書き下ろしてみてくださいな

>>405
「原理的に」つっただろ……なぜお前の代わりにそんな面倒なことする必要がある？

>>406
できないのですね

煽っても何も得られないと思うぞ

ということにしたいのですね

CPS変換すればなんでもGOTO

関数呼び出すは引数をスタックに積んでｇｏｔｏしてるんだものな。

呼び出した場所の情報もスタックに積まないと戻れないぞ

それも引数だと思えばいい。

ていうかCPS変換てのは、戻らない形にするプログラム変換だから。

「継続」だな
引数だけ渡しても再開できるとは限らんから

「再開できる」とはスタックは一本しかないことを認めているようなもの

アクティベーションフレームはスタックである必要性ないから

こっちもよろしく

アルゴリズムとデータ構造について語ろう
http://ai.2ch.net/test/read.cgi/math/1379334483/

a=a+1 を解釈する時点で混ぜるな危険

とっつきやすいスレはここ。数学板は基本的に過疎なので遊びにきてほしい

P vs NP
http://ai.2ch.net/test/read.cgi/math/1344808587/

>>419
呼ぶな

>>398
再帰の技法　基本的考え方・アルゴリズム・プログラミング
http://www.amazon.co.jp/dp/4434085972/

この本良いよ。
階乗、フィボナッチ、ハノイあたりから始まって再帰を使った問題を解説している
もちろん再帰をループに書き直す考え方とかも入ってる

再帰だけ取り上げてる本ってありそうでなかったけど、苦手な人はこういう本で
一度基礎からちゃんと勉強した方が早道だと思う

俺は買わないけど言語は何使ってるの？
アマゾン見てみたが書いてなかったな、使用言語

表紙に書いてあるけど
中身もそれかどうかは不明

なか見検索で見た限りは純粋なCだよ
でも索引まで入れて140ページちょいって少なすぎないか？

なかみで見れた
もうおなかいっぱい

C言語で再帰の本かい
そういうのもあるんだなあ

>>422
そのページの表紙の写真の下にある
[この本の中身を閲覧する]をクリックして出てくるサンプルの3ページ目の下から3行あたりに
「この本ではC言語を用いてプログラムを示すことにしますので、読者はC言語の知識があるものとします。」
と書いてあるぞ。

>>427
× サンプルの3ページ目
○ サンプルの2ページ目

お前ら何か紹介されるととにかくまずけなしまくるよな
読んでさえいなくても

>>427
さんくす、見てきた
もう、お目目キラキラ一年生のために書きました！って言っていいくらいに丁寧にゼロから書いてる感じだった
「再帰？わかんねえよ」
「再帰の本ってリスプとかだろ？
べらんめえ！こちとら江戸っこでぇ、カッコカッコでコケコッコーじゃ埒が明かねえ！」
とか思うがヒトにはいいかもね
(俺は買わないけど)

(フリックで打ってると誤変換ふえるなあ、慣れなきゃ)

うぜえ

じゃ、しんでろ

NGNG

>>429
べつにいいんじゃね、挨拶みたいなもんだよ

毎度のことなんで紹介する方もわかってるでしょ

>>421
void main() だと？！

>>436
VSなら間違ってないから(震え声)
それに定説は「void main()な入門書は大概糞」ってだけだし

> なお、C/C++の言語そのものの解説ではない書籍、例えば圧縮アルゴリズムに
> 関する書籍に void main() のような記述があったとしても、その書籍の有用性とは
> 直接関係ないので、大目に見てあげてください。
http://www.kijineko.co.jp/tech/superstitions/void-main.html

ttp://www.youtube.com/watch?v=FbqCbc7tFZg
総務省、「データサイエンス」力の高い人材の育成進める方針

組み込みを長くやっていた人なら
void main()とか、無限ループしてmain()から抜けないとか、
日常茶飯事の感覚だろうな。

gotoも日常茶飯事だな

組み込みは"hosted environments"じゃないことが多いからな。
"free standing environments"ならmainは必要ない。ある時の型も任意。

437のリンク先の要約をありがとう

まあ C はオールマイティーだからな‥実装がすべて規格なんて糞食らえ

つまり組み込みプログラマーは知的底辺ということか

動きゃいい！の匂いがプンプンする

実際、動きゃイイよっての多くないか?
単価が高めの案件ほど特にｗ

コードレビュー無し。
テスト仕様は徹底的だが

高給な現場ほど、なぜかやり方を突っ込まれない。
悪意をもてばやりたい放題出来る。費用も言い値。
まあ悪意はそうそう持ち込めるものじゃないが。

多分STAP細胞の現場もそうだったんだろうな、と想像出来る。

組み込み系のひとのソースは汚いのが多いよ
ほんと動けば良いのノリだけで造ってる
もちろんまともなひとがいない訳じゃないけどね

>>448
一番最初のソースがひどいとダメだよね
次からはちょっと変更する工数しかないから、みんな割り切ってそのまま変更
まともな人は黙って or ダメソースをなんとかする工数うんぬんで上司と揉めて辞めてしまう

ハードウェアが仕様通りに動くかどうかわかりません、もしくは仕様ありませんって世界だろ?
ソフトウェアも相当部分が使い捨てだよね。完全にスレ違いの話題。

しょうがない

>>450
へ？ハードが完全とはいえんから
ソフトも適当でいいっていっるのか？

じゃ、馬鹿だ

組み込み系のニンゲン
だめな奴おおすぎ

のりじゃ作れんよ、凍死老

>>448
組込みに限らず、出来る人は2chなんかに来ないだろ。

クロック数単位の動作速度保証組み込んだ高級言語ってあるんかいなとふと思った

エミュレータでカウントします。

機能実装の作業がいつのまにかハードの不具合調査になってたり、
結果、ソフトに柔軟でかつ早急な対応が必要になるし。
クラス設計とかやった方がいいのかもしれないが、2の次になるとかそういうことだと思う。

組み込み系は、ハード屋に使いまわされてて気の毒に思うことも多い。

そりゃハード屋からみりゃ組込み君は奴隷
ハードのために仕事しろ！
だし
アプリのためのOSのためのハードじゃないからな

このように、スレ違いであろうと自己憐憫の機会は決して逃さないFW屋であった。

整数x, yの範囲内で
z個の重複しない乱数を発生させるためのアルゴリズムはどうしますか？

【例】 x=100, y=200, z=5だと、121, 129, 142, 189, 195みたいなのを返す(当然y-x+1>zである必要がある)。

>>462
xからyまでの個数の配列作って乱数でシャッフル
先頭からz個取得

でいいんじゃないの？

>>463
シャッフルはオレのプログラミング哲学に反する。
先頭から取得するとどうしてても最初のほうの数が選ばれる確率が高くなるのは避けられない。

int a[z];
r=y-x+1;
for(i=0;i<z;) {
a[i]= x + 乱数生成(r);
for(j=0;j<i;j++) {
if(a[i]==a[j]) break;
i++;
}
}

>>464
>先頭から取得するとどうしてても最初のほうの数が選ばれる確率が高くなるのは避けられない。
根拠は？

z個取得する位置もランダムで選択してもいいんじゃないの

取得位置がランダムならシャッフルする必要ない。
シャッフルする必要なければ配列に入れる必要もない。
選んだ配列のインデックスが重複すれば無視しなければいけないのだから>>465と何ら変わることはない。

>>467
配列からz個読み出す初期位置を先頭からズラすって意味なんだけどね

オブジェクト指向は愚かな考え。
http://peace.2ch.net/test/read.cgi/tech/1393660194/

例えばFisher-Yatesシャッフルすればコスト少なくいい塩梅にシャッフルできるから、
(と言ってもzでなくy-xのオーダーになるので、
オーダーは変わらないものの>>465よりコスト安になることはない)
>>464の懸念もあまり意味は無い。

しかし仮にちゃんとシャッフルできてないのでは?って懸念を認めるとすると、
最初の方だけ偏りがあるという変なシャッフルをしない限り、
どこから取っても偏りがあることには変わりない。
そういうわけなんで>>466は修正案の部分がおかしい。
「根拠は?」のところはいいんだけど、良いシャッフルアルゴリズムを挙げられればもっと良かった。

>>462
こんなかんじかな。
先頭から、それぞれが選ばれる確率をきちんと設定して、
すべて等確率になるようになってる……はず。
検定は自分でやってくれ。

void
choose(int x, int y, int z) {
int i;
int n = z;
int d = (y-x+1);
for (i = x; i <= y; i++) {
if (n/d の確率で真) {
printf("%d ", i);
n--;
}
d--;
}
}

あ、すまん。ぜんぜんちがった。
忘れてくれ。

>>470
xとyに大きな隔たり、つまり配列が大きい場合、最終的にz個取り出す位置にもランダム性があれば
よりランダム性のあるz個の列を何度も取り出せるって意味合い程度だよ、思いつきだよ

シャッフルでありがちな実装ってこんなんかな
乱数生成エンジンが質の良い物ならこんなんでいいと思うけどね

int size = 10;
int a[size] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

for(int i=size-1; i>0;i--)
{
int j = rand()%i;
swap(a[i], a[j]);
}

>>462
こうだ。
dCn はコンビネーションな。d!/(n!(d-n)!) のこと。

void
choose(int x, int y, int z) {
int i;
int n = z;
int d = (y-x+1);
for (i = x; i <= y; i++) {
if ( (d-1)C(n-1) / dCn の確率で真) {
printf("%d ", i);
n--;
}
d--;
}
}

>>462
一応突っ込んでおくと、それを乱数とは言わない。
乱数を加工して得られる数列。

１−１００の乱数で、重複しない乱数って重複が許されている乱数より、より
乱数じゃないよね。だって、後の方になるほど次に出る数に制限があって予想が
つくわけだし。
99個目の次は100％当てられる
そんなの乱数って呼んで良いの？　数学的に。

乱数として考えるのは「幾つかの数からなる集合」としてであって、
「集合に含まれる個々の数」では無いのだが。

さっきから馬鹿なこと言い続けてる奴がいるな。

>>477
それは乱択

>>476
そうだよ
それは乱数じゃないよ

順列の集合から1個をランダムに取り出すんだと解釈すれば乱数やね
>462の設問は言葉足らずかもしれないが、意図は通じるでしょ

N回目の試行がN+1回目の試行に影響を及ぼしてはいけない
>>462 は ambiguous だから知らんが
>>476 は乱数ではない
>>480 は
順列の集合から1個をランダムに取り出す
の後で1個をもとに戻せばよい

>>481
その定義だと、線形合同法は乱数じゃなくなるね。
線形合同法を禁止するわけにはいかないのだろうか。

影響って言葉の意味がズレてる。

「箱の中から1個取り出して元に戻さない」方式の場合は、取り出す前は 1/N の確率だったものが、
1/(N-1) の確率に変化してしまう、ということを言っている。

決定的である、という意味では、線形合同法に限らず、真の乱数でない、あらゆる疑似乱数が
決定的だから、線形合同法だけ槍玉に上げるのはおかしい。

馬鹿な476の話題を引きずらなくて良いよ

>>482
線形合同法はN回目に取り出された物がN+x回目(xは1から周期の長さ)に取り出される確率は0じゃん。
線形合同法は「箱の中から1個取り出して元に戻さない」方式だよ。
481=483だとすると主張がよく分からない。

>>485
その理屈では、M系列だろうがMTだろうがXORShiftだろうが、ありとあらゆる方式に同じことが言える。
単に状態空間が、線形合同法は通常32ビットぐらいで、MT19937の場合は19937ビットある、というだけ。

>>462はhashmap使えばO(z)までに効率化できるな。

>>486
ありとあらゆる方式なんだ?
まあそれは置いといて、481=483だとすると主張がよく分からない。
どういうものなら乱数なんだ?
線形合同法やM系列は違うわけだね。
これは「箱の中から1個取り出して元に戻さない」方式というのを
否定はしてないようだし。
何か詳しい人かと思ったんだけど、違うのかな。

極端なことを言えば、決定的な（つまり、普通の）擬似乱数列は、
決定的なんだから、箱の中からどれかを選んで取り出しているのではなく、
ただ単に一列に数が並んでるだけ。

この説明でわからないなら消えろ。

>>489
あれ?
線形合同法は「箱の中から1個取り出して元に戻さない」方式ではないという主張なんだ。
線形合同法はN回目に取り出された物がN+x回目(xは1から周期の長さ)に取り出される確率は0で、
ただ単に数が並んでるだけではないんだけど。
それ(確率は0ということ)は決定的かどうかとは無関係。

主張がよく分からないので自分ではっきり言って欲しいんだが、
「箱の中から1個取り出して元に戻さない」方式は乱数でなくて、
線形合同法は乱数だと言っている?

線形合同法は乱数じゃないよ

厳密には乱数じゃないから擬似乱数なんでしょ？

はっきり結論出てしまうとつまらんな

では聞くが、完全な乱数列ってのはどうやったら手に入るのだ

専用ハードウェアが必要だね。

> 主張がよく分からないので自分ではっきり言って欲しいんだが、

おまえが何を言っているのかよくわからない。
ていうか、自分がわかってないだけだろ。

シードを作るだけじゃなくて、量子揺らぎとかで完全な乱数を作るハードってないの？

>>495
AVX 以降は「専用ハードウェア」が入っているらしい
http://peace.2ch.net/test/read.cgi/tech/1192628099/337

random_device

同じ数字が二回連続で出る可能性が0%
ってのは乱数じゃないよな
どう見ても

だから「擬似」乱数なのだと何度いえば

「乱数らしさ」の検定のひとつである誕生日検定では、線形合同法は成績が低い、と。
それだけの話なんだが。

もしかして前にオレオレ生成系を自慢しようとして壮大に自爆していた奴か？

乱数デバイスも「乱数」ではない。

ラプラスの魔ですね分かります

乱数という呼び方は無機質でいやだな。
出来れば淫数と予備隊。

賛成

淫らと濫りと乱れは違うぞ。

ハノイの塔のアルゴリズムがどう考えても理解できません。
誰か分かりやすく説明してください。

>>509
そんな解説サイトは山ほどあるので、
ググって10個くらい熟読してから、
それでもダメなら諦めましょう

>>509
再帰を使わない方法なら判る？

>>509
机の上に500円玉と10円玉と1円玉を積み重ねる
Nが3の場合のプログラムの動作と比較しながら動かす

つーか、再帰を使ったほうがわかりやすいだろ。
たいていのプログラムは、正解ありきで上の円盤から動かす前提で書いてあるから、
それを直接理解しようとするとわかりにくい。

棒を 1 2 3 として、塔を 1 → 3 に動かしたい、とするだろ。
すると、その手続きは次のように分解できる。
・ 一番下の円盤を除く塔を 1 → 2 に動かす
・ 一番下の円盤を 1 → 3 に動かす
・ 残りの塔を 2 → 3 に動かす

これで、動かす必要のある塔のサイズがN-1になったわけだから、
これをどんどん再帰的に適用してゆけば、円盤だけを動かす手順まで
分解できる。

こんどベトナムのハノイへ旅する予定です。
が、いま話題のハノイの塔、あるいはそれに関連する塔はハノイのどこにありますか？

無いけど、そういえばなんで「ハノイの」塔なのに、日本でよく言われている「伝説」だと、
インドのベナレス（ワーラーナシー）にある、という話になってるんだろう。

>>509
その感想はほとんど理解している。
再帰の計算力に気づいているわけだから。

連立一次方程式じゃん

誤爆失礼

最終局面から、さかのぼって考える
最終局面Cの1つ前の局面はB、その前はAなら

A(B(C))
これは、Aを呼ぶと、Bを呼んで、Cを呼んで、
Cが処理され、Bが処理され、Aが処理される

呼ぶ順が、A→B→C
処理される順が、呼ぶ順の逆で、C→B→A

ゲーム木でもよく出てくる
最終局面を取れば勝つ場合に、
いきなりCへ持っていくのは、難しいので、
その前の局面Aを目指すとか

処理する順はF{ DO; F(); }なのかF{ F(); DO; }なのかによる。

http://qiita.com/kenokabe/items/41189c45001321c9e283
Swiftで脱アルゴリズム！
iOS開発を関数型（宣言型）プログラミングへパラダイムシフトしてみる【脱アルゴリズム宣言�@】

>>521 チューリング-チャーチの提唱について256年勉強してからまた来いやヴォケ

>>522
おまえ何様？
反論あったら表から具体的にどうぞ？
多少オーバーなレトリックはあったものの、内容にはなんら矛盾はないね
好評だったし、お誉めのメールも何通か頂いたが？

> お誉めのメールも何通か頂いた
本人かよ。

みなさんに通告です。
このスレには「毛の壁」と呼ばれているバカが常駐しましたので、
しばらくレスにはご注意ください。

>>521
関数型プログラミング(によって書かれたコード)とかアルゴリズムの最たるもののひとつじゃねえか

これがご尊顔だ
https://avatars2.githubusercontent.com/u/1316994?s=460

>>521
言ってることは至極真っ当だと思う。
なかなか国内にはここまで書ける奴は居ないね。

>>521
ツッコミどころはいくつかあるけど、
軽いノリで書いた記事だと思えば些細な事柄だろうし、
よくできていると評価していいレベルだと思う

自分としては、FRPに関する非関数型言語プログラマ向けの
記事を見たのは初めてだったし、
現時点でのFRP入門からSwift/iOS上のアプリケーション開発へと
どう内容をつないでいくのか？という、
著者のプログラミングと文章執筆の能力に興味がある
もし最後までたどりつけたなら、評価も大絶賛へ変わるかもしれない
期待している

>>521
へ？これが？
絶賛、、よくかけてる？

どひゃあー！！！！！！

脱アルゴリズム！！！

精神病やでぇ

脱アルゴリズム？
へ？
へへ？
へへへのれれれ！

http://peace.2ch.net/test/read.cgi/tech/1403215505/18

// 一つ書き忘れていた

どうせカキコするならこのスレじゃなくて
この板か新Mac板のSwiftスレにすれば
スレ住人の反応も違ったものになっていたと思う

わかったから後はこっちで。
http://peace.2ch.net/test/read.cgi/tech/1403215505/l50

ガリバーやってるぞ、見てないけど

おまえらは頭いい風の馬鹿
数学やれ。出直してこい
岡部健さんの真意をなに一つ理解してなかったことがわかる
まあ無駄だろうけど

>>534
>>532

脱アルゴリズムの時代にこのスレは時代遅れすぎるよな。
原始人かお前らは？

脱アルゴリズム！
ぷぷぷ

なんちゃってギークが本物のギークに嫉妬か
おまえら、「数学やれ」。

その人のgithubのコード見てからほざけ

ギリシャ人がどうかしたのか？

>>538
ぷぷぷ

>>539
精神病だと見抜けない、三流君、乙！

岡野っての、愚かしくも顔写真出してるだろ
本人歯カッコイイとおもってるんだろうが
ありゃ、露骨に精神病の写真

特徴は線源した世界を、それのみがありうる世界とみなし、演繹的帰結は、それまた直ちに世界そのものとかみなすこと

アホさらけ出しのアルゴリズムの独善的定義と、そこからの演繹
もろそのものズバリ

もし
>>528が、本人の自演でないなら、そのあたり把握できん同類じゃないか？
要するに、精神病か形而上頭のオバカさん

×線源
○宣言

パンツ脱いでクソをする手順もアルゴリズム。間違えると大変なことに

むしろ
プロトコール
と
ルーティーン
だな

>>536 >>537

え？何？脱糞がどうしたって？

歌舞伎町で脱糞事件があったな

おい、脱アルゴリズムの人の言い訳エントリ来たぞ
ttp://qiita.com/kenokabe/items/821ce4020644372b648c

わきゃきゃ、やっぱり岡部っての精神病だろ
ネットでの批判に対して、ねちねちと記事の中で攻撃してるのが笑える
要するに形而上学頭で馬鹿ということ

>>549
ガチで関数型やreduceやmapはアルゴリズムでないと思ってたのか
真性だったとは

こっちでやれ
http://peace.2ch.net/test/read.cgi/tech/1403215505/l50

言語により吸収されているかどうかの違いって話だけで
ここまでアレコレ記事をかけるってのは一つの才能だな

>>549
コイツここまで言われて自分がアホだってまだ気付いてないのか

>>549
うーむ

>>549
この人のTwittersickuserという別ブログ読んだけど、
精神的にアレな人なんじゃない？？

こっちでやれ
http://peace.2ch.net/test/read.cgi/tech/1403215505/l50

そんなに怒るなよ、毛。悪かったよ。
昨日から突然500人ぐらい閲覧数が急上昇したのは確かに俺が宣伝したことだけど、
お前は自分の書いたことに自信があるんだろ？だったら宣伝してやったようなもんだ。怒るなよ。
あと、俺だけに切れるな。月琴さんにも怒れw

staticおじさん並にヤバイな

これからは脱アルゴリズム。

これからしばらくは脱アルゴリズムをNGワードに入れましょう。

脱毛アルゴリズム！
はずかしい

僕の毛根も閉鎖されそうです＞＜

>「アルゴリズム」とは「バズワード」であり、「一般的に命令型プログラミング
>パラダイムを指し示す」のであり、その他の使用は一般的ではない、ということです。
勉強になるな。

>>564
あほ

脱毛の人は一人アホの世界を生きてることがよく分かる一文だ。

http://qiita.com/kenokabe/items/821ce4020644372b648c

＞「アルゴリズム」とは「バズワード」であり、「一般的に命令型プログラミングパラダイムを指し示す」のであり、
＞その他の使用は一般的ではない、

酔っ払って書いたんですよ　脱アルコリズム

アルゴリズムはバズワードだから脱アルゴリズムするべきなんですよ。

>>567
この人病人だと思う

精神病である傍証が、批判されて頭に来て記事の中でさえそれに対して個人攻撃はじめたことだな
ここでも暴れ出したし

一般的にアルゴリズムはパラダイムではないから、話がかみ合うことはない

>>572
こりゃまた酷い発言が
パラダイムという概念がまるでわかってないな
アルゴリズムの概念にしてもそうなんだが、哲学的認識が低すぎるくせに哲学的なことを言いたがるね、君

ズバリ精神病だろ？
特定の捉え方が心理的に付着してしまい、それ自身の捉え返しが不可能になるんだな
あとは、そこからの演繹的は構築のみ

だから、ああいうお馬鹿な形而上学的珍説が生まれてしまう

>>573
　　　　 (´･ω･｀)
　　　／ 　　　　｀ヽ.　　　お薬増やしておきますねー
　 __/　 ┃)) ＿_i　|
／　ヽ,,⌒)＿__（,,ノ＼

>>574
わははは
俺を精神疾患者だとしたいのか？
無能、必死のアイデアか？
笑止

>>575
　　　　 (´･ω･) ﾁﾗｯ
　　　／ 　　　　｀ヽ.
　 __/　 ┃　 ＿_i　|
／　ヽ,,⌒)＿__（,,ノ＼


　　　　 (´･ω･｀)
　　　／ 　　　　｀ヽ.　　　今度カウンセリングも受けましょうねー
　 __/　 ┃)) ＿_i　|
／　ヽ,,⌒)＿__（,,ノ＼

古典でも読んでいた方がマシだなあ
ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM
http://www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf

脱毛アルゴリズムのせいですっかりスレが精神病スレになった
精神病は恐ろしい

　　　　　　　　　　　　　　）
　　　　　　　　　,.-―:￣｀ー::::::::::､ 　　　　　　　　　　　　　（
　　　　　　　／::::::::::::.::::::::::::::::::::::::::::｀::､､ 　　　 　　　　　,,　　　　　　　　）　　　　　　）
　　　　　　/::::::::::::::::::::::::::::::::::::::::::::::::::::::｀､ 　　　　 　　　　ﾞﾐ;;;;;,_　　　　　　　　　　　（
　　　　　 ｌ::::::::::::::::::::::::::::::::::::::::;':l:::::::::::＼::l 　　　　 　　　　　ミ;;;;;;;;､;:..,,.,,,,,
　　　 　 l:::::::::::::::::::::::::::::::::,,::::::::;-,:,::::::::::::::::l 　　　　　　　　　　i;i;i;i; '',',;^′..ヽ
　　　　 l::::::::::::::::,＿,.::::,';::::::;:::::: :: l ::::::::::::::l 　　　　　　　　　　ﾞゞy､､;:..､）　　｝
　　　 　l::::::::::／-/:::/-ニ,.::::／=,.／::::::::::l 　　　　　　　　　　.¨.､,_,,､_,,r_,ノ′
　　　　 ヽ::::　´､ひ> ;: 　l .<ひ>'　 ､::::::::/ 　　　　 　　　/;:;":;.:;";i; '',',;;;_~;;;′.ヽ
　　　　ヽ:::::　　 ￣ .)::;　 l　￣　　　ｌ::::/ 　　　　　　　　ﾞ{y､､;:...:,:.:.､;:..:,:.:.　._　　､｝
　　　　　､:::::..　　 /:::;　.,-､　　　　 l:::/、 　　　　　　　　".¨ｰ=v ''‐ .:v､,,､_,r_,ノ′
　　　　,―::::::::　　ゝヽ- ｰ' ､　　　 l::/,､ヽ 　　　　　　 /;i;i; '',',;;;_~⌒¨;;;;;;;;ヾ.ﾐﾞ´ﾞ^′..ヽ　
　　 　 l,､,､,,:､::　/ ,--､,-.､_ l　 　 /::::::,､,､l 　　　　　 ﾞ{y､､;:...:,:.:.､;､;:.:,:.:.　._　　.､）　　､｝
　　　ｌ,､,､,､,､,､::､　｀ー￣-'　　　/:::::::::::,､,､l 　　　　　　".¨ｰ=v ''‐ .:v､冫_._ .､,_,,､_,,r_,ノ′
　　　ｌ,､,､,､,､,､,､::ヽ　　　　　 ／::::::::､,､,､,､,ﾉ:＼ 　　/i;i; '',',;;;_~υ⌒¨;;;;;;;;ヾ.ﾐﾞ´ﾞ^′.ｿ.ヽ
　　　ｌ,､,､,､,､,､,､,､,､,,ー― ':::::::,､,､,､,／,､,､,､,､,｀ 　ﾞ{y､､;:..ゞ.:,:.:.､;:.ﾐ.:,:.:.　._υﾟo,,'.､）　　､｝
　　/,､,､,､,､,､,､,､,､,､:::::::::::::::::::::::::::、,､､,､,､,､,､,､,､ 　　ヾ,,..;::;;;::,;,::;):;:;:; .:v､冫_._ .､,_,,､_,,r_,ノ′
　　　　　　

精神病っていうか ID:CytiCPlP みたいな子は、
極度に知能が劣ってるんだと思うよ。
人より二段くらい下というか。

脱データ構造、脱アルゴリズム、脱デザインパターンにスレの名前を変えるべき

あぼーんばっかりだな……

>>580
わはは
俺の著作は国会図書館にゴロゴロ
面白いこというやつだな

評価能力皆無の暴露乙

>>580
おまえ、おかべ？
笑いが止まりません

国会図書館は出版された図書を網羅的に集めるところだから自慢にはならない。
ぶっちゃけた話、電波本も収蔵してるし。
OPACで調べると多数の大学図書館が所蔵してる事の方がまだいい。

本人がこっちのスレに書いても、

レスはこっちのスレに書くようにしてください。
http://peace.2ch.net/test/read.cgi/tech/1403215505/l50

ますます脱アルゴリズムパラダイムへの変換が進んでいる感じだな世間では

脱毛アルゴリズムのせいでこのスレ荒廃著しいな
さすがは脱毛頭頂

>>587
おまえ、精神病の岡部町だろ

ほざけ。貴様らナンチャッテコーダーに理解できてるとはおもわないがね
岡部のこと言ってることがおかしかったら論理的に反論してみろ

俺も読んでみたけど、岡部が言ってることには別段おかしいところはないと思った

また岡部が来たぞ

岡部認定する簡単なお仕事です

理解できる人もいれば、理解できない人もいる。
俺が岡部なら理解できる人と親しくなりたいと思うだろうな。
つまりお前らは岡部から嫌われるべくして嫌われた。
脱アルゴリズムという一語にとらわれてカリフォルニア大卒の
秀才から見放されたブタどもｗ

>>590
ほーら、もろ精神病
写真ももろ精神病
底辺で精神病なんてやだなあ

>>594
あははは
おまえ、認識が浅いんだよ
科哲でも勉強しろ
むだかなあ、その形而上学頭じゃ

だから、精神病なんだしな

反応はあっちのスレに書き込んでください。
http://peace.2ch.net/test/read.cgi/tech/1403215505/l50

>>596
　　　　　　　　　　　　　　　　　　　　　　 ∩_＿＿∩
　　　　　,.-―-、　　　　　　　　　　　 　| ノ ノ　　 ヽ＼
　　 ∩|~_ヽ.╋/∩　　　　　　　　　　　 /　　●　　 ● |
　　 | ノ⌒￣￣⌒ヽ　　　　　　　　　　ミ　　　( _●_) ミ
　　/　　●　　　● |　重症クマ　 　／　　　￣￣＼／⌒ゝ
　 |　　　　( _●_)　 ミ　　　　　　　彡　　　　　　　　　　/￣￣￣￣￣￣￣
　彡　　　　|∪| 　 、゛　　　　　　　.ミ　　　　　　　ヘ_／:::
　｜　　　　ヽノ　 〈　.　プス！　. ミ　　　　　　　　ミ::::::::
　　〉、 ヽ.＿　　＿.＼＿＿_　　　ミ　　　　　　　ヽミ:::::
　　　ヽ、＿_.〉|=|==|(⌒)++++][コ==-〇　　　　　　＼:::
　　　　　　　　　￣￣￣￣￣　　 ＼　＼＿＿＿　　ヽ:

>>594
おやおや、自分で脱アルゴリズムは単なる扇動のための表現と認めたな
おまえのやってることは人をだましてイメージ植え付けるやり方
それを指摘されてぶち切れるあたり

もろ精神病

>>599
誰が何にどう騙されたのかな？お〜ん？

で、お前ら最終学歴なによ？岡部はカリフォルニア大だが？お〜ん？

脱アルゴリズムでーす
ビローン

　　　　　 　　　／_ノ '　ヽ_＼
　　　　　　　／（≡） 　 （≡）＼
　　　　　 ／::::::⌒（__人__）⌒:::::＼ 　　
　　　　　 |　　　　　|r┬-|　　　　　|　　　
　,.--――＼ 　　 　`ー'´ 　 　 ／――--､
（ )　　　　(￣　　　　　　　　　　￣）　　　 ( ）
　ヽ 　 　　￣| 　 　 　 　　　　 |￣　　　　 /
　　 ヽ 　 　　|　　　　э　　　　|　　　　　/　　　
　　　　ヽ、＿(　　　　,,,,　　　 ,ﾉ 　　＿_ノ
　　　　　　 ／ 　　 ､(Ｕ)ﾉ　　 ＼￣
　　　　　／　　／´ 　　　｀＼　　＼ 　 　　　　　　
　　　 ／　 ／ 　 　　　　　　　＼　 ＼　

>>602
ﾊﾟｼｬ　ﾊﾟｼｬ　 ﾊﾟｼｬ　ﾊﾟｼｬ　ﾊﾟｼｬ　　ﾊﾟｼｬ　ﾊﾟｼｬ　ﾊﾟｼｬ　ﾊﾟｼｬ　ﾊﾟｼｬ
　　　ﾊﾟｼｬ　ﾊﾟｼｬ　ﾊﾟｼｬ　ﾊﾟｼｬ　ﾊﾟｼｬ　 ﾊﾟｼｬ　ﾊﾟｼｬ　ﾊﾟｼｬ　　ﾊﾟｼｬ 　ﾊﾟｼｬ
　∧_∧　　　 　　∧_∧ 　　　 ∧_∧　　∧_∧　　　　∧_∧　　　　 ∧_∧
　(　　 )】 　 　 　(　　 )】　　　 (　　 )】 【(　　 )　　　 【(　　 )　　　 【(　　 )
　/　 /┘　.　 　/　 /┘.　 　　/　 /┘ └＼ ＼　 　└＼ ＼　　 └＼ ＼
ノ￣ゝ　 　　　ノ￣ゝ 　　　 　ノ￣ゝ　 　　　ノ￣ゝ 　　 ノ￣ゝ　 　 　ノ￣ゝ

LISP

作家になったエンジニア
http://matogrosso.jp/engineer/engineer-01.html

＞藤井　コードはわかる、というか、数式での理解が苦手なんです。数式で見ても
＞よくわからないんですが、コードになったアルゴリズムで見れば「あぁ！」って
＞腑に落ちる。群とか集合とかの処理の方法なんかもコードで見たほうがわかるんですよね。

こんなことってあるの？
数式でわからないものが、コードで書いたらわかったなんて経験ないんだけど。
そういう人もいるのか、単にハッタリなのか？

知らない・慣れない記号でわんさか書かれたものよりはコードのほうが……かもね

記号を覚えてなかったり
上とか下とか小さく書いてあったりするのが
英単語混じりで一列に並ぶから

微分方程式だといまいちピンとこないのが、
差分方程式に変形してプログラムにまでなればなんとなく、とか。

ただ、あまり良いことじゃない。抽象を扱えない頭だと、後々苦労する。

狂気のマッドコーダー、鳳凰院凶真だっ！フゥーハハハ！
機関の妨害が入っているようだな
そのようなものに私が屈すると思ったかっ！

全ては脱アルゴリズムの選択だっ！
エル・プサイ・コングルゥ

オカリンは凄いね〜ｗｗｗｗｗ

「CERNだけど何か質問ある？」でCERNが「シュタインズ・ゲート」に触れ大盛り上がり
http://gigazine.net/news/20140623-ama-cern/

>>605
数式をプログラムコードにして実行すると、計算結果の数値やグラフを見てイメージがつかめる、っていうなら判る。

JavaScriptで、2分木を書こうと思ったが、
1-100をこの順番で追加したら、rootが1となり、
どんどん右側へ追加されていき、
直線となって、2分木にならない

B-Tree, 赤黒木は、どうやって木の高さをそろえているの？

>>612
左の子が親より小さく、右の子が親より大きいって
いうのが満たされてれば、一直線となっても立派な2分探索木でござるよ。
効率は悪いけど。

B-Treeはノードが持つ子の数に制限を設けて、子の数がいっぱいになったら
ノードを分割していく感じ。すべてのリーフノードの高さは同じになる。

赤黒木は色をチェックして平衡化を行ってく。
黒ノードがB-Treeのノードに対応するから、黒ノードの数が左右で同じになる。

>>612
アルゴリズムの本を1冊は持っておけ

で、出た〜本持っとけ言奴

>>615
その煽りの面白さがおじさんにはさっぱりわからんわ

ネットに転がってるpdfで良いです。

>>615
「知的でタメになるつっこみの仕方」
監修・吉本興業
を一冊持ってろ

おじさんの　くちさきから　いてつくはどうが　ほとばしる！！

>>612
まず木の回転は順序保ったまま高さを調整できる。
あとは回転をどういう条件でやるかで赤黒木・AVL木とかに分かれる。
B木は二分木じゃないのでまた別

>>612
平衡二分木なら、まず原理が簡単なAVL木を勉強しよう。
次にspray木。
次に2-3-4木(これは二分木ではない)、赤黒木(2-3-4木の二分木化)。

「代数的構造」買ったけど難しいな
頭が固くなってきているせいか、なかなか辛い

>>618
そのレスを見るとあまりタメにならなそうな気が…

脱アルゴリズムってなんなん？

>>624
あぼーん推奨ワード

2分木の木の高さをそろえる方法まで、
載せている本なんて、無いだろ？

載っていたら買うけどさー
載せられないということは、かなり難しいと言うこと

つ　アルゴリズムC・新版―基礎・データ構造・整列・探索、R. セジウィック
http://www.amazon.co.jp/dp/4764903091/

アルゴリズムとデータ構造、岩波講座
にも、載ってた気がする
実家に置いたままだわ

R・セジウィックの20年前のアルゴリズムC++の本を見たら、
2分木の回転については、10行ほどしか載っていなかった

プログラミング・コンテスト・チャレンジブックにも、
2分木の回転・平衡化は載っていない

オライリーの「入門 データ構造とアルゴリズム」には、
AVL木の回転について、図入りの説明が載っていた

でも赤黒木を詳細に説明した本は無い
Linuxのタスクディスパッチで使っているのに

ところで2分木で、nullの代わりに、
番兵を使っているものがあったが、
番兵を使った方がよいのか？

ぶっちゃけググった方が早い…
木の回転　https://ja.wikipedia.org/wiki/%E6%9C%A8%E3%81%AE%E5%9B%9E%E8%BB%A2
AVL木 　 http://www.geocities.jp/m_hiroi/light/pyalgo12.html
赤黒木 　 http://www.geocities.jp/m_hiroi/light/pyalgo16.html

番兵は性能よりもコードをシンプルにするためのもんだし、お好みでどうぞ

>>630
いやいや、シンプルになっても終了条件が見えなくなってリーダビリティ下がるでしょ。
前処理と後始末がいることも多いしコメント必須になる。
性能上がらないなら使うもんじゃない。

えー。しかし番兵なんて所詮ゴミみたいな定数倍最適化にしかならんしなあ
多少短く書ける以外に価値がほぼないから、趣味の領域かと

そういう意味ではNull Objectパターンやnilも番兵の亜種っぽいな
使い方次第で可読性が下がるし

脱アルゴリズム・・・・・

宣言型言語の制約プログラミングや論理プログラミングなら
アルゴリズムを必ずしも記述する必要はないが、
結局糞みたいな処理速度にならないために隠蔽されたアルゴリズムを
意識せにゃならなくなるから脱アルゴリズムは飛ばし過ぎ

どんなプログラム書いても、それアルゴリズムになるから
アルゴリズムってそういうものなんだけど

>>632
最近のCPUじゃあ定数倍最適化にもならないんじゃない？
分岐の投機的実行があるから。

分岐予測が当たると早い、という石で、直感に反する順序で判定を並べたほうが
良い場合もあるという報告があったし(※)、正直、個々の機械で実アプリで
確かめない限り、何も言えん。

ただ、勉強としては色々なモディファイがあるというのは抑えておいた
ほうが良い。速度だけじゃなくモディファイが要ることはよくある。

(※)
普通は、確率が50%→25%→12.5%→....といった順に並べたほうが、先に結果が
確定するから速い、というのが定石なのだが、そうすると分岐予測的には最悪に
なるので、確率が低いほうから ...→12.5%→25%→50%のように並べたほうが速い
プロセッサがある。

>>638
>12.5%→25%→50%のように並べたほうが速い
ほうほう、なるへそ

脱アルゴリズムとか馬鹿なんじゃねえの

正直、あの記事の主は病人だと思う。

脱プログラミング、人差し指でディスプレイのあっちこっちから引っ張るとプログラムができる

人差し指でディスプレイのあっちこっちから引っ張ることがプログラミング作業となるだけであって

だからそれはこっちでやれ
http://peace.2ch.net/test/read.cgi/tech/1403215505/l50

>>638
最近は実行時プロファイル取ってJITします。

>>626
＞2分木の木の高さをそろえる方法まで、
＞載せている本なんて、無いだろ？

上にもでてる、岩波の「アルゴリズムとデータ構造」石畑清のをみたいけど、
この話題、AVL木、B木で数十ページつかって詳しく解説してたよ。
というかこのあたり読んでなかった。

やっぱ日本人の書いたアルゴリズム本のなかでこれは良い方だと思う。

おまえら、頭いい風のトンチキ。数学やれ。

やはり、2分木の回転を説明した本はなさそう
Webに載ってる情報で我慢するしかないのかー

(ﾟДﾟ) ﾊｱ??

木の二重回転だるい。あるとなしでどの程度違うんだろ？
親への参照をもたせると参照のはりかえがかなり複雑になる

岩波の「アルゴリズムとデータ構造」石畑清

"Algorithms" Robert Wayne, Kevin Sedgewick

どっちも amazon の書評わろす

「アルゴリズムとデータ構造」
とか
「データ構造とアルゴリズム」
ってタイトルの本多過ぎ

データ構造は重要

そこは否定してない
一字一句完全に同じタイトルの本がいくつもありすぎて紛らわしいので
もっと工夫すれば良いのにと思った

>>648
>>650
sedgewick読めばいいのに。
この人はアルゴリズム解析屋だからそのへんは結構しっかり書いてる。
Knuthのところ出身。

>>648
Niklaus Wirth: 「アルゴリズム+データ構造=プログラム」日本コンピュータ協会
浅野哲夫: 「データ構造」近代科学社
桐山清: 「C言語によるデータ構造とプログラム書法」森北出版
近藤嘉雪: 「定本 Cプログラマのためのアルゴリズムとデータ構造」ソフトバンク
渡邊敏正: 「データ構造と基本アルゴリズム」共立出版

のどれにも、AVL木（バランス木）の回転の解説あるよ

今時Wirth先生の本はないわ。
均衡二分木はあまり実行効率が良くないAVL木中心だし、
多分木派生の二分木は赤黒じゃないし。
しかも言語がPascal。
言語屋さんだけあってコードは綺麗。

『アルゴリズム・イントロダクション』読め。
総合版は武器にもなってお得だぞ。

セジウィックのアルゴリズム本もわかりやすくておすすめ

アルゴリズム・イントロダクション
セジウィック新版
の二択だな。
アルゴリズム・イントロダクションをちら見してみて挫折しないようならこっちやればいい。
この二冊ほどしっかり書けてる本はほとんどない。TAOCPは実装言語が独自すぎて除外。

>>646
石畑清のは、AVL木の回転について、図入りの説明がある
ただし、25年前の本で、ソースコードがPascal

石畑清の本はいいよやっぱり。説明が細かいし。

しかしPascalだから困るという意見が結構多いのが不思議。
アルゴリズムを説明するためのたかが数十行のコード、言語仕様やライブラリに
深く依存しているわけでもないプログラム読むのにそんな苦労するのか？

疑似コードとして読めばいいでしょ。俺もPascal知らんけど充分理解できるよ。

もひとつ言っとくと、石畑清の本、巻末にちゃんとCとLISPのコード例も付録
で載ってるんだよ。ほんとは持ってないんじゃないのお前ら？
コピペしかできない知恵遅れにも安心（笑）

Pascalは配列添字が1から始まるから、他の言語に移植するときに、
Off by one エラーに注意しながら書き直す必要がある。
これが面倒。

>>663
1オリジンを他のオリジンに直すだけだろう？簡単な線形変換をかますだけなのでは？
ま、2オリジンに書き直すなら多少のぐちゃぐちゃは厭わないが、1オリジンを0オリジンにわざわざ直す必要もない

大学のアルゴリズムの講義の教科書が石畑Pascal本だ

６６６

AVL木は挿入や削除で必要になる回転が多いので遅い。
バランスしてるからオーダーは良いが、
オーダーを計算する時に無視する定数部が悪い。
均衡二分木がAVL木しか書いてない本はとてつもなく古い。

>>662
漏れは研究家で、本はプログラミング・コンテスト・
チャレンジブックしか持っていない
漏れは立ち読みするから、誰よりも厳しいよw

まず図を載せていない著者を評価しない。
そういう著者はコピペしているだけで、
本当にアルゴリズムを作っていないかも

いかに読者に解かりやすく説明できるか？
まず図を作る段階で、戦いは始まっている

入門 データ構造とアルゴリズム
http://www.oreilly.co.jp/books/9784873116341/

＞インド工科大学（IIT）と企業の両方で豊富な経験を持つインド人著者による、
＞実例豊富なデータ構造とアルゴリズムの解説書。

この本の評価どうですか？

目次を見る限り、インド人ってネタを活かしてるようには見えないな

漏れは研究家でw
誰よりも厳しいよww
評価しないwww

朝からニヤリとさせてもらった
さて働こう…

>>667
不正確だ
挿入で必要な木の回転は、ただの一回だけ、問題は削除だね。これは AVL も赤黒木も同じ
削除が頻繁におこなわれるのなら、左右のバランスのゆるい赤黒木がいいね

インド人嘘つかない

アルゴリズムの名著にはPascalで書かれた本も多いし、Pascalもひと通り勉強したほうがいいんだろうか？

pascalはCというかPL/I系統の言語が出来るなら読むのはそんなに難しくない。

CがPL/I系統？

ていうかPascalないしAlgolは、いちいち勉強なぞしなくとも読むのにそうは苦労しないだろ。
Algolには名前呼びとか変な機能があるが、普通はそういうトラップは回避して説明に使うから。

http://qiita.com/kenokabe/items/13ea8d2da6adce1b3b9a
関数型プログラミングとオブジェクト指向の抜き差しならない関係について整理して考える



お、これはなかなか優秀な人が現れたな。わかりやすい良エントリ。

>>678
スレ違いです。こちらへどうぞ。

【毛の壁】脱アルゴリズム宣言【FXST】
http://peace.2ch.net/test/read.cgi/tech/1403215505/

アルゴリズムを学ぼう (アスキー書籍)
川中 真耶
http://www.amazon.co.jp/dp/B00JGI5H2I/

Amazonのレビューでも評価低いけど、この本意外に良書やね。
もっとレベルが低いのかと思ってたけど、二分木だとAVL木の回転とかまで
ちゃんと説明している。
ただ、レビューでも触れられているけど、ストーリー仕立てにする意味が
ほとんどないというか、単純につまらない。
こういうのが受けると思ったんだろうけど、キャラクターにも魅力がない。

Kindle版だと安いから買って読む価値はある。

アルゴリズムを学ぼう サポートページ
https://sites.google.com/site/adtalgo/home

>>680-681

【これは】重大な誤り【ひどい】
１つ本当にひどい誤りを含んでおりました。本当に申し訳ありません。恥ずかしくて夜も寝られません。

P. 33

O(aN) = O(eN)
この文章の記述は大嘘です。デタラメです。
指数の底を変えることは出来ません。
そもそも数式の展開も誤っています。
指数の場合も同様で〜〜となる。の文を削除。


わろ・・・えない

あまり話題にならないけど丸善から出ている黄色い表紙の装丁のアルゴリズム本でオススメある？
お前らには難しくくて縁のない本が多い？

　　　　　　　　　　　　　 　　|￣｀`''- ､
　　　　　　　　　　　　　 　　|　　　　　 ｀ﾞ''ｰ- ､　　＿＿＿＿＿＿__
　　　　　　　　　　　　　 　　|　　　 ,. -‐ ''´￣￣｀ヽ､＿　　　　　 　 /
　　　　　　　　　　　　　　　 |, - '´￣　 　 　 　 　 　 　 ｀ヽ、 　 　 /
　　　　　　　　　　　　　　／　　　　　　　　　　　　　　　｀ヽ､ヽ 　 /
　　　　　　　　　　　　 _/　　　　　　　　　　　　　　　　　　　 ヽヽ/
　　　　　　　　　　 ／ / / 　 /　　/　 /　　　　　　　　　　　　ヽﾊ
　　　　　　　　　 く　 / /! 　 | 　 〃 _/__　l|　　 | | 　 |　　|　 | | ||ヽ
　　　　　　　　　　 ＼l//　/ |　 /|'´ ∧　 ||　　 | |ｰ､||　　|　 | l　| ヽ
　　　　　　　　　　　　/ハ/　|　 | ヽ/　ヽ | ヽ　 | ||　/|ヽ/!　 |/　|　ヽ
　　　　　　　　　　　 /　|　　||ヽ { ,r===､　　 ＼| _!V　|//　//　 .! 　 |
　　　　　　　　　　　 |　|| 　 |l　|ヽ!'´￣｀ﾞ 　 ,　　==ミ､ /イ川　　|─┘
　　　　　　　　　　　 | ﾊ||　 ||　|　"""　┌---┐　　｀　 /　//　 |
　　　　　　　　　　　 V　!ヽ ト! ヽ､　　　 | 　 　 !　　　　/　//|　/
　　　　　　　　　　　　　　 ヽ! ＼ハ`　､ ヽ､__ノ　 　 ,.イ/ // | /
　 　 ┌/）/）/）/）/）/）/）/）/）/）lｰ/　` ー‐┬ '´ レ//l/　|/
　　　 |（/（/（/（/（/（/（/（/（/（/│||　　　 　 |＼　 〃
　　r'´￣ヽ.　　　　　 　 　 　 　 | | ト　　　 /　 　 ＼
　 /　￣｀ｱ　　　　　　　　 　 　 | | |　　⌒/　　　　 入
　 〉　￣二)　知ってるが　　　 | | |　　／　　 　 ／/ ヽ
　〈! 　 ,. -'　 　 　 　 　 　 　 　 | | ヽ∠-----',　'´　 　 ',
　 | ＼| | 　 .お前の態度が 　 | |<二Z二￣　 ／　　 　 ',
　 | 　 | |　　 　 　 　　 　　　　 _r'---|　　[ ｀`ヽ､　　　　　 ',
　 | 　 | |　　　気に入らない　>-､__　　　 [　　　 ヽ　　 　 　!
　　＼.| l.　　　　　　　　　 　 　 ヽ､　 　 　 [　　　　 ヽ　　　　|
　　　 ヽ|　　　　　　　　　　　　　　＼　 　 r'　　　　　ヽ､　 　 |

そう言わず教えろよ

本ばかり読んでないで実践しろよ

結城浩の「Java言語で学ぶデザインパターン入門」ってオリジナルと増補改訂版って
買い直した方がいいぐらい違いが大きいんですか？

Cookieを使わずにユーザーを追跡する仕組みが普及しつつある
http://it.slashdot.jp/story/14/07/22/0613210/

GoFは言語が未熟だった時代の名残のようなもの
現代的なほとんどの言語（特に動的型付言語）では、多くのパターンが適用できない
（適用しても、バッドパターンにしかならない）

Javaなどの一部の古めかしい静的型付言語では、まだ頼る余地は残っていたが
そのJavaでさえも関数型の要素を取り入れ、設計が大幅に変わってきている
GoF自体の改定でもなければ、改めて学ぶ価値はない

なんだ本人が来たのか（笑）

突然ですが質問させてください
重みなし無向グラフの場合、ダイクストラ法より反復深化の方が計算量少なくて済むんですか？

アルゴリズムとプログラミングをビジュアルで一挙に理解できる「VisuAlgo」
http://gigazine.net/news/20140819-visualgo/

「アルゴリズムを学ぼう」は続の方が面白いな。

http://qiita.com/kenokabe/items/821ce4020644372b648c

＞「アルゴリズム」とは「バズワード」であり、「一般的に命令型プログラミング
＞パラダイムを指し示す」のであり、その他の使用は一般的ではない、ということ
＞です。

勉強になるな。このページ。

>>694
どこらへんが？

>>694 毛の壁は隔離スレから出るんじゃねぇよ
http://peace.2ch.net/test/read.cgi/tech/1403215505/l50

そんな意地悪言うなよ。

死ねゴミ共がw

カリー化とは何でしょうか？

「大抵のものはカレー味にしとけば失敗しない」という理論

なるほど深いですね

は？

ねんまつ

1うんこ

「オブジェクト指向のこころ」って原題とは何も関係ない変な題名で誤解されているけど、実はデザインパターンの良書だよね
結城本みたいなトイプログラムじゃなくてちゃんと仕事に活かせるコードや考え方が載ってる
もっと評価されるべき本だと思う

まるち