＜集大成＞アルゴリズム大辞典
レス数が950を超えています。1000を超えると書き込みができなくなります。
0001デフォルトの名無しさん
NGNG0002デフォルトの名無しさん
NGNG0003デフォルトの名無しさん
NGNG0004デフォルトの名無しさん
NGNG0005デフォルトの名無しさん
NGNG0006デフォルトの名無しさん
NGNG0007デフォルトの名無しさん
NGNG0008デフォルトの名無しさん
NGNG0009デフォルトの名無しさん
NGNG僕のは、まだ新品同然です。
この本の内容を、あらかた覚えるにはどれくらいの月日がかかったのでしょうか？
0010デフォルトの名無しさん
NGNG0011デフォルトの名無しさん
NGNGあの本は事典ですよ？
0012デフォルトの名無しさん
NGNG0013デフォルトの名無しさん
NGNGゴリズム氏が考え出したとある手法の一つです。
0014デフォルトの名無しさん
NGNGちがうよ。
１６世紀、オーストリアのディマン＝アルゴが提唱した基礎的な音楽のリズムだよ。
0015デフォルトの名無しさん
NGNG0016デフォルトの名無しさん
NGNG0017デフォルトの名無しさん
NGNG事典として使うものですか。。。
どうりでいっぱいある訳だ
0018デフォルトの名無しさん
NGNGあれのJava版についてはどう思うよ？
アルゴリズムが増えて改良されてなかなかのもんだと思うが。
しかしあの本のソースコード書いた香具師は
クラス継承の合理的な使い方を分かってない感じだな。
0019デフォルトの名無しさん
NGNG0020デフォルトの名無しさん
NGNG0021デフォルトの名無しさん
NGNG0022デフォルトの名無しさん
NGNGJava版出てるの知らんかったよ。今度買ってみる。
0023デフォルトの名無しさん
NGNG0024デフォルトの名無しさん
NGNG0025デフォルトの名無しさん
NGNG0026デフォルトの名無しさん
NGNG0027デフォルトの名無しさん
NGNGそんなに多くないよ
0028デフォルトの名無しさん
NGNG0029デフォルトの名無しさん
NGNGそんなに暇ならコードの一つぐらい覚えろ
他力本願野郎がｗ
0030デフォルトの名無しさん
NGNG0031デフォルトの名無しさん
NGNGブルーベレーちゃんが手作業で並べ替えてくれまつ。
http://valve.kubota.co.jp/main.html
0032デフォルトの名無しさん
NGNG0033デフォルトの名無しさん
NGNG計算確率アルゴリズムについて、知っている人、または
説明があるサイトをご存知の方は教えてください
お願いします。
0034デフォルトの名無しさん
NGNG0035デフォルトの名無しさん
NGNGどうやってファイルに遠近感を付けるというのだ！
0036デフォルトの名無しさん
NGNGと言ってみるﾃｽﾄ
0037デフォルトの名無しさん
NGNG0038デフォルトの名無しさん
NGNG0039デフォルトの名無しさん
NGNG0040デフォルトの名無しさん
NGNG・ ・
△
ЦЦ
0041デフォルトの名無しさん
NGNG0042デフォルトの名無しさん
NGNGそれともキーが多次元でランダムなのか？
0043ケンや
NGNGパソコン買い換えるので何とか壊してください。
[email protected]
0044デフォルトの名無しさん
NGNG□□□■■□□□□□■□□□□□□□■■■■■■■■■■■■□□
□□■■□□□□□■■■■■■□□□□□□□□□□□□□■■□□
□■■□□■□□□■□□□□■□□□□□□□□□□□□■■□□□
□□■□■■□□■■■□□■■□□□□□□□□□□□■■□□□□
□□□■■□□■■□■■■■□□□□□□□□□□□■■□□□□□
□□■■□□□□□□□■■□□□□□□□□□□□■■□□□□□□
□□■□□□■□□□■■■■□□□□□□□□□□■□□□□□□□
□■■■■■■□□■■□□■■□□□□□□□□□■□□□□□□□
□□□□■□□□■■□□□□■■□□□□□□□□■□□□□□□□
□□■□■□■□□□□■■□□□□□□□□□□□■□□□□□□□
□□■□■□■□□□□□■■□□□□□□□□□□■□□□□□□□
□■■□■□■□□□□□□□□□□□□□□□□□■□□□□□□□
□■□□■□□□□■■■□□□□□□□□□□□□■□□□□□□□
□□□□■□□□□□□■■■□□□□□□□□□□■□□□□□□□
□□□□■□□□□□□□□■■□□□□□□■■■■□□□□□□□
0045デフォルトの名無しさん
NGNG00461
NGNGついに強固なスレが現れました
00471
NGNG□□□■■□□□□□■□□□□□□□■■■■■■■■■■■■□□
□□■■□□□□□■■■■■■□□□□□□□□□□□□□■■□□
□■■□□■□□□■□□□□■□□□□□□□□□□□□■■□□□
□□■□■■□□■■■□□■■□□□□□□□□□□□■■□□□□
□□□■■□□■■□■■■■□□□□□□□□□□□■■□□□□□
□□■■□□□□□□□■■□□□□□□□□□□□■■□□□□□□
□□■□□□■□□□■■■■□□□□□□□□□□■□□□□□□□
□■■■■■■□□■■□□■■□□□□□□□□□■□□□□□□□
□□□□■□□□■■□□□□■■□□□□□□□□■□□□□□□□
□□■□■□■□□□□■■□□□□□□□□□□□■□□□□□□□
□□■□■□■□□□□□■■□□□□□□□□□□■□□□□□□□
□■■□■□■□□□□□□□□□□□□□□□□□■□□□□□□□
□■□□■□□□□■■■□□□□□□□□□□□□■□□□□□□□
□□□□■□□□□□□■■■□□□□□□□□□□■□□□□□□□
□□□□■□□□□□□□□■■□□□□□□■■■■□□□□です。
0048デフォルトの名無しさん
NGNG0049デフォルトの名無しさん
NGNG教育用？
クレオソートってどんなときに使うの？
0050デフォルトの名無しさん
NGNG> クレオソートってどんなときに使うの？
下痢止めの薬を作るとき、かな。
0051デフォルトの名無しさん
NGNG使うときほぼないけど、学習用によく使われるみたい。
00521
NGNGバルブソートでググったら、なんとこのスレが２番目にあったよ
0053デフォルトの名無しさん
NGNG0054デフォルトの名無しさん
05/01/30 17:56:480055デフォルトの名無しさん
05/03/08 22:07:30サンプリングレートは8000。
チャンネルは1つ(モノラル)。
ビット数は16。
音声データは160バイト(20[ms])に細かく切られている。
これが複数の音源からやって来ます。
複数の音源の同期は取りません。取り敢えずタイミングは無視してミックスします。
同期よりも遅延の方を問題に思っていますので。
こんな感じで良いのでしょうか？
for( int i = 0; i != 160; i++ )
if( buffer_1[i] < buffer_2[i] )
buffer_o[i] = buffer_2;
else
buffer_o[i] = buffer_1;
その後でDirectXでストリーミング再生します。
005655: 訂正
05/03/08 22:08:24if( buffer_1[i] < buffer_2[i] )
buffer_o[i] = buffer_2[i];
else
buffer_o[i] = buffer_1[i];
0057デフォルトの名無しさん
05/03/09 00:07:52DirectXとかよくわからんけど
005855
05/03/09 00:37:21ポイントは、音源Aと音源Bのデータをミックスする時にどの様にすべきかです。
例えば以下の様な事が単純に思い付きます。
1.AとBの平均を取る。
out=(A+B)/2
2.AとBを単純に足す。最大値を越えた場合(65535<(A+B))は最大値(==65535)とする。
out=max(65535, A+B)
3.AとBを比較して、大きい方の値とする。(>>56の内容に等しい)
out=max(A, B)
良く分かりませんが、他にもっとインテリジェンスなやり方が有ったら教えて頂きたいなあと思った次第です。
0059デフォルトの名無しさん
05/03/09 00:51:31(a, bは入力レベル。通常は1でいいと思うけど、音割れするようだったら絞ればいい)
006055
05/03/09 01:03:55実はRTPもどきを使って3人以上で会話するってプログラムを作ってました。
会話の場合は、1人が喋っていても他の2人は無音の場合が多く、>>59のやり
方で問題無いと思います。
0061デフォルトの名無しさん
2005/04/04(月) 15:57:46サウンドプログラミング2
http://pc8.2ch.net/test/read.cgi/tech/1091054082/
で聞いてくれれば良かったかもな。
問題は、複数の音源の場合、サンプリングレートが微妙に違う点にあると思うよ。
まあ、無音の間に適当に入れたり出したりして誤魔化すんだろうけど
0062デフォルトの名無しさん
2005/04/04(月) 16:01:51out = r*(A+B);
if( abs(out)>=0x7fFF) r = r*0.95 else r=min(1.0, r+1/8000);
こんな感じで、合成音がクリッピングしたら、出力を絞るような方式がいいと思うよ。
0063デフォルトの名無しさん
2005/04/30(土) 22:21:530064デフォルトの名無しさん
2005/04/30(土) 22:25:140065デフォルトの名無しさん
2005/04/30(土) 22:37:29Redoはログからもう一度ユーザーの内容を再現していく。
うまく動くと面白いし、何かを編集するアプリなら必須機能の１つ。
がんばって作ってくれ。
0066デフォルトの名無しさん
2005/04/30(土) 22:56:45現在の状態を全部ファイルにバックアップする
006763
2005/04/30(土) 23:00:560068デフォルトの名無しさん
2005/05/01(日) 12:54:000069デフォルトの名無しさん
2005/05/01(日) 13:11:040070デフォルトの名無しさん
2005/05/01(日) 13:15:15図書館から借りてくることをオススメする
0071デフォルトの名無しさん
2005/05/02(月) 01:03:58されません
0072デフォルトの名無しさん
2005/05/02(月) 19:34:010073デフォルトの名無しさん
2005/05/02(月) 19:47:56m_buttonHogeを用意しといて
if(stCell == 0)
m_buttonHoge(FALSE);
else
m_buttonHoge(TRUE);
ってな感じでは？
0074デフォルトの名無しさん
2005/05/02(月) 19:49:540075デフォルトの名無しさん
2005/05/02(月) 19:53:44そこが難しいんです
0076デフォルトの名無しさん
2005/05/02(月) 19:56:24m_buttonHogeを用意しといて
if(stCell[x][y] == 0)
m_buttonHoge.ShowWindow(FALSE);
else
m_buttonHoge.ShowWindow(TRUE);
のまちがいだろ
0077デフォルトの名無しさん
2005/05/02(月) 20:03:22{
if(stCell[x-1][y-1]
m_buttonHoge[x-1][y-1].ShowWindow(FALSE);
else
m_buttonHoge[x-1][y-1].ShowWindow(TURE);
if(stCell[x][y-1]
m_buttonHoge[x][y-1].ShowWindow(FALSE);
else
m_buttonHoge[x][y-1].ShowWindow(TURE);
if(stCell[x][y-1]
m_buttonHoge[x][y-1].ShowWindow(FALSE);
else
m_buttonHoge[x][y-1].ShowWindow(TURE);
if(stCell[x+1][y-1]
m_buttonHoge[x+1][y-1].ShowWindow(FALSE);
else
m_buttonHoge[x+1][y-1].ShowWindow(TURE);
以下略
return TRUE;
}
0078デフォルトの名無しさん
2005/05/02(月) 20:09:35↓
０だ
↓
周りを探す
↓
また０だ
↓
周りを探す
↓
・・・・・・元の場所わかんねぇ('A`)
0079デフォルトの名無しさん
2005/05/02(月) 20:18:10reverse(0, 0);
は大丈夫なのかな？
0080デフォルトの名無しさん
2005/05/02(月) 20:25:38>>79
TRY CATCHでくくって例外は処理しないようにすれば？
0081デフォルトの名無しさん
2005/05/02(月) 20:32:24TUREって何よ？
0082デフォルトの名無しさん
2005/05/02(月) 20:33:16つまんねーレスすんなよ。
0083デフォルトの名無しさん
2005/05/02(月) 20:41:59アドレスと文字列の区別は・・・どうするのが一般的？
2バイト文字にぶち当たったらとかかな。
0084デフォルトの名無しさん
2005/05/02(月) 20:44:22"つれ"た、ってことなんじゃ？
0085デフォルトの名無しさん
2005/05/02(月) 22:39:55sedでよければｗ
0086デフォルトの名無しさん
2005/05/02(月) 22:47:57そこで再帰関数ですよ。
こんな感じだったけなぁー。
なんせ3年前位に作ったやつだから忘れちゃってる。
間違ってる可能性大
int hoge(int x,int y){
int b=0;
if(table[x][y] == BOME){
return BOME;
}
for(int i=0;i<9;i++){
if(table[pos[i].x+x][pos[i].y+y]==BOME){
b++;
}
}
if(b==0){
for(int i=0;i<9;i++){
hoge(pos[i].x+x,pos[i].y+y)
}
}
return 0;
}
0087デフォルトの名無しさん
2005/05/04(水) 21:48:03ググってもでてきません。よろしくお願いします。
0088デフォルトの名無しさん
2005/05/04(水) 21:50:41検索が下手。
http://www.google.co.jp/search?hl=ja&q=%E8%99%9A%E7%84%A1%E5%83%A7%E3%81%A8&btnG=Google+%E6%A4%9C%E7%B4%A2&lr=lang_ja
0089デフォルトの名無しさん
2005/05/04(水) 23:06:09ttp://www.ffortune.net/comp/develop/sort/gaikan.htm
0090デフォルトの名無しさん
2005/05/04(水) 23:52:38ありがとうございます。
でもできたら参考文献とかあったらうれしいな、なんて
0091デフォルトの名無しさん
2005/05/05(木) 00:02:290092デフォルトの名無しさん
2005/05/05(木) 00:12:42Comb sort algorithm
http://www.google.co.jp/search?hl=ja&q=Comb+sort+algorithm&lr=
0093デフォルトの名無しさん
2005/05/05(木) 04:30:230094デフォルトの名無しさん
2005/05/07(土) 20:38:46その二つの配列に共通する数値のみを選び出す効率的なアルゴリズムって何かありますか？
0095デフォルトの名無しさん
2005/05/07(土) 21:17:43a.格納位置も一緒
b.格納位置が違っていてもＯＫ
b.だとすると数値がダブっている場合どう考えるんだ？
0096デフォルトの名無しさん
2005/05/08(日) 05:15:32衝突がなければO(1)
0097デフォルトの名無しさん
2005/05/08(日) 07:11:44片方で分布数えソートの前段階（分布だけ調べる）まで行い、
もう片方をスキャンすれば、重複する値がわかる
0098デフォルトの名無しさん
2005/05/08(日) 12:50:16配列に格納されている数値が何かのハッシュだったら、どうするの？
0099デフォルトの名無しさん
2005/05/08(日) 15:42:48内容がなんであっても、ハッシュで問題ないと思うがどうだろう？
0100デフォルトの名無しさん
2005/05/13(金) 13:47:35複数のベジェ曲線へと変換するアルゴリズムって何かありますか？
http://www.simdesign.nl/bezier.html
上記のような有料のライブラリは見つかったのですが・・・。
0101デフォルトの名無しさん
2005/05/13(金) 15:56:51そのサンプリング点を端点に、
端点の微分が一致するという条件で解いたらどう？
0102デフォルトの名無しさん
2005/05/13(金) 16:00:58ttp://www.tensyo.com/urame/prog/linealgo.htm
ここの 折れ線から滑らかな曲線に という所に、点を与えながら処理する方法が
0103デフォルトの名無しさん
2005/05/15(日) 19:46:060104デフォルトの名無しさん
2005/05/17(火) 09:09:03ここの 折れ線から滑らかな曲線に 以外に
複数のベジェ曲線へと変換するアルゴリズムって何かありますか？
0105デフォルトの名無しさん
2005/05/17(火) 23:45:000106デフォルトの名無しさん
2005/05/18(水) 07:29:50それ以外にと聞かれるならば
１、３次スプライン補間法 で解いてからベジェに変換する
２、混合スプライン、ベーススプライン等で解いてからベジェに変換する
という方法が考えられます
0107デフォルトの名無しさん
2005/05/20(金) 09:14:39ベジェ曲線を描くのではなく、点を間引いて描きたいのですが、
どのように点を間引いたらいいかがわかりません。
何か良いアイデアはありませんか？
0108デフォルトの名無しさん
2005/05/20(金) 23:32:010109デフォルトの名無しさん
2005/05/21(土) 08:38:54たとえば、直線的に引いた通過点を間引きたいならそうすればいい
前２点の延長線からの誤差が一定いないなら、その前の点を除くとかさ
0110デフォルトの名無しさん
2005/05/21(土) 19:06:48単純な検索はBtree*を用いて作成しましたが、XMLのある部分が合致するような
検索をする場合どのような手法があるのでしょうか？
0111デフォルトの名無しさん
2005/05/21(土) 19:44:10となると、その部分をB木の検索キーに入れておくしかないかもな
0112デフォルトの名無しさん
2005/05/21(土) 20:40:13後差分を取る方法って今主流な方法でどのような方法があるのでしょうか？
XMLデータの差分を取ってみたいと思うのですがそっち方面は何もわかりません。
0113デフォルトの名無しさん
2005/06/15(水) 08:29:58int i=1;調べるビット列 bits;
while(i<sizeof(調べるビット列)*8+1){
if(bits%2){
cout << i << ",";
}
bits >> 1;
i++;
}
cout << endl;
0114デフォルトの名無しさん
2005/06/15(水) 11:51:50while(bits!=0)
{
if(bits&1!=0)
{
cout << i << ",";
}
i++;
bits=bits>>1;
}
cout << endl;
上位がゼロになればそれ以上調べなくてもよい。
ビットが1つしか立ってないなら、二分探索が使えるが。
0115デフォルトの名無しさん
2005/06/15(水) 15:49:290116デフォルトの名無しさん
2005/06/15(水) 22:55:010117デフォルトの名無しさん
2005/06/16(木) 07:05:100118デフォルトの名無しさん
2005/06/16(木) 09:34:53Prologの述語呼び出しや、述語定義の参照述語を使って
部分構造の検索をする。
0119デフォルトの名無しさん
2005/06/24(金) 07:20:01m/456 * 100/101 < x2 < m/456 * 100/99
m/789 * 100/101 < x3 < m/789 * 100/99
x1, x2, x3 に正の整数が含まれるm > 0の条件は？
0120デフォルトの名無しさん
2005/07/09(土) 20:48:02全文検索系のアルゴリズムが参考になるんじゃない？
suffix tree とか suffix array とか。
ってもう一月以上前か。
0121デフォルトの名無しさん
2005/08/26(金) 11:16:09パトリシアトライ木とハッシュテーブルを比較したら、
ハッシュの方が速い事が多いんですが、
こんなものでしょうか？（特に検索はハッシュが倍以上速い）
なんかパトリシアは苦労して作ったのにこれではちょっと納得いかなかったので。
パトリシアの枝を平衡木にすればマシになるのかな？
0122デフォルトの名無しさん
2005/08/26(金) 13:38:290123デフォルトの名無しさん
2005/08/26(金) 22:16:26msは挿入、検索で、検索の速い順に並んでます。
データの種類にもよるでしょうが、自分が対象とするデータはほぼこの順位です。
検索ではTernary Search Trieが健闘してます。
でもtstとtrieはメモリ食います。
>tst (Ternary Search Trie)
55040 件辞書に登録しました。
1268ms
81ms
>hash
55040 件辞書に登録しました。
1224ms
82ms
>pat (Patricia)
55040 件辞書に登録しました。
1444ms
158ms
>trie (Trie)
55040 件辞書に登録しました。
1285ms
224ms
0124デフォルトの名無しさん
2005/08/26(金) 22:25:10かまいたちの夜２のネタバレｷﾀ━━━━━━(ﾟ∀ﾟ)━━━━━━ !!
0125デフォルトの名無しさん
2005/08/27(土) 03:16:430126デフォルトの名無しさん
2005/08/27(土) 03:58:42patriciaは辞書データ構造に使うんだよ
圧縮が効くしインクリメンタルサーチもできるという特性がある
hashはキーがまるごと必要でしょ
0127デフォルトの名無しさん
2005/08/27(土) 04:05:02中学生か？
0128デフォルトの名無しさん
2005/08/27(土) 04:28:18条件分岐は一回以下とする。
0129デフォルトの名無しさん
2005/08/27(土) 06:49:06普通のパターンだと、条件分岐1回では直角三角形を分離できない（はずだ）けどいいの？
トリッキーにすれば、条件分岐を使わずにできるけど
0130デフォルトの名無しさん
2005/08/27(土) 07:26:28は宿題の丸投げか？
自分で考えろよ
0131デフォルトの名無しさん
2005/08/27(土) 10:06:02こんなものも自分ひとりで解決できないようじゃ先が思いやられるな
0132デフォルトの名無しさん
2005/08/27(土) 10:41:25cosA・cosB・cosC ＜ 0
なら鈍角だー
0133121
2005/08/28(日) 06:19:01tstがこれぐらい差が付くとhashの３倍はメモリ食っても使ってみたくなる。
>tst
57260 件辞書に登録しました。
1275ms
63ms
>hash
57260 件辞書に登録しました。
1284ms
78ms
>pat
57260 件辞書に登録しました。
1450ms
106ms
0134デフォルトの名無しさん
2005/08/28(日) 07:01:14ピーキーなのきぼん
0135デフォルトの名無しさん
2005/09/16(金) 09:46:27なかなかいい方法が浮かばないんで、何かいい方法があれば
教えてください。
二次元配列のデータ
dat[i][j]
という200x200くらいのデータ（モノクロ画像データ）があります。
そのデータに対して、i,j面でスムージングをして、new_dat[i][j]
を作りたいのですが、どうするのが簡単で良い方法でしょうか？
簡単にスムージング（もどき）が出来るアルゴリズムをご存知の方が
居られれば教えてください。
0136デフォルトの名無しさん
2005/09/16(金) 10:01:42線形のローパスフィルタかけるか、中央値フィルタかけたら？
0137デフォルトの名無しさん
2005/09/16(金) 10:09:32a01 = 1
a11 = 1
{lon w
w = a00*dat[i][j];
w+= a01*dat[i][j+1]+a01*dat[i][j-1];
w+= a10*dat[i+1][j]+a01*dat[i-1][j];
new_data[i][j] =w /(a00+2*a01+2*a10);
};
ってな所から始めたら?
0138デフォルトの名無しさん
2005/10/22(土) 08:57:260139デフォルトの名無しさん
2005/10/22(土) 10:44:17if (x < 0) x = 0;
と
x = max(x, 0);
はどっちが優れてるの？
0140デフォルトの名無しさん
2005/10/22(土) 18:50:57コンパイラによるだろmax関数の解釈とかは、
とりあえずアセンブラの出力を比べてみては。
0141デフォルトの名無しさん
2005/10/22(土) 19:23:39最上位ビットを0にするのがいいんじゃないの？
0142デフォルトの名無しさん
2005/10/22(土) 19:45:38if (x < 0) x = 0;
0143デフォルトの名無しさん
2005/10/23(日) 14:00:30アセンブラ読めない、頑張ってみた
---if(x<0) x=0;
+++x=max(x,0)
movl $1, -4(%ebp)
- cmpl $0, -4(%ebp)
- jns L2
- movl $0, -4(%ebp)
-L2:
+ movl $0, 4(%esp)
+ movl -4(%ebp), %eax
+ movl %eax, (%esp)
+ call _max
+ movl %eax, -4(%ebp)
movl $0, %eax
左の列が言わんとしてる事はわかるんですが、他は字に見えません
movlとjnsとcmplとcallがどれだけの奴か知らないので臨場感が伝わってきませんでした。
>142
おすすめのポイントはcallの有無？
>141
おー！と思ったけどビット演算は自分の脳に負荷がかかりました
とりあえず右の列
グーグルと一緒にとっつかまえてくる
0144デフォルトの名無しさん
2005/10/23(日) 20:02:39max()自体が最適化されてcallがなくなる処理系もある。
>>142 は記述形式がアセンブラに一番近い、つまり
最適化の有無に因らず、どのような処理系でも
「一番速いコード」が生成される「はず」
が根拠だ。
0145デフォルトの名無しさん
2005/10/23(日) 20:54:550146デフォルトの名無しさん
2005/10/27(木) 07:56:09つまり、ｘが負数ならゼロにするという事は、 ２の補数表現であれば
xの最上位ビットが１の時に、xを0にすればいい。
よって x := x and (not (x asr 31) ) という計算と等価となる
・符号拡張命令
・バレルシフタ
のどちらかを持っているCPU（x86は両方持ってる）なら
符号拡張
NOT
AND
の３ステップで実現出来る
0147デフォルトの名無しさん
2005/10/28(金) 03:24:19計算マンセーの前時代的思考方法だな。
xが整数型であると、どこに書いてある？
という、無駄な突っ込みは別として、その手の置き換えは
「必ず計算が実行される」と言う面から考えると、速くも、
また、美しくもない。
if (x < 0) x = 0;
は、しなくとも良い計算や代入は発生しない。
そう言った意味で
x := x and (not (x asr 31) )
は、問題外。
0148デフォルトの名無しさん
2005/10/28(金) 06:29:38だからもし突っ込むなら、 ２の補数の方だろう
0149デフォルトの名無しさん
2005/10/28(金) 07:31:16つまり >>147の前半の突っ込みは無駄ではなくて、無知なツッコミ。
後半もちょっと変
if (x < 0) x = 0; は表現であって、実際に分岐を指示しているわけではない。
この計算は賢いコンパイラなら
最近のX86に対応しているなら 条件付代入命令に変換される可能性が高い
CMP
CMOVS
となる。
ちなみに、浮動小数点命令にも条件付代入命令はある
さて、分岐と演算命令のどちらが高速という話なら、
分岐命令は並列演算の妨げとなるが
演算命令は並列化可能な部分は並列化される故に
命令数が多少多くても現在でも分岐より演算が速く、将来はもっと高速になる可能性が大
並列処理のことを言わず、一昔前のCPUや現在のH8やSHでは
分岐命令は演算命令２～４つ分のコストを支払わされるのが普通
なお、この部分 x := x and (not (x asr 31) ) も 条件代入も並列化出来ないが
その次に同じような演算があれば先読み実行される可能性があるという事
0150デフォルトの名無しさん
2005/10/28(金) 16:21:10x := x and (not (x asr 31) )
は、問題外ということでよろしかったですか？
0151デフォルトの名無しさん
2005/10/28(金) 17:14:49それがそのまま通る言語がそもそもないだろう。 あほか？
0152デフォルトの名無しさん
2005/10/28(金) 17:23:32(x and (not (x asr 31))) が格別優れているわけでもなかろが、
>>150
ええと、>>147はまったく意味の無い記述とされてるし、
32bit(asr 31)などの算出はコンパイラに充分可能なのは自明だと思うし、
ようするにalgorithmなり記述を評価する能力無し、という告白でよろしいか?
0153デフォルトの名無しさん
2005/10/28(金) 17:30:27x := x and (not (x asr 31) )
は、アルゴリズムじゃなくて「技」だしなあ。
0154デフォルトの名無しさん
2005/10/28(金) 17:38:39x := x and (not (x asr sizeof(x) )
0155デフォルトの名無しさん
2005/10/28(金) 17:48:120156デフォルトの名無しさん
2005/10/28(金) 17:50:29覚えてないけど、符号拡張＋XORだったかな？
0157デフォルトの名無しさん
2005/10/28(金) 18:41:28＞ 32bit(asr 31)などの算出はコンパイラに充分可能なのは自明だと思うし、
さすがに、そんなコンパイラは使いもんにならないと思う。
31と記述しているのに64bitサイズの変数だったら64bit(asr 63)と解釈する
となると、マジヤバイ。
>>154
えーと、１年生ですか？w
0158デフォルトの名無しさん
2005/10/28(金) 18:54:11>31と記述しているのに64bitサイズの変数だったら64bit(asr 63)と解釈する
!!!? バカ、マジヤバス。低脳乙www 終了。
0159デフォルトの名無しさん
2005/10/28(金) 18:54:210160デフォルトの名無しさん
2005/10/28(金) 18:55:310161デフォルトの名無しさん
2005/10/28(金) 18:56:510162デフォルトの名無しさん
2005/10/28(金) 19:14:010163デフォルトの名無しさん
2005/10/28(金) 23:28:42えーと、幼稚園ですか？w
0164デフォルトの名無しさん
2005/10/29(土) 00:12:48おまえがなwww
0165デフォルトの名無しさん
2005/11/03(木) 23:15:110166デフォルトの名無しさん
2005/11/08(火) 00:13:18アホ向けに解説してあるサイトか書籍ないでしょうか。
0167デフォルトの名無しさん
2005/11/08(火) 00:33:13ttp://unit.aist.go.jp/itri/knoppix/
0168デフォルトの名無しさん
2005/11/08(火) 01:55:08クノッピでBtreeが理解できるの?
0169デフォルトの名無しさん
2005/11/08(火) 05:05:57ともかくそんな高度な話題を論じれる貴方達を尊敬する。
俺にはついていけないよ。
0170デフォルトの名無しさん
2005/11/09(水) 00:00:21読み辛いのなら、デバッガを使って変数の値を追っていくといい
0171デフォルトの名無しさん
2005/11/10(木) 01:14:30http://lecture-wiki.ecc.u-tokyo.ac.jp/index.php?uonoue%2FJSR%2F11
このページにもその部分だけ書かれてなくて困ってます。
「平方採中法」とは違うものなんでしょうか？
0172171
2005/11/10(木) 04:11:500173デフォルトの名無しさん
2005/11/13(日) 19:12:43によってバランスを保つことを勉強しました．
単一回転と二重回転の選択の判断ってどうしてるんですか?
0174デフォルトの名無しさん
2005/11/13(日) 20:25:30その勉強した内容は、隅から隅まで読んでみたのかな？
たとえば次のページみたいに、普通は書いてあるよ。
ttp://lecture.ecc.u-tokyo.ac.jp/~yamaguch/pub/cp2-8/what-is-search-avl.html
0175& ◆i.twkzJbf.
2005/11/13(日) 21:41:13大変，ありがとうございます!
図書館にあるアルゴリズムの本をあさり，「こういうパターン
の時は単一回転」という図は掲載されていたのですが，明確に
文章で書かかれているものが，無かったんです．
上記のURL には明確に文章で記載されていたので，理解できました．
ありがとうございました．
0176デフォルトの名無しさん
2006/02/05(日) 09:40:090177デフォルトの名無しさん
2006/02/05(日) 09:41:090178デフォルトの名無しさん
2006/02/15(水) 22:05:35できればCASL2形式のソースコードで頼む。
0179デフォルトの名無しさん
2006/03/06(月) 23:50:20また、ArcToを実装する場合、Google等でそのアルゴリズムの名前を検索するとヒット
するようなメジャーなアルゴリズムってあるのでしょうか？
今、DirectXを使用してVRAMに直接弧を描画する関数を作っています。
楕円描画のアルゴリズムを使用して、弧を描く関数自体はできたのですが、問題点として、
① 条件分岐が多くスパゲッチーなコードになる
② ○○のアルゴリズム、とかの名前で、世間一般に知られているかが分からず、
スパゲッチーなコードでも、その内容を見た人が調べて把握できるかが不安。
今後の保守性に不安があるので、弧の描画に用いられている一般的な
アルゴリズムがあるなら、そちらに揃えたいです。
ないなら、多少速度を犠牲にしてもGDIのArcToを使ってしまおうかと悩みちゅうです。
0180デフォルトの名無しさん
2006/03/08(水) 11:31:540181デフォルトの名無しさん
2006/04/05(水) 02:28:16しかし、ある条件を満たしている間は最小値を、
そうでない場合は最大値を取り出すとなると、効率のいい方法が思いつきません。
線形探索で最大値を探し出すことになってしまいます。
（ソースコードは以下のURL）
ttp://anotherred.hp.infoseek.co.jp/cgi-bin/src/up1346.txt
なにかいい方法は無いものなのでしょうか。
0182デフォルトの名無しさん
2006/04/05(水) 02:32:24某ソフトのある部分と流れがそっくりですが・・・
そっくりそのままコピペしたわけではないので、
そこらへんは目をつぶっていただけるとありがたいです。
0183デフォルトの名無しさん
2006/04/05(水) 05:54:32ようするに、最大値と最小値の両方を高速に取り出せるデータ構造か。
両方 O(1) で出来るものはしらんが、両方 O(log n) でできるものならB木の類。
0184デフォルトの名無しさん
2006/04/05(水) 12:56:410185デフォルトの名無しさん
2006/04/05(水) 13:19:15木構造ですか・・・
たしか、木構造を使用したデーターベース関連のソースがあるので、
速度のことさえ気にしなければいけそうですね。
ちょっとベンチマークを取ってることにします。
わざわざ答えてくださりありがとうございました。
>184
二分ソートを使うとなると、かえって遅くなりそう・・・
適切な位置を探すのにO(log n)
データの移動に最悪でO(n)
平均はいくらぐらいか知らないけど。
0186デフォルトの名無しさん
2006/04/23(日) 23:18:330<= x < N までの値を巡回する式を作りたいのです。
用途としては、選択肢を指すカーソルが一番下まで行った時、さらに下ボタンを押すと一番上を指すように。
一番上まで行った時にさらに上ボタンを押すと、一番下を指すように。
という使い方です。
x = (x + N) % N;
でとりあえず事足りているのですが、xが-N未満だった時によろしくありません。
Nが2の乗数なら、マスクをとるという方法も思いつくのですが…。
何か定型的な方法はありますでしょうか？
x = ((x % N) + N) % N;
でもとりあえず良いのですが、かなり冗長に見えます。
0187デフォルトの名無しさん
2006/04/23(日) 23:39:39> でとりあえず事足りているのですが、xが-N未満だった時によろしくありません。
つか、xが-N未満になりうる時点でバグってると思うが？
0<= x < N なんでしょ？
0188デフォルトの名無しさん
2006/04/23(日) 23:51:29x % n + (x < 0 ? n : 0)
0189デフォルトの名無しさん
2006/04/24(月) 00:08:33説明が下手ですいません。
xになにかしらの数が代入され、それをうまく 0<=x<N に丸め込みたいのです。
int hoge(int x)
{
while(x < 0) x += N;
x %= N;
return x;
}
とお考えください。
>>188
その式だと、ちょっとやりたいこととは違うようです。
whileやifを使わずに綺麗にやる式があれば…と思っているのですが
0190デフォルトの名無しさん
2006/04/24(月) 00:46:260191デフォルトの名無しさん
2006/04/24(月) 00:50:35＞x = ((x % N) + N) % N;
のほうが分岐無いだけ速くねーか
0192デフォルトの名無しさん
2006/04/24(月) 06:33:35NM=INT_MAX/N;
として
x = (x + NM) % N;
でいいんじゃないの？
0193デフォルトの名無しさん
2006/04/24(月) 16:25:32UIなら計算量をケチる必要性はないので多少冗長でもかまわないのでは。
xの初期値として
x = (x + N) % N;
が計算できて、xは以降、0<=y<N、という値が足されたり引かれたりするだけという状況を仮定すると、
(>>186だとそういう状況ですよね。xに乗除算は入ってこない)
x-yを行うときはx<yならばNを足してからyを引くでいいんでないかい。
除算よりも比較の方が圧倒的に速いから。
0194デフォルトの名無しさん
2006/04/24(月) 16:36:30xが-N未満になど、普通はなりようがないのだ。
x <-Nになる事はないのだから 用途的には
x = (x + N) % N; で何の問題もない。
過剰仕様といえよう。
もし、xがEPROMとかに保存されてる間にゴミと化しても変な事にならないようにという事なら
x を 符号無数とすればいい
0195デフォルトの名無しさん
2006/04/25(火) 00:18:10-500000とか入れられたときに、0～4095に直すとどうなるか。みたいな。
DWORDにする手もあるんだが、Javaだと符号intしかないからなぁ・・
0196デフォルトの名無しさん
2006/04/25(火) 06:36:530197デフォルトの名無しさん
2006/05/16(火) 22:52:10leveshteinとかsimilar_textだと、"abcdefgh"と"hgfedcba"の類似性を
かなり低く見積もってくれたりするんだけど、人間の直感にマッチするような
アルゴリズムってないもんですかね。
0198デフォルトの名無しさん
2006/05/17(水) 10:17:580199デフォルトの名無しさん
2006/05/17(水) 16:01:49俺の直感だと、その2つは似てない
0200デフォルトの名無しさん
2006/05/20(土) 21:35:30similar_text
ttp://jp2.php.net/manual/ja/function.similar-text.php
0201デフォルトの名無しさん
2006/05/23(火) 17:06:120202デフォルトの名無しさん
2006/05/30(火) 16:49:01そこに重み付けを導入する場合って、どんなアルゴリズムがあります?
0203デフォルトの名無しさん
2006/06/08(木) 07:54:15C で文字列を比較するのは
(*(int *)s1) == (*(int *)s2)
これのほうが早い？
0204デフォルトの名無しさん
2006/06/08(木) 07:57:42ここで聞く前に試したほうが早いし確実だと思うのは気のせいでしょうか
0205デフォルトの名無しさん
2006/06/08(木) 09:25:220206203
2006/06/08(木) 09:29:080207デフォルトの名無しさん
2006/06/08(木) 10:42:46間違ってるの？
0208207
2006/06/08(木) 10:47:380209デフォルトの名無しさん
2006/06/08(木) 13:58:46これどのCPUでもいけるの？
0210デフォルトの名無しさん
2006/06/08(木) 15:47:530211デフォルトの名無しさん
2006/06/22(木) 15:26:030212デフォルトの名無しさん
2006/06/22(木) 15:47:54ナイス情報サンクス｡
LATEXとＪＡＶＡかー｡
アルゴリズムキボンヌだなぁ｡
0213デフォルトの名無しさん
2006/06/22(木) 16:02:00「JAVAによるアルゴリズム事典」はpLaTeXで書いたとちゃっかり宣伝していた。
0214デフォルトの名無しさん
2006/06/25(日) 00:14:43理解しやすいオープンソースプログラムってあります？
0215デフォルトの名無しさん
2006/07/06(木) 08:08:550216デフォルトの名無しさん
2006/07/06(木) 15:40:550217デフォルトの名無しさん
2006/08/06(日) 13:40:04何かで世界統一されることなんてないよ。
0218デフォルトの名無しさん
2006/08/06(日) 17:01:29ソースは？
解釈が間違っている可能性がある。
0219デフォルトの名無しさん
2006/08/06(日) 20:40:34放送大学で言っていた。
0220デフォルトの名無しさん
2006/08/12(土) 09:04:260221デフォルトの名無しさん
2006/09/02(土) 16:52:02と ） | |
Ｙ /ノ 人
/ ） < >__Λ∩
＿/し' ／／. Ｖ｀Д´）/
（＿フ彡 /
0222デフォルトの名無しさん
2006/09/14(木) 01:08:000223デフォルトの名無しさん
2006/09/17(日) 22:57:32簡単の為、問題を２次元にします。
この時、
(0,0)
(1,0)
(0,1)
(1,1)
(2,0)
(2,1)
(1,2)
(2,2)
・・・・・・・
という配列を得たいのです。
思いついた単純な方法は、
for(i =1; i < N ; i++)
for(j = 1 ; j < N; j++){
d = i**2 + j**2
arry.push([i,j],d)
}
sort arry by d
aryy.each { a
printt a
}
という方法ですが、あまりスマートとはいえないし、
同じ距離d (= 1)をもつ点(1,0),(0,1)がこの順で並ぶとは限らないという欠点があります。
（同じ距離を持つ(x,y)なら x>=yというを満足する点からで並んで欲しい)
0224デフォルトの名無しさん
2006/09/17(日) 23:03:57「安定なソート」でぐぐれ。若しくはC++のstd:stable_:sortで関数オブジェクトに
x>=yという条件を含めれば簡単。
0225デフォルトの名無しさん
2006/09/17(日) 23:04:27○std::stable_sort
0226デフォルトの名無しさん
2006/09/17(日) 23:33:51群論とか使えばいけそうだが。。。
俺の知識では無理ｗ
0227デフォルトの名無しさん
2006/09/17(日) 23:42:44#include <vector>
#include <algorithm>
#include <utility>
struct MyComp {
bool operator()(const std::pair<double, double>& p1, const std::pair<double, double>& p2)
{
double d1 = p1.first * p1.first + p1.second * p1.second;
double d2 = p2.first * p2.first + p2.second * p2.second;
if (d1 < d2)
return true;
else if (d1 > d2)
return false;
else { // d1 == d2
if (p1.first < p1.second && p2.first > p2.second)
return false;
else return true;
}
}
};
struct MyOut {
void operator()(const std::pair<double, double>& p)
{
std::cout << '(' << p.first << ',' << p.second << ')' << std::endl;
}
};
0228デフォルトの名無しさん
2006/09/17(日) 23:43:16{
double a[][2] = {{0, 0}, {1, 0}, {0, 1}, {1, 1}, {2, 0}, {2, 1}, {1, 2}, {2, 2}};
std::vector<std::pair<double, double> > dp;
for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
dp.push_back(std::make_pair(a[i][0], a[i][1]));
std::sort(dp.begin(), dp.end(), MyComp());
std::for_each(dp.begin(), dp.end(), MyOut());
}
(1, 0), (0,5, 0) なんてペアがある場合は考慮してない。
0229デフォルトの名無しさん
2006/09/18(月) 00:43:400230デフォルトの名無しさん
2006/09/20(水) 15:41:34最終的には、与えられた領域を重複の無い横に細長い形の矩形で表現したいと思っているのですが、
これを表現するための良いアルゴリズムはあるでしょうか？
0231デフォルトの名無しさん
2006/09/20(水) 22:14:34スキャンラインコンバージョン？
0232デフォルトの名無しさん
2006/09/20(水) 23:44:29おれは力技でやった
0233デフォルトの名無しさん
2006/09/24(日) 15:55:300234デフォルトの名無しさん
2006/09/24(日) 17:39:47平面走査で解ける．計算量は O( n log n + k )，
ただし n は矩形の数，k は分割線の個数．
簡単のため，どの矩形の上下の y 座標にも，同じものはないとする．
アルゴリズムを述べた後にこの制限は外す．
1. すべての矩形の上側の辺と下側の辺を，
y 座標の昇順に並べられたキュー Q に突っ込む．
2. while Q が空でない:
3. e = Q.pop()
4. if e が下辺
then T に対応する矩形を挿入
else T から対応する矩形を削除
5. T に入っている矩形で，e と交わるものを切断する．
ここで T は平面走査構造．x でソートされた平衡二分探索木を用いると
4 が O(log n) で行える．5 は e の左側の点で二分探索し，交わる領域を
線型に探すと O(log n + k') で行える．ただし k' は e と交わる矩形の数．
同じ y 座標を許す場合は，一括に処理できる辺を蓄えておいて，
一度しか切断しないようにすれば対応できる．
0235デフォルトの名無しさん
2006/09/30(土) 15:33:44void DrawEllipse(HDC hdc, double dFx1, double dFy1, double dFx2, double dFy2, double dLen )
{
double a,b,c,d,A,B,C,L,M,x;
int sx,sy;a = dFx1;
c = dFx2;L = dLen;
A = L*L-(a-c)*(a-c);
BOOL bFlg = TRUE;
for(int y=0; y<300; y++){
b = y-dFy1;d = y-dFy2;
M = L*L-a*a-b*b-c*c-d*d;
B = -2*(a*(c*c+d*d)+c*(a*a+b*b))-M*(a+c);
C = (a*a+b*b)*(c*c+d*d)-M*M/4;
if(B*B-4*A*C>0){
x = (-B+sqrt(B*B-4*A*C))/(2*A);
if( bFlg ){
bFlg = FALSE;
sx = x;sy = y;
MoveToEx(hdc,x,y,NULL);
}
LineTo(hdc,x,y);
}
}
0236デフォルトの名無しさん
2006/09/30(土) 15:34:17for(int y=300; y>0; y--){
b = y-dFy1;d = y-dFy2;
M = L*L-a*a-b*b-c*c-d*d;
B = -2*(a*(c*c+d*d)+c*(a*a+b*b))-M*(a+c);
C = (a*a+b*b)*(c*c+d*d)-M*M/4;
if(B*B-4*A*C>0){
x = (-B-sqrt(B*B-4*A*C))/(2*A);
LineTo(hdc,x,y);
}
}
if( !bFlg ){
LineTo(hdc,sx,sy);
}
}
あげちまたスマソ
0237デフォルトの名無しさん
2006/09/30(土) 15:35:42ベジエ勉強したほうが良いのかな
0238デフォルトの名無しさん
2006/09/30(土) 19:41:450239デフォルトの名無しさん
2006/09/30(土) 23:01:13ベジエ曲線で完全な楕円は表現できない
近似はできるけどな
0240デフォルトの名無しさん
2006/09/30(土) 23:20:49HDCはおいておいて、残りの5つは
焦点の座標（２つ）と長径
>>239
実用に耐えるなら近似で良いんだけどね
0241デフォルトの名無しさん
2006/09/30(土) 23:59:260242デフォルトの名無しさん
2006/10/22(日) 19:47:46この最大遅れの「最大」ってなんなの?
遅れの合計を最大化したものを最小化? 意味がわからん。
エロい人教えて
0243デフォルトの名無しさん
2006/10/22(日) 19:51:50・最初の仕事で30分遅れてあとの仕事はジャスト．（最大遅れ30分）
・全部10分づつ遅れる．（最大遅れ10分）
の二つだったら，後者のほうが良いとするスケジューリング．
0245デフォルトの名無しさん
2006/10/31(火) 16:55:59$b=array('white','blue','yellow','green');
$c=array('green','red','yellow','cian','black');
$a,$b,$cのどれにも存在する要素の'yellow','green'を取得するソースをPHPで。
0246デフォルトの名無しさん
2006/11/02(木) 01:42:060247デフォルトの名無しさん
2006/11/02(木) 11:51:23array_uintersect
0248デフォルトの名無しさん
2006/11/02(木) 19:21:30N個の要素からメディアンを計算量O(LogN)で求めるアルゴリズムを教えてください。
http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf
http://www.cse.ust.hk/faculty/scheng/comp271h/assign/hw2_sol.pdf
検索して出てきたこの二つのPDFにある擬似コードをCで実装してみたんですけど
何度かテストしたらどちらも時々スタックオーバーフローが発生してしまいました。
（正しい結果を返すときもありました）
二つの配列の長さが同じ場合にしか使えないコードでもいいのでお願いします。
0249デフォルトの名無しさん
2006/11/02(木) 20:57:412つのソート済み配列をA,Bとする。
Aの中央値とBの中央値を比較する。
Aの方が大きいとすると、Aの小さいほうの集合とBの大きいほうの集合を残す。
以下これを反復する。1回の反復は配列の要素を指定して比較するだけだから定数オーダー。
反復ごとに要素数が半分になるから反復回数はlog N回
0250248
2006/11/03(金) 03:05:44ありがとうございます。こんな感じになりました。
int median_search(const int *A,const int *B, int n){
int m;
if(n==1)
return A[0]>B[0]?A[0]:B[0];
m = n>>1;
if(A[m]>B[m])
return median_search(A,B+m,m);
return median_search(A+m,B,m);
}
nは配列AとBの長さです。
ソート済みの配列AとBをマージした長さ2nの配列をCとするとこの関数はC[n]を返します。
A[0]>B[0]?A[0]:B[0];の部分を、A[1]<B[1]?A[1]:B[1];にすればC[n+1]を返します。
0252デフォルトの名無しさん
2006/11/04(土) 02:07:100253デフォルトの名無しさん
2006/12/01(金) 10:57:06最も的確な結果を表示するために、上の6件と似たページは除かれています。
0254デフォルトの名無しさん
2006/12/26(火) 19:17:240255デフォルトの名無しさん
2006/12/27(水) 11:18:500256デフォルトの名無しさん
2006/12/28(木) 09:05:200257デフォルトの名無しさん
2006/12/30(土) 16:37:470259デフォルトの名無しさん
2007/01/05(金) 00:45:08例えば、NOT2個とAND複数、OR複数個だけで並列な独立した3つのNOT回路と等価な回路を探すアルゴリズム。
「思考する機械コンピュータ」という本に載っていた問題です。(この条件が)
この間バックトラックでやったらあっさりできましたが・・・
0260デフォルトの名無しさん
2007/01/05(金) 07:45:57加算器ぐらい合成できないと意味はない
0261デフォルトの名無しさん
2007/02/13(火) 08:13:380262デフォルトの名無しさん
2007/02/13(火) 08:54:07証明
0263デフォルトの名無しさん
2007/02/13(火) 15:00:13ちなみに「条件を満たす回路が存在しない」ことの証明は
総当たりで調べても見つからなかったことを言う以外に方法はない。
典型的なNP問題。
0264デフォルトの名無しさん
2007/02/13(火) 19:51:44総当りでしか証明できないならNPに入っていないじゃん。
探査空間Pで十分だからPSPACEには入っているけど。
0265デフォルトの名無しさん
2007/02/14(水) 16:25:03？
0266デフォルトの名無しさん
2007/02/14(水) 18:10:31NP=ある多項式長の補助入力が存在してPで解ける
総当り→補助入力は多項式長でないからダメ
補問題であるある場所にいけるかは
道順の例を補助入力として与えればこれは多項式長であり、明らかにPで検証可能。
したがって補問題はNP。
補問題がNPだから、PSPACEよりも狭いco-NPに入る。
0267デフォルトの名無しさん
2007/02/15(木) 03:59:350268263
2007/02/15(木) 06:14:34等価な回路を探すアルゴリズムがNPで、存在しないことの証明はNPじゃない。
0269259
2007/02/15(木) 16:03:390270デフォルトの名無しさん
2007/02/16(金) 00:56:550271デフォルトの名無しさん
2007/02/16(金) 04:04:040272259
2007/02/16(金) 04:34:16ttp://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/3659.c
0273デフォルトの名無しさん
2007/02/16(金) 07:39:570274デフォルトの名無しさん
2007/02/16(金) 07:40:390275デフォルトの名無しさん
2007/02/18(日) 16:31:13多数のオブジェクトの衝突判定を並列化する方法
移動後の座標をボクセルに振り分ける。
1つのボクセル内に存在するキャラを総当たりで衝突判定。
処理の順序としては、移動、振り分け、衝突判定、衝突処理。
これで処理を並列化できる。
もう少し詳しく言えば、衝突判定をしやすくするために、
ボクセルに振り分ける時点で座標値などをボクセルごとの一時バッファに複製しておく。
これにより巨大なバッファをLSにロードする必要がなくなる。
衝突の連鎖については次フレームに回す。それで結果的には再帰処理になる。
普通は移動後に振り分けるというより
ボクセル内のオブジェクトを管理するバッファを常設しておいて
移動でボクセル外に出たときだけバッファの更新をするでしょ。
0276デフォルトの名無しさん
2007/02/19(月) 01:19:29ボクセルよりも適当な空間木を用いたほうがよいと思う。
オブジェクトの分布や座標空間にもよるが、計算量の
意味で速度が改善されることも珍しくない。
0277デフォルトの名無しさん
2007/02/20(火) 03:50:22ふつーNOT_Aなのは分かる
しかし、Shiftを押しながら「ろ」キーを押す手間が面倒なのも分かってしまうんだな
俺はどっちを応援すればいいんだ？
0278デフォルトの名無しさん
2007/02/20(火) 06:10:110279デフォルトの名無しさん
2007/02/20(火) 16:04:220280デフォルトの名無しさん
2007/02/22(木) 07:38:32コメントぐらいかこうね
0281デフォルトの名無しさん
2007/07/03(火) 15:59:46Minimal を用いて次のように定義する。(ただしプログラム中、A or B はA とB のうち少
なくともどちらか一方がtrue のときtrue を返し、それ以外のときはfalse を返す論理演算
である。) 以下の問に答えよ。
fun member x lst =
case lst of
[] => false
| hd::tl => hd=x or (member x tl)
end;
fun nayose lst =
case lst of
[] => []
| hd::tl => if (member hd tl) then (nayose tl) else hd::(nayose tl)
end;
(1) 関数nayose はどのような計算を行う関数か簡潔に答えよ。
(2) 長さがn のリストに関数nayose を適用したときの計算量をO(f(n)) の形で表せ。
(3) あらかじめ整列された整数のリスト（重複があってもよい）を入力とし、関数nayose と
同様の結果を出力する関数で、入力リストの長さがn のときの計算量がO(n) となるよ
うな関数nayose2 を、Minimal プログラムで示せ。関数nayose2 がnayose と同様の結
果を出力する理由を簡単に説明すること。
(関数nayose2 は、整列されていない入力についてはnayose と異なる結果を返しても良
い。）
0282デフォルトの名無しさん
2007/07/05(木) 07:23:150283デフォルトの名無しさん
2007/09/08(土) 02:49:460284デフォルトの名無しさん
2007/09/10(月) 15:56:14% 何も生成しない生成器
repeat.
repeat :- repeat.
% 類型 リストからの生成
member(A,[A|_]).
member(A,[_|R]) :- member(A,R).
% 類型 リストの分解
append([],X,X).
append([U|X],Y,[U|Z]) :- append(X,Y,Z).
0285デフォルトの名無しさん
2007/09/11(火) 03:52:19% 連続整数の生成器(昇順)
for(N,N,E) :- N =< E.
for(S,N,E) :- S =< E,S2 is S+1,for(S2,N,E).
0286デフォルトの名無しさん
2007/09/23(日) 09:39:58> よく知られている問題ですが、一般に、Ｎ個のもののソーティング(順序付け)の
> ための必要最少限の比較回数はlog2(Ｎ！) ≦ ｋを満たす最小の整数ｋです。
って本当?
ていうか必要だけど充分じゃないっていう意味で言ってるんだろうか.
0287アルゴリズム初心者
2007/10/13(土) 20:48:56そういったアルゴリズムの解説お願いします。
もしくはためになりそうなキーワードやウェブサイトを教えてください。
３年くらいプログラミングはしているのですが、画面を作るばかりで
頭を使うようなことは一切やったことが無いので詰まってしまいました。。。
0288デフォルトの名無しさん
2007/10/13(土) 21:04:060289デフォルトの名無しさん
2007/10/14(日) 00:14:49WinMergeをダウンロードしてくるといいよ
0290デフォルトの名無しさん
2007/10/14(日) 00:39:33見にくくてしょうがない。
DFみたいにフォルダごとに見れるようにしてくれよ。
0291アルゴリズム初心者
2007/10/14(日) 07:53:310292アルゴリズム初心者
2007/10/14(日) 07:59:150293デフォルトの名無しさん
2007/10/14(日) 08:56:050294デフォルトの名無しさん
2007/10/14(日) 09:55:04さすがに手作業で同じ事はできるよな？
じゃ、まずは簡単な例で手作業でやってみよう。
次に、どういう手順で行ったか書き下してみる。
で、人間なら分かるけど計算機には分からないといった about なところを詳細化する。
最後にコードに落としてやれば OK だ。
この程度で、アルゴリズムだとかライブラリだとか情報源とか探してるようだと
いつまでたってもそのレベルから抜け出せないよ？
0295デフォルトの名無しさん
2007/10/14(日) 10:34:59system("diff -r dir1 dir2")
0296デフォルトの名無しさん
2007/10/14(日) 10:39:330297デフォルトの名無しさん
2007/10/14(日) 12:55:17どういう範囲内でユニーク？
ユニークなことを確実に保障するのって難しいよ。
0298デフォルトの名無しさん
2007/10/14(日) 13:21:17範囲というか、DBの正規化レコードのテストに使うので1～1000万ぐらいで。
乱数をハッシュテーブルに登録してユニークな乱数列を作れないかと
思ったんですが、目的レコード件数分まわしても、重複で抜け番号が
出てくるので、一気に全部埋まる方法ないかなと。
0299296
2007/10/14(日) 13:24:14ランダムに混ぜる方法でもいいです。
0300296
2007/10/14(日) 13:28:030301デフォルトの名無しさん
2007/10/14(日) 13:50:17全数チェックしたらｗ
0302デフォルトの名無しさん
2007/10/14(日) 16:24:11多分、ユニークな乱数列、の意味が人によって違っているような気がする。
「乱数列」がユニークであることを望んでいるのではなくて、乱数列中に表れる数値がユニーク(重複しない)
ってことなんだよね？
C++ で良ければ(アルゴリズムの説明にならないけど)、>299 で random_shuffle() 使うのが一番簡単かと。
あるいは、random(N) を 0～N-1 の整数を発生する(シード値をとれる)疑似乱数生成関数として、a[0]～a[N-1] にたいして、
for(i=0;i<N;++i) {
idx = random(N);
tmp = a[i];
a[i] = a[idx];
a[idx] = tmp;
}
で、いいんじゃない？
0303296
2007/10/14(日) 20:45:00その通りです。
ありがとうございました。
0304デフォルトの名無しさん
2007/10/14(日) 20:49:40そのコードだと均等に混ざらない（すなわち、全ての可能なケースが等確率で出ない）。
正しくはこんな感じ
for(i=0;i<N;++i) {
idx = random(N-i) + i;
swap(a[i], a[idx]);
}
0305デフォルトの名無しさん
2007/11/13(火) 01:55:34最適なアルゴリズムってどれですかね？
0306デフォルトの名無しさん
2007/11/20(火) 17:17:18質問の意味がよくわからない
最長共通文字列？
ところで、良いアルゴリズムというかロジックが思い浮かばないんだけど何か良いの無いかな。
配列をPivotとの大小関係で三つに区切る。
C++っぽい擬似コードで書くとこんな感じ
under = partition( Begin
End
< Pivot )
partition( under
End
== Pivot )
これより計算量係数を下げたいんだけど。
0307デフォルトの名無しさん
2007/11/23(金) 08:28:25係数を議論するなら計算モデルを出さないと普通不可能だし，
その擬似コードの partition の実装もわからないからなんともいえない．
0308デフォルトの名無しさん
2007/11/24(土) 19:00:09携帯からでカンマが改行になってしまいました。
>>307
具体的に計算する必要はありません。
何か他の実装が
partitionの実装が分からなければSTLのソースでも見てください。
0309デフォルトの名無しさん
2007/11/24(土) 19:52:52ちと文章が切れてるので何を言いたいか察しかねるが、
計算量係数ってことは O(n) で隠れてる定数部分を
評価したいんでしょ？ そのためには、たとえば
・対象はどう表現されているか（リスト，配列 etc）
・n として何を数えるか（比較，イテレータの移動，スワップ etc）
・それぞれどれくらいの計算コストの差があるか
なんか決まらないと、とても評価できない。
「実用上早い」ってのは知られてるけど、計算量の係数が
実際にどんくらい小さいかってのは不明。
あと、306 のコードは「C++ 風の擬似コード」じゃなかったの？
それで「実装は STL を見ろ」というのではあなたの言うところの
擬似コードの意味がよくわからないんだけれど。
それに STL の partition はアルゴリズムは全く決めてないから
例えば「gcc のどのバージョンの STL の実装」とか言わないと。
0310デフォルトの名無しさん
2007/11/24(土) 23:27:09エスパーで問題を考えて回答しよう。
入力
*X;(1,2,4,4,4,5,6,7);//ソート済み配列,長さO(n)
Pivot=4;//比較する値
Begin=0;//探索範囲？
End==7;//
出力
(2,5);//(1,2),(4,4,4),(5,6,7)と分けたときの4と5のインデックス
アルゴリズム
B=Begin;E=End;
while(E-B&g;1)
if(X[(B+E)/2]>Pivot)
E=(B+E)/2;
else if(X[(B+E)/2]<Pivot)
B=(B+E)/2;
else
{ N=(B+E)/2; break; }
以降はBとN間、NとE間の境界を通常の二分探索で見つける。
比較回数の最悪は明らかに1回目の比較でbreakして全体の1/2のサイズの二分探索を二回行わなければならないときで、
1+2(logn-1)=2logn-1回
0311デフォルトの名無しさん
2007/11/25(日) 02:31:58それはエスパー失敗
ソートされていない配列をピボットよりも
「小さい・同じ・大きい」に分ける」のが問題でしょう。
0312デフォルトの名無しさん
2007/11/25(日) 16:45:03そんなの順番に見ていくブルートフォースアルゴリズムが自明で最速ではないか。古典では。
0313デフォルトの名無しさん
2007/11/25(日) 17:58:59ブルートフォースという意味がよくわからないけれど、
先頭から順に見ていき、ピボットとの小中大によって
対応するリストにコピーする、というアルゴリズムのこと？
もしそうであれば、普通の計算コストの設定では最速ではない。
なぜならば、そのアルゴリズムは、「要素のコピー」 が
必ず n 回発生するが、普通はコピーは比較より数倍重い。
0314デフォルトの名無しさん
2007/11/25(日) 21:55:16そのアルゴリズムが最速ではないというなら最速なアルゴリズムを記述してくれ。
コピーが重いならコピーせずにポインタで参照すればいいのでは。
二段参照になるからリストの性能は落ちるだろうが。
0315デフォルトの名無しさん
2007/11/25(日) 22:09:04「最速」かどうかは知らないが次の論文を参照。
Jon Bentley and Robert Sedgewick,
"Fast Algorithms for Sorting and Searching Strings",
Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
New Orleans, January 1997
0316315
2007/11/25(日) 22:12:19コピーが重いというのは、別にオブジェクトが重いとかそんなものではなく、
int の値のコピーと int の値の比較でもコピーのほうが数倍遅い。
本当に膨大なデータを処理しようと思ったときは、この定数倍が響くことがある。
（それに、上のアルゴリズムは余計な空間を使うのも痛い）
0317デフォルトの名無しさん
2007/11/25(日) 22:52:24おｋ理解した。
swapで必要なところだけ入れ替えると。
swapでコピーが2重に発生するから
最悪上の単純なアルゴリズムの2倍かかってしまうが、
平均的には速いと。
クイックソートは最悪時間はバブルソートと同じになるが、
平均的にはマージソートよりも速いみたいなものと。
0318315
2007/11/25(日) 23:30:21ちょっと理解できていないように見えるんだけどな。
計算コストをきちんと設定しないといけないと言っていて、例えば
・スワップはコピーを2回実行する
・どこへのコピーも同じ単位時間で行える
みたいなモデルを考えればあなたの言ってることはほぼ正しい
（というか「平均的」（何の平均かわからんが）にも単純アルゴリズムが早くなる）。
しかし、現実の CPU ではそんなことは全然無くて、実際は
・値のスワップはコピー2回よりも若干高速に実行される
・同一作業領域中でのスワップは、別領域へのコピーよりもはるかに高速
ということになっているから、「2倍かかる」という算定は全く間違い。
x86 あたりを前提に算定すると「10倍以上早い」という結論でも不思議じゃない。
このあたりはオーダにしちゃうと完全に隠れる部分だから
クイックソートを例に出すのは不適当だと思う。
0319デフォルトの名無しさん
2007/11/25(日) 23:54:190320315
2007/11/26(月) 00:33:18何の具体例だい？「10倍以上遅くなる」ような実装の具体例？
そんなのは、Bentley-Sedgewick の論文からコードを引っ張ってきて、
手元で適当にコードを書けば簡単に具体例になるよ。
0321306
2007/11/27(火) 15:19:23だらだらコード書くよりSTL使った方がやりたいことが分かり易いかと。
ﾌｧﾝｸﾀ書くのが億劫で擬似と言っただけです。
対象のデータ構造は特定しません。というかあわよくばデータ構造による差が分かれば尚良いです。…が面倒なのでﾗﾝﾀﾞﾑｱｸｾｽって事いいです。
STLは、書きながら思ったけど本当に突っ込まれるとは思いませんでした。一般に同じ様な実装だと思ってました。すみません。
確認したのはgcc3.4.4/4.2.2、VC8、bcc5.5、SGI3.3です。
>>311
補完ありがとうございます。
>>314
その最速が今揚げてる議題です。
0322デフォルトの名無しさん
2007/11/27(火) 23:05:25で、コスト設定はどうするの？
少なくとも「イテレータの移動、比較、スワップ、スワップ」くらいのコスト比を
決めてくれないと、とても定数部分の違いは算定できないと思うんだけど。
現実のCPUみたいなキャッシュや分岐予測があるモデルだと、解析は
さらに面倒なことになるけど、それはどれくらい考えないといけないの？
あと、 Bentley-Sedgewick は読んでみた？
0323デフォルトの名無しさん
2007/12/28(金) 03:47:560324デフォルトの名無しさん
2008/03/05(水) 01:18:02ライブラリを主に使ってるから、ソート程度しか知らないんだけど、
今日、先輩プログラマにアルゴリズムも知らんのか？と言われた。
0325デフォルトの名無しさん
2008/03/05(水) 02:01:070326デフォルトの名無しさん
2008/03/05(水) 23:39:340327デフォルトの名無しさん
2008/03/06(木) 03:11:28推奨書籍はありますか？
0328デフォルトの名無しさん
2008/03/06(木) 07:54:07であって、アルゴリズムを知ってるだけじゃ駄目だろ。
アルゴリズムを知ってるだけでは、Fizz-Buzz問題でさえ解けるのは半数なんだそうだ
0329デフォルトの名無しさん
2008/03/06(木) 07:55:370330デフォルトの名無しさん
2008/03/06(木) 09:19:280331デフォルトの名無しさん
2008/03/06(木) 09:35:24[CLRS] T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, Second Edition, MIT Press
[KT] J. Kleinberg, E. Tardos, Algorithm Design, Addison Wesley
[I] 石畑 清，アルゴリズムとデータ構造，岩波書店
[S] R. Sedgewick, Algorithms in C, Addison-Wesley
[CLRS] はこの分野では定番で，標準的な教科書．和訳有．
[KT] は最近出た本で，現代的な記述がされている．
[I] は個人的にお勧めする本で，記述がやさしい．入門には適正．
[S] は実装中心に書かれていて，理論より実装という人向け．和訳有．
KT は最近和訳が進んでるって話もあるけど，きっとだいぶ先．
0332デフォルトの名無しさん
2008/03/06(木) 11:32:210333デフォルトの名無しさん
2008/03/07(金) 07:20:530334デフォルトの名無しさん
2008/03/07(金) 07:24:48[S] R. Sedgewick, Algorithms in C, Addison-Wesley やん
このあわてんぼさん。
0335デフォルトの名無しさん
2008/03/07(金) 18:40:37つ ttp://d.hatena.ne.jp/yaneurao/20050522
0337デフォルトの名無しさん
2008/03/11(火) 02:31:13の順列をぜーんぶ列挙するのになにかよい方法ってありますか？
つまりは任意の配列から総当りするためのネタ作りをしたい訳なのですが。。。
0338デフォルトの名無しさん
2008/03/11(火) 02:37:180339デフォルトの名無しさん
2008/03/11(火) 08:06:36でぐぐれ
いっぱいサンプルプログラムが転がってる
0340デフォルトの名無しさん
2008/03/11(火) 09:33:12はい。2が入力だったAB,BA見たいな感じのものが生成されるような。。。
>>339
ありがとうございます。見てみますね。
0341デフォルトの名無しさん
2008/03/11(火) 22:47:150342337
2008/03/11(火) 23:54:54並べ替えたいN個の要素のリストから一つ取っては、N-1人の自分にN-1個になったリストと自分の
ポインタをそれぞれ丸投げし、N-k番目の子はk番目の要素を一つとってさらに子に・・・取るものが
ラスト一個になったら、自分の親の取った要素をつなげて表示する。
みたいな実装イメージになるんでありましょうか。
0343デフォルトの名無しさん
2008/03/12(水) 23:07:29っちゅーかそれこそ調べればいいんじゃないの？と言いつつ安易に書いてみる。
後、26! = 403291461126605635584000000 なんで全部回してるとやってられないと思う。
#include <iostream>
int result[26];
void permutation_imp(int n, int m) {
if(m == n) {
for(int i=0;i<n;++i) for(int j=0;j<n;++j) if(result[j] == i) std::cout << ' ' << static_cast<char>('A' + j);
std::cout << std::endl;
} else {
for(int i=0;i<n;++i) if(result[i] == -1) { result[i] = m; permutation_imp(n, m+1); result[i] = -1; }
}
}
void permutation(int n) {
for(int i=0;i<n;++i) result[i] = -1;
permutation_imp(n, 0);
}
int main(void) {
permutation(3);
return 0;
}
出力結果：
A B C
A C B
B A C
B C A
C A B
C B A
0344デフォルトの名無しさん
2008/03/13(木) 21:43:11#include<stdio.h>
#include<string.h>
void swap(char *a, char *b){
char c;
c=*a;*a=*b;*b=c;
}
void func_internal(char *buf, int bufsize, int left){
int i;
if(left<=0) printf("%.*s\n", bufsize, &buf[-bufsize]); // 気持ち悪いかな？
for(i=0;i<left;i++){
swap(&buf[0], &buf[i]);
func_internal(buf+1, bufsize, left-1);
swap(&buf[0], &buf[i]);
}
}
void func(char *buf, int bufsize){
func_internal(buf, bufsize, bufsize);
}
int main(void){
char buf[]="abcde";
func(buf, strlen(buf));
return 0;
}
0345337
2008/03/14(金) 03:01:52これまた短いですね。。。なんでこんなのが思いつくのかが不思議です。
自分の思った方法でも無理ではないんだろうなとは思うのですが、擬似コードの段階で
だらだらしたものになってますからね。。。
再帰ですらすら考えられる人ってあたまよさそうです。
0347デフォルトの名無しさん
2008/03/14(金) 09:00:14このスレのタイトルの本もそういうものだわな
0348デフォルトの名無しさん
2008/03/17(月) 18:49:55として移動平均以外に何かありますか？
移動平均は平均回数をおおくとると、反応
が遅く（変化が鈍く）なるので、なるべくそうならな
い方法を探しています。
0349デフォルトの名無しさん
2008/03/17(月) 22:10:48Ａ／Ｄ、Ｄ／Ａ半導体
http://science6.2ch.net/test/read.cgi/denki/1120158621/
0350デフォルトの名無しさん
2008/03/18(火) 02:11:43高次曲線近似とかベジェ曲線近似はどうかな？
0351デフォルトの名無しさん
2008/03/18(火) 09:17:19計算量の面では２次の IIRフィルタにすれば、応答性と安定性と計算量も両立出来る。
0352デフォルトの名無しさん
2008/03/18(火) 10:01:45初めてききました。なんだかC言語で書くと難しそうですね。
>>351
係数って平均回数のことですよね？
0353デフォルトの名無しさん
2008/03/18(火) 11:45:53FIRフィルタでするという場合は、それぞれに重みを付けて計算するわけ
だから、移動平均に比べて計算コストは非常に大きい
例えば、サンプリング間隔の1/5以上で変動するようなノイズを取りたいという時に
16個の移動平均をしても ノイズは1/16までしか減らないけど
0, 0.015270303
1, 0.048044002
2, 0.098545986
3, 0.151768713
4, 0.186370997
5, 0.186370997
6, 0.151768713
7, 0.098545986
8, 0.048044002
9, 0.015270303
と１０個の係数かけて累積すれば、サンプリング間隔の1/5以上の成分は1/200以下に減る
0354デフォルトの名無しさん
2008/03/18(火) 15:30:03１０、１５、２０、１０
っていう４つのデータがある場合
10*0.4 + 15*0.2 + 20*0.2 + 10*0.2みたいに
するっていうことですか？
この重みの決め方がまた大変そうですね。
ちなみに353の例だとなんで1/200になるんですか？
なんかアルゴリズムとは関係なさげな話になって
申し訳ないです。
0355デフォルトの名無しさん
2008/03/18(火) 20:34:43入力 移動平均 >>353の方式それぞれの結果は
200.0 12.5 3.1
296.4 31.0 14.1
251.6 46.7 37.8
131.2 54.9 73.6
111.7 61.9 115.1
221.5 75.8 152.4
299.9 94.5 178.6
231.9 109.0 192.7
117.2 116.3 198.4
123.8 124.1 200.0 <-- 10個目から >>353 の方式はほぼ200に安定
242.0 139.2 200.0
298.7 157.9 200.1
210.8 171.0 200.0
107.1 177.7 199.9
139.5 186.4 200.0
260.6 202.7 200.1 <-- 移動平均は16個目以後でも±8程度変動する
292.9 208.5 200.0
189.1 201.8 200.0
101.3 192.4 199.9 ただしsin(i*w) のwの係数が 2*PI/5=1.25 以上の時に >>353 は効く
158.1 194.1 200.0
276.3 204.4 200.1
0356デフォルトの名無しさん
2008/04/13(日) 22:37:03例えば300個の積み木があるとして、これらは様々な重さ・大きさがあり、5種の色のいずれかが
ついてたとします。
これらを山に積み上げて行くときに、なるべく重さのピークが高い山がたくさん欲しいけれど、以下
の条件を満たさないといけないとします。
１．大きいものほど下にある
２．一山は積み木は10個が限度だけど、赤い積み木が三つ含まれていたら8個が限度になる。
３．一山には2色しか存在してはいけないし、異なる色の境界は1箇所だけ(赤青赤はだめで、赤赤青は良いみたいな)
ものすごく簡略化してしまいましたが、ナップザック問題に条件が加わったようなものになるのかと
思います。
細々とした条件・・・特に色の条件のせいで欲張り法が使えない気がするのですが、こういったものを常識的
時間で解く方法を調べたいので、キーワード程度でも教えてもらえませんか？厳密、近似は問いません。
0357デフォルトの名無しさん
2008/04/13(日) 23:31:07「重さのピークが高い」って言葉の意味が分からない．
あと，複数の山があったときにどう評価するかも分からない．
具体例をいくつか出してくれないかしら．
0358デフォルトの名無しさん
2008/04/13(日) 23:40:00重さのピークについてですが、例えば価値＝重さが
1 2 2 3 4 5 6 7 8 9
のような9個があったとして、ここから>>356より少ないですが、2段まで積んでいいこととするならば
98 76 54 32 21
のような山できてほしくて、
19 82 27 36 45
のようにはできて欲しくないのです。
できた山の価値の標準偏差が一番でかい組み合わせになるんでしょうか・・・
書いてて思いつきましたが、>>356をさらにいうならば、300個から最大で10個（特例を除く）で構成される山
を例えば15個作るとき、最も15山の価値の合計が高くなる組み合わせ。
これだとまた全く別の問題になってしまうのでしょうか。
0359デフォルトの名無しさん
2008/04/13(日) 23:40:3710個でした。
0360デフォルトの名無しさん
2008/04/13(日) 23:46:060361デフォルトの名無しさん
2008/04/13(日) 23:53:53問題を考えるときは，それを数式で書けるくらいまで整理しないと，
アルゴリズムなんて出せるはずがない．
きっとなんか解きたい問題があって，あなたはその要点のみを
取り出したつもりだと思うんだけど，取り出し方が悪くて全然分からないよ．
0362デフォルトの名無しさん
2008/04/14(月) 00:10:42できるのかな？と思ったのです。
で、もうちょっと整理してみました。
ナップサックが10個、取れる品物は300個あるとしてこれらはランダムに5色のいずれかの色がついている
１．品物の価値が高いものを先に詰めねばならない
２．品物の色は、一袋には2色までしか混載できない
３．さらに一袋を詰め終わる過程で、色の切り替わる回数は一回のみ
４．ナップサック一つには10個まで入るが、赤い色の品物を3個入れていたら8個までになる
以上の満たして10個のナップサックをつくり、10袋の価値和を最大にする
２、３は、「赤赤赤赤青青青青青青」はいいが、「赤赤赤赤青青青青赤赤」だめ
４は「赤赤緑緑緑緑緑緑緑緑」で一袋、「赤赤赤緑緑緑緑緑」で一袋になるという感じ
これですっきりしたよーに思いますがどうでしょう？
色がついているのと、4みたいな条件のせいで、欲張れないんじゃないかと思うのです。
0363デフォルトの名無しさん
2008/04/14(月) 00:10:52を最大化するの？
0364デフォルトの名無しさん
2008/04/14(月) 00:27:01「袋の価値」は、中身の総和でいいのかな？
あと、その問題は、前の問題とはかなり違うように見えるんだけど。
重さのピークってのは忘れていいのかな？
0365デフォルトの名無しさん
2008/04/14(月) 00:51:46「袋の価値」＝中身の価値の総和です。
ピークはですね。。。上手く表現できないので省いてしまってかまいません。
が、、、いいたかったことは
10袋の価値の総和が等しいケースが2ケースあった場合、満遍なく10個そろったやつよりも
ばらついてる方を解としたいというような・・・・
仮に100円なら、「10円のうまい棒10本」よりは「40円のよっちゃんイカ1つと4本のうまい棒と4円のﾅﾆｶおかし5個」
の方を解としたいというような感じだったのです('A`)
0366デフォルトの名無しさん
2008/04/16(水) 21:11:480367デフォルトの名無しさん
2008/04/17(木) 00:22:15再同期を含む同期を実行する種の
アルゴリズムってどの分野に区分
されるの？
全然文献なくて困る
0368デフォルトの名無しさん
2008/04/17(木) 03:14:15おそらくそうなると思います。
赤があるから制限が8個になるからって、8個でも10個詰めたときより価値が高くなることも
あるし、それは調べてみないとわからないよなぁと思うのです。
0369デフォルトの名無しさん
2008/04/25(金) 06:58:34なんかsuffix trieにしないとできないみたいなんですが…
0370デフォルトの名無しさん
2008/04/26(土) 10:14:29suffix array を用いて全く同じ計算量で実行できる．
0371デフォルトの名無しさん
2008/04/28(月) 22:01:30有向グラフっての？ 巡回サラリーマンっての？ ダイクストラ法っての？ なんかそんなの。よくわからないけど。
平面上に有限の座標群がある。まぁA～Zとしよう。
いくつかの座標間には経路がある。A-Bには経路があるが、B-Cには経路がないって感じ。
で、与えられた二点間を結ぶ全ての経路を算出するんだが、最短とか最長とかを考慮する必要はない。
とにかく、全ての経路を表示する。
座標情報はRDBに入力され、常に変動するので、計算するたびに違う結果になることもある。
乗り換え案内みたいなソフトウェアを作ろうと思ってるんだけど。
こういうのってどう考えればいいの？
0372デフォルトの名無しさん
2008/04/28(月) 22:18:32多すぎだろ。
0373デフォルトの名無しさん
2008/04/28(月) 22:20:53いったいどういうことだよ。
おれがおかしいのか？
0374デフォルトの名無しさん
2008/04/28(月) 22:38:38東大かどっかの研究レポートがwebにのってたよ
0375デフォルトの名無しさん
2008/04/29(火) 02:26:12ウェブ "バルブソート" に一致する日本語のページ 10 件中 1 - 10 件目 (0.14 秒)
ダブルコーテーションで括らないと曖昧検索される
0376デフォルトの名無しさん
2008/04/29(火) 03:52:36アホ。
0377デフォルトの名無しさん
2008/04/29(火) 04:32:38KY
0378デフォルトの名無しさん
2008/04/29(火) 12:42:32条件の確認なんだけど，「二点間の経路」で列挙したいのは
同じ頂点を複数回通らないような経路でよい？
あと，経路の数は半端なく多くなることがあるけど
出力順は問わないの？
0379デフォルトの名無しさん
2008/04/30(水) 01:09:48おー、レスサンクス！
例えば、下図のパターンで考えると、
┌B─D┐
A｜ ｜ F
└C─E┘
ABDF、ACEF、ACBDF、ABCEF、ABCDEF、ACBDEF、ACDEF、ABDEFだっけ？
全体が重複してさえいなければ同じ頂点、同じパスを辿ってもかまわない。
今は、とりあえず経路の算出方法で頭をひねってる。
次の段階として、各パスにはコストを持たせ、出力する際には、パスが少ない順・多い順、総コストの多い順・少ない順、パスがnになる場合のみ出力、
ノードBが利用不能になった場合の代替経路は…
とかってのを考えてるよ。
0380デフォルトの名無しさん
2008/04/30(水) 01:21:35ということは
ABDECBDF
ABDECBDECBDF
ABDECBDECBDECBDF
ABDECBDECBDECBDECBDF
ABDECBDECBDECBDECBDECBDF
ABDECBDECBDECBDECBDECBDECBDF
ABDECBDECBDECBDECBDECBDECBDECBDF
ABDECBDECBDECBDECBDECBDECBDECBDECBDF
ABDECBDECBDECBDECBDECBDECBDECBDECBDECBDF
ABDECBDECBDECBDECBDECBDECBDECBDECBDECBDECBD........ECBDECBDECBDECBDECBDF
でもOK？
0381デフォルトの名無しさん
2008/04/30(水) 09:37:50重複アリだと >>380 みたいになって，経路が無限個になって「列挙」できなくなるのよ．
この場合方針としては
・経路が無限個にならないように問題を変更する
・経路総数は無限個でもよいから、適当な順序で（上から有限個）出力する
のどっちか．さあどうしよう？
あと，そろそろ用語を正しておくと経路やパスってのは全体のことで，
隣り合ってるところは辺や枝と呼ぶのが普通ね．
0382デフォルトの名無しさん
2008/04/30(水) 10:50:28用語サンキュ。じゃ、座標を「節」、隣り合っている経路を「辺」、始点から終点を「経路」とすればいいかな。
それと、何となく頭の中に次みたいな考え方が頭にあったから380の指摘は頭になかったな～。
1.まずAをピックアップ。Aには除外マークを付ける
2.Aに隣り合う節B、Cの中からまずBをピックアップしBに除外マーク。
3.Bに隣り合う節A、C、Dの内、除外マークがないC、DからまずCをピックアップ
4.Cに隣り合う節A、B、Eの内、除外マークがないEをピックアップしEに除外マーク
5.Eに隣り合う節D、Fのうち除外マークがないD、F、そのうちDをピックアップ
6.～略～で、除外マークがないFをピックアップし、Fは終点なのでABCDEFの経路が一つ完成
7.5でDに行かずFに至って、ABCDFが一つ完成
8.2でCをピックアップし、以下ループ
ということは、378の指摘どおりだったのか。...スマソ。
0383デフォルトの名無しさん
2008/04/30(水) 11:31:000384デフォルトの名無しさん
2008/04/30(水) 11:38:530385デフォルトの名無しさん
2008/04/30(水) 19:53:080386デフォルトの名無しさん
2008/04/30(水) 20:29:010387デフォルトの名無しさん
2008/05/03(土) 08:34:47変な名前のせいで、この手法のポイントが要するにどこにあるのか
なかなか理解できなかった。
「部分問題解展開法」とかそんな名前にすれば良かったと思う。
0388デフォルトの名無しさん
2008/05/03(土) 08:35:36○「動的計画法（dynamic programming）」って名前最悪だな。
0389デフォルトの名無しさん
2008/05/03(土) 08:47:58"programming"は「コンピューター・プログラミング」ではなく、「計画」のこと。
overlapping subproblems, optimal substructure, memoizationする手法のこと。
0390デフォルトの名無しさん
2008/05/03(土) 09:55:42たとえば "greedy algorithm" や "divide and conquer" も載ってないしね。
ネーミングの由来は、部分問題を解いて、それを元に新たな計画問題を作る感じが、
動的に計画問題を解いているっぽいから、だそうな。
0391デフォルトの名無しさん
2008/05/10(土) 19:34:49いろいろ調べてみたけど式にΣが出てきたからわけわからなくなった。
そんな馬鹿な俺でも理解できるようにだれか説明してくれないかな。
0392デフォルトの名無しさん
2008/05/10(土) 20:20:42「挿入ソート」にもマイナーバージョンがいくつもあるので，
もう少し詳しいアルゴリズムを述べてくれないと厳密には解析できない．
まあ大雑把には，挿入ソートは
・空リストから初めて，要素を一つづつ "INSERT" する
・INSERT は，ソート済みのリストに要素を順序を壊さないように追加する
というアルゴリズムなので，これを解析する．
計算量を要素の比較回数で評価することにする．
長さ m のリストに対して INSERT するときの比較の回数を T(m) と書くと，
全体での比較の回数は Σ[m=0..n-1] T(m) になる．
T(m) は実装にもよるが，順番に比較していって挿入できる場所を探すと
最大 m 回の比較が発生しうる．つまり T(m) ≦ m．
よって全体の比較回数は Σ[m=0,n-1] T(m) ≦ Σ[m=0,n-1] m = n(n-1)/2 = O(n^2)
多分上の説明だと分からないところがあると思うので，ここが分からんとか聞いとくれ．
0393デフォルトの名無しさん
2008/05/11(日) 12:58:18参考にさせていただきました。
webやテキストの説明でもそれぞれ異なった説明の仕方をしていましたので多少混乱していたようです。
なんとか理解することができました。ありがとうございます。
0394デフォルトの名無しさん
2008/05/30(金) 16:30:27void sort(int[] data) {
for (int h = data.length * 10 / 13; h >= 1; h = h * 10 / 13) {
for (int i = h; i < data.length; i++)
if (data[i-h] < data[i]) {
int w = data[i-h];
data[i-h] = data[i];
data[i] = w;
}
}
}
普通にクイックソート並みに速いけど。どうなんでしょう？
クイックソートと違って欠点が無いように思う。
クイックソートの方が速いって反論よろしく。
0395デフォルトの名無しさん
2008/05/30(金) 18:38:560396デフォルトの名無しさん
2008/05/30(金) 19:02:59アルゴリズムはもちろん、クイックソート。ただし、工夫されているとのこと。
自作のクイックソートがダメなだけだった。
なので反論は遠慮しとく。
0397デフォルトの名無しさん
2008/05/30(金) 19:07:41やってみたけどstd::sort()の1/2程度の速度しか出ないじゃん
0398デフォルトの名無しさん
2008/05/30(金) 22:02:40速度以前に正しくないんでは？
[1,6,3,4,3,1,6] → [6,4,6,3,3,1,1] となったけども。
0399デフォルトの名無しさん
2008/05/31(土) 11:16:46岩波ソフトウェア科学シリーズの『アルゴリズムとデータ構造』のクイックソート
の項目は読むべき。
0400デフォルトの名無しさん
2008/05/31(土) 15:30:24comb sortについてよく調べると、ギャップが1になったら普通にバブルソートにするようです。
しかも、その時に整列済みか確認しないといけないようです。
ギャップがある程度(16ぐらい)に小さくなったら、挿入ソートに切り替えってのを試したら、意外と速いです。
ただのシェルソートっていう突っ込みは（ｒｙ
0401デフォルトの名無しさん
2008/06/04(水) 09:25:07> ギャップがある程度(16ぐらい)に小さくなったら、
> 挿入ソートに切り替えってのを試したら、意外と速いです。
これはquick sortもそう。
特にintとかチンケなものをsortしているときは。
0402デフォルトの名無しさん
2008/06/04(水) 11:13:39いかにもオリジナル的な書き方になったのはすみませんが、それは知っていました。
ついでにちょっと改良したやつを。
コムソートの部分をシェーカーソート風にすると、より良いです。(オリジナルではないです)
シェーカーソートはバブルソートを双方向から行います。
シンプルさが売りなのにちょっとゴチャついてるので、本当はシェーカーソートは外したいんですけどね。(つづく)
void sort(int[] data) {
for (int h = data.length * 10 / 13; h >= 17; h = h * 10 / 13) {
for (int i = h; i < data.length; i++)
if (data[i-h] < data[i])
swap(data, i-h, i);
h = h * 10 / 13;
if (h < 17) break;
for (int i = data.length - 1; i >= h; i--)
if (data[i-h] < data[i])
swap(data, i-h, i);
}
for (int i = 1; i < data.length; i++) {
int w = data[i], j = i;
for (j = i; j > 0 && data[j-1] < w; j--)
data[j] = data[j-1];
data[j] = w;
}
}
void swap(int[] a, int i, int j) {
int w = a[i];
a[i] = a[j];
a[j] = w;
}
0403デフォルトの名無しさん
2008/06/04(水) 11:21:56解決策として、２分挿入ソートが良さそうです。
ただ、さっきも書いたとおり、コムソート(バブルソートの改良)と挿入ソートの組み合わせという
単純なアルゴリズムで結構速し、特に欠点なしという所をアピールしたいので、まぁそのままで。
Javaの標準ライブラリとは同じぐらいの速さですが、興味があれば勝負させて見てください。でわ。
0404デフォルトの名無しさん
2008/06/04(水) 11:23:250405デフォルトの名無しさん
2008/06/04(水) 13:01:44今なら分散処理できるようなデータ構造やアルゴリズムの方が良いかもな。マルチコアだから。
0406デフォルトの名無しさん
2008/06/05(木) 00:41:48たった1000000個くらいのランダムデータに対しても
std::sort() の1/2未満の性能しか出ないよ。
ソーティングの世界では一瞬でも遅いのは大きな欠点。
0407デフォルトの名無しさん
2008/06/05(木) 09:11:39その通りで。
あれから、VC++をダウンロードしてちょこっと試してみたんですが
std::sort()の前にまずはCの標準のqsort()でやったところ
qsort()の方が全然速かったです。qsort()の方がstd::sort()よりも速いのかもしれませんが
試す前にやめました。(C++をあまり知らないということもあって)
0408デフォルトの名無しさん
2008/06/05(木) 23:21:040409デフォルトの名無しさん
2008/06/06(金) 00:23:300410デフォルトの名無しさん
2008/06/07(土) 17:13:13確実にインライン化されない qsort よりも一般に速い。
0411デフォルトの名無しさん
2008/06/21(土) 23:56:21要はb-treeとなにが違うの？
突然の話題で申し訳ない。
0412デフォルトの名無しさん
2008/06/22(日) 09:25:030413デフォルトの名無しさん
2008/06/23(月) 00:55:46葉にデータを集めたり、葉同士をリンクリストで繋げるなど、積め方を
工夫して末端の葉へのアクセスを単純にできるようにしたのがB+木。
(B木でもイテレーションは再帰やスタックでできるが)
B+木のノードの追加削除は複雑で、手間の割にうまく実装しても速度は
素のB-Treeに劣る。空間効率は良くなるので外部記憶で使うとか、
構造上範囲検索で有利に働くので、それを多用するなら意味がある。
B木でもキャッシュやファイルマッピングが使える状況だと空間効率を除き
差はほとんどない。
0414デフォルトの名無しさん
2008/07/03(木) 16:37:27木の分割についてのアルゴリズムがどこを探しても見当たりません。
バランスを保ちながら木を2つに分割するアルゴリズムは存在しないのでしょうか?
0415デフォルトの名無しさん
2008/07/04(金) 07:19:150416デフォルトの名無しさん
2008/07/04(金) 22:53:420417414
2008/07/04(金) 23:48:17ありがとうございます。一応insertとdeleteの組み合わせではできたのですが
もっと早い方法が無いのかと思って書き込みました。
もう少し考えてみます。
>>416
木をある値を境にして二つの木に分けたい、という意味です。
一つ一つのノードを木からdeleteして新しい木にinsertしなおせばできるのですが、
もっと単純にやる方法がないかと探しています。
0418デフォルトの名無しさん
2008/07/05(土) 00:55:24> 木をある値を境にして二つの木に分けたい
任意の値と言うこと？
なんかいい方法ありそうなが気がするが、俺の頭では無理だ...。
0419415
2008/07/05(土) 13:40:030420デフォルトの名無しさん
2008/07/05(土) 14:48:090421414
2008/07/06(日) 00:40:59そうです、任意の値を境にして二つのred-black-treeに分割したい、という意味です。
>>419
なるべくo(logn)の係数を抑えてやりたいのです。。。
>>420
そうなんです＞＜
いろいろ考えてみてはいるんですが。。。どうしてもバランスがとれなくて
困っています。
0422415
2008/07/06(日) 01:32:25判ってるから、分割した要素の総数から大雑把に見積もった
空のツリーを作成しておいて、データの穴埋めをしていけば
線形時間で済むでしょ。
例えば1から10までの要素で平衡木を作るなら1+2+4+8の
15に収まる4階層の平衡木が確定する。
あとは右端からトラバースして埋めていくだけ。
7
4 9
2 6 8 10
1 3 5
0423デフォルトの名無しさん
2008/07/06(日) 07:16:54探索木で分割自体が O(log n) でいくようなものもたくさんあるでしょや。
0424デフォルトの名無しさん
2008/07/07(月) 23:28:29平衡木を適当にぶった切ったら、もうそれは平衡木ではない。
バランス取れなくて当前。
比較は必要ないが、結局双方の木でdeleteやinsert相当の
回転操作をやる必要がある。
0425デフォルトの名無しさん
2008/07/24(木) 14:46:340426デフォルトの名無しさん
2008/07/24(木) 18:47:510427デフォルトの名無しさん
2008/07/24(木) 19:08:030428デフォルトの名無しさん
2008/07/24(木) 19:29:59価格か商品番号か購入順か
オレは購入順を推しておこう
0429デフォルトの名無しさん
2008/07/24(木) 20:01:37物の名前の一部などであいまい検索で引っかかったのを片っ端から探るとか。
あわててるとクエリの生成が適当になる。
0430デフォルトの名無しさん
2008/07/25(金) 00:09:11緊急時に出る道具ってある程度固定されてる気がする。
夢確かめ機みたいなろくでもないのは毎回出てくるだろ？
ポケットの中身はおそらく、ろくでもない順（＝Fに愛されてる順）にソートされてる。
0431425
2008/07/25(金) 04:18:330432デフォルトの名無しさん
2008/07/25(金) 09:26:300433デフォルトの名無しさん
2008/07/25(金) 10:33:52たしかドラポケットは「思ったものが出てくる」仕組みなので、慌ててる
ときにいらんもんが出てくるのは、そもそもの探索キー(思考)がgdgdなん
だと思われ。
0436デフォルトの名無しさん
2008/07/25(金) 15:41:230437デフォルトの名無しさん
2008/08/08(金) 02:49:00ブラウザで前回の更新時以降に追加されたログのみを受け取り、
ログ出力に反映させる。という部分を作っているのですが、
サーバのデータを受信する時の形式をどんなふうにしようか少し悩んでいます。
今のところは
(受信成功確認用の文字)<>時間<>発言者<>発言<>文字色 ・・・・以降受信が必要な分だけ時間から文字色のデータをループで渡す。
のようなことを考えているのですが、
何となくデータに若干の抜けがあったら結果が変なことになりそうな気がしてるのですが、
問題は無いでしょうか？
0438デフォルトの名無しさん
2008/08/08(金) 05:37:580439デフォルトの名無しさん
2008/08/08(金) 07:50:260440デフォルトの名無しさん
2008/08/08(金) 08:53:590441デフォルトの名無しさん
2008/08/08(金) 17:59:540442デフォルトの名無しさん
2008/08/09(土) 08:06:54やりはじめはその手の処理忘れるよな
0443デフォルトの名無しさん
2008/08/29(金) 05:02:14一定の半径を持つ円の中に点(座標)をランダムに打ちたい。
条件は、中心から一定距離までは打たない、円周になるほど高頻度で打ちたい
使える物は、精度(分解能)のよくないSin(Cos)テーブル
高級ではない言語と低レベルな頭脳なので、できれば数学系ライブラリとかを使わずに
計算や乱数などで済ませたいです。
具体例ではなく考え方でも構いません。
0444デフォルトの名無しさん
2008/08/29(金) 06:28:21こんな感じ？
http://www.dotup.org/uploda/www.dotup.org0569.png
0445443
2008/08/29(金) 07:05:54まさに理想形です。
可能な範囲で助言をいただけると嬉しいです。
今更かもしれませんが、補足
中心から方向Xに距離Rで配置すると中心の密度が上がってしまうので困ってます。
0446デフォルトの名無しさん
2008/08/29(金) 07:29:24方向X、円周からの距離Rの片側正規分布で一定以上は切ればいい希ガス。
0447デフォルトの名無しさん
2008/08/29(金) 08:51:36中心からの距離を、
一様分布に対して 1/r かけたもので作れば r に比例した分布になる。
1/r^2 とかかけとけば 442 みたいな分布になると思う。
0448デフォルトの名無しさん
2008/08/29(金) 10:02:34x=乱数;
y=乱数;
if(x*x+y*y<r*r) 点を打つ;
0449443
2008/08/29(金) 11:38:57乱数は一様乱数しか知らなかったので、正規乱数を使う事で解決しました。
ありがとうございました。
0450デフォルトの名無しさん
2008/08/30(土) 07:10:180451デフォルトの名無しさん
2008/09/02(火) 14:25:43B+木を実装する際に、ページに複数のエントリを入れる場合、
ページにできるだけたくさんエントリを入れようとすると、
空間効率は上がるが、木がバランスされなくなると思うのですが、
実際はどのような実装するのが普通なのでしょうか？
ページに入れるエントリ数を固定するのでしょうか？
（その場合は、エントリのサイズが小さい場合は、空間効率が悪くなるし、
大きい場合は、１ページに入らないといった問題がおきて、
実装がややこしくなりそうと思っています。）
0452デフォルトの名無しさん
2008/09/02(火) 14:32:31一般的には、
次数を d としたとき、d <= m <= 2 d となるような m が各ノードのエントリ数となる
ということは理解していますが、
エントリのサイズが可変の場合は、最大2d個のエントリをどう格納するのかが
よくわかっていません。
* ページサイズを可変にする
* ページサイズは固定で、入りきらない場合は複数のページを使う
この辺があると思っています。
0453デフォルトの名無しさん
2008/09/03(水) 20:16:03バランスされなくなるって、ノードの兄弟を見ながら
2dに収まるように分割してくんだよ。
ほとんど理解できてないみたいだから
より単純なB木から学んだ方がいい。
0454デフォルトの名無しさん
2008/09/16(火) 18:38:15xy平面上に正しくA、B、C、Dを配置したいのですが考え方がわかりません。
アドバイスをいただけないでしょうか？
0455デフォルトの名無しさん
2008/09/16(火) 19:12:080456デフォルトの名無しさん
2008/09/16(火) 21:57:19三角関数
0457デフォルトの名無しさん
2008/09/16(火) 22:07:09回転が確定しなくていいなら、相対測位とかいうキーワードでぐぐれ。
0458454
2008/09/17(水) 16:07:09余弦定理を用いて半径ACと半径BCの円の交点を考えC点を導いたのですが
次のD点を考えるときに半径AD・BD・CDの円が（当たり前かもしれませんが）１点で交わらないので求められませんでした。
455様と457様が言っている「回転」が必要だなと思い、
B点をA点のまわりで距離ABを保ちつつグルグル回るようにしたのですが、どうも違うみたいで困ってしまいました。
回転についての詳しい説明を教えていただけないでしょうか？
今は下のような状態になっています。
ttp://www.dotup.org/uploda/www.dotup.org0494.png
赤・青の円は半径AC・BCの円でC点（黄緑）を求めました。
薄い赤・青・緑の円は半径AD・BD・CDの円でとりあえず円AD・BDの交点から仮のD（紫)を導いたところです。
よろしくお願いします。
0459デフォルトの名無しさん
2008/09/17(水) 17:00:27分かりやすい座標で１回やってみた方がよさげ。
0460デフォルトの名無しさん
2008/09/17(水) 22:38:41各点間の距離データはあってるんだよね？？
0461デフォルトの名無しさん
2008/09/18(木) 00:59:48とはいえその場合でも、対称を同一視すれば一意に求まるはず。
0462デフォルトの名無しさん
2008/09/18(木) 02:23:10そ れ だ。
現実の都市間の距離で、球面上には矛盾無く配置できるけど平面上では矛盾無く配置できないとかな。
とりあえず454はそれぞれの距離を提示するべき。
0463454
2008/09/18(木) 14:11:16まず都市ABCDが現実に存在する都市かどうかですが、この世に存在しない都市を仮定しています。
そのため距離は毎回乱数で定まっています。
最初に断わっておくべきでした申し訳ないです。
4点が同一平面上にない場合があることは考えていませんでした。
今回の考え方を元に、単語同士の非関連度を距離に置き換えてそれぞれを配置するプログラムを作ろうかと思っていたのですが、
平面上のみで考えるのは無理があるのでしょうか。
0464デフォルトの名無しさん
2008/09/18(木) 14:40:44距離を何の制約も無しに乱数で作ると、それは4点間の距離と言えないものもできてしまう。
a,b,cで三角形になるのだから、ab+bc>acなどの制約が必要。
a,b,c、a,b,d、a,c,d、b,c,dの各組が三角形になる制約を満たすなら、
4つの点a,b,c,dは4面体を作る。
0465デフォルトの名無しさん
2008/09/18(木) 17:25:13完全ランダムでは無理条件ができるけど
0466デフォルトの名無しさん
2008/09/18(木) 20:06:30> 二点間の間での距離だけを定義する
という意味がわからないけれど，
『任意の二点間で三角不等式が成立するならば実現可能」
という主張なら，4点で反例が構成できる：
d(12) = 1, d(13) = √5, d(14) = √2, d(23) = 2, d(24) = 1, d(34) = 1
0467デフォルトの名無しさん
2008/09/18(木) 20:25:51以下の事実が知られている．
定義：
n×n 行列 D = (d_ij) が EDM であるとは，
ある点 p_1, ..., p_n ∈ R^k が存在して，
d_ij = |p_i - p_j|^2 が成立することをいう．
k を D の埋め込み次元という．
I を単位行列，J をすべての成分が 1 の行列とする．
定理(Schoenberg, Young-Householder)：
対称かつ対角成分がゼロの非負行列 D が EDM であることと，
G := -V D V / 2 が半正定値であることが同値．
ただし V = I - J/n である．
また，G = X X^T を コレスキー分解としたとき，
X の列ベクトルは D の実現となる．
なので，与えられたデータから行列 D を構成して
G を計算してコレスキー分解すれば埋め込みが決定できる．
もし rank G > 2 だったら平面には埋め込めない．
詳しくはEuclidean Distance Matrixなどで検索してくれ．
0468デフォルトの名無しさん
2008/09/19(金) 00:48:36XY平面上に、その座標データを保持するオブジェクトが複数個あり、
それらの座標はそれぞれランダムだったとします。
それぞれのオブジェクト間の距離が一定以下の場合は、
一定距離の間隔を置けるように引き離し、
さらにオブジェクトの距離の一番近いオブジェクトを探す
というようなことをしたいのです。
この処理はリアルタイムループ内で実行するので、
引き離しは1距離だけ離れるだけで十分であるとします。
一応は下記のようなプログラムで実装は出来ているのですが、
オブジェクトの数が増えた場合に処理が急激に重くなります。
この処理の計算量がn^2であるので、
オブジェクトの数が100、200と増えていった場合には
とてもリアルタイムループでは遅すぎる速度になってしまうのです。
何とかしてこの計算量を減らす方法はないものでしょうか？
0469デフォルトの名無しさん
2008/09/19(金) 00:50:56#define n 200
struct Object {
double x, y;
int near;
} op[n];
double dx, dy, dr, drmin;
for(int i = 0; i < n; i++) {
drmin = 1000000; //とりあえず大きい数
for(int j = 0; j < n; j++) {
dx = op[i].x - op[j].x;
dy = op[i].y - op[j].y;
dr = sqrt(dx * dx + dy * dy);
//一番近いオブジェクトを探す
if (dr <= drmin) {
op[i].near = j;
drmin = dr;
}
//一定距離以内の場合は引き離す
if (dr <= 400) {
op[i].x += dx / dr;
op[i].y += dy / dr;
op[j].x -= dx / dr;
op[j].y -= dy / dr;
}
}
}
0470デフォルトの名無しさん
2008/09/19(金) 01:27:09動的ボロノイ図を使えば，一反復が O(n + k log n) でできる．
ただし k は引き離す必要のあるペアの数．
ただ，これは実装が結構しんどいので，現実的には
x 座標でソートしたリストを盛っておいて，x 座標の近い順に見て
枝刈りするのが有力だと思う
（x 座標が一定距離を超えたら，距離が一定距離以下にはならない等）
計算量は最悪 O(n^2) だから変わってないけれど，現実的には改善されるはず．
なお，ソートは最初の一回だけ行えば，あとは引き離したところだけ更新すると
多少の効率化ができる．
0471デフォルトの名無しさん
2008/09/19(金) 19:43:55動的ボロノイ図は調べてみましたがサッパリ理解できませんでした（汗
なので後者のソートして近いところから探す方法を試してみたところ、
オブジェクト800個くらいまでは実用レベルの速度で動くようになりました。
但しやはり位置関係によっては重くなることもあり、
必ずしも安定しているとは言えませんが、
総当りに比べれば桁違いの速度になりました。
ありがとうございました。
0472デフォルトの名無しさん
2008/09/19(金) 23:01:01引き離し処理をするときには、データとその周囲の9マス分の範囲だけ調べるとか。
□□□□□
□■■■□
□■▲■□ ←▲のところが自分の属すマス
□■■■□
□□□□□
データの散らばってる範囲が狭過ぎると密集して役に立たないし、
逆に広過ぎるとマス目の管理を工夫する必要があるけど。
あと、「一定距離」以上でも最も近い点を取得する必要があるなら、これじゃだめかも。
0473デフォルトの名無しさん
2008/09/19(金) 23:06:330474デフォルトの名無しさん
2008/09/20(土) 11:26:32次のようなもので悩んでます。
１．複数の矩形があるときに同じところを再描画しないように無駄なく描画する矩形を計算するにはどうしたらいいか?
場合によっては複数矩形を包含する矩形で一度に描画した方がいい場合も含む。
総当たり以外でエレガントな方法というとどんなんざんしょ?
２．同じような話なのかもしれんが、矩形と線分(曲線含む)が混在してる場合で描画する矩形にかかる部分だけの線分を描画する効率のいい方法。
教えてエロイ人･･･
0475デフォルトの名無しさん
2008/09/20(土) 12:15:000476デフォルトの名無しさん
2008/09/20(土) 12:15:420477468
2008/09/20(土) 18:05:06>>472
空間分割とかいうやつですかね？
しかしこれは「最も近い点を取得する」という場合に
やはりお察しのように問題がありまして、
結局こちらの方法は諦めたのであります。
一応この最も近い点を探す距離も制限されてはいるのですが、
結構範囲が広いのでその表現は省かせていただきました。
>>475
これはその空間分割の究極ですね・・・
しかしこれはまた違う方向で膨大な判定量になりそうな気がします。
0478デフォルトの名無しさん
2008/09/20(土) 19:00:54472の亜種だと思うけどＸ，Ｙ軸上でソートして、各軸上の分布をクラスタとして扱うっていうのがGameProgrammingGEMに載っていた。
0479デフォルトの名無しさん
2008/09/20(土) 21:40:57問題が明確じゃないのだけれど，
(1)
『描画する』条件は，単に『別の矩形に包含されないこと』でよい？
それとも，矩形間に上下関係（例: Windowsのウインドウ）がある？
(2)
『描画する』条件は (1) と共通ということでよい？
それと，曲線はどのような形で与えられる？（例：ベジエ曲線）
何にせよ平面走査型のアルゴリズムが有力に動くと思う．
0480デフォルトの名無しさん
2008/09/21(日) 11:23:34一番価値が高くなるように効率よくいれるにはどういれたらよいかの手順を考える問
題ですよね。
これに、価値が高くなることに加えて、入れる順番も重さがあるものから入れる、あるいは
軽い順に入れるなどの制限が加わった場合にどのようにすればよいかという解法は
存在しますか？
0481デフォルトの名無しさん
2008/09/21(日) 11:59:36入れるものを決めた後で重量でソートすればいい
0482474
2008/09/21(日) 12:35:56不明確ですいません･･･orz
1．矩形間に上下関係有りです。ただその辺含めてまとめて”無駄な矩形を省く”というかたちでまとめられないかと。
２．描画の段階ではパラメトリック曲線から計算された連続した直線になると仮定しています。
平面走査型ちょっくらぐぐってきます。
0483デフォルトの名無しさん
2008/09/22(月) 00:32:18書くべき事がたりませんでした。。。
では更に、例えば前に入れたものよりn単位以上軽いものは配置してはいけない
というような、ソート後にだめだという事がわかってしまう場合はどうでしょうか？
0484デフォルトの名無しさん
2008/09/22(月) 02:43:010485デフォルトの名無しさん
2008/09/23(火) 09:49:23状態を (現在の重さ，最後に入れた重さ，現在の価値) という三つ組みで持つ．
重さが自然数であれば，品数を n，重さの最大値を W としたとき
普通の動的計画法に基づく O(n W) アルゴリズムを修正すれば
O(n^2 W) のアルゴリズムが簡単に作れる．
重さが実数であれば，基本的には枝刈り探索しかないのだから，
上の三つ組みを持って適当に探索する．
本気を出すなら，品数や重さなどによって適切な探索法が変わるけど
そこまでがんばるかい？
0486デフォルトの名無しさん
2008/09/23(火) 11:07:05もうググって見つけたかもしれないけれど，
1 に関しては平面走査型アルゴリズム（plane sweeping）が考えられる：
・y 軸に平行な直線を考える（走査線と呼ぶ）
・走査線を x = -∞ → +∞ に移動させていく．
・走査線に新たな矩形が乗ったら走査線上の矩形とだけ描画判定を行う．
走査線は y 座標でソートされた二分探索木を用いると，
描画判定を行うべき矩形を O(log n + k) 程度で列挙できる．
二分探索木を管理するのが面倒ならリストで持ってもよいが，
これだと列挙に O(n) かかる．
（矩形がそれなりに散らばっていれば，現実的には相当改善する）
こういうのは「線分交差列挙」などで調べると参考になると思う．
ちなみに矩形が動的に増えたり減ったりするような状況設定なら，
空間分割木などの幾何データ構造を使うことになる．
2 に関しては，描画の段階でなくて，データの段階でどうなるかが問題．
もしデータの段階で「連続した線分の集まり」と思ってよいなら，
1 の平面操作型アルゴリズムに走査線に線分が交わったら云々を追加するだけ．
それがダメなら，扱う曲線のデータ構造が分からないと，どうしようもない．
たとえば『曲線の方程式 (x(t), y(t)) が与えられる』くらいだと，
曲線と矩形の交差を全チェックするしかない．
0487デフォルトの名無しさん
2008/09/25(木) 01:27:20それぞれ検証する意外に、もっと早そうな根本から違うアルゴリズムって有るかな。
0488デフォルトの名無しさん
2008/09/25(木) 19:54:18指定したサイズのもの全てとか、小さい順とかで列挙すること？
それとも、条件を満たすもののサンプリング？
0489デフォルトの名無しさん
2008/09/25(木) 21:02:22n=7なら、108通り全部とか。
0490デフォルトの名無しさん
2008/10/19(日) 01:32:310491デフォルトの名無しさん
2009/01/18(日) 20:54:290492デフォルトの名無しさん
2009/01/19(月) 19:28:430493デフォルトの名無しさん
2009/01/19(月) 23:10:09B-Treeなどのアルゴリズムについてなんとなく理解したのですが、
それをどのように外部記憶上に保存するのかについてあまり見つかりませんでした。
C言語で実装されているソースの解説などどこかにあるでしょうか。
もう少し実力があればTokyoCabinetなどを解析すればよいのでしょうが、
ちょっと敷居が高いです。
0494デフォルトの名無しさん
2009/01/20(火) 01:02:000495デフォルトの名無しさん
2009/03/03(火) 06:57:31>それをどのように外部記憶上に保存するのかについてあまり見つかりませんでした。
互換性が要らないならバイナリでダンプしてもいいし、サイズを優先してバイナリで
writeしてもいい。互換性を重視するならテキストでwriteするといい。
速度を優先するならseekしたほうがいい。言語によってはシリアライズ機構がある。
よく分かっただろう？
0496デフォルトの名無しさん
2009/03/03(火) 08:09:55自分で実装したC#のソースなら持ってるけど
0497デフォルトの名無しさん
2009/03/04(水) 18:34:350498デフォルトの名無しさん
2009/03/05(木) 06:32:120499デフォルトの名無しさん
2009/03/20(金) 20:01:140500デフォルトの名無しさん
2009/03/20(金) 20:56:210501デフォルトの名無しさん
2009/03/20(金) 21:16:26ISAM
0502デフォルトの名無しさん
2009/03/20(金) 23:09:410503デフォルトの名無しさん
2009/04/01(水) 00:32:52その図形の重心を求めるアルゴリズムを教えてください。
頂点の数は３以上。
全ての辺について、他の辺と交差することは無い。
一つの角の大きさは0～360度。
0504デフォルトの名無しさん
2009/04/01(水) 00:43:45多角形の場合は、三角形に分割して、
それぞれの重心に対して、面積で重み付けして相加平均かな。
0505デフォルトの名無しさん
2009/04/01(水) 00:58:49http://oshiete1.goo.ne.jp/qa4821139.html
0506デフォルトの名無しさん
2009/04/01(水) 01:09:53これで先に進めそうです。
ありがとうございました。
0507デフォルトの名無しさん
2009/04/08(水) 10:28:330508デフォルトの名無しさん
2009/06/21(日) 20:30:51百万個を20ステップでバイナリサーチするlog nの威力を前にしてあっさり宗旨替えしたｗ
0509デフォルトの名無しさん
2009/06/21(日) 21:06:100510（ナワバリ付き）グループ内問題なら処理を軽くする法
2009/06/21(日) 21:48:11「指標が高い奴は低い奴に八つ当たりOK」
っていう移動対象絞り込み方が浮かんだ…
特定対象ばかりが連続移動を避けたい時？
実際には、完全独立自由主義でなければ
ご近所さんグループで扱う方がいいかな
グループ内成員どうしが比較的接近してて
他のグループの成員とは離れている場合
「外」への移動を好ませればいいのかな
平面なら上が第一候補、ダメなら右など
優先でダメなら時計回りに選択肢変更
一通り計算後グループ内を一斉移動
明確なグループがなければ初期座標で分類
以降はそれに従う（大きな変動がなければ）
通信などによって掛かる時間が移動させる
対象の個数そのものならこんな感じかな？
均等に散らばってれば走査線が一番？
研究・ライブラリ等充実してるようだし
(「MMORPGのアイテムやPCの移動じゃないんだから…w」
※身内や同画面内の都合なら移動もガマンしてくれる等
0511デフォルトの名無しさん
2009/06/22(月) 23:33:24ソートのステップ数も入れて考えられた？
0512デフォルトの名無しさん
2009/07/27(月) 18:33:040513デフォルトの名無しさん
2009/07/27(月) 21:07:380514デフォルトの名無しさん
2009/07/29(水) 07:01:460515デフォルトの名無しさん
2009/07/29(水) 07:07:200516デフォルトの名無しさん
2009/07/29(水) 07:15:13だとしてもエラトスに帰着されるのですか？
0517デフォルトの名無しさん
2009/07/29(水) 09:05:55「ぷりぷり生成」の意味が曖昧。
0518デフォルトの名無しさん
2009/07/29(水) 09:17:270519デフォルトの名無しさん
2009/07/29(水) 12:23:11したがって、（最初の2を別として）奇数を順に生成して、それを
ふるいにかけるという方法しかない。
0520デフォルトの名無しさん
2009/07/29(水) 12:42:47> 一般的に次の素数を求める方法、というのは存在しない。
マジ？詳しく教えて
0521デフォルトの名無しさん
2009/07/29(水) 13:25:072 からスタートして永遠に次に大きい素数を吐き出し続ける事とします
0522デフォルトの名無しさん
2009/07/29(水) 14:38:46メモリは無限にあるとしてよいならば試し割りなり篩なりで十分。
高々有限ならば、不可能。
0523デフォルトの名無しさん
2009/07/29(水) 15:18:33無理しなくていいよ
たまには素直になろうね
0524デフォルトの名無しさん
2009/07/29(水) 16:11:26>>516のように2,3,5,7,9,11,13とぷりぷりたれるだけなら、
a[0]=2,a[1]=3,a[n+1]=a[n]+2で十分だろ
9を素数だと思ってんだしさ
このテの人はどうせめちゃくちゃ大きい素数なんて出力させないんだし、
試し割りでも採用してればいいだろｗ
0525デフォルトの名無しさん
2009/07/29(水) 16:19:430526デフォルトの名無しさん
2009/07/29(水) 16:39:480527デフォルトの名無しさん
2009/07/29(水) 17:28:28これで200個ぷりぷりでます
これ以上圧縮してかけなかったｗ
0528デフォルトの名無しさん
2009/07/29(水) 18:34:01x[1<<15],w=1200,p,r;main(s){for(;++s<w;)for(x[p+=r==1]=r=s;s%--r;);}
0529デフォルトの名無しさん
2009/07/29(水) 19:31:03素数はメモライズしていった方が速いわけですね
でもこのやり方はメモリも無尽蔵に使うということですかね
0530デフォルトの名無しさん
2009/07/29(水) 19:59:530531デフォルトの名無しさん
2009/07/29(水) 20:46:49確かwikiで見たが、思い出せん
0532デフォルトの名無しさん
2009/07/29(水) 20:54:28これとは別に、wikiに解が素数となる式が載ってるね
常人には理解不能だわ
wz + h + j ? q = 0
(gk + 2g + k + 1)(h + j) + h ? z = 0
(16k + 1)3(k + 2)(n + 1)2 + 1 ? f2 = 0
2n + p + q + z ? e = 0
e3(e + 2)(a + 1)2 + 1 ? o2 = 0
(a2 ? 1)y2 + 1 ? x2 = 0
16r2y4(a2 ? 1) + 1 ? u2 = 0
n + l + v ? y = 0
(a2 ? 1)l2 + 1 ? m2 = 0
ai + k + 1 ? l ? i = 0
((a + u2(u2 ? a))2 ? 1)(n + 4dy)2 + 1 ? (x + cu)2 = 0
p + l(a ? n ? 1) + b(2an + 2a ? n2 ? 2n ? 2) ? m = 0
q + y(a ? p ? 1) + s(2ap + 2p ? p2 ? 2p ? 2) ? x = 0
z + pl(a ? p) + t(2ap ? p2 ? 1) ? pm = 0
0533デフォルトの名無しさん
2009/07/29(水) 22:48:35どこのwikiに載ってたの？
0534デフォルトの名無しさん
2009/07/30(木) 07:13:020535デフォルトの名無しさん
2009/07/30(木) 12:13:470536デフォルトの名無しさん
2009/07/30(木) 12:42:35声優で喩えて
0537デフォルトの名無しさん
2009/07/30(木) 13:38:190538デフォルトの名無しさん
2009/07/30(木) 15:11:050539デフォルトの名無しさん
2009/07/30(木) 17:33:34google books で、ウェルズのプライムナンバーズの訳本が読めるぞ。
該当箇所は、P122だけど、ちょうどそこは読める範囲にある。
興味があればどうぞ。
0540デフォルトの名無しさん
2009/07/31(金) 02:19:19名言集 その１
『アパッチ砲はワシが作った』
http://jbbs.livedoor.jp/bbs/read.cgi/internet/134/1229674638/5062
自分の管理するしたらばで借りた掲示板にて
> 5062 ：自動保守 ◆AOIMAD.NZM [] ：2009/08/16(日) 00:46:29 ID:nQYgq9jg0
> そもそも、アパッチ砲っていうのは、私が指揮官になった時代に私の先輩たちが導入して
> 先輩たちが命名したもの、っていうかまぁ、そういう砲は今まで存在してないから
> 名前つけなくちゃいけないしｗ
>
> ってことで、使っているうちに広まった名前なので、それが正式名称になるんじゃないかと。
>
> http://www.paradisearmy.com/doujin/pasok_apache.htm（俺の先輩が命名）
> http://www.paradisearmy.com/doujin/pasok_hping.htm（俺が命名？）
※注 「アパッチ砲」の正式名称は「Apache Jmeter」で、もちろん自動焼人の先輩が作ったものではありません
----------------------------------------------
この自動焼人 ★メールマガジンの配信停止をご希望される方は
http://qb5.2ch.net/test/read.cgi/sec2chd/1250169591/
にて自動焼人 ★までご連絡ください
0542デフォルトの名無しさん
2009/11/09(月) 05:02:04小数点演算を使用せず整数のまま演算し、
実数の平方根を超えない最大の整数を返すものとします
0543デフォルトの名無しさん
2009/11/09(月) 06:29:510544デフォルトの名無しさん
2009/11/09(月) 08:42:180545デフォルトの名無しさん
2009/11/09(月) 12:09:280546デフォルトの名無しさん
2009/11/09(月) 20:55:550547デフォルトの名無しさん
2009/11/11(水) 09:09:02f'(x)=2x
2a(x-a)+(a^2-n)=0
x=(n+a^2)/2a
>>> def x(n, a):
... b = (n+a*a)/(2.0*a)
... if b - a > -0.000000001 and b - a < 0.000000001:
... print b
... else:
... x(n, b)
...
>>> x(2, 1)
1.41421356237
0548デフォルトの名無しさん
2009/11/11(水) 09:43:10なんでニュートン方の実装例出してるの？
0549デフォルトの名無しさん
2009/11/11(水) 10:39:580550デフォルトの名無しさん
2009/11/11(水) 10:49:462の平方根が1とかって意味あんのか？
0551デフォルトの名無しさん
2009/11/12(木) 01:38:30最小自乗などなら解けるかなと思ったのですが…、どなたかご教授願います。
問題：
ΣCkX^k→Σ(AkXk-Bk)^k+e
すべて実数スカラ値。kの範囲は0<k<n。eは誤差値。^kはk乗の意。
左辺が与えられた時に、eを最小にするAnとBnを求める。
0552551
2009/11/12(木) 01:58:02ΣCkX^k→Σ(AkXk-Bk)^k+e
ではなくて
Σ(CkX^k)→Π(AkXk-Bk)^k+e
でした
0553デフォルトの名無しさん
2009/11/12(木) 12:50:07でなく？
0554551
2009/11/12(木) 13:38:170555デフォルトの名無しさん
2009/11/13(金) 10:02:20それバグってルし
0556デフォルトの名無しさん
2009/11/13(金) 12:28:15なんでニュートン方の実装例出してるの？
0557デフォルトの名無しさん
2009/11/13(金) 12:42:552の平方根が1とかって意味あんのか？
0558デフォルトの名無しさん
2009/11/14(土) 23:12:53なんで無いと思うんだ？
0559デフォルトの名無しさん
2009/11/15(日) 09:52:32>>548-550
>>556-557
0560デフォルトの名無しさん
2009/11/15(日) 10:20:04いや、そういう仕様だし。
これを平方根だというから誤解が生じるんであって、
「(int)floor(sqrt(x)) の値を float 介さず求める関数を作れ」でしょ。
0561デフォルトの名無しさん
2009/11/16(月) 23:15:100562デフォルトの名無しさん
2009/11/16(月) 23:33:04「実数の平方根を超えない最大の整数を返すものとします」
0563デフォルトの名無しさん
2009/11/17(火) 23:52:09整数なら各ビット毎に収束させる事で必要ビット数の半分のループ（32bitなら16)で解がでるのね
0564デフォルトの名無しさん
2009/11/18(水) 02:02:43事実上>>545の亜種のような気がするが…
0565デフォルトの名無しさん
2009/11/18(水) 12:28:240566デフォルトの名無しさん
2009/11/18(水) 12:43:06{
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;
}
0567デフォルトの名無しさん
2010/04/14(水) 05:43:19オレの中ではインサーションソートが一番なんだが、これよりもっと使いやすいのある？
0568デフォルトの名無しさん
2010/04/14(水) 07:48:39高速に安定なソートをしたければ。
再帰が不可ってのはマージソートも不可？
0569デフォルトの名無しさん
2010/04/14(水) 08:01:420570デフォルトの名無しさん
2010/04/14(水) 08:08:29実装が容易(=コード量が少ない)とか、並列化が容易とか、オンラインとか、構造に依存しないとか。
0571デフォルトの名無しさん
2010/04/14(水) 08:27:51矛盾は無いが、現実には・・・・・
0572デフォルトの名無しさん
2010/04/14(水) 09:02:29欲しいな
0573デフォルトの名無しさん
2010/04/14(水) 09:07:100574デフォルトの名無しさん
2010/04/14(水) 09:25:22ソートだったら、開始する時点で対象データが不完全(あとで増えるかもしれない)でもいいってこと。
0575デフォルトの名無しさん
2010/04/14(水) 09:38:09入力待ちしつつ、入力されたものを随時処理してソート済みデータに並べられるようなヤツね。
while (fgets(buf, sizeof(buf), stdin) != EOF) {
add_with_sort(array, buf);
}
みたいな。
0576デフォルトの名無しさん
2010/04/14(水) 21:08:57そういう言い方をするとアルゴリズムというより、パターンって気がしないか？
単にオンラインアルゴリズムと呼んだ場合は、入力の随時処理じゃなくて、
とあるアルゴリズムで入力データ列を取り扱う時、全体を捜査しなくても
実行できるアルゴリズムのことだろう。
もちろん途中で入力が行われてもアルゴリズム自体はそれに対して特別な
処理を行わず、入力された値は単にデータ列の最後に追加されるだけ。
それはともかく、プログレスバーの表示を、オンラインアルゴリズムで処理する
うまい方法はないものだろうか。
もちろん完全な処理が無理なのは分かっているが…大量のファイルを取り扱うときに
いつも悩んでしまう。
0577デフォルトの名無しさん
2010/04/14(水) 21:22:37進捗状況の評価方法や表示方法を再検討して
適切なものに切り替えていく…とか？
0578デフォルトの名無しさん
2010/04/14(水) 22:20:33In place mergeの亜種が現在最速かな。
0579デフォルトの名無しさん
2010/04/18(日) 00:42:41マージソートは再帰なしでも実装できるが
0580デフォルトの名無しさん
2010/04/18(日) 13:03:030581デフォルトの名無しさん
2010/04/25(日) 16:42:26-----------
0.4 | 0.2| 0.2
----------
0.1 | 0.5| 0.3
みたいな3x3バッファがあって
座標をxとyであらわして
ただxyは整数ではなく0.0～1.0の微笑範囲で
示された座標の値を計算するにはどうすればいいんだろう
手法の名前でも分かれば検索出来るんだけど
こういう計算って何て呼ぶのか分からない
0582デフォルトの名無しさん
2010/04/25(日) 16:46:280583581
2010/04/25(日) 16:51:09中の数字を広大な平面に広げた時になめらかに起伏した山と谷になるでしょ
その広大な座標の中での実際の数字が知りたい
0584デフォルトの名無しさん
2010/04/25(日) 16:56:11バイリニア補間やらスプライン補間やら好きなの使え
0585デフォルトの名無しさん
2010/04/25(日) 17:17:33ああ そうか 補完と同じことか
ありがとう助かった
0586デフォルトの名無しさん
2010/05/05(水) 14:07:080587デフォルトの名無しさん
2010/05/05(水) 14:44:330588デフォルトの名無しさん
2010/05/21(金) 19:32:09の表紙がグロテスクで買うのに躊躇(>_<)
http://www.amazon.co.jp/gp/product/images/4873114284/ref=dp_image_0?ie=UTF8&n=465392&s=books
何の虫？
一瞬、ゴキブリかと思ってしまった。
0589デフォルトの名無しさん
2010/05/21(金) 19:41:46ザリガニか何かの一種？
0590デフォルトの名無しさん
2010/05/21(金) 20:05:29って健康器具の夢を見た
0591デフォルトの名無しさん
2010/05/21(金) 21:06:07お前のレスのおかげで忘れかけてた何かを思い出した
真中で折れ曲がる簡易ベッドみたいなやつを思い出した
頭の中から離れなくなったぞ、どうしてくれる
0592デフォルトの名無しさん
2010/05/22(土) 06:19:10ヤドカリだよ
0593デフォルトの名無しさん
2010/05/22(土) 23:00:07衝突した際の平面移動については実装できたのですが、
円盤の回転については、これといったアルゴリズムが見つかりません。
壁や円盤に衝突した円盤の角速度の求め方は、
どのようなものでしょうか？
0594デフォルトの名無しさん
2010/05/22(土) 23:25:43接触した瞬間の微小時間における「こすれる速度」を求める。
速度vで45度で壁に衝突したなら、0.7v （√2 / 2）。
それに適当な摩擦係数で、円盤自身の回転も加味してやればいいんじゃないかな？
ていうか物理板あたりにシミュレーションのスレが...ないなw
0595デフォルトの名無しさん
2010/05/22(土) 23:29:43角速度から円周での速度に置き換えてさ
0596デフォルトの名無しさん
2010/05/22(土) 23:58:490597デフォルトの名無しさん
2010/05/23(日) 01:08:53float や double とかなら数学ライブラリであるんだけど、char だと
for(int y = 0; y < H; ++y)
for(int x = 0; x < W; ++x)
dst[x][y] = *(++src);
とか順番に入れていく方法しか思いつかない。
0598デフォルトの名無しさん
2010/05/23(日) 10:56:200599デフォルトの名無しさん
2010/05/23(日) 11:35:28それって、アルゴリズムはいいとして、
*(++src) って src をインクリメントしたものを参照してるよね？
分かってるんならいいけど。
0600デフォルトの名無しさん
2010/05/23(日) 20:37:32で一つのイディオムとして覚えてる。
0601デフォルトの名無しさん
2010/08/12(木) 15:25:030602デフォルトの名無しさん
2010/09/03(金) 12:10:05いわゆるcの累乗根 c^(1/2n)（但しnは2の倍数）です。
ニュートン法で愚直に求める以外だと、power法ぐらいしか思い浮かびませんでした。
cは実数を考えてますが複素数のアルゴリズムでも構いません。
0603デフォルトの名無しさん
2010/09/03(金) 19:01:09つまりc^(1/m)（但しmは4の倍数）か。
0604デフォルトの名無しさん
2010/09/03(金) 19:54:280605デフォルトの名無しさん
2010/09/03(金) 20:13:010606デフォルトの名無しさん
2010/09/04(土) 08:19:340607デフォルトの名無しさん
2010/09/04(土) 09:46:552の倍数ではなくて 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は複素数なのでニュートン法以外で累乗根を求めるアルゴリズムを所望します。
0608デフォルトの名無しさん
2010/09/04(土) 10:41:180609デフォルトの名無しさん
2010/09/25(土) 18:32:00「アルゴリズムイントロダクション」を見たら、ならし解析（だったっけ）と書いてあった。
amortizeってそんな意味があるの？
0610デフォルトの名無しさん
2010/09/26(日) 18:43:11英辞郎引け馬鹿者が
0611デフォルトの名無しさん
2010/09/26(日) 19:19:320612デフォルトの名無しさん
2010/10/28(木) 20:47:40そんな都合のイイアルゴリズムって有りますか？
0613デフォルトの名無しさん
2010/10/28(木) 20:54:260614デフォルトの名無しさん
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桁の数を答えよ。
0615デフォルトの名無しさん
2010/10/30(土) 14:39:19def 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)
}
}
}
}
}
すんげー遅い。アルゴリズムとはよべないｗ
0616デフォルトの名無しさん
2010/10/30(土) 14:44:170617デフォルトの名無しさん
2010/10/30(土) 21:22:16http://codepad.org/CxbENTUj
0618デフォルトの名無しさん
2010/10/31(日) 01:11:19中学入試でそんな難しい問題が出るのかよw
0619デフォルトの名無しさん
2010/10/31(日) 05:04:08下手なコードだなあ
0620デフォルトの名無しさん
2010/10/31(日) 05:38:32総当りしなくても求められそうだけど
http://codepad.org/U6V8vTuL
0622デフォルトの名無しさん
2010/10/31(日) 05:56:15うまいな
http://codepad.org/VofqW1k0
0623デフォルトの名無しさん
2010/10/31(日) 07:29:41下手なコードだなあ
0624デフォルトの名無しさん
2010/10/31(日) 10:54:56http://ideone.com/v5yBW
こんなもんかな。
0625デフォルトの名無しさん
2010/10/31(日) 10:56:14同じ書き方なら、Cとかでやっても3秒くらいかかるね。
早くしたければ、動的計画法的なアルゴリズム使わなきゃダメだけど、ものすごい面倒。
0626デフォルトの名無しさん
2010/10/31(日) 11:44:22大げさすぎて吹いたｗ
>>617
ああ、やっぱそうやって b = a + 1方式で減らせるのか。
>>625
まぁほんとは、そういう何らかの気の利いたのを求めてるんだろうけど。
0627デフォルトの名無しさん
2010/10/31(日) 13:04:53>>626
問題文をそのまま書いたらそうなった。
問題文を手続きに翻訳とかしたくない。
0628デフォルトの名無しさん
2010/10/31(日) 18:06:140629デフォルトの名無しさん
2010/10/31(日) 18:26:080630デフォルトの名無しさん
2010/10/31(日) 22:38:092桁の数「アイ」は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 は オ)
ということで、こんなもんかな → http://codepad.org/OTEAlb7U
0631デフォルトの名無しさん
2010/10/31(日) 22:40:130632デフォルトの名無しさん
2010/11/01(月) 13:30:120633デフォルトの名無しさん
2010/11/01(月) 18:58:48コードがへたくそか否かを示すことは多項式時間でできるが、
上手なコードを書くことはできない。
0634デフォルトの名無しさん
2010/11/02(火) 05:28:27エレガントなアルゴリズムを吐き続けるアルゴリズムが書けるぞ。
0635620 ◆mNdSWHMiXkWr
2010/11/02(火) 06:36:303つの数の選び方ってどの組み合わせでも成立しないとダメ？
http://codepad.org/D8bessOz
0636デフォルトの名無しさん
2010/11/02(火) 06:48:520637デフォルトの名無しさん
2010/11/02(火) 17:06:300638デフォルトの名無しさん
2010/11/02(火) 17:37:43それ、チャイティンがパラドックス指摘してただろ
0639デフォルトの名無しさん
2010/11/02(火) 20:06:47そうなるとまずエレガントなアルゴリズムの定義が必要になる
0640デフォルトの名無しさん
2010/11/02(火) 20:10:03／￣￣￣￣￣＼
| ・ Ｕ |
| |ι |つ
Ｕ｜｜ ￣￣ ｜｜
ぼくエレガント
0641デフォルトの名無しさん
2010/11/02(火) 20:53:320642デフォルトの名無しさん
2010/11/02(火) 20:57:160643デフォルトの名無しさん
2010/11/03(水) 05:38:31> エレガントなアルゴリズムの定義
「同機能のプログラムの中で、最小ビットのプログラム」.
しかしそれは、ベリーのパラドックスと同じように、容易に矛盾をきたす。
0644デフォルトの名無しさん
2010/11/03(水) 13:17:30要求仕様とアルゴリズムがあまりにも乖離してると
保守性が悪くて難儀する
0645デフォルトの名無しさん
2010/11/03(水) 16:18:50下k桁で考える場合は？
0646デフォルトの名無しさん
2010/11/03(水) 16:20:35∧＿∧∩))
( ・∀・)彡 パーン！
((⊂彡☆∩ _, ,_
⊂(⌒⌒（；｀Д´）
｀ヽ_つ ⊂ノ ←>>640
0647デフォルトの名無しさん
2010/11/03(水) 16:25:471997年、僕のお兄さんの年齢は、w+x+y+zになりました。
僕のお兄さんは何歳になったでしょう？
0648デフォルトの名無しさん
2010/11/03(水) 16:30:33これはいける？
0649デフォルトの名無しさん
2010/11/03(水) 16:34:43w = 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歳。
0650デフォルトの名無しさん
2010/11/03(水) 16:36:51この正９角形の周上にすべての頂点を持つ正多角形の
辺数n を５つ求めよ。
さらに各n に対し、そのような正n 角形の例を１つあげて１辺の長さを求めよ。
0651デフォルトの名無しさん
2010/11/03(水) 16:42:24(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
}
}
}
}
0652デフォルトの名無しさん
2010/11/03(水) 16:55:37n = 3 の時、一辺の長さ無数にないか。
0653デフォルトの名無しさん
2010/11/03(水) 17:00:09辺の長さについては一例でいいのでしょうね
0654デフォルトの名無しさん
2010/11/03(水) 17:13:200655デフォルトの名無しさん
2010/11/03(水) 17:23:200656デフォルトの名無しさん
2010/11/09(火) 02:41:51例えば、3:2:2:1の比率でfunc[0],func[1],func[2],func[3]をランダムに取得したい
さらに言うと比率も項数も動的に変化する
0657デフォルトの名無しさん
2010/11/09(火) 02:58:55if r < 3 then i = 0
else if r < 5 then i = 1
else if r < 7 then i = 2
else i = 3
func[i]
じゃダメ？
0658デフォルトの名無しさん
2010/11/09(火) 03:39:410659デフォルトの名無しさん
2010/11/09(火) 05:27:55void 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)];
0660デフォルトの名無しさん
2010/11/09(火) 10:15:320661デフォルトの名無しさん
2010/11/09(火) 10:26:11f = a[乱数 % (3+2+2+1)]
f()
0662デフォルトの名無しさん
2010/11/09(火) 17:58:11do{x=r()%size(a);y=r()%max(a);}while(a[x]<=y);
f[x]();
0663デフォルトの名無しさん
2010/11/12(金) 23:27:030664デフォルトの名無しさん
2010/11/19(金) 21:40:090665デフォルトの名無しさん
2010/12/01(水) 15:36:00ハッシュ関数のパラメーターをループでまわしながら見つかるまで耐えるんですか？
0666デフォルトの名無しさん
2010/12/02(木) 18:10:58純粋なヒープとヒープソートってどこが違うの？
0667デフォルトの名無しさん
2010/12/02(木) 18:57:15ヒープソートはヒープを使った整列アルゴリズム。
0668デフォルトの名無しさん
2010/12/02(木) 19:23:19gperfとか実装があるんだから、おそらくたいていの場合は実用になるような
アルゴリズムはあるんだろうと思われる。
0669デフォルトの名無しさん
2010/12/10(金) 09:48:220670デフォルトの名無しさん
2010/12/10(金) 09:56:270671デフォルトの名無しさん
2010/12/10(金) 09:57:290672デフォルトの名無しさん
2010/12/10(金) 17:19:190673デフォルトの名無しさん
2010/12/10(金) 20:58:330674デフォルトの名無しさん
2010/12/10(金) 21:13:430675デフォルトの名無しさん
2010/12/10(金) 21:37:45データーベースのレコードが少ないなら、INT数値で表現可能。
0676デフォルトの名無しさん
2010/12/10(金) 21:47:24つーか1ビットのデータを圧縮することが出来ないから完全に圧縮できるアルゴリズムは存在しない
0677デフォルトの名無しさん
2010/12/10(金) 21:48:190678デフォルトの名無しさん
2010/12/10(金) 21:56:15URL短縮サービスなんかがまさにそれだよね。
0679デフォルトの名無しさん
2010/12/10(金) 22:06:510680デフォルトの名無しさん
2010/12/10(金) 22:14:21DNFにする方法はないでしょうか？
あったら，命題論理式の充足可能性が線形時間で解ける，ということはないのかな？
0681デフォルトの名無しさん
2010/12/10(金) 23:05:29それって辞書方じゃない？
0682デフォルトの名無しさん
2010/12/10(金) 23:22:090683デフォルトの名無しさん
2010/12/11(土) 02:25:070684デフォルトの名無しさん
2010/12/11(土) 04:57:470685デフォルトの名無しさん
2010/12/11(土) 12:36:54ファイルを作りまくったら、
あっという間に限界数に達するでしょ
110a000f Winodws10_Ult.iso
これ解凍してみて
0686デフォルトの名無しさん
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を探す
わりと利用価値はあると思うんですが
こういうのってないですかね？
0687デフォルトの名無しさん
2010/12/11(土) 19:30:23"[1-6,8-10,11-13]" みたいな出力をおこなうメソッドを追加する、とかする。私なら。
要素の数が何万とかになるんだったら考え直すけどね。
0688デフォルトの名無しさん
2010/12/11(土) 19:41:03struct X{int max,min;struct r{int MAX,MIN;,struct r*next;}*hole;};
0689デフォルトの名無しさん
2010/12/11(土) 19:43:44昔、十年位前に同じような発想で同じようなもの作ったことあるわ。
はっきり思い出せないけど。
0690デフォルトの名無しさん
2010/12/11(土) 20:01:360691デフォルトの名無しさん
2010/12/11(土) 20:37:19> わりと利用価値はあると思うんですが
具体的に、どういうシーンでどういう利用方法（需要）があるの？
いくつか挙げてみて
アルゴリズムとデータ構造というのは、
なにか問題を解決するために生まれるものだからね
その解決したい問題が具体的に無ければ、たいてい話は発展せず、
あやふやなまますぐに消えるよ
問題が具体的にあって、それがみんなの興味を惹けば、
データ構造から、それを使ったアルゴリズム、
計算量の話まで発展する場合もある
0692デフォルトの名無しさん
2010/12/11(土) 20:49:01自分が使おうと思ってるのは、繰り返し要素付のカレンダーの実装です
探索や追加削除の速度よりも、和集合/差集合が早いデータ構造だと嬉しいです
オレオレ実装なら自分でも多分作れますが
よく知られたデータ構造は無いんですかね？
コンテナの要素をRange<T>型にして
T型の大小の比較関数と、精度関数があれば
ジェネリックに出来ると思うんですよ
(比較関数だけだと
1-3と3-4はくっつけられるが
1-2と3-4はくっつけられない)
0693デフォルトの名無しさん
2010/12/11(土) 21:54:30和集合/差集合の演算が速くて楽だと思う。
範囲の先端のインデックスと、終端のインデックスの対をリストにして持つ。
[(先端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) とすればいい。
0694デフォルトの名無しさん
2010/12/11(土) 22:30:42A,Bがソート済ならCもソート済になると思うので、
実質和集合を取る操作はO(A+B)=O(N)かな？
ソートは先端の昇順、終端の降順にして
<2>の追加時にある程度処理しておけば計算量的には同じだけど少しだけ速く出来そうです
和集合O(N),探索O(N),追加O(N)ですね
ちょっと実装してみます
0695デフォルトの名無しさん
2010/12/11(土) 22:37:01アルゴリズムとしてはそれほど難しいものにはならないだろうし、それほど深い議論には
発展しないだろうが、ジェネリックで実装された使いやすいクラスにでもまとまれば、
使用する機会もあるだろう。
0696デフォルトの名無しさん
2010/12/11(土) 23:05:39ただそれ以上の汎用的な物は作ったことがないな。
使うケースもそうないし。
0697デフォルトの名無しさん
2010/12/11(土) 23:15:120698デフォルトの名無しさん
2010/12/11(土) 23:41:07Javaで手抜きジェネリック版を書いてみたけど
codepad、今落ちてます？アクセスできない
0699デフォルトの名無しさん
2010/12/11(土) 23:46:43というかNSIndexSetか
0700デフォルトの名無しさん
2010/12/12(日) 02:33:59授業内容がif文とは～とか５分ぐらい説明してでは後は皆さんで自習してくださいって感じの超手抜き
なのにレポートがこれ実装できないと出来ないっぽい問題で唖然とした
0701デフォルトの名無しさん
2010/12/12(日) 03:13:150702デフォルトの名無しさん
2010/12/12(日) 03:19:18大学は教えてもらう場所でもありますよ
0703デフォルトの名無しさん
2010/12/12(日) 09:51:53せっかくの授業料をドブに捨てて、独学しましたとか自慢するバカ。
よくいるよねw
0704デフォルトの名無しさん
2010/12/12(日) 10:07:000705デフォルトの名無しさん
2010/12/12(日) 14:31:40その受け身な態度じゃ何も身につかないってw
ほんとに「学び方」知らないのか？
0706デフォルトの名無しさん
2010/12/12(日) 15:03:460707デフォルトの名無しさん
2010/12/12(日) 15:13:22つまり講義形式の勉強は存在しないと主張するわけですか？
ひょっとして頭おかしいんじゃないですか？もう一度よく確認してください
教えてもらう講義形式、参加型のゼミや実験、自習もなにもかもひっくるめて大学でしょう
そもそも読書による独学も直接的な対話が無いだけで教えてもらっていることには違いは無いというのに
すべてが独力で学べるものであり、学生は独力で勉強するものであると考えているなら一度脳を解剖して検査してもらったほうが良いですよ
0708デフォルトの名無しさん
2010/12/12(日) 15:14:330709デフォルトの名無しさん
2010/12/12(日) 15:17:57専ブラで見れば実際の順位なんてあってないようなもんなのに
0710デフォルトの名無しさん
2010/12/12(日) 15:21:35教えてもらう場所じゃない、学びに行く場所だよ
>>709
専ブラで見ないような奴が寄って来ないようにするためにsageるんだよ
0711デフォルトの名無しさん
2010/12/12(日) 15:46:58もしかして業務でもカスみたいなオーバーヘッドで騒ぎ立てるタイプ？
0712デフォルトの名無しさん
2010/12/12(日) 15:56:09ショーもない時代遅れのテクニックで得意になるタイプ？
0713デフォルトの名無しさん
2010/12/12(日) 16:02:400714デフォルトの名無しさん
2010/12/12(日) 16:28:470715デフォルトの名無しさん
2010/12/12(日) 16:48:07>>700 の講師の態度は教育者として良くないと思う。
でも、大学は学ぶ場所だから、レポートを提出しろと言われたら、
提出期限までにあらゆる手段を使って精一杯努力して学ぶのが本来の姿だよね。
その時間をしっかり取れるようにするのは大学側の責任だが、
そういう仕組みになっていない大学では、生徒は困惑するな。
>>700 の大学ではそうだったのかも知れんね。
0716デフォルトの名無しさん
2010/12/12(日) 16:55:100717デフォルトの名無しさん
2010/12/12(日) 17:09:380718デフォルトの名無しさん
2010/12/12(日) 17:15:57範囲の積ってどういう演算だっけ
0719デフォルトの名無しさん
2010/12/12(日) 17:23:44{ [1,2), [4,5] } * { [1,4] } = { [1,2), [4,4] }
0720デフォルトの名無しさん
2010/12/12(日) 17:55:37「速い文法」の意味が図りかねるが、
>>688 や >>693 と同じで昇順リストで持てばいいと思う。
補 ((補 A) 和 (補 B)) でよくない？
この計算が遅いの？
0721デフォルトの名無しさん
2010/12/13(月) 00:16:06開区間と閉区間の両方を許容させるの？
0722デフォルトの名無しさん
2010/12/13(月) 01:10:59doubleみたいな型ならともかく、整数型とかなら離散値だから
Complement({1,2})は{ [INT_MIN,0],[3,INT_MAX]}とすれば閉区間のみでいけるでしょ
補集合の計算は、実際は複数個範囲があるから-∞と∞を加えて(N-1)+2回ループでO(N)
なので積もO(N)で計算出来るね
0723デフォルトの名無しさん
2010/12/13(月) 01:16:140724デフォルトの名無しさん
2010/12/13(月) 02:18:130725デフォルトの名無しさん
2010/12/13(月) 02:45:24とりあえず株式会社ケイブに相談してみるｗ
0726デフォルトの名無しさん
2010/12/13(月) 07:49:01範囲検索([12,15][14,18] に対して [13,16] と重複する範囲要素を見つけるみたいな)も
したいならSkipListをベースに範囲拡張を仕込む手も
0727デフォルトの名無しさん
2010/12/13(月) 07:50:150728デフォルトの名無しさん
2010/12/13(月) 15:16:060729デフォルトの名無しさん
2010/12/13(月) 15:19:120730デフォルトの名無しさん
2010/12/13(月) 17:09:030731デフォルトの名無しさん
2010/12/14(火) 00:12:23こんなデータ構造があるんですね、面白いです
こういうわりと新しいデータ構造一覧みたいなの誰かどっかにまとめてくれないですかね
あれからちょっと考えていたのが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)*絞った要素数)、ぐらいで動きそうなので
シンプルな実装よりは早くなるんじゃないかと思います
0732デフォルトの名無しさん
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みたいな
0733デフォルトの名無しさん
2010/12/14(火) 01:20:46ユニマガでも解説されていたな。
0734デフォルトの名無しさん
2010/12/14(火) 03:14:500735デフォルトの名無しさん
2010/12/14(火) 03:24:060736デフォルトの名無しさん
2010/12/14(火) 03:29:460737デフォルトの名無しさん
2010/12/14(火) 09:57:56載っていたな。
0738デフォルトの名無しさん
2010/12/14(火) 10:37:51うろ覚えだけどそれってR木じゃない？
0739デフォルトの名無しさん
2010/12/14(火) 10:50:49さらに複数キー対応したら Multikey SkipGraph
検索を効率化した Skip B-trees
範囲キー対応した Rangekey SkipGraph
範囲内の最大値最小値平均値を高速に求められる 集約Skip Graph
多次元をあつかう SkipIndexやZnet
とかSkip系列は最近派生種が増えております
0740デフォルトの名無しさん
2010/12/14(火) 11:06:37こういうの放送大学とかでやってくれんかな。
0741デフォルトの名無しさん
2010/12/14(火) 11:08:250742デフォルトの名無しさん
2010/12/14(火) 11:54:25分散系だけどやってることの実現方法とか考え方はSkipListとかのデータ
構造に反映できると思う。
0743デフォルトの名無しさん
2010/12/14(火) 14:01:150744デフォルトの名無しさん
2010/12/14(火) 18:55:070745デフォルトの名無しさん
2010/12/14(火) 19:21:470746デフォルトの名無しさん
2010/12/14(火) 19:34:260747デフォルトの名無しさん
2010/12/14(火) 20:34:28そのあたりをタグに調べたら色々と見つかりました。
古典的には
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木の実装が面白かったです
0748デフォルトの名無しさん
2010/12/14(火) 23:11:33なわけない。
0749デフォルトの名無しさん
2010/12/15(水) 06:35:000750デフォルトの名無しさん
2010/12/17(金) 00:45:10・(例えばN=8なら)11387653みたいなクイーンの座標列を1遺伝子として
複数の遺伝子をつくり、交叉や突然変異で世代を進めていく
・83541267のように縦横にクイーンが重複しない遺伝子の組み合わせをつくり、
遺伝子内の座標の入れ替えで縦横の重複がない状態を保持しながら世代を進め、
斜めの重複を評価していく
のどちらが標準的なんでしょうか？遺伝的アルゴリズムの説明を読むと
前者な気がするんですが、Nクイーン、遺伝的アルゴリズムで検索して
はじめにヒットするpdfだと後者だと書いてあります。
単純に考えると前者は計算量が多くなり、後者は局所解に陥る（っていうんでしょうか）
可能性が高くなる気がしますが…
0751デフォルトの名無しさん
2010/12/20(月) 17:23:020752デフォルトの名無しさん
2010/12/20(月) 17:27:140753デフォルトの名無しさん
2010/12/20(月) 17:30:160754デフォルトの名無しさん
2010/12/20(月) 17:56:190755デフォルトの名無しさん
2010/12/20(月) 18:03:370756デフォルトの名無しさん
2010/12/20(月) 18:33:500757デフォルトの名無しさん
2010/12/20(月) 22:35:110758デフォルトの名無しさん
2010/12/20(月) 22:42:46INT_MAXを超えた場合はそれ未満の自然数（と0）は全部使われてるわけで
どっちみち一意にできっこない
0759デフォルトの名無しさん
2010/12/20(月) 22:49:15・オブジェクトは生成されたり破棄されたりする
・オブジェクトが生成されると同時にハンドルが与えられる
・オブジェクトが破棄されるとハンドルが再利用可能になる
・同時にINT_MAX個を超えるオブジェクトは存在しない
・再現性が必要なのでメモリアドレスをハンドルにすることはできない
としたらどうですか？
0760デフォルトの名無しさん
2010/12/20(月) 22:53:06過去レス読んでないけど、その処理は普通にやってる簡単だけど?
0761デフォルトの名無しさん
2010/12/20(月) 23:00:050762デフォルトの名無しさん
2010/12/20(月) 23:05:08単に、空きのIDを最速で検索する方法が答えではないのか?
0763デフォルトの名無しさん
2010/12/20(月) 23:06:160764デフォルトの名無しさん
2010/12/20(月) 23:09:37MAXが多い場合最速だろ。リストが空ならMAX使用中。
0765デフォルトの名無しさん
2010/12/20(月) 23:15:26・再現性が必要なのでメモリアドレスをハンドルにすることはできない
これが気になるな
何の情報を基に何を再現したいの？
0766デフォルトの名無しさん
2010/12/20(月) 23:35:22それってメモリ効率悪くね？
0767デフォルトの名無しさん
2010/12/20(月) 23:36:430768764じゃないけど
2010/12/21(火) 04:08:06単純連結リストがどんなものを想定しているのかしらんけど
配列ベースの循環キューにしとけばデータ分の配列＋頭と尻の位置ぐらいで済ませられる
0769デフォルトの名無しさん
2010/12/21(火) 08:40:220770デフォルトの名無しさん
2010/12/21(火) 09:13:150771デフォルトの名無しさん
2010/12/21(火) 09:50:510772デフォルトの名無しさん
2010/12/21(火) 19:33:400773デフォルトの名無しさん
2010/12/25(土) 08:38:540774デフォルトの名無しさん
2010/12/27(月) 15:16:140775デフォルトの名無しさん
2010/12/27(月) 18:45:28>>691
まー漏れも質問ばっかりになるのはどうかと思うけど
0776デフォルトの名無しさん
2011/01/11(火) 23:48:550777デフォルトの名無しさん
2011/01/28(金) 22:23:230778デフォルトの名無しさん
2011/02/16(水) 20:41:440779デフォルトの名無しさん
2011/02/24(木) 22:05:05.77今回加わった boost::icl、特に interval_set がそれ。
custom interval も喰える凄い奴。
0780デフォルトの名無しさん
2011/03/03(木) 22:01:40.300～節（葉も含む）の数通し番号を振って
通し番号順に値左右の子の番号を配列に格納してwrite
これより効率いい方法ありますか？
0781デフォルトの名無しさん
2011/03/03(木) 23:11:43.20要素ごとに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ビットの情報があれば再構成できそう
あとはこのビット情報をまとめてファイルに書き込めば
いいんじゃないかと
0782デフォルトの名無しさん
2011/03/03(木) 23:43:58.26ちょっとなんで？と悩みましたが良さそうですね
どうもありがとう！
0783デフォルトの名無しさん
2011/03/03(木) 23:45:27.730784デフォルトの名無しさん
2011/03/30(水) 01:46:58.51http://www.youtube.com/watch?v=kz1pPoTRhq4
0785デフォルトの名無しさん
2011/04/02(土) 18:56:53.74割り込みフラグ、割り込みマスクの意味を持っていて、
フラグが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;
}
0786デフォルトの名無しさん
2011/04/02(土) 19:11:35.76if(x&1)
x>>=1
0787デフォルトの名無しさん
2011/04/07(木) 14:18:17.60つまりどういうことです？
0788デフォルトの名無しさん
2011/04/26(火) 21:54:46.08単純に毎回ランダムな方向に進むんだったら酔歩になっちゃいますよね
ある方向にしばらく進む→しばらく止まる→またある方向に進む→
ようなかんじにしたいです。
参考になるサイト等ありますでしょうか
よろしくお願いします
0789デフォルトの名無しさん
2011/04/26(火) 23:29:18.80と
> ある方向にしばらく進む→しばらく止まる→またある方向に進む→
の違いが分からん
0790デフォルトの名無しさん
2011/04/26(火) 23:48:58.19ごめんさない
『進む』行為を1ステップごとに行うとして
毎ステップランダムな方向だとかんたんに実装できるけど酔歩で不自然な動きになりますよね
ある程度同じ方向に進んでから向きをランダムに変えてまたある程度同じ方向に進むような感じにしたいのです
よくゲームの敵キャラがそんな風に動いている気がするのですが、どのようなアルゴリズムなのかな、と
0791デフォルトの名無しさん
2011/04/27(水) 00:04:27.00と
止まる（じっとしてる）
を交互にやればいいじゃん
0792デフォルトの名無しさん
2011/04/27(水) 00:04:28.453歩先なり5歩先の座標を計算して
3あるいは5歩分は計算した座標まで均等にまっすぐ進む
計算座標まで到達したらランダムに方向を決めて再計算するとか
20年くらい前のレトロゲームならこんなものだと思う
0793デフォルトの名無しさん
2011/04/27(水) 11:29:31.10元祖ローグでは基本ランダム。
プレイヤーがとある範囲に入ったとき、
・近づく
・逃げる
・興味を示さない
などを行う。
ここら辺は敵の特性だったり、また状態(体力)などにより変る。
敵対なら範囲に入ってきたら近づいて攻撃したり、
プレイヤーに攻撃されて瀕死になった場合は遠ざかるなど。
ここが一般的にはＡＩとよばれています。
初代では行われていないけれど、もう少し世代が進むと経路探索を利用して、
ダンジョンのカベに引っかからずに目標のポイントに進むことも出来るようになっいます。
0794デフォルトの名無しさん
2011/04/27(水) 11:33:21.38>>788あてだったのにアンカー間違えた。
0795デフォルトの名無しさん
2011/04/27(水) 12:32:13.56頻繁に立ち止まったり
ときどきルートを少し外れながら帰り道をスタックするとそれっぽいかもしれないなあ
0796デフォルトの名無しさん
2011/04/27(水) 12:45:07.200797デフォルトの名無しさん
2011/04/27(水) 13:15:39.01まあお絵かきツールの塗りつぶしアルゴリズムに距離をついかししやれば
簡単な経路探索アルゴリズムが出来ますよ。
0798デフォルトの名無しさん
2011/04/27(水) 19:10:45.17人間が何かふらふらと見回りしているかのような徘徊だと思うが
実際のゲームは知らんが、>>790 の言う通りにするのなら、
まず進む向き d ベクトルと歩数 n をランダムに決める
それから、d 方向にランダムに k (<n) 歩歩いたら、少し止まって、
d 方向を平均として適当な分散の正規分布に従って、
ランダムに d' 方向を決める（要するに d' は d に近い値）
d' 方向にランダムに k' (<n-k) 歩歩いたら、また少し止まって、
先ほどと同じように d'' と k'' を決めてまた歩く
歩数 n 歩に到達したら、最初の進む向き d ベクトルと
歩数 n をランダムに決める事からまたやり始める
0799788
2011/04/27(水) 21:10:29.90やってみます
0800デフォルトの名無しさん
2011/04/28(木) 08:57:26.190801デフォルトの名無しさん
2011/04/28(木) 12:02:14.96経路探索いれて、目的地をランダムで決定すればよいとおもったんだけどな。
0802デフォルトの名無しさん
2011/04/28(木) 12:45:05.74壁とかあるかんじ？
0803デフォルトの名無しさん
2011/04/28(木) 13:24:34.55ターン制のシミュとかでも応用で移動コスト計算付で移動可能範囲を計算したり、
そこまでの移動経路を計算できたりするよ。
0804デフォルトの名無しさん
2011/04/28(木) 15:08:28.56AIは「モード」を持っていて、クロックごとにそのモードに従って行動する。
例えば「何もしない」「地点(X,Y)に速度Zで移動」「敵が視界内にいたらその位置に移動」とか。
0805デフォルトの名無しさん
2011/04/28(木) 15:22:20.640806デフォルトの名無しさん
2011/04/28(木) 16:09:07.690807デフォルトの名無しさん
2011/04/28(木) 18:02:10.24たぶん
主人公から遠い…非表示
主人公から近い…キョロキョロ>>788
キョロキョロ中に主人公が視界にはいる…発見
発見中…主人公追いかける、経路探索?
発見中に主人公を見失う…警戒
警戒中…はげしくキョロキョロ
警戒後一定時間経過…キョロキョロ
こんなんだったよな
実装めんどくさそう
0808デフォルトの名無しさん
2011/04/28(木) 18:50:18.99いろいろ難しいからなぁ
0809デフォルトの名無しさん
2011/04/29(金) 17:01:04.41http://xlinux.nist.gov/dads/
0810デフォルトの名無しさん
2011/05/09(月) 21:34:56.01長方形領域の集合を求めたいです。
全領域サイズの長方形をもってくればひとつの長方形でおおえますし、
大きさ一の長方形で覆うと考えれば最小の面積でおおえますが、
そのバランスのとれたかたち、なるべく少ない数の長方形の集合でそれなりに無駄なく覆う
というようなものをどうやったら求められるかなあと考えています。
こういう問題を解くためにはどういったアルゴリズムを用いればよいでしょうか？
また、こうした問題や、類似の問題で名前のついた問題ってありますかね？なにでぐぐってよいかわからなくて。
0811デフォルトの名無しさん
2011/05/09(月) 21:50:36.160812810
2011/05/09(月) 22:17:59.82文章がわかりにくかったです。
長方形領域の集合で、すべての１である部分を覆いたい、という問題です。
障子のあちこちに大きさ形まちまちの穴があいていて、
その穴をふさぐために使える障子の形を長方形に限定して
どうすればいい感じに全ての穴を塞げるか、というイメージです。
>>811
バックパッキングというのは、ナップサック問題みたいなものでしょうか？
どのように>>810に還元出来るでしょうか？
0813デフォルトの名無しさん
2011/05/09(月) 22:23:52.05つまりテーブルの上にコーヒーをこぼして、濡れてるところが 1 とかそんな。
0815デフォルトの名無しさん
2011/05/09(月) 22:31:35.13>>812
要するに、２次元平面上にある点群に対して、
ある程度近いもの同士でグループ分けしたいということでしょ
（問題名、アルゴリズム名は忘れた）
で、それぞれのグループを覆う長方形を考えれば、
まぁだいたいバランスは取れてる
0816デフォルトの名無しさん
2011/05/09(月) 23:01:54.69領域分割でぐぐるとそれらしいのが引っかかってくる
提示の例だと
http://codezine.jp/article/detail/167
とか
0817デフォルトの名無しさん
2011/05/09(月) 23:42:31.45□
□□□
□
が２つの長方形で重複はするが過不足なく覆えることは
どう考えればいいのだろう
0818デフォルトの名無しさん
2011/05/10(火) 00:30:51.45例えばパターンマッチにかけ、５個の長方形が十字型に並ぶパターンを見つけたら、
それらを融合させて２個の長方形へ最適化
しかし、例えば２個の長方形と、それをひとつにまとめた１個の長方形とで、
どちらが「少ない数の長方形の集合でそれなりに無駄なく覆う」ことになるのか
その「評価関数」は >>810 の中ではどうなってるんだろう
0819デフォルトの名無しさん
2011/05/10(火) 00:42:50.44ってのじゃ駄目かい？
全部1か0の場所は分割しないっていう感じで
大きさ1の長方形が定義されてるなら、関数を停止させる事も出来るだろうし
いや、よく分からんのだけど
0820デフォルトの名無しさん
2011/05/10(火) 07:55:25.52> 障子のあちこちに大きさ形まちまちの穴があいていて、
穴の位置が {(3.8, 2.6), (1.4, 1.4), (2.1, 3.5)} みたいにして与えられると思えばいい？
> その穴をふさぐために使える障子の形を長方形に限定して
辺は x, y 軸と平行？ どんな向きでもあり？
0821810
2011/05/10(火) 09:53:10.32ありがとうございます。
>>818
評価関数もふくめ方向性を考えてます
開いている穴のうちふさがれている割合 1.0
を必要条件として
長方形領域の集合のうち、穴を塞いでいる部分の割合をP
用いる長方形の個数をnとすると、
Pとnの多項式で定式化出来ると思いますが、具体的にどうとは考えてないです
>>820
今回私が解こうとしている問題に関しては
BOOL area[][];のようなかたちで入力は与えられますが、
おおむねそういう感じです。
長方形の辺は軸に平行で考えています。
0822デフォルトの名無しさん
2011/05/10(火) 14:22:27.31>>817 にあるように、うまく部分問題に分割できないのが難しいねぇ。
理屈の上では組合わせは有限なので順番に評価関数に食わせて一番評価の高いのを
選べばいいわけだけど、現実には組み合わせ爆発で無理だから、よさげなのを探索
するしかないかな。
戦略としてはトップダウンとボトムアップの2通りがあると思うんだけど、トップダウンのほうは、
まず1個の矩形からはじめて、矩形の数が増えてもいいから、塞いでる割合が増えるパターンを、
探索していく。この時最初の矩形より外に広がることはない。（>>817のように途中のプロセス
ではそうでない場合もあるのが難しいところ）
逆にボトムアップは、穴の1個1個をそれぞれ小さな矩形でふさいで、それをだんだん大きい
矩形の集まりにしてゆくというもの。これもやっぱり一本道というわけにいかないのが難しい。
0823デフォルトの名無しさん
2011/05/10(火) 22:59:01.22Graham走査だろ？ あとはググれ。
0824デフォルトの名無しさん
2011/05/10(火) 23:12:57.91おまえは使える奴なんだから、凸包の多角形から、どういうアルゴリズムで、
いい感じの長方形の集合を作るのか、ちゃんと説明しろよな。
0825デフォルトの名無しさん
2011/05/10(火) 23:51:27.600826デフォルトの名無しさん
2011/05/10(火) 23:58:02.300827デフォルトの名無しさん
2011/05/11(水) 10:02:48.660828デフォルトの名無しさん
2011/05/11(水) 12:00:00.47が言いたいことはGraham捜査で全ての点を包含する凸包の点を取得し、
その集合からXYそれぞれについての最上、最下の座標を探せば言いよってことなんじゃねえかと。
まあ全ピクセルを捜査してXYの各座標について最小、最大を
見つけるたびに書き換えてあげれば目的の長方形の見つかると思う。
ただし重いｗ
もしデータを書き込むところから制御できるなら、書き込むたびに
XYについて最小値、最大値を書き換えてあげば簡単に見つかると思う。
0829デフォルトの名無しさん
2011/05/11(水) 12:35:11.13もし >>823の意図がそれなら、彼は必ず一つの長方形で覆うものと勘違いしてないか？
点群が１ヶ所に固まっていれば長方形一つが最も無駄が無いだろうが、
まばらに分散していれば複数の長方形で覆った方が無駄が無い場合の方が多い
0830デフォルトの名無しさん
2011/05/11(水) 13:18:57.72前提として点を2つ以上含めた物を長方形とするって決まりが暗黙的に適用されるのかな。
長方形同士ってかさなってはいけないとかもあるのかな？？
0831デフォルトの名無しさん
2011/05/11(水) 15:06:17.79とりあえず、ある程度の塊に点群を分類してからやりたいなら、空間(ここでは平面か)分割してクラスタリング。
クラスタ重心を計算しながら分割領域を調整。調整が終わったらグラハムさんの出番。
…で、できそうな気がするけど、適当思考なので上手く分割できるかちょっと自信ない。
これだと、矩形の重なりは発生する可能性が残ってるし。
0832デフォルトの名無しさん
2011/05/11(水) 15:17:43.65だとすると、水平方向はある程度無駄が在ってもいいけど垂直方向はできるだけ無駄がない方がいいとか、
矩形同士が重ならないだけでなく水平方向に違う高さを持つ矩形が存在したら拙いとかw
0833デフォルトの名無しさん
2011/05/11(水) 15:25:36.600834デフォルトの名無しさん
2011/05/11(水) 15:47:16.41面積を最小にするのか、矩形の数を最小にするのか。
n個の点に対して、面積の最小値はnだし、矩形の最小値は1。
なので、求めるモノを定義しないと、「だいたいこんな感じ」の解しかでてこない。
0835デフォルトの名無しさん
2011/05/11(水) 18:06:34.87だから >>818 で評価関数はどうすんのと訊いたら、
>>821 でまだ考えていないと
0836デフォルトの名無しさん
2011/05/12(木) 00:17:47.500837デフォルトの名無しさん
2011/05/16(月) 19:43:52.240838デフォルトの名無しさん
2011/05/16(月) 20:55:05.61悪いが意味が分からん
具体的に、何か例を示してくれ
こういう入力に対して、こんな計算をして、こういう出力を得たい、とか
0839デフォルトの名無しさん
2011/05/16(月) 20:55:53.56なぜにそんな限定を？
0840837
2011/05/16(月) 22:13:20.11Yesなら[a,b)、Noなら[-inf,a)or[b,+inf)
で可変個の質問にユーザーに答えさせて範囲をand結合して絞りこむ
で、最後に絞り込んだ範囲を表示
という課題がでたんです
でもその講義でまだ入出力とifとgotoしかやってないんです配列もやってません
どうも周りに聞いたところによるとその教授は講義範囲外のことをあまり使うといい顔をしないらしいんです
ですので講義範囲内で処理したいんですが…という感じです
0841デフォルトの名無しさん
2011/05/16(月) 22:58:41.220842デフォルトの名無しさん
2011/05/16(月) 23:32:25.49宿題は自分でやれよ屑。
あと、おまえみたいなゴミは社会に出てくるな。
氏ね。
0843デフォルトの名無しさん
2011/05/17(火) 01:34:33.750844デフォルトの名無しさん
2011/05/17(火) 03:16:59.99講義範囲外のこと使っていい顔しない教授とかクソだから無視で。
0845デフォルトの名無しさん
2011/05/17(火) 07:32:31.58「できるんだったら来週からこなくていいよ。単位だしとくから」
ってのが大学的
0846デフォルトの名無しさん
2011/05/31(火) 21:25:56.80を行うデータが見つかるまで、それぞれ何回の判定が必要か、期待値を求めよ
これの逐次ってどうやって求めるんですか？？
1/31+2*1/30+・・・・
みたいな感じでしょうか・
またキーが含まれない場合もおしえてくださいｍｍ
0847デフォルトの名無しさん
2011/05/31(火) 21:39:11.09キーが含まれない場合は31回
0848デフォルトの名無しさん
2011/05/31(火) 21:53:04.17含まれる場合の期待値の求め方をおしえてください
キーが含まれない場合の２分木探索はどうやるんでしょうか？？
0849デフォルトの名無しさん
2011/05/31(火) 23:00:07.250850デフォルトの名無しさん
2011/06/04(土) 19:20:16.63何があるのですか？
0851デフォルトの名無しさん
2011/06/09(木) 15:23:27.24①昇順ソート→index1,2を取り出して合計して戻す
②一回操作して最小の2つのインデックスを記録→取り出して合計して戻す
どっちが速いかな？オーダーだけ見ると①のような気がするけどswapコストとか考えると②の方がいい？
0852デフォルトの名無しさん
2011/06/09(木) 15:29:12.790853デフォルトの名無しさん
2011/06/09(木) 16:00:31.18N=100万とかなら、迷わず2じゃね？
なんで、1のオーダーの方が小さいと思うの？
0854デフォルトの名無しさん
2011/06/10(金) 15:40:48.70これをjpgエンコードしたほうがいいのかpnhエンコードしたほうがいいのか判別するにはどのような方法が考えられるでしょうか
0855デフォルトの名無しさん
2011/06/10(金) 15:42:51.030856デフォルトの名無しさん
2011/06/10(金) 16:12:56.690858デフォルトの名無しさん
2011/06/10(金) 19:09:13.910859デフォルトの名無しさん
2011/06/10(金) 20:40:53.310860デフォルトの名無しさん
2011/06/10(金) 21:44:37.610861デフォルトの名無しさん
2011/06/10(金) 22:29:46.37グラデは順子が多いとか。
0862デフォルトの名無しさん
2011/06/10(金) 23:47:52.31(3) 最初にヒープを作る→ヒープから最小値2個取り出し合計してヒープに戻す
オーダー的にはこれがいいと思うよ
0863デフォルトの名無しさん
2011/06/12(日) 18:55:05.37それとも論理的な計算量だけで考える？
0864デフォルトの名無しさん
2011/06/12(日) 19:16:10.150865デフォルトの名無しさん
2011/06/14(火) 21:48:47.05a <= x <= bになる、「いい感じの整数x」を求める方法はないかね？
クイックソートのピボット選択や、パーリンノイズやGAで使いたい。
一番簡単なのはx=(a+b)/2なのだが、面白味に欠ける。
x=rand(b-a)+aだと、オーバーヘッドが大きい気がする。
できればaとbが一意ならxも一意で決まって欲しい。
フィボナッチ分割はどーかなー。
0866デフォルトの名無しさん
2011/06/14(火) 22:00:02.990867デフォルトの名無しさん
2011/06/14(火) 22:27:59.93> x=rand(b-a)+aだと、オーバーヘッドが大きい気がする。
アルゴリズムスレなんだから、「気がする」で放っておくんじゃなくて、
本当に求めているパフォーマンスを達成できないほどのオーバーヘッドか確認しようよ
あとアルゴリズムスレなんだから、何が「いい感じ」なのか
できる限りハッキリさせようよ
とりあえず、a と b の中間値が「いい感じではない」ことは分かった
擬似乱数はシードを決めれば入力値に対して一意に決まるが、
もしオーバーヘッドが気にならないほどであれば、擬似乱数でいいのか？
擬似乱数が「いい感じ」なのか？
そして、アルゴリズムスレなんだから、「フィボナッチ分割はどーかなー」ではなく、
実際にフィボナッチ分割したらどんな a b に対してどんな値が出力されたのか示してくれ
0868デフォルトの名無しさん
2011/06/14(火) 22:44:09.900869デフォルトの名無しさん
2011/06/15(水) 10:53:51.44でも、ピボットに使うっていっても、分布しだいじゃね？
0870デフォルトの名無しさん
2011/06/15(水) 16:07:33.88func 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);
}
}
で、モヤモヤした感じが出したい。
ピボットはまあ、乱択っぽくて任意の分布でもいいかなと。
0871デフォルトの名無しさん
2011/06/15(水) 16:15:47.190872デフォルトの名無しさん
2011/06/15(水) 18:27:45.990873デフォルトの名無しさん
2011/09/17(土) 00:42:57.61ここで質問して良いですか？
株の専門用語の話とかじゃなくてグラフに関する事なんですが。
0874デフォルトの名無しさん
2011/09/17(土) 09:06:44.120875デフォルトの名無しさん
2011/09/17(土) 11:11:15.41では、それで御願いします。
株のサイトでチャートの形によって、売買銘柄を
選択するサイトがあるのですが、その仕組みというか
考え方を教えて下さい。
一例として、上昇トレンドかどうか判断するには移動平均を
1日ずつ計算して前日より上がっているかどうかを比較して
いけばいいかなと思ったのですが、実際には上がったり下がったりして、
単純な比較だと、実際は上昇トレンドなのに途中に下がった日があるので、
上昇トレンドと判定できない場合が出てきます。
期間を決めて、その期間内の最高値と最安値が何月何日か、
もしくは、本日が期間内の最安値より高いかで決めるにも、
それじゃ、期間を何日間にするのかと言った条件によって
変わってくるだろうし、どう判断条件を作ればいいか分からないのです。
チャートの形にも色々あるので、簡単には説明できないと思いますが、
上昇トレンドの判断の仕方だけでも教えてもらえれば、他にも応用できるかも
しれないと思いますのでよろしくお願いします。
長文失礼しました。
0876デフォルトの名無しさん
2011/09/17(土) 11:52:34.060877デフォルトの名無しさん
2011/09/17(土) 12:13:47.96失礼しました。
0878デフォルトの名無しさん
2011/09/17(土) 14:12:58.78ロケット工学投資法にはトレンドラインの作り方が載ってる
まああれを馬鹿正直に実装するより楽な方法もあるんだが……
タダでは教えられんｗ
0879デフォルトの名無しさん
2011/09/17(土) 14:14:23.21追記。単に作画したパターンにマッチする銘柄を選択するだけなら、
それは「パターン認識」技術の世界だ。ぐぐれ。
0880デフォルトの名無しさん
2011/09/17(土) 15:01:28.43∧∧ ｺｲﾔｧｧｧｧ！！
(д´* )
（⊃⌒*⌒⊂)
/__ノωヽ__）
>>879
パターン認識、オソロシス
0881デフォルトの名無しさん
2011/09/18(日) 18:17:06.360882デフォルトの名無しさん
2011/09/18(日) 18:19:46.59チャートだけ見て判断とか馬鹿だろ。
帰納的に、現実に起こった事実と、チャートの微分を比較できなきゃ
予測がかすりさえしないだろ。
0883デフォルトの名無しさん
2011/09/18(日) 18:47:34.80お前は質問スレで何言ってんだ？
だったら、微分を調べろで良いだろ
馬鹿なのか？氏にやがれなのか？
0884デフォルトの名無しさん
2011/09/18(日) 21:10:40.430885デフォルトの名無しさん
2011/09/18(日) 21:15:05.39ごめんよ
0886デフォルトの名無しさん
2011/09/25(日) 05:50:28.01グラフの中から最長となる閉路を探す方法を教えて下さい
0887デフォルトの名無しさん
2011/09/25(日) 14:11:58.10前者の場合
元の木Tの最も深いノードをルートにした木T'において、
木T'のルートと最も深いノードの間に
一本だけ辺をつけ加えたのが最長閉路になるのでは？
0888デフォルトの名無しさん
2011/10/12(水) 11:34:06.03イテレータの内部にスタックorキューor到達済みノードのリストを動的に確保して保持することなく
すべてのノードを巡回する方法はありますか？
イテレーターなので再帰関数を使って一気にという事ができないので
どうしても内部に状態を保持しないとダメかなとは思うんですがアロケートを駆使返すのは効率が気になって…
0889デフォルトの名無しさん
2011/10/12(水) 13:32:29.720890デフォルトの名無しさん
2011/10/12(水) 20:48:32.37すべてのノードを共通の動的配列上に確保しておけば?
0891デフォルトの名無しさん
2011/10/12(水) 21:27:39.010892デフォルトの名無しさん
2011/10/12(水) 22:06:08.910893デフォルトの名無しさん
2011/10/12(水) 22:27:53.42ただし、木を破壊する
[1]. ルートノードを巡回する
[2]. ルートノードの子ノードから１つノードxを選び、
他の子ノードを全てxの子ノードにする
[3]. xをルートノードと見なして [1] へ
0894デフォルトの名無しさん
2011/10/12(水) 22:32:36.910895デフォルトの名無しさん
2011/10/13(木) 14:44:27.480896デフォルトの名無しさん
2011/10/25(火) 21:39:34.27アルゴリズム入門の授業なんですが
・性の小数部分を求めるサブルーチンＤＥＣのフローチャートを書け
・サブルーチンＤＥＣとサブルーチンＩＮＴを使って入力した正の実数の小数点以下を切り上げた
整数を表示するフローチャートを書け
お願いします
0897デフォルトの名無しさん
2011/10/25(火) 22:24:50.900898デフォルトの名無しさん
2011/10/26(水) 02:34:55.29アルゴリズムの授業なんだから多分ダメなんだろうね。
0899デフォルトの名無しさん
2011/10/26(水) 04:55:27.33切り上げは、小数部分が0かどうかで整数値か整数値+1かを返せばいい。
整数値は
1より小さくなるまで10で割るのを繰り返す。
その回数分10を掛けながら1～9までの値と比較することで一桁づつ数字を確定していく…
なかんじかな。ループ中に10を掛けている値から確定した数字を引いていくのと、
0に初期化してある変数に10を掛けながら足していくのを忘れずに。この変数が元の値の整数値になる。
浮動小数点数でやると、誤差が出るだろうけれど…
0900デフォルトの名無しさん
2011/10/26(水) 08:11:17.890901デフォルトの名無しさん
2011/10/26(水) 09:02:43.690902デフォルトの名無しさん
2011/10/26(水) 15:02:05.330903デフォルトの名無しさん
2011/10/26(水) 15:14:01.810904デフォルトの名無しさん
2011/10/26(水) 15:17:13.300905デフォルトの名無しさん
2011/10/26(水) 15:17:20.20教科書が、高校の情報の教科書の中で一番人気だという話だ。
0906デフォルトの名無しさん
2011/10/26(水) 15:30:03.53日本のソフトウェア開発は育たないわね。
0907デフォルトの名無しさん
2011/10/26(水) 15:36:20.78日本全体でオフィスソフトに使われている莫大な金を節約できる
0908デフォルトの名無しさん
2011/10/26(水) 16:20:09.01使う側からしたら無料なのはありがたいけど、作る側それこそ育たない。
0909デフォルトの名無しさん
2011/10/26(水) 17:41:00.780910デフォルトの名無しさん
2011/10/26(水) 17:58:05.44有料だと金が国外に流出してるだけだし
かといって無料だと国内でも回らないし
0911デフォルトの名無しさん
2011/11/07(月) 18:03:02.90末尾再帰の最適化について質問です。
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の累乗でスタックに詰まれていくから重くなるのだと思います。
0912デフォルトの名無しさん
2011/11/07(月) 18:19:50.43これで理解できなければあなたには無理です。
0913デフォルトの名無しさん
2011/11/07(月) 18:56:27.710914デフォルトの名無しさん
2011/11/07(月) 19:25:14.40末尾呼び出しになってない。
0915デフォルトの名無しさん
2011/11/08(火) 00:20:34.510916デフォルトの名無しさん
2011/11/08(火) 09:56:31.880917デフォルトの名無しさん
2011/11/08(火) 12:52:21.062つの関数が再帰呼び出ししてるのは関数の末尾じゃないし、
FunctionA と FunctionB で異なるのは引数がゼロの場合の返値だけ
おまけに、FunctionA(n-1)+FunctionB(n-1) は共に同じ n-1 に関数を適用してる
だったらアルゴリズムのスレとしては、
相互再帰呼び出しの形自体を止めて一つの関数にまとめた方が効率が良い、
としか言いようがない
そもそも、ここはアルゴリズム大辞典のスレなんだから、
何を実現したくてこのアルゴリズムを選択したのか言わないと議論にならん
（何を入力して何を得るのか）
これなら、ここじゃなくてExcelVBAの住人が答えるべきだと思うが
0918デフォルトの名無しさん
2011/11/08(火) 19:09:42.38このサイトの後半で紹介されている
最大公約数を使って配列を回転させるアルゴリズム
何か名称がついていたら教えてください。
0919デフォルトの名無しさん
2011/11/08(火) 19:38:54.10もしかして、
http://p2.2ch.net/p2/read.php?host=hibari.2ch.net&bbs=tech&key=1086272325&rc=918#r917
ここの METHOD 3 と同じかな
>>918 のページの方は配列の要素が遷移する様子が解説されていないから、
処理を追うのが面倒でざっとしか見てないが
「珠玉のプログラミング」という本にも
METHOD 3 と同じ [お手玉の方法] として紹介されているらしいね
0920デフォルトの名無しさん
2011/11/08(火) 19:42:11.71http://ecommons.cornell.edu/handle/1813/6292
の中では Dolphin algorithm って書いてあるけど、
そんな名前で呼ばれてもだれもわからんだろうな
0921デフォルトの名無しさん
2011/11/08(火) 19:44:20.42http://www.imminentweb.com/technologies/rotating-algorithms-programming-pearls-jon-bentley
0922デフォルトの名無しさん
2011/11/08(火) 19:58:54.92ありがとうございます。
自分で図を書いて理解した後だと
イルカが連なって飛び跳ねるイメージはしっくり来ますね。
0923デフォルトの名無しさん
2011/11/08(火) 20:02:34.39名前が付いてるということは初めて見た気がする。
0924デフォルトの名無しさん
2011/11/08(火) 20:09:28.83"gcd array rotate" でググったら、一番最初に >>919 のページがヒットして、
9件目にその本に載ってると書かれてたブログがヒットしたのを見ただけ
0925デフォルトの名無しさん
2011/11/08(火) 20:20:34.120926918
2011/11/08(火) 20:40:16.46http://www.geeksforgeeks.org/archives/2398
の事だったんですね。 キーワードが分かったのでたどり着けました。
0927デフォルトの名無しさん
2011/11/08(火) 21:08:53.87あるいは全体の位置が移動してもいいとか。エレガントな手法として悪くないと思うけど。
0928デフォルトの名無しさん
2011/11/08(火) 22:37:53.23スマン、指摘されるまで全く気づかんかった
貼るURLを間違えてた
0929デフォルトの名無しさん
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
おそらく細かい実装の違いではカバーしきれないほどの差が出ます。
まあ、この種のアルゴリズムが必要になる前にデータ構造の見直しをしたほうがいいとは思います。
リスト構造なら一部の配線付け替えで一瞬です
0930デフォルトの名無しさん
2011/11/09(水) 19:22:14.990931デフォルトの名無しさん
2011/11/09(水) 20:04:05.29というわけで最適化無しでもやってみました。
$ 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
これで比べるとテンポラリ配列の方法もそれなりに健闘しています。
二回逆転の方法は、おい大丈夫か？レベルです。最適化ってすごいですね
0932デフォルトの名無しさん
2011/11/09(水) 21:51:10.45珠玉のデータはもっとでかい配列までとってたような気が。
> リスト構造なら一部の配線付け替えで一瞬です
目的の場所まで行くのに時間かかるから、結局O(n)だけどね。
0933デフォルトの名無しさん
2011/11/09(水) 21:53:47.81> アルゴリズムの性能評価をするときに、コンパイラの最適化を有効にするのって無しでしょ？
なんで？ありでしょ。
どれもO(n)だ、結局どれが速いのってときに、
最適化しなかったらコーディングの差を見てるだけになる。
0934デフォルトの名無しさん
2011/11/09(水) 22:12:51.33その前にもっとやっておくことがある
同じ O(n) でも n を何で測るかをちゃんと揃えないといけない
例えば一方のアルゴリズムはステップ数で測って、
他方のアルゴリズムはステップ数にメモリアクセスの数も含めて測る
なんてやってはいけない
その上でまだ同じ O(n) なら、今度はオーダーを計算する為に省いた係数を
低次元のものまでちゃんと補ってより細かく比較しないといけない
コンパイラの最適化に頼って処理速度によるアルゴリズムの優劣を比較するのは
少なくともその後にすべきで、同じ O(n) だからといって安易にすべきではない
それでも、その最適化による比較で分かるのはアルゴリズムの質的な優劣ではなく、
単にそのコンパイラや表現する言語と「相性が良いかどうか」でしかないと思う
0935デフォルトの名無しさん
2011/11/09(水) 22:17:14.400936931
2011/11/09(水) 22:30:20.090937デフォルトの名無しさん
2011/11/09(水) 22:34:33.71最適化なしに測定なんかできん。
0938931
2011/11/09(水) 22:35:58.31>目的の場所まで行くのに時間かかるから、結局O(n)だけどね。
例にあげたようなノードオブジェクトが大きい場合
リンクを辿るのに要するコスト ＜ ノードコピーに要するコスト
になりますよね。
>>934 の言う
オーダーを計算するための係数の違いという事になると思います。
0939デフォルトの名無しさん
2011/11/09(水) 22:41:21.64そうであるなら、その比較検証に使用したマシンの
キャッシュ性能や特性もちゃんと細かく公表しないとけないね
（細かくと言うのは、処理速度の計測に影響が出る範囲でという意味）
でなければ、追試や他環境との比較ができない
0940デフォルトの名無しさん
2011/11/09(水) 22:53:01.18だからこそatlasなんかビルド時にベンチマークしてチューンしまくる。
0941デフォルトの名無しさん
2011/11/09(水) 22:53:21.320942デフォルトの名無しさん
2011/11/10(木) 12:09:55.94BLASが何年生き残ってると思ってるんだwwww
新しいハードウェアができたらそれに合わせてパラメータをチューニングするんだよ
0943デフォルトの名無しさん
2011/11/10(木) 13:38:08.420944デフォルトの名無しさん
2011/11/10(木) 14:43:19.120945デフォルトの名無しさん
2011/11/10(木) 14:54:42.970946デフォルトの名無しさん
2011/11/10(木) 14:57:53.230947デフォルトの名無しさん
2011/11/10(木) 17:56:42.11それは場合によるので一般的な基準はないでしょうね。
0948デフォルトの名無しさん
2011/11/11(金) 09:21:28.970949デフォルトの名無しさん
2011/11/11(金) 19:47:40.37移動については、ワードよりでかい物のソートの時はポインタ使うのが普通
0950デフォルトの名無しさん
2011/11/11(金) 22:49:55.98値の大小判定の回数を使うのが普通
0951デフォルトの名無しさん
2011/11/11(金) 22:54:18.350952デフォルトの名無しさん
2011/11/12(土) 12:37:01.030953デフォルトの名無しさん
2011/12/03(土) 21:14:05.30ちなみに入力はゼロ終端のASCII文字列で出力はintです
0954デフォルトの名無しさん
2011/12/03(土) 21:16:27.860955デフォルトの名無しさん
2011/12/03(土) 21:21:41.411文字ごとにあらかじめ用意したテーブルから文字に対応する乱数を持ってきてXORしていく
そこそこ軽くてばらつきはいいよ
0956デフォルトの名無しさん
2011/12/03(土) 22:35:28.70良い感じですね
ありがとうございます
0957デフォルトの名無しさん
2011/12/04(日) 01:46:10.28矩形領域内を差した時にどの矩形領域内を差したかを
効率よく判定する方法がありましたら教えてください
0958デフォルトの名無しさん
2011/12/04(日) 01:48:54.810959デフォルトの名無しさん
2011/12/04(日) 01:54:28.80矩形をx方向にソートしてｘ方向で二分探索して候補を絞る
絞った候補をy方向にソートしてy方向で二分探索して確定
0960デフォルトの名無しさん
2011/12/04(日) 03:29:35.090961デフォルトの名無しさん
2011/12/04(日) 03:51:15.50まあ例えばいくつかの領域に区切り
それぞれの領域と重なるオブジェクトを登録しておくとか…
0962デフォルトの名無しさん
2011/12/04(日) 04:22:36.90重ならなくてもR-Treeでいいかも
まぁ、簡単な >>959 を試してからでいいね
0963デフォルトの名無しさん
2011/12/04(日) 07:25:04.860964デフォルトの名無しさん
2011/12/04(日) 09:20:04.631つの点対無数の矩形なのか
無数の点対無数の矩形なのか
何回ぐらい判定するのか
複数回判定するとして矩形の座標は頻繁に更新されるのか固定なのか
このへんの情報で変わってくるよね
点1つ、判定一回なら全探索が最速だし
そうでないなら空間分割が速い
0965デフォルトの名無しさん
2011/12/04(日) 12:52:40.84いろいろヒントが得られる
0966デフォルトの名無しさん
2011/12/04(日) 12:54:24.91間違えちゃった
「コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用」 でした
0967デフォルトの名無しさん
2011/12/23(金) 15:08:59.610968デフォルトの名無しさん
2011/12/23(金) 15:40:59.57激しくおすすめできないが。
0969デフォルトの名無しさん
2011/12/23(金) 15:59:05.770970デフォルトの名無しさん
2011/12/23(金) 17:28:00.43すいませんググったけどわかりませんでした
>>969
pre-orderを考えてます
0971デフォルトの名無しさん
2011/12/24(土) 09:59:11.160972デフォルトの名無しさん
2011/12/26(月) 19:38:15.54持ってるのならそれほど難しい問題ではないけども・・・。
0973デフォルトの名無しさん
2011/12/26(月) 20:28:32.100974デフォルトの名無しさん
2011/12/27(火) 09:01:44.930975デフォルトの名無しさん
2011/12/27(火) 12:35:05.74他の情報も合わせて詳しく載ってる
0976デフォルトの名無しさん
2011/12/27(火) 17:38:21.78例えば10色欲しいとしたら、10個のテーブルで、各色の色差が最もあるテーブルを作りたい。
単色グラデーションなら簡単だけどRGB織り交ぜた最大の色差を出すのが難しい。
0977デフォルトの名無しさん
2011/12/27(火) 17:54:40.80それぞれの距離の平均が最大となるn個の点の座標を求める問題と同じ？
特定の３次元空間の領域内というのがRGB色空間やHSV色空間になるわけだけど
0978デフォルトの名無しさん
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回ぐらい繰り返す
問題の性質が良ければ、適当な答えに収束するかも
0979デフォルトの名無しさん
2011/12/28(水) 07:20:57.68色空間の中心にぎゅっと押し込めてから緊張を解くことをシミュレートしてみるとか
やったこと無いから、実際にどうなるかは知らんが
0980デフォルトの名無しさん
2011/12/28(水) 08:21:41.060981デフォルトの名無しさん
2011/12/28(水) 19:20:40.870982デフォルトの名無しさん
2011/12/28(水) 19:25:49.87証明しろよ
0983デフォルトの名無しさん
2011/12/29(木) 10:19:39.29６角形の一辺の２色と、一つ飛びの２色との間にある色は
一辺の色差より大きい
だめだ論破
８色だと、立方体の頂点でいいんだよな。たぶん。
0984デフォルトの名無しさん
2011/12/29(木) 14:20:05.95全ての点間で距離を最大化できても見づらい色同士が出てくる
0985デフォルトの名無しさん
2011/12/29(木) 21:05:13.740986デフォルトの名無しさん
2011/12/29(木) 21:15:13.49> 全ての点間で距離を最大化できても見づらい色同士が出てくる
かどうかは、やってみなくちゃ分からんと思うが
そもそも、距離を最大化する配置が分かってないのに言えんだろ
レス数が950を超えています。1000を超えると書き込みができなくなります。