計算アルゴリズム【�U】

1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ] 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉 >プログラム板の皆さん、こんにちは。 >無謀にもこんなスレを立ててみました。 >四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。 >人間にとって計算しやすい方法についても別途語ることにしましょう。 前スレ↓ pc8.2ch.net/test/read.cgi/tech/1090227743/ 331 名前：デフォルトの名無しさん mailto:sage [2006/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 名前：デフォルトの名無しさん mailto:age [2006/04/18(火) 13:54:18 ] あぶらあげ 333 名前：デフォルトの名無しさん mailto:sage [2006/04/22(土) 16:23:12 ] >>331 ゲーム木使って実際に解いてみたら。 EXPTIME完全か知らんが、3×3ぐらいなら解けるだろ。 終盤6個そろってからの場合の数は 9*8*7*6*5*4 = 60480 回転と対称で重なるものを除くと 60480/8 = 7560 リーチがかかってかつ自分の手番のような自明な場面を除けばもっと少なくなる。 自分の手番でダブルリーチをかけられる状態であれば勝ち。 双方最善を尽くしたとき、ループに陥れば引き分け。 334 名前：デフォルトの名無しさん mailto:sage [2006/04/22(土) 17:08:22 ] 消してから勝利判定だとダブルリーチにならないんじゃない？ 335 名前：デフォルトの名無しさん [2006/05/22(月) 17:26:54 ] 楕円近似ライブラリなんてありまつか？ 336 名前：デフォルトの名無しさん mailto:sage [2006/05/22(月) 17:37:12 ] 楕円近似というのは　 １、点列を楕円の一部として近似する事 ２、楕円の周長を近似計算する事 どっち？１はとても難しい　円ならまだ方法があるが 337 名前：デフォルトの名無しさん [2006/05/22(月) 17:56:27 ] ＞１、点列を楕円の一部として近似する事 これをやりたいです。 338 名前：デフォルトの名無しさん mailto:sage [2006/05/22(月) 18:20:03 ] 円なら　 ttp://www.tensyo.com/urame/prog/linealgo.htm ここの円弧推定が良い方法だと思える。 普通は、円との誤差を　ｓ＝√｛（ｘ−ｘ0）^2 ＋（ｙ−ｙ0）^2｝−ｒ 　と置くが これだと非線形で解かなければならない。 （ｘ−ｘ0）^2 ＋（ｙ−ｙ0）^2−r^2 とすれば数値解が簡単に求まるというものだ。 楕円の場合は、検索すれば出ると思うが、円よりさらに厄介だ 339 名前：AVL木 [2006/05/22(月) 20:52:10 ] 18,7,35,13,16,10,40,21,22,50,46,3,5　　を からっぽのAVL木に入れていくとどうなりますか？誰か教えてください。 340 名前：デフォルトの名無しさん mailto:sage [2006/05/22(月) 21:41:44 ] 教科書読め 341 名前：デフォルトの名無しさん mailto:sage [2006/05/25(木) 18:54:44 ] 繰り返し二乗法のプログラムをご教授お願い出来ますでしょうか？ 342 名前：デフォルトの名無しさん mailto:sage [2006/05/25(木) 20:20:09 ] デジタル回路の閾値関数を考えたのですが、既知ですか？ f:=x->cos(PI/2*x)^2 f(f(f(x))), x=-0.5..1.5 343 名前：デフォルトの名無しさん mailto:sage [2006/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 research.microsoft.com/~awf/ellipse/ research.microsoft.com/~awf/ellipse/ellipse-pami.pdf 一応 Java 実装もあるけどコードがちょっと汚いかも。 344 名前：デフォルトの名無しさん mailto:sage [2006/07/28(金) 23:01:36 ] fla板から来ました以下の解答お願いします。 プレーヤの歩いた軌跡が、あらかじめ引いてある直線にどれくらい近いかを数値化するにはどうしたらいいでしょうか？ (x,y)座標を取って計算をすればよいらしいっていうのはなんとなくわかるんですが 具体的にどういった計算をすればいいかご教授願います ちなみに最小二乗法だと、 ＼ ／ ＼ ／ このように蛇行した場合も直線に近似されてしまうのでダメですよね・・・ 345 名前：デフォルトの名無しさん mailto:sage [2006/07/28(金) 23:26:48 ] >>344 軌跡が直線に近いってのは、どういうこと? 346 名前：デフォルトの名無しさん mailto:sage [2006/07/28(金) 23:37:46 ] >>344 最小二乗法で相関係数みりゃいいだろ。 347 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 00:13:17 ] >344 数値を求めたいんだろう？ 最後の行が意味不明だぞ 348 名前：344 mailto:sage [2006/07/29(土) 00:16:20 ] >>345 www.uploda.org/uporg461782.gif この画像のように、どれだけ直線に近い動きをしたか、ということを 直線との接触時間などからではなく、座標から軌跡と直線との近さを計算したいのです。 >>346 相関係数ですか、調べてみます ありがとうございます 349 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 15:15:39 ] もしかして、344は「軌跡から最小自乗法で直線を求めて、与えられている直線と比較する」とか考えているのだろうか。 「軌跡と与えられた直線の距離の自乗を最小にする」でいいんじゃないの？ 350 名前：デフォルトの名無しさん mailto:sage [2006/08/10(木) 08:08:24 ] あらかじめ引いてある直線が X 軸に合うように回転させて Σ(Yi^2)/N とか 軌跡の2次モーメントとか 351 名前：デフォルトの名無しさん mailto:sage [2006/09/15(金) 13:37:19 ] 軌跡に沿って所与の直線との距離を積分すればいいじゃないの。 352 名前：デフォルトの名無しさん mailto:sage [2006/09/16(土) 00:36:41 ] 随分とまた遅い進行だな 353 名前：デフォルトの名無しさん mailto:sage [2006/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 mailto:age [2006/10/18(水) 22:38:49 ] age 355 名前：デフォルトの名無しさん [2006/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 名前：デフォルトの名無しさん [2006/10/19(木) 00:02:01 ] >>353 >どうしても速度が気になります。 本当に気になる速度なのかどうか、まず実測してみたらどうでしょう。 sqrtを使わなければできないと思いますけど。 本当にsqrtが速度的にネックであれば、高速のsqrtを自前で作るとか。 ただし、精度を犠牲にしてのことですけど。 Newton法でのsqrtの近似の場合、ループは高々20回くらいです。（誤差1.0e-15で） まずは実測です。 357 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 00:08:31 ] 脳味噌ぶら〜んにでも行って速そうなの探してこいよ。 358 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 01:37:21 ] >353 まず環境晒そうや。 CPU、使用言語、必要精度、それらの情報も無しでアドバイスなんて出来ん。 359 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 10:20:45 ] >>356 精度にもよるけどせいぜい３−５回ぐらいじゃなかったか？ 20回もまわすか。 360 名前：デフォルトの名無しさん mailto:sage [2006/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 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 10:56:57 ] >>353 www.google.co.jp/search?q=fast%20sqrt 362 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 12:32:48 ] >>360 そのコードで３−５回 1.0E-15で9回ってところ 確かに20回もありえるけど、極端な言いぐさは信用されないな。 363 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 13:16:19 ] >>360 Intel系ならニュートン法使うより、素直に浮動小数点命令を使った方が速いだろ。 SSE乗ってるならaddss/mulss/rsqrtps辺りでまとめて計算できるし。 364 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 13:44:45 ] >>355 その計算式のままだと思うけど… アルゴリズムの入力と出力は理解できてる? (入力は格子状の標本点における f の値 (二次元の double 配列) と補間すべき点の座標 (u0, v0) で、出力は (u0, v0) における補間値) 365 名前：デフォルトの名無しさん [2006/10/19(木) 16:36:19 ] 式は分かってるんですがプログラムにできないんです・・・ 366 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 17:01:18 ] >>365 具体的なコードが欲しいなら 具体的な入力形式を指定した方がいいと思うよ。 (これは大学の宿題か何かですか?) 367 名前：デフォルトの名無しさん [2006/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 名前：デフォルトの名無しさん [2006/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 名前：デフォルトの名無しさん [2006/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 名前：デフォルトの名無しさん [2006/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 名前：デフォルトの名無しさん [2006/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 名前：デフォルトの名無しさん [2006/10/19(木) 17:27:39 ] この線形ほかんの部分を3次補間にしないといけないのですが・・・ 373 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 17:50:33 ] 宿題スレ池 374 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 21:39:46 ] >367-371 ・宿題の趣旨を理解していないバカ ・「初心者」と書けばなにをしても許されると思ってるバカ ・構造化出来ないバカ ・ざっと見ただけでもコンパイルが通らないのが解るコードを晒すバカ 久々に悪寒が走るほど汚ぇコード見たわ。 375 名前：デフォルトの名無しさん [2006/10/19(木) 22:12:12 ] 初心者をバカにするやつに上級者はいない(^.^) 376 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 23:37:57 ] >>374 これ、たぶん宿題出した先生が書いたコードだと思うんだけど、 大学の先生 (特に年配の人) って結構こういうコード書くのよ。 漏れが習った人も FORTRAN が最初だったらしくてこんな感じだった。 理論とかに関してはすごく頭切れるんだけどね…。 377 名前：デフォルトの名無しさん mailto:sage [2006/10/20(金) 01:36:50 ] ・糞レスでageるやつは2ch初心者 ・携帯のノリで顔文字使ってるやつは2ch初心者 378 名前：デフォルトの名無しさん mailto:sage [2006/10/20(金) 10:59:23 ] >>371 ＞nt = floor(i/bai); キャストしる。 ＞R[(unsigned char)nt][(unsigned char)nn] このキャストは意味あるの？ 元画像が縦横どちらか256pixel超えると破綻すると思うけど。 それとも、charが16bitか32bitの処理系？ マジで講師の書いたコードだとしたらヤバイな。 こんなの習った奴が卒業して、新人として入社してくるんか・・・orz 379 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 13:02:51 ] >>376 結構いるよね 原理が分かるんだからいいじゃん， コード読みやすくするのは各自勝手にやってくれとか思ってそう 380 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 14:37:21 ] まあ、歳食うと新しいこと覚えられないからねぇ。 FORTRAN のパラダイムのままで C とか Java 書くのなんて当たり前。 381 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 15:04:24 ] つまり、年寄りってゴミっていうこと？ 382 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 15:28:34 ] そこまでは言わんが･･･ 383 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 15:58:18 ] でも実際この業界では、年寄りは廃棄処分にされるんだよね？ 384 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 16:11:20 ] >>383 その当時、専門でなかった人材を無理矢理ソフトウェア開発に回した、という背景があるからじゃない？ そういう年寄り連中は基礎的な事を学ばずに、現場たたき上げで今までやってきたけど、そのツケが今に回ってきてる。 385 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 16:31:02 ] んじゃ、年寄りが新しいことを覚えられないというのは、基礎的なことを知らないから、新しいことに対処する能力が低いということ？ 386 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 17:07:54 ] 歳食うと新しいこと覚えられないってのは、人間なら誰でも。 普通は、新しいこと出来ないってのを今までの経験からくる勘とかで補うんだけど、 >>384 みたいな背景があるんじゃ、この業界じゃほんとにゴミになりかねんな、年寄り。 387 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 19:36:38 ] どの業界でも年取れば、現場から一歩引いて管理職になるが普通じゃないのか？ ただし、ITドカタじゃそれが特別速く押し寄せるってこと。 388 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 20:05:52 ] >>387 アメリカでは職種は変わらない。 389 名前：デフォルトの名無しさん mailto:sage [2006/10/21(土) 20:48:27 ] お前はどこで仕事してる？ 390 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 00:03:00 ] >>387 まあ、だってさ、管理職って多人数は必要ないわけじゃん。 全員が管理職にはなれないだろ。 って、話題がなんかマ板臭いな。 391 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 00:13:51 ] 【】この業界では何故、年寄りは廃棄されるのか？【】 392 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 13:56:19 ] >>390 その話の最後は、「国が必要もない公共工事をいつまでも続けるのはなぜなのか」に落ち着くぞ。 393 名前：デフォルトの名無しさん [2006/10/22(日) 22:12:32 ] ｵﾏｲﾗ赤黒木ってしってる？ 394 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 22:13:44 ] 常識では 395 名前：デフォルトの名無しさん [2006/10/22(日) 23:30:04 ] 実装を知ってるのと聴いたことあるのとではまったく違う 396 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 23:53:11 ] どのくらい効率いいの？＞red-black tree 小規模のDBなら偏っても問題無いし、大規模DBならいまどきツリー使ってないだろうし。 ターゲットはどこらなん？ 397 名前：デフォルトの名無しさん [2006/10/23(月) 00:33:08 ] FEMプログラムで使われてるのは見たことある。 398 名前：デフォルトの名無しさん [2006/10/23(月) 00:43:13 ] >>国が必要も無い公共工事を続ける理由 三下土方に職を与える為 に落ち着くぞ 399 名前：デフォルトの名無しさん [2006/10/23(月) 00:45:39 ] >>人口減ってるから、住宅作らなくてもいいんだよ。 どうせ大半は地震でぶっ壊れるし。 いやいやゼネコンの小遣い稼ぎでしょう。 400 名前：デフォルトの名無しさん mailto:sage [2006/10/23(月) 02:05:37 ] >>393 日本語だと、2色木って言われることの方が多いような、red-black tree。 >>396 要素の挿入・削除時にちょっと処理が増えるけど、 要素の探索時にはペナルティなしで、 木の高さが必ず log n オーダーに抑えられる。 数百〜数万程度のデータ扱うときにはすごい効率いいと思うよ。 C++ の map とか C# の SortedDictionary は2色木使ってる。 Java の Hashtable も、名前に反して実装は2色木じゃなかったっけ？ 401 名前：デフォルトの名無しさん mailto:sage [2006/10/23(月) 16:39:56 ] 2色木は初めて聞いた。俺は赤黒木派。 402 名前：デフォルトの名無しさん mailto:sage [2006/10/23(月) 18:36:23 ] 実測結果キボンヌ 403 名前：デフォルトの名無しさん [2006/11/17(金) 17:26:34 ] 平面上の凸とは限らないポリゴンを三角形分割したいのですが、どういったアルゴリズムがあるでしょうか？ また、そのポリゴンに穴が開いている場合も対処できるアルゴリズムはありますか？ 1週間ほど調べているのですが埒があかなくて。。。 404 名前：デフォルトの名無しさん [2006/11/17(金) 18:51:11 ] 穴空きなら、外側とつなぐ。切れ込みを入れる感じで。 凹なら凹部と別の頂点で分割して凸にする。 405 名前：デフォルトの名無しさん mailto:sage [2006/11/18(土) 03:15:54 ] どんな多角形だろうと、単調多角形への分割をした後に 単調多角形の三角形分割をして O(n) で解けることが知られている。 まともな計算幾何の本ならだいたい書いてあるとおもうが。 406 名前：デフォルトの名無しさん mailto:sage [2006/11/18(土) 03:21:41 ] その単調って凸と同じ意味？ 407 名前：デフォルトの名無しさん mailto:sage [2006/11/18(土) 12:45:18 ] 違う。端点のリストを一番下にある点から巡回したとき y_1 < y_2 < ... < y_k, y_k > y_{k+1} > y_{k+2} ... > y_n となること。 つーか本嫁。 408 名前：デフォルトの名無しさん [2006/11/18(土) 21:06:08 ] ここにでてくるShare Sortってなに？ ぐぐっても日本語の解説が見つからなかったよ。 とりあえず並列処理用のアルゴリズムらしいのは わかったけど。 www.cs.rit.edu/~atk/Java/Sorting/sorting.html 409 名前：403 mailto:sage [2006/11/19(日) 15:10:28 ] >>404-407 ありがとうございます。 なんとなくわかりました。 ただ、本屋に行ってみて計算幾何の本をいくつか見てみたのですが、どの本がよいかよくわからなくて... もしお勧めがあれば教えていただけないでしょうか。すみません。 410 名前：デフォルトの名無しさん mailto:sage [2006/11/19(日) 15:57:59 ] >>408 www.cs.mu.oz.au/498/notes/node35.html これじゃだめ？ ・row columnにわける(row数,column数はプロセッサ数の定数倍に近いほうがよいだろう) ・奇数rowで昇順ソート偶数rowで降順ソートをする ・columnで昇順ソートをする 何回かやってるとできるはずなのでできたら取り出す なんでrowのソートで逆にする必要があるのかな... 411 名前：デフォルトの名無しさん mailto:sage [2006/11/19(日) 19:39:16 ] >>409 www.amazon.co.jp/gp/product/476490277X/ www.amazon.co.jp/gp/product/4795263213/ 412 名前：デフォルトの名無しさん mailto:sage [2006/11/19(日) 20:20:48 ] >>411 ありがとうございます！ 早速買ってこようとおもいます。本当にありがとうございました。 413 名前：デフォルトの名無しさん [2006/11/19(日) 20:44:17 ] shear sort実装してテストしてみたんだが、std::sortに比べて遅い・・・ int型で要素数2^16程度だと何回か繰り返してみたが25倍程度遅く、 2^32程度だと１回のテストで1000倍程度遅かった。 coreが1個だとオーダも悪いね。n個もcoreがあるなら、 quick sortでも順次分けていけるようなきがするし、 メモリを飛び飛びにアクセスして書き換えるから並列処理にも合ってない気がする。 414 名前：デフォルトの名無しさん mailto:sage [2006/11/19(日) 21:06:23 ] O(n log n) を切れるソートって、かなり特殊な前提がないと使えないんじゃないの？ データの数と同じだけプロセッサがあるなら、 バブルソートでも O(n) でしょ、確か。 その Shear ソートも、そういう前提の下で O(√n) とかではないの？ 415 名前：デフォルトの名無しさん [2006/12/13(水) 12:06:49 ] 「ｍ個の数字集合からｎ(0〜ｍ)個の組み合わせを比較し、指定値Ｘ以上かつ最小の組み合わせを求める。」 こういうプログラムを作りたいのですが、どうアルゴリズムを組めばいいのかわかりません。 どなたかお願いします。 例 インプット 　数字集合：5,7,10,12,15 　指定値：18 　↓数字集合の組み合わせで、『指定値』以上かつ最小の組み合わせを求める。 アウトプット 　最小合計値の組み合わせ：7+12=19 416 名前：デフォルトの名無しさん mailto:sage [2006/12/13(水) 12:34:57 ] >>415 アルゴリズムを説明すれば自分でプログラム書けるの？ プログラム書いてほしいとか言うのは宿題スレいってくれ 417 名前：デフォルトの名無しさん mailto:sage [2006/12/13(水) 12:50:26 ] ナップサック問題のバリエーション？ 418 名前：415 mailto:sage [2006/12/13(水) 12:50:50 ] >>416 アルゴリズムによってはプログラムで書けるか分からないので、宿題スレに行きます。 419 名前：429 mailto:sage [2006/12/13(水) 13:26:11 ] 415ではないが移動先はっとく pc8.2ch.net/test/read.cgi/tech/1165943509/22/ 420 名前：デフォルトの名無しさん mailto:sage [2006/12/13(水) 14:16:15 ] >>417 Subset Sum Problem という有名 NP （の、最適化問題版）。 まあバリエーションといえばそうなんだけど、知ってて損はない名前よ。 421 名前：デフォルトの名無しさん mailto:sage [2006/12/13(水) 14:37:22 ] 問題から推測すると集合の最大値は指定値をより小さいのかな 422 名前：415 mailto:sage [2006/12/13(水) 15:15:11 ] >>419 お手数おかけしました。 >>417>>420 有名な問題なのですね。 名前自体しらなかったです。 >>421 集合の全合計値より、指定値が小さいという意味ならそうです。 423 名前：デフォルトの名無しさん mailto:sage [2007/01/23(火) 17:46:53 ] sqrt(O(N^2)の処理)の計算量が知りたいのですが sqrtの計算量わかる人いますか 424 名前：デフォルトの名無しさん mailto:sage [2007/01/23(火) 19:59:02 ] >>423 sqrt( O(N^2) の処理 ) という記号の意味がわからん。処理の平方根って何。 具体的にどんなことをしているかを書いたほうが正しい解が得られると思われる。 425 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 00:00:12 ] ひょっとして多倍長計算？ ニュートン法なら一回の反復で桁数２倍 426 名前：426 mailto:sage [2007/01/24(水) 15:42:39 ] ttp://www.apple.com/jp/downloads/dashboard/developer/colourmod.html このようなカラーピッカーを作りたいのだけれど、 中心からの位置によってどのようなRGBに変換されるかの式がわかりません。 どうやって計算しているのでしょう？ 427 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 15:46:57 ] >>426 ttp://image-d.isp.jp/commentary/color_cformula/HSV.html Hが円角度 Sが円半径 Vが隣の垂直ﾊﾞｰ　じゃねーかな？ 428 名前：426 mailto:sage [2007/01/24(水) 15:54:15 ] >>427 ありがとう、作ってみます 429 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 16:01:43 ] >>428 変な色マップになったら　同サイトの HLS変換も試してみてね 430 名前：426 mailto:sage [2007/01/24(水) 16:58:12 ] >>429 おかげさまで出来ました。atanの戻り値[-pi/2,pi/2]を[0,360]に変換するのにミスったのと 427さんに紹介してもらったページのFの式が間違っていた（正しくはF = H/60 - I）ので ちょっとだけ手間取りましたが、無事きれいなカラーサークルになりました。 ありがとうございました。 431 名前：デフォルトの名無しさん [2007/01/24(水) 17:14:29 ] 強欲アルゴリズムについて分かる人はいますか？

---

---

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

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