計算アルゴリズム【Ⅱ】

計算アルゴリズム【Ⅱ ..

331:デフォルトの名無しさん
06/04/18 07:42:35
いわゆる○×。ただし、ちょっと特殊。
ban(0) ban(1) ban(2)
ban(3) ban(4) ban(5)
ban(6) ban(7) ban(8) //盤面　位置関係はこんな感じ
turn //ターン数　最初は1

プレイヤーＡのターン開始
↓
Ａが指定しかつその場所に当たる変数（真ん中ならban(4)）が0であるならばそれに（turn×１０）＋プレイヤーの番号
（Ａは１、Ｂは２とする。）を代入。
↓
turn>6ならば、次のことを行う。
　banの中で下１桁がプレイヤーの番号と等しいもののなかで、一番小さいものに0を代入
↓
banに縦横斜めに自分の番号が並んでいるならば勝利
↓
turnに１を足し、Ａのターンを終了、Ｂのターンになる。

で、できるだけ強いCOMのアルゴリズムを考えてほしいのです。
お願いします。

332:デフォルトの名無しさん
06/04/18 13:54:18
あぶらあげ

333:デフォルトの名無しさん
06/04/22 16:23:12
>>331
ゲーム木使って実際に解いてみたら。
EXPTIME完全か知らんが、3×3ぐらいなら解けるだろ。
終盤6個そろってからの場合の数は
9*8*7*6*5*4 = 60480
回転と対称で重なるものを除くと
60480/8 = 7560
リーチがかかってかつ自分の手番のような自明な場面を除けばもっと少なくなる。
自分の手番でダブルリーチをかけられる状態であれば勝ち。
双方最善を尽くしたとき、ループに陥れば引き分け。

334:デフォルトの名無しさん
06/04/22 17:08:22
消してから勝利判定だとダブルリーチにならないんじゃない？

335:デフォルトの名無しさん
06/05/22 17:26:54
楕円近似ライブラリなんてありまつか？

336:デフォルトの名無しさん
06/05/22 17:37:12
楕円近似というのは　

１、点列を楕円の一部として近似する事

２、楕円の周長を近似計算する事

どっち？１はとても難しい　円ならまだ方法があるが

337:デフォルトの名無しさん
06/05/22 17:56:27
＞１、点列を楕円の一部として近似する事

これをやりたいです。

338:デフォルトの名無しさん
06/05/22 18:20:03
円なら　
URLﾘﾝｸ(www.tensyo.com)
ここの円弧推定が良い方法だと思える。

普通は、円との誤差を　ｓ＝√｛（ｘ－ｘ0）^2 ＋（ｙ－ｙ0）^2｝－ｒ　と置くが
これだと非線形で解かなければならない。

（ｘ－ｘ0）^2 ＋（ｙ－ｙ0）^2－r^2 とすれば数値解が簡単に求まるというものだ。

楕円の場合は、検索すれば出ると思うが、円よりさらに厄介だ

339:AVL木
06/05/22 20:52:10
18,7,35,13,16,10,40,21,22,50,46,3,5　　を
からっぽのAVL木に入れていくとどうなりますか？誰か教えてください。

340:デフォルトの名無しさん
06/05/22 21:41:44
教科書読め

341:デフォルトの名無しさん
06/05/25 18:54:44
繰り返し二乗法のプログラムをご教授お願い出来ますでしょうか？

342:デフォルトの名無しさん
06/05/25 20:20:09
デジタル回路の閾値関数を考えたのですが、既知ですか？
f:=x->cos(PI/2*x)^2
f(f(f(x))), x=-0.5..1.5

343:デフォルトの名無しさん
06/05/31 01:36:13
>>335
Direct least-squares fitting of ellipses
Andrew W. Fitzgibbon, Maurizio Pilu, and Robert B. Fisher
IEEE Transactions on Pattern Analysis and Machine Intelligence,
21(5), 476--480, May 1999

URLﾘﾝｸ(research.microsoft.com)
URLﾘﾝｸ(research.microsoft.com)

一応 Java 実装もあるけどコードがちょっと汚いかも。

344:デフォルトの名無しさん
06/07/28 23:01:36
fla板から来ました以下の解答お願いします。

プレーヤの歩いた軌跡が、あらかじめ引いてある直線にどれくらい近いかを数値化するにはどうしたらいいでしょうか？
(x,y)座標を取って計算をすればよいらしいっていうのはなんとなくわかるんですが
具体的にどういった計算をすればいいかご教授願います

ちなみに最小二乗法だと、

＼
／
＼
／

このように蛇行した場合も直線に近似されてしまうのでダメですよね・・・

345:デフォルトの名無しさん
06/07/28 23:26:48
>>344
軌跡が直線に近いってのは、どういうこと?

346:デフォルトの名無しさん
06/07/28 23:37:46
>>344
最小二乗法で相関係数みりゃいいだろ。

347:デフォルトの名無しさん
06/07/29 00:13:17
>344
数値を求めたいんだろう？
最後の行が意味不明だぞ

348:344
06/07/29 00:16:20
>>345
URLﾘﾝｸ(www.uploda.org)
この画像のように、どれだけ直線に近い動きをしたか、ということを
直線との接触時間などからではなく、座標から軌跡と直線との近さを計算したいのです。

>>346
相関係数ですか、調べてみます
ありがとうございます

349:デフォルトの名無しさん
06/07/29 15:15:39
もしかして、344は「軌跡から最小自乗法で直線を求めて、与えられている直線と比較する」とか考えているのだろうか。

「軌跡と与えられた直線の距離の自乗を最小にする」でいいんじゃないの？

350:デフォルトの名無しさん
06/08/10 08:08:24
あらかじめ引いてある直線が X 軸に合うように回転させて
Σ(Yi^2)/N とか
軌跡の2次モーメントとか

351:デフォルトの名無しさん
06/09/15 13:37:19
軌跡に沿って所与の直線との距離を積分すればいいじゃないの。

352:デフォルトの名無しさん
06/09/16 00:36:41
随分とまた遅い進行だな

353:デフォルトの名無しさん
06/10/18 22:34:05
ベクトルを正規化する式は
float x, y, z;//元のベクトル
float vx, vy, vz;//正規化したベクトル
float s;
s=sqrt(x*x+y*y+z*z);
vx=x/s;
vy=y/s;
vz=z/s;

で求まると思いますが、sqrtを使わずに正規化するにはどうすればいいのでしょうか？
どうしても速度が気になります。
自分でも考えてみましたが分かりませんでした。よろしく御願いします。

354:age
06/10/18 22:38:49
age

355:デフォルトの名無しさん
06/10/18 23:04:16
f(u0,v0)=
ΣΣf(uk,vl)C(uk-u0)C(vl-v0)
k l

ここで
C(x)= 1-2|x|^2+|x|^3 (0<|x|<1)
4-8|x|+5|x|^2-|x|^3 (1<|x|<2)
0 (2<|x|)

3次補間法の計算式なのですが，どのようにプログラムで書いたら良いのでしょうか?

356:デフォルトの名無しさん
06/10/19 00:02:01
>>353
>どうしても速度が気になります。
本当に気になる速度なのかどうか、まず実測してみたらどうでしょう。

sqrtを使わなければできないと思いますけど。
本当にsqrtが速度的にネックであれば、高速のsqrtを自前で作るとか。
ただし、精度を犠牲にしてのことですけど。

Newton法でのsqrtの近似の場合、ループは高々20回くらいです。（誤差1.0e-15で）

まずは実測です。

357:デフォルトの名無しさん
06/10/19 00:08:31
脳味噌ぶら～んにでも行って速そうなの探してこいよ。

358:デフォルトの名無しさん
06/10/19 01:37:21
>353
まず環境晒そうや。
CPU、使用言語、必要精度、それらの情報も無しでアドバイスなんて出来ん。

359:デフォルトの名無しさん
06/10/19 10:20:45
>>356
精度にもよるけどせいぜい３－５回ぐらいじゃなかったか？
20回もまわすか。

360:デフォルトの名無しさん
06/10/19 10:52:10
double sqrt(double x) {
double a = 1.0;
double eps = 1.0E-10; /* 精度 */
while (abs(a * a - x) > 1.0E-10) {
a = 0.5 * (a + x / a);
}
return a;
}

361:デフォルトの名無しさん
06/10/19 10:56:57
>>353
URLﾘﾝｸ(www.google.co.jp)

362:デフォルトの名無しさん
06/10/19 12:32:48
>>360
そのコードで３－５回
1.0E-15で9回ってところ
確かに20回もありえるけど、極端な言いぐさは信用されないな。

363:デフォルトの名無しさん
06/10/19 13:16:19
>>360
Intel系ならニュートン法使うより、素直に浮動小数点命令を使った方が速いだろ。
SSE乗ってるならaddss/mulss/rsqrtps辺りでまとめて計算できるし。

364:デフォルトの名無しさん
06/10/19 13:44:45
>>355
その計算式のままだと思うけど…
アルゴリズムの入力と出力は理解できてる?
(入力は格子状の標本点における f の値 (二次元の double 配列) と補間すべき点の座標 (u0, v0) で、出力は (u0, v0) における補間値)

365:デフォルトの名無しさん
06/10/19 16:36:19
式は分かってるんですがプログラムにできないんです・・・

366:デフォルトの名無しさん
06/10/19 17:01:18
>>365
具体的なコードが欲しいなら
具体的な入力形式を指定した方がいいと思うよ。
(これは大学の宿題か何かですか?)

367:デフォルトの名無しさん
06/10/19 17:19:03
初心者なもですいません．大学のC言語の画像処理の宿題です．

#include <stdio.h>
#include <rasterfile.h>
#include <math.h>
#include "bitshift.h"

void Disp_Ras(struct rasterfile ras);
void cercle(struct rasterfile ras, unsigned char **r, unsigned char **g, unsigned char **b, int point[2]);
void tri(struct rasterfile ras, unsigned char **r, unsigned char **g, unsigned char **b, int point[2]);
void sq(struct rasterfile ras, unsigned char **r, unsigned char **g, unsigned char **b, int point[2]);
void satr(struct rasterfile ras, unsigned char **r, unsigned char **g, unsigned char **b, int point[2]);

int height;
int width;

int main(int argc,char *argv[]){

/*変数宣言*/
int i=0;
int j=0;
int point[2];
struct rasterfile ras;
unsigned char **R,**G,**B;
unsigned char **r,**g,**b;
FILE *fp1,*fp2;

int nt,nn;
double p,q;
double bai;
int tmp_nt,tump_nn;

368:デフォルトの名無しさん
06/10/19 17:22:41
続き
printf("倍率を入力");
scanf("%lf",&bai);

/* 入力画像 */
if((fp1 = fopen("hane256.ras","rb")) == NULL){
fprintf(stderr,"can't open file!!\none more check it!!\n");
exit(1);}

/* ヘッダ読み込み */
ras.ras_magic = readtoInt(fp1);
ras.ras_width = readtoInt(fp1);
ras.ras_height = readtoInt(fp1);
ras.ras_depth = readtoInt(fp1);
ras.ras_length = readtoInt(fp1);
ras.ras_type = readtoInt(fp1);
ras.ras_maptype = readtoInt(fp1);
ras.ras_maplength = readtoInt(fp1);

369:デフォルトの名無しさん
06/10/19 17:23:35
続き
height =bai*ras.ras_height;
width = bai*ras.ras_width;
height = height - height%4;
width = width - width%4;
/* 出力画像 */
fp2 = fopen("out.ras","wb");

/* ヘッダ書き込み */
writetoInt(fp2,ras.ras_magic);
writetoInt(fp2,width);
writetoInt(fp2,height);
writetoInt(fp2,ras.ras_depth);
writetoInt(fp2,ras.ras_length);
writetoInt(fp2,ras.ras_type);
writetoInt(fp2,ras.ras_maptype);
writetoInt(fp2,ras.ras_maplength);

370:デフォルトの名無しさん
06/10/19 17:24:06
続き
/* メモリ確保 */
R = (unsigned char**)calloc(ras.ras_height,sizeof(unsigned char *));
G = (unsigned char**)calloc(ras.ras_height,sizeof(unsigned char *));
B = (unsigned char**)calloc(ras.ras_height,sizeof(unsigned char *));
r = (unsigned char**)calloc(height,sizeof(unsigned char *));
g = (unsigned char**)calloc(height,sizeof(unsigned char *));
b = (unsigned char**)calloc(height,sizeof(unsigned char *));
for(i=0;i<ras.ras_height;i++){
R[i]=(unsigned char*)calloc(ras.ras_width,sizeof(unsigned char));
G[i]=(unsigned char*)calloc(ras.ras_width,sizeof(unsigned char));
B[i]=(unsigned char*)calloc(ras.ras_width,sizeof(unsigned char));
}
for(i=0;i<height;i++){
r[i]=(unsigned char*)calloc(width,sizeof(unsigned char));
g[i]=(unsigned char*)calloc(width,sizeof(unsigned char));
b[i]=(unsigned char*)calloc(width,sizeof(unsigned char));
}

371:デフォルトの名無しさん
06/10/19 17:24:59
/* 画素データ取り込み */
for(i=0;i<ras.ras_height;i++){
for(j=0;j<ras.ras_width;j++){
/* B → G → R(24bit) */
fread(&B[i][j],sizeof(unsigned char),1,fp1);
fread(&G[i][j],sizeof(unsigned char),1,fp1);
fread(&R[i][j],sizeof(unsigned char),1,fp1);
}
}

/*線形補間法*/
for(i=0;i<height;i++){
for(j=0;j<width;j++){

nt = floor(i/bai);
nn = floor(j/bai);
p = i/bai - nt;
q = j/bai - nn;

r[i][j] = R[(unsigned char)nt][(unsigned char)nn]*(1-p)*(1-q)+R[(unsigned char)(nt+1)][(unsigned char)nn]*p*(1-q)
+R[(unsigned char)nt][(unsigned char)(nn+1)]*(1-p)*q+R[(unsigned char)(nt+1)][(unsigned char)(nn+1)]*p*q;
g[i][j] = G[(unsigned char)nt][(unsigned char)nn]*(1-p)*(1-q)+G[(unsigned char)(nt+1)][(unsigned char)nn]*p*(1-q)
+G[(unsigned char)nt][(unsigned char)(nn+1)]*(1-p)*q+G[(unsigned char)(nt+1)][(unsigned char)(nn+1)]*p*q;
b[i][j] = B[(unsigned char)nt][(unsigned char)nn]*(1-p)*(1-q)+B[(unsigned char)(nt+1)][(unsigned char)nn]*p*(1-q)
+B[(unsigned char)nt][(unsigned char)(nn+1)]*(1-p)*q+B[(unsigned char)(nt+1)][(unsigned char)(nn+1)]*p*q;

}
}

372:デフォルトの名無しさん
06/10/19 17:27:39
この線形ほかんの部分を3次補間にしないといけないのですが・・・

373:デフォルトの名無しさん
06/10/19 17:50:33
宿題スレ池

374:デフォルトの名無しさん
06/10/19 21:39:46
>367-371
・宿題の趣旨を理解していないバカ
・「初心者」と書けばなにをしても許されると思ってるバカ
・構造化出来ないバカ
・ざっと見ただけでもコンパイルが通らないのが解るコードを晒すバカ

久々に悪寒が走るほど汚ぇコード見たわ。

375:デフォルトの名無しさん
06/10/19 22:12:12
初心者をバカにするやつに上級者はいない(^.^)

376:デフォルトの名無しさん
06/10/19 23:37:57
>>374
これ、たぶん宿題出した先生が書いたコードだと思うんだけど、
大学の先生 (特に年配の人) って結構こういうコード書くのよ。
漏れが習った人も FORTRAN が最初だったらしくてこんな感じだった。
理論とかに関してはすごく頭切れるんだけどね…。

377:デフォルトの名無しさん
06/10/20 01:36:50
・糞レスでageるやつは2ch初心者
・携帯のノリで顔文字使ってるやつは2ch初心者

378:デフォルトの名無しさん
06/10/20 10:59:23
>>371
＞nt = floor(i/bai);
キャストしる。

＞R[(unsigned char)nt][(unsigned char)nn]
このキャストは意味あるの？
元画像が縦横どちらか256pixel超えると破綻すると思うけど。
それとも、charが16bitか32bitの処理系？

マジで講師の書いたコードだとしたらヤバイな。
こんなの習った奴が卒業して、新人として入社してくるんか・・・orz

379:デフォルトの名無しさん
06/10/21 13:02:51
>>376
結構いるよね
原理が分かるんだからいいじゃん，
コード読みやすくするのは各自勝手にやってくれとか思ってそう

380:デフォルトの名無しさん
06/10/21 14:37:21
まあ、歳食うと新しいこと覚えられないからねぇ。
FORTRAN のパラダイムのままで C とか Java 書くのなんて当たり前。

381:デフォルトの名無しさん
06/10/21 15:04:24
つまり、年寄りってゴミっていうこと？

382:デフォルトの名無しさん
06/10/21 15:28:34
そこまでは言わんが･･･

383:デフォルトの名無しさん
06/10/21 15:58:18
でも実際この業界では、年寄りは廃棄処分にされるんだよね？

384:デフォルトの名無しさん
06/10/21 16:11:20
>>383
その当時、専門でなかった人材を無理矢理ソフトウェア開発に回した、という背景があるからじゃない？
そういう年寄り連中は基礎的な事を学ばずに、現場たたき上げで今までやってきたけど、そのツケが今に回ってきてる。

385:デフォルトの名無しさん
06/10/21 16:31:02
んじゃ、年寄りが新しいことを覚えられないというのは、基礎的なことを知らないから、新しいことに対処する能力が低いということ？

386:デフォルトの名無しさん
06/10/21 17:07:54
歳食うと新しいこと覚えられないってのは、人間なら誰でも。
普通は、新しいこと出来ないってのを今までの経験からくる勘とかで補うんだけど、
>>384 みたいな背景があるんじゃ、この業界じゃほんとにゴミになりかねんな、年寄り。

387:デフォルトの名無しさん
06/10/21 19:36:38
どの業界でも年取れば、現場から一歩引いて管理職になるが普通じゃないのか？
ただし、ITドカタじゃそれが特別速く押し寄せるってこと。

388:デフォルトの名無しさん
06/10/21 20:05:52
>>387
アメリカでは職種は変わらない。

389:デフォルトの名無しさん
06/10/21 20:48:27
お前はどこで仕事してる？

390:デフォルトの名無しさん
06/10/22 00:03:00
>>387
まあ、だってさ、管理職って多人数は必要ないわけじゃん。
全員が管理職にはなれないだろ。

って、話題がなんかマ板臭いな。

391:デフォルトの名無しさん
06/10/22 00:13:51
【】この業界では何故、年寄りは廃棄されるのか？【】

392:デフォルトの名無しさん
06/10/22 13:56:19
>>390
その話の最後は、「国が必要もない公共工事をいつまでも続けるのはなぜなのか」に落ち着くぞ。

393:デフォルトの名無しさん
06/10/22 22:12:32
ｵﾏｲﾗ赤黒木ってしってる？

394:デフォルトの名無しさん
06/10/22 22:13:44
常識では

395:デフォルトの名無しさん
06/10/22 23:30:04
実装を知ってるのと聴いたことあるのとではまったく違う

396:デフォルトの名無しさん
06/10/22 23:53:11
どのくらい効率いいの？＞red-black tree

小規模のDBなら偏っても問題無いし、大規模DBならいまどきツリー使ってないだろうし。
ターゲットはどこらなん？

397:デフォルトの名無しさん
06/10/23 00:33:08
FEMプログラムで使われてるのは見たことある。

398:デフォルトの名無しさん
06/10/23 00:43:13
>>国が必要も無い公共工事を続ける理由

三下土方に職を与える為
に落ち着くぞ

399:デフォルトの名無しさん
06/10/23 00:45:39
>>人口減ってるから、住宅作らなくてもいいんだよ。
どうせ大半は地震でぶっ壊れるし。

いやいやゼネコンの小遣い稼ぎでしょう。

400:デフォルトの名無しさん
06/10/23 02:05:37
>>393
日本語だと、2色木って言われることの方が多いような、red-black tree。

>>396
要素の挿入・削除時にちょっと処理が増えるけど、
要素の探索時にはペナルティなしで、
木の高さが必ず log n オーダーに抑えられる。

数百～数万程度のデータ扱うときにはすごい効率いいと思うよ。
C++ の map とか C# の SortedDictionary は2色木使ってる。
Java の Hashtable も、名前に反して実装は2色木じゃなかったっけ？

401:デフォルトの名無しさん
06/10/23 16:39:56
2色木は初めて聞いた。俺は赤黒木派。

402:デフォルトの名無しさん
06/10/23 18:36:23
実測結果キボンヌ

403:デフォルトの名無しさん
06/11/17 17:26:34
平面上の凸とは限らないポリゴンを三角形分割したいのですが、どういったアルゴリズムがあるでしょうか？
また、そのポリゴンに穴が開いている場合も対処できるアルゴリズムはありますか？
1週間ほど調べているのですが埒があかなくて。。。

404:デフォルトの名無しさん
06/11/17 18:51:11
穴空きなら、外側とつなぐ。切れ込みを入れる感じで。
凹なら凹部と別の頂点で分割して凸にする。

405:デフォルトの名無しさん
06/11/18 03:15:54
どんな多角形だろうと、単調多角形への分割をした後に
単調多角形の三角形分割をして O(n) で解けることが知られている。

まともな計算幾何の本ならだいたい書いてあるとおもうが。

406:デフォルトの名無しさん
06/11/18 03:21:41
その単調って凸と同じ意味？

407:デフォルトの名無しさん
06/11/18 12:45:18
違う。端点のリストを一番下にある点から巡回したとき
y_1 < y_2 < ... < y_k, y_k > y_{k+1} > y_{k+2} ... > y_n となること。
つーか本嫁。

408:デフォルトの名無しさん
06/11/18 21:06:08
ここにでてくるShare Sortってなに？
ぐぐっても日本語の解説が見つからなかったよ。
とりあえず並列処理用のアルゴリズムらしいのは
わかったけど。

URLﾘﾝｸ(www.cs.rit.edu)

409:403
06/11/19 15:10:28
>>404-407
ありがとうございます。
なんとなくわかりました。
ただ、本屋に行ってみて計算幾何の本をいくつか見てみたのですが、どの本がよいかよくわからなくて...
もしお勧めがあれば教えていただけないでしょうか。すみません。

410:デフォルトの名無しさん
06/11/19 15:57:59
>>408
URLﾘﾝｸ(www.cs.mu.oz.au)
これじゃだめ？
・row columnにわける(row数,column数はプロセッサ数の定数倍に近いほうがよいだろう)
・奇数rowで昇順ソート偶数rowで降順ソートをする
・columnで昇順ソートをする
何回かやってるとできるはずなのでできたら取り出す
なんでrowのソートで逆にする必要があるのかな...

411:デフォルトの名無しさん
06/11/19 19:39:16
>>409
URLﾘﾝｸ(www.amazon.co.jp)
URLﾘﾝｸ(www.amazon.co.jp)

412:デフォルトの名無しさん
06/11/19 20:20:48
>>411
ありがとうございます！
早速買ってこようとおもいます。本当にありがとうございました。

413:デフォルトの名無しさん
06/11/19 20:44:17
shear sort実装してテストしてみたんだが、std::sortに比べて遅い・・・
int型で要素数2^16程度だと何回か繰り返してみたが25倍程度遅く、
2^32程度だと１回のテストで1000倍程度遅かった。
coreが1個だとオーダも悪いね。n個もcoreがあるなら、
quick sortでも順次分けていけるようなきがするし、
メモリを飛び飛びにアクセスして書き換えるから並列処理にも合ってない気がする。

414:デフォルトの名無しさん
06/11/19 21:06:23
O(n log n) を切れるソートって、かなり特殊な前提がないと使えないんじゃないの？
データの数と同じだけプロセッサがあるなら、
バブルソートでも O(n) でしょ、確か。
その Shear ソートも、そういう前提の下で O(√n) とかではないの？

415:デフォルトの名無しさん
06/12/13 12:06:49
「ｍ個の数字集合からｎ(0～ｍ)個の組み合わせを比較し、指定値Ｘ以上かつ最小の組み合わせを求める。」

こういうプログラムを作りたいのですが、どうアルゴリズムを組めばいいのかわかりません。
どなたかお願いします。

例
インプット
　数字集合：5,7,10,12,15
　指定値：18

　↓数字集合の組み合わせで、『指定値』以上かつ最小の組み合わせを求める。

アウトプット
　最小合計値の組み合わせ：7+12=19

416:デフォルトの名無しさん
06/12/13 12:34:57
>>415
アルゴリズムを説明すれば自分でプログラム書けるの？
プログラム書いてほしいとか言うのは宿題スレいってくれ

417:デフォルトの名無しさん
06/12/13 12:50:26
ナップサック問題のバリエーション？

418:415
06/12/13 12:50:50
>>416
アルゴリズムによってはプログラムで書けるか分からないので、宿題スレに行きます。

419:429
06/12/13 13:26:11
415ではないが移動先はっとく
ｽﾚﾘﾝｸ(tech板:22番)

420:デフォルトの名無しさん
06/12/13 14:16:15
>>417
Subset Sum Problem という有名 NP （の、最適化問題版）。
まあバリエーションといえばそうなんだけど、知ってて損はない名前よ。

421:デフォルトの名無しさん
06/12/13 14:37:22
問題から推測すると集合の最大値は指定値をより小さいのかな

422:415
06/12/13 15:15:11
>>419
お手数おかけしました。

>>417 >>420
有名な問題なのですね。
名前自体しらなかったです。

>>421
集合の全合計値より、指定値が小さいという意味ならそうです。

423:デフォルトの名無しさん
07/01/23 17:46:53
sqrt(O(N^2)の処理)の計算量が知りたいのですが
sqrtの計算量わかる人いますか

424:デフォルトの名無しさん
07/01/23 19:59:02
>>423
sqrt( O(N^2) の処理 ) という記号の意味がわからん。処理の平方根って何。
具体的にどんなことをしているかを書いたほうが正しい解が得られると思われる。

425:デフォルトの名無しさん
07/01/24 00:00:12
ひょっとして多倍長計算？
ニュートン法なら一回の反復で桁数２倍

426:426
07/01/24 15:42:39
URLﾘﾝｸ(www.apple.com)
このようなカラーピッカーを作りたいのだけれど、
中心からの位置によってどのようなRGBに変換されるかの式がわかりません。
どうやって計算しているのでしょう？

427:デフォルトの名無しさん
07/01/24 15:46:57
>>426
URLﾘﾝｸ(image-d.isp.jp)
Hが円角度 Sが円半径 Vが隣の垂直ﾊﾞｰ　じゃねーかな？

428:426
07/01/24 15:54:15
>>427
ありがとう、作ってみます

429:デフォルトの名無しさん
07/01/24 16:01:43
>>428
変な色マップになったら　同サイトの HLS変換も試してみてね

430:426
07/01/24 16:58:12
>>429
おかげさまで出来ました。atanの戻り値[-pi/2,pi/2]を[0,360]に変換するのにミスったのと
427さんに紹介してもらったページのFの式が間違っていた（正しくはF = H/60 - I）ので
ちょっとだけ手間取りましたが、無事きれいなカラーサークルになりました。
ありがとうございました。

431:デフォルトの名無しさん
07/01/24 17:14:29
強欲アルゴリズムについて分かる人はいますか？

432:デフォルトの名無しさん
07/01/24 17:32:15
貪欲とかgreedyとかで検索したらどうだろう。

433:デフォルトの名無しさん
07/01/24 17:36:37
それがなくて…

434:デフォルトの名無しさん
07/01/24 19:08:19
俺はだいたいのところは分かっていると思うぜ

435:デフォルトの名無しさん
07/01/24 19:27:16
>>430 atan2使えばいいんじゃね？

436:デフォルトの名無しさん
07/01/26 06:11:36
長さが同じint配列が2個ある。
一つの配列内で重複する数は無い。
同じ数がそれぞれの配列で同じ位置にあるとは限らない。
で、一方の配列内に入ってる数が全て他方の配列にも入っているかを確認したい。
こういう場合で配列をそれぞれソートして
先頭から最後まで一致するかを調べる以外に何かいい方法ある？

437:デフォルトの名無しさん
07/01/26 07:12:23
それは set equality problem という問題で，
O(n log n) が計算量下界であることが知られている．
よって，計算量的には 436 のソート比較は最適．

ハッシュとか確率的アルゴリズムとかで実用的な速度は
上がるかもしれんが，ソート比較が簡素で良いと思うよ．

438:デフォルトの名無しさん
07/01/26 09:06:29
>>437
なるほど。
ありがとう。

439:デフォルトの名無しさん
07/01/26 09:26:09
>438
データの範囲が狭ければ有無の配列(データが添字)を使ってO(n)で可能
データに対して有効なハッシュ関数があれば広くても同上

440:デフォルトの名無しさん
07/01/27 00:38:31
データの個数があんまり多くないからソート比較でも十分速くできた。
>>439
>>437でハッシュと聞いてピンと来た。
機会があれば今度その方法も試してみるよ。
ありがとう。

441:デフォルトの名無しさん
07/02/02 14:13:28
有無なら配列じゃなくてビットマップにしろや

442:デフォルトの名無しさん
07/02/04 11:48:52
>441
もしかして：ビットの［配列］

443:デフォルトの名無しさん
07/02/04 14:05:22
>>441
アルゴリズムと実装は区別しような
分からなかったらスレッド名も見てくれ

444:デフォルトの名無しさん
07/02/04 23:26:47
>>443
言葉遊びがしたいのか？
アルゴリズムと実装でいうならどう実装をしようが配列は配列
最適化の話がしたいならアセンブラスレでも逝け

445:デフォルトの名無しさん
07/02/05 00:44:54
>>444
444=441 ?

とりあえず君の配列の定義が知りたい。

アルゴリズム論の文脈では、実装における配列と理論における
配列はまったく対応しない可能性があるけど、それは大丈夫？

446:デフォルトの名無しさん
07/02/05 10:54:45
え～い面倒くせえ
ビットマップ＝ビットの配列
でFAだろ

447:デフォルトの名無しさん
07/02/05 12:10:45
まぁ、普通そんなこと言わんがな。

448:デフォルトの名無しさん
07/02/08 15:47:29
ある会計（０円～９９９円）を行う際に
一回の硬貨のやり取り（渡す枚数+受け取る枚数）を最小にするアルゴリズム

考えているんだけど思いつかない・・・助けてくれ

449:デフォルトの名無しさん
07/02/08 16:32:47
void minimumExchange(int account) {
　　int pay = account;
　　int min = getCount(account);
　　for (int i = account + 1; i < 1000; i++) {
　　　　int c = getCount(i) + getCount(i - account);
　　　　if (c < min) {
　　　　　　pay = i;
　　　　　　min = c;
　　　　}
　　}

　　System.out.println("account=" + account + " pay=" + pay + " min=" + min);
}

int getCount(int n) {
　　int c = n/500;
　　n %= 500;
　　c += n/100;
　　n %= 100;
　　c += n/50;
　　n %= 50;
　　c += n/10;
　　n %= 10;
　　c += n/5;
　　n %= 5;
　　return c + n;
}

450:デフォルトの名無しさん
07/02/08 17:16:55
ちょっと修正

＞　　for (int i = account + 1; i < 1000; i++) {
を
　　for (int i = account + 1; i <= 10000; i++) {

＞int getCount(int n) {
を
int getCount(int n) {
　　n %= 1000;

アルゴリズムを考える時はまず、最も分かりやすい方法（しらみつぶしとか）を考えるといいと思います。
それでダメならそれから工夫する事を考えればいいのですが、大抵はそのままでも大丈夫です。

＃「硬貨のやり取りが最小」とは別に紙幣を払ってもいいのですね。

451:デフォルトの名無しさん
07/02/09 22:24:47
1円札から999円札まで1円単位の紙幣を使ってもいいんですよね
特に条件が指定されてないので

452:デフォルトの名無しさん
07/02/09 22:28:43
999円札なんて無いだろ
常識で考えれ
1円札を999枚使うんだ

453:デフォルトの名無しさん
07/02/10 08:59:48
>>452
>1円札を999枚使うんだ

現在有効なお金
URLﾘﾝｸ(www.boj.or.jp)

一円券は今でも有効だから使用は違法ではないし
常識で考えて不可能というわけではないな。
つまり「現在発行されている」という条件がない限り、
硬貨のやり取りは常に0が最小というわけだ。

一本取られたな。

454:デフォルトの名無しさん
07/02/10 14:08:01
でも一円札とかって１円より価値あるよな

455:デフォルトの名無しさん
07/02/10 14:24:42
貨幣として使う分には１円だ。

456:デフォルトの名無しさん
07/02/10 14:26:34
そこでコイン商やオクだな

457:デフォルトの名無しさん
07/02/10 15:35:02
買いたい人が*いれば*ね。
はっきり言わせてもらうと、一円札程度なら、札束で無いと誰も買わないよ。

458:デフォルトの名無しさん
07/02/12 20:53:26
金融恐慌時の裏面がすってないお札なんかは高かったりするのだろうか

459:デフォルトの名無しさん
07/02/12 22:02:58
刷られた数
使用された期間
現存数
等は少なければ少ないほど良い

どんなにいらなそうな物でもコレクターにとっては価値がある

460:デフォルトの名無しさん
07/02/13 03:28:54
そういえばうちの親父が記念硬貨とか集めてたな。
天皇陛下御在位６０年1万円硬貨とか。

461:デフォルトの名無しさん
07/02/13 10:21:21
売りたい人は山のようにいるから。

462:デフォルトの名無しさん
07/03/03 14:04:36
質問よろしいですか。

２次元空間上に重複して平面が沢山（簡単のため長方形で）ありました。
ある点を選んだとき、その位置を含む平面の集合が欲しいのですが、
どんなアルゴリズムがいいでしょう？

よくある問題っぽいですね、もし問題に名前がついてたら、それだけでも
教えていただけると助かります。

463:デフォルトの名無しさん
07/03/03 15:16:32
ん？

たとえばＡ４用紙の束かなんかを床に撒き散らしてから、ピンを一本床に突き刺す。
ピンが刺さっている紙を全部調べよう

って問題？

464:デフォルトの名無しさん
07/03/03 17:58:17
>>463
ピンを横に置くんじゃないの？

465:デフォルトの名無しさん
07/03/04 09:59:17
長方形と点のコリジョンだね。元データをグリッドに分割しておくのが
普通かな？２次元だと正方形や可変サイズのグリッドとか
ツリー状（検索を対数的なオーダーに減らす）にしておくとかいろいろ種類はあるよ。

466:デフォルトの名無しさん
07/03/04 10:41:11
重複していない空間の分割なら、もっと簡単なのだから
平面を全部領域別けして、その領域にリンクリストで平面を割り付けるのが簡単じゃないのかな

467:デフォルトの名無しさん
07/03/04 11:15:36
六十周年金貨はあったけど
五十周年金貨ってなかったよね？

468:462
07/03/04 18:16:51
そうです、紙をピン止めみたいな奴です。

3次元に拡張するために、かなりの広さで使うため、グリッドにするのは無理なもので、木にできると嬉しいです。

実装は難しくてもかまいません。

469:デフォルトの名無しさん
07/03/04 19:08:06
長方形は固定で点がいろいろ与えられるって考えていいのかな
今適当に考えただけだけど
最初に排他的な長方形の集合を探してR1とする
(多い方がいいけど最大独立点集合問題はNP困難なので適当でいい）
R1に含まれてない長方形の中から排他的な集合を探してR2とする。
これを再帰的に繰り返す。
点が与えられたらR1から順番にどの長方形に入ってるか調べればいい。

全部の長方形が重なってたらそれぞれ1つの要素からなる集合になるから
結局全部チェックしなきゃいけなくなってしまうのでダメ。
もっといい方法があるのかもしれん。

470:デフォルトの名無しさん
07/03/04 19:10:09
空間を超平面で切って平面集合を2つに分ける。
両方に属する平面があってもよいが、できるだけ2分するような超平面を選ぶ。
探索は点がどちらの超空間に属するかを調べて属するほうの平面集合を総当りで調べる。
これで全部の平面を総当りよりおよそ1/2の計算量になる。
あとはこれを再帰で最終的に完全二分木に近い形で分割できればOK。

471:462
07/03/05 01:18:32
空間を超平面で切るってのは、いわゆるBSP木みたいなもんですよね。

その場合平面が両方の空間に属すると、両方の枝に平面を登録することになるわけで。
例えば一番最後に全部を覆う大きさの平面が入ってきたら、その平面を分割しまくら
なくちゃいけなかったり、データ量が問題になるかな、というのが現在の悩みです。

472:デフォルトの名無しさん
07/03/05 03:30:57
閾値より大きな領域は、別段そのツリー内に入れなければいいのでは？
単一の構造にする必要性も無いし、BSPは静的なものだけにすればいいし。

473:デフォルトの名無しさん
07/03/05 20:42:16
空間を平面で切るときに
・一方の空間に完全に属する領域の集合（２つ）
・断面と交わる領域の集合
の３つに分けてみるのはどうか．こうすれば各領域は必ず一箇所に属する．

探索するときは，断面上の領域と点の落ちる空間内の領域の２つを調べる．

断面と交わる領域の格納は
数が少ないとき（多分，n < (log(n))^d'（d'は断面の次元）のとき）は単純なリスト
数が多いときは１つ次元を落とした同様の構造にする

よくわからないけど最終的には
(log(n))^d （dは次元）←適当
あたりになりそうな気がする．

474:デフォルトの名無しさん
07/03/05 21:19:27
>470-471 >473
なぜ一般次元に拡張を…
応用が利くのは良いっちゃあ良いんだけど微妙

475:462
07/03/06 01:07:58
>>472
大きいというか、重複が多い場合に結構問題になるんです。
今回は空間全ての領域で少なくとも３枚は被さっているのを想定してるんで、
必要な記憶領域がかなり大きくなってしまうという。

>>473
あ、そうか、２つとも探索すればいいんですね。
１次元で紙に書いてみたら、いけそうな感じです。
記憶領域はO(n)ですね、計算量もちょい大き目のlog(n)っぽい。
よーし、明日の夜にでも組んでみます。

476:デフォルトの名無しさん
07/03/06 20:33:21
こーいうのって全くの別人が同時期に同じ解法を求める事ってないよな。

特定(ry

477:デフォルトの名無しさん
07/03/06 21:20:05
空間を分けるってちゃんと図形の配置を考えてやるの?
そうじゃないならどこかで打ちきるわけだから計算量は何分の一かになるだけ
それに重なってるところは分割できないので結局全探索になる

478:462
07/03/07 00:33:13
473氏の方法をちょっと変えた物で、無事実装完了しました。今のところい
い感じに動いています。ありがとうございました。

479:デフォルトの名無しさん
07/03/07 23:42:48

高卒でしかも数II？とか勉強いたことない俺にはまったく理解できないんだが
どうすりゃいい？

480:デフォルトの名無しさん
07/03/07 23:44:26
絵を描いてみる
諦める

481:デフォルトの名無しさん
07/03/08 00:10:43
>>479
余り気付かれていないが、高校生ではなくても高校レベルの数学を
勉強することはできる。

482:デフォルトの名無しさん
07/03/08 07:00:17
>>477
おまえ他人の言ってる事理解してないよ
でしゃばるなカス

483:デフォルトの名無しさん
07/03/09 00:58:56
>>482
理解できてないといって理由を書かない

484:デフォルトの名無しさん
07/03/10 23:39:52
自然科学なんかだと、実測データをグラフにプロットしたあと、なめらかな曲線でつないだりしますが、
そういう曲線を計算するアルゴリズムはありますか？

485:デフォルトの名無しさん
07/03/10 23:47:55
つ[Excel]
一般的なところで、一次回帰とその応用である対数回帰指数回帰冪乗回帰、それと二次回帰程度知ってればなんとでもなる。

486:484
07/03/10 23:49:18
ググってたらcurve fittingと呼ばれている問題だと分かりました。
すれを汚してすいませんでした。

487:デフォルトの名無しさん
07/03/10 23:50:07
>>485
キーワードありがとうございます。
調べてみます。

488:デフォルトの名無しさん
07/03/11 02:21:41
最小二乗法とかね

489:51
07/04/15 21:22:27
SHA-1のハッシュを求めるプログラムを作ろうと調べていて
URLﾘﾝｸ(homepage2.nifty.com)
のサイトを見ていたのですが、

他に参考になるサイトはありませんか？

490:デフォルトの名無しさん
07/04/15 21:54:51
Wikipedia(EN)

491:デフォルトの名無しさん
07/04/24 04:03:28
計算アルゴリズムには限界があり、結局は全部探索したほうが良いって結論？

492:デフォルトの名無しさん
07/04/26 00:56:22
そーでもないと思う。問題が大規模な場合はアルゴリズム使わないと無理だね。
でも、ノイズなんかの問題で理論的に最適な解が微妙な場合だったり、
問題が小規模で全探索で十分満足できる結果が得られるなら、全探索が
安定してるし実装が楽だからいいね。木構造はメモリリークよくやっち
ゃうし。

493:デフォルトの名無しさん
07/04/26 01:28:59
２４シーズンⅤで解析に、独自のアルゴリズムを使って出す、とか言ってた。

494:デフォルトの名無しさん
07/04/26 05:30:17
OR

495:デフォルトの名無しさん
07/05/01 21:40:37
今日専門の方でアルゴリズムの授業が行われたんですがその際この3問だけどうしてもわかりません
何方かこの3問のフローチャートがかける方が居ましたら教えてください
1問目：成績判定１
アルゴリズムの点数を入力して、80点以上のとき「Ａ」、60点以上80点未満の時「B」、60点未満の時「Ｃ」
と出力するフローを答えなさい

2問目：成績判定２
英語と数学と国語の点数を入力して英語の点数が80点以上、または数学と国語の点数がどちらも80点以上の時、「合格」と出力し、そうでない時「不合格」と出力するフローを答えなさい。
なお、数学と国語の点数がどちらも80点以上の時を一つの選択処理にすること

3問目：成績判定3
2-12.成績判定2の選択処理の部分を一つにまとめなさい
選択処理部分
英語の点数が80以上、または数学と国語の点数がどちらも80点以上の時、「合格」と出力し、そうでない時「不合格」と出力する

496:デフォルトの名無しさん
07/05/01 21:50:36
アルゴリズムじゃない。

そんくらいのフローチャートは基礎中の基礎だろ。本見ればわかるだろ。

497:デフォルトの名無しさん
07/05/01 22:19:41
それが問題集しかもらってなくてわからないんですよ

498:デフォルトの名無しさん
07/05/01 22:34:38
>>495
URLﾘﾝｸ(www.cs.takushoku-u.ac.jp)
これみりゃ大体わかるだろ。
いまどきフローチャートを書かせる問題ってのも、どうかと思うけれど。

スレ違いsage

499:デフォルトの名無しさん
07/05/03 14:45:41
問題集しかもらってなくてわからないとか言うんだったら、
2chで質問する前にググれよ。っていうか授業ちゃんと聞いた上で
わからないのであったら講師や友達に聞け。

500:デフォルトの名無しさん
07/05/03 19:47:24
ぐぐれる香具師
友達いる香具師

は

2chで質問しない

501:デフォルトの名無しさん
07/05/04 00:08:57
友達の作り方を教える本でも買った方がいいと思う。

502:デフォルトの名無しさん
07/05/04 18:07:54
おとうさんはネットで調べても作れなかったけど

503:デフォルトの名無しさん
07/05/09 01:56:23
グラフ探索でダイクストラやA*より良いのない？

それはそうとA*探索はぐぐるのが難しい。

504:デフォルトの名無しさん
07/05/09 10:12:59
>>503
「Astar探索」とかでググってみたら？
ちなみにA*の場合、heuristicsがadmissible（各ノードから目的地までの予測コストが実際のコストを決して上回らない）でconsistent（いわゆる三角不等式が成立）なら、必ず最適解を返すよ。
それよりも良いってのは、heuristicsを設計できない場合ってこと？

505:デフォルトの名無しさん
07/05/10 07:32:41
どんな探索かわからんし、「良いの」って意味もわからんなあ。

506:sage
07/05/11 04:14:25
>>504
そうですね、良いヒューリスティックを設計できない時です。
近似解法含め、良いのを探してます。

>>505
たしかに「良い」ってのはアバウトでした＾＾；
主観的にでも、よさげなアルゴリズムがないかなぁと。
検索してもダイクストラばっかり引っかかるもので。

507:デフォルトの名無しさん
07/05/11 04:15:48
すみません、間違えて名前欄に書いてしまいました・・・

508:デフォルトの名無しさん
07/05/13 10:47:07
最短路探索ってことでいいの？

だとしたら、厳密最短路はたぶん理論的には Dijkstra が最良で、
実用的にはヒューリスティックに頼るってのが現在の理解だと思う。
（現在行われてるコンテストでもそんな調子だよね）

近似最短路はヒープ操作を手抜いたり、三角不等式を気にせずに
ヒューリスティックを突っ込んだりするくらいだけど、
グラフが何の性質も持たない場合は性能評価が難しいところ。

509:デフォルトの名無しさん
07/05/13 16:40:43
ヒルス達がやってる６４個のソート問題ってどんな問題？

510:デフォルトの名無しさん
07/05/13 16:44:37
クイックソート問題

511:503
07/05/13 18:40:21
つまりのところ、厳密解を求めるなら、あまり良くないヒューリスティック
を用意した時、A*（と色々な改良版）が最速ってことですか。
というか、授業で習ったダイクストラとA*しか知らない物で＾＾；

近似についても、微妙な改良版くらいしかないって事ですね。

512:デフォルトの名無しさん
07/05/13 19:42:30
>>511
とにかく実行速度をなんとかしたいという実用的な要求なら、
問題にあったヒューリスティックとヒープを設計して A* が
たぶんもっとも現実的だと思う。

近似は、微妙な改良版といっても、たとえば幾何グラフとかなら
普通の Dijkstra と比較して一億倍以上早くなるケースもザラなので、
具体的な問題を見ないとなんともいえないところ。

513:503
07/05/15 01:35:21
ありがとうございます。じゃヒューリスティックに精を出してみることに
します。ちなみに問題は経路探索です。

514:デフォルトの名無しさん
07/05/15 22:13:04
>513
ちなみに、カーナビの経路探索だと、ネットワーク側の方を階層的にいくつか持って切り替えることによって高速化してる。
現在地、目的地近辺では全道路のネットワークで探索、それで見つからなければ国道以上のネットワークに移って探索、
さらに探索する場合は高速道路のみのネットワークに移って探索、みたいな感じ。
もちろん最適解は出ないけど、そもそもカーナビの場合、計算で出てくる最適解が、ドライバーにとって最適になるとも限らないしね。

515:503
07/05/15 23:00:45
あぁ、なるほど、中距離の探索とかで、たまにすごくアホな間違いをするの
はそれが理由なんだ。

516:デフォルトの名無しさん
07/05/16 01:49:50
いや
渋滞回避してるだけだろう

517:デフォルトの名無しさん
07/05/29 07:24:16
ｽﾚﾘﾝｸ(jisaku板)
上記スレで強制NaNの計算でインテル不利にするベンチが論争を呼んでますが
極端にAMD不利にする方法を探しています。
では。

518:デフォルトの名無しさん
07/07/10 16:03:47
多倍長演算の割り算のアルゴリズムで
たとえば521を21で割るとき
↓
まず521が三桁で20が二桁だから答えも二桁だろう
↓
２桁目を決めよう
↓
答えは10かな？21*10＝210で521より小さい
↓
じゃ20かな？21*20＝420＜521
↓
じゃ30かな？21*30＝630＞521（もし90でも超えなければ二桁目は9にする）
↓
大きくなったからおそらく答えの2桁目は2だろう
↓
次は１桁目・・・

こんなのを考えたのですが、もっと良い方法はないですか？

519:デフォルトの名無しさん
07/07/10 16:04:24
age

520:デフォルトの名無しさん
07/07/10 17:02:29
何このマルチレス

521:デフォルトの名無しさん
07/07/10 20:02:17
10,20,30...
だったら時間掛かるだろ

522:デフォルトの名無しさん
07/07/10 21:23:37
自分で考える前にまず一般にどういう方法が使われているかを知れ
せっかく苦労して自分で考えついたとしても
それが既にみんなが普通に使ってるものと同じやそれ以下だったら悲しいだろ？

523:デフォルトの名無しさん
07/08/15 23:41:39
URLﾘﾝｸ(ss.nkk.affrc.go.jp)
に記述されている、
図４の(a)から(b)の結果はどのようなアルゴリズムになりますか？

524:デフォルトの名無しさん
07/08/16 00:12:41
マルチうぜえ

525:デフォルトの名無しさん
07/08/18 19:37:21
ウィキペディアでB木の項を参照すると、
B+木やB*木というものが存在するとに書いてありますが、
どういったものですか？

>（厳密にはB木の改良型であるB+木やB*木を使うことが多い)

526:デフォルトの名無しさん
07/08/18 20:07:24
B+ は B であって、キーを葉にのみ格納するもの
B* は B で、子の比が 1/2 だったところを 2/3 にしたもの

wikipedia の情報は不正確だから参考にすんな
ちゃんとした教科書とか論文を参照すれば分かるだろ

527:デフォルトの名無しさん
07/08/18 22:38:43
>>526
ありがとうございました。
ウィキペディアから引用したら怒らせてしまった様で。
たまたま名前が載ってたから出しただけです。
B+木B*木は名前だけは以前から知ってましたが、
ググっても関係しそうなのは引っかからないですね。
本は
アルゴリズム事典
はじめてのアルゴリズム入門
アルゴリズムとデータ構造
など持ってますが、載ってないみたいです。

>教科書とか論文
できればこれのポインタ教えてください。

528:デフォルトの名無しさん
07/08/18 23:24:10
>>527
誰が怒っているの?

529:デフォルトの名無しさん
07/08/19 03:52:13
>教科書とか論文
できればこれのポインタ教えてください。

530:デフォルトの名無しさん
07/08/19 07:29:10
>>527
B-plus-tree とか B-star-tree で検索すればいくらでも出るんだけどね。

教科書については、そんな一般的なアルゴリズムの本には
あまり出てなくて、データベースよりの本を見ないとダメ。
R. Ramakrishnan, J. Gehrke, "Database Management Systems", 3rdEd. McGlaw-Hill, 2002

まあ次のサーベイ論文がよくまとまってるので、これを読んでおけば十分だろうけど。
D. Comer, "Ubiquitous B-Tree", ACM Computing Surveys, 1979
(URLﾘﾝｸ(www.cl.cam.ac.uk))

次ページ