- 1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ]
- 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉
>プログラム板の皆さん、こんにちは。
>無謀にもこんなスレを立ててみました。
>四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。
>人間にとって計算しやすい方法についても別途語ることにしましょう。
前スレ↓
pc8.2ch.net/test/read.cgi/tech/1090227743/
- 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 ]
- 強欲アルゴリズムについて分かる人はいますか？
- 432 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 17:32:15 ]
- 貪欲とかgreedyとかで検索したらどうだろう。
- 433 名前：デフォルトの名無しさん [2007/01/24(水) 17:36:37 ]
- それがなくて…
- 434 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 19:08:19 ]
- 俺はだいたいのところは分かっていると思うぜ
- 435 名前：デフォルトの名無しさん mailto:sage [2007/01/24(水) 19:27:16 ]
- >>430 atan2使えばいいんじゃね？
- 436 名前：デフォルトの名無しさん mailto:sage [2007/01/26(金) 06:11:36 ]
- 長さが同じint配列が2個ある。
一つの配列内で重複する数は無い。
同じ数がそれぞれの配列で同じ位置にあるとは限らない。
で、一方の配列内に入ってる数が全て他方の配列にも入っているかを確認したい。
こういう場合で配列をそれぞれソートして
先頭から最後まで一致するかを調べる以外に何かいい方法ある？
- 437 名前：デフォルトの名無しさん mailto:sage [2007/01/26(金) 07:12:23 ]
- それは set equality problem という問題で，
O(n log n) が計算量下界であることが知られている．
よって，計算量的には 436 のソート比較は最適．
ハッシュとか確率的アルゴリズムとかで実用的な速度は
上がるかもしれんが，ソート比較が簡素で良いと思うよ．
- 438 名前：デフォルトの名無しさん mailto:sage [2007/01/26(金) 09:06:29 ]
- >>437
なるほど。
ありがとう。
- 439 名前：デフォルトの名無しさん mailto:sage [2007/01/26(金) 09:26:09 ]
- >438
データの範囲が狭ければ有無の配列(データが添字)を使ってO(n)で可能
データに対して有効なハッシュ関数があれば広くても同上
- 440 名前：デフォルトの名無しさん mailto:sage [2007/01/27(土) 00:38:31 ]
- データの個数があんまり多くないからソート比較でも十分速くできた。
>>439
>>437でハッシュと聞いてピンと来た。
機会があれば今度その方法も試してみるよ。
ありがとう。
- 441 名前：デフォルトの名無しさん mailto:sage [2007/02/02(金) 14:13:28 ]
- 有無なら配列じゃなくてビットマップにしろや
- 442 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 11:48:52 ]
- >441
もしかして：ビットの［配列］
- 443 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 14:05:22 ]
- >>441
アルゴリズムと実装は区別しような
分からなかったらスレッド名も見てくれ
- 444 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 23:26:47 ]
- >>443
言葉遊びがしたいのか？
アルゴリズムと実装でいうならどう実装をしようが配列は配列
最適化の話がしたいならアセンブラスレでも逝け
- 445 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 00:44:54 ]
- >>444
444=441 ?
とりあえず君の配列の定義が知りたい。
アルゴリズム論の文脈では、実装における配列と理論における
配列はまったく対応しない可能性があるけど、それは大丈夫？
|
 |
