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

1 名前：デフォルトの名無しさん mailto:sage [2013/03/03(日) 18:10:11.63 .net] 【関連スレ】 3Dアルゴリズム全般 toro.2ch.net/test/read.cgi/tech/1164171086/ ＜集大成＞アルゴリズム大辞典 toro.2ch.net/test/read.cgi/tech/1086272325/ アルゴリズム総合スレ in ム板 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 75 名前：デフォルトの名無しさん mailto:sage [2013/10/02(水) 06:46:43.90 .net] 率直に言って、C++という言語はデータ構造を分からせるのには向かない。 内容は時間的/空間的計算量という評価に徹してデータ構造とその読み出し方を 解説したもので、むしろ優れた本だと思う。 76 名前：デフォルトの名無しさん [2013/10/02(水) 08:06:05.95 .net] >>75 普通の大学で使うような教科書のほうがいいと思う。 エイホ・ホップクロフト・ウルマンのアルゴリズムとデータ構造とか MITの教科書とか。 77 名前：デフォルトの名無しさん mailto:sage [2013/10/02(水) 08:33:04.43 .net] Ahoの本は良いな はずれがない 78 名前：デフォルトの名無しさん [2013/10/02(水) 09:11:06.55 .net] クヌースの本も読んだほうがいい？ クヌースの本はプログラマ必読の書らしいけど 79 名前：デフォルトの名無しさん [2013/10/02(水) 11:01:55.61 .net] >>78 全部読むのは難しいんじゃないですか？ アルゴリズムの解析の部分は難しいし、実益が少ない。 アルゴリズムの手順だけ読むくらいでいいのでは？ あと新しいアルゴリズムが書かれていないらしい。 80 名前：デフォルトの名無しさん mailto:sage [2013/10/02(水) 11:55:09.13 .net] クヌース（ブルース風に） 81 名前：デフォルトの名無しさん mailto:sage [2013/10/02(水) 19:03:31.81 .net] クヌースは古典だな 読むか読まないかなら、もちろん読んだ方がいいが >>79 新しいアルゴリズムは論文読むしか 82 名前：デフォルトの名無しさん mailto:sage [2013/10/03(木) 10:30:06.56 .net] クヌース　ホシーイ　ケレード ゼパーン　ニナーテ　ルヨーネ シカータ　ナイカーラ　エイーゴ デヨンデール　 83 名前：デフォルトの名無しさん mailto:sage [2013/10/03(木) 14:33:48.67 .net] >>79 ところで新しいアルゴリズムてどんなの？ 遺伝とかならいらないけど 84 名前：デフォルトの名無しさん [2013/10/03(木) 19:57:54.46 .net] >>83 すみません。よく知りません。 擬似乱数を生成するメルセンヌツイスターが載っていないって、 考案者が文句言っていたのは知っています。 85 名前：デフォルトの名無しさん [2013/10/03(木) 20:17:33.09 .net] クヌースの本は要約版が1冊になって出版される予定だけど、実現しないだろうね。 というかThe Art of Computer Programming自体が完成しないか。 既刊の第4巻はおもしろそう。 86 名前：デフォルトの名無しさん mailto:sage [2013/10/04(金) 09:08:51.46 .net] わざと初等的な証明をつかってるから 無駄にめんどくさいね。 群とか環とか使えば良いのにっておもうよ。 87 名前：デフォルトの名無しさん mailto:sage [2013/10/04(金) 09:12:18.81 .net] self containedになっているのだろう 88 名前：デフォルトの名無しさん mailto:sage [2013/10/07(月) 09:07:45.97 .net] >>84 あの膨大な本の中の、たった一つのテーマだからね。 89 名前：デフォルトの名無しさん [2013/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 [2013/10/07(月) 23:01:02.14 .net] 補足です。 void AppDerived::method(){ ptr->func(); } class DetailBase{ virtual void func(){ return; } } 上記の方法を避けたいための方法です。 91 名前：デフォルトの名無しさん mailto:sage [2013/10/07(月) 23:12:12.86 .net] >>89 >オブジェクト思考的 は関係ないね,、C++の実装としてだろう 92 名前：デフォルトの名無しさん mailto:sage [2013/10/08(火) 00:52:45.41 .net] >>89 その派生クラス同士の関係性によってはアリな場合もあるんだけど、 一般的には無しだね。 基底クラスを触りたくないからと言うのは全く理由にならないと思うよ。 93 名前：デフォルトの名無しさん mailto:sage [2013/10/08(火) 10:05:07.76 .net] >>89 AppBaseがコンポジションするDetailBaseはPublicやProtectedってことでしょ？ それなら派生クラスから弄られることを想定しているってことになるから AppDerivedのMethod()で新しくDetailDerivedを保持し直したらいいんじゃないの？ Privateなら基底クラスでしかDetailBaseを弄らないのだから AppDerivedのMethod()内でのみ使用するためにDetailDerivedのインスタンス生成すりゃいいんじゃないの？ >>90の方法を避けたいってのは、AppBaseがDetailBaseをコンポジションしてポリモーフィズムするのを 否定しちゃってんじゃないの？コンポジションしている意味が無くならない？ 94 名前：デフォルトの名無しさん [2013/10/09(水) 18:19:09.59 .net] ﾌﾟｯw 95 名前：デフォルトの名無しさん mailto:sage [2013/10/10(木) 07:27:16.17 .net] ｸｻｯ 96 名前：デフォルトの名無しさん mailto:sage [2013/10/10(木) 07:54:38.65 .net] すまん 97 名前：デフォルトの名無しさん mailto:sage [2013/10/10(木) 08:38:38.27 .net] おまえかよ 98 名前：デフォルトの名無しさん mailto:sage [2013/10/10(木) 18:02:10.65 .net] このように他人（主に女の子）の汚名を代わって受けるのがイケメンパターン 99 名前：デフォルトの名無しさん [2013/10/12(土) 18:05:18.38 .net] 死ねゴミ共がw 死ねゴミ共がw 100 名前：デフォルトの名無しさん mailto:sage [2013/10/12(土) 21:43:22.30 .net] 落ち着け 101 名前：デフォルトの名無しさん mailto:sage [2013/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 名前：デフォルトの名無しさん mailto:sage [2013/10/13(日) 14:24:30.97 .net] 要素の重複とかあるの？ 103 名前：デフォルトの名無しさん mailto:sage [2013/10/13(日) 14:29:12.64 .net] >>101 > 「変化が少ない」の基準は必ずしも特定しないが、一例として「各要素の > 移動距離の二乗和が小さい」などが考えられる。 これに激しく違和感を感じるけど、 > ここで、近似解でよいので計算量の少ないアルゴリズムが欲しいのですが、 近似解でいいならGAが楽じゃね？ 104 名前：デフォルトの名無しさん mailto:sage [2013/10/13(日) 15:28:06.54 .net] Aを走査していき、Bにも含まれる要素に当たったら、Bの要素順で置き換える ……だと変化が大きいのかもしれないのか 105 名前：101 mailto:sage [2013/10/13(日) 16:04:56.10 .net] >>102 重複はない前提です。 >>103 その基準のところも、なにか使えそうなものがあれば調べてみたいと思いますが。 ところで、どういうところで違和感を感じるでしょう？ >>104 Bの並びによっては団子になってしまいそうですが、確かに計算量は非常に 少なそうですね。 106 名前：デフォルトの名無しさん mailto:sage [2013/10/13(日) 16:45:07.14 .net] >>105 順列と最小二乗って、同じ目的で使って嬉しくなる数学的根拠があるのかな、と思って。 置換の数で距離を測るのが一般的かな？とか。 感覚的な意見で申し訳ないけど。 107 名前：デフォルトの名無しさん mailto:sage [2013/10/13(日) 17:11:59.64 .net] 感覚的なものなのでそこはあまり根拠はないですが、移動距離が大きくなるにつれて ペナルティは増大するほうがいいのかなと。 ただまぁ、ひとつの要素が移動すればその距離に応じて他の要素もずれるわけなんで、 移動距離の総和とかあるいは単純に移動した要素の数でもいいかもしれないですね。 順序の距離とか順列間の距離とかで探したらいくつか距離の定義が見つかりました。 108 名前：デフォルトの名無しさん [2013/10/14(月) 09:57:46.64 .net] 死ねゴミ共がw 109 名前：デフォルトの名無しさん mailto:sage [2013/10/14(月) 10:21:17.60 .net] 落ち着け 110 名前：デフォルトの名無しさん [2013/11/03(日) 22:41:37.52 .net] グーグルのアルゴリズムコンテストとか受けてるやついる？ 111 名前：デフォルトの名無しさん mailto:sage [2013/11/18(月) 20:09:19.22 .net] 全要素の値を0で初期化した要素数nの一次元配列にたいして、 ランダムに選んだm (< n) 個の要素のみ値を1にした配列を作りたいです。 次の方法を考えました。 1. 先頭からm個の要素の値を1に、残りの要素の値を0にした配列を用意する。 2. その配列に対して Fisher-Yates shuffle を施す。 これよりも実行速度において効率的な方法はあるでしょうか。 （並列化を利用して効率よくする方法もアリです） ただ、できるだけ偏りは無くしたいです。 112 名前：デフォルトの名無しさん mailto:sage [2013/11/18(月) 20:13:31.20 .net] nとmをどれくらいに想定してるのさ 113 名前：デフォルトの名無しさん mailto:sage [2013/11/18(月) 20:56:55.33 .net] >>112 n は 1000000 くらい m は 1000 log 1000 くらいなので、だいたい 7000 弱程度です 114 名前：デフォルトの名無しさん mailto:sage [2013/11/18(月) 20:59:21.68 .net] （その程度だと、どんな馬鹿なアルゴリズムでも一瞬で終わる処理だと思うが、何らかの効率的アルゴリズムが欲しい理由でもあるのかも……） 115 名前：デフォルトの名無しさん mailto:sage [2013/11/18(月) 21:24:13.39 .net] >>114 もっと巨大な配列なら、より効率的な方法があるのでしょうか。 どんな方法か知りたいです。 116 名前：デフォルトの名無しさん mailto:sage [2013/11/18(月) 22:58:36.70 .net] >>115 くじ引きと同じ論法でO(N)で作れるだろ 117 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 07:10:30.69 .net] >>116 それって、1000000個の重複のない数列から7000個を取り出すんだろ？ 重複のないくじを作るのに結局シャッフルがいるんじゃないのか？ だったら、やってることは>>111と同じだと思うが というか、>>111だってシャッフルはO(N)なんだから、 そもそも質問の意図もよう分からんが 118 名前：デフォルトの名無しさん mailto:sage [2013/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 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 13:06:53.22 .net] 偏りをなくしたいということは低周波成分をなくしたいということかな？ すなわち、1が連続したり、なかなか出なかったりするのを無くすということ。 だったら乱数を使うのは誤り。 120 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 20:29:44.62 .net] >>118 すごいですね、その発想は出てこなかったです。 簡単な例で図を描いて確かめてみましたが、みんな当たる確率は同じになりました。 Fisher-Yates shuffle でやるより断然スジがいいです。 採用させてもらいます。 >>119 たしかに、1 や 0 があまりに連続しているの好ましくないです。 その場合、乱数を使わずにどうやるのでしょうか。 1 か o かを選ぶのに乱数を使うのではなく、もっと別のところで使うという意味でしょうか。 それとも、全くどこにも使わないのでしょうか。 121 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 21:16:46.95 .net] >>120 乱数から低周波成分を除去した数列を使います。別名ブルーノイズ。 配列を参照するだけなので超高速で偏りの無いパターンを作ることができる。 100万個から7000個を選んでも１が連続する確率は0。規則性もなし。 ブルーノイズ数列の一部をとってもブルーノイズ数列。使い回しができる。 欠点として１回はブルーノイズ数列を作る必要があるが時間がかかる。100万個 の数列だと1時間くらいかかる。一回作ってファイルに保存しておけばOK。 122 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 21:23:07.46 .net] >>120 不思議に思ったんだがひょっとして 配列の全要素の初期値って不定扱いなのか？ なら>>118を採用する理由もわかるが 123 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 22:01:24.83 .net] 言語にもよるけど、int 型なら多くの場合0じゃない？ で気づいたけど、1 か 0 しか入らないなら bool 型でいいんじゃないか？メモリもグッと節約できる。 124 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 22:12:20.58 .net] >>122 いえ、今回は、必ず何らかの値で初期化される、という種類のデータ構造（配列）を使っています。 （言語的は初期値として未定を表す値を指定できる配列も簡単に作れますが、 今回は意味ないので、そのような配列は使っていません） >>118を採用しようと思ったのは、配列の頭から順に要素をトラバースしながら、 その要素のみを参照して値を設定していけるという点がシャッフルに比べて優れていると思ったからです。 要するに、データ構造そのものをどんどん大きくしながら作っていけます。 シャッフルも Fisher-Yates shuffle でしたら順にトラバースしますが、 その要素と、別のランダムに選んだ要素を参照しなければならず、 シャッフル処理をする前にデータ構造が完全に出来上がっていなければなりません。 その上で要素をスワップしていきます。 じつはプログラミング言語はCではなくHaskellを使っており、Haskellでは後者より前者のように、 値を入れた要素を次々と繋げながらデータ構造を（目的の規模まで）大きくしていく方が プログラムしやすいんです。 >>123 すいません、0 と 1 を使ったのは単に質問をシンプルにするためでした。 本当は、質問で 1 を入れるところでは min < x < max のランダムな浮動小数点を入れます。 そもそもの目的をぶっちゃけますと、ランダムな重み付き有向グラフの隣接行列を作ることです。 125 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 22:14:23.54 .net] >>124 > >>118を採用しようと思ったのは、配列の頭から順に要素をトラバースしながら、 > その要素のみを参照して値を設定していけるという点がシャッフルに比べて優れていると思ったからです。 すいません、ちょっと言い方がおかしいですね。 配列の頭から順に要素をトラバースしながら、ではなくて、順に配列を大きくしながら、 とか、配列を組み上げながらと言うべきでした。 126 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 22:23:35.67 .net] >>121 申し訳ないです、そこまで強力なものは今回は求めていないです。 あまりに偏りすぎていると使えないな、という程度のことでした。 しかし、これはこれで大変興味深いです。 ホワイトノイズやピンクノイズなどは聞いたことがありますが、ブルーは初耳です。 調べてみます。 127 名前：122 mailto:sage [2013/11/19(火) 22:35:24.77 .net] なるほど納得 非零要素を一次元上（あるいは二次元とか）に並べて それを仮想電子のようにみなし仮想クーロン斥力みたいなの計算して 要素番号補正したらとか考えてたんだが それだと逆に傾向出ちゃうか 値を入れた同じ行、同じ列に対して再度選択を阻害するパラメーターを入れて 云々かんぬん…いかん、わけがわからくなってきた 逃走っ（しゅたたた…） 128 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 22:54:30.96 .net] やってみましたら、たとえ Haskell であっても、 >113 程度の規模ではシャッフルでもくじ引きでも、あっという間でした。 >>114 の指摘通りで、かなり恥ずかしいです。 憶測で遅いと決めつけず、質問する前に試すべきでした。 プログラムの見やすさが抜群に良いという点で、くじ引きの方法でやることにします。 みなさん、ありがとうございました。 129 名前：デフォルトの名無しさん mailto:sage [2013/11/27(水) 04:14:03.66 .net] Edmonds's Blossom Algorithmを詳しく説明していただけないでしょうか 130 名前：デフォルトの名無しさん mailto:sage [2013/12/14(土) 23:50:45.85 .net] 二次元座標に、ラベル(高さ固定、横書き)を 重ならないように配置したいです。 現在は、y軸をラベル高さで分割して、 各領域で、ラベルが指定座標を含むように左側から詰めて配置しています。 この方法だと、3点以上集中すると、大きくずれてしまいます。 どのようなアルゴリズムがありますでしょうか？ また、動的生成なので、優先順位は コスト > 見栄え です。 131 名前：デフォルトの名無しさん mailto:sage [2013/12/15(日) 02:57:49.26 .net] >>130 ある点を矢印で示すようなラベルなら多少点から離れてもいいよね それなら幾らでもやり方はあると思うよ 例えば、点や四角（ラベル）の当たり判定で配置 132 名前：デフォルトの名無しさん mailto:sage [2013/12/15(日) 12:12:29.22 .net] >>131 おっしゃる通り、多少離れるのはかまわないです。 >点や四角（ラベル）の当たり判定で配置 ラベルの矩形の判定はやってみたのですが、 どの方向にずらすべきかのところで詰ってしまいました。 結果、上記のx軸+方向のみ補正な方法になってしまいました。 何かヒントがいただけたらと思います。 133 名前：デフォルトの名無しさん mailto:sage [2013/12/15(日) 15:32:28.35 .net] >>132 そういったアルゴリズムを組んだことはないけど ラベルの矩形が重なった時 指し示す点とラベルの四隅の点との距離が一番短いラベルの点を選出し 最初に、2点間の傾きを保ちならがら、そのラベルが指し示す点との距離を縮めて 縮めた際に2点間の距離が0になっても矩形が重なっているなら2点間の傾きを変える 目安となる距離と傾きの初期値を設定しておけばいいかな 傾きの初期値はラベルの4隅それぞれ、回転して考える 判定する矩形の4隅の点を左下にのみ、指示す点の45度右上の傾きにラベルを固定してしまってもいいかもね 机上の空論だから上手くいくかどうか分からないのは許してね 難しく考えすぎているのかもしれないわ 134 名前：デフォルトの名無しさん mailto:sage [2013/12/16(月) 00:06:30.24 .net] こういう事ができればいいんでしょ 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っていうオープンソースソフトが解りやすかった 135 名前：デフォルトの名無しさん mailto:sage [2013/12/16(月) 21:53:44.96 .net] 力学エネルギーに基づくグラフ描画が求めていたもののようです。 まとまった時間を作って、出ているアルゴリズムを読んでみます。 お付き合いしてくださった皆様ありがとうございました。 136 名前：デフォルトの名無しさん [2013/12/28(土) 23:22:37.13 .net] グーグルの検索エンジンのアルゴリズム webblogsakusei.main.jp/seo_taisaku_syukyaku.html 137 名前：デフォルトの名無しさん [2014/01/17(金) 16:44:24.77 .net] ふぇぇ」 138 名前：デフォルトの名無しさん mailto:sage [2014/01/19(日) 15:03:35.30 .net] 計算量のオーダーの考え方で質問です。 (a # b) を a の b 個の下降階乗冪を表す式とし、 (#) は除算 (/) よりも優先順位が高いとします。 x や y は m よりも十分大きい数とすると、 f(m) = x#m / y#m この場合、計算量のオーダーは O(m) と考えていいでしょうか。 139 名前：デフォルトの名無しさん mailto:sage [2014/01/19(日) 22:30:57.31 .net] ダーク構造、エルゴリズム、ディザインパクトに見えたマジで。 140 名前：デフォルトの名無しさん mailto:sage [2014/01/20(月) 22:08:25.07 .net] 下記の問題について、私が考えた方法では計算量が n 乗のオーダーになってしまい、 たいして大きくない数で試しても計算にかなり時間がかかるのですが、 みなさんならどのような解き方をするでしょうか。 [問題] m 枚のカードの束からランダムに x 枚引き（x <= m）、引いたカードに印をつける。 引いたカードを元のカードの束に戻し、再度ランダムに先ほどと同数 x 枚引き、 印がついていなかったら印をつけ、また元の束に戻す。 このように x 枚カードを引いて印を付けて戻す行為を n 回繰り返した後、 m 枚のカードの束に印のついていないカードが p 枚ある確率を求める関数 F(m, x, n, p) を作れ。 141 名前：140 mailto:sage [2014/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 名前：デフォルトの名無しさん mailto:sage [2014/01/20(月) 22:18:46.73 .net] ちょいと質問だけど、有理数で計算してるの？ 143 名前：140 mailto:sage [2014/01/20(月) 23:12:18.37 .net] >>142 私は、関数 R と D と {C(m,x)}^n の計算は任意精度整数で、 関数 F 内の割り算は有理数型で、 そして最後にそれを倍精度浮動小数点型にしています。 144 名前：デフォルトの名無しさん mailto:sage [2014/01/20(月) 23:44:20.55 .net] これってアルゴリズムの問題じゃなくて数学の問題じゃね？ オイラーのガンマとか関係してそうだけど。数学できるやつならパパっと式が出てくるんだろうな。 残念ながら僕は数学ができたという過去形なので無理です。 145 名前：デフォルトの名無しさん mailto:sage [2014/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 mailto:sage [2014/01/21(火) 00:24:59.04 .net] >>144 わたしも、これを代数的に解く方法は知らないのでプログラムで解こうと思いました。 プログラムで解く場合に n 乗よりも低いオーダーのアルゴリズムが存在しないのなら諦めます。 今のところ私が挑戦した限りでは、n 乗のオーダーが限界でした。 147 名前：140 mailto:sage [2014/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 名前：デフォルトの名無しさん mailto:sage [2014/01/21(火) 01:34:30.52 .net] >>145 C(m,p) で選んだp枚に対し、m-p枚からx枚選ぶ過程が一意でなく重複が入ってるから×だな 149 名前：デフォルトの名無しさん mailto:sage [2014/01/31(金) 19:15:00.72 .net] a[0]からa[n-1]までの配列があって、 その中身をコンマで区切って表示したい print a[i] + ',' みたいなことをすると、最後の要素にもコンマが付くので、 これをうまく避けるアルゴリズムは無いものか 150 名前：デフォルトの名無しさん mailto:sage [2014/01/31(金) 19:50:00.15 .net] if (a=next()) { push(a); while (a=next()) push(cat(",",a)); } 151 名前：デフォルトの名無しさん mailto:sage [2014/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 名前：デフォルトの名無しさん mailto:sage [2014/01/31(金) 21:15:03.01 .net] 出力してしまわずに一旦文字列に出して、 出来上がってから最後のコンマを1個削る 153 名前：デフォルトの名無しさん mailto:sage [2014/01/31(金) 21:30:32.04 .net] n が小さければ >>151 の方法でOK。シンプルでわかりやすい。 ただし、if 文で n 回の比較が発生するから、n があまりに大きい場合は >>152 のやり方がいいと思う。 最後の文字を削れない場合は for 文で a[n-2] まで ',' と一緒に出力して、追加で a[n-1] を出力するか。 >>150 は何の言語？ 154 名前：デフォルトの名無しさん mailto:sage [2014/01/31(金) 21:35:58.74 .net] 最初の要素と残りの配列に分ければいいだろと、Haskell なら考える 155 名前：デフォルトの名無しさん mailto:sage [2014/01/31(金) 22:35:19.83 .net] 分ければ簡単なんだけど、同じような処理を2回書く羽目になるんだよな 156 名前：デフォルトの名無しさん mailto:sage [2014/01/31(金) 22:38:32.60 .net] >>149 puts a[0..n-1].join('.') 157 名前：デフォルトの名無しさん mailto:sage [2014/01/31(金) 22:49:27.58 .net] 結局、うまい方法が無いので言語側で join 機能を提供している join があるならそれを使うのが最もスマート 158 名前：SD mailto:sage [2014/02/01(土) 15:47:33.85 .net] String d="" String r=""; for(String b:a){r+=d+b;d=",";} 159 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 16:20:22.09 .net] コンマが先にあると考えて、先頭のコンマを削除する方式だな 毎回同じ値で更新するのが美しくない 160 名前：デフォルトの名無しさん mailto:sage [2014/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 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 17:23:17.66 .net] それが正解だろうな lengthが2回出てくる以外は殆ど無駄がない 162 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 17:47:07.99 .net] printの部分が長いコードなど２つに分けたくない事情があるときは>>158の方がいい。 定数へのポインタを代入するだけなので効率も悪くない。 163 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 18:04:45.52 .net] 長くなくても、似た出力が2箇所あるのは嫌だな コンマ部分だけ出力が別にあるのは構わないけど str = a[i]; if (i < n - 1) {str += ','} こうすれば一箇所 >>151とほぼ同じ 164 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 18:09:57.02 .net] 俺もかつては悩んだがあるとき以降はずっとこう書いてる。 for (int i = 0; i < a.size; i++) { if (i != 0) print(,) print(a[i]) } 165 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 18:53:19.10 .net] 俺ならdo-whileの条件文にカンマ出力ねじ込んで軍事法廷に召喚される 166 名前：デフォルトの名無しさん mailto:sage [2014/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 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 19:46:34.49 .net] は？ 168 名前：デフォルトの名無しさん mailto:sage [2014/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 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 21:03:39.16 .net] それはただのバグだな 170 名前：デフォルトの名無しさん mailto:sage [2014/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 　} 　# 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言語へ移植することも容易いだろう 171 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 23:18:11.99 .net] >>168 この考え方、感じ方は大事だね 例えば、これを範囲を指定してコンマ区切りの文字列を返す関数にしたら 前者ならすんなり行く 172 名前：デフォルトの名無しさん mailto:sage [2014/02/02(日) 00:01:46.64 .net] テキストエディタでコンマ区切りのデータを編集する時に、 どうしてもコンマが余ったり足りなかったりする 173 名前：デフォルトの名無しさん mailto:sage [2014/02/02(日) 00:49:30.38 .net] print (xs[0]) for x in (xs[1..n]) 　print (", " + x) では間違い？ 174 名前：デフォルトの名無しさん mailto:sage [2014/02/02(日) 01:00:24.64 .net] 例えばファイルへの出力に変更した時に、 複数箇所のprintを直して回らないといけない 175 名前：デフォルトの名無しさん mailto:sage [2014/02/02(日) 01:07:52.48 .net] バカ？

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef