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))
531:デフォルトの名無しさん
07/08/19 18:25:09
便乗だけど、B木と赤黒木どっちがいいか、
って判断はどこら辺ですればいいですか？
使い分ける時の基準みたいなのが知りたい。
532:デフォルトの名無しさん
07/08/19 19:19:15
>>531
どんな用途に使おうとしてるか分からないので、普通の設定で一般的な話をする。
赤黒木は、本質的にはブロックサイズの小さな B 木なので、
あなたの質問は B 木のブロックサイズをどう選ぶか、という質問と同じ。
普通の実装では、n 個の要素を格納するブロックサイズが b の B 木から
要素を検索には O(log (n/b)) 回の木上の探索（ランダムアクセス）と
O(b) 回のブロック内の探索（シーケンシャルアクセス）が必要となる。
ここで雑な計算をするとブロックサイズは、木上の探索の速度と
ブロック内の探索の速度の比くらいに選ぶのがよいことが分かる。
木が丸ごと全部メモリに乗るような場合は、木のアクセスもブロックの
アクセスも同じくらいなので、ブロックサイズも小さく選ぶのが良い。
一方、ハードディスクやネットワーク上のデータベースのような
木のアクセスが遅く、ブロックのアクセスが早い場合は、
ブロックサイズも大きく選ぶのが良い。
533:デフォルトの名無しさん
07/08/19 19:50:28
>>528 参考にすんな→この人怒ってる怖いよぉ
534:デフォルトの名無しさん
07/08/19 19:54:51
どこぞの園児じゃあるまいし。
535:デフォルトの名無しさん
07/08/19 21:04:07
なんでそんな偉そうなんですか
536:デフォルトの名無しさん
07/08/19 21:04:43
どこが偉そうなの
537:デフォルトの名無しさん
07/08/19 21:37:32
質問を質問で返すな
わかりませんと言え
538:デフォルトの名無しさん
07/08/19 21:40:56
なんでそんな偉そうなの
539:デフォルトの名無しさん
07/08/19 21:41:29
そういうのは質問の体をなしてから言え
540:デフォルトの名無しさん
07/08/19 22:26:02
順序付きコンテナは、どうもトライが最強っぽいんだけど、
メモリが・・
なんとかなりませんか？
541:デフォルトの名無しさん
07/08/19 22:59:51
つ パトリシア
542:デフォルトの名無しさん
07/08/28 05:58:02
2Dの多角形ポリゴン2個(n個)を合成して1個(?)の多角形にするアルゴリズム
ネット上にこれを実装したソースコードが公開されてない(見つからない・・・)のでどなたか教えてください。
＿＿
＿|＿ |
| |＿|＿|
|＿＿|
ポリゴン1 = (0,0)-(2,0)-(2,2)-(0,2)-(0,0)
ポリゴン2 = (1,1)-(3,1)-(3,3)-(1,3)-(1,1)
↓
＿＿
＿| |
| ＿|
|＿＿|
ポリゴン1+2 = (0,0)-(2,0)-(2,1)-(3,1)-(3,3)-(1,3)-(1,2)-(0,2)-(0,0)
というような感じです。
中抜き( 合成後のポリゴンの内側に穴が開いている )まで考えると、結構むずかしそうで・・・
これでやりたいことは、国土地理院の市町村別のポリゴンデータを県ごとに合成して、県別のポリゴンデータにすることです。
Excel VBAで精細な都道府県地図を描きたいなーと思って、
都道府県の無料のポリゴンデータを探したけど市町村別しか見つからなかったので
じゃあ合成して作ろうか、と思ってたんですが・・・詰まりました。
Java の awt パッケージでポリゴンの合成をしているクラスのオリジナルのソースコードを見ればアルゴリズムがわかるかも
とも思ってみてみたけどソースコードは入っておらず・・・orz
宿題とか課題とかではなくて、あくまで趣味的なものなので急ぎません。
VBでもcでもc++でも良いので、どなたか、お知恵を拝借させてください。
543:542
07/08/28 06:00:14
>>542
図形ずれちゃった・・・
＿＿
＿|＿ |
| |＿|＿|
|＿＿|
ポリゴン1 = (0,0)-(2,0)-(2,2)-(0,2)-(0,0)
ポリゴン2 = (1,1)-(3,1)-(3,3)-(1,3)-(1,1)
↓
＿＿
＿| |
| ＿|
|＿|
ポリゴン1+2 = (0,0)-(2,0)-(2,1)-(3,1)-(3,3)-(1,3)-(1,2)-(0,2)-(0,0)
こうです。
544:デフォルトの名無しさん
07/08/28 09:44:30
>542
悪いこと言わないから別の方法考えたほうがいいと思う。
塗り分けるだけなら市町村別のデータでも構わないわけだし。
で、
コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用 ISBN 476490277X
の第 2 章にアルゴリズムは載ってる。でも、ここから実装まで持っていくのもそう単純じゃないと思う。
あと、オープンソースライブラリの CGAL にそういう機能はある。
URLﾘﾝｸ(www.cgal.org)
Reference Manual の VI Polygon and Polyhedron Operations 辺り。
545:542
07/08/28 21:33:57
>>544
コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用 ISBN 476490277Xの第2章 早速読んできました。
例題に挙げられてるのも地図でよさそうだったけど、
プログラミング言語を限定してないアルゴリズムとしての本なんで、
やろうとしていることを実装するには、どういうプログラムを書けばよいのかまでは踏み込めなそうです。
せめて
i ← S1 と S2 の交点
みたいなのがあればなぁ。
CGALのマニュアルも読んでみました。joinあたりのコードか数式が出ていればVBAでも実装できそうなんですが・・・
>悪いこと言わないから別の方法考えたほうがいいと思う。
そうですねー。
ただ、ポリゴンをくっつけるのはもうちょっと粘ってみます。考えるのも楽しいので。
市町村同士は重ならないので、
・辺と辺が重なっている（隣り合っている）ところを見つけてくっつけていく
・中抜きはこの際無視
というように簡単なものを作る方針で考えてみます。
重なりまで考えて汎用的なアルゴリズムにしようと思ったけど、結構しんどそうですので・・・
どうもありがとうございましたー。
546:デフォルトの名無しさん
07/08/29 01:21:12
今日から専門学校のほうで授業アルゴリズムが始まったんですが
時間計算
分時間を入力して○時○分に変換して出力するフローのaとbに該当する処理を記述しなさい。
なお、計算結果は整数部のみとし、小数部は切捨てとなる。
余り（X%Y)で除数の余りを求めることができる。[例、余り（100%3）は1となる]
例：117分の時 1時間57分
（開 始） 何方かa bに入る答えがわかる方いましたら教えてください
↓
（データ）・・分時間を入力
↓
（処理）・・a 時を求める
↓
（データ）・・時を出力
↓
（処理）・・b 残りの分を求める
↓
（データ）・・分を出力
↓
（終了）
547:デフォルトの名無しさん
07/08/29 01:28:01
aとbに入るのは数字？式？言葉？
548:デフォルトの名無しさん
07/08/29 01:39:28
式です＾＾；
549:デフォルトの名無しさん
07/08/29 01:54:03
a・・・分時間/60
b・・・分時間%60
550:デフォルトの名無しさん
07/08/29 03:31:39
>>546
宿題はスレ違い
しかも回答もらって礼も無しかよ
551:デフォルトの名無しさん
07/08/29 19:38:32
三角関数はマクローリン展開して計算しますよね。
単純に考えればsinθのθが何であれ計算時間は変わりませんが、
速度面でチューニングが施されているであろうライブラリではどうなんでしょう？
552:デフォルトの名無しさん
07/08/29 23:22:57
>三角関数はマクローリン展開して計算しますよね。
ここで間違ってる
関数近似の教科書読むべし
553:デフォルトの名無しさん
07/08/29 23:30:11
>>552
すみません、悠長に教科書読んでる暇がないので結論をお願いします
554:デフォルトの名無しさん
07/08/29 23:36:55
CPUのアーキテクチャ等やライブラリ作った奴の腕に依存して色々な可能性がある
ただ，どれもθを0～π/2の範囲に正規化してるだろうから
その範囲なら少し速いはず
これ以上は本嫁
555:デフォルトの名無しさん
07/08/30 01:07:36
ぶっちゃけ、今時の単精度演算アクセラレータはテーブル参照プラスリニア補間で済ませている希ガス。
556:デフォルトの名無しさん
07/08/30 07:24:15
>>554
絶対的な速度が問題なのではなく、速度のむらを気にしているのです。
たとえばsin(0.1)を計算するのに1μsかかったとして、sin(0.2)では5μsかかったりするのか？ということです
>>555
ターゲットはマイコンなのでそういう容量食いな方法は取らないような気がします。
ターゲットはSH7145
ルネサスのコンパイラを使ってます。
ただ、ピンポイントでこのコンパイラに通じている方がいるとは考えにくいので
VCやgccだったらどうなのかという意見でもいいのでお願いします。
557:デフォルトの名無しさん
07/08/30 09:28:07
後出し多いな
558:デフォルトの名無しさん
07/08/30 10:04:11
5倍の差はないだろうけど，1～2割位なら充分あり得る
実測するのが手っ取り早いかと
559:デフォルトの名無しさん
07/08/30 17:45:37
>>556
マイコンの方がむしろテーブル変換使用すると思うが
560:デフォルトの名無しさん
07/08/30 17:47:40
>>554
いっそπ/8に正規化するとか
561:デフォルトの名無しさん
07/09/09 14:05:26
>>553
＞悠長に教科書読んでる暇がないので
そうか。残念だったな。
562:デフォルトの名無しさん
07/09/12 02:03:16
差異のアルゴリズムでレーベンシュタイン距離を求めていますが、
結局これ求めてどうなるんですか？
馬鹿でも分かるようにく教えてください。
563:デフォルトの名無しさん
07/09/12 08:42:09
>>562
そんな限られた分野でしか使わないようなものを
さも誰もが知ってるかのように聞かなくても。
自然言語処理とかで使う。
Google 先生とかがよくやってる
もしかして: ○○
を出したりとかに使える。
564:デフォルトの名無しさん
07/09/13 00:02:29
>563
レスどうも。
2つの文字列を比較して"n文字違います"とかは想像できるんだけど、
diffみたいに異なるものを表示するとかの処理にはどうやって組めばいいんだろうと思って、、、
565:デフォルトの名無しさん
07/09/13 00:05:36
>>564
URLﾘﾝｸ(ja.wikipedia.org)
566:デフォルトの名無しさん
07/09/15 23:51:51
今、ロバスト解について勉強しています。
ロバスト解発見手法にはシックスシグマ法のDesign For Six Sigma[Brue 03]やDesign For Multi-Objective Six Sigma[Shimoyama 06]、またはガウスノイズがあるということが分かりました。
しかし、上に述べた手法の利点・欠点がほとんど分かりません。
どなたか他の手法と比べた場合の利点・欠点を教えてはいただけないでしょうか?
下に今分かっていることを書きます。
----------------------------------------------------------------------
Design For Six Sigma[Brue 03]
ロバスト解を1つ発見する場合に有効。
Design For Multi-Objective Six Sigma[Shimoyama 06]
Design For Six Sigma[Brue 03]を拡張したもの。複数のロバスト解を同時に発見する場合に有効。
ガウスノイズ
アルゴリズムは簡単。
ガウスノイズは上に述べたシックスシグマ法を使ったときよりもすばやく収束できる。
吸収現象などのせいでロバスト解からずれた位置に収束するかもしれない。
567:デフォルトの名無しさん
07/09/19 03:20:29
質問させてください．
y=Ax （x,y:ベクトル， A:マトリックス，大きさ数百～数万）
に対し，
x = inv(A) * y
を解く問題を考えています．
ここで，逆行列演算inv(A)がO(N^3)のコストが掛かり，ネックになっています．
いま，Aは疎な帯行列（しかも対称）という条件があるので，
大幅な計算削減ができるのではないか？と考えております．
例えば，計算コストをO(N^2)にするといったことは可能でしょうか？
キーワードだけでも良いので，知恵を貸していただけると幸いです．
568:デフォルトの名無しさん
07/09/19 03:49:22
つ[特異値分解]
569:デフォルトの名無しさん
07/09/19 07:22:57
>>567
LU使っているのか？
対称行列だと、LDL分解でOK
帯行列だとさらに、0要素を見ないことで、さらにスピードアップ
570:デフォルトの名無しさん
07/09/19 17:36:11
そんな話，数値計算の本見ればいくらでも載ってるだろ
571:567
07/09/20 01:53:07
>>568
キーワードありがとうございます！
調べてみます．
>>569
LU分解→直接法で逆行列としていました．
LDL分解というものがあるのですね．
解法は反復法に持って行くのですかね・・・調べてみようと思います．
反復法は精度の面が少し気になりますが，勉強含めて試してみます．
多謝！
>>570
数値計算の門外漢なもので・・・勉強してきます．
572:デフォルトの名無しさん
07/09/24 22:11:26
kd木で、近い領域を何度も連続して調べたい時、毎回根から辿らないようにショートカットするような技法ってありますか？
573:デフォルトの名無しさん
07/09/28 09:44:52
二つの整列済みリストのマージで
要素数が一方がk個,もう一方が2個の場合,
n回の比較でマージできる最大のkをanとすると
a[n] = [sqrt(2*a[n-1]*(a[n-1]+1))] # []: Gauss記号
で与えられるらしいのですが
これがどういうアルゴリズムでマージしたときの物なのか,
またこれが最良値なのか知りたいのですが, 誰か知りません?
574:デフォルトの名無しさん
07/09/29 14:28:02
>>573
a[n] = [sqrt(2*a[n-1]*(a[n-1]+1))] # []: Gauss記号
この式を見るとnが1増えると√2倍でa[n]は指数的な増加。
ソート済みk個と2個のマージは
2分探索を2回使えば2logk回。
詳しくは見てないが、2logkの係数の2が√2になりそうだし、
kが指数的に増加して比較回数が線形増加もa[n]の式とオーダーは合っている。
575:573
07/09/30 13:03:48
>>574
考えてくれてありがとう.
2分探索だけだと最良値にはならないみたい.
573の式だと最初の10個位までは最良値になってるのは
確認できた(虱潰しで)
さらに知らべて,もう一方のリストが3個の場合みっけた.
Optimal Merging of 3 Elements with n Elements
っていう論文のAbstructで
f3(1)=0, f3(2)=1, f3(3)=1, f3(4)=2, f3(5)=3, f3(6)=4, f3(7)=6, f3(8)=8
r >= 3
f3(3r) = [(43/7)*2**(r-2)]-2
f3(3r+1) = [(107/7)*2**(r-3)]-2
f3(3r+2) = [17*(2**(r-3)-6)/7]-1
との事.
576:デフォルトの名無しさん
07/10/30 01:16:41
各データの値がかなり近い時に
ハッシュのみだとデータの衝突回数
多い場合ってどうやってみんななら解決する？
あとね、kd木で何の本に詳しく載ってますか？
577:デフォルトの名無しさん
07/10/30 01:55:31
値近くてハッシュが衝突するって、どんなアルゴリズムだよ
578:デフォルトの名無しさん
07/10/31 02:27:51
8byteの16進データを
完全ハッシュ化するソースコード置いてある
とこないですか？
579:デフォルトの名無しさん
07/10/31 21:09:37
区分サンプリング法やラテン超方格法のアルゴリズムを教えてください。
580:デフォルトの名無しさん
07/11/28 05:05:51
二点で定義されてる直線上に、ある点があるかどうかを判定するにはどうすればいいですか、教えてください。
581:デフォルトの名無しさん
07/11/28 06:17:51
要は３点が一直線に並んでいるかを知りたい、と解釈し直してみた。
１点を基準に他２点へ直線を引くときの傾きが一緒だったらOK。
x軸と垂直だった場合なんかも考慮すると、
(x1-x0)*(y2-y0)==(x2-x0)*(y1-y0)
582:デフォルトの名無しさん
07/11/28 13:05:52
あ、なるほど、ありがとうございます
583:デフォルトの名無しさん
07/12/07 21:54:02
[N][N]の2次元配列を３つ
[N]の配列を2つ使ってる場合の使用領域のオーダーってＯ(n^2)におさまります？
584:デフォルトの名無しさん
07/12/07 22:02:42
うん
585:デフォルトの名無しさん
07/12/09 21:31:14
3N^2+2N = O(N^2) が分かってないのか？
586:デフォルトの名無しさん
07/12/14 13:42:55
グレブナ基底を求めるプログラム、誰か持っていませんか？
C言語でおねがいしたいです。
587:デフォルトの名無しさん
07/12/15 02:12:22
>>586
23457円になります。
588:デフォルトの名無しさん
07/12/29 03:46:49
均一なセル上に分割した空間で、円（または球）を配置して、円と交差する
セルを全て見つけたいのですが、どうしたら効率よく求まるでしょう？
589:デフォルトの名無しさん
07/12/29 06:33:27
セルってのはよくわからないのだが、格子なの？
格子が座標と平行になるように回転変換して 格子間隔が1になるように伸縮して
円の中心座標の小数点以下座標を見ればいいだけでは？
590:デフォルトの名無しさん
07/12/29 07:51:56
あ、格子です。あ、最初から座標軸並行を仮定してます。
さらに辺の長さを1で仮定してしまいましょか。
えーと意味がいまいちつかめないんですが、
＞格子が座標と平行になるように回転変換、格子間隔が1になるように伸縮
これは元々が単位格子であるなら何もしないでOK?
＞円の中心座標の小数点以下座標
これで、なぜ全ての格子が求まるかがわかりません。
整数部をみれば、中心を含む格子は求まると思いますが。
591:デフォルトの名無しさん
07/12/29 13:33:11
欲しいのは「円周」と交わるセルだろ？
そこがちゃんと書いてないから勘違いされたと思われ
592:デフォルトの名無しさん
07/12/29 17:06:31
あ、そうです。申し訳ない。
593:デフォルトの名無しさん
07/12/30 12:13:13
DDA(digital diffrential analyzer)というのがあるが使えないかな？
３次元は分からんが
594:デフォルトの名無しさん
07/12/30 12:39:28
3次元も、半径が違う円で切り出したものと考えればイケルんじゃないの？
595:デフォルトの名無しさん
07/12/31 01:56:42
ある年月日が与えられ、そのn日後の日付を求めたいのですが、
1,fairfieldの公式で西暦1年1月0日からの経過日数daysを求める
2,days+nを西暦年月日に変換する
という方法を考えました。
2は1の式を変形して解けるだろうと見当を付けていましたが、
小数点以下を切り捨てたりしているためうまく式を求められません。
素直に最初の日付にnを足し、年・月に順次繰り上げていくほうが賢明でしょうか？
日付は最近のものに限定して考えています。
ユリウス暦とグレゴリオ暦の判断が面倒になるので…
596:デフォルトの名無しさん
07/12/31 08:25:44
>>595
日付を1日進めるプログラムは書けるかい？
おｋ。ならば、1日進める部分をn回実行するんだ。
597:デフォルトの名無しさん
07/12/31 08:49:10
つーか、なんで既存ライブラリを使わないのだろう。
大抵の言語に日付け処理系の関数があると言うのに。
598:デフォルトの名無しさん
07/12/31 11:47:35
>>595
URLﾘﾝｸ(ufcpp.net)
599:デフォルトの名無しさん
07/12/31 12:25:41
>>595
ちょっと検索してみたらこんなのがあった
delphiだけど、ｃ言語に変換するのはこどもあそびにひとしい
URLﾘﾝｸ(kwikwi.cocolog-nifty.com)
ところで前々から思ってたんだけど、fairfieldの公式って誰が考案したの？
日本のサイトしか引っかからないんだよね
600:デフォルトの名無しさん
07/12/31 12:29:16
>>596
なるほど。
ただ、(情報が小出しになってすみません)n日前の日付も求められるようにしたいので
上に書いたような方法だとdays+nを-に変えるだけで実現できるかなーと･･･
>>597
Cなのでそういった関数はもちろんあるのですが、若干不便なので
勉強も兼ねて自前で実装してみようというわけです。
601:デフォルトの名無しさん
07/12/31 12:51:11
>>598
おおお÷4を右シフト演算できるのは考えが及んでませんでした
>>599
(mjd - 15078.2) / 365.25 …? もはや何がなんだか。
URLﾘﾝｸ(cl.is.kyushu-u.ac.jp)
こんなの見つけたので読んできます。
602:デフォルトの名無しさん
07/12/31 13:18:34
>>600
URLﾘﾝｸ(www.tensyo.com)
ここの
int YMD_AddD(int *Y,char *M,char *D,long d） って関数を見ると
負数を渡した場合は 400年循環を使って正に直せばいいみたい。
603:デフォルトの名無しさん
08/01/01 10:28:35
つまり、-3日なら 400年前から(146097-3)日後と計算するわけか
604:デフォルトの名無しさん
08/01/02 02:09:27
除算のシフト演算化はコンパイラの最適化段階で
自動でやってくれるものだと思ってたんだが、そうでもない？
605:デフォルトの名無しさん
08/01/02 08:29:27
コンパイラの性能がソレなりならって事でしょう。
固定値の除算ならさらに、掛け算で代用してくれるのも多いね。
606:デフォルトの名無しさん
08/01/02 10:22:11
>>604
2のべきの定数ならね。
607:デフォルトの名無しさん
08/01/02 12:18:44
という事で
１、カレンダを1日進める関数関数を作る
２、+N日は１の関数をN回呼ぶ
３、-N日は、年数を400日戻してから、146097-N回 １の関数を呼ぶ
608:595
08/01/02 20:05:17
これでいいのかな？
struct Date{
int year,month,day;
};
/* 1日進める */
void tomorrow(Date& x)
{
int days[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
if((x.year%4==0 && x.year%100!=0) || x.year%400==0){
days[2]++;
}
x.day++;
if(x.day>days[x.month]){
x.day=1;
x.month++;
}
if(x.month>12){
x.month=1;
x.year++;
}
}
609:595
08/01/02 20:06:50
/* n日後の日付 */
Date after(Date x,int n)
{
for(int i=0;i<n;i++){
tomorrow(x);
}
return x;
}
/* n日前の日付 */
Date before(Date x,int n)
{
n=146097-n;
for(int i=0;i<n;i++){
tomorrow(x);
}
x.year-=400;
return x;
}
610:595
08/01/02 20:39:23
「1にちずつ遡りながら日付を表示」とかやるとbefore()の処理量が馬鹿にならないので、
>>601に載ってるのを参考に書き換えてみました
/* 西暦1年1月0日からの経過日数から、日付を求める */
Date make_date(int n)
{
int y=(n+305)/146097*400
+(n+305)%146097/36524*100
+(n+305)%146097%36524/1461*4
+(n+305)%146097%36524%1461/365;
int diff=n-(365*(y-1)+y/4-y/100+y/400+31+28); // 3月0日からの経過日数
if(diff==0){ //2月29日
diff=366;
y--;
}
int m;
for(m=3;;m++){
//3月0日からm月0日までの経過日数, 30*(m-3)+3*(m+1)/5-2 の変形
if(153*(m+1)/5-122<diff && diff<=153*(m+2)/5-122){
break;
}
}
int d=diff-(153*(m+1)/5-122);
if(m>12){
m-=12;
y++;
}
Date x={y,m,d};
return x;
}
611:デフォルトの名無しさん
08/01/08 03:16:56
漸近的上界とか下界っての何なの締め切り明後日＼(^o^)／ｵﾜﾀ
612:デフォルトの名無しさん
08/01/08 03:17:24
誤爆です。
ごめんなさい
613:デフォルトの名無しさん
08/01/08 13:01:23
>>611
そのまんまの意味じゃなーの。
f(x)=sin xで1,-1は明らかに漸近的ではないが
g(x)=1/x(x≥0)で0は漸近的。
614:デフォルトの名無しさん
08/02/09 20:18:07
質問させてください。
「ハッカーのたのしみ」p137 で多倍長のかけ算のサンプルがあったのですが、
わからない部分があります。
void mulmns( unsigned short w[], unsigned short u[], unsigned short v[], int m, int n ) {
unsigned int k, t, b;
int i, j;
for( i = 0; i < m; i++ ) {
w[ i ] = 0;
}
for( j = 0; j < n; j++ ) {
k = 0;
for( i = 0; i < m; i++ ) {
t = u[i] * v[j] + w[ i + j ] + k;
w[ i + j ] = t;
k = t >> 16;
}
w[ j + m ] = k;
}
}
u と v がかける数、かけられる数、w に結果が入ることはわかるのですが、k は何に使われているんでしょうか？
615:デフォルトの名無しさん
08/02/09 20:31:46
繰り上がり
616:614
08/02/09 20:41:09
>>615 すばやい回答ありがとうございます。
くりあがりですね。
このプログラムの結果って、w に short で表せる数を法としたそれぞれの桁が入ると思うんですけど、
この理解で合っていますか？10 進数で表示したいときには変換するルーチンも別に必要でしょうか？
617:デフォルトの名無しさん
08/02/09 20:44:43
>>616
そのとおり。
10進数で画面に表示する回数が、普通の計算を行う回数よりも
圧倒的に少ないと考えると、そういう数の表現になる。
618:デフォルトの名無しさん
08/02/11 16:13:21
w[ i + j ] = t;
k = t >> 16;
この部分を
k = t/10;
t -=k*10;
w[ i + j ] = t;
とすれば、１０進法になるんじゃない？
8bitなら１００進数
16bitなら10000進数なんてのがオススメだよ
619:デフォルトの名無しさん
08/02/11 23:37:33
HLISP だっけ，32 bit int 使って radix 10^8 で多倍長整数実装してた
620:デフォルトの名無しさん
08/02/18 17:15:48
行列計算するときに、掃き出し法、ガウスザイデル法、SOR法、等ありますが、
調べると掃き出し法は他の計算方法に比べると誤差が大きいと書いてありました。
なぜ誤差が大きくなるのでしょうか？
621:デフォルトの名無しさん
08/02/18 23:15:28
誤差についてはほとんど知識がないので調べてみました。
たまたま今やっていることに関係あるので。
さて、分かったことは小数演算は必ず誤差を含むと言ってもいいこと。
なので、10^n倍で整数に変換したり、ライブラリを使ったり対策を
しなければいけないこと。まぁ大体こんな感じです。
ではなぜ掃き出し法が誤差が大きいかというと、予測ですが
単純に計算量が他に比べて多いからではないでしょうか。
誤差を含む演算はやればやるほど誤差が大きくなるというわけです。
ちゃんとした理由ではないかもしれませんが、それよりも
どうすれば誤差を小さくできるか考えた法がいいと思います。
まぁ原因が分からなくては始まりませんが。
622:デフォルトの名無しさん
08/02/18 23:42:00
>>621
そんなに詳しくないから適当に書くけど、
基本的にはその通り。
収束性が悪いほど誤差は積もりやすい。
あと、除算があると誤差大きくなる。
なので、掃き出し法みたいな手計算的手法のものよりも、
ガウスザイデル法みたいな反復計算の方が誤差少ない。
623:デフォルトの名無しさん
08/02/19 02:13:06
>>620
一概にそうとは言えない。というか、単純に比べることは不適当。
そもそも掃き出しは（解けるならば）必ず A x = b を解くが、
ガウスザイデル、SOR は特殊な A に対してしか一次方程式を解かない。
したがって、無条件で比較することはできない。
次に、生じる誤差が違う。掃き出し法は直接解法なので、考える誤差は丸め誤差のみ。
一方のガウスザイデル、SORは反復解法なので考える誤差は丸め誤差と打切り誤差。
反復法の打切り誤差をどの程度に設定するかということを述べないと、比較はできない。
624:デフォルトの名無しさん
08/02/19 13:21:15
>>623
掃き出しで解けるものでもガウスザイデル、SORで解けないものもあるということでしょうか？
新たな課題ですね(￣□￣;)!!
実は、エクセルマクロで書いた掃き出し法で計算した回帰分析と、
エクセルの分析ツールの回帰分析した結果、
後者の方が精度がよかったので分析ツールの回帰分析は別のアルゴリズムなのかなと考え調べていました。
後者はガウスザイデルなのかもしれません。
625:デフォルトの名無しさん
08/02/19 16:20:26
>>624
マクロでやってるなら、ピボットの選択してる？
626:デフォルトの名無しさん
08/02/19 18:31:45
>>624
掃き出しで解けてガウスザイデルで解けない問題なんて
いくらでもあるよ．たとえば
x + 2 y = 1
2 x + y = 1
をこの順番で連立方程式と考え，ガウスザイデルを
初期値 x = 0, y = 0 で適用すると，発散する．
ガウスザイデルが収束する必要十分条件は，未解決のはず．
627:デフォルトの名無しさん
08/02/21 22:41:32
>>625
＞ マクロでやってるなら、ピボットの選択してる？
いえ、まず中心をすべて1にしてから掃き出しています。
これではダメでしょうか？
628:デフォルトの名無しさん
08/02/22 19:59:46
>>627
ダメ
629:デフォルトの名無しさん
08/04/03 03:18:18
あげ
630:デフォルトの名無しさん
08/04/17 12:46:54
ユークリッドのアルゴリズム(テキストp.10参照．java版はHP参照)を用いて
1,000,000,000,000,000,000(10の18乗)と25の最大公約数を求めるとしたとき、
引き算は何回行われるか答えよ。また、1秒間に10億回の計算を行えるCPU(クロック
1GHzに相当）を用いてこの計算を行ったとき、計算にはどのくらいの時間がかかるか。
「X年Xヶ月」など実感が分かる単位に直して答えよ。
この解き方がわかる人がいましたら是非教えて下さい。
解けなくて困っています。
631:デフォルトの名無しさん
08/04/17 13:30:05
>>630
宿題は自分で解決しようと努力しないと意味がないぞ
どこまでは理解できていて、どこが分からないんだ？
632:デフォルトの名無しさん
08/04/17 14:05:58
というか、奇妙な問題だな
10^N は N>=2 なら25で割り切れる。
つまり最大公約数はユークリッド互除法でも最初のステップで求まってしまう
もしかして 64bit整数演算が出来ない32bitCPUで除算も筆算法でコードを書いたら
って場合か？ それでも実感がわかる単位にはならないわな
633:デフォルトの名無しさん
08/04/17 14:46:19
・>>630が問題を間違えている
・出題者のちょっとした遊び心
どっちかじゃね？
難しそうに見えて実は簡単な問題を出して
最初から課題をやる気がない奴を調べるためだったりしてｗ
634:デフォルトの名無しさん
08/04/21 13:16:15
int型のデータをN個格納できる配列aを考える．つまり，配列要素は a[0],
a[1], ..., a[N-1] でアクセスする．a[0]～a[k]まではデータが既に格
納されており，a[k+1]～a[N-1]までは「空き」の状態であるとする(0 <= k < N)．
このとき，次に挙げる各操作に必要な手間(時間)を，「最も手間のかから
ない場合」と「最も手間のかかる場合」のそれぞれの場合について答えよ．
理由も書くこと．(例を参考にせよ)
例：指定された位置にデータを挿入する操作
答:最も手間のかからない場合：定数時間
最も手間のかかる場合：kに比例する時間
理由：指定された位置が末尾の場合には，データをずらす必要がな
いため定数時間で可能．指定された位置が先頭の場合には，既に格
納されているk+1個のデータを順にずらす必要があるため，kに比例
した時間が必要．
1-1 指定した位置のデータを削除する操作
1-2 指定したデータが格納されているか探索する操作
1-3 格納されているデータの中で最小の値を探索する操作
これを現在解こうと思っていますが、よく分かりません。
分かる人は是非教えて下さい、お願いします。
635:デフォルトの名無しさん
08/04/21 13:32:09
1-1
最良：定数
最悪：k比例
1-2
最良：定数
最悪：k比例
1-3
最良：k比例
最悪：k比例
636:デフォルトの名無しさん
08/04/21 15:08:07
配列を用いてリストを実現することを考える．今，配列には以下のように
データが格納されているとする．(配列keyと配列nextはint型のデータを格
納するとする)
key[0] = 0 ,next[0] = 3
key[1] = 0 ,next[1] = 1
key[2] = 'S' ,next[2] = 6
key[3] = 'L' ,next[3] = 4
key[4] = 'A' ,next[4] = 5
key[5] = 'I' ,next[5] = 2
key[6] = 'T' ,next[6] = 1
位置0はhead, 位置1はzを表す．
このとき，次の問に答えよ．
(1)リストに格納されている文字を，リストの先頭から順に書け．
(2) もしも next[0] の値が4だった場合，リストに格納されている文字を
リストの先頭から順に書くとどうなるか述べよ．
(3) リストから'A'を格納している節点(key[4]とnext[4]に対応)を削除し
た場合，配列keyと配列nextの中身はどのように変化するか述べよ
(key[4]とnext[4]の値はそれぞれ0に設定せよ)
637:デフォルトの名無しさん
08/04/21 16:28:55
ここは宿題すれじゃねーんだよ・・・
638:デフォルトの名無しさん
08/04/21 17:03:43
行列計算のガウスザイデル法が収束しないことがあるので気になっていたけど
検索するとGMRes(一般化残差最少法、GMRes法 )というのがあるらしい。
(残差を最小にするから、たとえ解が無くても最適な値が求まる？収束に向かうのは確実？)
ただ、ガウスザイデル法は数行のプログラムなのに対して
見つけたプログラムがかなりでかいサイズになっているのがまた気になる。
ガウスザイデル法で残差を小さくするような改良って無いのかな？誰か知ってる？
639:デフォルトの名無しさん
08/04/21 17:40:08
これが、SOR法である。
ここで、問題なのが加速緩和係数の値の選び方である。明らかに、それが1の場合、ガウス・ザイデル法となりメリットは無い。また、1以下だと、ガウス・ザイデル法よりも収束が遅い。ただし、ガウス・ザイデル法で収束しないような問題には使える。
従って、1以上の値にしたいわけであるが、余り大きくすると、発散するのは目に見えている。これについては、2を越えると発散することが分かっている。最適値となると、だいたい1.9くらいが選ばれることが多い。
URLﾘﾝｸ(www.akita-nct.ac.jp)
640:デフォルトの名無しさん
08/04/21 18:02:14
ω=1.9から始めて発散なら値を引き下げていけばいいって事だな
ω=1がもともとのやつ
641:デフォルトの名無しさん
08/04/22 00:29:31
ガウスザイデル法には，原理的に収束しないインスタンスが存在するので
収束しないことが気になるような場合には，そもそも使ったらダメ．
これはSORでも状況は変わらない．
GMResやらBiCGやらIDRやら反復解法は色々あるんだから
解きたい問題にあわせて適切に解法を選ばないとダメよ．
642:デフォルトの名無しさん
08/04/22 00:57:39
原理的に収束しないとは? 解が存在する行列でもできないってこと?
643:デフォルトの名無しさん
08/04/22 05:48:37
>>641
なるほど、どうもです。
プログラマ的な発想で少し工夫すればいけるんじゃない？と思ってましたが
やはり数学は厳密ですからね。たまたま、やってみたものがうまくいっても
その正しさを証明しなければならないので、出来上がったものを使いたいなと思います。
644:デフォルトの名無しさん
08/04/22 09:27:07
>>642
そのとおり．
ガウスザイデル法は，対角優位とか半正定とかを満たしている場合を除いて
解が存在しても，収束するとは限らない．
いつ収束するかの厳密なところ（必要十分条件）は，現在でも未解決問題．
645:デフォルトの名無しさん
08/04/23 16:48:12
>>644
639のこれは?
。また、1以下だと、ガウス・ザイデル法よりも収束が遅い。ただし、ガウス・ザイデル法で収束しないような問題には使える。
646:デフォルトの名無しさん
08/04/23 17:10:06
>>644
SOR法の0 < ω < 2である係数を2以上にすると必ず収束しない事がわかっている
ωの値によって収束が左右される 0に近づければガウスザイデル法で無理な場合も収束するのでは?
647:デフォルトの名無しさん
08/04/23 20:15:14
ω=1はガウスザイデル法である
648:デフォルトの名無しさん
08/04/25 01:51:21
グレースケール変換。こいつより高速アルゴキボンヌ。
条件：徐々にグレースケール変換できればvolumeの持たせ方は自由
// 【メソッド名】convGrayScale
// 【引数説明】
// srcRGB：変換元画像(0xRRGGBBのピクセル配列)
// pixel_num：ピクセル数
// volume 0(無変換)～255(完全変換)の範囲でグレースケールに変換
// dstRGB：変換先(0xRRGGBBのピクセル配列)
649:デフォルトの名無しさん
08/04/25 01:52:02
public void convGrayScale(int[] srcRGB, int pixel_num, int volume, int[] dstRGB){
int red, green, blue, Y;
for(int i=0; i<pixel_num; i++){
red = srcRGB[i] >> 16;
green = (srcRGB[i] & 0xFF00) >> 8;
blue = srcRGB[i] & 0xFF;
Y = (red * 298912 + green * 586611 + blue * 114478) / 1000000; // グレースケールの計算
if(Y > red){ // R成分の調整
red += volume;
if(Y < red) red = Y;
}else if(Y < red){
red -= volume;
if(Y > red) red = Y;
}
if(Y > green){ // G成分の調整
green += volume;
if(Y < green) green = Y;
}else if(Y < green){
green -= volume;
if(Y > green) green = Y;
}
if(Y > blue){ // B成分の調整
blue += volume;
if(Y < blue) blue = Y;
}else if(Y < blue){
blue -= volume;
if(Y > blue) blue = Y;
}
dstRGB[i] = (red << 16) + (green << 8) + blue; // 変換結果
}
}
650:デフォルトの名無しさん
08/04/25 01:54:17
あ、一応JavaだけどCとかでもおｋ
651:デフォルトの名無しさん
08/04/25 02:10:24
volumeって要は、グレイ化度合いみたいなものなのね。
処で、volumeを255まで振る前にグレイになってしまうし、振っていく途中で違う色相の色が出てしまいそうだけどいいのかね。
652:648
08/04/25 03:08:47
volumeって要は、グレイ化度合い⇒そのとおり！
volumeを255まで振る前にグレイになってしまう
⇒それは思ったけど、取り得る範囲がわからんかった。。。
r=0,g=0,b=255、r=255,g=255,b=0の場合で29.191890～225.808365の範囲で196.616475がMAXかなぁ
振っていく途中で違う色相の色が出てしまいそうだけどいいのかね。
⇒ちょっとわからんkwsk
ちなみに自分の使い方としては元画像srcRGBはずっと変えずにvolumeを増やす感じ
だから一度変換したdstRGBをsrcRGBに使うことはない
653:648
08/04/25 03:15:22
ちなみに、volumeを0～100%として
dstRGB[i] = (((Y * volume + red * (100 - volume)) / 100)<<16) +
(((Y * volume + green * (100 - volume)) / 100)<<8) +
((Y * volume + blue * (100 - volume)) / 100);
としたてみたけど、遅くなったorz
654:デフォルトの名無しさん
08/04/25 06:45:23
Y = (red * 298912 + green * 586611 + blue * 114478) / 1000000; // グレースケールの計算
これの意味を教えて
655:デフォルトの名無しさん
08/04/25 06:54:50
>>654
YUV とか 色空間あたりでググって見たら、、、
wikipedia の 「色空間」だとか
URLﾘﾝｸ(ofo.jp) の 2.NTSC ～
にある式を 小数点 の無い形にしたと考えたらいいんじゃない?
656:デフォルトの名無しさん
08/04/25 07:26:42
こういう時は
Y = (red * 19589+ green * 38444+ blue * 7503) / 0x10000;
か、
Y = (red * 77 + green * 150+ blue * 29)/ 256 ;
と２のベキにしたらどうかな /256 は >>8 に出来る
8bitにすれば rgbも8bitだから 16bitの入れ物で計算出来る
dstRGB[i] = (((Y * volume + red * (100 - volume)) / 100)<<16) +
(((Y * volume + green * (100 - volume)) / 100)<<8) +
((Y * volume + blue * (100 - volume)) / 100);
もvolumeを２のベキにして
Y*k + X*(1-k) = X+(Y-X)*k なので
dstRGB[i] = ((( red + (( (Y - red )*volume)>>8) )<<16) +
((( green+ (( (Y - green)*volume)>>8) )<<8) +
(( blue + (( (Y - blue )*volume)>>8) );
としたら掛け算は減らせるよ
657:648
08/04/25 07:54:03
>>656
なるほど！！さんくす
Y = (red * 77 + green * 150 + blue * 29) >> 8;
dstRGB[i] = (((red + (((Y - red) * volume) >> 8)) << 16) +
((green + (((Y - green) * volume) >> 8)) << 8) +
(blue + (((Y - blue) * volume) >> 8)));
今、これで自分の環境で試したら1000ms切った！(前は1100msくらい)
でも500くらいは欲しいorz
658:デフォルトの名無しさん
08/04/25 08:51:23
>>657
distRGB の方は、
(red + (～)>>8)<<16 を red<<16 + (～)<<8 などど展開して
red<<16+green<<8+blue とまとめて、
*volume) << の部分を出して因数分解できれば良さげだよね。
>>8 の方も レジスタの H を取るような方法で早くなるかな。
だだ、新しいCPUだと シフト演算もテーブル化してあって
シフト回数がステート数に影響しないからなぁ。
あっ。もうすぐ9時なのでここまででカキコ。
659:デフォルトの名無しさん
08/04/25 10:12:30
java だから 割り算をシフトにするとかの最適化があんまり効かないのかもな
どの行が一番時間かかってるか コメントアウトしては時間計って
一番時間かかってる行から順に工夫してゆくしかないと思うけど
cかDelphiでDLL作った方が早いんじゃないの？
660:デフォルトの名無しさん
08/04/25 10:20:09
あとは
Y8 = Y<<8
v = 256-volume;
dstRGB[i] =(((( ( Y8 - ( (Y - red )*v) ) & 0xFF00 )<<8 +
((( ( Y8 - ( (Y - green)*v) ) & 0xFF00 ) +
(( ( Y8 - ( (Y - blue )*v) )>>8 ;
くらいかなv = 256-volume は最初からそう使えば問題ない
でも半分は無理だろな
661:デフォルトの名無しさん
08/04/26 10:06:56
>>645
任意のパラメタωに対して、真の解に収束しない例が作れる．
662:648
08/04/26 13:27:23
>>658-660
いろいろありがと。
今んとこ、volume調整計算を事前にしておくことで800ms切ることができた
volumeは10段階くらいあればよくて、グレースケールの精度もそこまで求めてない
この条件でまだいげねがな？
char[][][] g_gray_tbl = new char[256][256][10]; // グレースケール変換計算テーブル
// 事前計算処理
// src：変換前値 dst：変換後値 vol：度合い(0～9の10段階)
for(int src=0; src<256; src++){
for(int dst=0; dst<256; dst++){
for(int vol=0; vol<10; vol++){
g_gray_tbl[src][dst][vol] = (char)(src + (((dst - src) * vol) / 9));
}
}
}
dstRGB[i] = ((g_gray_tbl[red][Y][volume] << 16) +
(g_gray_tbl[green][Y][volume] << 8) +
g_gray_tbl[blue][Y][volume]);
663:デフォルトの名無しさん
08/06/12 13:23:40
誰かクイックソートが挿入法よりなぜ早いのか教えてくれ
クイックソートのほうがめんどくさそうなのに最速とか理解できん・・・
664:デフォルトの名無しさん
08/06/12 14:07:54
>>663
クイックソートがソートの中で最速ってわけではないが……
同じデータ数なら、挿入法よりもクイックソートの方が
ソートが完了するまでの比較回数やデータ位置の入れ替えの回数が
平均的に少ないアルゴリズムになっているから。
ソートは基本的にループや再帰呼び出しによる操作だけれど、
ループに入る前や出た後の準備や後始末、
それにループ内での操作が少しくらい複雑になっても、
ループや再帰の回数がそれを補って余るだけ減少する方法なら全体として速くなる。
665:デフォルトの名無しさん
08/06/12 15:26:15
>>663
大まかな話、例えば10,000個のデータをソートする場合、データの比較や交換を行う平均的な操作回数は、
挿入法なら1回当たり2～10,000個のデータの操作を行うループを10,000回行うから50,000,000回程度の操作が必要。
クイックソートは10,000個のデータをピボットに対する大小で2グループに分けるということを行うのに10,000回の操作が必要。
さらに2つに分けたグループごとに同じことを行うので両方のグループ合わせてやはり10,000回の操作が必要。
この分割をどんどん進めて最終的にグループ内のデータ数が1個になるまで行うと分割回数はlog10,000/log2=13回程度。
つまり全部で約130,000回の操作が必要になる。
50,000,000回と130,000回の操作では比べるべくもないということ。
しかもクイックソートは挿入法に比べて全体的に複雑なことをやっているように見えても、
データの比較や移動という基本的な操作にかかる時間が変わるわけではないから、
操作回数の極端な減少はソート時間の減少に繋がるということになる。
666:デフォルトの名無しさん
08/07/04 23:20:30
エクスポゼのような敷き詰めとGraphVizのようなほかの四角とかとぶつからないように関係する四角を近くにレイアウトしてさらに関係線を四角にかぶらないように線を引くアルゴリズムがわかりません(´・ω・｀)
667:デフォルトの名無しさん
08/07/27 08:46:19
>>666
おまい自身が手で線を引くなら、そういうときは
どういう手順で何を基準に線を引いてるんだ？
668:デフォルトの名無しさん
08/08/30 18:14:43
あげ
669:デフォルトの名無しさん
08/10/11 22:27:10
URLﾘﾝｸ(www.forest.impress.co.jp)
↑テキスト比較ツール「DF」のように２つのテキストファイルを比較して
お互い一致しない行を探し出すプログラムを自前で組みたいとおもっています。
（C#を予定）
この手のプログラムを組むにはどのようなアルゴリズムを調べれば実現できる
ようになるでしょうか？
670:669
08/10/11 22:29:00
失礼。↓こちらのスレで質問した方が適切でしたね。よく調べずに質問してすいません(´･ω･｀)
プログラミングの為の数学と算数 vol.3
ｽﾚﾘﾝｸ(tech板)
671:デフォルトの名無しさん
08/10/11 23:04:05
>>670
こっちでいいよ
そのソフトウェアをダウンロードする気が無いから確認だけど
aaa
bbb
ccc
ってテキストと
aaa
ccc
ってテキストを比較するとどうなるの？
672:669
08/10/11 23:11:15
>>671
両者の「aaa」と「ccc」がそれぞれ一致したと見なされ、前者の「bbb」が不一致と表示されます。
673:デフォルトの名無しさん
08/10/11 23:16:47
>>669
手始めに ONP とか LCS とかでググレばいいんじゃね。
ONP とかだけだと、関係ないものがいっぱいヒットするから
「ONP アルゴリズム」とかでググルが吉。
674:デフォルトの名無しさん
08/10/12 01:23:58
どうでもよさげだがDFの説明だとしたら>>672はちょっと言い方が適当過ぎないか？
diffっぽく聞こえる。 いや、やりたいことはdiffなんだろうけど。
675:669
08/10/12 01:54:11
>>674
オリジナルの文のうち、消えた部分を特定できれば十分です。
aaa aaa
bbb ccc
ccc ddd
左がオリジナル、右が比較用としますとオリジナルから消えた部分として
bbbを特定できれば満足です。
676:デフォルトの名無しさん
08/10/12 02:27:20
>>675
あくまでアルゴリズムが知りたいなら>>673のとおりに。
外部ソフトの起動初心者じゃなくて、手軽にやりたくて、
２ファイル間の比較でいいならDOSにFCというコマンドがあるからC#からそれを呼んでその結果を解析すればおｋ
677:デフォルトの名無しさん
08/10/12 07:27:56
> 手軽にやりたくて、
今時 FC はないだろ。
って言うか、それなら DF 呼び出すようにするだろうし。
単に楽したいだけなら、C# で LCS の実装例とかも見つけられるでしょ。
参考 URL: URLﾘﾝｸ(d.hatena.ne.jp)
678:デフォルトの名無しさん
08/10/12 12:10:51
>>677
DFってそういう出力する方法あるのか？
わざわざ実装したいくらいだから結果をプログラム中で使いたいのだと思ったんだが。
あとFCなら配布時に別途導入してもらう必要が無いし。
あと>>673のキーワードで見つけられない人が実装例みて実装できるのかちょっと疑問。
679:デフォルトの名無しさん
08/10/12 13:30:35
> わざわざ実装したいくらいだから結果をプログラム中で使いたいのだと思ったんだが。
FC 勧める理由がわからん。
比較するテキストファイルの書式が決まってるならまだしも任意のテキストファイルを
想定すると、FC の出力の解析は結構大変だよ。
680:669
08/10/12 14:19:04
動的計画法と配列アラインメント
URLﾘﾝｸ(www.ibm.com)
↑LCSのプログラムに関して概念を説明しているサイトがありました。
これにそってLCSテーブルを作り、LCSを見つけてみようと思います。
681:デフォルトの名無しさん
08/10/12 15:09:12
>>679
勧めた理由はその次の行に書いたが？
ぶっちゃけそれ以上の理由は無い。
解析が大変だと思うのは同意。
>>680
>>677のソースをコピペでいいのに。
682:デフォルトの名無しさん
08/10/12 15:26:58
>>681
> 勧めた理由はその次の行に書いたが？
配布の容易さと解析の容易さの比較は状況次第だから議論は避けるよ。
> >>677のソースをコピペでいいのに。
>>669 は、アルゴリズムを理解しようとしてるんだろうと思うし、コピ
ペでは得られないものがあると思うよ。
頑張れ > >>669