計算アルゴリズム【�U】
レス数が1000を超えています。これ以上書き込みはできません。
0001デフォルトの名無しさん
2005/10/15(土) 20:42:23>プログラム板の皆さん、こんにちは。
>無謀にもこんなスレを立ててみました。
>四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。
>人間にとって計算しやすい方法についても別途語ることにしましょう。
前スレ↓
http://pc8.2ch.net/test/read.cgi/tech/1090227743/
0002デフォルトの名無しさん
2005/10/15(土) 20:52:570003デフォルトの名無しさん
2005/10/15(土) 21:10:02プログラミングの為の数学と算数 vol.2
http://pc8.2ch.net/test/read.cgi/tech/1094368921/
を使ってクレって言ったのに、たてちゃったか。
ようし、前スレで我慢してたけど、 精度ネタいっちゃうぞ。
まずは、「2直線の角度を求める」ネタだ。
前スレでは、ベクトルの内積A・B A・B = cos(φ) *|A|*|B| から、角度を求める。
こいつは2つのベクトルの角度の定義でもあるから王道のように見えるだろう。
しかし、問題はcos(φ)が1に近い時、つまり2直線が平行に近くなると精度が悪いという事だ。
解決は簡単で、Aに垂直な線で同じことをやれば sin(φ)が求まるという事を利用して
cos と sin から atan2 で求ればいい。
さあ、↓ まずは2次元で公式を作ってみよう
0004デフォルトの名無しさん
2005/10/15(土) 21:15:500005デフォルトの名無しさん
2005/10/15(土) 21:28:050006デフォルトの名無しさん
2005/10/15(土) 21:41:280007デフォルトの名無しさん
2005/10/15(土) 21:57:53方向ベクトル [dx,dy] を90度回転させれば [dy, -dx] になる
つまりx,yを入れ替えて片方負数にすればいい
内積 (dx1*dx2+dy1*dy2) 90度回転させた相手との内積 (dy1*dx2-dx1*dy2)
で この比の ArcTanを取ればいいことになる。 実際にはatan2を使えば良い。
0008デフォルトの名無しさん
2005/10/15(土) 22:55:06ある自然数が作れるかどうかを判定するプログラムを書いてみたい(出来ればCで)と思います。
数字の方はfor文使って順に変えていけばいいんですが、演算やカッコは
数値じゃないから、色々と変えていく作業をループで回せませんよね?
だから組み合わせの場合わけが膨大になってしまいます。
いい案があれば教えてください。
0009デフォルトの名無しさん
2005/10/15(土) 23:02:18四則演算は優先順位を付けるの? だったら計算は再起下降で処理させればいい
0010デフォルトの名無しさん
2005/10/15(土) 23:10:59「カッコの組み合わせ」とあるから、頭っからの総当りで十分だろ。
[0-9][+-*/][0-9][+-*/][0-9][+-*/][0-9]
10*4*10*4*10*4*10=640000通り
実際は被るパターンがあるけど、まぁいいか。
0011デフォルトの名無しさん
2005/10/15(土) 23:37:360012デフォルトの名無しさん
2005/10/15(土) 23:54:110013デフォルトの名無しさん
2005/10/15(土) 23:59:400014デフォルトの名無しさん
2005/10/16(日) 00:04:21使えるなら1+1+1+...+1で終了だし。
0015デフォルトの名無しさん
2005/10/16(日) 00:05:070016デフォルトの名無しさん
2005/10/16(日) 00:08:27a/(b+c/d)みたいなのは括弧無しだと無理じゃない?
0017デフォルトの名無しさん
2005/10/16(日) 01:05:15*,/と+,-の優先順位は考えなくても良くなる。
計算順は以下の5通りになる。?はいずれかの演算子ね。
チェックの冗長性をもっと減らす方法もあるだろうけど
この5パターンでそれぞれやればいいんじゃない?
((a?b)?c)?d
(a?(b?c))?d
a?((b?c)?d)
a?(b?(c?d))
(a?b)?(c?d)
0018デフォルトの名無しさん
2005/10/16(日) 01:09:223つの数の表は2つの数の表から1個と数1数を演算子でつなぐだけ。
4つの数の表は2つの数の表から2個とってくるか、3つの数の表から1個と数1個でつくることができる。
指数オーダーだけど、4つぐらいならなんとかならないか。
0019デフォルトの名無しさん
2005/10/16(日) 01:15:18同じ数字を複数回使えないという制限がある場合にはその方法は難しいな。
>8の文面だけではその制限があるのかどうかわからないが。
0020デフォルトの名無しさん
2005/10/16(日) 02:15:28(9*9+9)/9
(1/9+1)*9
この2つだけ解れば十分な希ガス。
0021デフォルトの名無しさん
2005/10/16(日) 02:16:350022デフォルトの名無しさん
2005/10/16(日) 02:49:120023デフォルトの名無しさん
2005/10/16(日) 03:04:57整数1,2,3,4をそれぞれ+,-,*,/に割り当てて、
1なら2つの数を足して、2なら前から後ろを引いて…っていうような
関数を用意して、forループ化したらいいんじゃないの?
例えば、int calc(int a, int b, int op)として、
int ans;
switch(op){
case(1):ans=a+b;break;
case(2):ans=a-b;break;
case(3):ans=a*b;break;
case(4):ans=a/b;break;
}
return(ans);
みたいな感じで。
0024デフォルトの名無しさん
2005/10/16(日) 06:39:30それじゃ、優先順位を表現出来ないから悩んでるんだろ?
文字配列にして再帰下降で処理すればいいよ
0025デフォルトの名無しさん
2005/10/16(日) 06:41:43procedure addsub ;forward;
procedure factor; begin
if p^ = '(' then begin inc(p); addsub; if p^<> ')' then Abort;inc(p);end
else if p^ in ['1'..'9'] then begin num:=StrToInt(p^);inc(p);end;
end;
procedure muldiv; var save:Integer; oldsym:char; begin
factor;
while (p^ in ['*','/'] ) do begin save:=num;oldsym:=p^; inc(p); factor;
case oldsym of
'*': num:=save*num;
'/': num:=save div num;
end;
end;
end;
procedure addsub; var save:Integer; oldsym:char; begin
case p^ of
'+': begin inc(p);MulDiv; end;
'-': begin inc(p);MulDiv; num:=-num; end;
else muldiv;
end;
while (p^ in [ '+','-'] ) do
begin save:=num;oldsym:=p^; inc(p);
muldiv;
case oldsym of
'+': num:=save+num;
'-': num:=save-num;
end;
end;
end;
begin
p:=PChar(作った文字列); addsub; 答えはnum
0026デフォルトの名無しさん
2005/10/16(日) 08:12:070028デフォルトの名無しさん
2005/10/16(日) 08:38:01char op[] = "1234+*+"; // (1+(2*(3+4)))
int stack[100];
for (int i = 0, top = 0, d; i < strlen(op); ++i)
switch (op[i]) {
case '+':
d = stack[--top];
d += stack[--top];
stack[top++] = d;
break;
case '*':
d = stack[--top];
d *= stack[--top];
stack[top++] = d;
break;
default:
stack[top++] = op[i] - '0';
}
printf("%d\n", stack[0]);
0029デフォルトの名無しさん
2005/10/16(日) 08:39:31それでも、結構めんどくさい。 瞬殺ってわけにはいかんと思うよ。
003029
2005/10/16(日) 08:40:44003129
2005/10/16(日) 08:46:359999XXX という文字列を作って .... X は + - * /
全スキャンをすれば 括弧つき四則演算は全て網羅出来るというわけで
後は、後置記法から逆変換するコードさえ書けば完成って所だね
003329
2005/10/16(日) 09:05:05003429
2005/10/16(日) 09:19:389999XXX
999X9XX
99X9X9X
99X99XX
全部必要か? なら 逆変換しなくていい 再起下降もそう悪くないな
003528
2005/10/16(日) 09:58:58それを言われると痛い…….でも中置では全ての式の生成がちょっとややこしくならない?
後置だと↓な感じで再帰回して済むんだけど.
#include <stdio.h>
#include <limits.h>
#include <math.h>
#include <string.h>
#define calc(stack, top, op) \
if (top < 2) return INT_MIN; \
if (#op[0] == '/' && stack[top-1] == stack[top-2]) return INT_MIN; \
stack[top-2] = stack[top-2] op stack[top-1]; --top;
double eval(char* p) {
double stack[100], d;
int top;
for (top = 0; *p != '\0'; ++p)
switch (*p) {
case '+': calc(stack, top, +); break;
case '-': calc(stack, top, -); break;
case '*': calc(stack, top, *); break;
case '/': calc(stack, top, /); break;
default: stack[top++] = *p - '0';
}
return top == 1 ? stack[0] : INT_MIN;
}
003628
2005/10/16(日) 10:00:55char *KEY = "9+-*/";
void solve(int x, char *work, int i) {
int j;
if (i < 7) for (j = 0; j < strlen(KEY); ++j)
work[i] = KEY[j], solve(x, work, i+1);
else if (fabs(eval(work)-x)<1e-7)
printf("%s = %.0lf\n", work, eval(work));
}
int main() {
char work[8];
solve(10, work, 0);
}
003729
2005/10/16(日) 10:53:47括弧の対応は再起下降処理中にチェック出来るから全部の組み合わせをやる方針なら
ややこしさは同じ程度だろう
ただ計算量は、後置だと組み合わせが少ないから探索目的ならそれで探すべきだな
003828
2005/10/16(日) 13:33:24× if (#op[0] == '/' && stack[top-1] == stack[top-2]) return INT_MIN; \
○ if (#op[0] == '/' && stack[top-2] == 0) return INT_MIN; \
0039デフォルトの名無しさん
2005/10/16(日) 13:35:140040検索したら見つけた
2005/10/16(日) 14:13:03int i,j=10000,k;double n[4];char*s="+-*/",c[4][14];void f(double*l,char c[][14]
,int n){int b,j;double x,y,m[4];char*p,d[4][14];--n||*l>10.001|*l<9.999||puts(*
c);for(b=n;b--;){x=l[b],y=l[b+1];for(i=n;i--;sprintf(d[i],"%s",c[i+(i>b)]))m[i]
=l[i+(i>b)];sprintf(d[b],"(%s %s)",c[b],c[b+1]);for(j=4;j--;f(m,d,n)){m[b]=j?j-
1?j-2?y*y<.0001?999:x/y:x*y:x-y:x+y;for(p=c[b];*p;p++);d[b][p-c[b]+1]=s[j];}}}
main(){for(;j--;f(n,c,4))for(k=j,i=4;i--;k/=10)*c[i]=(n[i]=k%10)+48;return 0;}
0041デフォルトの名無しさん
2005/10/16(日) 14:46:55前スレの>>1に聞いてください。
0042デフォルトの名無しさん
2005/10/16(日) 16:24:41理系・数学板の任意のスレでKingと呼べばいつでも出てきてくれます。
0043デフォルトの名無しさん
2005/10/16(日) 17:34:59どうすればいいんでしょうか?計算方法を教えてください。
0044デフォルトの名無しさん
2005/10/16(日) 18:03:09(x-xb)^2+(y-yb)^2=(r+rb)^2
(x-xc)^2+(y-yc)^2=(r+rc)^2
の連立方程式解くわけでしょ?適当な2式を組み合わせて両辺をさっ引いたらx^2,y^2,r^2の項は全部消える。
その結果が
Ax+By+Cr+D=0
Ex+Fy+Gr+H=0
の形になるはずなので、たとえばxとyの2元連立方程式と思って解く。つまりrの式で表す。
それを最初の式に突っ込んだら解けるんじゃない?
0045デフォルトの名無しさん
2005/10/16(日) 18:04:18外包円=ぴったり3つの円が収まる状態なら
外包円との接点と、中心を結ぶ線上に、接する円の中心もあるというのが拘束条件に出来ると思う
俺なら、厳密解を出すのはメンドクサイから、
一つの円にまず接しておいて、のこり1つの円に接するとした時の求まる 外包円の中心で
外包円を描いて、 最後の一つの円との距離で2分法かニュートン法的に解くかな
0046デフォルトの名無しさん
2005/10/16(日) 18:25:503つの円の中心までの距離±半径が 接する円の半径と等しいわけで
(x-xa)^2+(y-ya)^2 +ra^2= r^2
(x-xb)^2+(y-yb)^2 +rb^2= r^2
(x-xc)^2+(y-yc)^2 +rc^2= r^2
になるのでは?
004746
2005/10/16(日) 18:27:43(x-xa)^2+(y-ya)^2=(r±ra)^2
(x-xb)^2+(y-yb)^2=(r±rb)^2
(x-xc)^2+(y-yc)^2=(r±rc)^2
004846
2005/10/16(日) 18:54:020049デフォルトの名無しさん
2005/10/16(日) 18:57:01あってると思う。
(上)-(中) と (中)-(下) と (下)-(上) で連立させれば
3元1次方程式が出てきてめでたしめでたしじゃないの?
005046
2005/10/16(日) 19:05:40うーん途中までやってみたけど、自分の仕事じゃないしな。
0051デフォルトの名無しさん
2005/10/16(日) 20:15:50外接円の中で半径最小のもの,とかしないと求まんないと思う.
0052デフォルトの名無しさん
2005/10/16(日) 20:20:120053デフォルトの名無しさん
2005/10/16(日) 20:33:32外積のほうが説明楽だろ、θ=tan^-1(|a x b|/|a ・ b|)
0054デフォルトの名無しさん
2005/10/16(日) 20:34:100055デフォルトの名無しさん
2005/10/16(日) 20:34:500056デフォルトの名無しさん
2005/10/16(日) 20:35:51元ネタは2次元だから外積持ち出すのは・・・・
0057デフォルトの名無しさん
2005/10/17(月) 16:22:400058デフォルトの名無しさん
2005/10/17(月) 18:14:480059デフォルトの名無しさん
2005/10/17(月) 20:20:520060デフォルトの名無しさん
2005/10/17(月) 20:39:42もう覚えてないや
0061デフォルトの名無しさん
2005/10/17(月) 22:11:56凸包だね。ドロネー図を求める手法なのは確かだが、凸包の方がはるかに
有名だと思うんだけど。
0062デフォルトの名無しさん
2005/10/17(月) 22:31:30教えてください。
0063デフォルトの名無しさん
2005/10/17(月) 23:33:21複素数の導入をはじめとして
次元をひとつ上げると関係が急にシンプルになるケースは非常に多いので
その突っ込み方はおかしいと思うす
0064デフォルトの名無しさん
2005/10/18(火) 02:06:23情報科学では、2次元の外積を定義することがありますよ
0065デフォルトの名無しさん
2005/10/18(火) 12:16:54a. Write a pseudo code for a divide-and-conquer algorithm
for the exponentiation problem of computing a^n where a>0 and n is a positive integer.
累乗の問題a^n (aは0よりも大きくnは正の整数)を計算するdivide-and-conquerアルゴリズムの擬似コードを書きなさい。
b. Set up and solve (for n=2^k) a recurrence ralation for the number of multiplications made by algorithm.
そのアルゴリズムによって作られた(発生した)掛け算の数のための回帰関係(n=2^k)を設定して解きなさい。
c. How does this algorithm compare with the brute-force algorithm for this problem.
このアルゴリズムはこの(同じ)問題のためのブルートフォースアルゴリズムとどう比較しますか?
(比較するとどうですか、ということだと思いますが)
a.でもう躓いてます。手のつけようがありません。
divide-and-conquerなんてmergesortとquicksortくらいなら知ってますが、
a^nなんて普通に計算すればいいんじゃないかと…いや、数が大きいと駄目なのかな?
どうか擬似コード教えてください。お願いします。m(__)m
0066デフォルトの名無しさん
2005/10/18(火) 12:20:44006765
2005/10/18(火) 12:23:16"a^n"の部分がうまく引っ掛からずに質問したんですが
キーワードをexponentiationにしたら擬似コード見つかりました。あらら。
例えばここ:
ttp://www.math.grin.edu/~rebelsky/Courses/CS152/2000S/Outlines/outline.22.html#simplerecursiveexponentiation
失礼しました。
でも(b)(c)で分からなかったらまたここに来ますね。
(ということで多分戻ってくることになると思います…)
0068デフォルトの名無しさん
2005/10/18(火) 14:14:12出た解を吟味するのがアルゴリズム的には簡単。
0069デフォルトの名無しさん
2005/10/18(火) 14:17:01真夜中の専門学校???
007065
2005/10/18(火) 14:38:38ありがとうございます。
a.は擬似コード見つけました。
FastPower(a; n):
if n = 1
return a
else
x FastPower(a; bn=2c)
if n is even
return x * x
else
return x * x * a
The total number of multiplications is given by the recurrence T(n) <= T(L n/2 」) + 2, with the
base case T(1) = 0. After a domain transformation, the Master Theorem gives us the solution
T(n) = O(log n).
Incidentally, this algorithm is asymptotically optimal|any algorithm for computing an must
perform
(log n) multiplications.
b.はT(n) <= T(L n/2 」) + 2, T(1) = 0で設定して最終的にO(log n)になるのは分かるのですが
どうやってそれを導きだせばいいのでしょうか?
自分でやると…
T(1) = 0
T(2) = T(L 2/2 」) + 2
= T(1) + 2
= 0 + 2 = 2 (!?) 2^4で掛け算の数が2になるはずですが…(2^2)^2)ですから…あれあれ?
ということで、どうか助けてください。お願いします。m(__)m
0072デフォルトの名無しさん
2005/10/18(火) 15:25:55n is oddのときのは+2、n is evenのときは+1。だからT(N) = T(L n/2 」) + 2
じゃなくてT(n) <= T(L n/2 」) + 2になってるだろ。問(b)の定義でn=2^kに
なっているのでT(n) = T(n/2) + 1になる。
0073デフォルトの名無しさん
2005/10/18(火) 15:45:09うちの大学は情報系の課題は"日付が変わるまで"の先生が多かったけど。
007465
2005/10/18(火) 23:38:06>>72さんの説明を読んでようやく理解し、今問題を終えました。
"<="になっていたのには気付きませんでした。(^^ゞ
b.
T(n) = T(n/2)+1
=(T(n/4)+1)+1
=T(n/4)+2
=(T(n/8)+1)+2
=T(n/8)+3
:
=T(n/2^k)+k
=1 + log2 (n)
≒O(log n)
c.は
brute forceでは
2^8=2*2*2*2*2*2*2*2=8つの掛け算≒O(n)
それに対してdivide and conquerでは
2^8=(2^4)^2=((2^2)^2)^2=3つの掛け算≒O(log n)
O(n) >> O(log n)
ですね。
間に合いました。これから授業です。ありがとうございました!
0075デフォルトの名無しさん
2005/10/19(水) 10:13:170076デフォルトの名無しさん
2005/10/19(水) 11:58:19ttp://www.tensyo.com/urame/prog/linealgo.htm
G=( y2*x1-y1*x2 +y3*x2-y2*x3 +y1*x3-y3*x1 )
Xc= (x12+y12)*(y2-y3)+(x22+y22)*(y3-y1)+(x32+y32)*(y1-y2)/(2*G)
Yc=-(x12+y12)*(x2-x3)+(x22+y22)*(x3-x1)+(x32+y32)*(x1-x2)/(2*G)
にあった。 数値計算なら、3つの円周上の点から半径が最大になる点を求めれば良さそうだが・・・・
0077デフォルトの名無しさん
2005/10/19(水) 23:19:460078デフォルトの名無しさん
2005/10/19(水) 23:22:46007962
2005/10/20(木) 00:34:120080デフォルトの名無しさん
2005/10/20(木) 01:59:030081デフォルトの名無しさん
2005/10/20(木) 17:26:42簡単に引く方法はありますか?
0082デフォルトの名無しさん
2005/10/20(木) 17:45:140083デフォルトの名無しさん
2005/10/20(木) 17:47:370084デフォルトの名無しさん
2005/10/20(木) 22:01:41>>76のページに 2点の中点を通りそれに直行する直線 というのがある
また、
> 3)点(X1,Y1)に一番近い点 {c(cX1-sY1)-s*d,-s(cX1-sY1)-c*d}
を使えば、その点と結べば垂線だ
0085デフォルトの名無しさん
2005/10/20(木) 23:56:473角定規をあてる。
0086デフォルトの名無しさん
2005/10/21(金) 01:16:510087デフォルトの名無しさん
2005/10/21(金) 10:33:10代数学では、3角定規は平行線を描く以外に使っちゃダメだろ習わなかったか?
そもそもアレは90゚なのか?
0088デフォルトの名無しさん
2005/10/21(金) 10:36:150089デフォルトの名無しさん
2005/10/21(金) 11:20:040090デフォルトの名無しさん
2005/10/22(土) 15:26:244行4列の行列
(x**2+y**2,x,y,1)
(x1**2+y2**2,x2,y2,1)
(x2**2+y2**2,x2,y2,1)
(x3**2+y3**2,x3,y3,1)
の行列式 = 0 と置けば出るよな。
0091デフォルトの名無しさん
2005/10/23(日) 10:35:15証明のヒントを下さい。
009290
2005/10/23(日) 13:24:43(x1**2+y2**2,x1,y1,1) (a)
(x2**2+y2**2,x2,y2,1) (b) = 0
(x3**2+y3**2,x3,y3,1) (c)
っていう連立方程式が a, b, c について解けるなら
x^2 + y^2 + ax + by + c = 0
が求める円の方程式になるよね。
解が存在するためには rank が 3 以下じゃなくちゃいけないので
行列式 = 0 が出てくるという寸法。
三点が同一直線上にないっていうことも別途確認する必要もあるね。
0093デフォルトの名無しさん
2005/10/23(日) 15:32:04ありがとうございました。
0094デフォルトの名無しさん
2005/10/23(日) 18:48:380095デフォルトの名無しさん
2005/10/23(日) 19:07:39複素平面上だと
Im((z1-z3)/(z2-z3)*(z2-z4)/(z1-z4))=0
0096デフォルトの名無しさん
2005/10/25(火) 22:00:04アルゴリズムC・新版―基礎・データ構造・整列・探索
R. セジウィック (著), Robert Sedgewick (原著), 野下 浩平 (翻訳), 佐藤 創 (翻訳), 星 守 (翻訳), 田口 東 (翻訳)
この本って買い?
内容とか翻訳の質とか教えてください。
0097デフォルトの名無しさん
2005/10/25(火) 23:15:47Cのコーディングスタイルは疑問なんで、丸写ししたい人向けじゃないです。
0098デフォルトの名無しさん
2005/10/26(水) 00:05:010099デフォルトの名無しさん
2005/10/26(水) 16:52:05そこにある座標がポリゴン内か外か、どういうアルゴリズムになりますか?
0100デフォルトの名無しさん
2005/10/26(水) 17:05:56どっかの学校があそこみて課題出してる?
0101デフォルトの名無しさん
2005/10/26(水) 22:30:360102デフォルトの名無しさん
2005/10/26(水) 22:53:40何言ってる不明
0103デフォルトの名無しさん
2005/10/26(水) 22:55:46工エエェェ(´д`)ェェエエ工
0104デフォルトの名無しさん
2005/10/26(水) 22:58:41ちなみに聞くけど複素数が何か知っていってるの?
0105デフォルトの名無しさん
2005/10/26(水) 23:04:04とか言うなよ?
言ったら笑っちゃうよ?
0106デフォルトの名無しさん
2005/10/26(水) 23:21:58えっと、幾何と代数の意味はわかってるよね?
0107デフォルトの名無しさん
2005/10/27(木) 02:21:08点ABCから成る三角形の内側に、点Pが存在しているか?
いくつか方法あるけど、
内積から以下の角度を求めて、成立していれば内側
( ∠ABC > ∠ABP ) && ( ∠BCA > ∠BCP )
あとは外積から法線の向きで判別する方法とかもある。
0108デフォルトの名無しさん
2005/10/27(木) 06:23:44の次は、 ttp://www.tensyo.com/urame/prog/linealgo.htm
・ 線分の上にあるか?
・ 線分が交わるか?
・ 線分と点の距離
・ 円を水平線で塗り潰す
・ 最小2乗法による直線推定
・ 最小2乗法による円弧推定
・ 面積/重心
・ スプライン
0109デフォルトの名無しさん
2005/10/27(木) 09:30:20結構ムズいんですね。
0110デフォルトの名無しさん
2005/10/27(木) 12:27:06コードは20行にもならないだろう
0111ハーピィ
2005/10/28(金) 14:05:040112デフォルトの名無しさん
2005/11/02(水) 16:26:06O(n)で計算できる夢のようなアルゴリズムはありますか?
0113デフォルトの名無しさん
2005/11/02(水) 17:17:52でもここでは余白が狭すぎて書けません。ごめんなさい。
0114デフォルトの名無しさん
2005/11/02(水) 17:33:49存在しない.
x = (x_1, ..., x_n) としたとき,Σ_{i,j} (x_i x_j) という二次形式がありうるが,
これは項数が n^2 なので,それより小さなオーダーにはできない.
0115デフォルトの名無しさん
2005/11/02(水) 17:53:58では一歩譲ってn^2オーダーだとしても、その中でなんとか
効率よく計算量を減らす方法などはありますでしょうか?
Aが対称行列なので、行列の半分だけを使って2倍しながら計算、
それにxi*a_iiの二乗和を加えるという方法で、なんとか半分程度に
減らすことはできたのですが、もはや削減もここまででしょうか?
0116デフォルトの名無しさん
2005/11/02(水) 18:48:190117デフォルトの名無しさん
2005/11/03(木) 00:53:28それ以下にはできんでしょ。
0118112
2005/11/03(木) 01:46:51FFTのアルゴリズムを理解してないんでなんとも言えませんが、
nが2の累乗みたいな特定の条件下のみで最適化可能というものでも
もしあればありがたいと思いましたが。。
>>117
ごもっともです。
必要なデータを読み出さずに計算なんて神の所業ですよね。
自分の書いたC言語のプログラムが、二次形式を計算する箇所の
for文二重ループたったひとつのせいでむやみやたらと遅くなったもので。。
だいたいnが数百〜数千くらいなんで当たり前っちゃ当たり前なんですが。
二次形式をn*100回以上繰り返し計算するわけですが、今回の場合、
Aはいつも定数で、xは要素のどれか一つだけが更新されているという
条件があって、もう少し計算が省けそうなのでがんばってみます。
0119112
2005/11/03(木) 01:51:08> xは要素のどれか一つだけが更新されているという条件
どれかひとつじゃなくてxの要素はまるごとそっくり
入れ替わっている必要がありました。失礼。
0120デフォルトの名無しさん
2005/11/03(木) 06:53:340121120
2005/11/03(木) 07:16:43行列処理だったら本質的に O(N^2) は避けられないので,それが許せないなら問題に合わせた解法を用意するしかない.
例えば A が問題設定の時点でわかってるならそれを対角化するような座標を選んで O(N) の反復に落とすとか.
0122デフォルトの名無しさん
2005/11/03(木) 08:08:581.SIMD命令で最適化する
2.ループを展開する
0124デフォルトの名無しさん
2005/11/03(木) 15:59:19直方体の空間をm*n*n個の直方体にさいの目状に分割したとします。で一個一個の直方体をセルとします。
例えば一つのセルの大きさを1とすると、
セル(i ,j ,k)は八つの点(i, j, k),(i+1, j, k),(i, j+1, k), (i, j+1, k), (i, j, k+1),, (i, j+1, k+1), (i+1, j, k+1), (i+1, j+1, k+1)
を頂点とする直方体です。(i, j, k = 0, 1, 2, 3...)
この空間内に単位方向ベクトルA(u, v, w)と通る点P(p, q, r)で表される直線を与えたとします。
すると直線は媒介変数表示でP + t*Aとかけると思います。
この直線がどのセルを通過するのか、
またはあるセル(i, j, k)とこの直線が交わるか判別するには
どのように考えたら宜しいでしょうか?
実際には、光線が通過するセルとの2つの交点を求めて、そのセル内での光線の通過距離を計算しようとしています。
0125デフォルトの名無しさん
2005/11/03(木) 16:26:47最終的に作りたいのはプログラムコードなわけですか?
0126デフォルトの名無しさん
2005/11/03(木) 16:42:16・x = iの時j < x < j+1かつk < z < k+1かどうか
・x = i + 1の時j < x < j+1かつk < z < k+1かどうか
といった具合にy = j, y =j+1, z = k, z = k + 1についても調べる。
で通る2点を計算、といった力技なのですが、もう少し手順を減らせそうな気がして・・・
0127デフォルトの名無しさん
2005/11/03(木) 16:53:50まず隣接する直方体をまとめて大きい直方体を作ってその直方体と
光線が交わるならその直方体の中の小さい直方体を調べる、という
やりかたで計算量を減らせると思うよ(八分木、oct tree)。
0128デフォルトの名無しさん
2005/11/03(木) 17:02:22全体の直方体との交点のうち一方を始点に使って。
通過するセルの数は m + n + n よりも小さいし。
0129デフォルトの名無しさん
2005/11/03(木) 17:13:241) あるセル(i, j, k)と直線が交わるか判別する
判別して通ると分かった場合に
2) その通るセルと直線との交点(2つ)を求めて、
そのセル内での光線の通過距離を計算する
ということ?
0130デフォルトの名無しさん
2005/11/03(木) 17:31:15A)全てのセル(m*n*n個)について光線と交わるか判別する→その通るそれぞれのセルについて光線との交点とセル内での光線の通過距離を計算
B)直線の式から通過するセルが分かる夢のような方法→その通るそれぞれのセルについて光線との交点とセル内での光線の通過距離を計算
のどちらかでしょうか。実はプログラミング自体限りなく初心者なので
オクトリー・DDAなどのアドバイスしていただいたアルゴリズムについて勉強してみようと思います。
0131デフォルトの名無しさん
2005/11/03(木) 17:57:31光線を原点から方向ベクトル(1,√2)とすると、
最初の交点の候補は、x=1とy=1になる点(1/√2,1)と(1,√2)だが、
xの小さい(1/√2,1)が最初の交点。
その次の候補点はx=2かy=1のときで(√2,2)か(1,√2)
だが、xの小さいほうをとって(1,√2)
みたいにするとよいのでは。
距離と通ったセルは簡単にわかるだろ。
三次元だと3つから選ぶだけ。
0132デフォルトの名無しさん
2005/11/03(木) 18:16:16x,y,zにだらーって整数を入れてって交点を求めてから、その交点がどのセルに属すかやったほうがよさげ。
0133デフォルトの名無しさん
2005/11/03(木) 18:19:110134デフォルトの名無しさん
2005/11/03(木) 21:14:54"ray march"のようなことがやりたいのかな?
0135124
2005/11/03(木) 23:48:11CGの分野では直線描画の基本らしい「ブレゼンハムのアルゴリズム」というものがヒントになりそうです。
農学系の研究にCGの手法が役立つとは・・・本当に有難うございました。
0136デフォルトの名無しさん
2005/11/04(金) 13:11:07農学って、単位空間あたりの光量の計算とかでもするのかな?
CGでボクセル描画するのだとばっかりおもてたyo
0137フローチャート
2005/11/08(火) 17:16:52フローチャートで書け。
0138デフォルトの名無しさん
2005/11/08(火) 17:22:24pow m n
| n == 0 = 1
| n `mod` 2 == 1 = m * pow m (n-1)
| otherwise = t * t where t = pow m (n `div` 2)
0139デフォルトの名無しさん
2005/11/08(火) 17:32:16CreateGame〜陸海空オンライン〜
ただ今、鋭意開発中!力ある奴だけこい!
0141デフォルトの名無しさん
2005/11/08(火) 19:46:42そのぐらいは自分でやりなさい。そもそも掲示板にどうやって
フローチャートを描けと。
0142デフォルトの名無しさん
2005/11/08(火) 20:29:36○pow(m, n)
│
│n==0
◇─┐
│ ○return 1
│
│n%2==1
◇─┐
│ ○return m * pow(m, n - 1)
│
□t = pow(m, n / 2)
│
○return t * t
0143デフォルトの名無しさん
2005/11/08(火) 20:55:31もっと効率よくできるはずです。やり直しなさい。
0144デフォルトの名無しさん
2005/11/08(火) 20:56:13あと、そのアルゴリズムにはバグが潜んでいます。なおしなさい。
0145デフォルトの名無しさん
2005/11/11(金) 00:09:510146デフォルトの名無しさん
2005/11/11(金) 01:23:17○pow(m, n)
│
□ ret ← 1
│
△ ループ( i=0 ; i<m ; i++)
│
□ ret ← ret*n;
│
▽
│
○ 戻り値 ← ret
0147デフォルトの名無しさん
2005/11/12(土) 04:00:38擬似コードでもいいです。
0148デフォルトの名無しさん
2005/11/12(土) 07:15:530150デフォルトの名無しさん
2005/11/13(日) 11:38:37その代わり解くのには数年間〜数十年間(ry
0152デフォルトの名無しさん
2005/11/13(日) 17:16:000153デフォルトの名無しさん
2005/11/13(日) 18:28:11入力の仕様がわからなかったので,以下の仕様に従うことにした.標準入力から読み込む.
「1行目: 都市の数,2行目から: 都市1 都市2 その間の距離,終端: EOF」
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int inf = 1 << 30;
// brute force using recursion ( O(n!) )
int solve(int pos, int start, vector< vector<int> >& adj, vector<bool>& used) {
used[pos] = true;
int d = inf;
if (find(used.begin(), used.end(), false) == used.end()) d = adj[pos][start];
for (int i = 0; i < used.size(); ++i)
if (!used[i]) d = min(d, adj[pos][i] + solve(i, start, adj, used));
used[pos] = false;
return d;
}
int main() {
int n; cin >> n;
vector< vector<int> > adj(n, vector<int>(n, inf));
int a, b, d;
while (cin >> a >> b >> d) adj[a][b] = adj[b][a] = d;
vector<bool> used(n, false);
int start = 0; used[start] = true;
cout << solve(start, start, adj, used) << endl;
}
0154147
2005/11/14(月) 06:25:03ありがとうございます。仕様はそのとおりでいきましょう。
走らせるために
#define min(a,b) (((a)<(b))?(a):(b))
と
return 0;
を追加しましたが入力の仕方がいまいち分かりません。
都市a bがint型ですよね…。
--------------------------------------------------
3
a b 3
-1073741824
Press any key to continue
--------------------------------------------------
これ↓ではエラーが出て駄目ですし…
--------------------------------------------------
3
1 2 3
4 5 6
Press any key to continue
--------------------------------------------------
どう入力するんでしょうか?m(__)m
0155147
2005/11/14(月) 11:24:19ダメダメな自分でもようやく分かりました。
Ctrl+Qで終了というのが渋いですね。
少し改良しました。
--------------------------------------------------
Number of Cities: 4
Source Destination Distance:
0 1 2
0 2 4
0 3 3
1 2 3
1 3 6
2 3 1
^Q
9
Press any key to continue
--------------------------------------------------
後はもう少しコメントなどを入れて改良してみます。(当然n数は10を超えない程度で)
ありがとうございました!
0156147
2005/11/14(月) 11:58:32#include <iostream>
#include <vector>
#include <algorithm>
#define min(a,b) (((a)<(b))?(a):(b))
using namespace std;
const int inf = 1 << 30;
// brute force using recursion ( O(n!) )
int solve(int pos, int start, vector< vector<int> >& adj, vector<bool>& visited) {
visited[pos] = true;
int d = inf;
if (find(visited.begin(), visited.end(), false) == visited.end()) d = adj[pos][start];
for (int i = 0; i < visited.size(); ++i)
if (!visited[i]) d = min(d, adj[pos][i] + solve(i, start, adj, visited)); //←ここで何か記録しないといけないんでしょうが…
visited[pos] = false;
return d;
}
void main() {
int cities, paths; cout << "Number of Cities: "; cin >> cities; cout << "Number of Paths: "; cin >> paths;
vector< vector<int> > adj(cities, vector<int>(cities, inf));
int a, b, d; cout << " S D Distance" << endl;
for (int i = 0; i < paths; ++i) {
cout << "Path" << i+1 << ": "; cin >> a >> b >> d; adj[a][b] = adj[b][a] = d;
}
vector<bool> visited(cities, false);
int start = 0; visited[start] = true;
cout << "The minimum distance is " <<solve(start, start, adj, visited) << endl;
}
あの、で、最短のルートを表示するにはどうしたらいいんでしょうか?本当にしつこくてすみません。m(__)m
0157デフォルトの名無しさん
2005/11/14(月) 17:58:34グローバルの map<vector<bool>, int> にでも覚えさせておくこと.
表示するときは適当な visited からスタートして,visited = 全部 true になるまで覚えさせた map を辿っていく.
具体的には下みたいな感じにやる.
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/1082.cpp
0158157
2005/11/15(火) 06:58:170159147
2005/11/15(火) 15:43:57ありがとうございます!m(__)mハハァー m(__)mハハァー m(__)mハハァー m(__)mハハァー m(__)mハハァー
再帰の途中で覚えさせる方法が分からなくて困っていました。
なるほど、ああやって割り込むんですね。本当に勉強になります。
solve(i, start, adj, visited)を二回呼んでるのは後でなんとかします。
ああ、もっと賢くなりたい。←自分
0160フローチャート
2005/11/23(水) 20:25:34支払い金額を計算するフローチャートを示せ。ただし、値引き率8%と
消費税5%を考慮すること
0161デフォルトの名無しさん
2005/11/23(水) 20:28:11そりは難しい課題だねえ。
まずはフローチャートを描くルーチンを作成しないと。
環境は何? まさか、線を引くルーチンから作らなくちゃいけない?
0162デフォルトの名無しさん
2005/11/26(土) 17:42:03また、有理数の円未満の端数処理をどうするか検討しないとな。
切捨て?切りage?四捨五入?設定で選択できるようにしないと
実用に耐えないかもよ。
0163デフォルトの名無しさん
2005/11/26(土) 20:15:280164デフォルトの名無しさん
2005/11/26(土) 21:21:570165デフォルトの名無しさん
2005/11/27(日) 18:06:06有理数体上の加減乗除は自明じゃねーの?
0166デフォルトの名無しさん
2005/11/27(日) 21:26:380167デフォルトの名無しさん
2005/11/27(日) 21:35:560168デフォルトの名無しさん
2005/11/27(日) 21:45:260169デフォルトの名無しさん
2005/12/01(木) 12:06:340170デフォルトの名無しさん
2005/12/01(木) 18:13:160171デフォルトの名無しさん
2005/12/04(日) 01:41:03その配列nの中のn-1個の数列を配列nの中だけでソートしたいのですが何かいいアイデアないでしょうか?
つまりデータ構造やポインタは勿論、
二分木や多分木を使ってヒープも駄目ということです。
0172デフォルトの名無しさん
2005/12/04(日) 02:00:230173デフォルトの名無しさん
2005/12/04(日) 03:54:54状況がよくわからん。
具体的に。
0174デフォルトの名無しさん
2005/12/05(月) 16:33:28書物で調べたりググったりしていますが、見つかりません。
0175174
2005/12/05(月) 16:35:590176デフォルトの名無しさん
2005/12/05(月) 16:40:060177174
2005/12/05(月) 16:58:41レスありがとうございます。
二次回帰分析ですと、y=a(x^2)+bx+c のa,b,cを決定するとこになると思われます。
今やりたいことは、例えば y = exp(-3*p)+q^2 に対応する離散データから
(p, q)を求めるというものです。
exp(x)は2次関数ではありませんが、例えばテイラー展開等で近似をすれば、
適応出来る物なのでしょうか?
0178デフォルトの名無しさん
2005/12/05(月) 19:46:30理論的には,s_1, ..., s_n をパラメータとする関数 f(x; s_1, ..., s_n) を
データ列 (x_1, y_1), ..., (x_N, y_N) にフィッティングするときは誤差の二乗和
φ(s_1, ..., s_n) = Σ(f(x_i; s_1, ..., s_n) - y_i)^2
を最小化する s_1, ..., s_n を求めてやればいい.
で,それは結構難しくて,凸関数とか条件付かないと最良解が出る保証は無い.
ある程度の解でいいなら,「勾配法 + アニーリング」くらいで,それなりに求まってくれるはず.
0179デフォルトの名無しさん
2005/12/05(月) 19:50:09イマイチ正確な定義が分かりません。
それか、組み込めるライブラリどこかに落ちてないでしょうか?
0180174
2005/12/05(月) 20:15:07詳しいレスありがとうございます。
今現在では、範囲と精度を与えて、全部の(p, q)について調べ、その誤差の二乗和が
最小になる(p, q)の組を解としています。
勾配法、アニーリングを調べてみて、検討してみます。
0181デフォルトの名無しさん
2005/12/05(月) 20:17:32質問の意味がわからないけど多分スレ違い。
・言語と開発ツールは何を使ってるのか
・具体的にやりたいことは何か
・今自分は何がわからないのか
この三点をはっきりさせて、適切なスレに行って聞いてください。
0182デフォルトの名無しさん
2005/12/05(月) 21:10:48Y = (A(X^3)+B(X^2))/(CX+D)
の最小自乗法を適応するばあい、
残差の2乗和 S に対して
A, B, C, Dそれぞれで偏微分したもの = 0
の連立方程式を解いて、
A = Σを含む式
B = ...
C = ...
D = ...
とすれば良いのでしょうか?
簡単な式の最小自乗法しか使っていなかったので、
そのまま適応して良いものかどうかが分かりません。
お願いします。
0183デフォルトの名無しさん
2005/12/05(月) 21:18:39OK.
ただ偏微分したもの = 0 が陽に解ける保証はどこにもないし,解けたとしても解は一般に複数存在するので
出した解が本当に良いフィッティングになってるかは十分議論する必要がある.
0184182
2005/12/05(月) 21:30:11ありがとうございます。勉強になります。
0185アルゴリズム
2005/12/06(火) 10:20:52ある。これを用いて次のプログラムをBASICで作成しなさい
年齢が30歳以下の人の、体重と身長の平均値を計算し表示する
0186デフォルトの名無しさん
2005/12/06(火) 10:59:370187デフォルトの名無しさん
2005/12/06(火) 12:50:40スレタイくらい嫁。
くだ質スレか宿題スレ池や。
0188デフォルトの名無しさん
2005/12/06(火) 20:36:58エクセルにデータを叩き込んでexpの形で近似曲線出すのが一番手軽な希ガス。
ところでexp()の形になると判ってるなら、logを取ったらどうなる?
0189デフォルトの名無しさん
2005/12/06(火) 21:51:460190デフォルトの名無しさん
2005/12/06(火) 22:09:54ヒント:Windowsとは限らない
0191デフォルトの名無しさん
2005/12/06(火) 22:28:030192デフォルトの名無しさん
2005/12/06(火) 22:34:45ヒント:そもそも汎用機とも限らない 例:宇宙計算用スパコン
だからこそのアルゴリズムスレだろ?
0193デフォルトの名無しさん
2005/12/06(火) 23:14:510194デフォルトの名無しさん
2005/12/06(火) 23:30:440195デフォルトの名無しさん
2005/12/07(水) 19:22:240196デフォルトの名無しさん
2005/12/07(水) 19:55:37y=(A(x^3)+B(x))/(C(x^2)+D)
の関数に最小自乗法を適応することは出来ますか?
残差の2乗和が最小になる(A,B,C,D)を見つけるわけですが、
例えばCで偏微分して=0となるCは、単なる極地のCであり、
それが極小かつ最小となるわけではありませんよね?
0197196
2005/12/07(水) 19:57:51よく見たら>>182とまったく同じ式でした・・・。
当方、学生ではないので課題とかでもないのですが。
同じ書物を読んでいるのかしら。
>>183を参考にします。
無視してください。
0198デフォルトの名無しさん
2005/12/07(水) 20:29:050199デフォルトの名無しさん
2005/12/08(木) 10:14:07その中の3つの点で定義される三角形があって、
ある点がその中か外か判定するアルゴリズム教えて下さい。
0200デフォルトの名無しさん
2005/12/08(木) 11:58:18(0,0), (0,2), (2,0) という要素数3個の2次元配列が与えられた場合、
(1,1) という点がその三角形の中にあるかどうかということだよな?
1)与えられた3点が三角形を構成するかどうかを吟味。
2)その3点から各々2点を取り出し(3通り)、2点を通る直線の式を求める。
3)その3本について、直線で座標平面を分割した場合、残りの頂点を含む領域を不等式(3通り)であらわす。
4)中か外かを判定したい点について、その3つの不等式を同時に満たせば中、そうでなければ外。
0201デフォルトの名無しさん
2005/12/08(木) 12:26:410202デフォルトの名無しさん
2005/12/08(木) 13:04:30できるだけ使い勝手の良いもので満たさなければならない。ナップザックの大きさは限られているので、
どのような荷物で満たすかが非常に大事な問題となる。ナップザック問題とは、ある目的のコストが
最大となるように限られたスペースにアイテム(item)を配置する問題のことである。次の問いに答えよ
*リュックサックに全ての荷物を入れて旅行する人のこと。
問1
0/1 ナップザック問題とは何か?
問2
全てのアイテムが(1)同じコストあるいは(2)同じサイズであればナップザック問題はどん
な問題となるのだろうか?
問3
アイテムのコストが大きさに比例する場合は、ナップザック問題はどんな問題となるの
か?
問4
ナップザックの大きさがアイテムに比べて非常に大きい場合は、一体何が起こるか?参考
書にあるプログラムを使って調べ、現象から生じた問題を指摘し、それが何故生じるのか
記述せよ.
0203デフォルトの名無しさん
2005/12/08(木) 15:35:02ここは君が来るべきスレでは無いよ。
0204デフォルトの名無しさん
2005/12/08(木) 15:59:27いいじゃんべつに。
お前の個人的な感情は出さなくてもいいよ。
そんなもの読んでいる人間には全く価値がないから。
文句があるならどのスレにいけ、ぐらいは言えよ。
あ、頭悪スレとかに誘導するのは全く無意味だからやめてね。
0205デフォルトの名無しさん
2005/12/08(木) 18:15:33つまんないネタ書くのも自由だし
それを批判するのも自由。
0206デフォルトの名無しさん
2005/12/08(木) 18:37:180207デフォルトの名無しさん
2005/12/08(木) 18:40:49自重しろよ。
自由ではないんだよ?あまりひどいとアク禁だ。
0208デフォルトの名無しさん
2005/12/08(木) 19:52:213点から辺の長さ求めてHeronの公式、とか。
0209デフォルトの名無しさん
2005/12/08(木) 20:01:43[v1-v2, v3-v2]/2 の絶対値が面積になるね。
[x,y] は x と y の外積ね。
0210デフォルトの名無しさん
2005/12/08(木) 20:02:07ある点を原点に移動させるように全体を並行移動させて、
(0,0),(a,b),(c,d)の三角形の面積が(1/2)*|a*d - b*c| であることを
使った方が簡単かも。
3点が三角形が作られない位置に無いことを確かめてからね。
0211デフォルトの名無しさん
2005/12/08(木) 20:03:50(>>182の式)≠(>>196の式)
である件について
0212デフォルトの名無しさん
2005/12/08(木) 20:55:54http://www.tensyo.com/urame/prog/linealgo.htm
の多角形の面積でやれば?
0214デフォルトの名無しさん
2005/12/13(火) 18:24:45でも、3点とも座標がわかってて位置不明ってどゆこと?
0215デフォルトの名無しさん
2005/12/13(火) 19:24:25「固定座標じゃない」って意味だろ。
確かに意味は解らないが、気持ちは伝わってきた。
0216デフォルトの名無しさん
2005/12/13(火) 20:30:040217デフォルトの名無しさん
2005/12/13(火) 20:39:02ヘロンの公式をわざわざ使うより
素直に台形公式による閉曲線積分
0218デフォルトの名無しさん
2005/12/13(火) 20:56:04頂点座標?閉曲線積分?言葉はちゃんと使おうぜ
0219デフォルトの名無しさん
2005/12/14(水) 01:18:24任意の三点ってことだろ。
0220デフォルトの名無しさん
2005/12/14(水) 11:53:042つのベクトル a = PQ、b = PR を定義。
(1/2) |a × b|
ただし、×は3次元ベクトルの外積、|| はベクトルの絶対値。
っつーか、ぐぐれ。
http://homepage2.nifty.com/PAF00305/math/triangle/node3.html
0221BASIC
2005/12/14(水) 15:57:56データを1件ずつ、ユーザ定義関数を利用して
「公共料金」を計算させることにします
<水道料金の計算>
基本料金:1250円 定量制料金単価は
・使用量が10立方米以下であれば80円/立方米
・ 〃 10立方米超20立方米以下であれば185円/立方米
・ 〃 20立方米超50立方米以下であれば205円/立方米
・ 〃 50立方米超100立方米以下であれば240円/立方米
・ 〃 100立方米超200立方米以下であれば275円/立方米
・ 〃 200立方米超であれば310円/立方米
(計算例)
使用量が8立方米であれば、1250+8×80
使用量が15立方米であれば、1250+10×80+(15−10)×185
=2050+(15−10)×185
使用量が40立方米であれば、1250+10×80+10×185+(40−20)×205
=3900+(40−20)×205
使用量が75立方米であれば、1250+10×80+10×185+30×205+
(75−50)×240=10050+(75−50)×240
使用量が120立方米であれば、1250+10×80+10×185+30×205
+50×240+(120−100)×275=22050+(120−100)×275
使用量が230立方米であれば、1250+10×80+10×185+30×205
+50×240 +100×275+(230−200)×310 =49550+(230−200)×310
0222デフォルトの名無しさん
2005/12/14(水) 15:58:420223デフォルトの名無しさん
2005/12/14(水) 16:01:00| ∧_∧
|. (・ω・` )スルー
|スス… /J J
↓ ,,, し―-J
0224デフォルトの名無しさん
2005/12/14(水) 16:51:100225デフォルトの名無しさん
2005/12/14(水) 19:15:460226デフォルトの名無しさん
2005/12/15(木) 00:36:360227デフォルトの名無しさん
2005/12/15(木) 04:40:030228デフォルトの名無しさん
2005/12/16(金) 15:42:28m^3と書かないの。
0229デフォルトの名無しさん
2005/12/16(金) 15:51:32メートル=米、だからね。
他にも糎とか粍とか。
でも、普通は立方米と書かずに立米(りゅうべい)と書く希ガス。
#平米は割と一般的でしょ。
0230デフォルトの名無しさん
2005/12/17(土) 12:32:02俺の父親が。
0231デフォルトの名無しさん
2005/12/17(土) 12:34:100232デフォルトの名無しさん
2005/12/17(土) 12:58:32ttp://www.fudemojiya.com/syo/katakana.htm
によると 女 らしい
0233デフォルトの名無しさん
2005/12/17(土) 13:05:23他にもグラムやインチなどにも当てられた漢字があることだし。
0234デフォルトの名無しさん
2005/12/17(土) 19:27:50発案した人も途中からヤケクソになっていったのだと推測
0235デフォルトの名無しさん
2005/12/17(土) 22:42:29そこまでして漢字にせんでもええやん…とおもた。
0236デフォルトの名無しさん
2005/12/18(日) 03:23:45外来語ヲ片仮名ニ割リ当テルトイウ
発想ハ無カッタンダロウナ
0237デフォルトの名無しさん
2005/12/18(日) 04:08:191、2、3、4、5、40、50、60、70 といった代表値である数字があるとします。
で、例えばXがその代表値のどれに一番近いかを求めるとき
すべてを探索すれば答えはわかると思いますが、できるだけ高速に
求めたいと考えたとき、代表地を木にすればいいのではと私は考えました、
例えばXが6だとするとまず、5が一番近いことがわかります
これをどうやって木にしたらいいのかがわかりません。
また1,2、3・・・・といっていましたが
(X,Y,Z)と三次元に増えた場合、一番近い点を見つけるにはどうしたらいいのでしょう?
一致するのを探すのではなく一番近いものを探すので苦労しています。
近さの判定としてはユークリッド距離を用います。
どうぞよろしくお願いいたします
0238デフォルトの名無しさん
2005/12/18(日) 04:13:080239デフォルトの名無しさん
2005/12/18(日) 04:32:56ありがとうございます。
バイナリサーチですと完全に一致する場合は問題ありませんが
完全に一致せず一番近いものを選択するときに問題がおきます
237の例で6に一番近いものをバイナリサーチで探そうとすると
40になると思われます
0240デフォルトの名無しさん
2005/12/18(日) 04:46:58この 40 と X を比較することによって 5 < X < 40 という関係はすぐにわかる。
あとはどちらに近いかを計算するだけじゃないのかな。
0241デフォルトの名無しさん
2005/12/18(日) 04:54:28最終段でヒットしなかった時、left/rightどちらの方が近いかチェックしろ。
n次の場合は、a=f(X,Y,...)で、aの値でソート。
0242デフォルトの名無しさん
2005/12/18(日) 05:01:13>>241
ありがとうございます。
n次の場合はうまくいかないように感じるのですが
できれば具体例を出していただけないでしょうか?
241さんのを自分なりに解釈すると、まずはXについてどれが一番近いか
しらべて次はY、Z・・・というふうなことだと感じているのですが
例えばXがかなり近くてもZ,Yがかなり遠いと総合的な距離は遠いわけで
Xが多少遠くてもY,Zが近ければ総合的な距離は近くなるので
あまりうまくいかなようなきがします。
間違っていたらすみません
0243241
2005/12/18(日) 05:37:33スマソ、完全に寝ぼけてた。
1次以上の距離で探したいのなら、総当りで検索するしかないんじゃね?
0244デフォルトの名無しさん
2005/12/18(日) 05:40:16ありがとうございます。
総当りですか・・・それですと時間がかかるので
何かいい方法がないかなと思いまして
0245デフォルトの名無しさん
2005/12/18(日) 07:16:282次元(平面)ならボロノイ図・近傍で似たような問題がある
3次元以上だとできるかどうか知らない
総当りにしたら
0247デフォルトの名無しさん
2005/12/18(日) 07:55:24ありがとうございます。
ボロノイ図については知っていまして、三次元でも可能のようです。
ですが、これをどう木にすればいいのかよくわからなかったもので
何かいい方法があればと思って相談してみました、。
0248デフォルトの名無しさん
2005/12/18(日) 09:03:12空間データベースって分野のお話だね.
望んだ形でデータを持ってていいなら,k-d tree を使うのが手軽かな.
空間に一点が追加されるたびに,その一点を通る超平面を引き,その超平面のどちら側に
点があるかで二分木を作る.探索は木を手繰りながら範囲を絞り込んで,
その中で全探索をする.最悪 O(n) だけど,適当にばらけてれば O(log n).
ほかにも SR-tree とか SS-tree とか色々あるので,参考になりそうなのを挙げとく:
http://www.kecl.ntt.co.jp/csl/sirg/people/kani/db.html
http://vision.unige.ch/~moennen/publi/moennen_tech0505.pdf
H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley
0249デフォルトの名無しさん
2005/12/18(日) 10:00:28ありがとうございます
望んだ形でデータを持っていても大丈夫です。
K−d tree についてなのですが、これでは一番近い代表値に近似することはできないと
考えられます。
例えば
http://www.kecl.ntt.co.jp/csl/sirg/people/kani/db.html
のk−d tree のところの図で説明しますと
代表地がPと考えると、P4とP5の線の中に点があるのですがP9に
一番近い点(一番近い代表地に近似したい点)があったとすると
これはP4かP5に近似されることになります。
実際はP9に一番近いのにこれには近似されないとおいうことです
木を作る際にP7からでなくP6からはじめたとしても同様の問題はおきると考えられます
しかしR−treeというのは使えそうな気がします
ちょっと読んでみますがいかんせん説明が少ないので理解できるかわかりませんが
なんとかがんばってみます
ありがとうございました
0250デフォルトの名無しさん
2005/12/18(日) 10:04:36のR−treeを読んでみましたがこれでも正確に一番近い代表地に
近似されないように感じます。
うーんどうしよう
0251デフォルトの名無しさん
2005/12/18(日) 10:05:18求めた点までの距離を半径とした点で総当りをその後ですればいいだろう。
たとえば2次元なら x 座標がその範囲にある条件、次にy座標がその範囲にあるという条件で絞りこんで
矩形で絞り込めばいいでしょ
0252デフォルトの名無しさん
2005/12/18(日) 10:07:59たとえば円周上に点が並んでいて、中心に近似しようとした場合など
0253デフォルトの名無しさん
2005/12/18(日) 10:17:52>>252
ありがとうございます。
自分の中で何か新しいアイデアが浮かんできそうな気がします
が、もう少し具体的にお願いできませんか。何かわかりそうな木がするんです
どうかおねがいします
0254デフォルトの名無しさん
2005/12/18(日) 10:25:28母点までのリンクを距離順に並べて持たせておいて
最初に検索した母点までの距離内にあるリンクだけ全検索する
検索する過程で、それより近い点を見つけたら、母点を移して同じ事をする
0255デフォルトの名無しさん
2005/12/18(日) 10:35:34ありがとうございます
私の理解力不足のためわからなかったです すいませんが
もう少し簡単な説明をしていただけないでしょうか どうかお願いします
0256248
2005/12/18(日) 10:53:05二つ目に挙げたテクニカルレポートも読んでね.ちゃんとそっちに作った木から kNN を絞り込む方法について
コメントが入ってるから.参考文献にもそれっぽいのが沢山あるので子引き,孫引きしましょう.
0257デフォルトの名無しさん
2005/12/19(月) 09:08:38アルゴリズムの本に
「図のどれがP、NP、NP完全(NPCと呼びます)のクラスについての私たちの知識と矛盾しているか?
"=Which of the diagrams do not contradict the current state of our knowledge
about the complexity classes P, NP, and NPC (NP-complete problems)"」
という質問があってヒントに
「これらのうちの二つのみが現在の私たちの知識と矛盾している
"=Just two of them do not contradict the current state of our knowledge about the complexity classes."」とあります。
「私たちの知識」とはその本に載っている
「もしP≠NPなら、PでもNP完全でもないNP問題があるはずだ
"=It is known that if P≠NP, there must exist NP problems that neither are in P nor are NP-complete."」
っぽいです。
図は五つあって、そのうち
aはP=NP=NPCで、bはNPCがP=NPの部分集合になっており、dはPとNPCが重なった形でNPの部分集合になっており、
これらは明らかに矛盾しているので除外です。
eは↓のサイトにも載っている一般的に知られているベン図ですから矛盾していません。
ttp://www.jyi.org/volumes/volume10/issue2/articles/widjaja.html
で問題のcなんですが、これは↑のサイトに載っている図のPとNPCが
NPを真っ二つにして占めており、まったく隙間がありません。(想像できますか?)
これも矛盾してますよね?PでもNP完全でもないNP問題がないといけないんですから。
そうだとしたらこの本の間違いなんですが…。
ここの賢い人、どうか答えてください。せめてヒントだけでも…。
0258257
2005/12/19(月) 09:19:37c. NP
┌─────┬─────┐
│ │ │
│ P │ NPC │
│ │ │
└─────┴─────┘
てな感じです。
0259257
2005/12/19(月) 09:23:48「図のどれがP、NP、NP完全(NPCと呼びます)のクラスについての私たちの知識と矛盾して『いない』か?」
と
「これらのうちの二つのみが現在の私たちの知識と矛盾して『いない』」
です。もう後で逝ってくるつもりです。m(__)m
0260デフォルトの名無しさん
2005/12/19(月) 10:19:49すみません
0261デフォルトの名無しさん
2005/12/19(月) 13:34:18「PでもNP完全でもないNP問題がないといけない」はあくまで「P≠NPならば」
であって、「P≠NP」とは限らない。
0262257
2005/12/20(火) 12:17:51ありがとうございます。
なるほど、「P≠NP」とは限りませんよね。
もしそうだとすれば選択肢は「P=NP」しかない訳で
その場合は「PでもNP完全でもないNP問題があろうがなかろうが関係ない」
と解釈してよいのでしょうか?
友達の一人は「『P=NP』は『現在の私たちの知識』に矛盾していないか?
図a, bはP=NPだから簡単に矛盾していると判断できたんじゃないか。
cがP=NPとするなら矛盾していると判断するべきだろう?」と問いかけてきました。うーむ。
すみません、自分、人より脳が少し足りないようです。
また説明お願いします。m(__)m
0263デフォルトの名無しさん
2005/12/20(火) 14:31:12現在の多くの人たちの『考え』には矛盾しているが、それは『知識』ではない。
P=NPは、我々が馬鹿なだけですべてのNP問題は実は多項式時間で
とくことが出来ると言うこと。そんなことはないだろうと思うかもしれないが、
多項式時間で解くことの出来ない問題があることを証明できていない現在、
P=NPは矛盾しているとはいえない。
0264257
2005/12/21(水) 12:01:14なるほど、ようやく分かりました。
すべてのNP問題が(近似解とかではなく)
多項式時間で解けるようになったら面白いでしょうね。
天寿を全うするまでに見たいものです。
ありがとうございました!
0265デフォルトの名無しさん
2006/01/09(月) 00:12:140266BASIC
2006/01/09(月) 16:12:52ある。これを用いて次のプログラムをBASICで作成しなさい
体重が60kg以上で、身長が150cm未満の人の名前を表示する
0267デフォルトの名無しさん
2006/01/09(月) 17:34:000268デフォルトの名無しさん
2006/01/09(月) 17:54:080269デフォルトの名無しさん
2006/01/09(月) 18:15:01VBとかでもいいとすれば随分アレだ
0270デフォルトの名無しさん
2006/01/09(月) 19:08:23http://www.sagami.ne.jp/tadaka/99Basic/
0271デフォルトの名無しさん
2006/01/11(水) 03:29:11(n*m)回の微分演算という時間を喰う処理を少しでも短くしたいです
もしくは優れたJacobianMatrixクラスの例をご存じであれば是非!
0272デフォルトの名無しさん
2006/01/11(水) 06:49:10定数オーダーでの最適化は計算モデルに依存するので議論できん.そもそもおまいが微分をどう実装してるかもわからんし.
O(nm) すら許せないなら,問題に応じてアドホックに解決するっきゃ無いと思うがなあ.どんな問題解いてるんだ?
0273デフォルトの名無しさん
2006/01/11(水) 10:57:45LZのスライド辞書みたいに、演算した組み合わせを辞書に登録しておいて、
次回以降は演算を省くってのはどうだろう?
辞書の検索にかかる時間を何らかの方法(連想配列とか)で短縮する必要はあるだろうけど。
0274271
2006/01/12(木) 12:31:26早いレスどうもです!
>>272
やはりO(nm)回は「本質的に」避けられないわけですよねー・・・
微分の差分近似をループでnm回やるつまらない実装なんで、
工夫できないかなと思った次第だったのですが。
ちなみに問題は非線形関数の最小値探査みたいな感じです
>>273
んー、いいアイディアなんですが今回は
適用できないような気がします、ゴメンナサイ
ただ、そのうち他の問題で使えそうな気がするんで、
そのネタはもらって覚えておきます! ありがとう!
0275デフォルトの名無しさん
2006/01/14(土) 00:48:34最小化したい非線型関数になんか条件付けないと定数レベルの最適化もつらいような
0276デフォルトの名無しさん
2006/01/31(火) 17:55:550277デフォルトの名無しさん
2006/02/01(水) 03:14:47ライブラリも何も、大した計算じゃないじゃん。
0278デフォルトの名無しさん
2006/02/01(水) 12:32:21世の中に存在するアルゴリズムの中で複雑と言えるものがどれだけある?
0279276
2006/02/01(水) 12:44:240280デフォルトの名無しさん
2006/02/01(水) 13:38:16このスレでも簡単な例がいくつか
>>178
>>182
>>196
非線形になってくるとちょっとめんどい
http://en.wikipedia.org/wiki/Gauss-Newton_algorithm
http://en.wikipedia.org/wiki/Levenberg-Marquardt_algorithm
ここら辺を参考に
0281デフォルトの名無しさん
2006/02/02(木) 02:20:31FFTになると、ライブラリが欲しい程度には複雑だと思う。
0282デフォルトの名無しさん
2006/02/02(木) 08:51:05どれだけある?という問いにFFT1個かよ。
0283デフォルトの名無しさん
2006/02/02(木) 09:25:21世の中に存在するアルゴリズムがどれくらいあるのか教えてくれたら答えてあげるよ。
0284デフォルトの名無しさん
2006/02/02(木) 13:43:210285デフォルトの名無しさん
2006/02/02(木) 14:58:57各分野毎にはいろいろとあるだろうけど。
画像エフェクト、サウンドエフェクト、3D系演算とか。
0286デフォルトの名無しさん
2006/02/02(木) 15:52:22難しくはないが複雑ではあるよな。
0287デフォルトの名無しさん
2006/02/02(木) 22:26:580288デフォルトの名無しさん
2006/02/05(日) 09:27:32円に適用するだけでも、厄介だし、
直線に適用しようとしたって、実はけっこう難しいよ。
たとえば、2次元画像から直線部を取りたいとしたら、学校でやるようなXとかYでの偏微分じゃ、それこそ偏る。
残差って何って所から取り掛からないとね。
そして、余程単純じゃないと、たいていは方程式1発で解けるという事にはならない。
数値解で求める事になるだろうな
0289デフォルトの名無しさん
2006/02/06(月) 07:09:38ただの偏微分でしか説明しないのって,相当ひどい学校だと思う
0291デフォルトの名無しさん
2006/02/06(月) 14:14:46最小二乗法はロバストでないのでそのあたりは考慮しないと。
例えば、y=x上に完全に点が並んでいる状態で、
たった一点(1,10000)が入ってきただけでy=2xとかになると困るわけだ。
0292276
2006/02/06(月) 14:22:510293288
2006/02/07(火) 06:30:36だから、最小2乗法を使うなら、何を最小にするのかって所が肝心って事さ
直線を求めるのにしたって、数表上と2次元データとは誤差の意味が違う
数表上なら結果の誤差を最小にしたいし
2次元なら直線からの誤差を最小にすると同時に回転変換で結果が変わらない必要がある
0294デフォルトの名無しさん
2006/02/09(木) 11:57:070295sage
2006/02/09(木) 21:45:420296デフォルトの名無しさん
2006/02/11(土) 17:31:27順序統計量を使うのだと思うのですが、帰納法を使って証明するのかどうか分かりません。
どなかか説明してもらえないでしょうか?よろしくお願いします。
高校の時に教師が言っていたんだけど急に思い出して・・・・おねがいします。
0297デフォルトの名無しさん
2006/02/11(土) 18:07:41/ ● ●
|Y Y \
| | | ▼ | パクッ
| \/ ____人__|
| |∨∨∨∨∨ ←296
\ \∧∧ )
| | |\  ̄ ̄\\\
| | |  ̄ ̄ ̄ し し/
(__)_)
0298デフォルトの名無しさん
2006/02/11(土) 18:33:39今適当に考えただけだから間違ってるかもしれないけど。
0299デフォルトの名無しさん
2006/02/11(土) 18:40:590300デフォルトの名無しさん
2006/02/11(土) 18:45:05いや、漏れが覚えている限りでは違うと思われ。
MITだかどっかの教科書の奴に載ってた。二番目を求めるけども一番最小を求めてからだったはず
院試にでてたかも。
0301デフォルトの名無しさん
2006/02/11(土) 18:57:23やっぱり違ってた。考え直したら、
nが偶数なら (3/2)*n - 2,
奇数なら (3/2)*n - 3/2 回だった。
0302デフォルトの名無しさん
2006/02/11(土) 20:58:20ソートアルゴリズムのところとかかな?学部生の時に必死こいてやったけどもう忘れた・・・。
あの教科書は原書で読んだ方がいいかもしれんな。英語だからかなりめんどくさいが。半期でやるのを英語でやったら一年半かかったよ。
0303デフォルトの名無しさん
2006/02/12(日) 00:24:160304デフォルトの名無しさん
2006/02/12(日) 03:01:20完全二分木でトーナメントを考えよう。
一番小さい要素を見つけるのにn-1回の比較が必要。
二番目に小さい要素は一番小さい要素の対戦相手のどれか。
木の高さはceil(log n)で木の一番上には対戦相手はいないから、
二番目に小さい要素の候補たりえるものはceil(log n)-1個
この中から一番小さいものをみつけるのにceil(log n)-2回の比較が必要。
したがって比較回数は、
(n-1)+ceil(log n)-2<n+logn-2
ただし、ceil(x)はxの小数点以下切り上げの関数
0305デフォルトの名無しさん
2006/02/13(月) 00:39:26なるほど。
それは比較は少ないけどコピーがメモリが多く必要になりそうなんだけど
どうなんだろう。
0306デフォルトの名無しさん
2006/02/13(月) 06:11:400307デフォルトの名無しさん
2006/02/14(火) 10:30:15実装の話はしてないんだよね。実際にこの比較回数で動くプログラムを作るのは
結構困難な気がするし、普通の 2n 回比較に定数倍で負けそう。
0308デフォルトの名無しさん
2006/02/27(月) 09:33:06N個をランダムに選んで1にするアルゴリズム。
(残りの32−N個は0)
賢い人教えて。
0309デフォルトの名無しさん
2006/02/27(月) 11:33:45そのサイズの乱数を一個生成するだけじゃいかんの? C なら rand() とかで。
それとも乱数生成のアルゴリズム自体を聞いてるの?
0310デフォルトの名無しさん
2006/02/27(月) 12:12:401)組み合わせの数の計算方法が判らない
2)乱数と、その全部の組み合わせを対応させる方法が判らない
のだろうと思うんだけどね
0311デフォルトの名無しさん
2006/02/27(月) 12:28:33とか、そういうことではないの?
0312デフォルトの名無しさん
2006/02/27(月) 12:35:07rand って完全にランダムじゃなくて、
下位ビットほど短い周期性持ってるから、
rand() & 31 はあんまりよくない。
(rand() >> 16) & 31 とか、何ビットかシフトするの推奨。
0313デフォルトの名無しさん
2006/02/27(月) 12:38:20random()でもMTでも好きなの使えばいいんじゃない?
0314デフォルトの名無しさん
2006/02/27(月) 12:41:56まあそうだけどね。
>>308 がそんな判断できると思えなかったんで、一応補足のつもり。
0315308
2006/02/27(月) 13:09:4116本を中心にした正規分布になってると思うんだけど、
必ずN本になるようにしたい。
3本とか30本とかってのはたまにしか発生しないし。
N回ループで一度使った数は記憶させとくとかっていう
愚直なのは思いついたんだけど遅そうなので聞いてみた。
0316デフォルトの名無しさん
2006/02/27(月) 15:31:210317デフォルトの名無しさん
2006/02/27(月) 20:50:08ですね。
1〜32の間で離散一様乱数発生させたものをa_0、
1〜31の間の乱数をa_1、1〜30の間をa_2として、
初期値は0で左からa_0番目のビットを1にする。
以降左からa_k番目の0のビットを1にする。
~~
0319308
2006/02/28(火) 09:58:33連投ごめん。
0320308
2006/03/01(水) 16:40:570321デフォルトの名無しさん
2006/03/01(水) 17:19:36これ以上議論するなら,「速い」をきっちり定義してもらわないと.
特に乱数生成のコスト,各ビットを参照するコストなどが無いと,
どっちが速いかなんて比較できんよ.
0322デフォルトの名無しさん
2006/03/02(木) 11:59:32それの配列番号を乱数で選ぶ事だね
0323デフォルトの名無しさん
2006/03/02(木) 12:53:162^32 / 2 (0≤N≤16 だから半分) = 2G×4Byte = 8GB
何を使って動かすつもり?
0324デフォルトの名無しさん
2006/03/02(木) 16:39:38それは、順番を考慮した場合のアルゴリズムだから違うようだけど
結果はN個のビットだから、どの組み合わせも等確率で発生するから問題ないのか
>>323
Nを固定すれば 最大の組合せ数は N=16の時で その1/4程度の容量だから最近のPCなら入るんじゃないの?
組み合わせの数ってどの程度だろ?
32!/N!/2^N では大きすぎるな
0325デフォルトの名無しさん
2006/03/02(木) 16:43:14たとえば32個中3個が1の組み合わせを F(32,3) のように書くと
先頭ビットが0 なら 残りは F(31,3)
先頭ビットが1 なら 残りは F(31,2)
という事で
F(N,M)=F(N-1,M)+F(N-1,M-1)
0326デフォルトの名無しさん
2006/03/02(木) 17:23:15ttp://ja.wikibooks.org/wiki/%E9%AB%98%E7%AD%89%E5%AD%A6%E6%A0%A1%E6%95%B0%E5%AD%A6A_%E5%A0%B4%E5%90%88%E3%81%AE%E6%95%B0%E3%81%A8%E7%A2%BA%E7%8E%87#.E7.B5.84.E3.81.BF.E5.90.88.E3.82.8F.E3.81.9B
0327デフォルトの名無しさん
2006/03/02(木) 18:34:31http://www.google.co.jp/search?q=32!/(16!*16!)
601 080 390
って事か
Σ M C n =2^M って事になるんだな
0328デフォルトの名無しさん
2006/03/02(木) 18:39:51なのに >>317の方法は 順列 で 32!/16! という事で、16! の重複があるから、なんか重そうに見えるという事?
0329デフォルトの名無しさん
2006/03/03(金) 07:29:430330デフォルトの名無しさん
2006/03/03(金) 07:50:10max1:=data[0];
max2:=data[1];
if max2> max1 then swap(max1,max2);
min2:=max1;
min1:=max2;
for i:=low(data)+2 to High(data) do begin
if data[i] > max2 then begin
if data[i] > max1 then max1:=data[i] else max2:=data[i];
end;
if data[i] < min2 then begin
if data[i] < min1 then min1:=data[i] else min2:=data[i];
end;
end;
こんな感じでは?
0331デフォルトの名無しさん
2006/04/18(火) 07:42:35ban(0) ban(1) ban(2)
ban(3) ban(4) ban(5)
ban(6) ban(7) ban(8) //盤面 位置関係はこんな感じ
turn //ターン数 最初は1
プレイヤーAのターン開始
↓
Aが指定しかつその場所に当たる変数(真ん中ならban(4))が0であるならばそれに(turn×10)+プレイヤーの番号
(Aは1、Bは2とする。)を代入。
↓
turn>6ならば、次のことを行う。
banの中で下1桁がプレイヤーの番号と等しいもののなかで、一番小さいものに0を代入
↓
banに縦横斜めに自分の番号が並んでいるならば勝利
↓
turnに1を足し、Aのターンを終了、Bのターンになる。
で、できるだけ強いCOMのアルゴリズムを考えてほしいのです。
お願いします。
0332デフォルトの名無しさん
2006/04/18(火) 13:54:180333デフォルトの名無しさん
2006/04/22(土) 16:23:12ゲーム木使って実際に解いてみたら。
EXPTIME完全か知らんが、3×3ぐらいなら解けるだろ。
終盤6個そろってからの場合の数は
9*8*7*6*5*4 = 60480
回転と対称で重なるものを除くと
60480/8 = 7560
リーチがかかってかつ自分の手番のような自明な場面を除けばもっと少なくなる。
自分の手番でダブルリーチをかけられる状態であれば勝ち。
双方最善を尽くしたとき、ループに陥れば引き分け。
0334デフォルトの名無しさん
2006/04/22(土) 17:08:220335デフォルトの名無しさん
2006/05/22(月) 17:26:540336デフォルトの名無しさん
2006/05/22(月) 17:37:121、点列を楕円の一部として近似する事
2、楕円の周長を近似計算する事
どっち?1はとても難しい 円ならまだ方法があるが
0337デフォルトの名無しさん
2006/05/22(月) 17:56:27これをやりたいです。
0338デフォルトの名無しさん
2006/05/22(月) 18:20:03ttp://www.tensyo.com/urame/prog/linealgo.htm
ここの円弧推定が良い方法だと思える。
普通は、円との誤差を s=√{(x−x0)^2 +(y−y0)^2}−r と置くが
これだと非線形で解かなければならない。
(x−x0)^2 +(y−y0)^2−r^2 とすれば数値解が簡単に求まるというものだ。
楕円の場合は、検索すれば出ると思うが、円よりさらに厄介だ
0339AVL木
2006/05/22(月) 20:52:10からっぽのAVL木に入れていくとどうなりますか?誰か教えてください。
0340デフォルトの名無しさん
2006/05/22(月) 21:41:440341デフォルトの名無しさん
2006/05/25(木) 18:54:440342デフォルトの名無しさん
2006/05/25(木) 20:20:09f:=x->cos(PI/2*x)^2
f(f(f(x))), x=-0.5..1.5
0343デフォルトの名無しさん
2006/05/31(水) 01:36:13Direct 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
http://research.microsoft.com/~awf/ellipse/
http://research.microsoft.com/~awf/ellipse/ellipse-pami.pdf
一応 Java 実装もあるけどコードがちょっと汚いかも。
0344デフォルトの名無しさん
2006/07/28(金) 23:01:36プレーヤの歩いた軌跡が、あらかじめ引いてある直線にどれくらい近いかを数値化するにはどうしたらいいでしょうか?
(x,y)座標を取って計算をすればよいらしいっていうのはなんとなくわかるんですが
具体的にどういった計算をすればいいかご教授願います
ちなみに最小二乗法だと、
\
/
\
/
このように蛇行した場合も直線に近似されてしまうのでダメですよね・・・
0345デフォルトの名無しさん
2006/07/28(金) 23:26:48軌跡が直線に近いってのは、どういうこと?
0346デフォルトの名無しさん
2006/07/28(金) 23:37:46最小二乗法で相関係数みりゃいいだろ。
0347デフォルトの名無しさん
2006/07/29(土) 00:13:17数値を求めたいんだろう?
最後の行が意味不明だぞ
0348344
2006/07/29(土) 00:16:20http://www.uploda.org/uporg461782.gif
この画像のように、どれだけ直線に近い動きをしたか、ということを
直線との接触時間などからではなく、座標から軌跡と直線との近さを計算したいのです。
>>346
相関係数ですか、調べてみます
ありがとうございます
0349デフォルトの名無しさん
2006/07/29(土) 15:15:39「軌跡と与えられた直線の距離の自乗を最小にする」でいいんじゃないの?
0350デフォルトの名無しさん
2006/08/10(木) 08:08:24Σ(Yi^2)/N とか
軌跡の2次モーメントとか
0351デフォルトの名無しさん
2006/09/15(金) 13:37:190352デフォルトの名無しさん
2006/09/16(土) 00:36:410353デフォルトの名無しさん
2006/10/18(水) 22:34:05float 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を使わずに正規化するにはどうすればいいのでしょうか?
どうしても速度が気になります。
自分でも考えてみましたが分かりませんでした。よろしく御願いします。
0354age
2006/10/18(水) 22:38:490355デフォルトの名無しさん
2006/10/18(水) 23:04:16ΣΣ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次補間法の計算式なのですが,どのようにプログラムで書いたら良いのでしょうか?
0356デフォルトの名無しさん
2006/10/19(木) 00:02:01>どうしても速度が気になります。
本当に気になる速度なのかどうか、まず実測してみたらどうでしょう。
sqrtを使わなければできないと思いますけど。
本当にsqrtが速度的にネックであれば、高速のsqrtを自前で作るとか。
ただし、精度を犠牲にしてのことですけど。
Newton法でのsqrtの近似の場合、ループは高々20回くらいです。(誤差1.0e-15で)
まずは実測です。
0357デフォルトの名無しさん
2006/10/19(木) 00:08:310358デフォルトの名無しさん
2006/10/19(木) 01:37:21まず環境晒そうや。
CPU、使用言語、必要精度、それらの情報も無しでアドバイスなんて出来ん。
0359デフォルトの名無しさん
2006/10/19(木) 10:20:45精度にもよるけどせいぜい3−5回ぐらいじゃなかったか?
20回もまわすか。
0360デフォルトの名無しさん
2006/10/19(木) 10:52:10double a = 1.0;
double eps = 1.0E-10; /* 精度 */
while (abs(a * a - x) > 1.0E-10) {
a = 0.5 * (a + x / a);
}
return a;
}
0361デフォルトの名無しさん
2006/10/19(木) 10:56:57http://www.google.co.jp/search?q=fast%20sqrt
0362デフォルトの名無しさん
2006/10/19(木) 12:32:48そのコードで3−5回
1.0E-15で9回ってところ
確かに20回もありえるけど、極端な言いぐさは信用されないな。
0363デフォルトの名無しさん
2006/10/19(木) 13:16:19Intel系ならニュートン法使うより、素直に浮動小数点命令を使った方が速いだろ。
SSE乗ってるならaddss/mulss/rsqrtps辺りでまとめて計算できるし。
0364デフォルトの名無しさん
2006/10/19(木) 13:44:45その計算式のままだと思うけど…
アルゴリズムの入力と出力は理解できてる?
(入力は格子状の標本点における f の値 (二次元の double 配列) と補間すべき点の座標 (u0, v0) で、出力は (u0, v0) における補間値)
0365デフォルトの名無しさん
2006/10/19(木) 16:36:190366デフォルトの名無しさん
2006/10/19(木) 17:01:18具体的なコードが欲しいなら
具体的な入力形式を指定した方がいいと思うよ。
(これは大学の宿題か何かですか?)
0367デフォルトの名無しさん
2006/10/19(木) 17:19:03#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;
0368デフォルトの名無しさん
2006/10/19(木) 17:22:41printf("倍率を入力");
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);
0369デフォルトの名無しさん
2006/10/19(木) 17:23:35height =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);
0370デフォルトの名無しさん
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));
}
0371デフォルトの名無しさん
2006/10/19(木) 17:24:59for(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;
}
}
0372デフォルトの名無しさん
2006/10/19(木) 17:27:390373デフォルトの名無しさん
2006/10/19(木) 17:50:330374デフォルトの名無しさん
2006/10/19(木) 21:39:46・宿題の趣旨を理解していないバカ
・「初心者」と書けばなにをしても許されると思ってるバカ
・構造化出来ないバカ
・ざっと見ただけでもコンパイルが通らないのが解るコードを晒すバカ
久々に悪寒が走るほど汚ぇコード見たわ。
0375デフォルトの名無しさん
2006/10/19(木) 22:12:120376デフォルトの名無しさん
2006/10/19(木) 23:37:57これ、たぶん宿題出した先生が書いたコードだと思うんだけど、
大学の先生 (特に年配の人) って結構こういうコード書くのよ。
漏れが習った人も FORTRAN が最初だったらしくてこんな感じだった。
理論とかに関してはすごく頭切れるんだけどね…。
0377デフォルトの名無しさん
2006/10/20(金) 01:36:50・携帯のノリで顔文字使ってるやつは2ch初心者
0378デフォルトの名無しさん
2006/10/20(金) 10:59:23>nt = floor(i/bai);
キャストしる。
>R[(unsigned char)nt][(unsigned char)nn]
このキャストは意味あるの?
元画像が縦横どちらか256pixel超えると破綻すると思うけど。
それとも、charが16bitか32bitの処理系?
マジで講師の書いたコードだとしたらヤバイな。
こんなの習った奴が卒業して、新人として入社してくるんか・・・orz
0379デフォルトの名無しさん
2006/10/21(土) 13:02:51結構いるよね
原理が分かるんだからいいじゃん,
コード読みやすくするのは各自勝手にやってくれとか思ってそう
0380デフォルトの名無しさん
2006/10/21(土) 14:37:21FORTRAN のパラダイムのままで C とか Java 書くのなんて当たり前。
0381デフォルトの名無しさん
2006/10/21(土) 15:04:240382デフォルトの名無しさん
2006/10/21(土) 15:28:340383デフォルトの名無しさん
2006/10/21(土) 15:58:180384デフォルトの名無しさん
2006/10/21(土) 16:11:20その当時、専門でなかった人材を無理矢理ソフトウェア開発に回した、という背景があるからじゃない?
そういう年寄り連中は基礎的な事を学ばずに、現場たたき上げで今までやってきたけど、そのツケが今に回ってきてる。
0385デフォルトの名無しさん
2006/10/21(土) 16:31:020386デフォルトの名無しさん
2006/10/21(土) 17:07:54普通は、新しいこと出来ないってのを今までの経験からくる勘とかで補うんだけど、
>>384 みたいな背景があるんじゃ、この業界じゃほんとにゴミになりかねんな、年寄り。
0387デフォルトの名無しさん
2006/10/21(土) 19:36:38ただし、ITドカタじゃそれが特別速く押し寄せるってこと。
0388デフォルトの名無しさん
2006/10/21(土) 20:05:52アメリカでは職種は変わらない。
0389デフォルトの名無しさん
2006/10/21(土) 20:48:270390デフォルトの名無しさん
2006/10/22(日) 00:03:00まあ、だってさ、管理職って多人数は必要ないわけじゃん。
全員が管理職にはなれないだろ。
って、話題がなんかマ板臭いな。
0391デフォルトの名無しさん
2006/10/22(日) 00:13:510392デフォルトの名無しさん
2006/10/22(日) 13:56:19その話の最後は、「国が必要もない公共工事をいつまでも続けるのはなぜなのか」に落ち着くぞ。
0393デフォルトの名無しさん
2006/10/22(日) 22:12:320394デフォルトの名無しさん
2006/10/22(日) 22:13:440395デフォルトの名無しさん
2006/10/22(日) 23:30:040396デフォルトの名無しさん
2006/10/22(日) 23:53:11小規模のDBなら偏っても問題無いし、大規模DBならいまどきツリー使ってないだろうし。
ターゲットはどこらなん?
0397デフォルトの名無しさん
2006/10/23(月) 00:33:080398デフォルトの名無しさん
2006/10/23(月) 00:43:13三下土方に職を与える為
に落ち着くぞ
0399デフォルトの名無しさん
2006/10/23(月) 00:45:39どうせ大半は地震でぶっ壊れるし。
いやいやゼネコンの小遣い稼ぎでしょう。
0400デフォルトの名無しさん
2006/10/23(月) 02:05:37日本語だと、2色木って言われることの方が多いような、red-black tree。
>>396
要素の挿入・削除時にちょっと処理が増えるけど、
要素の探索時にはペナルティなしで、
木の高さが必ず log n オーダーに抑えられる。
数百〜数万程度のデータ扱うときにはすごい効率いいと思うよ。
C++ の map とか C# の SortedDictionary は2色木使ってる。
Java の Hashtable も、名前に反して実装は2色木じゃなかったっけ?
0401デフォルトの名無しさん
2006/10/23(月) 16:39:560402デフォルトの名無しさん
2006/10/23(月) 18:36:230403デフォルトの名無しさん
2006/11/17(金) 17:26:34また、そのポリゴンに穴が開いている場合も対処できるアルゴリズムはありますか?
1週間ほど調べているのですが埒があかなくて。。。
0404デフォルトの名無しさん
2006/11/17(金) 18:51:11凹なら凹部と別の頂点で分割して凸にする。
0405デフォルトの名無しさん
2006/11/18(土) 03:15:54単調多角形の三角形分割をして O(n) で解けることが知られている。
まともな計算幾何の本ならだいたい書いてあるとおもうが。
0406デフォルトの名無しさん
2006/11/18(土) 03:21:410407デフォルトの名無しさん
2006/11/18(土) 12:45:18y_1 < y_2 < ... < y_k, y_k > y_{k+1} > y_{k+2} ... > y_n となること。
つーか本嫁。
0408デフォルトの名無しさん
2006/11/18(土) 21:06:08ぐぐっても日本語の解説が見つからなかったよ。
とりあえず並列処理用のアルゴリズムらしいのは
わかったけど。
http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html
0409403
2006/11/19(日) 15:10:28ありがとうございます。
なんとなくわかりました。
ただ、本屋に行ってみて計算幾何の本をいくつか見てみたのですが、どの本がよいかよくわからなくて...
もしお勧めがあれば教えていただけないでしょうか。すみません。
0410デフォルトの名無しさん
2006/11/19(日) 15:57:59http://www.cs.mu.oz.au/498/notes/node35.html
これじゃだめ?
・row columnにわける(row数,column数はプロセッサ数の定数倍に近いほうがよいだろう)
・奇数rowで昇順ソート偶数rowで降順ソートをする
・columnで昇順ソートをする
何回かやってるとできるはずなのでできたら取り出す
なんでrowのソートで逆にする必要があるのかな...
0411デフォルトの名無しさん
2006/11/19(日) 19:39:16http://www.amazon.co.jp/gp/product/476490277X/
http://www.amazon.co.jp/gp/product/4795263213/
0412デフォルトの名無しさん
2006/11/19(日) 20:20:48ありがとうございます!
早速買ってこようとおもいます。本当にありがとうございました。
0413デフォルトの名無しさん
2006/11/19(日) 20:44:17int型で要素数2^16程度だと何回か繰り返してみたが25倍程度遅く、
2^32程度だと1回のテストで1000倍程度遅かった。
coreが1個だとオーダも悪いね。n個もcoreがあるなら、
quick sortでも順次分けていけるようなきがするし、
メモリを飛び飛びにアクセスして書き換えるから並列処理にも合ってない気がする。
0414デフォルトの名無しさん
2006/11/19(日) 21:06:23データの数と同じだけプロセッサがあるなら、
バブルソートでも O(n) でしょ、確か。
その Shear ソートも、そういう前提の下で O(√n) とかではないの?
0415デフォルトの名無しさん
2006/12/13(水) 12:06:49こういうプログラムを作りたいのですが、どうアルゴリズムを組めばいいのかわかりません。
どなたかお願いします。
例
インプット
数字集合:5,7,10,12,15
指定値:18
↓数字集合の組み合わせで、『指定値』以上かつ最小の組み合わせを求める。
アウトプット
最小合計値の組み合わせ:7+12=19
0416デフォルトの名無しさん
2006/12/13(水) 12:34:57アルゴリズムを説明すれば自分でプログラム書けるの?
プログラム書いてほしいとか言うのは宿題スレいってくれ
0417デフォルトの名無しさん
2006/12/13(水) 12:50:260419429
2006/12/13(水) 13:26:11http://pc8.2ch.net/test/read.cgi/tech/1165943509/22/
0420デフォルトの名無しさん
2006/12/13(水) 14:16:15Subset Sum Problem という有名 NP (の、最適化問題版)。
まあバリエーションといえばそうなんだけど、知ってて損はない名前よ。
0421デフォルトの名無しさん
2006/12/13(水) 14:37:220422415
2006/12/13(水) 15:15:11お手数おかけしました。
>>417>>420
有名な問題なのですね。
名前自体しらなかったです。
>>421
集合の全合計値より、指定値が小さいという意味ならそうです。
0423デフォルトの名無しさん
2007/01/23(火) 17:46:53sqrtの計算量わかる人いますか
0424デフォルトの名無しさん
2007/01/23(火) 19:59:02sqrt( O(N^2) の処理 ) という記号の意味がわからん。処理の平方根って何。
具体的にどんなことをしているかを書いたほうが正しい解が得られると思われる。
0425デフォルトの名無しさん
2007/01/24(水) 00:00:12ニュートン法なら一回の反復で桁数2倍
0426426
2007/01/24(水) 15:42:39このようなカラーピッカーを作りたいのだけれど、
中心からの位置によってどのようなRGBに変換されるかの式がわかりません。
どうやって計算しているのでしょう?
0427デフォルトの名無しさん
2007/01/24(水) 15:46:57ttp://image-d.isp.jp/commentary/color_cformula/HSV.html
Hが円角度 Sが円半径 Vが隣の垂直バー じゃねーかな?
0429デフォルトの名無しさん
2007/01/24(水) 16:01:43変な色マップになったら 同サイトの HLS変換も試してみてね
0430426
2007/01/24(水) 16:58:12おかげさまで出来ました。atanの戻り値[-pi/2,pi/2]を[0,360]に変換するのにミスったのと
427さんに紹介してもらったページのFの式が間違っていた(正しくはF = H/60 - I)ので
ちょっとだけ手間取りましたが、無事きれいなカラーサークルになりました。
ありがとうございました。
0431デフォルトの名無しさん
2007/01/24(水) 17:14:290432デフォルトの名無しさん
2007/01/24(水) 17:32:150433デフォルトの名無しさん
2007/01/24(水) 17:36:370434デフォルトの名無しさん
2007/01/24(水) 19:08:190435デフォルトの名無しさん
2007/01/24(水) 19:27:160436デフォルトの名無しさん
2007/01/26(金) 06:11:36一つの配列内で重複する数は無い。
同じ数がそれぞれの配列で同じ位置にあるとは限らない。
で、一方の配列内に入ってる数が全て他方の配列にも入っているかを確認したい。
こういう場合で配列をそれぞれソートして
先頭から最後まで一致するかを調べる以外に何かいい方法ある?
0437デフォルトの名無しさん
2007/01/26(金) 07:12:23O(n log n) が計算量下界であることが知られている.
よって,計算量的には 436 のソート比較は最適.
ハッシュとか確率的アルゴリズムとかで実用的な速度は
上がるかもしれんが,ソート比較が簡素で良いと思うよ.
0438デフォルトの名無しさん
2007/01/26(金) 09:06:29なるほど。
ありがとう。
0439デフォルトの名無しさん
2007/01/26(金) 09:26:09データの範囲が狭ければ有無の配列(データが添字)を使ってO(n)で可能
データに対して有効なハッシュ関数があれば広くても同上
0440デフォルトの名無しさん
2007/01/27(土) 00:38:31>>439
>>437でハッシュと聞いてピンと来た。
機会があれば今度その方法も試してみるよ。
ありがとう。
0441デフォルトの名無しさん
2007/02/02(金) 14:13:280442デフォルトの名無しさん
2007/02/04(日) 11:48:52もしかして:ビットの[配列]
0443デフォルトの名無しさん
2007/02/04(日) 14:05:22アルゴリズムと実装は区別しような
分からなかったらスレッド名も見てくれ
0444デフォルトの名無しさん
2007/02/04(日) 23:26:47言葉遊びがしたいのか?
アルゴリズムと実装でいうならどう実装をしようが配列は配列
最適化の話がしたいならアセンブラスレでも逝け
0445デフォルトの名無しさん
2007/02/05(月) 00:44:54444=441 ?
とりあえず君の配列の定義が知りたい。
アルゴリズム論の文脈では、実装における配列と理論における
配列はまったく対応しない可能性があるけど、それは大丈夫?
0446デフォルトの名無しさん
2007/02/05(月) 10:54:45ビットマップ=ビットの配列
でFAだろ
0447デフォルトの名無しさん
2007/02/05(月) 12:10:450448デフォルトの名無しさん
2007/02/08(木) 15:47:29一回の硬貨のやり取り(渡す枚数+受け取る枚数)を最小にするアルゴリズム
考えているんだけど思いつかない・・・助けてくれ
0449デフォルトの名無しさん
2007/02/08(木) 16:32:47int 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;
}
0450デフォルトの名無しさん
2007/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;
アルゴリズムを考える時はまず、最も分かりやすい方法(しらみつぶしとか)を考えるといいと思います。
それでダメならそれから工夫する事を考えればいいのですが、大抵はそのままでも大丈夫です。
#「硬貨のやり取りが最小」とは別に紙幣を払ってもいいのですね。
0451デフォルトの名無しさん
2007/02/09(金) 22:24:47特に条件が指定されてないので
0452デフォルトの名無しさん
2007/02/09(金) 22:28:43常識で考えれ
1円札を999枚使うんだ
0453デフォルトの名無しさん
2007/02/10(土) 08:59:48>1円札を999枚使うんだ
現在有効なお金
ttp://www.boj.or.jp/type/list/yuko/okane.htm
一円券は今でも有効だから使用は違法ではないし
常識で考えて不可能というわけではないな。
つまり「現在発行されている」という条件がない限り、
硬貨のやり取りは常に0が最小というわけだ。
一本取られたな。
0454デフォルトの名無しさん
2007/02/10(土) 14:08:010455デフォルトの名無しさん
2007/02/10(土) 14:24:420456デフォルトの名無しさん
2007/02/10(土) 14:26:340457デフォルトの名無しさん
2007/02/10(土) 15:35:02はっきり言わせてもらうと、一円札程度なら、札束で無いと誰も買わないよ。
0458デフォルトの名無しさん
2007/02/12(月) 20:53:260459デフォルトの名無しさん
2007/02/12(月) 22:02:58使用された期間
現存数
等は少なければ少ないほど良い
どんなにいらなそうな物でもコレクターにとっては価値がある
0460デフォルトの名無しさん
2007/02/13(火) 03:28:54天皇陛下御在位60年1万円硬貨とか。
0461デフォルトの名無しさん
2007/02/13(火) 10:21:210462デフォルトの名無しさん
2007/03/03(土) 14:04:362次元空間上に重複して平面が沢山(簡単のため長方形で)ありました。
ある点を選んだとき、その位置を含む平面の集合が欲しいのですが、
どんなアルゴリズムがいいでしょう?
よくある問題っぽいですね、もし問題に名前がついてたら、それだけでも
教えていただけると助かります。
0463デフォルトの名無しさん
2007/03/03(土) 15:16:32たとえばA4用紙の束かなんかを床に撒き散らしてから、ピンを一本床に突き刺す。
ピンが刺さっている紙を全部調べよう
って問題?
0464デフォルトの名無しさん
2007/03/03(土) 17:58:17ピンを横に置くんじゃないの?
0465デフォルトの名無しさん
2007/03/04(日) 09:59:17普通かな?2次元だと正方形や可変サイズのグリッドとか
ツリー状(検索を対数的なオーダーに減らす)にしておくとかいろいろ種類はあるよ。
0466デフォルトの名無しさん
2007/03/04(日) 10:41:11平面を全部領域別けして、その領域にリンクリストで平面を割り付けるのが簡単じゃないのかな
0467デフォルトの名無しさん
2007/03/04(日) 11:15:36五十周年金貨ってなかったよね?
0468462
2007/03/04(日) 18:16:513次元に拡張するために、かなりの広さで使うため、グリッドにするのは無理なもので、木にできると嬉しいです。
実装は難しくてもかまいません。
0469デフォルトの名無しさん
2007/03/04(日) 19:08:06今適当に考えただけだけど
最初に排他的な長方形の集合を探してR1とする
(多い方がいいけど最大独立点集合問題はNP困難なので適当でいい)
R1に含まれてない長方形の中から排他的な集合を探してR2とする。
これを再帰的に繰り返す。
点が与えられたらR1から順番にどの長方形に入ってるか調べればいい。
全部の長方形が重なってたらそれぞれ1つの要素からなる集合になるから
結局全部チェックしなきゃいけなくなってしまうのでダメ。
もっといい方法があるのかもしれん。
0470デフォルトの名無しさん
2007/03/04(日) 19:10:09両方に属する平面があってもよいが、できるだけ2分するような超平面を選ぶ。
探索は点がどちらの超空間に属するかを調べて属するほうの平面集合を総当りで調べる。
これで全部の平面を総当りよりおよそ1/2の計算量になる。
あとはこれを再帰で最終的に完全二分木に近い形で分割できればOK。
0471462
2007/03/05(月) 01:18:32その場合平面が両方の空間に属すると、両方の枝に平面を登録することになるわけで。
例えば一番最後に全部を覆う大きさの平面が入ってきたら、その平面を分割しまくら
なくちゃいけなかったり、データ量が問題になるかな、というのが現在の悩みです。
0472デフォルトの名無しさん
2007/03/05(月) 03:30:57単一の構造にする必要性も無いし、BSPは静的なものだけにすればいいし。
0473デフォルトの名無しさん
2007/03/05(月) 20:42:16・一方の空間に完全に属する領域の集合(2つ)
・断面と交わる領域の集合
の3つに分けてみるのはどうか.こうすれば各領域は必ず一箇所に属する.
探索するときは,断面上の領域と点の落ちる空間内の領域の2つを調べる.
断面と交わる領域の格納は
数が少ないとき(多分,n < (log(n))^d'(d'は断面の次元)のとき)は単純なリスト
数が多いときは1つ次元を落とした同様の構造にする
よくわからないけど最終的には
(log(n))^d (dは次元)←適当
あたりになりそうな気がする.
0474デフォルトの名無しさん
2007/03/05(月) 21:19:27なぜ一般次元に拡張を…
応用が利くのは良いっちゃあ良いんだけど微妙
0475462
2007/03/06(火) 01:07:58大きいというか、重複が多い場合に結構問題になるんです。
今回は空間全ての領域で少なくとも3枚は被さっているのを想定してるんで、
必要な記憶領域がかなり大きくなってしまうという。
>>473
あ、そうか、2つとも探索すればいいんですね。
1次元で紙に書いてみたら、いけそうな感じです。
記憶領域はO(n)ですね、計算量もちょい大き目のlog(n)っぽい。
よーし、明日の夜にでも組んでみます。
0476デフォルトの名無しさん
2007/03/06(火) 20:33:21特定(ry
0477デフォルトの名無しさん
2007/03/06(火) 21:20:05そうじゃないならどこかで打ちきるわけだから計算量は何分の一かになるだけ
それに重なってるところは分割できないので結局全探索になる
0478462
2007/03/07(水) 00:33:13い感じに動いています。ありがとうございました。
0479デフォルトの名無しさん
2007/03/07(水) 23:42:48高卒でしかも数II?とか勉強いたことない俺にはまったく理解できないんだが
どうすりゃいい?
0480デフォルトの名無しさん
2007/03/07(水) 23:44:26諦める
0481デフォルトの名無しさん
2007/03/08(木) 00:10:43余り気付かれていないが、高校生ではなくても高校レベルの数学を
勉強することはできる。
0482デフォルトの名無しさん
2007/03/08(木) 07:00:17おまえ他人の言ってる事理解してないよ
でしゃばるなカス
0483デフォルトの名無しさん
2007/03/09(金) 00:58:56理解できてないといって理由を書かない
0484デフォルトの名無しさん
2007/03/10(土) 23:39:52そういう曲線を計算するアルゴリズムはありますか?
0485デフォルトの名無しさん
2007/03/10(土) 23:47:55一般的なところで、一次回帰とその応用である対数回帰指数回帰冪乗回帰、それと二次回帰程度知ってればなんとでもなる。
0486484
2007/03/10(土) 23:49:18すれを汚してすいませんでした。
0487デフォルトの名無しさん
2007/03/10(土) 23:50:07キーワードありがとうございます。
調べてみます。
0488デフォルトの名無しさん
2007/03/11(日) 02:21:41048951
2007/04/15(日) 21:22:27ttp://homepage2.nifty.com/bkclass/doc_sha1.html
のサイトを見ていたのですが、
他に参考になるサイトはありませんか?
0490デフォルトの名無しさん
2007/04/15(日) 21:54:510491デフォルトの名無しさん
2007/04/24(火) 04:03:280492デフォルトの名無しさん
2007/04/26(木) 00:56:22でも、ノイズなんかの問題で理論的に最適な解が微妙な場合だったり、
問題が小規模で全探索で十分満足できる結果が得られるなら、全探索が
安定してるし実装が楽だからいいね。木構造はメモリリークよくやっち
ゃうし。
0493デフォルトの名無しさん
2007/04/26(木) 01:28:590494デフォルトの名無しさん
2007/04/26(木) 05:30:170495デフォルトの名無しさん
2007/05/01(火) 21:40:37何方かこの3問のフローチャートがかける方が居ましたら教えてください
1問目:成績判定1
アルゴリズムの点数を入力して、80点以上のとき「A」、60点以上80点未満の時「B」、60点未満の時「C」
と出力するフローを答えなさい
2問目:成績判定2
英語と数学と国語の点数を入力して英語の点数が80点以上、または数学と国語の点数がどちらも80点以上の時、「合格」と出力し、そうでない時「不合格」と出力するフローを答えなさい。
なお、数学と国語の点数がどちらも80点以上の時を一つの選択処理にすること
3問目:成績判定3
2-12.成績判定2の選択処理の部分を一つにまとめなさい
選択処理部分
英語の点数が80以上、または数学と国語の点数がどちらも80点以上の時、「合格」と出力し、そうでない時「不合格」と出力する
0496デフォルトの名無しさん
2007/05/01(火) 21:50:36そんくらいのフローチャートは基礎中の基礎だろ。本見ればわかるだろ。
0497デフォルトの名無しさん
2007/05/01(火) 22:19:410498デフォルトの名無しさん
2007/05/01(火) 22:34:38ttp://www.cs.takushoku-u.ac.jp/caed/kisosemi/k7/FlowChart.html
これみりゃ大体わかるだろ。
いまどきフローチャートを書かせる問題ってのも、どうかと思うけれど。
スレ違いsage
0499デフォルトの名無しさん
2007/05/03(木) 14:45:412chで質問する前にググれよ。っていうか授業ちゃんと聞いた上で
わからないのであったら講師や友達に聞け。
0500デフォルトの名無しさん
2007/05/03(木) 19:47:24友達いる香具師
は
2chで質問しない
0501デフォルトの名無しさん
2007/05/04(金) 00:08:570502デフォルトの名無しさん
2007/05/04(金) 18:07:540503デフォルトの名無しさん
2007/05/09(水) 01:56:23それはそうとA*探索はぐぐるのが難しい。
0504デフォルトの名無しさん
2007/05/09(水) 10:12:59「Astar探索」とかでググってみたら?
ちなみにA*の場合、heuristicsがadmissible(各ノードから目的地までの予測コストが実際のコストを決して上回らない)でconsistent(いわゆる三角不等式が成立)なら、必ず最適解を返すよ。
それよりも良いってのは、heuristicsを設計できない場合ってこと?
0505デフォルトの名無しさん
2007/05/10(木) 07:32:410506sage
2007/05/11(金) 04:14:25そうですね、良いヒューリスティックを設計できない時です。
近似解法含め、良いのを探してます。
>>505
たしかに「良い」ってのはアバウトでした^^;
主観的にでも、よさげなアルゴリズムがないかなぁと。
検索してもダイクストラばっかり引っかかるもので。
0507デフォルトの名無しさん
2007/05/11(金) 04:15:480508デフォルトの名無しさん
2007/05/13(日) 10:47:07だとしたら、厳密最短路はたぶん理論的には Dijkstra が最良で、
実用的にはヒューリスティックに頼るってのが現在の理解だと思う。
(現在行われてるコンテストでもそんな調子だよね)
近似最短路はヒープ操作を手抜いたり、三角不等式を気にせずに
ヒューリスティックを突っ込んだりするくらいだけど、
グラフが何の性質も持たない場合は性能評価が難しいところ。
0509デフォルトの名無しさん
2007/05/13(日) 16:40:430510デフォルトの名無しさん
2007/05/13(日) 16:44:370511503
2007/05/13(日) 18:40:21を用意した時、A*(と色々な改良版)が最速ってことですか。
というか、授業で習ったダイクストラとA*しか知らない物で^^;
近似についても、微妙な改良版くらいしかないって事ですね。
0512デフォルトの名無しさん
2007/05/13(日) 19:42:30とにかく実行速度をなんとかしたいという実用的な要求なら、
問題にあったヒューリスティックとヒープを設計して A* が
たぶんもっとも現実的だと思う。
近似は、微妙な改良版といっても、たとえば幾何グラフとかなら
普通の Dijkstra と比較して一億倍以上早くなるケースもザラなので、
具体的な問題を見ないとなんともいえないところ。
0513503
2007/05/15(火) 01:35:21します。ちなみに問題は経路探索です。
0514デフォルトの名無しさん
2007/05/15(火) 22:13:04ちなみに、カーナビの経路探索だと、ネットワーク側の方を階層的にいくつか持って切り替えることによって高速化してる。
現在地、目的地近辺では全道路のネットワークで探索、それで見つからなければ国道以上のネットワークに移って探索、
さらに探索する場合は高速道路のみのネットワークに移って探索、みたいな感じ。
もちろん最適解は出ないけど、そもそもカーナビの場合、計算で出てくる最適解が、ドライバーにとって最適になるとも限らないしね。
0515503
2007/05/15(火) 23:00:45はそれが理由なんだ。
0516デフォルトの名無しさん
2007/05/16(水) 01:49:50渋滞回避してるだけだろう
0517デフォルトの名無しさん
2007/05/29(火) 07:24:16上記スレで強制NaNの計算でインテル不利にするベンチが論争を呼んでますが
極端にAMD不利にする方法を探しています。
では。
0518デフォルトの名無しさん
2007/07/10(火) 16:03:47たとえば521を21で割るとき
↓
まず521が三桁で20が二桁だから答えも二桁だろう
↓
2桁目を決めよう
↓
答えは10かな?21*10=210で521より小さい
↓
じゃ20かな?21*20=420<521
↓
じゃ30かな?21*30=630>521(もし90でも超えなければ二桁目は9にする)
↓
大きくなったからおそらく答えの2桁目は2だろう
↓
次は1桁目・・・
こんなのを考えたのですが、もっと良い方法はないですか?
0519デフォルトの名無しさん
2007/07/10(火) 16:04:240520デフォルトの名無しさん
2007/07/10(火) 17:02:290521デフォルトの名無しさん
2007/07/10(火) 20:02:17だったら時間掛かるだろ
0522デフォルトの名無しさん
2007/07/10(火) 21:23:37せっかく苦労して自分で考えついたとしても
それが既にみんなが普通に使ってるものと同じやそれ以下だったら悲しいだろ?
0523デフォルトの名無しさん
2007/08/15(水) 23:41:39に記述されている、
図4の(a)から(b)の結果はどのようなアルゴリズムになりますか?
0524デフォルトの名無しさん
2007/08/16(木) 00:12:410525デフォルトの名無しさん
2007/08/18(土) 19:37:21B+木やB*木というものが存在するとに書いてありますが、
どういったものですか?
>(厳密にはB木の改良型であるB+木やB*木を使うことが多い)
0526デフォルトの名無しさん
2007/08/18(土) 20:07:24B* は B で、子の比が 1/2 だったところを 2/3 にしたもの
wikipedia の情報は不正確だから参考にすんな
ちゃんとした教科書とか論文を参照すれば分かるだろ
0527デフォルトの名無しさん
2007/08/18(土) 22:38:43ありがとうございました。
ウィキペディアから引用したら怒らせてしまった様で。
たまたま名前が載ってたから出しただけです。
B+木B*木は名前だけは以前から知ってましたが、
ググっても関係しそうなのは引っかからないですね。
本は
アルゴリズム事典
はじめてのアルゴリズム入門
アルゴリズムとデータ構造
など持ってますが、載ってないみたいです。
>教科書とか論文
できればこれのポインタ教えてください。
0528デフォルトの名無しさん
2007/08/18(土) 23:24:10誰が怒っているの?
0529デフォルトの名無しさん
2007/08/19(日) 03:52:13できればこれのポインタ教えてください。
0530デフォルトの名無しさん
2007/08/19(日) 07:29:10B-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
(http://www.cl.cam.ac.uk/~smh22/docs/ubiquitous_btree.pdf)
0531デフォルトの名無しさん
2007/08/19(日) 18:25:09って判断はどこら辺ですればいいですか?
使い分ける時の基準みたいなのが知りたい。
0532デフォルトの名無しさん
2007/08/19(日) 19:19:15どんな用途に使おうとしてるか分からないので、普通の設定で一般的な話をする。
赤黒木は、本質的にはブロックサイズの小さな B 木なので、
あなたの質問は B 木のブロックサイズをどう選ぶか、という質問と同じ。
普通の実装では、n 個の要素を格納するブロックサイズが b の B 木から
要素を検索には O(log (n/b)) 回の木上の探索(ランダムアクセス)と
O(b) 回のブロック内の探索(シーケンシャルアクセス)が必要となる。
ここで雑な計算をするとブロックサイズは、木上の探索の速度と
ブロック内の探索の速度の比くらいに選ぶのがよいことが分かる。
木が丸ごと全部メモリに乗るような場合は、木のアクセスもブロックの
アクセスも同じくらいなので、ブロックサイズも小さく選ぶのが良い。
一方、ハードディスクやネットワーク上のデータベースのような
木のアクセスが遅く、ブロックのアクセスが早い場合は、
ブロックサイズも大きく選ぶのが良い。
0533デフォルトの名無しさん
2007/08/19(日) 19:50:280534デフォルトの名無しさん
2007/08/19(日) 19:54:510535デフォルトの名無しさん
2007/08/19(日) 21:04:070536デフォルトの名無しさん
2007/08/19(日) 21:04:430537デフォルトの名無しさん
2007/08/19(日) 21:37:32わかりませんと言え
0538デフォルトの名無しさん
2007/08/19(日) 21:40:560539デフォルトの名無しさん
2007/08/19(日) 21:41:290540デフォルトの名無しさん
2007/08/19(日) 22:26:02メモリが・・
なんとかなりませんか?
0541デフォルトの名無しさん
2007/08/19(日) 22:59:510542デフォルトの名無しさん
2007/08/28(火) 05:58:02ネット上にこれを実装したソースコードが公開されてない(見つからない・・・)のでどなたか教えてください。
__
_|_ |
| |_|_|
|__|
ポリゴン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++でも良いので、どなたか、お知恵を拝借させてください。
0543542
2007/08/28(火) 06:00:14図形ずれちゃった・・・
__
_|_ |
| |_|_|
|__|
ポリゴン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)
こうです。
0544デフォルトの名無しさん
2007/08/28(火) 09:44:30悪いこと言わないから別の方法考えたほうがいいと思う。
塗り分けるだけなら市町村別のデータでも構わないわけだし。
で、
コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用 ISBN 476490277X
の第 2 章にアルゴリズムは載ってる。でも、ここから実装まで持っていくのもそう単純じゃないと思う。
あと、オープンソースライブラリの CGAL にそういう機能はある。
http://www.cgal.org/
Reference Manual の VI Polygon and Polyhedron Operations 辺り。
0545542
2007/08/28(火) 21:33:57コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用 ISBN 476490277Xの第2章 早速読んできました。
例題に挙げられてるのも地図でよさそうだったけど、
プログラミング言語を限定してないアルゴリズムとしての本なんで、
やろうとしていることを実装するには、どういうプログラムを書けばよいのかまでは踏み込めなそうです。
せめて
i ← S1 と S2 の交点
みたいなのがあればなぁ。
CGALのマニュアルも読んでみました。joinあたりのコードか数式が出ていればVBAでも実装できそうなんですが・・・
>悪いこと言わないから別の方法考えたほうがいいと思う。
そうですねー。
ただ、ポリゴンをくっつけるのはもうちょっと粘ってみます。考えるのも楽しいので。
市町村同士は重ならないので、
・辺と辺が重なっている(隣り合っている)ところを見つけてくっつけていく
・中抜きはこの際無視
というように簡単なものを作る方針で考えてみます。
重なりまで考えて汎用的なアルゴリズムにしようと思ったけど、結構しんどそうですので・・・
どうもありがとうございましたー。
0546デフォルトの名無しさん
2007/08/29(水) 01:21:12時間計算
分時間を入力して○時○分に変換して出力するフローのaとbに該当する処理を記述しなさい。
なお、計算結果は整数部のみとし、小数部は切捨てとなる。
余り(X%Y)で除数の余りを求めることができる。[例、余り(100%3)は1となる]
例:117分の時 1時間57分
(開 始) 何方かa bに入る答えがわかる方いましたら教えてください
↓
(データ)・・分時間を入力
↓
(処理)・・a 時を求める
↓
(データ)・・時を出力
↓
(処理)・・b 残りの分を求める
↓
(データ)・・分を出力
↓
(終了)
0547デフォルトの名無しさん
2007/08/29(水) 01:28:010548デフォルトの名無しさん
2007/08/29(水) 01:39:280549デフォルトの名無しさん
2007/08/29(水) 01:54:03b・・・分時間%60
0550デフォルトの名無しさん
2007/08/29(水) 03:31:39宿題はスレ違い
しかも回答もらって礼も無しかよ
0551デフォルトの名無しさん
2007/08/29(水) 19:38:32単純に考えればsinθのθが何であれ計算時間は変わりませんが、
速度面でチューニングが施されているであろうライブラリではどうなんでしょう?
0552デフォルトの名無しさん
2007/08/29(水) 23:22:57ここで間違ってる
関数近似の教科書読むべし
0553デフォルトの名無しさん
2007/08/29(水) 23:30:11すみません、悠長に教科書読んでる暇がないので結論をお願いします
0554デフォルトの名無しさん
2007/08/29(水) 23:36:55ただ,どれもθを0〜π/2の範囲に正規化してるだろうから
その範囲なら少し速いはず
これ以上は本嫁
0555デフォルトの名無しさん
2007/08/30(木) 01:07:360556デフォルトの名無しさん
2007/08/30(木) 07:24:15絶対的な速度が問題なのではなく、速度のむらを気にしているのです。
たとえばsin(0.1)を計算するのに1μsかかったとして、sin(0.2)では5μsかかったりするのか?ということです
>>555
ターゲットはマイコンなのでそういう容量食いな方法は取らないような気がします。
ターゲットはSH7145
ルネサスのコンパイラを使ってます。
ただ、ピンポイントでこのコンパイラに通じている方がいるとは考えにくいので
VCやgccだったらどうなのかという意見でもいいのでお願いします。
0557デフォルトの名無しさん
2007/08/30(木) 09:28:070558デフォルトの名無しさん
2007/08/30(木) 10:04:11実測するのが手っ取り早いかと
0559デフォルトの名無しさん
2007/08/30(木) 17:45:37マイコンの方がむしろテーブル変換使用すると思うが
0560デフォルトの名無しさん
2007/08/30(木) 17:47:40いっそπ/8に正規化するとか
0561デフォルトの名無しさん
2007/09/09(日) 14:05:26>悠長に教科書読んでる暇がないので
そうか。残念だったな。
0562デフォルトの名無しさん
2007/09/12(水) 02:03:16結局これ求めてどうなるんですか?
馬鹿でも分かるようにく教えてください。
0563デフォルトの名無しさん
2007/09/12(水) 08:42:09そんな限られた分野でしか使わないようなものを
さも誰もが知ってるかのように聞かなくても。
自然言語処理とかで使う。
Google 先生とかがよくやってる
もしかして: ○○
を出したりとかに使える。
0564デフォルトの名無しさん
2007/09/13(木) 00:02:29レスどうも。
2つの文字列を比較して"n文字違います"とかは想像できるんだけど、
diffみたいに異なるものを表示するとかの処理にはどうやって組めばいいんだろうと思って、、、
0565デフォルトの名無しさん
2007/09/13(木) 00:05:36http://ja.wikipedia.org/wiki/Diff
0566デフォルトの名無しさん
2007/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]を拡張したもの。複数のロバスト解を同時に発見する場合に有効。
ガウスノイズ
アルゴリズムは簡単。
ガウスノイズは上に述べたシックスシグマ法を使ったときよりもすばやく収束できる。
吸収現象などのせいでロバスト解からずれた位置に収束するかもしれない。
0567デフォルトの名無しさん
2007/09/19(水) 03:20:29y=Ax (x,y:ベクトル, A:マトリックス,大きさ数百〜数万)
に対し,
x = inv(A) * y
を解く問題を考えています.
ここで,逆行列演算inv(A)がO(N^3)のコストが掛かり,ネックになっています.
いま,Aは疎な帯行列(しかも対称)という条件があるので,
大幅な計算削減ができるのではないか?と考えております.
例えば,計算コストをO(N^2)にするといったことは可能でしょうか?
キーワードだけでも良いので,知恵を貸していただけると幸いです.
0568デフォルトの名無しさん
2007/09/19(水) 03:49:220569デフォルトの名無しさん
2007/09/19(水) 07:22:57LU使っているのか?
対称行列だと、LDL分解でOK
帯行列だとさらに、0要素を見ないことで、さらにスピードアップ
0570デフォルトの名無しさん
2007/09/19(水) 17:36:110571567
2007/09/20(木) 01:53:07キーワードありがとうございます!
調べてみます.
>>569
LU分解→直接法で逆行列としていました.
LDL分解というものがあるのですね.
解法は反復法に持って行くのですかね・・・調べてみようと思います.
反復法は精度の面が少し気になりますが,勉強含めて試してみます.
多謝!
>>570
数値計算の門外漢なもので・・・勉強してきます.
0572デフォルトの名無しさん
2007/09/24(月) 22:11:260573デフォルトの名無しさん
2007/09/28(金) 09:44:52要素数が一方がk個,もう一方が2個の場合,
n回の比較でマージできる最大のkをanとすると
a[n] = [sqrt(2*a[n-1]*(a[n-1]+1))] # []: Gauss記号
で与えられるらしいのですが
これがどういうアルゴリズムでマージしたときの物なのか,
またこれが最良値なのか知りたいのですが, 誰か知りません?
0574デフォルトの名無しさん
2007/09/29(土) 14:28:02a[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]の式とオーダーは合っている。
0575573
2007/09/30(日) 13:03:48考えてくれてありがとう.
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
との事.
0576デフォルトの名無しさん
2007/10/30(火) 01:16:41ハッシュのみだとデータの衝突回数
多い場合ってどうやってみんななら解決する?
あとね、kd木で何の本に詳しく載ってますか?
0577デフォルトの名無しさん
2007/10/30(火) 01:55:310578デフォルトの名無しさん
2007/10/31(水) 02:27:51完全ハッシュ化するソースコード置いてある
とこないですか?
0579デフォルトの名無しさん
2007/10/31(水) 21:09:370580デフォルトの名無しさん
2007/11/28(水) 05:05:510581デフォルトの名無しさん
2007/11/28(水) 06:17:511点を基準に他2点へ直線を引くときの傾きが一緒だったらOK。
x軸と垂直だった場合なんかも考慮すると、
(x1-x0)*(y2-y0)==(x2-x0)*(y1-y0)
0582デフォルトの名無しさん
2007/11/28(水) 13:05:520583デフォルトの名無しさん
2007/12/07(金) 21:54:02[N]の配列を2つ使ってる場合の使用領域のオーダーってO(n^2)におさまります?
0584デフォルトの名無しさん
2007/12/07(金) 22:02:420585デフォルトの名無しさん
2007/12/09(日) 21:31:140586デフォルトの名無しさん
2007/12/14(金) 13:42:55C言語でおねがいしたいです。
0587デフォルトの名無しさん
2007/12/15(土) 02:12:2223457円になります。
0588デフォルトの名無しさん
2007/12/29(土) 03:46:49セルを全て見つけたいのですが、どうしたら効率よく求まるでしょう?
0589デフォルトの名無しさん
2007/12/29(土) 06:33:27格子が座標と平行になるように回転変換して 格子間隔が1になるように伸縮して
円の中心座標の小数点以下座標を見ればいいだけでは?
0590デフォルトの名無しさん
2007/12/29(土) 07:51:56さらに辺の長さを1で仮定してしまいましょか。
えーと意味がいまいちつかめないんですが、
>格子が座標と平行になるように回転変換、格子間隔が1になるように伸縮
これは元々が単位格子であるなら何もしないでOK?
>円の中心座標の小数点以下座標
これで、なぜ全ての格子が求まるかがわかりません。
整数部をみれば、中心を含む格子は求まると思いますが。
0591デフォルトの名無しさん
2007/12/29(土) 13:33:11そこがちゃんと書いてないから勘違いされたと思われ
0592デフォルトの名無しさん
2007/12/29(土) 17:06:310593デフォルトの名無しさん
2007/12/30(日) 12:13:133次元は分からんが
0594デフォルトの名無しさん
2007/12/30(日) 12:39:280595デフォルトの名無しさん
2007/12/31(月) 01:56:421,fairfieldの公式で西暦1年1月0日からの経過日数daysを求める
2,days+nを西暦年月日に変換する
という方法を考えました。
2は1の式を変形して解けるだろうと見当を付けていましたが、
小数点以下を切り捨てたりしているためうまく式を求められません。
素直に最初の日付にnを足し、年・月に順次繰り上げていくほうが賢明でしょうか?
日付は最近のものに限定して考えています。
ユリウス暦とグレゴリオ暦の判断が面倒になるので…
0596デフォルトの名無しさん
2007/12/31(月) 08:25:44日付を1日進めるプログラムは書けるかい?
おk。ならば、1日進める部分をn回実行するんだ。
0597デフォルトの名無しさん
2007/12/31(月) 08:49:10大抵の言語に日付け処理系の関数があると言うのに。
0598デフォルトの名無しさん
2007/12/31(月) 11:47:35ttp://ufcpp.net/study/algorithm/o_days.html
0599デフォルトの名無しさん
2007/12/31(月) 12:25:41ちょっと検索してみたらこんなのがあった
delphiだけど、c言語に変換するのはこどもあそびにひとしい
ttp://kwikwi.cocolog-nifty.com/blog/2005/12/delphi_266f.html
ところで前々から思ってたんだけど、fairfieldの公式って誰が考案したの?
日本のサイトしか引っかからないんだよね
0600デフォルトの名無しさん
2007/12/31(月) 12:29:16なるほど。
ただ、(情報が小出しになってすみません)n日前の日付も求められるようにしたいので
上に書いたような方法だとdays+nを-に変えるだけで実現できるかなーと・・・
>>597
Cなのでそういった関数はもちろんあるのですが、若干不便なので
勉強も兼ねて自前で実装してみようというわけです。
0601デフォルトの名無しさん
2007/12/31(月) 12:51:11おおお÷4を右シフト演算できるのは考えが及んでませんでした
>>599
(mjd - 15078.2) / 365.25 …? もはや何がなんだか。
ttp://cl.is.kyushu-u.ac.jp/Literacy/PP/H14/adp/program/date.html
こんなの見つけたので読んできます。
0602デフォルトの名無しさん
2007/12/31(月) 13:18:34ttp://www.tensyo.com/urame/date/day_c.shm
ここの
int YMD_AddD(int *Y,char *M,char *D,long d) って関数を見ると
負数を渡した場合は 400年循環を使って正に直せばいいみたい。
0603デフォルトの名無しさん
2008/01/01(火) 10:28:350604デフォルトの名無しさん
2008/01/02(水) 02:09:27自動でやってくれるものだと思ってたんだが、そうでもない?
0605デフォルトの名無しさん
2008/01/02(水) 08:29:27固定値の除算ならさらに、掛け算で代用してくれるのも多いね。
0606デフォルトの名無しさん
2008/01/02(水) 10:22:112のべきの定数ならね。
0607デフォルトの名無しさん
2008/01/02(水) 12:18:441、カレンダを1日進める関数関数を作る
2、+N日は1の関数をN回呼ぶ
3、-N日は、年数を400日戻してから、146097-N回 1の関数を呼ぶ
0608595
2008/01/02(水) 20:05:17struct 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++;
}
}
0609595
2008/01/02(水) 20:06:50Date 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;
}
0610595
2008/01/02(水) 20:39:23>>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;
}
0611デフォルトの名無しさん
2008/01/08(火) 03:16:560612デフォルトの名無しさん
2008/01/08(火) 03:17:24ごめんなさい
0613デフォルトの名無しさん
2008/01/08(火) 13:01:23そのまんまの意味じゃなーの。
f(x)=sin xで1,-1は明らかに漸近的ではないが
g(x)=1/x(x≥0)で0は漸近的。
0614デフォルトの名無しさん
2008/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 は何に使われているんでしょうか?
0615デフォルトの名無しさん
2008/02/09(土) 20:31:460616614
2008/02/09(土) 20:41:09くりあがりですね。
このプログラムの結果って、w に short で表せる数を法としたそれぞれの桁が入ると思うんですけど、
この理解で合っていますか?10 進数で表示したいときには変換するルーチンも別に必要でしょうか?
0617デフォルトの名無しさん
2008/02/09(土) 20:44:43そのとおり。
10進数で画面に表示する回数が、普通の計算を行う回数よりも
圧倒的に少ないと考えると、そういう数の表現になる。
0618デフォルトの名無しさん
2008/02/11(月) 16:13:21k = t >> 16;
この部分を
k = t/10;
t -=k*10;
w[ i + j ] = t;
とすれば、10進法になるんじゃない?
8bitなら100進数
16bitなら10000進数なんてのがオススメだよ
0619デフォルトの名無しさん
2008/02/11(月) 23:37:330620デフォルトの名無しさん
2008/02/18(月) 17:15:48調べると掃き出し法は他の計算方法に比べると誤差が大きいと書いてありました。
なぜ誤差が大きくなるのでしょうか?
0621デフォルトの名無しさん
2008/02/18(月) 23:15:28たまたま今やっていることに関係あるので。
さて、分かったことは小数演算は必ず誤差を含むと言ってもいいこと。
なので、10^n倍で整数に変換したり、ライブラリを使ったり対策を
しなければいけないこと。まぁ大体こんな感じです。
ではなぜ掃き出し法が誤差が大きいかというと、予測ですが
単純に計算量が他に比べて多いからではないでしょうか。
誤差を含む演算はやればやるほど誤差が大きくなるというわけです。
ちゃんとした理由ではないかもしれませんが、それよりも
どうすれば誤差を小さくできるか考えた法がいいと思います。
まぁ原因が分からなくては始まりませんが。
0622デフォルトの名無しさん
2008/02/18(月) 23:42:00そんなに詳しくないから適当に書くけど、
基本的にはその通り。
収束性が悪いほど誤差は積もりやすい。
あと、除算があると誤差大きくなる。
なので、掃き出し法みたいな手計算的手法のものよりも、
ガウスザイデル法みたいな反復計算の方が誤差少ない。
0623デフォルトの名無しさん
2008/02/19(火) 02:13:06一概にそうとは言えない。というか、単純に比べることは不適当。
そもそも掃き出しは(解けるならば)必ず A x = b を解くが、
ガウスザイデル、SOR は特殊な A に対してしか一次方程式を解かない。
したがって、無条件で比較することはできない。
次に、生じる誤差が違う。掃き出し法は直接解法なので、考える誤差は丸め誤差のみ。
一方のガウスザイデル、SORは反復解法なので考える誤差は丸め誤差と打切り誤差。
反復法の打切り誤差をどの程度に設定するかということを述べないと、比較はできない。
0624デフォルトの名無しさん
2008/02/19(火) 13:21:15掃き出しで解けるものでもガウスザイデル、SORで解けないものもあるということでしょうか?
新たな課題ですね( ̄□ ̄;)!!
実は、エクセルマクロで書いた掃き出し法で計算した回帰分析と、
エクセルの分析ツールの回帰分析した結果、
後者の方が精度がよかったので分析ツールの回帰分析は別のアルゴリズムなのかなと考え調べていました。
後者はガウスザイデルなのかもしれません。
0625デフォルトの名無しさん
2008/02/19(火) 16:20:26マクロでやってるなら、ピボットの選択してる?
0626デフォルトの名無しさん
2008/02/19(火) 18:31:45掃き出しで解けてガウスザイデルで解けない問題なんて
いくらでもあるよ.たとえば
x + 2 y = 1
2 x + y = 1
をこの順番で連立方程式と考え,ガウスザイデルを
初期値 x = 0, y = 0 で適用すると,発散する.
ガウスザイデルが収束する必要十分条件は,未解決のはず.
0627デフォルトの名無しさん
2008/02/21(木) 22:41:32> マクロでやってるなら、ピボットの選択してる?
いえ、まず中心をすべて1にしてから掃き出しています。
これではダメでしょうか?
0628デフォルトの名無しさん
2008/02/22(金) 19:59:46ダメ
0629デフォルトの名無しさん
2008/04/03(木) 03:18:180630デフォルトの名無しさん
2008/04/17(木) 12:46:541,000,000,000,000,000,000(10の18乗)と25の最大公約数を求めるとしたとき、
引き算は何回行われるか答えよ。また、1秒間に10億回の計算を行えるCPU(クロック
1GHzに相当)を用いてこの計算を行ったとき、計算にはどのくらいの時間がかかるか。
「X年Xヶ月」など実感が分かる単位に直して答えよ。
この解き方がわかる人がいましたら是非教えて下さい。
解けなくて困っています。
0631デフォルトの名無しさん
2008/04/17(木) 13:30:05宿題は自分で解決しようと努力しないと意味がないぞ
どこまでは理解できていて、どこが分からないんだ?
0632デフォルトの名無しさん
2008/04/17(木) 14:05:5810^N は N>=2 なら25で割り切れる。
つまり最大公約数はユークリッド互除法でも最初のステップで求まってしまう
もしかして 64bit整数演算が出来ない32bitCPUで除算も筆算法でコードを書いたら
って場合か? それでも実感がわかる単位にはならないわな
0633デフォルトの名無しさん
2008/04/17(木) 14:46:19・出題者のちょっとした遊び心
どっちかじゃね?
難しそうに見えて実は簡単な問題を出して
最初から課題をやる気がない奴を調べるためだったりしてw
0634デフォルトの名無しさん
2008/04/21(月) 13:16:15a[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 格納されているデータの中で最小の値を探索する操作
これを現在解こうと思っていますが、よく分かりません。
分かる人は是非教えて下さい、お願いします。
0635デフォルトの名無しさん
2008/04/21(月) 13:32:09最良:定数
最悪:k比例
1-2
最良:定数
最悪:k比例
1-3
最良:k比例
最悪:k比例
0636デフォルトの名無しさん
2008/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に設定せよ)
0637デフォルトの名無しさん
2008/04/21(月) 16:28:550638デフォルトの名無しさん
2008/04/21(月) 17:03:43検索するとGMRes(一般化残差最少法、GMRes法 )というのがあるらしい。
(残差を最小にするから、たとえ解が無くても最適な値が求まる?収束に向かうのは確実?)
ただ、ガウスザイデル法は数行のプログラムなのに対して
見つけたプログラムがかなりでかいサイズになっているのがまた気になる。
ガウスザイデル法で残差を小さくするような改良って無いのかな?誰か知ってる?
0639デフォルトの名無しさん
2008/04/21(月) 17:40:08ここで、問題なのが加速緩和係数の値の選び方である。明らかに、それが1の場合、ガウス・ザイデル法となりメリットは無い。また、1以下だと、ガウス・ザイデル法よりも収束が遅い。ただし、ガウス・ザイデル法で収束しないような問題には使える。
従って、1以上の値にしたいわけであるが、余り大きくすると、発散するのは目に見えている。これについては、2を越えると発散することが分かっている。最適値となると、だいたい1.9くらいが選ばれることが多い。
http://www.akita-nct.ac.jp/yamamoto/lecture/2004/5E/linear_equations/relaxation/html/node6.html
0640デフォルトの名無しさん
2008/04/21(月) 18:02:14ω=1がもともとのやつ
0641デフォルトの名無しさん
2008/04/22(火) 00:29:31収束しないことが気になるような場合には,そもそも使ったらダメ.
これはSORでも状況は変わらない.
GMResやらBiCGやらIDRやら反復解法は色々あるんだから
解きたい問題にあわせて適切に解法を選ばないとダメよ.
0642デフォルトの名無しさん
2008/04/22(火) 00:57:390643デフォルトの名無しさん
2008/04/22(火) 05:48:37なるほど、どうもです。
プログラマ的な発想で少し工夫すればいけるんじゃない?と思ってましたが
やはり数学は厳密ですからね。たまたま、やってみたものがうまくいっても
その正しさを証明しなければならないので、出来上がったものを使いたいなと思います。
0644デフォルトの名無しさん
2008/04/22(火) 09:27:07そのとおり.
ガウスザイデル法は,対角優位とか半正定とかを満たしている場合を除いて
解が存在しても,収束するとは限らない.
いつ収束するかの厳密なところ(必要十分条件)は,現在でも未解決問題.
0645デフォルトの名無しさん
2008/04/23(水) 16:48:12639のこれは?
。また、1以下だと、ガウス・ザイデル法よりも収束が遅い。ただし、ガウス・ザイデル法で収束しないような問題には使える。
0646デフォルトの名無しさん
2008/04/23(水) 17:10:06SOR法の0 < ω < 2である係数を2以上にすると必ず収束しない事がわかっている
ωの値によって収束が左右される 0に近づければガウスザイデル法で無理な場合も収束するのでは?
0647デフォルトの名無しさん
2008/04/23(水) 20:15:140648デフォルトの名無しさん
2008/04/25(金) 01:51:21条件:徐々にグレースケール変換できればvolumeの持たせ方は自由
// 【メソッド名】convGrayScale
// 【引数説明】
// srcRGB:変換元画像(0xRRGGBBのピクセル配列)
// pixel_num:ピクセル数
// volume 0(無変換)〜255(完全変換)の範囲でグレースケールに変換
// dstRGB:変換先(0xRRGGBBのピクセル配列)
0649デフォルトの名無しさん
2008/04/25(金) 01:52:02int 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; // 変換結果
}
}
0650デフォルトの名無しさん
2008/04/25(金) 01:54:170651デフォルトの名無しさん
2008/04/25(金) 02:10:24処で、volumeを255まで振る前にグレイになってしまうし、振っていく途中で違う色相の色が出てしまいそうだけどいいのかね。
0652648
2008/04/25(金) 03:08:47volumeを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に使うことはない
0653648
2008/04/25(金) 03:15:22dstRGB[i] = (((Y * volume + red * (100 - volume)) / 100)<<16) +
(((Y * volume + green * (100 - volume)) / 100)<<8) +
((Y * volume + blue * (100 - volume)) / 100);
としたてみたけど、遅くなったorz
0654デフォルトの名無しさん
2008/04/25(金) 06:45:23これの意味を教えて
0655デフォルトの名無しさん
2008/04/25(金) 06:54:50YUV とか 色空間あたりでググって見たら、、、
wikipedia の 「色空間」だとか
http://ofo.jp/osakana/cgtips/grayscale.phtml の 2.NTSC 〜
にある式を 小数点 の無い形にしたと考えたらいいんじゃない?
0656デフォルトの名無しさん
2008/04/25(金) 07:26:42Y = (red * 19589+ green * 38444+ blue * 7503) / 0x10000;
か、
Y = (red * 77 + green * 150+ blue * 29)/ 256 ;
と2のベキにしたらどうかな /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を2のベキにして
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) );
としたら掛け算は減らせるよ
0657648
2008/04/25(金) 07:54:03なるほど!!さんくす
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
0658デフォルトの名無しさん
2008/04/25(金) 08:51:23distRGB の方は、
(red + (〜)>>8)<<16 を red<<16 + (〜)<<8 などど展開して
red<<16+green<<8+blue とまとめて、
*volume) << の部分を出して因数分解できれば良さげだよね。
>>8 の方も レジスタの H を取るような方法で早くなるかな。
だだ、新しいCPUだと シフト演算もテーブル化してあって
シフト回数がステート数に影響しないからなぁ。
あっ。もうすぐ9時なのでここまででカキコ。
0659デフォルトの名無しさん
2008/04/25(金) 10:12:30どの行が一番時間かかってるか コメントアウトしては時間計って
一番時間かかってる行から順に工夫してゆくしかないと思うけど
cかDelphiでDLL作った方が早いんじゃないの?
0660デフォルトの名無しさん
2008/04/25(金) 10:20:09Y8 = 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 は最初からそう使えば問題ない
でも半分は無理だろな
0661デフォルトの名無しさん
2008/04/26(土) 10:06:56任意のパラメタωに対して、真の解に収束しない例が作れる.
0662648
2008/04/26(土) 13:27:23いろいろありがと。
今んとこ、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]);
0663デフォルトの名無しさん
2008/06/12(木) 13:23:40クイックソートのほうがめんどくさそうなのに最速とか理解できん・・・
0664デフォルトの名無しさん
2008/06/12(木) 14:07:54クイックソートがソートの中で最速ってわけではないが……
同じデータ数なら、挿入法よりもクイックソートの方が
ソートが完了するまでの比較回数やデータ位置の入れ替えの回数が
平均的に少ないアルゴリズムになっているから。
ソートは基本的にループや再帰呼び出しによる操作だけれど、
ループに入る前や出た後の準備や後始末、
それにループ内での操作が少しくらい複雑になっても、
ループや再帰の回数がそれを補って余るだけ減少する方法なら全体として速くなる。
0665デフォルトの名無しさん
2008/06/12(木) 15:26:15大まかな話、例えば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回の操作では比べるべくもないということ。
しかもクイックソートは挿入法に比べて全体的に複雑なことをやっているように見えても、
データの比較や移動という基本的な操作にかかる時間が変わるわけではないから、
操作回数の極端な減少はソート時間の減少に繋がるということになる。
0666デフォルトの名無しさん
2008/07/04(金) 23:20:300667デフォルトの名無しさん
2008/07/27(日) 08:46:19おまい自身が手で線を引くなら、そういうときは
どういう手順で何を基準に線を引いてるんだ?
0668デフォルトの名無しさん
2008/08/30(土) 18:14:430669デフォルトの名無しさん
2008/10/11(土) 22:27:10↑テキスト比較ツール「DF」のように2つのテキストファイルを比較して
お互い一致しない行を探し出すプログラムを自前で組みたいとおもっています。
(C#を予定)
この手のプログラムを組むにはどのようなアルゴリズムを調べれば実現できる
ようになるでしょうか?
0670669
2008/10/11(土) 22:29:00プログラミングの為の数学と算数 vol.3
http://pc11.2ch.net/test/read.cgi/tech/1197063023/
0671デフォルトの名無しさん
2008/10/11(土) 23:04:05こっちでいいよ
そのソフトウェアをダウンロードする気が無いから確認だけど
aaa
bbb
ccc
ってテキストと
aaa
ccc
ってテキストを比較するとどうなるの?
0673デフォルトの名無しさん
2008/10/11(土) 23:16:47手始めに ONP とか LCS とかでググレばいいんじゃね。
ONP とかだけだと、関係ないものがいっぱいヒットするから
「ONP アルゴリズム」とかでググルが吉。
0674デフォルトの名無しさん
2008/10/12(日) 01:23:58diffっぽく聞こえる。 いや、やりたいことはdiffなんだろうけど。
0675669
2008/10/12(日) 01:54:11オリジナルの文のうち、消えた部分を特定できれば十分です。
aaa aaa
bbb ccc
ccc ddd
左がオリジナル、右が比較用としますとオリジナルから消えた部分として
bbbを特定できれば満足です。
0676デフォルトの名無しさん
2008/10/12(日) 02:27:20あくまでアルゴリズムが知りたいなら>>673のとおりに。
外部ソフトの起動初心者じゃなくて、手軽にやりたくて、
2ファイル間の比較でいいならDOSにFCというコマンドがあるからC#からそれを呼んでその結果を解析すればおk
0677デフォルトの名無しさん
2008/10/12(日) 07:27:56今時 FC はないだろ。
って言うか、それなら DF 呼び出すようにするだろうし。
単に楽したいだけなら、C# で LCS の実装例とかも見つけられるでしょ。
参考 URL: http://d.hatena.ne.jp/siokoshou/20070308
0678デフォルトの名無しさん
2008/10/12(日) 12:10:51DFってそういう出力する方法あるのか?
わざわざ実装したいくらいだから結果をプログラム中で使いたいのだと思ったんだが。
あとFCなら配布時に別途導入してもらう必要が無いし。
あと>>673のキーワードで見つけられない人が実装例みて実装できるのかちょっと疑問。
0679デフォルトの名無しさん
2008/10/12(日) 13:30:35FC 勧める理由がわからん。
比較するテキストファイルの書式が決まってるならまだしも任意のテキストファイルを
想定すると、FC の出力の解析は結構大変だよ。
0680669
2008/10/12(日) 14:19:04ttp://www.ibm.com/developerworks/jp/java/library/j-seqalign/index.html
↑LCSのプログラムに関して概念を説明しているサイトがありました。
これにそってLCSテーブルを作り、LCSを見つけてみようと思います。
0681デフォルトの名無しさん
2008/10/12(日) 15:09:12勧めた理由はその次の行に書いたが?
ぶっちゃけそれ以上の理由は無い。
解析が大変だと思うのは同意。
>>680
>>677のソースをコピペでいいのに。
0682デフォルトの名無しさん
2008/10/12(日) 15:26:58> 勧めた理由はその次の行に書いたが?
配布の容易さと解析の容易さの比較は状況次第だから議論は避けるよ。
> >>677のソースをコピペでいいのに。
>>669 は、アルゴリズムを理解しようとしてるんだろうと思うし、コピ
ペでは得られないものがあると思うよ。
頑張れ > >>669
0683デフォルトの名無しさん
2008/10/12(日) 16:11:41とはいえスレとしては後者として考えるべきだった。 スマンカッタ
0684669
2008/10/12(日) 16:18:39> >>669 は、アルゴリズムを理解しようとしてるんだろうと思うし、コピ
> ペでは得られないものがあると思うよ。
はい、>>680のサイトでO(NM)の単純なアルゴリズムに関してはおおよそ把握することができました。
可能ならば
http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm
で紹介されていますO(ND)アルゴリズムや、さらに進化したO(NP)アルゴリズムも
理解したいと思っています。
さっそくO(ND)とO(NP)を解説した原著論文をDLしてきたのですがなかなか全体像を
把握するのが難しいです(´・ω・`)
もう少し優しくかみ砕いて説明してくれているサイト、できましたら日本語で、があれば
嬉しいのですがそういうサイトは無いでしょうか?
0685669
2008/10/12(日) 16:19:20http://d.hatena.ne.jp/siokoshou/20070315
aaa aaa
bbb bbb
ccc
(左がオリジナル、右が比較対象)
早速この二つを比較してみたところ。
オリジナルの"aaa"はCommon(共通)と判断されたものの、オリジナルの"bbb"はModified(変更)
と判断されました。ぱっと見た目では"aaa"も"bbb"も変更点は無いように思えるのですが・・・。
0686デフォルトの名無しさん
2008/10/12(日) 16:22:21もっとPCの全般的な基礎知識を得た方がいいような希ガス。
おそらく、左のbbbには行末に改行文字がないのではないか?
0687669
2008/10/12(日) 16:35:39左のbbbには\nを付けましたが、やはりModifiedが返されるようです。
あと
aaa aaa
bbb ccc
bbb
だと
Common
Modified
Common
と返されるようです。
オリジナルが2行なのに返される行が3行だと後々の処理がちょっとややこしくなるかもしれません・・・
0688デフォルトの名無しさん
2008/10/12(日) 17:10:18C# のソースがあるんだから、ステップ実行しながら見てみればいいと思うんだが。
あと、それはそれとしてバイナリエディタを1つ使えるようになっておいた方がいいと思う。
テキストエディタ上では同じ改行に見えても片方は 0x0d のみで、もう一方は 0x0d 0x0a
なんてこともあるから。
0689デフォルトの名無しさん
2008/10/12(日) 17:48:14鈍らな比較ツールだと、「挿入された」ことを理解できないから>687のようなことになる。
逆に言えば、「挿入された」ことを考慮しないアルゴリズムでは、目的に合っていないと言うことだけ。
それにしても、>685では右の2行目はbbbなのに>687ではcccにするなど、
意図的に釣ろうとしているのでなければ余程の間抜けか説明下手にしか見えない。
0690669
2008/10/12(日) 17:56:39> それにしても、>685では右の2行目はbbbなのに>687ではcccにするなど、
> 意図的に釣ろうとしているのでなければ余程の間抜けか説明下手にしか見えない。
釣りとかでは無いです(;´∀`)・・・
>>685も>>687もどちらもオリジナルが2行なのに対して
比較対象の文字列(どちらも3行)をいじるだけで出力が
2行になったり3行になったりと変わってしまうと後々の
処理がややこしくなるかなと思った次第です
0691だから、無駄なことはやめておけと
2008/10/12(日) 18:14:36読解力のない間抜けだということはよく判りました。
0692デフォルトの名無しさん
2008/10/12(日) 18:47:390693デフォルトの名無しさん
2008/10/12(日) 19:52:19> >>677さんに紹介していただいたサイトに掲載されていましたC#のコードを早速試してみました。
> http://d.hatena.ne.jp/siokoshou/20070315
そこのコードは最長共通部分とか返してくれない。
「とにかくO(NP)の最速で動くdiffコードを作ってみました」
ということを実証するためのコードだからあまり実用的じゃないぞ。
あるいはコードに手を入れてちょっとした改造を施すか汁。
0694デフォルトの名無しさん
2008/10/12(日) 20:58:19>それにしても、>685では右の2行目はbbbなのに>687ではcccにするなど、
なんか勘違いしてね?
その二つの例が別の話題だということは>>687が「あと」と言っていることから分かる
自分の読解力を過信して、ろくに理解せずに他人にいちゃもんを付けるのは格好悪いよ
0695デフォルトの名無しさん
2008/10/12(日) 21:04:24> 読解力のない間抜けだということはよく判りました。
読解力の無いマヌケはお前の方だったようだなw
0696デフォルトの名無しさん
2008/10/12(日) 21:07:150697デフォルトの名無しさん
2008/10/12(日) 21:07:290698デフォルトの名無しさん
2008/10/12(日) 21:17:48(ノ∀`)アチャー
0699デフォルトの名無しさん
2008/10/12(日) 22:11:350700
2008/10/14(火) 00:07:37詳しいアルゴリズムを解説したページありませんか?
なんか宣伝のようなページしか見つかりません。
0701デフォルトの名無しさん
2008/10/14(火) 18:55:04ここにたどり着いた
あってるかは知らん
0702デフォルトの名無しさん
2008/10/14(火) 19:06:55>>700 はどこでSIGMAという名前を知ったの?
0704アラフOO.o(笑)
2008/10/15(水) 23:21:58オモローな記事があるぞ。兄弟。
いまさらアルゴリズムを学ぶ意味
Page1
アルゴリズムを学ぶ意味
世界のナベアツのアルゴリズム
世界のナベアツのアルゴリズムの実装
Page2
ナベアツアルゴリズムを理解してみる
そのほかのナベアツアルゴリズム
あらためてアルゴリズムを学ぶ意味
Page3
フローチャートを学ぶ
UMLを学ぶ
さまざまなアルゴリズムを知っておこう
ttp://www.atmarkit.co.jp/fcoding/articles/algorithm/01/algorithm01a.html
0705デフォルトの名無しさん
2008/10/16(木) 20:09:11http://pr.fujitsu.com/jp/news/2006/12/15.html
> 九州大学の有川節夫氏(現在、理事・副学長)と研究グループが
> 1981年に発表した、一方向逐次処理方式による
> 超高速パターンマッチングエンジン・SIGMA(シグマ)を基に開発・実装されている。
アルゴリズムじゃなくてシステムじゃないか。
人物から見ても >>701 であってるんだな。
あと、エラーが出るならどんなエラーが出るかくらい書こうよ。
少なくとも俺の環境では問題なく見られるけど。
0707デフォルトの名無しさん
2008/10/18(土) 18:41:25例えば、[1,2][5,7][8,15]という範囲のリストがあります。
上記のリストに[3,5]という範囲を追加すると
[1,2][3,5][5,7][8,15]に。
上記のリストに[1,6]という範囲を追加すると
新しく追加する範囲が常に優先されて、
[1,6][6,7][8,15]に。
上記のリストに[10,13]を追加すると[8,15]が2つに分割されて
[1,2][5,7][8,10][10,13][13,15]。
リストは常にソートされているものとして、各範囲は重なって
はいけません。上記で範囲[Start,End]でEndは含まれません。
範囲のリストに1万件とか2万件を高速に連続追加できれば幸いです。
よろしくお願いします。定石のアルゴリズムがありそうですが、私の実力ではわかりません。
0708デフォルトの名無しさん
2008/10/18(土) 18:46:16アクセスをしたいので。
0709デフォルトの名無しさん
2008/10/18(土) 18:53:280710デフォルトの名無しさん
2008/10/18(土) 19:14:08実際は、各範囲にオブジェクトが関連付けられていますというより、
あるクラスに開始範囲を表すStartIndex,EndIndexフィールドがあります。
考えたのは、まず、追加する範囲の開始インデックスをキーにリストをバイナリ
サーチして追加位置決定?
んー。
0711デフォルトの名無しさん
2008/10/18(土) 19:14:40範囲を示すインデックスにどの範囲に属するかという情報を持たせる。
上の例で実際にやってみる。
[1,2][5,7][8,15]に[3,5]を追加する。
範囲を示すインデックスがどの範囲に属するかという変数 = ID (0,1,0,0,0,2,2,0,3,3,3,3,3,3,3)
[3,5]を追加。(0,1,0,4,4,2,2,0,3,3,3,3,3,3,3)
[1,6]を追加。(0,4,4,4,4,4,2,0,3,3,3,3,3,3,3)
[10,13]を追加。(0,1,0,0,0,2,2,0,3,3,4,4,4,3,3)
以上。追加は高速だと思う。
範囲のリストへのアクセスはIDからリストを作るので、そこは作る処理の時間だけ遅くなる。
0712デフォルトの名無しさん
2008/10/18(土) 19:19:05追加範囲と比較対象の範囲が重なり合う部分があれば、比較対象の範囲を調整?
完全に含まれていれば、削除?
0713デフォルトの名無しさん
2008/10/18(土) 19:24:57でお願いしますといいましたが、撤回します。すみません。
ある程度高速であればいいです、自分が考えたコードが醜く読みずらくなっていくので
何かいいシンプルなアルゴリズムないのかなと思った次第です。
>>711
ありがとうございます。ちょっと考えてみます。
0714デフォルトの名無しさん
2008/10/18(土) 19:39:07なるほど、おもしろいですね。塗りつぶしていくイメージですね。追加する場合の
アルゴリズムは単純ですね。必要であればIDの伸張と指定範囲の塗りつぶし(データ転送)。
0715デフォルトの名無しさん
2008/10/18(土) 21:13:16例えば[1,2][5,7][8,15]を3で分割すると[1,2]と[5,7][8,15]に、
10で分割すると[1,2][5,7][8,10]と[10,15]になる(このように列の分割が範囲そのものの分割を伴うことがある)
範囲の列Sに[start, end]を挿入するには、Sをstartで分割してS1とS2を得、S2をendで分割してS3とS4を得、
S1とS4の間に[start, end]を挟んだものを結果とすればいい
Sをpで分割するには、まずS中の範囲でendがpを越えるもののうち一番左にあるものを探す
そういうものがなければ、SはSと空列に分割される
あれば、それのbeginをpと比較して、それを分割するか全部右側に入れるか決める
多分この手順でいけるけど、これが高速に実行できるようなデータ構造は何があるだろう
2-3 Finger Treesとかならindexとappendとsplitが全部O(log n)だから、O((log n)^2)で挿入できるかな
0716デフォルトの名無しさん
2008/10/18(土) 21:47:34データ構造を弄ってよいなら,
できるべき操作をちゃんと指定してほしい.
たとえば
(1) 範囲の追加
(2) 範囲 [x,y] に含まれる全ての範囲を小さい順に出力
(3) 小さいほうから数えて k 番目の範囲の出力
(4) ある点を含む区間の有無の判定
(5) ...
みたいな感じで列挙してください.
あと,>>710 に関して質問なのだけど,
いまある区間が分割された場合(>>707 の [10,13] の例),
オブジェクトとしてはどうなっているの?
(a) オブジェクトが複製されて [8,10] と [13,15] が別物として管理される
(b) [8,10] と [13,15] は同じオブジェクトに対応する
どっち?
0717デフォルトの名無しさん
2008/10/18(土) 23:22:08範囲が狭いなら、>>709 の言うようにビットマッブでいいと思うけど、
2万件とか言ってるなら、
struct {
unsigned int StartIndex;
unsigned int EndIndex;
};
みたいなノードを StartIndex をキーにして BTree とかで管理して、
挿入とか削除は自前で好きなように実装にするな、俺なら。
0718デフォルトの名無しさん
2008/10/18(土) 23:25:14まさにその部分を質問してるんじゃね?
0719デフォルトの名無しさん
2008/10/19(日) 00:17:17反応してくれてどうもです。
最近はあまりやらないんですけど、前はパズルを解くプログラムを作ったりしていました。
ポイントは簡単な問題を数多くこなす事だと思っています。
すると、どういう処理が効率がいいのか分かってきます。
こういう場合の為におすすめです。あまり無いと思いますが。。。
0720デフォルトの名無しさん
2008/10/19(日) 00:52:35>[1,2][5,7][8,10][10,13][13,15]。
これだけどさ、なんで
[1,2][5,7][8,15]
じゃないの? そういうルールだからと言われたらそれまでだけど
こういう処理が必要な実例が思いつかない。
0721デフォルトの名無しさん
2008/10/19(日) 00:59:37想像力不足
0722デフォルトの名無しさん
2008/10/19(日) 01:38:100723デフォルトの名無しさん
2008/10/19(日) 01:42:24あと>>721はどんなもの想像してたんかな?
0724デフォルトの名無しさん
2008/10/19(日) 10:05:09>>716
>(a) オブジェクトが複製されて [8,10] と [13,15] が別物として管理される
オブジェクトを複製して別物で管理します(範囲以外のプロパティをコピーして)
>できるべき操作をちゃんと指定してほしい.
外部に公開する機能は
・範囲の追加(1個ずつ)
・リストの先頭から末尾への連続アクセス
・リストの全削除
以上です。
>>717
なるほど、上で書いた外部に公開する機能みてもB-Treeでいいのかもしれませんね。
ちょっと実装してみます。
>>715
わ。ありがとうございます。すごいわかりやすいです。
もうちょっと色々もだえてみます。
0725デフォルトの名無しさん
2008/10/19(日) 10:12:56だとリストでデータ構造固定しちゃうような意味にとられるかもしれないので
正確には、
範囲の列に昇順に連続アクセス
かな。途中からアクセスすることはありません。
0726デフォルトの名無しさん
2008/10/19(日) 12:23:29ttp://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=41
こんな感じの問題解くときにはそういう処理でやってもいいかもしれない。
0727デフォルトの名無しさん
2008/10/22(水) 23:08:313が何個、5が何個って分かればいいんだけど
あと表せない数はあるんだろうか
最初の5つはこんな感じ
8=5+3
9=3+3+3
10=5+5
11=5+3+3
12=3+3+3+3
13=5+5+3
0728デフォルトの名無しさん
2008/10/22(水) 23:37:070729デフォルトの名無しさん
2008/10/22(水) 23:37:408,9,10,11,12が書き表せている時点で、次の5つ組
13,14,15,16,17はそれぞれさらに5を足せば作れ、
以降5つ組ごとに足す5を増やしていけばすべて作れるので、
8以上の正の整数でつくれないものはない。
0730デフォルトの名無しさん
2008/10/22(水) 23:39:21http://d.hatena.ne.jp/gould2007/20071009
0731デフォルトの名無しさん
2008/10/22(水) 23:41:500732デフォルトの名無しさん
2008/10/23(木) 00:01:14とりあえず列挙できることが分かったので、個数の組はあらかじめ計算して持つようにしよう
というか>>729の通り5を足せばいいんじゃん、気づかなかった
ありがとうございました
0733デフォルトの名無しさん
2008/10/23(木) 00:50:53>最初の5つはこんな感じ
6つあったのねw
0734デフォルトの名無しさん
2008/10/25(土) 01:09:36これ何度みても計算できねぇ助けて
0735デフォルトの名無しさん
2008/10/25(土) 01:53:540736デフォルトの名無しさん
2008/10/25(土) 02:07:20ttp://cial.csie.ncku.edu.tw/pdf/%5BY200X%5D%5BIEICE%20TRANS%5DA%20Small%20and%20Fast%20IP%20Forwarding%20Table%20Using%20Hashing.pdf
ぐぐった
合ってるかは知らん
0737デフォルトの名無しさん
2008/10/26(日) 11:10:39それっすそれっす
0738しろうと
2008/10/26(日) 16:22:55バイナリーサーチの計算量はO(log n)ですが、その導き方について。
T(n)=O(1) n<=1
T(n)=T(n/2)+O(1) n>1
以上から、T(n)=T(n/2)+1=T(n/4)+2=T(n/8)+3...=T(n/2^k)+k。
ここまではわかるんだが、解説によると(n/2^k)=1とおいて、T(n)=log n+1
したがってT(n)=O(log n)となっている。なぜ、(n/2^k)=1とおくのでしょうか。
また、(n/2^k)=1をkについて解けばlog nにわかりますがlog n+1の1って何なんでしょうか?
0739デフォルトの名無しさん
2008/10/26(日) 18:18:41k=1のとき、つまり1回分割したときはn/2
k=2のとき、つまり2回分割したときはn/4 = n/2^2
k=3のとき、つまり3回分割したときはn/8 =n/2^3
といって、求めたいのは、つまりnをk回分割したときの計算量だから
k=???のとき、つまりk回分割したときにn/2^k → ???を求める為には
数式頼みはよろしくないよ
0740デフォルトの名無しさん
2008/10/26(日) 18:49:12ひどい導出だ.O(1) の扱いが雑すぎる.
T(n) = O(1) (n <= 1) なんて意味不明すぎる記述.
もし本当に本にこう書いてあるなら捨てたほうがいい.
0741くまさん
2008/10/26(日) 18:59:21アルゴリズムの流れ図について、自然数m、nに対して、
mのn乗を計算する効率の良いアルゴリズムのフローチャ
ート書くという問題です。
どなたかご教授ください。
0742デフォルトの名無しさん
2008/10/26(日) 19:37:22ではまず、効率の良いアルゴリズムを言ってくれ。
0743くまさん
2008/10/26(日) 22:23:58n^2*n^2*n^2
これがヒントだそうです。
どうしたら、よろしいのでしょうか?
お願いします。
0744くまさん
2008/10/26(日) 22:44:42従い、nの64乗はnの2乗×nの32乗ですから、nの2乗×nの2乗×nの2乗×nの2乗×nの2乗×nの2乗となります。
の2乗
これを利用して、mのn乗のアルゴリズムのフローチャートを書くみたいです。
0745デフォルトの名無しさん
2008/10/26(日) 22:45:56ビット演算を絡ませたアセンブラ的な問題なのかな?
お前らどうする?これ放置していいん?
0746デフォルトの名無しさん
2008/10/26(日) 22:53:29説明がデタラメだし。
0747デフォルトの名無しさん
2008/10/26(日) 23:18:56>nの8乗はnの2乗×nの4乗
ダウト。乗数は足し算です。
n^8
= n^(4+4)
= n^4 * n^4
= (n * n * n * n) * (n * n * n * n)
ね?
>nの64乗はnの2乗×nの32乗
同様に、nの32乗×nの32乗がnの64乗で
あえて言うなら(nの32乗)の2乗がnの64乗
つまり
>>745
問題のヒントが出鱈目だから放置していい。
0748デフォルトの名無しさん
2008/10/26(日) 23:20:450749デフォルトの名無しさん
2008/10/26(日) 23:27:51サマリー読む限り、別に問題提起ってわけではなさそうだけど……?
0750デフォルトの名無しさん
2008/10/26(日) 23:35:164bitの集合を考え、具体例として以下で計算した場合
0000, 1100 0011, 0100, 0110, 0111, 1011, 0001.
1100まで計算した場合のV0とV1って
V0: 0 0 0 0
V1: 4 3 1 1
になりますかね?
0751デフォルトの名無しさん
2008/10/27(月) 00:12:250752デフォルトの名無しさん
2008/10/27(月) 20:28:440753デフォルトの名無しさん
2008/10/28(火) 20:57:21上記は疑似コードで書かれていますが、アルゴリズム1もアルゴリズム2も
配列の中から最小値を探し出す処理をしているそうですが、アルゴリズム1の
02行目では配列をどうやってtempにぶちこめるのでしょうか? 配列Aが例えば
{2, 6, 3, 7}だとすると、tempには最初に何が入るのですか?再帰なので、
A[1, 4]を呼び出そうとして、tempに値が入る前にA[1, 3]が呼び出され、やっぱり
A[1, 2]が呼び出され、最終的にA[1, 1]になって、A[1]の2が返されて処理が
終了しそうな気がするのですが、間違っているところを教えて下さい。
0754デフォルトの名無しさん
2008/10/28(火) 21:06:35リンク先は見ていないが、再帰の仕組みを勉強しなおし給え。
要は、a[1]の結果が返されるのはa[1, 2]の呼び出しのtempへの代入なのだろ。
0755デフォルトの名無しさん
2008/10/29(水) 00:57:04何と言うか、考え方がピンと来るか来ないか、脳みそにマッチするかしないかみたいなもんだ
>>753
間違ってない、でも再帰の考え方をそうやって深部に潜ってく物だと考えるのは良くない
君の配列の書き方を使って書くと
A[1,4]の最小値は・・・A[1,3]の最小値とA[4]の小さい方!
じゃあA[1,3]の最小値って何さ → 同じやり方で済むじゃん
みたいな考え方を適用すべき
0756デフォルトの名無しさん
2008/10/29(水) 01:01:16だまし絵とか見に行くといいんじゃないかな
0757755
2008/10/29(水) 01:09:03おっと、質問に答えてなかったので答えます
最初にtempに入るのは、A[1,3]の最小値なので2です。
0758デフォルトの名無しさん
2008/10/29(水) 14:22:29ソートして先頭3つでやるのはなんかもったいない気がして・・・
0759デフォルトの名無しさん
2008/10/29(水) 14:41:450760デフォルトの名無しさん
2008/10/29(水) 14:47:310761デフォルトの名無しさん
2008/10/29(水) 14:50:260762デフォルトの名無しさん
2008/10/29(水) 14:53:240763デフォルトの名無しさん
2008/10/29(水) 15:30:41ありがとうございました。
0764デフォルトの名無しさん
2008/10/29(水) 15:31:130765デフォルトの名無しさん
2008/10/29(水) 18:05:02上から k 個欲しかったらサイズ k のヒープを作って次々に突っ込むのがよい.
計算量は全データ数を n とすれば O(n log k).
k は高々 n なので,計算量はデータ数によらずソートするよりも良い.
実用的にはデータの分布に依存するので,実測しないと何とも.
0766デフォルトの名無しさん
2008/10/29(水) 18:16:37全体ソートするのとオーダーかわらんじゃん
0767デフォルトの名無しさん
2008/10/29(水) 18:31:520768デフォルトの名無しさん
2008/10/29(水) 18:33:230769デフォルトの名無しさん
2008/10/29(水) 18:38:050770デフォルトの名無しさん
2008/10/29(水) 18:41:470771デフォルトの名無しさん
2008/10/29(水) 18:43:47それ、なんのこと言ってるの? C++前提なの?
0772デフォルトの名無しさん
2008/10/29(水) 18:50:020773デフォルトの名無しさん
2008/10/29(水) 19:03:5593点以上が100個程度であるとわかっていれば、93点以上を選べばいい。
0774デフォルトの名無しさん
2008/10/29(水) 19:09:33次のループでそれ以上を選ぶ。
0775デフォルトの名無しさん
2008/10/29(水) 21:53:17わからねー
0776デフォルトの名無しさん
2008/10/30(木) 06:19:01全体ソートは O(n log n) だから log の値が違う
0777デフォルトの名無しさん
2008/10/30(木) 13:30:13任意の数aに最も近いx[k]を知りたいとき、普通はO(N)の時間がかかりますが、
あらかじめx[]をソートしておけば二分法を使ってO(log N)でできます。
ここからが質問なのですが、2次元の座標としてx[N],y[N]があるときに、
任意の直線との距離が最も小さい(x[k],y[k])を知りたいとします。
(与えられたa,bに対してa*x[k]+b*y[k]-1.0 の値が最も小さくなるkが知りたいということ)
このときに上の二分法のようなアルゴリズムはあるでしょうか?
普通にやるとO(N)が必要ですが、O(N)より速い方法を探しています。
0778デフォルトの名無しさん
2008/10/30(木) 13:54:090779デフォルトの名無しさん
2008/10/30(木) 15:30:46ないこと証明できる?
困る例なんていくらでも思いつくでしょ。
まさか二分探索は不要だとか主張するつもり?
0780デフォルトの名無しさん
2008/10/30(木) 15:43:210781デフォルトの名無しさん
2008/10/30(木) 16:07:07http://i11www.iti.uni-karlsruhe.de/~awolff/pub/dmsw-fpqgc-06.pdf
のイントロに書いてあるけど,
[CY84]: 前処理 O(n^2),問い合わせ O(log n)
[LC85]: 前処理 O(n^2),問い合わせ O(log n)
[MC95]: 前処理 O(n log n),問い合わせ O(n^0.695)
[Mu03]: 前処理 O(n^1+ε),問い合わせ O(n^{1/2 + ε})
くらいの結果はあるみたいね.
一通り目を通してみたけど,LC85 は特に簡単.双対変換すると
「直線 l に一番近い点 p」⇔「点 l* の真上にある直線 p*」
という関係になることに注意して,点位置決定問題に帰着するだけ.
0782デフォルトの名無しさん
2008/10/30(木) 17:50:08あるんですね。双対変換を使うという発想はなかったです。嬉しいです。
この方法はイメージがついたので、これからちゃんと考えてみます。
追加ですみませんが、
他の方法について、やり方または論文をネット上で見られるものはありますか?
0783デフォルトの名無しさん
2008/10/30(木) 19:16:370784デフォルトの名無しさん
2008/10/30(木) 19:34:27私の大学からだとCY84以外は契約論文誌なので,Webから取れた.
もし必要ならどっかにアップロードするよ.
Mu03はciteseerからも取れたので,論文名で検索してみると良い.
0785デフォルトの名無しさん
2008/10/30(木) 19:47:130786デフォルトの名無しさん
2008/10/30(木) 19:50:29http://scholar.google.com/scholar?q=simplicial+partitions+determine+closest&lr=
0787デフォルトの名無しさん
2008/10/30(木) 20:04:09Mu03を見ることができたので、
これまでの材料で頑張ってみます。
ありがとうございました。
>>785
点を一個追加するとか、色々やりたくなるかもしれないので、
いくつかの方法を知っておきたいと思いました。
0788デフォルトの名無しさん
2008/10/30(木) 20:29:11O(n^2) は大規模なデータを相手にするには重過ぎるという感覚。
n < 2^32 程度でも前処理しきれない。
なので、クエリ時間を増やしても n^2 より安い手法が存在する。
0789デフォルトの名無しさん
2008/10/31(金) 16:28:46AAA ABA
ABB ABA
AAA AAA
というような回転させたら同じ場面を見つける為にいい方法は無いでしょうか?
0790デフォルトの名無しさん
2008/10/31(金) 17:43:56問題が不明瞭
マス目に記号が入ったものが二つ与えられたとき、
それが回転で移りあうかどうかをチェックしろということ?
0791デフォルトの名無しさん
2008/10/31(金) 17:54:59地道に全回転・反転パターン(8通り)を網羅してチェックする。
プログラムが見通しよくなるように工夫がひつようかも。
0792デフォルトの名無しさん
2008/10/31(金) 18:21:540793デフォルトの名無しさん
2008/10/31(金) 18:37:25ここでやる夫的に説明してくれよ
0794デフォルトの名無しさん
2008/10/31(金) 19:41:21/ /´ -‐…‐- .`\
/ /´ i !`ヽト、
. ,ヘ ,' i ! ! | |i |ハ i ヽ キリッ
/ ゝ! ノ| ! !::__!::ノ ´  ̄ i::.i |!
\ .| .:i i :i i |´ \ / `!、ハ:!
`ヽi 从 i i | ニニミ .ニニ !:::::| <トランザクションメモリの実装
. | YハiハN {r::リ` ´{r::リ '::::N ここでやる夫的に説明してくれよ
. | ヽゝ ´´ ``ハ!`
. |∧ �Y! ′ ,':::|
j/∧ _!::} 、 ⊂' ..イ:::::|
///∧´ ∨ ` ,.... ィ´゙Y:::::|
. /////∧ ヽ {ト、∧ |::::::!
,< ̄ ̄∧ } `ヽ >''} { ̄`ヽ
. / `ヽ:::::::::Y´ヽ i´`∨::::∧
/ ∨:::::| .:: ! i .:.: !::::/ i
_ ___
,. :'´: :,. -―‐-ミ:ヽ、
/: : : :厶ィ': ´ ̄ ̄ヾ : :\
/: : : : : :.!: :M: : : : : }、: ヽト、:.\ <じゃっておwww
i: : :.!: : : レ‐' ` ̄⌒ ⌒" トヘ:ハ!
ト--|: : :.!: : 、| ー‐'' ´ `'ー }: :.ト
ミ ミ ミ : :!: : : :! z=≡ ≡z.{: :.ハ ミ ミ ミ
/⌒)⌒)⌒.ハ :_Nとつ \\\ C VVリ /⌒)⌒)⌒)
| / / /:弋こ \ヽ __,. } (⌒)/ / / //
| :::::::::::(⌒) : :}\ / 1 / ゝ :::::::::::/
| ノくf⌒Y ` {_ _,ノイ| / ) /
ヽ / ヽ ヘ,、 _「 |::!:::::} / / バ
| | l||l 从人 l||l.!::|イ:::ヽ_./ l||l 从人 l||l バ ン
ヽ -一''''''"~~``'ー--、/:::::イ; -一'''''''ー-、 ン
ヽ ____(⌒)(⌒)⌒) ):::/} (⌒_(⌒)⌒)⌒))
0795デフォルトの名無しさん
2008/10/31(金) 21:00:100796デフォルトの名無しさん
2008/11/13(木) 03:17:29って意味のわかる人教えて下さい。
0797デフォルトの名無しさん
2008/11/13(木) 06:37:03「隣接リストが O(V+E)」 ← これはまともな言い方じゃない。
0798796
2008/11/13(木) 06:40:40無向グラフG=(V, E)が隣接リストの配列で表現されるとき、Gが接続していようと
なかろうとO(V+E)であることを証明せよ。だったらどうですか?
0799デフォルトの名無しさん
2008/11/13(木) 07:13:30今度は日本語としてもひどくて、何が O(V+E) なのかが分からん。
0800796
2008/11/13(木) 07:25:040801796
2008/11/13(木) 07:31:12例えばどういうときかわかりますか?
0802デフォルトの名無しさん
2008/11/13(木) 07:42:43G = (V,E) を 3点 a,b,c からなるグラフとし,
頂点間距離を d(a,b) = 0, d(a,c) = 1, d(b,c) = -2 と設定し,
頂点 a から b への最短路を求めようとすると破綻する.
0803796
2008/11/13(木) 07:49:210804デフォルトの名無しさん
2008/11/13(木) 08:36:21その例では破綻しないぞ
0805デフォルトの名無しさん
2008/11/13(木) 11:31:33kwsk
0806デフォルトの名無しさん
2008/11/13(木) 21:00:49正答が得られないって意味で破綻なんじゃね?
0807デフォルトの名無しさん
2008/11/14(金) 22:07:03ぜひ解答お願いしたいです。
スレチでしたらすみません。。
0808びぎなぁ
2008/11/16(日) 05:22:26(どの用語がどの用語の中に含まれているのかとか)
ヒープと二分ヒープという言葉があるのですが、同じ意味でしょうか?
木構造--------二分木---------------二分探索木・・・左の子<=親<=右の子
木構造--------二分木---------------二分ヒープ・・・(1)根に最大値がくる、
(2)N[a],N[2a],N[2a+1]のデータでは必ずN[a]のデータが一番大きい
木構造--------二分木---------------ヒープ・・・二分ヒープと同義?
木構造--------多分木
0809デフォルトの名無しさん
2008/11/16(日) 06:29:55ヒープとは,木であって各頂点でヒープ条件『自分の値が子の値以上』
を満たすもののことをいう.よって.一般の木上のヒープがありうる.
例えば多分木上のヒープとしてはd分ヒープはたまに使われるし,
より一般の木上のヒープとしてはフィボナッチヒープが有名.
ただ,最もよく使われるヒープは完全二分木上のヒープで,
何も断らずにヒープと言ったときこれを指す場合も多い.
場合によっては配列実装まで含めてヒープと言う場合もあるけど,
フォーマルには構造と実装は別に考えるので,
>>808 の二分ヒープの説明は本当はちょっとよろしくない.
0810デフォルトの名無しさん
2008/11/16(日) 06:53:51どれくらいの精度で解析すればいいの?
あと,Lameの定理の結果を用いないというのは
Lameの定理を証明して用いるのは良いということ?
それとも,フィボナッチ数で抑えること自体が禁止されるの?
0811デフォルトの名無しさん
2008/11/16(日) 09:19:57どの程度の制度かまでは問題に書いてないので、わかりません。
Lameの定理を証明してもダメだと思います。
フィボナッチ数を用いても良いかまでもわかりませんが、使わないでできるのなら使わないで解いてもらいたいです。
0812デフォルトの名無しさん
2008/11/16(日) 11:41:06互除法のアルゴリズムを
gcd(a,b) = if b == 0 then return a else return gcd(b, a mod b)
として解析する(mod は割り算の余り).a, b ≧ 0 の場合のみ考える.
補題.
a > b ≧ 0 について,gcd(a,b) が k (≧ 1) ステップで終わるならば
a ≧ 1.1^{k+1}, b ≧ 1.1^k が成立する.
証明.
k = 1 のときは自明.k-1 まで正しいと仮定.
gcd(a,b) が k ステップで終わるとき,
gcd(b, a mod b) は k-1 ステップで終わるので帰納法の仮定から
b ≧ 1.1^{k-1}, a mod b ≧ 1.1^k,したがって
a ≧ 1.1^k + 1.1^{k-1} = 1.1^{k-1}×2.1 ≧ 1.1^{k-1}×1.21 = 1.1^{k+1}.
系.
gcd(a,b) のステップ数は O(log min{a,b}).
証明.
a > b としてよく,log b = m とおけば補題より O(m) 回以下のステップ数で終わるため.
0813811
2008/11/16(日) 17:41:20a ≧ 1.1^{k+1}, b ≧ 1.1^k
この式をなぜ持ち出したのかがわかりません。
あと、系の証明が補題より証明できるあたりがいまいちわかりません。
よろしければ教えてください。
0814デフォルトの名無しさん
2008/11/16(日) 20:51:27上:なんとなく.
1.1 に必然性はなくて,1.0001^k でも 1.0000000001^k でも何でもいい.
(1+ε)^k で示せれば系が示せるので,適当に不等式が成り立ちそうな値にした.
本当に解析しようとしたらギリギリの不等式評価を作るべきなんだけど,
この場合にギリギリに評価するとフィボナッチ数が出てしまうので,
わざとガバガバに評価しているという事情がある.
下:
> できるあたりがいまいちわかりません。
そういうときは具体的にここが分からないとか言うもんだよ.
ただ,補題が少し不十分な書き方だったね.補題は
「k (≧ 1) ステップ以上かかるならば」 に置き換えてよい(同じ証明が動く)ので,
そう置き替えておいて,対偶を取ると
「a < 1.1^{k+1} もしくは b < 1.1^k ならば k ステップ未満で終わる」 になるので
b < 1.1^m なる m を見つけられれば m ステップ未満で終わる.
そのような m としては log b (の切り上げ) にでも取れば十分(log は 1.1底).
0815811
2008/11/16(日) 21:04:38もう一度問題と向き合って理解を深めたいと思います。
0816びぎなぁ
2008/11/19(水) 07:05:43返事が遅くなりました。ありがとうございました。
ところで、最小全域木を求めるクラスカル法とプリム法の概要を理解出来たのですが、
計算量のところがウェブ(ウィキとか)で調べてもよく理解できません。
(1)クラスカル法
グラフの中で一番重みの小さい辺をMSTとして加えて行く。ただしその過程でcyclicに
なってしまうような辺は加えないようにする。計算量はO(E log E)またはO(E log V)
(2)プリム法
MSTに属する頂点とそうでないものの2グループに分け、まだMSTに属していない頂点から
最もコストの安く済む頂点をMSTに付け加えて行く。計算量は3種類あるみたい。
・隣接行列、探索→O(V^2)
・2分ヒープと隣接リスト→O(E log V)(←これはO((V+E)log(V))より)
・フィボナッチヒープと隣接リスト→O(E+V log (V))
ウェブの説明を読んでもわからないということはここで教えてもらってもわからないかも知れませんが
もしわかりやすい説明とかありましたら参考に教えて欲しいです
0817デフォルトの名無しさん
2008/11/19(水) 08:22:57アルゴリズムの計算量を評価するためには
もっと正確にアルゴリズムを述べないといけないんだけど,
あなたの説明だと,良く分からない部分が多い.
(もちろん「普通の実装」というのがあるのだけれど,
それがあなたの理解しているものと違う可能性もある)
なので,あなたが理解している形で,For やら If やらを使って
手続きが明確に分かるようにアルゴリズムを書いてくれるかな?
その計算量だったら評価するよ.
0818びぎなぁ
2008/11/19(水) 16:22:32イントロダクショントゥアルゴリズム二版から抜粋です
---------------------------------------
MST-クラスカル(G, w)
A←0
for each vertex v∈ V[G]
do MAKE-SET(v)
sort the edges of E into nondecreasing order by weight w
for each edge (u, v) ∈ E, taken in nondecreasing order by weight
do if FIND-SET(u)≠FIND-SET(v)
then A←A∪{(u, v)}
UNION(u, v)
return A
---------------------------------------
MST-プリム(G, w, r)
for each u∈V[G]
do key[u]←∞
π[u]←NIL
key[r]←0
Q←V[G]
while Q≠0
do u ← EXTRACT-MIN(Q)
for each v∈Adj[u]
do if v∈Q and w(u, v) < key[v]
then π[v]←u
key[v]←w(u, v)
---------------------------------------
0819デフォルトの名無しさん
2008/11/19(水) 21:49:58その本に計算量の説明が懇切丁寧に書いてあるよ
0820デフォルトの名無しさん
2008/11/19(水) 21:54:240821デフォルトの名無しさん
2008/11/20(木) 00:37:390823びぎなぁ
2008/11/20(木) 02:46:49正の数だった場合、ダイクストラ法は失敗することがあるか?」
あれば例を教えて欲しいです
0824デフォルトの名無しさん
2008/11/20(木) 21:21:360825びぎなぁ
2008/11/20(木) 23:44:170826デフォルトの名無しさん
2008/11/24(月) 19:02:46詳細に書いてる本ってありますか?
0827デフォルトの名無しさん
2008/11/24(月) 20:00:17詳細ってどの程度?
必要なトピックを具体的にいくつか挙げてください。
0828デフォルトの名無しさん
2008/12/02(火) 09:34:20サイクリックなグラフでもソート出来ると思うのですが。
0829デフォルトの名無しさん
2008/12/02(火) 10:13:52トポロジカルソート(トポロジカルオーダリング)をどう定義してるの?
いくつか流儀があるから君の流儀が分からないと適切には答えられない.
0830デフォルトの名無しさん
2008/12/02(火) 13:40:19(1)DAGに対して、DFSを実行する。
(2)Finishing timeの大きい順に頂点を並べる。
というものですが、いかがでしょうか。
0831デフォルトの名無しさん
2008/12/02(火) 17:21:09それを定義に採用するなら,DAGでなくてもいいよ.
ただ,普通はそれを定義にはしない.
(それは,トポロジカルソートのひとつを求めるアルゴリズム)
普通のトポロジカルソートの定義は頂点への番号付け(並び順)σで,
u から v に枝があるとき σ(u) < σ(v) なるものを言うんだけど,
これだと u → v → w → u なるサイクルがあると
σ(u) < σ(v) < σ(w) < σ(u) で番号付けに矛盾する.
0832デフォルトの名無しさん
2008/12/03(水) 04:53:21なるほど。わかったような気がします。
ありがとうございます。
0833初心者プログラマ
2008/12/03(水) 16:31:24書こうとしています。例えば1と指定した場合は六角形内に1個の円が描かれます。例として9を指定した場合の図を
添付します。
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/8194.zip
聞きたいのは、nの辺の数に対してどのような法則性があるかということです。
1辺の長さを仮に1とした場合、n=1なら中心から半径√3/2の円が描かれると思いますが、
n>=2のときはどのように半径は決まって行くのでしょうか。nが何個であっても普遍的な
法則などあるのでしょうか。アホな質問だったらすみません。
0834デフォルトの名無しさん
2008/12/04(木) 00:19:45数学板へどうぞ。
0835デフォルトの名無しさん
2008/12/04(木) 00:48:43(√3/2)/n
0836デフォルトの名無しさん
2008/12/04(木) 01:02:08>>835は間違い。
(√3/2)/(1+n√3)
0837デフォルトの名無しさん
2008/12/04(木) 01:02:56さらに間違えてた。orz
(√3/2)/(1+ (n-1)√3)
0838デフォルトの名無しさん
2008/12/04(木) 14:49:490839デフォルトの名無しさん
2008/12/07(日) 04:37:19a(n)=n^(1/2)
b(n)=10*log[2]n
どちらが大きいですか?導き方を教えて下さい。
0840デフォルトの名無しさん
2008/12/07(日) 07:34:40十分大きな n に対しては n^{1/2} > 10 log n.
lim_{x→∞} x^{1/2} / (10 log x) をロピタルなり何なりで示して
εδで書いてε = 1 にでも取れば良い.
0842デフォルトの名無しさん
2008/12/07(日) 14:14:550843デフォルトの名無しさん
2008/12/11(木) 01:52:02a^n >> n^b >> log(n)
とでも暗記しておけ。
大概はこれだけ覚えてりゃ問題ない
0844デフォルトの名無しさん
2008/12/11(木) 03:53:27A->B->C->A => 1
A->B->C->B => 2
A->C->C->C->D => 3
とかの並びが含まれていたら、それをパターンと識別して
=>の後の値に変換する処理を書いています。
今はパターンをトライ木に登録していて速度は問題ないのですが、
共通パターンが少ないとメモリを食うのが気になります。
もう少し効率の良い方法はあるでしょうか。
パターンの候補であるかはインクリメンタルに読み取れる必要があります。
0845デフォルトの名無しさん
2008/12/11(木) 04:41:33基数木は簡単に言えばメモリ使用量を最適化したトライ木であり、
トライ木で子ノードが1つしかないノードを子ノードとマージしたものである。
だとか。もう少し見たら
HAT-trie は基数木の一種で、キャッシュを考慮した文字列検索用データ構造である。
時間計算量も領域計算量もハッシュテーブルに匹敵する。
とか。
0846デフォルトの名無しさん
2008/12/11(木) 06:33:09パトリシアではダメ?
0847デフォルトの名無しさん
2008/12/11(木) 08:28:21何か別の方法がないか聞いて見ました。
HAT-trieは初めて聞きました。調べてみます。
0848デフォルトの名無しさん
2008/12/11(木) 12:02:22自分もかなり興味があるので調べているのですが、難しいです。。。
とりあえず、HAT-trieの発案者の一人であるDr. Nikolas Askitisのホームページを張っておきます。
http://goanna.cs.rmit.edu.au/~naskitis/
調べた結果を少しずつでも書いていったらうれしいです。人任せモードに入ってそばで見ております。。。
0849デフォルトの名無しさん
2008/12/11(木) 21:53:25代わりに、キーの一部の文字そのものを使い、キーの残りに共通部が
なければ衝突のない小さな順序付きテーブルを作って葉に残りの
文字列を入れる。平衡木が深くなるのを避けつつ、
ハッシュ表と違い順序構造も維持できるって事でしょうかね。
テーブルの入れ方の指定とかチューニングとか書いてありますが、
実際に比較した実装も見せないで他のアルゴリズムとの比較グラフが
載ってるのは胡散臭いです。複雑さによる速度低下はありそうだし、
都合の良いデータなのかもしれません。
1つ言えることは、メモリは減るのかもしれないけど、
平衡木が絡んでくるだけでコード量は数倍に増えると思います。
今使ってるトライのコードは登録検索だけですが60行程度です。
パトリシアにするだけでコードは2倍以上に増えました。
メモリは半分以下になりますが速度は3割減ぐらいです。
0850デフォルトの名無しさん
2008/12/12(金) 02:43:00間違いがあるかもしれませんが。。。
-----------------------------------------------------------
HAT-trie: キャッシュを考慮したトライベースの文字列のデータ構造
Nikolas Askitis Ranjan Sinha
School of Computer Science and Information Technology,
RMIT University, Melbourne 3001, Australia.
Email: {naskitis,rsinha}@cs.rmit.edu.au
概要
トライは文字列を扱うツリーベースの最速のデータ構造だが、メモリ食いである。
burst-trieはほとんど同じぐらい速いが、バケツの中へトライチェーンを押し込む事でメモリを節約する。
しかしながらこれは、キャッシュを考慮したアプローチではなく、現在のプロセッサでは
不十分なパフォーマンスにつながり得る。
この論文では、既存の手法とうまく組み合せたキャッシュを考慮した
トライベースのデータ構造であるHAT-trieを提案する。
いくつかの現実のデータセットを使用したり、他の高性能なデータ構造と比較して性能を評価する。
ほとんどの場合、キャッシュを考慮したハッシュテーブルに匹敵するぐらいの
実行時間とメモリ使用量の改善が見られた。
HAT-trieはソート順を維持した可変長文字列を扱う最も効率的なトライベースのデータ構造と思われる。
0851デフォルトの名無しさん
2008/12/12(金) 11:22:50初めて本格的な翻訳作業をしますがなかなか面白いですね。
段落ごとにまったりとやっていきますので。。
----------------
3 The HAT-trie
現在可変長文字列を扱う(格納、検索)利用可能な最も速いデータ構造はburst-trieと
アクセス時にmove-to-frontするチェーンハッシュテーブルである。(Zobel et al. 2001)
これらのデータ構造は検索と更新に必要な命令を最小にするので速いが
とくにキャッシュを考慮しているわけではない。
我々は資料からlinked lists(bucketsやchainsとしてそれぞれ利用される)が原因である事を知っている。
0852デフォルトの名無しさん
2008/12/12(金) 11:24:460853デフォルトの名無しさん
2008/12/12(金) 20:03:11ってどういう事?
0854デフォルトの名無しさん
2008/12/12(金) 20:08:110855デフォルトの名無しさん
2008/12/13(土) 01:06:000856デフォルトの名無しさん
2008/12/13(土) 09:13:33翻訳が怪しくなりそうなところは英単語のままにしてあります。
アクセス時にmove-to-frontするというのは良く分かりませんが、直訳ぐらいにはなってるでしょうか。
>>855
すみません。今回は翻訳は置いといて(継続!?)
お詫びに、昨日お風呂の中でふと思いついたネタを投下します。
はじめに(論文っぽく)
ハッシュは完全ハッシュしか良いとは思っていません。例えば、>>844でいうと
1 <= A->B->C->A
2 <= A->B->C->B
3 <= A->C->C->C->D
という処理をハッシュでやると、右側を文字列として
int[][][][][] pattern;
pattern['A']['B']['C']['A'][0] = 1;
pattern['A']['B']['C']['B'][0] = 2;
pattern['A']['C']['C']['C']['D'] = 3;
という感じでやります。
しかし、たった5文字でint * 256^5=int * 1099511627776Byteのメモリを使います。
そこで最小完全ハッシュを考えます。最小完全ハッシュとはハッシュ値を
0からデータ数-1に割り振る事です。例えば'A'を1、'B'を2、'C'を3にする事を考えますと
すぐに思いつくものはkey['A'] = 1という感じでやれば出来ます。
このまま終わればそっちのネタになってしまいますが、ここからが本題です。
最小完全ハッシュの為のキーを返す処理にただの完全ハッシュを使うのでは本末転倒ですが
その処理を量子演算、量子アルゴリズムを使えば簡単に出来てしまうのではないか
という事を思いつきました。ただの思いつきではなくて見込みのある思いつきだと思います。
そこで量子演算、量子アルゴリズムについて話題を振りたいと思います。(おれ誰?)あ、出掛けます。。。
0857デフォルトの名無しさん
2008/12/14(日) 04:24:470858デフォルトの名無しさん
2008/12/14(日) 06:01:04そんなこと普通に勉強してれば思いつく程度だし、第一そのアプローチだと「神は存在するんだ!」みたいなドツボにはまるだろう。
>しかし、たった5文字でint * 256^5=int * 1099511627776Byteのメモリを使います。
だってこの発想からだろw
続きはブログでやれ。ブログぐらい持ってるよな?w
0859デフォルトの名無しさん
2008/12/14(日) 11:40:590860デフォルトの名無しさん
2008/12/15(月) 04:18:46その通りでした。でも、完全ハッシュを説明する為の例なので、言いたい事が伝わればいいかなと思います。
>>858
ブログありますよ。だいぶ書いてないので、仕様で少し大きめの広告をのせられてますが。。。
>>859
BM法は今まで使う機会が無かったですが、>>844には良さそう(?)です。良く分かりませんが。
量子アルゴリズムには一匹も釣れ・・誰も反応しませんねぇ。改めてWebで調べたら思っていたのと
ちょっと違う感じでしたが、少し考えを進ませました。量子アルゴリズムは厳密ではなくても高速で
結果を知りたい場合に有効らしいので、それを元に考えてみました。例えば、キーが3bitで表せるとして
101, 000, 010のデータに最小完全ハッシュを施すのに、3bitの全パターンの全並び(順列)の中から
データがなるべく始めの方に固まっているパターンを見つけます。 例えば100 000 010 101 001 111 110 011
という並びは、始めの4つまでに全データが現れるので、ハッシュの大きさは4つ分ですみます。
次に、全並びに番号をつけたとしてその並びの番号を覚えます。この場合は0〜!(2^3)-1の番号をつけて974を
覚えます。そして、例えば000のキーが知りたい場合は、番号から並びをほぼ正確に復元して
データのある位置がキーになり、なるべく正しい位置を探します。
この処理のどこかに量子アルゴリズムを適応できるか。あと、格納は置いときます。
翻訳>>851のつづき
-------------------------------------------------------------------------------
burst-trieのボトルネックを解決する為、トライ走査のコスト(作成されるだろうトライノードの数)を
かなり削減しなければならないが、より重要なのはbucketsを探すコストであるが、
それらが現在アクセスする中で最もコストのかかる要素だからである。
そのような削減はbucketsの表現をlinked listからキャッシュを考慮した巨大な配列に
変える事でしか達成できない。したがって、それはキャッシュを考慮したハッシュテーブルの
bucketsの構造化を考えるとよい(Askitis & Zobel 2005)。
シンプルな配列と対照させてハッシュ配列を使う利点は、bucketsがはるかに効率的にscale muchでき、
さらに保持されるトライノード数を減らせることである。
0861デフォルトの名無しさん
2008/12/15(月) 04:47:32ここに長文を置かずにBlogに置いて、ここから誘導するようにすると喜ばれるでしょう。
0862デフォルトの名無しさん
2008/12/15(月) 04:56:42なんつーか、層化みたいな新興宗教の奴らと同じなんだよね。
0863デフォルトの名無しさん
2008/12/16(火) 12:04:510864デフォルトの名無しさん
2008/12/16(火) 16:41:59中途半端はよくないよ
0865デフォルトの名無しさん
2008/12/16(火) 20:58:14多くの人は途中経過に興味はないだろうし、俺は結果にも興味は無い。
0866デフォルトの名無しさん
2008/12/17(水) 18:29:56ただし、各ノードは子ノードだけ持っていて親ノードや兄弟ノードに関する情報は持ってないものとします
現在考えているのは、Iteratorの内部に現在たどっているノードをスタックで保持するってかんじなんですが、
もっと効率よい方法があるんじゃないのかなー?って思ったんです
0867デフォルトの名無しさん
2008/12/17(水) 18:44:55木構造のイテレータは全部それで実装したよ。
効率が良いとされる方法はB+木みたく葉を全部末端に集めて
線形に辿らせるぐらいしかないんじゃないの。
構造に依存するし付け替えも面倒だけど。
0868デフォルトの名無しさん
2008/12/17(水) 18:46:22末端の空きノードを利用するって事だったけど忘れた。
0869デフォルトの名無しさん
2008/12/17(水) 18:49:46追加や削除で余計なコストも掛からないから速度も大して変わらないと思うけどね。
0870デフォルトの名無しさん
2008/12/20(土) 01:36:40あれと同じようにすればいいんじゃないか。
0871デフォルトの名無しさん
2008/12/27(土) 22:19:19短い方法はないでしょうか?
n = n & 0x8 ? 1 : 0;
n = (n & 0x8) == 0x8;
0872デフォルトの名無しさん
2008/12/27(土) 22:23:34unsigned char n;
n = (n & 0xf0) + (((n & 0x8) == 0x8) << 4 );
のようなことです。
0x17なら0x10、
0x18なら0x20、
0xffならオーバーフローして0でかまいません。
これをもっと簡単にできないかと。
0873デフォルトの名無しさん
2008/12/27(土) 22:55:390874デフォルトの名無しさん
2008/12/27(土) 23:05:15ありがとうございました。
0875デフォルトの名無しさん
2008/12/27(土) 23:14:21http://namidame.2ch.net/test/read.cgi/eco/1205843429/l50
1 :金持ち名無しさん、貧乏名無しさん:2008/03/18(火) 21:30:29
アメリカは、アメロに移行し、わざとドルを暴落させ、
国債を返還するのではないかという説
アメロ
http://www.y-asakawa.com/message/amerikano-inbou.htm
ふーむ、ジム・ロジャース氏がドル建て資産をすべて処分したのも・・・???
アメリカに対して厳しすぎるのではないかとの問いに
2年後にわかるだろうと答えたのも・・・
気になるところです
0876デフォルトの名無しさん
2009/01/07(水) 23:29:40ってのを考えてます。
要するに除算なんですが、vec.size() == divisor であ
り、かつ、vec 内の総和が divident に等しいものです。
divident % divisor をブレゼンハムみたいに振り分け
たいのでブレゼンハムから色々考えてみたんですがうま
くいきませんでした…。
0877デフォルトの名無しさん
2009/01/07(水) 23:56:08void div(std::vector<unsigned>& vec, unsigned divident, unsigned divisor) {
vec.resize(divisor);
uint64_t prev = 0;
for (unsigned i = 0; i < divisor; ++i) {
uint64_t cur = (uint64_t(i + 1) * divident + divisor / 2) / divisor;
vec[i] = unsigned(cur - prev);
prev = cur;
}
}
0878デフォルトの名無しさん
2009/01/08(木) 10:41:10要するに、ある整数(divident)をある個数(divisor)で分割するって事?(「要するに」の使い方を参考にしてください)
> divident % divisor をブレゼンハムみたいに振り分けたい
まず、vecにはそれぞれdivident / divisorを入れるのはOKですよね。
次に、余り(divident % divisor)を振り分けるのは
vecの0から(divident % divisor) - 1までを+1すればいいのではないでしょうか。
0879デフォルトの名無しさん
2009/01/08(木) 10:58:280880デフォルトの名無しさん
2009/01/08(木) 11:05:51少しキツイ言い方になりましたが、これは>>877やその他の方への配慮です。
丁寧さに限度はないと思いますので、質問は出来るだけ伝わりやすくした方が良いのかなと思います。
ついでに面白い読み物を紹介
身近な具体例の利用は数学学習の助けにならない
http://health.nikkei.co.jp/hsn/hl.cfm?i=20080501hk000hk
テレビのニュースで見たのですが、最初は「えっ」と思いました。
最近、気になって検索して読み返したら、「文章題やおはじき・・・」で始まる最後の段落を見て納得しました。
どこが納得したのかははっきりは言えませんが、今まで考えていた事を否定する内容ではなかったようです。
回りくどくなってしまいましたが、具体例は伝えやすくする為に便利です。
0881デフォルトの名無しさん
2009/01/08(木) 11:09:15あ、ちょっとレスが前後してしまいました。
整数ではこれ以上均等に配分できません。
0882デフォルトの名無しさん
2009/01/08(木) 11:25:301 1 0 0 0
ではなくて
0 1 0 1 0
のようにしたいということなんですが。
DDA っぽくと言い換えてもいいけど。
0883デフォルトの名無しさん
2009/01/08(木) 11:30:170884デフォルトの名無しさん
2009/01/08(木) 13:59:44しばらく考えてみます。
0885デフォルトの名無しさん
2009/01/08(木) 14:03:32int[] data;
for(int i = 0; i < 5; ++i){
s += 2;
if(s >= 5){
data[i]++;
s -= 5;
}
}
0886デフォルトの名無しさん
2009/01/08(木) 14:07:090887デフォルトの名無しさん
2009/01/08(木) 14:20:08int s = 0;
int[] vec;
for(int i = 0; i < divisor; ++i){
s += divident;
while(s >= divisor){
vec[i]++;
s -= divisor;
}
}
0888デフォルトの名無しさん
2009/01/08(木) 14:21:590889デフォルトの名無しさん
2009/01/08(木) 15:43:00うちょっと考えると while() が消せるかも(ブレゼン
ハムで線引く場合に縦長/横長で場合分けする感じ)。
void Div(vector<unsigned>& vec, unsigned divident, unsigned divisor) {
int e = divisor;
while (vec.size() < divisor) {
e -= 2*divident;
unsigned q = 0;
while (e <= 0) {
e += 2*divisor;
++q;
}
vec.push_back(q);
}
}
0890デフォルトの名無しさん
2009/01/08(木) 21:30:43vec.resize(0);
vec.reserve(divisor);
unsigned div = divident / divisor;
unsigned mod = divident % divisor;
unsigned of = divisor;
for(std::vector<unsigned>::size_type c=divisor;c--;){
of += mod*2;
vec.push_back(of >= divisor*2 ? of -= divisor*2 , div + 1 : div);
}
}
0891デフォルトの名無しさん
2009/01/08(木) 23:27:56データ内容 1から40億までのUINT型の値
こんなデータ内容を格納するのに最適な
木構造って何かありますでしょうか?
0892デフォルトの名無しさん
2009/01/08(木) 23:44:590893デフォルトの名無しさん
2009/01/08(木) 23:52:18順序性のある連想配列が必要なら平衡2分探索木とか、
最小値だけ必要ならヒープとか。
それこそ単なる連想配列として使いたいなら
いっそハッシュテーブルでいいし、
格納するだけならリストでいい。
整数ってだけじゃ木構造で
特別有効なデータ構造は思いつかないが…
0894デフォルトの名無しさん
2009/01/09(金) 00:02:59要素数や値の最大値が見えてるから
それを使えば色々と高速な構造がある。
0895デフォルトの名無しさん
2009/01/09(金) 00:06:350896デフォルトの名無しさん
2009/01/09(金) 00:21:44Bツリーか赤黒木を作ろうかと思います
0897デフォルトの名無しさん
2009/01/09(金) 00:22:390898デフォルトの名無しさん
2009/01/09(金) 00:35:230899デフォルトの名無しさん
2009/01/09(金) 01:58:19計算量は同じようですが
0900デフォルトの名無しさん
2009/01/12(月) 08:50:401.点数がnの完全2分木の高さhを厳密に求めよ。そのうえで、h=Θ(log(n))であることを示せ。
2.単純な無向グラフGを表現する隣接行列をAとする。また、A^k=(※)とする
※aの右下にij、右上に(k)
(1)A^2,A^3,...,A^iは何を表すか
(2)(aの右下にii、右上に(2))は何を表すか
(3)1/6Σ(aの右下にii、右上に(3)) は何を表すか。ただし、n=n(G)とする。
できれば考え方等も教えていただけるとありがたいです。
0901デフォルトの名無しさん
2009/01/12(月) 13:01:581.
n = 8 くらいまで書いて類推するだけ.略.
2.
(1). A^k は,ij 成分が「i から j へ k 歩で行く方法の数」を表す行列.
これは冷静に考えればわかる.分からないなら帰納法で確認.
(2), (3) は (1) を使えばいいだけで,たとえば (2) だったら
「i から i へ 2 歩で行く方法」がどんなものがあるかを考えればいい.
(3) も同様.ただし同じものをマルチカウントするので 1/6 している.
0902デフォルトの名無しさん
2009/01/12(月) 20:18:08ぶっちゃけB木の方が速い
0903デフォルトの名無しさん
2009/01/12(月) 20:39:54B木書くの面倒やだ
0904デフォルトの名無しさん
2009/01/13(火) 00:22:46これ再起無しにするの難しい
0905デフォルトの名無しさん
2009/01/13(火) 00:45:48スタックを自分で作ればいいだけ。
0906デフォルトの名無しさん
2009/01/13(火) 00:58:34http://d.hatena.ne.jp/yaneurao/20051008
http://d.hatena.ne.jp/yaneurao/20051025
http://d.hatena.ne.jp/yaneurao/20060227
0907デフォルトの名無しさん
2009/01/18(日) 00:11:26鬱になりそうです助けてください
0908デフォルトの名無しさん
2009/01/18(日) 01:12:47真面目に「高速な」ものを作ろうと思ったら
CPUの特徴とかを考えながら組むんだけど,
そういうことをしたいの?
とにかく問題設定がよく分からないので
なんともいえない.
0909デフォルトの名無しさん
2009/01/18(日) 01:28:030910デフォルトの名無しさん
2009/01/18(日) 02:25:35ソートは結構な種類がありますが、文字列の方の比較的簡単なアルゴはあとはハッシュ法ぐらいしか思い浮かびません。
一応正規表現を自作してるのでstrstr(とmemchr)は切っても切り離せないんですけど、何か助けとなるような助言はありませんか?
0911デフォルトの名無しさん
2009/01/18(日) 02:28:57そもそもバイナリサーチが遅いということ自体あり得ないと思うんだが。
どんなに遅くても 32 回もかからんっつーのに。
0912デフォルトの名無しさん
2009/01/18(日) 02:31:36助言もなにも、何がしたいのかが分からんよ。
文字列検索なんて、それだけで一冊本が書けるほど大量にある。
簡単なものでも http://www-igm.univ-mlv.fr/~lecroq/string/index.html くらい。
0913デフォルトの名無しさん
2009/01/18(日) 02:31:480914デフォルトの名無しさん
2009/01/18(日) 02:31:54有名なのには他にKMP法ってのもあるよ。
Wikipedia を見ると他にもあるようだよ。
ttp://ja.wikipedia.org/wiki/%E6%96%87%E5%AD%97%E5%88%97%E6%A4%9C%E7%B4%A2%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
0915デフォルトの名無しさん
2009/01/18(日) 02:41:45データサイズが非常に大きいとか
CPUが貧弱とか
バイナリサーチを多数回実行するとか
バイナリサーチを僅かでも高速化したい状況は結構あるよ。
0916デフォルトの名無しさん
2009/01/18(日) 03:10:01奥村先生の本でやってるんですけど文字列検索はあまり載ってなかったんで、検索アルゴはあまりないのかなって。
ただ、正規表現自体が文字列検索そのものなので、BM法みたく表作ろうかどうしようかなって・・・
ソートしたり、表作ったりするよりも、結局一番単純なmemchrがいいのかなってのが感想です。
多少遅いかも知れませんが、今のハードの資源を考えると、BM法も単純なリニア検索もたぶん10ミリ秒以内の差しかないんでしょうけど。
検索アルゴ自体よりも、newしたりメモリにアクセスする方が時間かかるんじゃないかなとか・・・
0917デフォルトの名無しさん
2009/01/18(日) 03:17:220918デフォルトの名無しさん
2009/01/18(日) 03:43:17Javaスレにいたアルゴ厨です。
0919デフォルトの名無しさん
2009/01/18(日) 03:44:15やっぱり何がやりたいか分からんよ.正規表現をどうしたいんだ.
あと線型探索は実装にもよるけど普通は O(n^2) でしょ.
aaaa....a から aaa...b を探すことを考えたら時間が大差なのは明らかだと思うけど.
0920デフォルトの名無しさん
2009/01/18(日) 03:47:34http://www.sansu-olympic.gr.jp/algo/ これじゃね?
0921デフォルトの名無しさん
2009/01/18(日) 03:49:400922デフォルトの名無しさん
2009/01/18(日) 04:07:54アルゴは、アプリと同じくなんとなく響きがいいですよね。
既にどういう状況でアルゴを適用するか決定してるので、>>919のようなaaaaaa...aの状況は現実的にありません。
別に100ミリ秒以内に結果が出ればどうでもいいかなってところです。上の10ミリは100ミリの間違えです。
どうせGUIとかWEB環境で使うつもりなんで難しい実装で小手先技を披露するよりも、
簡単な実装でかつバグがなく動く(必ず停止する)方が重要なんで・・・そういう実装が容易なアルゴはないかなって。
0923デフォルトの名無しさん
2009/01/18(日) 04:12:32いいえ。
0924デフォルトの名無しさん
2009/01/18(日) 04:25:16林はるひこの本も手元にあるんですけど、はるひこもアルゴも同じぐらいキモキモ・オーラが出てるですけどね。
とすると、アルゴってのが嫌なら、アプリって省略することも、あなたの信念に反するんじゃないですか?
0925デフォルトの名無しさん
2009/01/18(日) 04:25:280926デフォルトの名無しさん
2009/01/18(日) 04:27:55正規表現を実装したかったのか.
正規表現なんて決まりきった実装法があるでしょ.
決定化しなかったら数十行で書ける.
memchr やら何やらを持ち出す理由が分からん.
0927デフォルトの名無しさん
2009/01/18(日) 04:29:56アルゴ:使う人が極少でキモメンばかり
OK?
0928デフォルトの名無しさん
2009/01/18(日) 04:44:54いや、だから正規表現自体が、(検索キー・パタンが固定ではない)文字列探索なんですけど。おk?
0929デフォルトの名無しさん
2009/01/18(日) 04:51:15これも一つの情報のデータ圧縮でしょうかね?!
計算速度の高速化とかオーダーにこだわったりして業界に深くかかわっていると観念が固定化してしまい、新しい発想(発明)ができなくなりますよ。
0930デフォルトの名無しさん
2009/01/18(日) 04:58:590931デフォルトの名無しさん
2009/01/18(日) 05:05:30それがどうしたの?
0932デフォルトの名無しさん
2009/01/18(日) 05:08:57よくあるトンデモ系の意見だな。
先行研究に対する理解なしに新規的な発明はできんよ。
0933デフォルトの名無しさん
2009/01/18(日) 05:09:090934デフォルトの名無しさん
2009/01/18(日) 05:28:18あまりに複雑な仕様のコンパイラなどは誰だって実装したくはありませんよね。
実際ハードの方が技術革新していった高速化していけば、線型探索でも十分に実用なんでしょうけど。
その発明&研究した複雑怪奇なアルゴリズムはいつ寿命が尽きるんでしょうか?
0935デフォルトの名無しさん
2009/01/18(日) 05:51:59> 実際ハードの方が技術革新していった高速化していけば、線型探索でも十分に実用なんでしょうけど。
そんなことはないよ。
ハードウェアが高性能化すればするほど扱えるデータが増えるから、
効率の良いアルゴリズムが必要になる。
アルゴリズムが使われなくなるのは、より良いものが出たときだけ。
つーかそもそもの話題だった正規表現の標準的なアルゴリズムは
非常に簡単で、しかも高速なんだけど?
0936デフォルトの名無しさん
2009/01/18(日) 06:05:06ネタ投入するといきなり活性化するスレですね。
あなたの論調では、扱えるデータ量が増えたら、それを扱う使う人も当然データ量を増やしていくって前提がありますね?
普通の人間なら、新しい機械が導入されたとしても従来からやってる仕事(例えばお役所仕事・事務処理とか)が速く終わるってことだけであって、
だからといって従来の仕事量以上の仕事を抱え込んだりはしませんよ。どうせ給料も同じなんでしょうし。
そういう辺りをちゃんと考慮しているかどうかってのが現実的な実用的なアルゴかどうかってことです。
正規表現は、文字クラス[ab]をどうしようかなってところですけど。
0937デフォルトの名無しさん
2009/01/18(日) 07:18:32> 難しい実装で小手先技を披露するよりも、
> 簡単な実装でかつバグがなく動く(必ず停止する)方が重要なんで
だったら、まずは線形探索で十分かどうか試すべきでは?
案外それで100ミリ秒の要求が達成できるなんてこともあり得る。
もう試していたらごめん。
0938デフォルトの名無しさん
2009/01/18(日) 09:19:240939デフォルトの名無しさん
2009/01/18(日) 10:15:21おい
紀伊店丘
おい
データ量=給料らしいぞ
0940デフォルトの名無しさん
2009/01/18(日) 11:18:47> 正規表現は、文字クラス[ab]をどうしようかなってところですけど。
お前には無理。
0941デフォルトの名無しさん
2009/01/18(日) 11:19:01入力値7を入れると
結果値10を返す検索を実現したいのですが
やり方が全然わかりません。
自分より大きくて配列要素の中でもっとも近い
要素を返す処理だと思うのですが
どうやって書けばいいのか思いつきません
0942デフォルトの名無しさん
2009/01/18(日) 12:01:49配列の最小値を探す処理は書けるか?
書けるなら、入力の配列から7以下の要素を取り除いた配列を作って、それの最小値を返せばいい
最小値を探す処理を工夫して、7以下の要素を無視するようにしてもいい
入力が昇順に並んでいることを仮定していいなら、二分探索が使える
0943デフォルトの名無しさん
2009/01/18(日) 16:08:53http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-639.pdf
これCで実装できる神様いませんか?
0944デフォルトの名無しさん
2009/01/18(日) 16:32:140945デフォルトの名無しさん
2009/01/18(日) 16:32:260946デフォルトの名無しさん
2009/01/18(日) 16:37:36状況は変わってないようだな
0947デフォルトの名無しさん
2009/01/18(日) 16:44:40コテンパにやられたんですねw
調子にのっちゃうとコテンパにされて痛い目にあう典型例ってことでしょうか。
0948デフォルトの名無しさん
2009/01/18(日) 17:06:36>コテンパにやられたんですねw
コテンパって何ですか?
0949デフォルトの名無しさん
2009/01/18(日) 17:07:480950デフォルトの名無しさん
2009/01/18(日) 17:17:27C/C++でも差はないのですが、なにぶんゼグメント・バイオレンスや時間関係のライブラリ(並列計算なども)が充実してないので、
それも自分で実装して再発明したり数値計算パッケージを導入することになります。
すると本来実装したいアルゴリズム以上の苦労がありませんか?
まさか「言語なんてどれも一緒。アセンブラでやれよ」ってのなしで。
0951デフォルトの名無しさん
2009/01/18(日) 17:25:010952デフォルトの名無しさん
2009/01/18(日) 17:30:26実験や試験的に試行錯誤したりするときはやっぱりC/C++なんですか?
アルゴリズはほとんどがメモリ操作であって、ハードをいじったりハードにアクセスすることはないので、
C/C++じゃなくJavaやRuby,C#(他のでもいいんですけど)でいいかなと思うんですが。
0953デフォルトの名無しさん
2009/01/18(日) 17:31:08アルゴリズムの種類にも、状況にも拠る。
行列が対象ならmatlabクローンのoctaveで確認してからってこともあるし、
数値解析関係ならmklが使えるc/c++からってこともあるし、
持ってお手軽にOpenOfficeCalcでちょちょいと試してからってこともある。
0954デフォルトの名無しさん
2009/01/18(日) 17:32:27Cだとメモリ確保が面倒だってこともあるけれど、C++ならクラスも使えるしSTLもあるから融通が利くと思うが。
0955デフォルトの名無しさん
2009/01/18(日) 17:32:590956デフォルトの名無しさん
2009/01/18(日) 17:42:470957デフォルトの名無しさん
2009/01/18(日) 17:50:57アルゴリズムの実装にクラス生成が必要ならその意見もわかるんですけど、そこまでC++に慣れちゃってるんですか?
べつにC/C++でも普通に使えるんでなんでもいいんですけど、Cはポインタに関係するバグ(というかコードミス)が多くて実装と関係なく、
C++はvtableがらみアライメントがらみでこれまた面倒が多いので、結局現代的なJavaとかになるんじゃないかなって。
Java,C#はGUI(アプレットとか)も簡単に作れるんで、グラフ化したり視覚的に速度比較するのも余裕なんですが。
The Sorting Algorithm Demo (1.1)
http://java.sun.com/applets/jdk/1.3/demo/applets/SortDemo/example1.html
英語はそんな苦じゃないので主にJava使ってますけど。
0958デフォルトの名無しさん
2009/01/18(日) 17:57:090959デフォルトの名無しさん
2009/01/18(日) 18:00:42http://pc11.2ch.net/test/read.cgi/tech/1226761546/
0960デフォルトの名無しさん
2009/01/18(日) 18:01:05いやだから、何でわざわざ地雷を踏まないといけないのよ。
C++使うからといって必ず継承するような必要もないし、低レベルのメモリ管理をする必要もないんだけど。
例えばたまたま手元にあるデータをちょっと加工したいときはawkを使うことだってあるけど、
そんなときに処理速度なんか気にしないしね。
あんたがJavaやC#やRubyに精通していて、他はろくに知らんと言うのなら黙ってJavaやC#やRubyを使っていてくれ。
こっちは適材適所でやるから。
0961デフォルトの名無しさん
2009/01/18(日) 18:01:07とりあえずコテハンつけてくんない?
0962デフォルトの名無しさん
2009/01/18(日) 18:18:37確実に停止するか(解が得られるか)が一番大事なことなんじゃないでしょうか?
それも、汎用的なアルゴリズムは既に50-70年代で出し尽くしてるので、
それ以上の技巧を凝らすのはナノ秒を競い合って職人技(論文)合戦しているだじゃないですか。
新しい分野たとえば動画の動き予測とかガベジコレクトとか資金が流れてるところはアルゴリズム研究もHOTななんですけどね・・
なので、解が得られるかどうかが一番大事なのにいつのまにか速度(O[n^2]とか)の問題になって、速度(速く解が得られるか)にこだわる意味が全く分からないんですが、どうしてですか?
そういう速い・実用ではないなどの問題はアルゴリズムじゃなくてハードの問題なんじゃないでしょうか?
0963デフォルトの名無しさん
2009/01/18(日) 18:20:460964デフォルトの名無しさん
2009/01/18(日) 18:30:14log n と n^2 を同列に扱えって主張はおかしい。
0965デフォルトの名無しさん
2009/01/18(日) 18:32:53適材適所とかなによ?誰もあんたのプログラミングスタイルなんか聞いてないよw
0966デフォルトの名無しさん
2009/01/18(日) 18:35:32その通り。これを評価する仕組みがO記法によるオーダー。これは計算量であって速度そのものではない。
例えば、O(n)やO(n log n)くらいなら、ハードウェアの性能向上でなんとかなると言える。
逆にO(c^n)なら入力をちょっと増やすだけですぐに計算量がおそろしく増えるから、
ハードウェアの性能向上は待っていられないねという具合。
現在、1日で答えが欲しい問題を解くに1年かかるなら、それは答えが出ないのと同じこと。
0967デフォルトの名無しさん
2009/01/18(日) 18:41:510968デフォルトの名無しさん
2009/01/18(日) 18:42:41なんて考えつく人は○○賞もらうレベルの人で滅多にないから。圧縮とかでも。
それをベースとして2,3度修正して速度調整する程度でアルゴリズム(ソフト)上の仕事は終わり。
例えば、O[n^2]だとしてもそのハードで40ナノ秒程度なら誰も気にしないよ。
かといってO[1]なのに、5秒掛かるなら問題あるなぁ。
例えばハイパリンク押した(定数)なのに、応答(ダウンロード)が5秒とか。
実践云々じゃなくて、そういうこと。
0969デフォルトの名無しさん
2009/01/18(日) 18:47:03普通のアルゴリズム論の文脈では、停止しないものはアルゴリズムとは言わない。
あと、普通のアルゴリズム系の論文では実時間を競うようなことはしない。
実時間なんて実行環境によっていくらでも変わるから、オーダーで測る。
0970デフォルトの名無しさん
2009/01/18(日) 18:48:02頼むからコテハンつけてくれ
0971デフォルトの名無しさん
2009/01/18(日) 18:56:37計算量=実実行時間なの?バカなの?死ぬの?
0972デフォルトの名無しさん
2009/01/18(日) 18:58:520973デフォルトの名無しさん
2009/01/18(日) 18:59:26あの〜意味が全く分からないですが、O[c^n]のアルゴwをn=2Gのデータ量に適用した場合、nが600MB増減してまあまり関係ないと思うんですけど。
たとえばコーデックとかだと当たり前ですよ?w
製作時間(総レンダリング)が3年にも及ぶCGを駆使した映画とか昔はありましたけど?
その1年ですけど、O[c^n]のアルゴwで並列計算(PC100台とかGPU20枚のハード)でやったら30秒で答えが出たとき、あなたは考え方を変えますかね。
どうせあなたは教科書読んで勉強すら出来ない人なんでしょうけど、あなたは何を言いたいんですか?
0974デフォルトの名無しさん
2009/01/18(日) 19:11:220975デフォルトの名無しさん
2009/01/18(日) 19:13:32かなり関係あると思うんですけどーwwwwwwwwwwwwwwwww
0976デフォルトの名無しさん
2009/01/18(日) 19:20:52大まかには単純にコア数分の1にしかならない。
実際にはコア数分の1になるのは並列化効率100%の時だけで、
100%に満たない場合はいくらマシンを増やしても
あまり効率が上がらない限界が存在する。
アムダールの法則でググれ。
0977デフォルトの名無しさん
2009/01/18(日) 19:24:330978デフォルトの名無しさん
2009/01/18(日) 19:27:02例えば、素数を割り切れるかどうかで判定しようとすれば
1 - 100 と 101 - 200は別々に処理できる。
0979デフォルトの名無しさん
2009/01/18(日) 19:36:59だから通常の利用で1秒以内に答えが欲しいなら、O[n]もO[n^2]も実質同じってことです。
実質同じなのに性能比較する必要はあまり実益があるとはいえません。
つまりハード(資源)が速く十分に使えるため、アルゴリズムが性能に及ぼす影響は全くないということです。
O[c^n]とかでも今のハード(例えば携帯とか)では n<2^64 までとか縛ればいいだけです。
なんか「理系が騙される統計のマジック!」とかと同列の議論ですね。w
それにも係わらずいつまでもオーダを気にするのはいかがなものかと。
0980デフォルトの名無しさん
2009/01/18(日) 19:39:230981デフォルトの名無しさん
2009/01/18(日) 19:41:33ここはアルゴリズムのスレなので、オーダを気にするところです。
つまり、自らスレ違いである理由を列挙しているということです。
0982デフォルトの名無しさん
2009/01/18(日) 19:43:01いくら早くてもあまりに実装が複雑なアルゴ、あまりに難解な論文はいらないかなって・・・
そのうち(3年程度で)ハードの方が速くなって、そういう運用のためのコストが高いアルゴリズムはどうでもよくなるんですけど、どうしてオーダでしか評価しないんですか?
0983デフォルトの名無しさん
2009/01/18(日) 19:45:440984デフォルトの名無しさん
2009/01/18(日) 19:52:39差分時間も3ミリ秒程度で実質同じなのに・・・
情報系が騙されるオーダ記法のマジック!w
0985デフォルトの名無しさん
2009/01/18(日) 21:05:190986デフォルトの名無しさん
2009/01/18(日) 21:15:13クイックソートはqsortを呼び、PNGを作りたければlibpngをリンクする。
0987デフォルトの名無しさん
2009/01/18(日) 21:51:570988デフォルトの名無しさん
2009/01/18(日) 21:59:24自分たちの開発対称になってるドメイン固有の問題はどうすんの?
0989デフォルトの名無しさん
2009/01/18(日) 22:12:540990デフォルトの名無しさん
2009/01/18(日) 22:16:49さあ?アルゴ本人に聞いてみたいところだ。
0991デフォルトの名無しさん
2009/01/18(日) 22:46:03それともここ使う?
http://pc11.2ch.net/test/read.cgi/tech/1217773415/
0992デフォルトの名無しさん
2009/01/18(日) 23:25:211つでいいよ
0993デフォルトの名無しさん
2009/01/18(日) 23:30:330994デフォルトの名無しさん
2009/01/18(日) 23:32:000995デフォルトの名無しさん
2009/01/18(日) 23:34:230996デフォルトの名無しさん
2009/01/19(月) 00:12:400997デフォルトの名無しさん
2009/01/19(月) 00:16:100998デフォルトの名無しさん
2009/01/19(月) 00:56:320999デフォルトの名無しさん
2009/01/19(月) 03:35:571000小倉優子 ◆YUKOH0W58Q
2009/01/19(月) 03:36:2810011001
Over 1000Threadもう書けないので、新しいスレッドを立ててくださいです。。。
レス数が1000を超えています。これ以上書き込みはできません。