＜集大成＞アルゴリズム大辞典

[表示 : 全て最新50 1-99 101- 201- 301- 401- 501- 601- 701- 801- 901- 2chのread.cgiへ]
Update time : 01/21 21:00 / Filesize : 241 KB / Number-of Response : 987
[このスレッドの書き込みを削除する]
[＋板最近立ったスレ＆熱いスレ一覧 : ＋板最近立ったスレ／記者別一覧] [類似スレッド一覧]


↑キャッシュ検索、類似スレ動作を修正しました、ご迷惑をお掛けしました

＜集大成＞アルゴリズム大辞典

1 名前：デフォルトの名無しさん mailto:sage [04/06/03 23:18]: どこにもない強固なスレにしたい
548 名前：デフォルトの名無しさん mailto:sage [2009/11/11(水) 09:43:10 ]: 小数使うなって書かれた上に、>>546 がそれ用の答え書いてくれてるのに
なんでニュートン方の実装例出してるの？
549 名前：デフォルトの名無しさん mailto:sage [2009/11/11(水) 10:39:58 ]: >>546 を「答え」とか
550 名前：デフォルトの名無しさん mailto:sage [2009/11/11(水) 10:49:46 ]: >>548
2の平方根が1とかって意味あんのか？
551 名前：デフォルトの名無しさん mailto:sage [2009/11/12(木) 01:38:30 ]: 以下のような多次元項の因数分解を近似的に行うプログラムを書きたいのですが…、
最小自乗などなら解けるかなと思ったのですが…、どなたかご教授願います。

問題：
ΣCkX^k→Σ(AkXk-Bk)^k+e
すべて実数スカラ値。kの範囲は0<k<n。eは誤差値。^kはk乗の意。
左辺が与えられた時に、eを最小にするAnとBnを求める。
552 名前：551 mailto:sage [2009/11/12(木) 01:58:02 ]: 訂正です
ΣCkX^k→Σ(AkXk-Bk)^k+e
ではなくて
Σ(CkX^k)→Π(AkXk-Bk)^k+e

でした
553 名前：デフォルトの名無しさん mailto:sage [2009/11/12(木) 12:50:07 ]: Σ(CkX^k)→Π(AkX-Bk)^k+e
でなく？
554 名前：551 mailto:sage [2009/11/12(木) 13:38:17 ]: Σ(CkX^k)→Π(AkX-Bk)^k+e です
555 名前：デフォルトの名無しさん mailto:sage [2009/11/13(金) 10:02:20 ]: >>546
それバグってルし
556 名前：デフォルトの名無しさん mailto:sage [2009/11/13(金) 12:28:15 ]: 小数使うなって書かれた上に、>>546 がそれ用の答え書いてくれてるのに
なんでニュートン方の実装例出してるの？
557 名前：デフォルトの名無しさん mailto:sage [2009/11/13(金) 12:42:55 ]: >>556
2の平方根が1とかって意味あんのか？
558 名前：デフォルトの名無しさん mailto:sage [2009/11/14(土) 23:12:53 ]: >>557
なんで無いと思うんだ？
559 名前：デフォルトの名無しさん mailto:sage [2009/11/15(日) 09:52:32 ]: >>558
>>548-550
>>556-557
560 名前：デフォルトの名無しさん mailto:sage [2009/11/15(日) 10:20:04 ]: >>557
いや、そういう仕様だし。
これを平方根だというから誤解が生じるんであって、
「(int)floor(sqrt(x)) の値を float 介さず求める関数を作れ」でしょ。
561 名前：デフォルトの名無しさん mailto:sage [2009/11/16(月) 23:15:10 ]: 単に開平法をさせたいだけじゃないの？
562 名前：デフォルトの名無しさん mailto:sage [2009/11/16(月) 23:33:04 ]: いやいや、ちゃんと >>542 読めよ。
「実数の平方根を超えない最大の整数を返すものとします」
563 名前：デフォルトの名無しさん mailto:sage [2009/11/17(火) 23:52:09 ]: 高速 sqrt 整数でググったらおもしろいの見つけた
整数なら各ビット毎に収束させる事で必要ビット数の半分のループ（32bitなら16)で解がでるのね
564 名前：デフォルトの名無しさん mailto:sage [2009/11/18(水) 02:02:43 ]: >>563
事実上>>545の亜種のような気がするが…
565 名前：デフォルトの名無しさん mailto:sage [2009/11/18(水) 12:28:24 ]: 亜種と言うかまんま
566 名前：デフォルトの名無しさん mailto:sage [2009/11/18(水) 12:43:06 ]: unsigned int isqrt(unsigned int x)
{
unsigned int s, t;

if (x == 0) return 0;
s = 1; t = x;
while (s < t) { s <<= 1; t >>= 1; }
do {
t = s;
s = (x / s + s) >> 1;
} while (s < t);
return t;
}
567 名前：デフォルトの名無しさん mailto:sage [2010/04/14(水) 05:43:19 ]: 安定な内部ソートの中で最も高速なのは何ですか？ちなみに再帰型は不可で。
オレの中ではインサーションソートが一番なんだが、これよりもっと使いやすいのある？
568 名前：デフォルトの名無しさん mailto:sage [2010/04/14(水) 07:48:39 ]: 不安定なソートに副キーを付けてソートするんじゃないの？
高速に安定なソートをしたければ。

再帰が不可ってのはマージソートも不可？
569 名前：デフォルトの名無しさん mailto:sage [2010/04/14(水) 08:01:42 ]: そもそも使いやすいって何だ？
570 名前：デフォルトの名無しさん mailto:sage [2010/04/14(水) 08:08:29 ]: >>569
実装が容易(=コード量が少ない)とか、並列化が容易とか、オンラインとか、構造に依存しないとか。
571 名前：デフォルトの名無しさん mailto:sage [2010/04/14(水) 08:27:51 ]: 高速かつ使いやすい
矛盾は無いが、現実には・・・・・
572 名前：デフォルトの名無しさん mailto:sage [2010/04/14(水) 09:02:29 ]: ソートに限らずオンライン総括処理の構築手引書
欲しいな
573 名前：デフォルトの名無しさん mailto:sage [2010/04/14(水) 09:07:10 ]: アルゴリズムがオンラインってどういう意味？
574 名前：デフォルトの名無しさん mailto:sage [2010/04/14(水) 09:25:22 ]: >>573
ソートだったら、開始する時点で対象データが不完全(あとで増えるかもしれない)でもいいってこと。
575 名前：デフォルトの名無しさん mailto:sage [2010/04/14(水) 09:38:09 ]: ソート中にデータを追加しても破綻しない、っつーことだよな？
入力待ちしつつ、入力されたものを随時処理してソート済みデータに並べられるようなヤツね。

while (fgets(buf, sizeof(buf), stdin) != EOF) {
add_with_sort(array, buf);
}

みたいな。
576 名前：デフォルトの名無しさん mailto:sage [2010/04/14(水) 21:08:57 ]: >>575
そういう言い方をするとアルゴリズムというより、パターンって気がしないか？

単にオンラインアルゴリズムと呼んだ場合は、入力の随時処理じゃなくて、
とあるアルゴリズムで入力データ列を取り扱う時、全体を捜査しなくても
実行できるアルゴリズムのことだろう。
もちろん途中で入力が行われてもアルゴリズム自体はそれに対して特別な
処理を行わず、入力された値は単にデータ列の最後に追加されるだけ。

それはともかく、プログレスバーの表示を、オンラインアルゴリズムで処理する
うまい方法はないものだろうか。
もちろん完全な処理が無理なのは分かっているが…大量のファイルを取り扱うときに
いつも悩んでしまう。
577 名前：デフォルトの名無しさん mailto:sage [2010/04/14(水) 21:22:37 ]: 一定時間または一定時間比ごとに
進捗状況の評価方法や表示方法を再検討して
適切なものに切り替えていく…とか？
578 名前：デフォルトの名無しさん mailto:sage [2010/04/14(水) 22:20:33 ]: >>567
In place mergeの亜種が現在最速かな。
579 名前：デフォルトの名無しさん [2010/04/18(日) 00:42:41 ]: >>568

マージソートは再帰なしでも実装できるが
580 名前：デフォルトの名無しさん mailto:sage [2010/04/18(日) 13:03:03 ]: 好きなソートはマージソートでつ！！
581 名前：デフォルトの名無しさん mailto:sage [2010/04/25(日) 16:42:26 ]: 0.3｜0.2| 0.1
-----------
0.4 | 0.2| 0.2
----------
0.1 | 0.5| 0.3

みたいな3x3バッファがあって
座標をxとyであらわして
ただxyは整数ではなく0.0～1.0の微笑範囲で
示された座標の値を計算するにはどうすればいいんだろう
手法の名前でも分かれば検索出来るんだけど
こういう計算って何て呼ぶのか分からない
582 名前：デフォルトの名無しさん mailto:sage [2010/04/25(日) 16:46:28 ]: 点反る
583 名前：581 mailto:sage [2010/04/25(日) 16:51:09 ]: 欲しい値は直接的な中の数字じゃなくて
中の数字を広大な平面に広げた時になめらかに起伏した山と谷になるでしょ
その広大な座標の中での実際の数字が知りたい
584 名前：デフォルトの名無しさん mailto:sage [2010/04/25(日) 16:56:11 ]: 補間したいってことだよね
バイリニア補間やらスプライン補間やら好きなの使え
585 名前：デフォルトの名無しさん mailto:sage [2010/04/25(日) 17:17:33 ]: >>584
ああ　そうか　補完と同じことか
ありがとう助かった
586 名前：デフォルトの名無しさん mailto:sage [2010/05/05(水) 14:07:08 ]: HashTreeってどんなアルゴリズムなのですか？
587 名前：デフォルトの名無しさん mailto:sage [2010/05/05(水) 14:44:33 ]: en.wikipedia.org/wiki/Hash_tree
588 名前：デフォルトの名無しさん [2010/05/21(金) 19:32:09 ]: オライリーのアルゴリズムクイックリファレンス
の表紙がグロテスクで買うのに躊躇(>_<)
www.amazon.co.jp/gp/product/images/4873114284/ref=dp_image_0?ie=UTF8&n=465392&s=books
何の虫？
一瞬、ゴキブリかと思ってしまった。
589 名前：デフォルトの名無しさん mailto:sage [2010/05/21(金) 19:41:46 ]: ゴキブリはこんな肢は持ってないだろw

ザリガニか何かの一種？
590 名前：デフォルトの名無しさん mailto:sage [2010/05/21(金) 20:05:29 ]: オライリー、オライリー
って健康器具の夢を見た
591 名前：デフォルトの名無しさん mailto:sage [2010/05/21(金) 21:06:07 ]: >>590
お前のレスのおかげで忘れかけてた何かを思い出した
真中で折れ曲がる簡易ベッドみたいなやつを思い出した

頭の中から離れなくなったぞ、どうしてくれる
592 名前：デフォルトの名無しさん mailto:sage [2010/05/22(土) 06:19:10 ]: >>589
ヤドカリだよ
593 名前：デフォルトの名無しさん [2010/05/22(土) 23:00:07 ]: 円盤同士の衝突の物理演算についてお聞きします。

衝突した際の平面移動については実装できたのですが、
円盤の回転については、これといったアルゴリズムが見つかりません。

壁や円盤に衝突した円盤の角速度の求め方は、
どのようなものでしょうか？
594 名前：デフォルトの名無しさん mailto:sage [2010/05/22(土) 23:25:43 ]: たとえば、だけど、まずは円盤自身は回転していないとして、
接触した瞬間の微小時間における「こすれる速度」を求める。
速度vで45度で壁に衝突したなら、0.7v （√2 / 2）。
それに適当な摩擦係数で、円盤自身の回転も加味してやればいいんじゃないかな？

ていうか物理板あたりにシミュレーションのスレが...ないなw
595 名前：デフォルトの名無しさん [2010/05/22(土) 23:29:43 ]: ぶつかった点同士の直進速度？のやり取りと考えればいんじゃね？
角速度から円周での速度に置き換えてさ
596 名前：デフォルトの名無しさん mailto:sage [2010/05/22(土) 23:58:49 ]: シミュ板があるだろ？
597 名前：デフォルトの名無しさん mailto:sage [2010/05/23(日) 01:08:53 ]: char[H][W] の行列を高速に転置させるアルゴリズムって無いかな。
float や double とかなら数学ライブラリであるんだけど、char だと
for(int y = 0; y < H; ++y)
for(int x = 0; x < W; ++x)
dst[x][y] = *(++src);
とか順番に入れていく方法しか思いつかない。
598 名前：デフォルトの名無しさん mailto:sage [2010/05/23(日) 10:56:20 ]: dst[x][y] でアクセスしてた所を dst[y][x] でアクセスするようにすればいい。
599 名前：デフォルトの名無しさん mailto:sage [2010/05/23(日) 11:35:28 ]: >>597
それって、アルゴリズムはいいとして、
*(++src) って src をインクリメントしたものを参照してるよね？
分かってるんならいいけど。
600 名前：デフォルトの名無しさん mailto:sage [2010/05/23(日) 20:37:32 ]: *dst++ = *src++;
で一つのイディオムとして覚えてる。
601 名前：デフォルトの名無しさん [2010/08/12(木) 15:25:03 ]: 上げ
602 名前：デフォルトの名無しさん mailto:sage [2010/09/03(金) 12:10:05 ]: 数値計算の分野なんですが、c^(1/2/n)を求めるアルゴリズムはどういうのがあるのでしょうか。
いわゆるcの累乗根 c^(1/2n)（但しnは2の倍数）です。
ニュートン法で愚直に求める以外だと、power法ぐらいしか思い浮かびませんでした。
cは実数を考えてますが複素数のアルゴリズムでも構いません。
603 名前：デフォルトの名無しさん mailto:sage [2010/09/03(金) 19:01:09 ]: > c^(1/2n)（但しnは2の倍数）

つまりc^(1/m)（但しmは4の倍数）か。
604 名前：デフォルトの名無しさん mailto:sage [2010/09/03(金) 19:54:28 ]: こんな過疎スレで聞いたのが間違いだったようだな
605 名前：デフォルトの名無しさん mailto:sage [2010/09/03(金) 20:13:01 ]: m9
606 名前：デフォルトの名無しさん mailto:sage [2010/09/04(土) 08:19:34 ]: ニュートン法でいいんじゃないの？
607 名前：デフォルトの名無しさん mailto:sage [2010/09/04(土) 09:46:55 ]: >>602
2の倍数ではなくて c^(1/n)で n=2^kのまちがいでした。
つまり c^(1/2), c^(1/4), c^(1/8), c^(1/16)ですがこれは実装できました。
c^(1/6)などこの方法では別のアルゴリズムに切替えることになるので２の倍数は私が勘違いしてたようです。
もともとニュートン法は代数方程式の求根(しかも根は実数)で累乗根 c^(1/n)を求めるのに特化した算法ではありません。
実際に使うcは複素数なのでニュートン法以外で累乗根を求めるアルゴリズムを所望します。
608 名前：デフォルトの名無しさん mailto:sage [2010/09/04(土) 10:41:18 ]: ja.wikipedia.org/wiki/%E5%86%AA%E6%A0%B9
609 名前：デフォルトの名無しさん mailto:sage [2010/09/25(土) 18:32:00 ]: Introduction to algorithmsにあるamortized analysisがどんな訳になるのかと思って
「アルゴリズムイントロダクション」を見たら、ならし解析（だったっけ）と書いてあった。

amortizeってそんな意味があるの？
610 名前：デフォルトの名無しさん mailto:sage [2010/09/26(日) 18:43:11 ]: >>609
英辞郎引け馬鹿者が
611 名前：デフォルトの名無しさん mailto:sage [2010/09/26(日) 19:19:32 ]: 英辞郎にはならし・分割の意味が出ていた。ありがとう。goo辞書で最初見ていたのだが、その様な意味が見当たらなかったのでね。
612 名前：デフォルトの名無しさん [2010/10/28(木) 20:47:40 ]: 最大N文字で最大M個の文字列を1～Mにマッピングするようなハッシュ関数を作りたいんですが
そんな都合のイイアルゴリズムって有りますか？
613 名前：デフォルトの名無しさん mailto:sage [2010/10/28(木) 20:54:26 ]: 完全ハッシュ
614 名前：デフォルトの名無しさん [2010/10/29(金) 18:29:54 ]: 問題投下/~

４つの相異なる３桁の整数があり、百の位は全て等しい
このうち３つの数は４つの数の和の約数になっている
このような４つの数の組を求めよ

（開智中2009入試問題）

1から8までの8つの数字を並べて、8桁の数を作る。その数の各位に、アイウエオカキクと名前をつける。
2桁の数「アイ」は2で割り切れ、3桁の数「アイウ」は3で割り切れる。
4桁の数「アイウエ」は4で割り切れ、5桁の数「アイウエオ」は5で割り切れる。
6桁の数「アイウエオカ」は6で割り切れ、7桁の数「アイウエオカキ」は7で割り切れ, 8桁の数「アイウエオカキク」は8で割り切れる。

8桁の数を答えよ。
615 名前：デフォルトの名無しさん mailto:sage [2010/10/30(土) 14:39:19 ]: >>614
def check(n, a, b, c, d)
a = 100 * n + a
b = 100 * n + b
c = 100 * n + c
d = 100 * n + d
sum = a + b + c + d
count = 0
count += 1 if sum % a == 0
count += 1 if sum % b == 0
count += 1 if sum % c == 0
count += 1 if sum % d == 0
return count == 3
end
(1..9).each {|n|
(0..99).each {|a|
(0..99).each {|b| next if b == a
(0..99).each {|c| next if c == a || c == b
(0..99).each {|d| next if d == a || d == b || d == c
print a, " ", b, " ", c, " ", d, " \n" if check(n, a, b, c, d)
}
}
}
}
}

すんげー遅い。アルゴリズムとはよべないｗ
616 名前：デフォルトの名無しさん mailto:sage [2010/10/30(土) 14:44:17 ]: rubyに実用的な「速度」を求めてはいけない。
617 名前：デフォルトの名無しさん [2010/10/30(土) 21:22:16 ]: >>615

codepad.org/CxbENTUj
618 名前：デフォルトの名無しさん mailto:sage [2010/10/31(日) 01:11:19 ]: >>614
中学入試でそんな難しい問題が出るのかよw
619 名前：デフォルトの名無しさん [2010/10/31(日) 05:04:08 ]: >>617
下手なコードだなあ
620 名前：デフォルトの名無しさん mailto:sage [2010/10/31(日) 05:38:32 ]: >>615下
総当りしなくても求められそうだけど
codepad.org/U6V8vTuL
621 名前：620 mailto:sage [2010/10/31(日) 05:39:28 ]: >>617のアンカー参考にしたらずれてたorz
>>614だったか
622 名前：デフォルトの名無しさん [2010/10/31(日) 05:56:15 ]: >>620
うまいな

codepad.org/VofqW1k0
623 名前：デフォルトの名無しさん [2010/10/31(日) 07:29:41 ]: >>622
下手なコードだなあ
624 名前：デフォルトの名無しさん mailto:sage [2010/10/31(日) 10:54:56 ]: >>614
ideone.com/v5yBW
こんなもんかな。
625 名前：デフォルトの名無しさん mailto:sage [2010/10/31(日) 10:56:14 ]: >>616
同じ書き方なら、Cとかでやっても3秒くらいかかるね。
早くしたければ、動的計画法的なアルゴリズム使わなきゃダメだけど、ものすごい面倒。
626 名前：デフォルトの名無しさん mailto:sage [2010/10/31(日) 11:44:22 ]: >>624
大げさすぎて吹いたｗ

>>617
ああ、やっぱそうやって b = a + 1方式で減らせるのか。

>>625
まぁほんとは、そういう何らかの気の利いたのを求めてるんだろうけど。
627 名前：デフォルトの名無しさん mailto:sage [2010/10/31(日) 13:04:53 ]: >>624 に追加で： ideone.com/pWegj

>>626
問題文をそのまま書いたらそうなった。
問題文を手続きに翻訳とかしたくない。
628 名前：デフォルトの名無しさん [2010/10/31(日) 18:06:14 ]: カスばっか
629 名前：デフォルトの名無しさん mailto:sage [2010/10/31(日) 18:26:08 ]: ↑カスがまた一人
630 名前：デフォルトの名無しさん mailto:sage [2010/10/31(日) 22:38:09 ]: >>614 後半
2桁の数「アイ」は2で割り切れ → イ = 2, 4, 6, 8
4桁の数「アイウエ」は4で割り切れ → エ = 2, 4, 6, 8
5桁の数「アイウエオ」は5で割り切れる → オ = 5
6桁の数「アイウエオカ」は6で割り切れ → カ = 2, 4, 6, 8
8桁の数「アイウエオカキク」は8で割り切れる → ク = 2, 4, 6, 8
イエカクで 2, 4, 6, 8 を使うから、アウキは 1, 3, 7 (5 はオ)

ということで、こんなもんかな →　codepad.org/OTEAlb7U
631 名前：デフォルトの名無しさん [2010/10/31(日) 22:40:13 ]: 下手なコードだなあ
632 名前：デフォルトの名無しさん mailto:sage [2010/11/01(月) 13:30:12 ]: >>631みたいなレスにお手本が添えられたのを一度も見たことが無い。
633 名前：デフォルトの名無しさん mailto:sage [2010/11/01(月) 18:58:48 ]: NP問題のようなものだって、研究室の先輩が言ってた。

コードがへたくそか否かを示すことは多項式時間でできるが、
上手なコードを書くことはできない。
634 名前：デフォルトの名無しさん mailto:sage [2010/11/02(火) 05:28:27 ]: アルゴリズムがエレガントかどうかを判定するアルゴリズムが存在したら、
エレガントなアルゴリズムを吐き続けるアルゴリズムが書けるぞ。
635 名前：620 ◆mNdSWHMiXkWr mailto:sage [2010/11/02(火) 06:36:30 ]: >>614上
3つの数の選び方ってどの組み合わせでも成立しないとダメ？
codepad.org/D8bessOz
636 名前：デフォルトの名無しさん [2010/11/02(火) 06:48:52 ]: で結局どのやり方が美しいの？
637 名前：デフォルトの名無しさん mailto:sage [2010/11/02(火) 17:06:30 ]: 美しいかどうかを判定するアルゴr(ry
638 名前：デフォルトの名無しさん mailto:sage [2010/11/02(火) 17:37:43 ]: >>634
それ、チャイティンがパラドックス指摘してただろ
639 名前：デフォルトの名無しさん mailto:sage [2010/11/02(火) 20:06:47 ]: >>634
そうなるとまずエレガントなアルゴリズムの定義が必要になる
640 名前：デフォルトの名無しさん mailto:sage [2010/11/02(火) 20:10:03 ]: ／￣￣￣￣￣＼
|　・　Ｕ　　　　　　|
| |ι　　　　　　　|つ
Ｕ｜｜￣￣｜｜

ぼくエレガント
641 名前：デフォルトの名無しさん mailto:sage [2010/11/02(火) 20:53:32 ]: 福井県か
642 名前：デフォルトの名無しさん [2010/11/02(火) 20:57:16 ]: elegante void func(void);
643 名前：デフォルトの名無しさん mailto:sage [2010/11/03(水) 05:38:31 ]: >>639
> エレガントなアルゴリズムの定義
「同機能のプログラムの中で、最小ビットのプログラム」.

しかしそれは、ベリーのパラドックスと同じように、容易に矛盾をきたす。
644 名前：デフォルトの名無しさん mailto:sage [2010/11/03(水) 13:17:30 ]: 説明の必要がないアルゴリズムは美しい、という観点もあるな
要求仕様とアルゴリズムがあまりにも乖離してると
保守性が悪くて難儀する
645 名前：デフォルトの名無しさん [2010/11/03(水) 16:18:50 ]: 2^nの下3桁が888になるnを5つあげろ

下k桁で考える場合は？
646 名前：デフォルトの名無しさん mailto:sage [2010/11/03(水) 16:20:35 ]: それエレファントや！

∧＿∧∩))
(　・∀・)彡　　パーン！
　 ((⊂彡☆∩　 _, ,_
　　　⊂(⌒⌒（；｀Д´）
　　　　　　｀ヽ_つ ⊂ノ ←>>640
647 名前：デフォルトの名無しさん [2010/11/03(水) 16:25:47 ]: 僕のお兄さん、西暦wxyz年の生まれです。
1997年、僕のお兄さんの年齢は、w+x+y+zになりました。
僕のお兄さんは何歳になったでしょう？
648 名前：デフォルトの名無しさん [2010/11/03(水) 16:30:33 ]: a^4+b^4+c^4+d^4=e^4が成り立つような整数a,b,c,d,eの組を見いだせ

これはいける？
649 名前：デフォルトの名無しさん mailto:sage [2010/11/03(水) 16:34:43 ]: 1997 - 9*4 = 1961
w = 1, x = 9
1997 - (1+9+9+9) = 1969
1997 - (1+9+0+0) = 1987
よって、y = 7,8,9
1997 - (1900 + 10y + z) = 10 + y + z
2z = 87 - 11y ≧ 0
y = 7, z = 5

1975年生まれ。1997年で、22歳。
650 名前：デフォルトの名無しさん [2010/11/03(水) 16:36:51 ]: 半径１の円に内接する正９角形がある。
この正９角形の周上にすべての頂点を持つ正多角形の
辺数n を５つ求めよ。
さらに各n に対し、そのような正n 角形の例を１つあげて１辺の長さを求めよ。
651 名前：デフォルトの名無しさん mailto:sage [2010/11/03(水) 16:42:24 ]: (0..9).each {|w|
(0..9).each {|x|
(0..9).each {|y|
(0..9).each {|z|
print(w, x, y, z, " ", (w + x + y + z), "\n") if 1997 - (1000 * w + 100 * x + 10 * y + z) == w + x + y + z
}
}
}
}
652 名前：デフォルトの名無しさん mailto:sage [2010/11/03(水) 16:55:37 ]: >>650
n = 3 の時、一辺の長さ無数にないか。
653 名前：デフォルトの名無しさん [2010/11/03(水) 17:00:09 ]: >>652
辺の長さについては一例でいいのでしょうね
654 名前：デフォルトの名無しさん [2010/11/03(水) 17:13:20 ]: よっこらせっくす
655 名前：デフォルトの名無しさん [2010/11/03(水) 17:23:20 ]: 誤爆ごめんねー
656 名前：デフォルトの名無しさん [2010/11/09(火) 02:41:51 ]: 特定の比率でランダムな値を返すアルゴリズムってないかな
例えば、3:2:2:1の比率でfunc[0],func[1],func[2],func[3]をランダムに取得したい
さらに言うと比率も項数も動的に変化する
657 名前：デフォルトの名無しさん mailto:sage [2010/11/09(火) 02:58:55 ]: r = 乱数 % (3+2+2+1)
if r < 3 then i = 0
else if r < 5 then i = 1
else if r < 7 then i = 2
else i = 3
func[i]
じゃダメ？
658 名前：デフォルトの名無しさん mailto:sage [2010/11/09(火) 03:39:41 ]: だめ
659 名前：デフォルトの名無しさん mailto:sage [2010/11/09(火) 05:27:55 ]: struct R{int fq[4];};
void init(R*x){int ad[]={3,2,2,1}; x->fq[0]=ad[0],x->fq[1]=ad[1],x->fq[2]=ad[2],x->fq[3]=ad[3];}
int rnd(R*x){
int r; if(x->fq[0]+x->fq[1]+x->fq[2]+x->fq[3]<=0)init(x);
do{r=rand()*4;}while(x->fq[r]<=0); x->fq[r]--; return r;}

R seed; init(&seed);
func[rnd(&seed)];
660 名前：デフォルトの名無しさん mailto:sage [2010/11/09(火) 10:15:32 ]: 比率に合わせた境界値を持つ配列作ってそれで判定するってのは？
661 名前：デフォルトの名無しさん mailto:sage [2010/11/09(火) 10:26:11 ]: a = [] + ([func[0]] * 3) + ([func[1]] * 2) + ([func[2]] * 2) + ([func[3]] * 1)
f = a[乱数 % (3+2+2+1)]
f()
662 名前：デフォルトの名無しさん mailto:sage [2010/11/09(火) 17:58:11 ]: int a[]={3,2,2,1},x,y;
do{x=r()%size(a);y=r()%max(a);}while(a[x]<=y);
f[x]();
663 名前：デフォルトの名無しさん mailto:sage [2010/11/12(金) 23:27:03 ]: GAで、遺伝子プールの中から引っ張ってくるときにやってなかったっけ
664 名前：デフォルトの名無しさん mailto:sage [2010/11/19(金) 21:40:09 ]: 純粋なヒープの使い道って、順序付きキューしか無い？
665 名前：デフォルトの名無しさん [2010/12/01(水) 15:36:00 ]: 最小完全ハッシュの作り方がわかりません
ハッシュ関数のパラメーターをループでまわしながら見つかるまで耐えるんですか？
666 名前：デフォルトの名無しさん mailto:sage [2010/12/02(木) 18:10:58 ]: >>664
純粋なヒープとヒープソートってどこが違うの？
667 名前：デフォルトの名無しさん mailto:sage [2010/12/02(木) 18:57:15 ]: ヒープはデータ構造。
ヒープソートはヒープを使った整列アルゴリズム。
668 名前：デフォルトの名無しさん mailto:sage [2010/12/02(木) 19:23:19 ]: >>665
gperfとか実装があるんだから、おそらくたいていの場合は実用になるような
アルゴリズムはあるんだろうと思われる。
669 名前：デフォルトの名無しさん mailto:sage [2010/12/10(金) 09:48:22 ]: どんなビット列を与えても必ず幾らかは圧縮される圧縮アルゴリズムって有りますか？
670 名前：デフォルトの名無しさん mailto:sage [2010/12/10(金) 09:56:27 ]: ない
671 名前：デフォルトの名無しさん mailto:sage [2010/12/10(金) 09:57:29 ]: シャノン限界超えろと？
672 名前：デフォルトの名無しさん mailto:sage [2010/12/10(金) 17:19:19 ]: 数学的に考えたら、そんなものがありえないことはすぐにわかると思うよ。
673 名前：デフォルトの名無しさん mailto:sage [2010/12/10(金) 20:58:33 ]: 完全にランダムなビット列は圧縮不能A
674 名前：デフォルトの名無しさん mailto:sage [2010/12/10(金) 21:13:43 ]: 圧縮したものをまた圧縮して・・・最後は全部なくなっちゃいそうだなw
675 名前：デフォルトの名無しさん mailto:sage [2010/12/10(金) 21:37:45 ]: 別の所にデーターベースを居て、そのインデックス値が圧縮したデータ。
データーベースのレコードが少ないなら、INT数値で表現可能。
676 名前：デフォルトの名無しさん [2010/12/10(金) 21:47:24 ]: それではＩＮＴより小さいビット列が圧縮できない
つーか1ビットのデータを圧縮することが出来ないから完全に圧縮できるアルゴリズムは存在しない
677 名前：デフォルトの名無しさん mailto:sage [2010/12/10(金) 21:48:19 ]: アルゴリズム(算術・算法）という感じではないな
678 名前：デフォルトの名無しさん mailto:sage [2010/12/10(金) 21:56:15 ]: >>675
URL短縮サービスなんかがまさにそれだよね。
679 名前：デフォルトの名無しさん mailto:sage [2010/12/10(金) 22:06:51 ]: 質問者は情報理論入門の教科書を買って嫁！
680 名前：デフォルトの名無しさん mailto:sage [2010/12/10(金) 22:14:21 ]: 命題論理式を線形時間でCNFにする方法はありますが，
DNFにする方法はないでしょうか？

あったら，命題論理式の充足可能性が線形時間で解ける，ということはないのかな？
681 名前：デフォルトの名無しさん mailto:sage [2010/12/10(金) 23:05:29 ]: >>675
それって辞書方じゃない？
682 名前：デフォルトの名無しさん mailto:sage [2010/12/10(金) 23:22:09 ]: どちらかと云えばハッシュ出しの方かな
683 名前：デフォルトの名無しさん mailto:sage [2010/12/11(土) 02:25:07 ]: >>675のような回答を期待していたとしたら>>669は質問の仕方がまずい
684 名前：デフォルトの名無しさん mailto:sage [2010/12/11(土) 04:57:47 ]: つ[THcomp]
685 名前：デフォルトの名無しさん mailto:sage [2010/12/11(土) 12:36:54 ]: THCompは1ビットだけしか違わないような
ファイルを作りまくったら、
あっという間に限界数に達するでしょ

110a000f Winodws10_Ult.iso
これ解凍してみて
686 名前：デフォルトの名無しさん mailto:sage [2010/12/11(土) 19:09:59 ]: 範囲を扱うのに適したデータ構造ってありますか
こんな感じ

和集合
　[1-4]と[2-5]を混ぜると[1-5]
　[1-2,5-6,8-10]と[3-4,11-13]を混ぜると[1-6,8-10,11-13]
差集合
　[1-10]から[3-4]を削除して[1-2,5-10]
検索
　[1-10,20-30]から15を探す

わりと利用価値はあると思うんですが
こういうのってないですかね？
687 名前：デフォルトの名無しさん mailto:sage [2010/12/11(土) 19:30:23 ]: 集合を扱うデータ構造を使って、扱う要素を自然数に特化して、
"[1-6,8-10,11-13]" みたいな出力をおこなうメソッドを追加する、とかする。私なら。

要素の数が何万とかになるんだったら考え直すけどね。
688 名前：デフォルトの名無しさん mailto:sage [2010/12/11(土) 19:41:03 ]: 範囲の中に空乏の範囲をリストで持つだけじゃん
struct X{int max,min;struct r{int MAX,MIN;,struct r*next;}*hole;};
689 名前：デフォルトの名無しさん mailto:sage [2010/12/11(土) 19:43:44 ]: >>686
昔、十年位前に同じような発想で同じようなもの作ったことあるわ。
はっきり思い出せないけど。
690 名前：デフォルトの名無しさん [2010/12/11(土) 20:01:36 ]: 変貌じゃなくて必然
691 名前：デフォルトの名無しさん mailto:sage [2010/12/11(土) 20:37:19 ]: >>686
> わりと利用価値はあると思うんですが

具体的に、どういうシーンでどういう利用方法（需要）があるの？
いくつか挙げてみて

アルゴリズムとデータ構造というのは、
なにか問題を解決するために生まれるものだからね
その解決したい問題が具体的に無ければ、たいてい話は発展せず、
あやふやなまますぐに消えるよ

問題が具体的にあって、それがみんなの興味を惹けば、
データ構造から、それを使ったアルゴリズム、
計算量の話まで発展する場合もある
692 名前：デフォルトの名無しさん mailto:sage [2010/12/11(土) 20:49:01 ]: >>691
自分が使おうと思ってるのは、繰り返し要素付のカレンダーの実装です
探索や追加削除の速度よりも、和集合/差集合が早いデータ構造だと嬉しいです

オレオレ実装なら自分でも多分作れますが
よく知られたデータ構造は無いんですかね？

コンテナの要素をRange<T>型にして
T型の大小の比較関数と、精度関数があれば
ジェネリックに出来ると思うんですよ
(比較関数だけだと
　1-3と3-4はくっつけられるが
　1-2と3-4はくっつけられない)
693 名前：デフォルトの名無しさん mailto:sage [2010/12/11(土) 21:54:30 ]: >>688 の言うように、素直に範囲のリストで考えた方が
和集合/差集合の演算が速くて楽だと思う。

範囲の先端のインデックスと、終端のインデックスの対をリストにして持つ。
[(先端0, 終端0), (先端1, 終端1), (先端2, 終端2), ...]
ただし、終端i < 先端j (i<j) として常に昇順に並べておく。

<和演算>
入力 :
A [(as0, ae0), (as1, ae1), (as2, ae2), ...]
B [(bs0, be0), (bs1, be1), (bs2, be2), ...]
C [空]
結果 :
C [(cs0, ce0), (cs1, ce1), (cs2, ce2), ...]

計算 :
<1> A と B の全要素を先端インデックスの昇順でひとつのリスト X に並べる
<2> X から先頭要素 (xsi, xei) を切り出して C の後尾要素の後ろに追加する
<3> X の先頭要素 (xsj, xej) を切り出し、C の後尾要素 (csi, cei) と比較する
if cei < xsj then
C の後尾要素の後ろに (xsj, xej) を追加する
else
(csi, cei) を (min (csi, xsi), max (cej, xej)) に変更する
<4> X の要素が残っていれば <3> へ

X を作りたくなければ、ループの各ステップにおいて A B の先頭要素の
先端インデックスが小さい方を選んで (xsj, xej) とすればいい。
694 名前：デフォルトの名無しさん mailto:sage [2010/12/11(土) 22:30:42 ]: 詳しく書いて頂いてありがとうございます
A,Bがソート済ならCもソート済になると思うので、
実質和集合を取る操作はO(A+B)=O(N)かな？
ソートは先端の昇順、終端の降順にして
<2>の追加時にある程度処理しておけば計算量的には同じだけど少しだけ速く出来そうです
和集合O(N),探索O(N),追加O(N)ですね

ちょっと実装してみます
695 名前：デフォルトの名無しさん mailto:sage [2010/12/11(土) 22:37:01 ]: 否定的な意見もあるが、私はこの範囲集合の問題は十分汎用性があると思う。
アルゴリズムとしてはそれほど難しいものにはならないだろうし、それほど深い議論には
発展しないだろうが、ジェネリックで実装された使いやすいクラスにでもまとまれば、
使用する機会もあるだろう。
696 名前：デフォルトの名無しさん mailto:sage [2010/12/11(土) 23:05:39 ]: Range<T>クラスは自分もよく作る。
ただそれ以上の汎用的な物は作ったことがないな。
使うケースもそうないし。
697 名前：デフォルトの名無しさん mailto:sage [2010/12/11(土) 23:15:12 ]: AppKit にある NSRange だな。
698 名前：デフォルトの名無しさん mailto:sage [2010/12/11(土) 23:41:07 ]: ObjectiveCは読めないっす
Javaで手抜きジェネリック版を書いてみたけど
codepad、今落ちてます？アクセスできない
699 名前：デフォルトの名無しさん mailto:sage [2010/12/11(土) 23:46:43 ]: >>697
というかNSIndexSetか
700 名前：デフォルトの名無しさん [2010/12/12(日) 02:33:59 ]: これ大学のプログラム入門でやったわ
授業内容がif文とは～とか５分ぐらい説明してでは後は皆さんで自習してくださいって感じの超手抜き
なのにレポートがこれ実装できないと出来ないっぽい問題で唖然とした
701 名前：デフォルトの名無しさん mailto:sage [2010/12/12(日) 03:13:15 ]: 大学は教えてもらう場所じゃないよ池沼
702 名前：デフォルトの名無しさん [2010/12/12(日) 03:19:18 ]: ひょっとして馬鹿ですか？
大学は教えてもらう場所でもありますよ
703 名前：デフォルトの名無しさん mailto:sage [2010/12/12(日) 09:51:53 ]: バカだろうな。
せっかくの授業料をドブに捨てて、独学しましたとか自慢するバカ。
よくいるよねw
704 名前：デフォルトの名無しさん mailto:sage [2010/12/12(日) 10:07:00 ]: 日本語でおか
705 名前：デフォルトの名無しさん mailto:sage [2010/12/12(日) 14:31:40 ]: >>702
その受け身な態度じゃ何も身につかないってw
ほんとに「学び方」知らないのか？
706 名前：デフォルトの名無しさん [2010/12/12(日) 15:03:46 ]: と知恵遅れが言っております
707 名前：デフォルトの名無しさん [2010/12/12(日) 15:13:22 ]: 大学は教えてもらう場所ではない
つまり講義形式の勉強は存在しないと主張するわけですか？
ひょっとして頭おかしいんじゃないですか？もう一度よく確認してください
教えてもらう講義形式、参加型のゼミや実験、自習もなにもかもひっくるめて大学でしょう
そもそも読書による独学も直接的な対話が無いだけで教えてもらっていることには違いは無いというのに
すべてが独力で学べるものであり、学生は独力で勉強するものであると考えているなら一度脳を解剖して検査してもらったほうが良いですよ
708 名前：デフォルトの名無しさん mailto:sage [2010/12/12(日) 15:14:33 ]: ageるなカス
709 名前：デフォルトの名無しさん mailto:sage [2010/12/12(日) 15:17:57 ]: ageとかいまだに拘るやついるんだ
専ブラで見れば実際の順位なんてあってないようなもんなのに
710 名前：デフォルトの名無しさん mailto:sage [2010/12/12(日) 15:21:35 ]: >>707
教えてもらう場所じゃない、学びに行く場所だよ

>>709
専ブラで見ないような奴が寄って来ないようにするためにsageるんだよ
711 名前：デフォルトの名無しさん [2010/12/12(日) 15:46:58 ]: せんブラも知らんような情弱がこんな僻地にくるかねｗ
もしかして業務でもカスみたいなオーバーヘッドで騒ぎ立てるタイプ？
712 名前：デフォルトの名無しさん mailto:sage [2010/12/12(日) 15:56:09 ]: たかが専ブラで偉ぶるバカってなんなの？
ショーもない時代遅れのテクニックで得意になるタイプ？
713 名前：デフォルトの名無しさん [2010/12/12(日) 16:02:40 ]: 偉ぶるｗテクニックｗｗｗ笑わせんなｗｗｗｗｗ
714 名前：デフォルトの名無しさん mailto:sage [2010/12/12(日) 16:28:47 ]: 大学で教えて貰うのもありだよ。その時間を社会で揉まれつつ自ら学ぶのに使うことができる人間は少ないだろうからね。
715 名前：デフォルトの名無しさん mailto:sage [2010/12/12(日) 16:48:07 ]: もし大学が教育をする場所であるなら、
>>700 の講師の態度は教育者として良くないと思う。

でも、大学は学ぶ場所だから、レポートを提出しろと言われたら、
提出期限までにあらゆる手段を使って精一杯努力して学ぶのが本来の姿だよね。
その時間をしっかり取れるようにするのは大学側の責任だが、
そういう仕組みになっていない大学では、生徒は困惑するな。
>>700 の大学ではそうだったのかも知れんね。
716 名前：デフォルトの名無しさん mailto:sage [2010/12/12(日) 16:55:10 ]: たぶん知れんね。
717 名前：デフォルトの名無しさん [2010/12/12(日) 17:09:38 ]: 範囲の扱い。和はいいけど積になると速い方法が見つからん
718 名前：デフォルトの名無しさん mailto:sage [2010/12/12(日) 17:15:57 ]: >>717
範囲の積ってどういう演算だっけ
719 名前：デフォルトの名無しさん [2010/12/12(日) 17:23:44 ]: ベン図でいうと全部重なってるところ
{ [1,2), [4,5] } * { [1,4] } = { [1,2), [4,4] }
720 名前：デフォルトの名無しさん mailto:sage [2010/12/12(日) 17:55:37 ]: >>719
「速い文法」の意味が図りかねるが、
>>688 や >>693 と同じで昇順リストで持てばいいと思う。

補 ((補 A) 和 (補 B)) でよくない？

この計算が遅いの？
721 名前：デフォルトの名無しさん mailto:sage [2010/12/13(月) 00:16:06 ]: >>719
開区間と閉区間の両方を許容させるの？
722 名前：デフォルトの名無しさん mailto:sage [2010/12/13(月) 01:10:59 ]: なるほどドモルガンつかって和を使い回すってのは数学的な発想だなー
doubleみたいな型ならともかく、整数型とかなら離散値だから
Complement({1,2})は{ [INT_MIN,0],[3,INT_MAX]}とすれば閉区間のみでいけるでしょ
補集合の計算は、実際は複数個範囲があるから-∞と∞を加えて(N-1)+2回ループでO(N)
なので積もO(N)で計算出来るね
723 名前：デフォルトの名無しさん mailto:sage [2010/12/13(月) 01:16:14 ]: 実数はいらない子ですか
724 名前：デフォルトの名無しさん mailto:sage [2010/12/13(月) 02:18:13 ]: 標準化してBoostあたりに組み込んでくれんかな。
725 名前：デフォルトの名無しさん mailto:sage [2010/12/13(月) 02:45:24 ]: 高速な区間クラスの開発を外注してくれと言われたら俺は
とりあえず株式会社ケイブに相談してみるｗ
726 名前：デフォルトの名無しさん mailto:sage [2010/12/13(月) 07:49:01 ]: >>686
範囲検索([12,15][14,18] に対して [13,16] と重複する範囲要素を見つけるみたいな)も
したいならSkipListをベースに範囲拡張を仕込む手も
727 名前：デフォルトの名無しさん mailto:sage [2010/12/13(月) 07:50:15 ]: 時間があったら範囲扱う機能をまとめてライブラリにしてみたいよね
728 名前：デフォルトの名無しさん mailto:sage [2010/12/13(月) 15:16:06 ]: md5みたいなアルゴリズムのパラメーターって誰がどうやって決めてるんですか？
729 名前：デフォルトの名無しさん mailto:sage [2010/12/13(月) 15:19:12 ]: あれってsin関数かなんかじゃなかった？
730 名前：デフォルトの名無しさん mailto:sage [2010/12/13(月) 17:09:03 ]: わおわおわお
731 名前：デフォルトの名無しさん mailto:sage [2010/12/14(火) 00:12:23 ]: >>726
こんなデータ構造があるんですね、面白いです
こういうわりと新しいデータ構造一覧みたいなの誰かどっかにまとめてくれないですかね

あれからちょっと考えていたのがRange<T>自身も範囲を持てるようにして
範囲を二分木/多分木で表す方法です
例として現在所持している範囲の最小値/最大値が1と16の時
全体の範囲を[1,16]で表します
例えば[1,2]と[3,4]というデータは

全体範囲[1,16]の中に
[1,8][9,16]があって
[1,8]が[1,4][4,8]、[9,16]が[9,12][13,16]に細分されて
[1,4]の中に[1,2]と[3,4]がある、といった具合
検索は上から順に範囲を狭めて行きます
検索範囲との包含関係でやると、[4,5]みたいな二分木を横断するパターンの扱いが面倒なので
範囲の開始時間と幅をキーにて絞り、その各要素について終了時間をチェックします
詳細は詰めてないですが、O(log2(N)*絞った要素数)、ぐらいで動きそうなので
シンプルな実装よりは早くなるんじゃないかと思います
732 名前：デフォルトの名無しさん [2010/12/14(火) 00:23:46 ]: ぴっちり半分じゃなくても
[a,b),[c,d),[e,f)
a<b<c<d<e<fになるってだけ守れば
A=[a,b)
B=[c,d)
C=[e,f)
の間にA<B<Cというような単純な比較が定義できるから二分木で扱えるね
これで検索とpoppushはlogNでいける
BとCを横断するような[x,y)を挿入するなら検索で前後を探してpopして[c,f)をpushみたいな
733 名前：デフォルトの名無しさん mailto:sage [2010/12/14(火) 01:20:46 ]: >>731
ユニマガでも解説されていたな。
734 名前：デフォルトの名無しさん mailto:sage [2010/12/14(火) 03:14:50 ]: 90年くらいに発明されたデータ構造だっけ。稀によく使う。
735 名前：デフォルトの名無しさん mailto:sage [2010/12/14(火) 03:24:06 ]: 稀によく？
736 名前：デフォルトの名無しさん mailto:sage [2010/12/14(火) 03:29:46 ]: ブロントさん何してるんですか
737 名前：デフォルトの名無しさん mailto:sage [2010/12/14(火) 09:57:56 ]: ロックフリーの実装が、The Art of Multiprocessor Programming 並行プログラミングの原理から実践まで、に
載っていたな。
738 名前：デフォルトの名無しさん mailto:sage [2010/12/14(火) 10:37:51 ]: >>731
うろ覚えだけどそれってR木じゃない？
739 名前：デフォルトの名無しさん mailto:sage [2010/12/14(火) 10:50:49 ]: SkipListを分散環境に拡張したら SkipGraph
さらに複数キー対応したら Multikey SkipGraph
検索を効率化した Skip B-trees
範囲キー対応した Rangekey SkipGraph
範囲内の最大値最小値平均値を高速に求められる集約Skip Graph
多次元をあつかう SkipIndexやZnet

とかSkip系列は最近派生種が増えております
740 名前：デフォルトの名無しさん mailto:sage [2010/12/14(火) 11:06:37 ]: へええ。
こういうの放送大学とかでやってくれんかな。
741 名前：デフォルトの名無しさん mailto:sage [2010/12/14(火) 11:08:25 ]: 放送大学では英語を勉強して。それで英語の文献読んで。
742 名前：デフォルトの名無しさん mailto:sage [2010/12/14(火) 11:54:25 ]: Multikey SkipGraph, Rangekey SkipGraph, 集約Skip Graph は日本語よ。
分散系だけどやってることの実現方法とか考え方はSkipListとかのデータ
構造に反映できると思う。
743 名前：デフォルトの名無しさん mailto:sage [2010/12/14(火) 14:01:15 ]: SkipListは単純なアイデアで実現されているから、応用、変種が幅広いのかね。
744 名前：デフォルトの名無しさん mailto:sage [2010/12/14(火) 18:55:07 ]: 表現方法が違うだけで結局多分木と同値のような気がする＞SkipList
745 名前：デフォルトの名無しさん mailto:sage [2010/12/14(火) 19:21:47 ]: 多分木に乱数でスキャッタする要素があるものってあったっけ？
746 名前：デフォルトの名無しさん mailto:sage [2010/12/14(火) 19:34:26 ]: は、まさかビットマップ表現にしたのを圧縮したかったとか？>>669
747 名前：デフォルトの名無しさん mailto:sage [2010/12/14(火) 20:34:28 ]: >>738-739
そのあたりをタグに調べたら色々と見つかりました。
古典的には
　1984 R木
　1985あたり box tree
　1989 skipList
　もっと前？　interval treeとsegment tree
最近だと
　2001 DHT(Distributed Hash Tree)
　2004 Priority r tree
　2006 DST(Distributed Segment Tree)
　2007 DAST(Distributed Arbitrary Segment Tree)
　2009ぐらい？ rangekey skipList
　今年の4月7日 BoostにITLライブラリが正式に導入←もうBoostに入ってた

この種のデータ構造は最近ではP2Pへの応用が多いみたいですね
ジェネリックな実装も落ちてたので
カレンダーにはPriority R Treeを使ってみようと思います
アルゴリズムとしては空間充填曲線を使うR木の実装が面白かったです
748 名前：デフォルトの名無しさん mailto:sage [2010/12/14(火) 23:11:33 ]: >>744
なわけない。
749 名前：デフォルトの名無しさん [2010/12/15(水) 06:35:00 ]: ここは質問スレじゃねーんだよ
750 名前：デフォルトの名無しさん [2010/12/17(金) 00:45:10 ]: 「Nクイーン問題を遺伝的アルゴリズムで解く」というとき、
・(例えばN=8なら)11387653みたいなクイーンの座標列を1遺伝子として
複数の遺伝子をつくり、交叉や突然変異で世代を進めていく
・83541267のように縦横にクイーンが重複しない遺伝子の組み合わせをつくり、
遺伝子内の座標の入れ替えで縦横の重複がない状態を保持しながら世代を進め、
斜めの重複を評価していく
のどちらが標準的なんでしょうか？遺伝的アルゴリズムの説明を読むと
前者な気がするんですが、Nクイーン、遺伝的アルゴリズムで検索して
はじめにヒットするpdfだと後者だと書いてあります。
単純に考えると前者は計算量が多くなり、後者は局所解に陥る（っていうんでしょうか）
可能性が高くなる気がしますが…
751 名前：デフォルトの名無しさん [2010/12/20(月) 17:23:02 ]: INT_MAXより小さいユニークIDの最も効率のよい生成器は？
752 名前：デフォルトの名無しさん mailto:sage [2010/12/20(月) 17:27:14 ]: id = (id + 1) % INT_MAX
753 名前：デフォルトの名無しさん [2010/12/20(月) 17:30:16 ]: 全然ユニークじゃない件
754 名前：デフォルトの名無しさん [2010/12/20(月) 17:56:19 ]: idなんてdouble GetID() { static double x = 0.0; return x++; }で十分ですよね
755 名前：デフォルトの名無しさん mailto:sage [2010/12/20(月) 18:03:37 ]: 「ユニーク」を定義してください
756 名前：デフォルトの名無しさん mailto:sage [2010/12/20(月) 18:33:50 ]: 日本語としては「笑えるID」？
757 名前：デフォルトの名無しさん mailto:sage [2010/12/20(月) 22:35:11 ]: 変なID？
758 名前：デフォルトの名無しさん mailto:sage [2010/12/20(月) 22:42:46 ]: >>753
INT_MAXを超えた場合はそれ未満の自然数（と0）は全部使われてるわけで
どっちみち一意にできっこない
759 名前：デフォルトの名無しさん [2010/12/20(月) 22:49:15 ]: ・オブジェクトに一意なハンドルを与えたい
・オブジェクトは生成されたり破棄されたりする
・オブジェクトが生成されると同時にハンドルが与えられる
・オブジェクトが破棄されるとハンドルが再利用可能になる
・同時にINT_MAX個を超えるオブジェクトは存在しない
・再現性が必要なのでメモリアドレスをハンドルにすることはできない

としたらどうですか？
760 名前：デフォルトの名無しさん mailto:sage [2010/12/20(月) 22:53:06 ]: >>759
過去レス読んでないけど、その処理は普通にやってる簡単だけど?
761 名前：デフォルトの名無しさん mailto:sage [2010/12/20(月) 23:00:05 ]: 無精をせずに>>751から読み返してからどうぞ
762 名前：デフォルトの名無しさん mailto:sage [2010/12/20(月) 23:05:08 ]: 「最も効率のよい生成器は？」　が課題なのか?
単に、空きのIDを最速で検索する方法が答えではないのか?
763 名前：デフォルトの名無しさん [2010/12/20(月) 23:06:16 ]: 未使用or使用済みのマーク付きの範囲オブジェクトでツリーを構成して云々カンヌンする
764 名前：デフォルトの名無しさん mailto:sage [2010/12/20(月) 23:09:37 ]: いやいや、空きIDを単純連結リストにして、解放時後ろに足し。GET時前からとるだけでは？
MAXが多い場合最速だろ。リストが空ならMAX使用中。
765 名前：デフォルトの名無しさん mailto:sage [2010/12/20(月) 23:15:26 ]: >>759
・再現性が必要なのでメモリアドレスをハンドルにすることはできない

これが気になるな

何の情報を基に何を再現したいの？
766 名前：デフォルトの名無しさん [2010/12/20(月) 23:35:22 ]: >>764
それってメモリ効率悪くね？
767 名前：デフォルトの名無しさん mailto:sage [2010/12/20(月) 23:36:43 ]: スピードとメモリー効率は殆どの場合反比例です。
768 名前：764じゃないけど mailto:sage [2010/12/21(火) 04:08:06 ]: >>766
単純連結リストがどんなものを想定しているのかしらんけど
配列ベースの循環キューにしとけばデータ分の配列＋頭と尻の位置ぐらいで済ませられる
769 名前：デフォルトの名無しさん [2010/12/21(火) 08:40:22 ]: INT_MAX個の要素持たせるの？
770 名前：デフォルトの名無しさん mailto:sage [2010/12/21(火) 09:13:15 ]: そこで>686ですよ
771 名前：デフォルトの名無しさん [2010/12/21(火) 09:50:51 ]: 可変長整数をインクリメントしながら割り振って適度なタイミングでハンドルの再配置をすればいい
772 名前：デフォルトの名無しさん mailto:sage [2010/12/21(火) 19:33:40 ]: 結局、範囲を効率よく所持する方法に帰着するのか
773 名前：デフォルトの名無しさん mailto:sage [2010/12/25(土) 08:38:54 ]: どこに処理限界を置くかに帰着するんじゃないかな
774 名前：デフォルトの名無しさん [2010/12/27(月) 15:16:14 ]: ここは質問スレじゃねーんだよ
775 名前：デフォルトの名無しさん mailto:sage [2010/12/27(月) 18:45:28 ]: >>774
>>691
まー漏れも質問ばっかりになるのはどうかと思うけど
776 名前：デフォルトの名無しさん mailto:sage [2011/01/11(火) 23:48:55 ]: 質問スレじゃないとしたら、強固な雑談スレでも目指すの？
777 名前：デフォルトの名無しさん mailto:sage [2011/01/28(金) 22:23:23 ]: うん
778 名前：デフォルトの名無しさん mailto:sage [2011/02/16(水) 20:41:44 ]: R-TreeやPR-Treeについて詳しく載ってる和書ない？
779 名前：デフォルトの名無しさん mailto:sage [2011/02/24(木) 22:05:05.77 ]: >>731
今回加わった boost::icl、特に interval_set がそれ。
custom interval も喰える凄い奴。
780 名前：デフォルトの名無しさん mailto:sage [2011/03/03(木) 22:01:40.30 ]: 無秩序な二分木をファイルに格納するときに
0～節（葉も含む）の数通し番号を振って
通し番号順に値左右の子の番号を配列に格納してwrite
これより効率いい方法ありますか？
781 名前：デフォルトの名無しさん mailto:sage [2011/03/03(木) 23:11:43.20 ]: >>780
要素ごとに2bitあればいけそう
　1
／＼
2　　5
　＼
　　3
　／
4
の場合、
1:2,5
2:0,3
3:4,0
4:0,0
5:0,0
とする代わりに
1,1 (node 1の左右の有無の示す)
0,1 (node 2の以下同様)
1,0
0,0
0,0
のようにノードごとに2ビットの情報があれば再構成できそう
あとはこのビット情報をまとめてファイルに書き込めば
いいんじゃないかと
782 名前：デフォルトの名無しさん mailto:sage [2011/03/03(木) 23:43:58.26 ]: なるほど
ちょっとなんで？と悩みましたが良さそうですね
どうもありがとう！
783 名前：デフォルトの名無しさん mailto:sage [2011/03/03(木) 23:45:27.73 ]: 空間効率、時間効率、左右の区別…それによって異なりそう
784 名前：デフォルトの名無しさん [2011/03/30(水) 01:46:58.51 ]: 旺文社マルチ辞典
www.youtube.com/watch?v=kz1pPoTRhq4
785 名前：デフォルトの名無しさん mailto:sage [2011/04/02(土) 18:56:53.74 ]: 32bit変数2つのそれぞれの1bitが
割り込みフラグ、割り込みマスクの意味を持っていて、
フラグが1 かつマスクが0 のビットのみに処理をしていきたい

現状こんなんなんだけど、ここから速度改善できるのだろうか？
maskが0であるほど処理時間が長くなるのがきになっている
flagは実際メモリマップドのレジスタで、リードに時間がかかるからそこを何とかしたいが
即時性？がいるのでラッチはしておけない

flag = フラグ;
mask = マスク;

bitmask = 1;
for(i=0;i<32;i++){
　if(mask&bitmask==0 && flag&bitmask==1){
　　iを使った処理;
　}
　bitmask <<= 1;
}
786 名前：デフォルトの名無しさん mailto:sage [2011/04/02(土) 19:11:35.76 ]: x = flag & not(mask)

if(x&1)

x>>=1
787 名前：デフォルトの名無しさん mailto:sage [2011/04/07(木) 14:18:17.60 ]: >>784
つまりどういうことです？
788 名前：デフォルトの名無しさん mailto:sage [2011/04/26(火) 21:54:46.08 ]: 敵のモンスターが徘徊するようなプログラムはどのようなアルゴリズムで書いたら良いのでしょうか

単純に毎回ランダムな方向に進むんだったら酔歩になっちゃいますよね

ある方向にしばらく進む→しばらく止まる→またある方向に進む→
ようなかんじにしたいです。
参考になるサイト等ありますでしょうか
よろしくお願いします
789 名前：デフォルトの名無しさん mailto:sage [2011/04/26(火) 23:29:18.80 ]: > 単純に毎回ランダムな方向に進むんだったら

と

> ある方向にしばらく進む→しばらく止まる→またある方向に進む→

の違いが分からん
790 名前：デフォルトの名無しさん mailto:sage [2011/04/26(火) 23:48:58.19 ]: >>789
ごめんさない
『進む』行為を1ステップごとに行うとして
毎ステップランダムな方向だとかんたんに実装できるけど酔歩で不自然な動きになりますよね
ある程度同じ方向に進んでから向きをランダムに変えてまたある程度同じ方向に進むような感じにしたいのです

よくゲームの敵キャラがそんな風に動いている気がするのですが、どのようなアルゴリズムなのかな、と
791 名前：デフォルトの名無しさん mailto:sage [2011/04/27(水) 00:04:27.00 ]: 　　歩く
と
　　止まる（じっとしてる）
を交互にやればいいじゃん
792 名前：デフォルトの名無しさん mailto:sage [2011/04/27(水) 00:04:28.45 ]: 超簡単なロジックなら、
3歩先なり5歩先の座標を計算して
3あるいは5歩分は計算した座標まで均等にまっすぐ進む
計算座標まで到達したらランダムに方向を決めて再計算するとか

20年くらい前のレトロゲームならこんなものだと思う
793 名前：デフォルトの名無しさん mailto:sage [2011/04/27(水) 11:29:31.10 ]: >>792
元祖ローグでは基本ランダム。

プレイヤーがとある範囲に入ったとき、
・近づく
・逃げる
・興味を示さない
などを行う。

ここら辺は敵の特性だったり、また状態(体力)などにより変る。

敵対なら範囲に入ってきたら近づいて攻撃したり、
プレイヤーに攻撃されて瀕死になった場合は遠ざかるなど。

ここが一般的にはＡＩとよばれています。

初代では行われていないけれど、もう少し世代が進むと経路探索を利用して、
ダンジョンのカベに引っかからずに目標のポイントに進むことも出来るようになっいます。
794 名前：デフォルトの名無しさん mailto:sage [2011/04/27(水) 11:33:21.38 ]: ↑
>>788あてだったのにアンカー間違えた。
795 名前：デフォルトの名無しさん mailto:sage [2011/04/27(水) 12:32:13.56 ]: いっそのことダンジョンやモンスターに獣道情報を付加しちゃうとか
頻繁に立ち止まったり
ときどきルートを少し外れながら帰り道をスタックするとそれっぽいかもしれないなあ
796 名前：デフォルトの名無しさん mailto:sage [2011/04/27(水) 12:45:07.20 ]: ゲームシステムじゃなくアルゴリズムを訊いてるんだよな？
797 名前：デフォルトの名無しさん mailto:sage [2011/04/27(水) 13:15:39.01 ]: A*使えでおわるんじゃないかな？

まあお絵かきツールの塗りつぶしアルゴリズムに距離をついかししやれば
簡単な経路探索アルゴリズムが出来ますよ。
798 名前：デフォルトの名無しさん mailto:sage [2011/04/27(水) 19:10:45.17 ]: >>788 の質問は経路探索じゃなくて、
人間が何かふらふらと見回りしているかのような徘徊だと思うが

実際のゲームは知らんが、>>790 の言う通りにするのなら、
まず進む向き d ベクトルと歩数 n をランダムに決める

それから、d 方向にランダムに k (<n) 歩歩いたら、少し止まって、
d 方向を平均として適当な分散の正規分布に従って、
ランダムに d' 方向を決める（要するに d' は d に近い値）

d' 方向にランダムに k' (<n-k) 歩歩いたら、また少し止まって、
先ほどと同じように d'' と k'' を決めてまた歩く

歩数 n 歩に到達したら、最初の進む向き d ベクトルと
歩数 n をランダムに決める事からまたやり始める
799 名前：788 mailto:sage [2011/04/27(水) 21:10:29.90 ]: 皆さんありがとうございます
やってみます
800 名前：デフォルトの名無しさん mailto:sage [2011/04/28(木) 08:57:26.19 ]: アルゴリズムちゅーかストラテジだな
801 名前：デフォルトの名無しさん mailto:sage [2011/04/28(木) 12:02:14.96 ]: >>798
経路探索いれて、目的地をランダムで決定すればよいとおもったんだけどな。
802 名前：デフォルトの名無しさん mailto:sage [2011/04/28(木) 12:45:05.74 ]: 経路探索ってなにん？
壁とかあるかんじ？
803 名前：デフォルトの名無しさん mailto:sage [2011/04/28(木) 13:24:34.55 ]: 障害物の在るマップで、とある地点を指定するだけでそこまでの経路を計算してくれるアルゴリズムだよ。
ターン制のシミュとかでも応用で移動コスト計算付で移動可能範囲を計算したり、
そこまでの移動経路を計算できたりするよ。
804 名前：デフォルトの名無しさん mailto:sage [2011/04/28(木) 15:08:28.56 ]: 多少力入れるならAIを有限状態機械にする。
AIは「モード」を持っていて、クロックごとにそのモードに従って行動する。
例えば「何もしない」「地点(X,Y)に速度Zで移動」「敵が視界内にいたらその位置に移動」とか。
805 名前：デフォルトの名無しさん mailto:sage [2011/04/28(木) 15:22:20.64 ]: スクリプトなり、関数ポインタなり、デリゲートなリでステートマシンの評価部分を入れ替えられれば色んな敵のアルゴリズムを切り替えられていいよな。
806 名前：デフォルトの名無しさん mailto:sage [2011/04/28(木) 16:09:07.69 ]: PSゲームの天誅のようなのがわかりやすくていいとおもうな
807 名前：デフォルトの名無しさん mailto:sage [2011/04/28(木) 18:02:10.24 ]: >>806
たぶん

主人公から遠い…非表示
主人公から近い…キョロキョロ>>788
キョロキョロ中に主人公が視界にはいる…発見
発見中…主人公追いかける、経路探索?
発見中に主人公を見失う…警戒
警戒中…はげしくキョロキョロ
警戒後一定時間経過…キョロキョロ

こんなんだったよな
実装めんどくさそう
808 名前：デフォルトの名無しさん mailto:sage [2011/04/28(木) 18:50:18.99 ]: ステートマシンの実装法か

いろいろ難しいからなぁ
809 名前：デフォルトの名無しさん mailto:sage [2011/04/29(金) 17:01:04.41 ]: アルゴリズムとデータ構造のオンライン事典

xlinux.nist.gov/dads/
810 名前：デフォルトの名無しさん mailto:sage [2011/05/09(月) 21:34:56.01 ]: バイナリ値を持つ２次元平面の、すべての１である部分を覆うような
長方形領域の集合を求めたいです。

全領域サイズの長方形をもってくればひとつの長方形でおおえますし、
大きさ一の長方形で覆うと考えれば最小の面積でおおえますが、
そのバランスのとれたかたち、なるべく少ない数の長方形の集合でそれなりに無駄なく覆う
というようなものをどうやったら求められるかなあと考えています。
こういう問題を解くためにはどういったアルゴリズムを用いればよいでしょうか？
また、こうした問題や、類似の問題で名前のついた問題ってありますかね？なにでぐぐってよいかわからなくて。
811 名前：デフォルトの名無しさん mailto:sage [2011/05/09(月) 21:50:36.16 ]: バックパッキングとは違うかな。
812 名前：810 mailto:sage [2011/05/09(月) 22:17:59.82 ]: >>810
文章がわかりにくかったです。
長方形領域の集合で、すべての１である部分を覆いたい、という問題です。

障子のあちこちに大きさ形まちまちの穴があいていて、
その穴をふさぐために使える障子の形を長方形に限定して
どうすればいい感じに全ての穴を塞げるか、というイメージです。

>>811
バックパッキングというのは、ナップサック問題みたいなものでしょうか？
どのように>>810に還元出来るでしょうか？
813 名前：デフォルトの名無しさん mailto:sage [2011/05/09(月) 22:23:52.05 ]: 平面上の任意の座標 (x, y) の値が、0 か 1 、というわけ？

つまりテーブルの上にコーヒーをこぼして、濡れてるところが 1 とかそんな。
814 名前：810 mailto:sage [2011/05/09(月) 22:31:18.40 ]: >>813
そうです。
815 名前：デフォルトの名無しさん mailto:sage [2011/05/09(月) 22:31:35.13 ]: >>810
>>812

要するに、２次元平面上にある点群に対して、
ある程度近いもの同士でグループ分けしたいということでしょ
（問題名、アルゴリズム名は忘れた）

で、それぞれのグループを覆う長方形を考えれば、
まぁだいたいバランスは取れてる
816 名前：デフォルトの名無しさん mailto:sage [2011/05/09(月) 23:01:54.69 ]: >>810
領域分割でぐぐるとそれらしいのが引っかかってくる

提示の例だと
codezine.jp/article/detail/167
とか
817 名前：デフォルトの名無しさん mailto:sage [2011/05/09(月) 23:42:31.45 ]: 難しそうだなあ
　 □
□□□
　 □
が２つの長方形で重複はするが過不足なく覆えることは
どう考えればいいのだろう
818 名前：デフォルトの名無しさん mailto:sage [2011/05/10(火) 00:30:51.45 ]: >>817
例えばパターンマッチにかけ、５個の長方形が十字型に並ぶパターンを見つけたら、
それらを融合させて２個の長方形へ最適化

しかし、例えば２個の長方形と、それをひとつにまとめた１個の長方形とで、
どちらが「少ない数の長方形の集合でそれなりに無駄なく覆う」ことになるのか

その「評価関数」は >>810 の中ではどうなってるんだろう
819 名前：デフォルトの名無しさん mailto:sage [2011/05/10(火) 00:42:50.44 ]: 大きい長方形の中を幾つかの長方形に分けて、さらにその長方形の中を幾つかの。。。
ってのじゃ駄目かい？
全部1か0の場所は分割しないっていう感じで
大きさ1の長方形が定義されてるなら、関数を停止させる事も出来るだろうし

いや、よく分からんのだけど
820 名前：デフォルトの名無しさん mailto:sage [2011/05/10(火) 07:55:25.52 ]: いい案があるわけではないんだけど、確認。

> 障子のあちこちに大きさ形まちまちの穴があいていて、

穴の位置が {(3.8, 2.6), (1.4, 1.4), (2.1, 3.5)} みたいにして与えられると思えばいい？

> その穴をふさぐために使える障子の形を長方形に限定して

辺は x, y 軸と平行？　どんな向きでもあり？
821 名前：810 mailto:sage [2011/05/10(火) 09:53:10.32 ]: 領域分割それっぽいですね。googleとと相談してみます。
ありがとうございます。

>>818
評価関数もふくめ方向性を考えてます
開いている穴のうちふさがれている割合 1.0
を必要条件として
長方形領域の集合のうち、穴を塞いでいる部分の割合をP
用いる長方形の個数をnとすると、
Pとnの多項式で定式化出来ると思いますが、具体的にどうとは考えてないです

>>820
今回私が解こうとしている問題に関しては
BOOL area[][];のようなかたちで入力は与えられますが、
おおむねそういう感じです。
長方形の辺は軸に平行で考えています。
822 名前：デフォルトの名無しさん mailto:sage [2011/05/10(火) 14:22:27.31 ]: TかFかが与えられる点は格子点で、斜めに置いたりはしないと。
>>817 にあるように、うまく部分問題に分割できないのが難しいねぇ。
理屈の上では組合わせは有限なので順番に評価関数に食わせて一番評価の高いのを
選べばいいわけだけど、現実には組み合わせ爆発で無理だから、よさげなのを探索
するしかないかな。

戦略としてはトップダウンとボトムアップの2通りがあると思うんだけど、トップダウンのほうは、
まず1個の矩形からはじめて、矩形の数が増えてもいいから、塞いでる割合が増えるパターンを、
探索していく。この時最初の矩形より外に広がることはない。（>>817のように途中のプロセス
ではそうでない場合もあるのが難しいところ）

逆にボトムアップは、穴の1個1個をそれぞれ小さな矩形でふさいで、それをだんだん大きい
矩形の集まりにしてゆくというもの。これもやっぱり一本道というわけにいかないのが難しい。
823 名前：デフォルトの名無しさん mailto:sage [2011/05/10(火) 22:59:01.22 ]: 使えねぇやつらだな。アルゴリズムスレなんだからそれらしいレスしろよ。
Graham走査だろ？あとはググれ。
824 名前：デフォルトの名無しさん mailto:sage [2011/05/10(火) 23:12:57.91 ]: 多角形の凸包が作れて、この問題的にどこがうれしいわけ？

おまえは使える奴なんだから、凸包の多角形から、どういうアルゴリズムで、
いい感じの長方形の集合を作るのか、ちゃんと説明しろよな。
825 名前：デフォルトの名無しさん mailto:sage [2011/05/10(火) 23:51:27.60 ]: Graham走査ググったら関係ないふいた
826 名前：デフォルトの名無しさん mailto:sage [2011/05/10(火) 23:58:02.30 ]: bitonic sortでクグれよ
827 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 10:02:48.66 ]: 一種のマージソート？
828 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 12:00:00.47 ]: >>823
が言いたいことはGraham捜査で全ての点を包含する凸包の点を取得し、
その集合からXYそれぞれについての最上、最下の座標を探せば言いよってことなんじゃねえかと。

まあ全ピクセルを捜査してXYの各座標について最小、最大を
見つけるたびに書き換えてあげれば目的の長方形の見つかると思う。

ただし重いｗ

もしデータを書き込むところから制御できるなら、書き込むたびに
XYについて最小値、最大値を書き換えてあげば簡単に見つかると思う。
829 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 12:35:11.13 ]: >>828
もし >>823の意図がそれなら、彼は必ず一つの長方形で覆うものと勘違いしてないか？

点群が１ヶ所に固まっていれば長方形一つが最も無駄が無いだろうが、
まばらに分散していれば複数の長方形で覆った方が無駄が無い場合の方が多い
830 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 13:18:57.72 ]: >>810の問題だと一つ以上の長方形の集合を求めるだっけか。

前提として点を2つ以上含めた物を長方形とするって決まりが暗黙的に適用されるのかな。
長方形同士ってかさなってはいけないとかもあるのかな？？
831 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 15:06:17.79 ]: 微妙に問題が曖昧なんだな。
とりあえず、ある程度の塊に点群を分類してからやりたいなら、空間(ここでは平面か)分割してクラスタリング。
クラスタ重心を計算しながら分割領域を調整。調整が終わったらグラハムさんの出番。
…で、できそうな気がするけど、適当思考なので上手く分割できるかちょっと自信ない。
これだと、矩形の重なりは発生する可能性が残ってるし。
832 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 15:17:43.65 ]: 危険点をカバーするように検査エリアを設定したいのかな。
だとすると、水平方向はある程度無駄が在ってもいいけど垂直方向はできるだけ無駄がない方がいいとか、
矩形同士が重ならないだけでなく水平方向に違う高さを持つ矩形が存在したら拙いとかw
833 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 15:25:36.60 ]: >>810応答せよｗ
834 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 15:47:16.41 ]: 何を求めるのか、それが曖昧だ。
面積を最小にするのか、矩形の数を最小にするのか。
n個の点に対して、面積の最小値はnだし、矩形の最小値は1。
なので、求めるモノを定義しないと、「だいたいこんな感じ」の解しかでてこない。
835 名前：デフォルトの名無しさん mailto:sage [2011/05/11(水) 18:06:34.87 ]: >>834
だから >>818 で評価関数はどうすんのと訊いたら、
>>821 でまだ考えていないと
836 名前：デフォルトの名無しさん mailto:sage [2011/05/12(木) 00:17:47.50 ]: 求めたものを結局何に使うのかがわかればもっと適した方法が絞れるんだろうけどな
837 名前：デフォルトの名無しさん mailto:sage [2011/05/16(月) 19:43:52.24 ]: ループと動的確保なしで数値範囲の和と積を扱う手法は有りますか？
838 名前：デフォルトの名無しさん mailto:sage [2011/05/16(月) 20:55:05.61 ]: >>837
悪いが意味が分からん
具体的に、何か例を示してくれ

こういう入力に対して、こんな計算をして、こういう出力を得たい、とか
839 名前：デフォルトの名無しさん mailto:sage [2011/05/16(月) 20:55:53.56 ]: >>837
なぜにそんな限定を？
840 名前：837 mailto:sage [2011/05/16(月) 22:13:20.11 ]: YesNoで答えられる質問一つで数値の範囲が決まる
Yesなら[a,b)、Noなら[-inf,a)or[b,+inf)
で可変個の質問にユーザーに答えさせて範囲をand結合して絞りこむ
で、最後に絞り込んだ範囲を表示
という課題がでたんです
でもその講義でまだ入出力とifとgotoしかやってないんです配列もやってません
どうも周りに聞いたところによるとその教授は講義範囲外のことをあまり使うといい顔をしないらしいんです
ですので講義範囲内で処理したいんですが…という感じです
841 名前：デフォルトの名無しさん mailto:sage [2011/05/16(月) 22:58:41.22 ]: goto と if 使えるならループ作れるじゃん
842 名前：デフォルトの名無しさん mailto:sage [2011/05/16(月) 23:32:25.49 ]: >>840
宿題は自分でやれよ屑。
あと、おまえみたいなゴミは社会に出てくるな。
氏ね。
843 名前：デフォルトの名無しさん mailto:sage [2011/05/17(火) 01:34:33.75 ]: いずれにしろこのスレで聞く事じゃないな
844 名前：デフォルトの名無しさん mailto:sage [2011/05/17(火) 03:16:59.99 ]: >>840
講義範囲外のこと使っていい顔しない教授とかクソだから無視で。
845 名前：デフォルトの名無しさん mailto:sage [2011/05/17(火) 07:32:31.58 ]: ざっとみて講義が目標とする力量に達していたら
「できるんだったら来週からこなくていいよ。単位だしとくから」
ってのが大学的
846 名前：デフォルトの名無しさん [2011/05/31(火) 21:25:56.80 ]: 相異なる３１個んもデータがある。この中に含まれる数をキーとして逐次探索
を行うデータが見つかるまで、それぞれ何回の判定が必要か、期待値を求めよ

これの逐次ってどうやって求めるんですか？？
1/31+2*1/30+・・・・
みたいな感じでしょうか・
またキーが含まれない場合もおしえてくださいｍｍ
847 名前：デフォルトの名無しさん mailto:sage [2011/05/31(火) 21:39:11.09 ]: 期待値は31/2回
キーが含まれない場合は31回
848 名前：デフォルトの名無しさん [2011/05/31(火) 21:53:04.17 ]: ありがとうございます
含まれる場合の期待値の求め方をおしえてください
キーが含まれない場合の２分木探索はどうやるんでしょうか？？
849 名前：デフォルトの名無しさん mailto:sage [2011/05/31(火) 23:00:07.25 ]: どっから二分木でてきたんだ
850 名前：デフォルトの名無しさん mailto:sage [2011/06/04(土) 19:20:16.63 ]: Write-Ahead Loggingのアルゴリズムって
何があるのですか？
851 名前：デフォルトの名無しさん mailto:sage [2011/06/09(木) 15:23:27.24 ]: Nこ（N<=256）の重さ付き要素から最小の2こを取り出して合計して1つにして戻す（N-1こになる)という操作をするときに
①昇順ソート→index1,2を取り出して合計して戻す
②一回操作して最小の2つのインデックスを記録→取り出して合計して戻す
どっちが速いかな？オーダーだけ見ると①のような気がするけどswapコストとか考えると②の方がいい？
852 名前：デフォルトの名無しさん mailto:sage [2011/06/09(木) 15:29:12.79 ]: それこそ直ぐにプログラムかいてベンチとれってかんじじゃね？ｗ
853 名前：デフォルトの名無しさん mailto:sage [2011/06/09(木) 16:00:31.18 ]: 256個なら誤算の範囲。
N=100万とかなら、迷わず2じゃね？
なんで、1のオーダーの方が小さいと思うの？
854 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 15:40:48.70 ]: 各ピクセルが得られるビットマップ画像があります
これをjpgエンコードしたほうがいいのかpnhエンコードしたほうがいいのか判別するにはどのような方法が考えられるでしょうか
855 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 15:42:51.03 ]: 何を指標にして判断したいのかかけよな、エスパーでもさがしてんのかよ。
856 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 16:12:56.69 ]: 俺はピクセルの取得できないビットマップ画像を教えて欲しい。
857 名前：忍法帖【Lv=3,xxxP】 mailto:sage [2011/06/10(金) 16:31:42.49 ]: そんなことよりも、私はpnhエンコードとやらを知りたい。
858 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 19:09:13.91 ]: ピンフ形式だよ。言わせるな恥ずかしい。
859 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 20:40:53.31 ]: アンコの方が好みです
860 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 21:44:37.61 ]: 平和、すなわちパチンコ業界の手先だな
861 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 22:29:46.37 ]: 麻雀の役を辞書にして圧縮するとかどうだろう。
グラデは順子が多いとか。
862 名前：デフォルトの名無しさん mailto:sage [2011/06/10(金) 23:47:52.31 ]: >>851
(3) 最初にヒープを作る→ヒープから最小値2個取り出し合計してヒープに戻す
オーダー的にはこれがいいと思うよ
863 名前：デフォルトの名無しさん mailto:sage [2011/06/12(日) 18:55:05.37 ]: アルゴリズム考える時ってキャッシュ効率とかアクセス効率とか最初から含めて作業始める？
それとも論理的な計算量だけで考える？
864 名前：デフォルトの名無しさん mailto:sage [2011/06/12(日) 19:16:10.15 ]: 私は数学屋じゃないから、先ずはシンプルかつ汎用性を考えるね。
865 名前：デフォルトの名無しさん mailto:sage [2011/06/14(火) 21:48:47.05 ]: 非負の整数a, b（a <=b)があったときに
a <= x <= bになる、「いい感じの整数x」を求める方法はないかね？
クイックソートのピボット選択や、パーリンノイズやGAで使いたい。
一番簡単なのはx=(a+b)/2なのだが、面白味に欠ける。
x=rand(b-a)+aだと、オーバーヘッドが大きい気がする。
できればaとbが一意ならxも一意で決まって欲しい。
フィボナッチ分割はどーかなー。
866 名前：デフォルトの名無しさん mailto:sage [2011/06/14(火) 22:00:02.99 ]: 黄金分割しろ。
867 名前：デフォルトの名無しさん mailto:sage [2011/06/14(火) 22:27:59.93 ]: >>865
> x=rand(b-a)+aだと、オーバーヘッドが大きい気がする。

アルゴリズムスレなんだから、「気がする」で放っておくんじゃなくて、
本当に求めているパフォーマンスを達成できないほどのオーバーヘッドか確認しようよ

あとアルゴリズムスレなんだから、何が「いい感じ」なのか
できる限りハッキリさせようよ

とりあえず、a と b の中間値が「いい感じではない」ことは分かった
擬似乱数はシードを決めれば入力値に対して一意に決まるが、
もしオーバーヘッドが気にならないほどであれば、擬似乱数でいいのか？
擬似乱数が「いい感じ」なのか？

そして、アルゴリズムスレなんだから、「フィボナッチ分割はどーかなー」ではなく、
実際にフィボナッチ分割したらどんな a b に対してどんな値が出力されたのか示してくれ
868 名前：デフォルトの名無しさん mailto:sage [2011/06/14(火) 22:44:09.90 ]: ゆとり乙
869 名前：デフォルトの名無しさん mailto:sage [2011/06/15(水) 10:53:51.44 ]: 比率を一定にしたいなら、積の平方根とか。0が入ったら知らんが。

でも、ピボットに使うっていっても、分布しだいじゃね？
870 名前：デフォルトの名無しさん mailto:sage [2011/06/15(水) 16:07:33.88 ]: たとえば
func shikaku(left, top, right, bottom){
if (十分小さければ){
塗りつぶす(left, top, right, bottom);
} else {
x = bunkatsu(left, right);
y = bunkatsu(top, bottom);
shikaku(left, top, x, y);
shikaku(x, top, right, y);
shikaku(left, y, x, bottom);
shikaku(x, y, right, bottom);
}
}

で、モヤモヤした感じが出したい。
ピボットはまあ、乱択っぽくて任意の分布でもいいかなと。
871 名前：デフォルトの名無しさん mailto:sage [2011/06/15(水) 16:15:47.19 ]: どう見ても全部塗りつぶしてるようにしかみえないのだが。
872 名前：デフォルトの名無しさん mailto:sage [2011/06/15(水) 18:27:45.99 ]: ああっ、色を指定するの忘れていた
873 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 00:42:57.61 ]: 株に関するプログラムをしたいのですが、
ここで質問して良いですか？
株の専門用語の話とかじゃなくてグラフに関する事なんですが。
874 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 09:06:44.12 ]: ロケット工学投資法を読破した俺が答えてしんぜよう
875 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 11:11:15.41 ]: >>874
では、それで御願いします。

株のサイトでチャートの形によって、売買銘柄を
選択するサイトがあるのですが、その仕組みというか
考え方を教えて下さい。

一例として、上昇トレンドかどうか判断するには移動平均を
1日ずつ計算して前日より上がっているかどうかを比較して
いけばいいかなと思ったのですが、実際には上がったり下がったりして、
単純な比較だと、実際は上昇トレンドなのに途中に下がった日があるので、
上昇トレンドと判定できない場合が出てきます。

期間を決めて、その期間内の最高値と最安値が何月何日か、
もしくは、本日が期間内の最安値より高いかで決めるにも、
それじゃ、期間を何日間にするのかと言った条件によって
変わってくるだろうし、どう判断条件を作ればいいか分からないのです。

チャートの形にも色々あるので、簡単には説明できないと思いますが、
上昇トレンドの判断の仕方だけでも教えてもらえれば、他にも応用できるかも
しれないと思いますのでよろしくお願いします。

長文失礼しました。
876 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 11:52:34.06 ]: そりゃスレチだな。
877 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 12:13:47.96 ]: スレチですか。
失礼しました。
878 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 14:12:58.78 ]: >>875
ロケット工学投資法にはトレンドラインの作り方が載ってる
まああれを馬鹿正直に実装するより楽な方法もあるんだが……
タダでは教えられんｗ
879 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 14:14:23.21 ]: >>875
追記。単に作画したパターンにマッチする銘柄を選択するだけなら、
それは「パターン認識」技術の世界だ。ぐぐれ。
880 名前：デフォルトの名無しさん mailto:sage [2011/09/17(土) 15:01:28.43 ]: >>878
　　　　　　　∧∧　　　ｺｲﾔｧｧｧｧ！！
　　　　　　 (д´*　)
　　　　　　（⊃⌒*⌒⊂)
　　　　　　　/__ノωヽ__）
　
>>879
パターン認識、オソロシス
881 名前：デフォルトの名無しさん mailto:sage [2011/09/18(日) 18:17:06.36 ]: この株のネタだと微分の話になるんじゃないのか？
882 名前：デフォルトの名無しさん mailto:sage [2011/09/18(日) 18:19:46.59 ]: >>875
チャートだけ見て判断とか馬鹿だろ。
帰納的に、現実に起こった事実と、チャートの微分を比較できなきゃ
予測がかすりさえしないだろ。
883 名前：デフォルトの名無しさん mailto:sage [2011/09/18(日) 18:47:34.80 ]: >>882
お前は質問スレで何言ってんだ？
だったら、微分を調べろで良いだろ
馬鹿なのか？氏にやがれなのか？
884 名前：デフォルトの名無しさん mailto:sage [2011/09/18(日) 21:10:40.43 ]: ここ質問スレじゃないだろ・・・スレタイなんて書いてあ
885 名前：デフォルトの名無しさん mailto:sage [2011/09/18(日) 21:15:05.39 ]: あ、ホントだ
ごめんよ
886 名前：デフォルトの名無しさん mailto:sage [2011/09/25(日) 05:50:28.01 ]: 木に一本だけ辺をつけ加えて最長となる閉路を探すアルゴリズムか
グラフの中から最長となる閉路を探す方法を教えて下さい
887 名前：デフォルトの名無しさん mailto:sage [2011/09/25(日) 14:11:58.10 ]: >>886
前者の場合

元の木Tの最も深いノードをルートにした木T'において、
木T'のルートと最も深いノードの間に
一本だけ辺をつけ加えたのが最長閉路になるのでは？
888 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 11:34:06.03 ]: 勉強で木構造とそれを巡回するイテレータをC++で作ってるんですが(STLのようなインターフェイスで)
イテレータの内部にスタックorキューor到達済みノードのリストを動的に確保して保持することなく
すべてのノードを巡回する方法はありますか？
イテレーターなので再帰関数を使って一気にという事ができないので
どうしても内部に状態を保持しないとダメかなとは思うんですがアロケートを駆使返すのは効率が気になって…
889 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 13:32:29.72 ]: vectorかlistを包含したnodeクラス作って再帰で巡回させるのはだめなのかい？
890 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 20:48:32.37 ]: 巡回する順番はどうでもいいんだったら
すべてのノードを共通の動的配列上に確保しておけば?
891 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 21:27:39.01 ]: Addしたら必ず1本の共通なリストにノードを追加するのはありだね！
892 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 22:06:08.91 ]: オブジェクトプーリングするのもいいかも
893 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 22:27:53.42 ]: 配列もリストも使わずに、状態保持もしないで全ノードを巡回するアルゴリズム
ただし、木を破壊する

[1]. ルートノードを巡回する
[2]. ルートノードの子ノードから１つノードxを選び、
　　他の子ノードを全てxの子ノードにする
[3]. xをルートノードと見なして [1] へ
894 名前：デフォルトの名無しさん mailto:sage [2011/10/12(水) 22:32:36.91 ]: 親へのポインタ持ってたら普通にできますた
895 名前：デフォルトの名無しさん mailto:sage [2011/10/13(木) 14:44:27.48 ]: バーローｗ
896 名前：デフォルトの名無しさん [2011/10/25(火) 21:39:34.27 ]: 誰か教えてください。
アルゴリズム入門の授業なんですが
・性の小数部分を求めるサブルーチンＤＥＣのフローチャートを書け
・サブルーチンＤＥＣとサブルーチンＩＮＴを使って入力した正の実数の小数点以下を切り上げた
　整数を表示するフローチャートを書け
お願いします
897 名前：デフォルトの名無しさん mailto:sage [2011/10/25(火) 22:24:50.90 ]: まず浮動小数点数の規格を調べます
898 名前：デフォルトの名無しさん [2011/10/26(水) 02:34:55.29 ]: 言語の持っている暗黙のキャスト機能が使ってよいなら簡単なんだが
アルゴリズムの授業なんだから多分ダメなんだろうね。
899 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 04:55:27.33 ]: まずは、整数値を求めればいい。元の値 -　整数値が小数部分だ。
切り上げは、小数部分が0かどうかで整数値か整数値+1かを返せばいい。
整数値は
1より小さくなるまで10で割るのを繰り返す。
その回数分10を掛けながら1～9までの値と比較することで一桁づつ数字を確定していく…
なかんじかな。ループ中に10を掛けている値から確定した数字を引いていくのと、
0に初期化してある変数に10を掛けながら足していくのを忘れずに。この変数が元の値の整数値になる。

浮動小数点数でやると、誤差が出るだろうけれど…
900 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 08:11:17.89 ]: アルゴリズムをフローチャートで書かせるって、まだ一般的なんか？
901 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 09:02:43.69 ]: いまどき信じられん教育のレベルだ
902 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:02:05.33 ]: 高校の情報なんちゃらとかって科目じゃね?
903 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:14:01.81 ]: てことは、日本の高校が信じられん教育レベルだって事実になってしまうわけだけども
904 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:17:13.30 ]: www.johoka.net/flowchart.htm
905 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:17:20.20 ]: 実際、「使える！Microsoft Office」って改名したらどうだ？　って言いたくなるような
教科書が、高校の情報の教科書の中で一番人気だという話だ。
906 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:30:03.53 ]: 大半の人にとって、Office の使い方が将来一番役立つ可能性が高いのは確かだけども。
日本のソフトウェア開発は育たないわね。
907 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 15:36:20.78 ]: 小学校から徹底してopen officeを使うように指導すれば
日本全体でオフィスソフトに使われている莫大な金を節約できる
908 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 16:20:09.01 ]: その考え方はまずい…
使う側からしたら無料なのはありがたいけど、作る側それこそ育たない。
909 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 17:41:00.78 ]: その論理ではOpenOfficeはともかく、GCCとかはこの世に存在しないことになるね。
910 名前：デフォルトの名無しさん mailto:sage [2011/10/26(水) 17:58:05.44 ]: >>907
有料だと金が国外に流出してるだけだし
かといって無料だと国内でも回らないし
911 名前：デフォルトの名無しさん [2011/11/07(月) 18:03:02.90 ]: （ExcelVBAのスレから誘導されてきました）

末尾再帰の最適化について質問です。

FunctionA(n As Long)
If n=0 then
FunctionA=1
Else
FunctionA=FunctionA(n-1)+FunctionB(n-1)
End if
End Function

FunctionB(n As Long)
If n=0 then
FunctionB=2
Else
FunctionB=FunctionA(n-1)+FunctionB(n-1)
End if
End Function

このように末尾で2つの関数が再帰呼び出しされている場合、どのように最適化すればよいでしょうか。
nが大きいと2の累乗でスタックに詰まれていくから重くなるのだと思います。
912 名前：デフォルトの名無しさん [2011/11/07(月) 18:19:50.43 ]: forをつかって普通にループをかいてください。
これで理解できなければあなたには無理です。
913 名前：デフォルトの名無しさん mailto:sage [2011/11/07(月) 18:56:27.71 ]: っていうか、FunctionA や FunctionB の演算って末尾なの？
914 名前：デフォルトの名無しさん mailto:sage [2011/11/07(月) 19:25:14.40 ]: どちらも、最後に自分に戻ってきて、2つの値を足して、それを戻す、という形になってるから、
末尾呼び出しになってない。
915 名前：デフォルトの名無しさん [2011/11/08(火) 00:20:34.51 ]: うるさいな
916 名前：デフォルトの名無しさん [2011/11/08(火) 09:56:31.88 ]: 足し算じゃなく1個ならforなりn--なりで終息させられるが2個なのが厄介だな
917 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 12:52:21.06 ]: 例が悪いよ
2つの関数が再帰呼び出ししてるのは関数の末尾じゃないし、
FunctionA と FunctionB で異なるのは引数がゼロの場合の返値だけ
おまけに、FunctionA(n-1)+FunctionB(n-1) は共に同じ n-1 に関数を適用してる

だったらアルゴリズムのスレとしては、
相互再帰呼び出しの形自体を止めて一つの関数にまとめた方が効率が良い、
としか言いようがない

そもそも、ここはアルゴリズム大辞典のスレなんだから、
何を実現したくてこのアルゴリズムを選択したのか言わないと議論にならん
（何を入力して何を得るのか）

これなら、ここじゃなくてExcelVBAの住人が答えるべきだと思うが
918 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 19:09:42.38 ]: www.cc.kyoto-su.ac.jp/~yamada/ap/array_rep2sol.html
このサイトの後半で紹介されている
最大公約数を使って配列を回転させるアルゴリズム
何か名称がついていたら教えてください。
919 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 19:38:54.10 ]: >>918
もしかして、

p2.2ch.net/p2/read.php?host=hibari.2ch.net&bbs=tech&key=1086272325&rc=918#r917

ここの METHOD 3 と同じかな

>>918 のページの方は配列の要素が遷移する様子が解説されていないから、
処理を追うのが面倒でざっとしか見てないが

「珠玉のプログラミング」という本にも
METHOD 3 と同じ [お手玉の方法] として紹介されているらしいね
920 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 19:42:11.71 ]: 開発者の
ecommons.cornell.edu/handle/1813/6292
の中では Dolphin algorithm って書いてあるけど、
そんな名前で呼ばれてもだれもわからんだろうな
921 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 19:44:20.42 ]: あと、ここも
www.imminentweb.com/technologies/rotating-algorithms-programming-pearls-jon-bentley
922 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 19:58:54.92 ]: >>919, >>920, >>921
ありがとうございます。
自分で図を書いて理解した後だと
イルカが連なって飛び跳ねるイメージはしっくり来ますね。
923 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 20:02:34.39 ]: 「珠玉のプログラミング」に載ってる、といって先日人から教えてもらったが、
名前が付いてるということは初めて見た気がする。
924 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 20:09:28.83 ]: いや、俺も実際に「珠玉のプログラミング」を読んだわけじゃないんだ

"gcd array rotate" でググったら、一番最初に >>919 のページがヒットして、
9件目にその本に載ってると書かれてたブログがヒットしたのを見ただけ
925 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 20:20:34.12 ]: 本にも載ってるけど、大きい配列だとキャッシュが働かなくて結局遅いっぽいね
926 名前：918 [2011/11/08(火) 20:40:16.46 ]: >>919 の URL では見えなかったですが
www.geeksforgeeks.org/archives/2398
の事だったんですね。キーワードが分かったのでたどり着けました。
927 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 21:08:53.87 ]: どうしても速度を求めてるなら、テンポラリ使ったほうが速そう。
あるいは全体の位置が移動してもいいとか。エレガントな手法として悪くないと思うけど。
928 名前：デフォルトの名無しさん mailto:sage [2011/11/08(火) 22:37:53.23 ]: >>926
スマン、指摘されるまで全く気づかんかった

貼るURLを間違えてた
929 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 18:35:38.20 ]: 上で紹介されている配列回転アルゴリズムはコピーにコストがかかるデータの場合に有利ですね。
テンポラリ配列や２回逆転方法の約半分のコピー回数で済むので
例えば、私の環境では以下のようになりました。
typedef struct {
long id;
long data[1000];
} data_t;
こんなデータの配列 data_t arr[1000] を回転操作( 0〜999 )

$ gcc -O3 -o rotate_temporaly rotate_temporaly.c
$ time ./rotate_temporaly
rreal 0m3.172s
user 0m3.158s
sys 0m0.012s

$ gcc -O3 -o rotate_reverse rotate_reverse.c
$ time ./rotate_reverse
real 0m1.915s
user 0m1.910s
sys 0m0.004s

$ gcc -O3 -o rotate_dolphin rotate_dolphin.c
$ time ./rotate_dolphin
real 0m0.703s
user 0m0.699s
sys 0m0.003s

おそらく細かい実装の違いではカバーしきれないほどの差が出ます。
まあ、この種のアルゴリズムが必要になる前にデータ構造の見直しをしたほうがいいとは思います。
リスト構造なら一部の配線付け替えで一瞬です
930 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 19:22:14.99 ]: アルゴリズムの性能評価をするときに、コンパイラの最適化を有効にするのって無しでしょ？
931 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 20:04:05.29 ]: >>930 確かにそうですね。
というわけで最適化無しでもやってみました。
$ time ./rotate_temporaly
real 0m4.044s
user 0m4.032s
sys 0m0.011s

$ time ./rotate_reverse
real 0m10.280s
user 0m10.274s
sys 0m0.005s

$ time ./rotate_dolphin
real 0m3.495s
user 0m3.490s
sys 0m0.004s

これで比べるとテンポラリ配列の方法もそれなりに健闘しています。
二回逆転の方法は、おい大丈夫か？レベルです。最適化ってすごいですね
932 名前：デフォルトの名無しさん [2011/11/09(水) 21:51:10.45 ]: >>929
珠玉のデータはもっとでかい配列までとってたような気が。

> リスト構造なら一部の配線付け替えで一瞬です
目的の場所まで行くのに時間かかるから、結局O(n)だけどね。
933 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 21:53:47.81 ]: >>930
> アルゴリズムの性能評価をするときに、コンパイラの最適化を有効にするのって無しでしょ？
なんで？ありでしょ。
どれもO(n)だ、結局どれが速いのってときに、
最適化しなかったらコーディングの差を見てるだけになる。
934 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 22:12:51.33 ]: コンパイラの最適化で比較するのは、本当に最後の最後
その前にもっとやっておくことがある

同じ O(n) でも n を何で測るかをちゃんと揃えないといけない
例えば一方のアルゴリズムはステップ数で測って、
他方のアルゴリズムはステップ数にメモリアクセスの数も含めて測る
なんてやってはいけない

その上でまだ同じ O(n) なら、今度はオーダーを計算する為に省いた係数を
低次元のものまでちゃんと補ってより細かく比較しないといけない

コンパイラの最適化に頼って処理速度によるアルゴリズムの優劣を比較するのは
少なくともその後にすべきで、同じ O(n) だからといって安易にすべきではない

それでも、その最適化による比較で分かるのはアルゴリズムの質的な優劣ではなく、
単にそのコンパイラや表現する言語と「相性が良いかどうか」でしかないと思う
935 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 22:17:14.40 ]: node数が億単位(>=2^32)になるとlinked list実装の方がはるかに高速というハード（システム)も現実にある
936 名前：931 mailto:sage [2011/11/09(水) 22:30:20.09 ]: ごめんなさい。単に興味を持ってやってみたらこうなったよ程度に受け取ってください。
937 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 22:34:33.71 ]: キャッシュの有効利用でさえ、良いアルゴリズムの条件。
最適化なしに測定なんかできん。
938 名前：931 mailto:sage [2011/11/09(水) 22:35:58.31 ]: >>932 なんか蒸し返してしまいますが
>目的の場所まで行くのに時間かかるから、結局O(n)だけどね。
例にあげたようなノードオブジェクトが大きい場合
リンクを辿るのに要するコスト＜ノードコピーに要するコスト
になりますよね。
>>934 の言う
オーダーを計算するための係数の違いという事になると思います。
939 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 22:41:21.64 ]: >>937
そうであるなら、その比較検証に使用したマシンの
キャッシュ性能や特性もちゃんと細かく公表しないとけないね
（細かくと言うのは、処理速度の計測に影響が出る範囲でという意味）

でなければ、追試や他環境との比較ができない
940 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 22:53:01.18 ]: もちろん。最善のアルゴリズムなんて、マシン固有のもので、
だからこそatlasなんかビルド時にベンチマークしてチューンしまくる。
941 名前：デフォルトの名無しさん mailto:sage [2011/11/09(水) 22:53:21.32 ]: そこまでやらなないと優位性をアピール出来ないような代物はハードの性能向上によって数年で淘汰される
942 名前：デフォルトの名無しさん mailto:sage [2011/11/10(木) 12:09:55.94 ]: アホかwwww
BLASが何年生き残ってると思ってるんだwwww

新しいハードウェアができたらそれに合わせてパラメータをチューニングするんだよ
943 名前：デフォルトの名無しさん [2011/11/10(木) 13:38:08.42 ]: ソートのアルゴリズムの性能って、数学的にはデータを移動させる回数で評価するんだっけ？
944 名前：デフォルトの名無しさん mailto:sage [2011/11/10(木) 14:43:19.12 ]: 比較する回数じゃなかったっけ？
945 名前：デフォルトの名無しさん mailto:sage [2011/11/10(木) 14:54:42.97 ]: 比較して、結果によって一定割合で移動が発生するんで、どっちでも同じ
946 名前：デフォルトの名無しさん mailto:sage [2011/11/10(木) 14:57:53.23 ]: もしオーダーが違うなら当然大きい方な
947 名前：デフォルトの名無しさん mailto:sage [2011/11/10(木) 17:56:42.11 ]: 比較に時間がかかる場合、コピー(移動)するのも時間がかかるか？
それは場合によるので一般的な基準はないでしょうね。
948 名前：デフォルトの名無しさん mailto:sage [2011/11/11(金) 09:21:28.97 ]: 無比較ソート
949 名前：デフォルトの名無しさん mailto:sage [2011/11/11(金) 19:47:40.37 ]: 比較にむちゃくちゃ時間がかかる場合は、一般的でない別の手法を使うこともある
移動については、ワードよりでかい物のソートの時はポインタ使うのが普通
950 名前：デフォルトの名無しさん mailto:sage [2011/11/11(金) 22:49:55.98 ]: そんなこんなでソートのアルゴリズムの優劣の比較には
値の大小判定の回数を使うのが普通
951 名前：デフォルトの名無しさん mailto:sage [2011/11/11(金) 22:54:18.35 ]: STLを馬鹿にするな
952 名前：デフォルトの名無しさん mailto:sage [2011/11/12(土) 12:37:01.03 ]: STLを馬鹿レスがどこにある？
953 名前：デフォルトの名無しさん mailto:sage [2011/12/03(土) 21:14:05.30 ]: 乱数におけるXORみたいに、処理が少なくてなおかつそれなりに良い感じにバラける、典型的なハッシュアルゴリズムってありますか？
ちなみに入力はゼロ終端のASCII文字列で出力はintです
954 名前：デフォルトの名無しさん mailto:sage [2011/12/03(土) 21:16:27.86 ]: XORShiftのこと？
955 名前：デフォルトの名無しさん mailto:sage [2011/12/03(土) 21:21:41.41 ]: 俺の知る限りだとZobrist Hashingが使えるね
1文字ごとにあらかじめ用意したテーブルから文字に対応する乱数を持ってきてXORしていく
そこそこ軽くてばらつきはいいよ
956 名前：デフォルトの名無しさん mailto:sage [2011/12/03(土) 22:35:28.70 ]: >>955
良い感じですね
ありがとうございます
957 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 01:46:10.28 ]: 重ならない矩形領域が沢山あって、
矩形領域内を差した時にどの矩形領域内を差したかを
効率よく判定する方法がありましたら教えてください
958 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 01:48:54.81 ]: 個数は何桁くらい？
959 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 01:54:28.80 ]: >>957
矩形をx方向にソートしてｘ方向で二分探索して候補を絞る
絞った候補をy方向にソートしてy方向で二分探索して確定
960 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 03:29:35.09 ]: そんな単純にはいかない
961 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 03:51:15.50 ]: 開き直って全数探索するのがマシだったりするけど
まあ例えばいくつかの領域に区切り
それぞれの領域と重なるオブジェクトを登録しておくとか…
962 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 04:22:36.90 ]: 領域が重なるならR-Treeがいいけど、
重ならなくてもR-Treeでいいかも

まぁ、簡単な >>959 を試してからでいいね
963 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 07:25:04.86 ]: 二分探索が適用できる矩形のソートってどうやるの？
964 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 09:20:04.63 ]: ヒットテストは
1つの点対無数の矩形なのか
無数の点対無数の矩形なのか
何回ぐらい判定するのか
複数回判定するとして矩形の座標は頻繁に更新されるのか固定なのか
このへんの情報で変わってくるよね
点1つ、判定一回なら全探索が最速だし
そうでないなら空間分割が速い
965 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 12:52:40.84 ]: この辺り、「プログラミングのための線形代数」って本を読むと、
いろいろヒントが得られる
966 名前：デフォルトの名無しさん mailto:sage [2011/12/04(日) 12:54:24.91 ]: >>965
間違えちゃった

「コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用」でした
967 名前：デフォルトの名無しさん mailto:sage [2011/12/23(金) 15:08:59.61 ]: 二分木構造の外部イテレーターってスタック無し、巡回済マーク無しでも実装できる？
968 名前：デフォルトの名無しさん mailto:sage [2011/12/23(金) 15:40:59.57 ]: 巡回済マークの一種かもしれんが、Knuthがポインタ付け替え法というのを提案してる。
激しくおすすめできないが。
969 名前：デフォルトの名無しさん mailto:sage [2011/12/23(金) 15:59:05.77 ]: 望みのイテレート順はあるの？
970 名前：デフォルトの名無しさん mailto:sage [2011/12/23(金) 17:28:00.43 ]: >>968
すいませんググったけどわかりませんでした

>>969
pre-orderを考えてます
971 名前：デフォルトの名無しさん mailto:sage [2011/12/24(土) 09:59:11.16 ]: あーごめん「ポインタ反転法」だわ
972 名前：デフォルトの名無しさん mailto:sage [2011/12/26(月) 19:38:15.54 ]: ノードは親ノードの参照を持ってるの?
持ってるのならそれほど難しい問題ではないけども・・・。
973 名前：デフォルトの名無しさん mailto:sage [2011/12/26(月) 20:28:32.10 ]: pre-orderって何？
974 名前：デフォルトの名無しさん mailto:sage [2011/12/27(火) 09:01:44.93 ]: 行きがけ順？
975 名前：デフォルトの名無しさん mailto:sage [2011/12/27(火) 12:35:05.74 ]: Wikipedia で「木構造」を調べてみろ
他の情報も合わせて詳しく載ってる
976 名前：デフォルトの名無しさん [2011/12/27(火) 17:38:21.78 ]: 最大の色差を持つn階調の色テーブルを作るアルゴリズム教えて。
例えば10色欲しいとしたら、10個のテーブルで、各色の色差が最もあるテーブルを作りたい。
単色グラデーションなら簡単だけどRGB織り交ぜた最大の色差を出すのが難しい。
977 名前：デフォルトの名無しさん mailto:sage [2011/12/27(火) 17:54:40.80 ]: 特定の３次元空間の領域内で、
それぞれの距離の平均が最大となるn個の点の座標を求める問題と同じ？

特定の３次元空間の領域内というのがRGB色空間やHSV色空間になるわけだけど
978 名前：デフォルトの名無しさん mailto:sage [2011/12/28(水) 02:14:38.09 ]: 「最大の色差を持つ」がどういうことなのか定義しよう
色iと色jの距離をd(i,j)としたとき、次の(1),(2),(3)のどの定義を採用するかで
(1) min_{i<j} d(i,j) が最大
(2) sum_{i<j} d(i,j) が最大
(3) sum_{i<j} d(i,j)^2 が最大
それぞれ違った答えが出てくる

次にこういった変数の個数の多い問題は手計算で答えを得ようとせず
プログラムを書いて数値計算で求めてみよう
step 1. 乱数でn個の色の初期値を決める
step 2. 乱数でn色の中から1色をランダムに選び、その色だけを変えて他の色を変更せずに
「色差」が最大になるようにする. この操作を1000回ぐらい繰り返す
問題の性質が良ければ、適当な答えに収束するかも
979 名前：デフォルトの名無しさん mailto:sage [2011/12/28(水) 07:20:57.68 ]: 10個くらいなら、全ての点と点の間に自然長が色空間より遙か長いバネを入れて、
色空間の中心にぎゅっと押し込めてから緊張を解くことをシミュレートしてみるとか

やったこと無いから、実際にどうなるかは知らんが
980 名前：デフォルトの名無しさん mailto:sage [2011/12/28(水) 08:21:41.06 ]: 大団円
981 名前：デフォルトの名無しさん mailto:sage [2011/12/28(水) 19:20:40.87 ]: １０色なら、真っ白と真っ黒と円周上の６色だよな？
982 名前：デフォルトの名無しさん mailto:sage [2011/12/28(水) 19:25:49.87 ]: >>981
証明しろよ
983 名前：デフォルトの名無しさん mailto:sage [2011/12/29(木) 10:19:39.29 ]: >>981
６角形の一辺の２色と、一つ飛びの２色との間にある色は
一辺の色差より大きい
だめだ論破
８色だと、立方体の頂点でいいんだよな。たぶん。
984 名前：デフォルトの名無しさん mailto:sage [2011/12/29(木) 14:20:05.95 ]: RGBでもHSVでも空間距離が単純に見た目の色差と比例するわけではないよ
全ての点間で距離を最大化できても見づらい色同士が出てくる
985 名前：デフォルトの名無しさん mailto:sage [2011/12/29(木) 21:05:13.74 ]: n体の色相環を使うのはダメなの？
986 名前：デフォルトの名無しさん mailto:sage [2011/12/29(木) 21:15:13.49 ]: >>984
> 全ての点間で距離を最大化できても見づらい色同士が出てくる

かどうかは、やってみなくちゃ分からんと思うが
そもそも、距離を最大化する配置が分かってないのに言えんだろ

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

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