05/10/15 20:42:23
前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉
>プログラム板の皆さん、こんにちは。
>無謀にもこんなスレを立ててみました。
>四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。
>人間にとって計算しやすい方法についても別途語ることにしましょう。
前スレ↓
ｽﾚﾘﾝｸ(tech板)
2:デフォルトの名無しさん
05/10/15 20:52:57
2 get
3:デフォルトの名無しさん
05/10/15 21:10:02
やれやれ、
プログラミングの為の数学と算数 vol.2
ｽﾚﾘﾝｸ(tech板)
を使ってクレって言ったのに、たてちゃったか。
ようし、前スレで我慢してたけど、 精度ネタいっちゃうぞ。
まずは、「2直線の角度を求める」ネタだ。
前スレでは、ベクトルの内積A・B A・B ＝ cos(φ) *|A|*|B| から、角度を求める。
こいつは2つのベクトルの角度の定義でもあるから王道のように見えるだろう。
しかし、問題はcos(φ)が１に近い時、つまり２直線が平行に近くなると精度が悪いという事だ。
解決は簡単で、Aに垂直な線で同じことをやれば sin(φ）が求まるという事を利用して
cos と sin から atan2 で求ればいい。
さあ、↓ まずは2次元で公式を作ってみよう
4:デフォルトの名無しさん
05/10/15 21:15:50
キモイ↑
5:デフォルトの名無しさん
05/10/15 21:28:05
ながい ↑
6:デフォルトの名無しさん
05/10/15 21:41:28
まとめサイトまだー
7:デフォルトの名無しさん
05/10/15 21:57:53
おまえらノリ悪いぞ。
方向ベクトル [dx,dy] を90度回転させれば [dy, -dx] になる
つまりx,yを入れ替えて片方負数にすればいい
内積 (dx1*dx2+dy1*dy2) 90度回転させた相手との内積 (dy1*dx2-dx1*dy2)
で この比の ArcTanを取ればいいことになる。 実際にはatan2を使えば良い。
8:デフォルトの名無しさん
05/10/15 22:55:06
4つの1から9までの数字と、+、-、*、/とカッコを組み合わせて、
ある自然数が作れるかどうかを判定するプログラムを書いてみたい（出来ればCで)と思います。
数字の方はfor文使って順に変えていけばいいんですが、演算やカッコは
数値じゃないから、色々と変えていく作業をループで回せませんよね?
だから組み合わせの場合わけが膨大になってしまいます。
いい案があれば教えてください。
9:デフォルトの名無しさん
05/10/15 23:02:18
別に、ループで回せばいいじゃない
四則演算は優先順位を付けるの？ だったら計算は再起下降で処理させればいい
10:デフォルトの名無しさん
05/10/15 23:10:59
>9
「カッコの組み合わせ」とあるから、頭っからの総当りで十分だろ。
[0-9][+-*/][0-9][+-*/][0-9][+-*/][0-9]
10*4*10*4*10*4*10=640000通り
実際は被るパターンがあるけど、まぁいいか。
11:デフォルトの名無しさん
05/10/15 23:37:36
たぶん 1+2*3+4 というような計算式をランダムに作った時に、どう計算させればいいかって部分で悩んでると見た
12:デフォルトの名無しさん
05/10/15 23:54:11
12+34は除外？
13:デフォルトの名無しさん
05/10/15 23:59:40
左の数を10倍にして右に足すという演算子を入れたら？ >>12
14:デフォルトの名無しさん
05/10/16 00:04:21
同じ数は二回以上使えないよね？
使えるなら1+1+1+...+1で終了だし。
15:デフォルトの名無しさん
05/10/16 00:05:07
すまん「４つ使う」というのを見てなかった
16:デフォルトの名無しさん
05/10/16 00:08:27
>>10
a/(b+c/d)みたいなのは括弧無しだと無理じゃない？
17:デフォルトの名無しさん
05/10/16 01:05:15
どんな場合にも必ず括弧を付けて演算順序を明記すると決めておけば
*,/と+,-の優先順位は考えなくても良くなる。
計算順は以下の５通りになる。?はいずれかの演算子ね。
チェックの冗長性をもっと減らす方法もあるだろうけど
この５パターンでそれぞれやればいいんじゃない？
((a?b)?c)?d
(a?(b?c))?d
a?((b?c)?d)
a?(b?(c?d))
(a?b)?(c?d)
18:デフォルトの名無しさん
05/10/16 01:09:22
まず2つの数でできる数をすべて列挙して表にする。もちろん分数も考慮。
3つの数の表は2つの数の表から1個と数1数を演算子でつなぐだけ。
4つの数の表は2つの数の表から2個とってくるか、3つの数の表から1個と数1個でつくることができる。
指数オーダーだけど、4つぐらいならなんとかならないか。
19:デフォルトの名無しさん
05/10/16 01:15:18
>18
同じ数字を複数回使えないという制限がある場合にはその方法は難しいな。
>8の文面だけではその制限があるのかどうかわからないが。
20:デフォルトの名無しさん
05/10/16 02:15:28
切符の４桁シリアル番号で10を作る遊びだろ？
(9*9+9)/9
(1/9+1)*9
この２つだけ解れば十分な希ガス。
21:デフォルトの名無しさん
05/10/16 02:16:35
一般的な切符のあれでいいんじゃないの？
22:デフォルトの名無しさん
05/10/16 02:49:12
後置記法
23:デフォルトの名無しさん
05/10/16 03:04:57
>>8
整数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);
みたいな感じで。
24:デフォルトの名無しさん
05/10/16 06:39:30
>>23
それじゃ、優先順位を表現出来ないから悩んでるんだろ？
文字配列にして再帰下降で処理すればいいよ
25:デフォルトの名無しさん
05/10/16 06:41:43
var num:Integer; p:PChar;
procedure 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
26:デフォルトの名無しさん
05/10/16 08:12:07
そんなめんどいことしないでも後置記法で表現しとけば式の全生成を含めても瞬殺
27:デフォルトの名無しさん
05/10/16 08:13:31
>>26
1234+++ てな感じで書いてから処理させるわけね。
じゃ、コード書いてみて。 >>25と比べてみたい
28:デフォルトの名無しさん
05/10/16 08:38:01
26より機能低いけどまあこんな雰囲気で
char 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]);
29:デフォルトの名無しさん
05/10/16 08:39:31
スタックが簡単に書ける C++ でないと1レスに入るくらいに簡単にはイカンだろう
それでも、結構めんどくさい。 瞬殺ってわけにはいかんと思うよ。
30:29
05/10/16 08:40:44
と思ったら、>>28 がんばってくれた。
31:29
05/10/16 08:46:35
後置記法なら、
9999XXX という文字列を作って .... X は + - * /
全スキャンをすれば 括弧つき四則演算は全て網羅出来るというわけで
後は、後置記法から逆変換するコードさえ書けば完成って所だね
32:28
05/10/16 08:57:37
>>31
それで表せる式は (a ? (b ? (c ? d))) だけだから駄目． (1 + 2) * (3 + 4) が表せない．
33:29
05/10/16 09:05:05
>>32 なるほどね。99X99XX も必要なのか
34:29
05/10/16 09:19:38
もしかして
9999XXX
999X9XX
99X9X9X
99X99XX
全部必要か？ なら 逆変換しなくていい 再起下降もそう悪くないな
35:28
05/10/16 09:58:58
>>34
それを言われると痛い……．でも中置では全ての式の生成がちょっとややこしくならない？
後置だと↓な感じで再帰回して済むんだけど．
#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;
}
36:28
05/10/16 10:00:55
続き
char *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);
}
37:29
05/10/16 10:53:47
>>35 確かに括弧の対応考えるとめんどくさいけど、
括弧の対応は再起下降処理中にチェック出来るから全部の組み合わせをやる方針なら
ややこしさは同じ程度だろう
ただ計算量は、後置だと組み合わせが少ないから探索目的ならそれで探すべきだな
38:28
05/10/16 13:33:24
>>35 なんか割り算のエラー処理が狂いまくってた orz...
× if (#op[0] == '/' && stack[top-1] == stack[top-2]) return INT_MIN; \
○ if (#op[0] == '/' && stack[top-2] == 0) return INT_MIN; \
39:デフォルトの名無しさん
05/10/16 13:35:14
「計算アルゴリズム」ってどういう意味?
40:検索したら見つけた
05/10/16 14:13:03
#include <stdio.h>
int 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;}
41:デフォルトの名無しさん
05/10/16 14:46:55
>>39
前スレの>>1に聞いてください。
42:デフォルトの名無しさん
05/10/16 16:24:41
>>39
理系・数学板の任意のスレでKingと呼べばいつでも出てきてくれます。
43:デフォルトの名無しさん
05/10/16 17:34:59
3つの円(半径・中心座標はわかっている)に接する円の半径・中心座標を求めるには
どうすればいいんでしょうか？計算方法を教えてください。
44:デフォルトの名無しさん
05/10/16 18:03:09
(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
の連立方程式解くわけでしょ？適当な2式を組み合わせて両辺をさっ引いたらx^2,y^2,r^2の項は全部消える。
その結果が
Ax+By+Cr+D=0
Ex+Fy+Gr+H=0
の形になるはずなので、たとえばxとyの2元連立方程式と思って解く。つまりrの式で表す。
それを最初の式に突っ込んだら解けるんじゃない？
45:デフォルトの名無しさん
05/10/16 18:04:18
接するというのは、組み合わせが多数あると思う。
外包円＝ぴったり３つの円が収まる状態なら
外包円との接点と、中心を結ぶ線上に、接する円の中心もあるというのが拘束条件に出来ると思う
俺なら、厳密解を出すのはメンドクサイから、
一つの円にまず接しておいて、のこり１つの円に接するとした時の求まる 外包円の中心で
外包円を描いて、 最後の一つの円との距離で2分法かニュートン法的に解くかな
46:デフォルトの名無しさん
05/10/16 18:25:50
３つの円を a,b,c 付けて表現すると
３つの円の中心までの距離±半径が 接する円の半径と等しいわけで
(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
になるのでは？
47:46
05/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
48:46
05/10/16 18:54:02
ダメ。解けそうなのに解けんな。 数値解法に一票いれるよ。
49:デフォルトの名無しさん
05/10/16 18:57:01
>>47
あってると思う。
(上)-(中) と (中)-(下) と (下)-(上) で連立させれば
3元1次方程式が出てきてめでたしめでたしじゃないの？
50:46
05/10/16 19:05:40
>>49
うーん途中までやってみたけど、自分の仕事じゃないしな。
51:デフォルトの名無しさん
05/10/16 20:15:50
3つの方程式に4つのパラメタだから解は全然一意じゃないよね．
外接円の中で半径最小のもの，とかしないと求まんないと思う．
52:デフォルトの名無しさん
05/10/16 20:20:12
円だから未知数は３つだろう 中心と半径
53:デフォルトの名無しさん
05/10/16 20:33:32
>>7
外積のほうが説明楽だろ、θ=tan＾-1(|a x b|/|a ・ b|)
54:デフォルトの名無しさん
05/10/16 20:34:10
ごめんなさい r, x, y, z とか数えてました……．
55:デフォルトの名無しさん
05/10/16 20:34:50
数値解も案外厄介だな
56:デフォルトの名無しさん
05/10/16 20:35:51
>>53
元ネタは2次元だから外積持ち出すのは・・・・
57:デフォルトの名無しさん
05/10/17 16:22:40
ていうか、3つの円の大きさとか位置関係とかどうなっているの？
58:デフォルトの名無しさん
05/10/17 18:14:48
そりゃ色々あるんだろう。 だから厄介みたいだね。
59:デフォルトの名無しさん
05/10/17 20:20:52
最悪ケースとして同心円×3 みたいな場合もあるから何も考えずに連立方程式を解くのは危ないかも
60:デフォルトの名無しさん
05/10/17 20:39:42
点の包含球だったらドロニー図書くのと似た技法使うんだっけか。
もう覚えてないや
61:デフォルトの名無しさん
05/10/17 22:11:56
>>60
凸包だね。ドロネー図を求める手法なのは確かだが、凸包の方がはるかに
有名だと思うんだけど。
62:デフォルトの名無しさん
05/10/17 22:31:30
ベジェでかかれた複合パスを分割するアルゴリズムへのポインタを
教えてください。
63:デフォルトの名無しさん
05/10/17 23:33:21
>>56
複素数の導入をはじめとして
次元をひとつ上げると関係が急にシンプルになるケースは非常に多いので
その突っ込み方はおかしいと思うす
64:デフォルトの名無しさん
05/10/18 02:06:23
>>56
情報科学では、２次元の外積を定義することがありますよ
65:デフォルトの名無しさん
05/10/18 12:16:54
すみません、質問ですが、まず翻訳から。(残り時間12時間…)
a. 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
66:デフォルトの名無しさん
05/10/18 12:20:44
宿題スレ行きなよ。
67:65
05/10/18 12:23:16
質問する前に「divide and conquer "a^n"」でググって
"a^n"の部分がうまく引っ掛からずに質問したんですが
キーワードをexponentiationにしたら擬似コード見つかりました。あらら。
例えばここ:
URLﾘﾝｸ(www.math.grin.edu)
失礼しました。
でも(b)(c)で分からなかったらまたここに来ますね。
(ということで多分戻ってくることになると思います…)
68:デフォルトの名無しさん
05/10/18 14:14:12
ていうか、とりあえず代数的に解いて、
出た解を吟味するのがアルゴリズム的には簡単。
69:デフォルトの名無しさん
05/10/18 14:17:01
残り時間12時間って、提出期限は夜中？
真夜中の専門学校？？？
70:65
05/10/18 14:38:38
>>68
ありがとうございます。
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
71:65
05/10/18 14:40:59
>>69
海外なものですから。
もう図書館が閉まるので8時間後くらいにまた来ます。
それまでも自分で考えてみますが、よろしくお願いします。
72:デフォルトの名無しさん
05/10/18 15:25:55
>>70
n 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になる。
73:デフォルトの名無しさん
05/10/18 15:45:09
>>69
うちの大学は情報系の課題は"日付が変わるまで"の先生が多かったけど。
74:65
05/10/18 23:38:06
>>72
>>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)
ですね。
間に合いました。これから授業です。ありがとうございました！
75:デフォルトの名無しさん
05/10/19 10:13:17
３点を通る円すら計算できない俺は終ったな。嗚呼
76:デフォルトの名無しさん
05/10/19 11:58:19
3点を通る円なら
URLﾘﾝｸ(www.tensyo.com)
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)
にあった。 数値計算なら、３つの円周上の点から半径が最大になる点を求めれば良さそうだが・・・・
77:デフォルトの名無しさん
05/10/19 23:19:46
弦の垂直二等分線の交点だろ
78:デフォルトの名無しさん
05/10/19 23:22:46
幾何の話になるとどうしても図が欲しくなるな
79:62
05/10/20 00:34:12
一般的にはないんでしょうか？企業機密？
80:デフォルトの名無しさん
05/10/20 01:59:03
ちいとは手前で考えろよ。
81:デフォルトの名無しさん
05/10/20 17:26:42
２点定義されてる直線のある距離の点から垂線を引きたいんですが、
簡単に引く方法はありますか？
82:デフォルトの名無しさん
05/10/20 17:45:14
プログラミングの前に数学勉強しろよ
83:デフォルトの名無しさん
05/10/20 17:47:37
>>81 方向ベクトル求めれば直交する方向ベクトルが自明に定まるのでそれを使う
84:デフォルトの名無しさん
05/10/20 22:01:41
>>81
>>76のページに ２点の中点を通りそれに直行する直線 というのがある
また、
＞ 3)点(X1,Y1)に一番近い点 {c(cX1-sY1)-s*d,-s(cX1-sY1)-c*d}
を使えば、その点と結べば垂線だ
85:デフォルトの名無しさん
05/10/20 23:56:47
>>81
3角定規をあてる。
86:デフォルトの名無しさん
05/10/21 01:16:51
寧ろコンパスかと。
87:デフォルトの名無しさん
05/10/21 10:33:10
>>85
代数学では、３角定規は平行線を描く以外に使っちゃダメだろ習わなかったか？
そもそもアレは９０ﾟなのか？
88:デフォルトの名無しさん
05/10/21 10:36:15
>>87 ﾊｧ? 代数学?
89:デフォルトの名無しさん
05/10/21 11:20:04
>>62 だと、何を聞きたいのか判らん。 >>79
90:デフォルトの名無しさん
05/10/22 15:26:24
三点((x1,y1), (x2, y2), (x3,y3))を通る円の方程式が欲しい場合は、
4行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 と置けば出るよな。
91:デフォルトの名無しさん
05/10/23 10:35:15
>>90
証明のヒントを下さい。
92:90
05/10/23 13:24:43
(x0**2+y0**2,x0,y0,1) (1)
(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 が出てくるという寸法。
三点が同一直線上にないっていうことも別途確認する必要もあるね。
93:デフォルトの名無しさん
05/10/23 15:32:04
>>92
ありがとうございました。
94:デフォルトの名無しさん
05/10/23 18:48:38
ゼロと比較する時は要注意だ。
95:デフォルトの名無しさん
05/10/23 19:07:39
>>90
複素平面上だと
Im((z1-z3)/(z2-z3)*(z2-z4)/(z1-z4))=0
96:デフォルトの名無しさん
05/10/25 22:00:04
アルゴリズムC・新版―基礎・データ構造・整列・探索
R. セジウィック (著), Robert Sedgewick (原著), 野下 浩平 (翻訳), 佐藤 創 (翻訳), 星 守 (翻訳), 田口 東 (翻訳)
この本って買い？
内容とか翻訳の質とか教えてください。
97:デフォルトの名無しさん
05/10/25 23:15:47
買いです。
Cのコーディングスタイルは疑問なんで、丸写ししたい人向けじゃないです。
98:デフォルトの名無しさん
05/10/26 00:05:01
新版はコードましになってると聞いたけど不明。
99:デフォルトの名無しさん
05/10/26 16:52:05
平面座標に座標配列で定義された閉じたポリゴンがあるとして、
そこにある座標がポリゴン内か外か、どういうアルゴリズムになりますか？
100:デフォルトの名無しさん
05/10/26 17:05:56
なんで >>76 のリンク先に丁度ある話題ばかりでるのだろう？
どっかの学校があそこみて課題出してる？
101:デフォルトの名無しさん
05/10/26 22:30:36
幾何と代数は複素数によって等価であることが結びつけられた。
102:デフォルトの名無しさん
05/10/26 22:53:40
>>101
何言ってる不明
103:デフォルトの名無しさん
05/10/26 22:55:46
>>101
工エｴェｪ(´д｀)ｪェｴエ工
104:デフォルトの名無しさん
05/10/26 22:58:41
>>101
ちなみに聞くけど複素数が何か知っていってるの？
105:デフォルトの名無しさん
05/10/26 23:04:04
i = √(-1)
とか言うなよ？
言ったら笑っちゃうよ？
106:デフォルトの名無しさん
05/10/26 23:21:58
>>101
えっと、幾何と代数の意味はわかってるよね？
107:デフォルトの名無しさん
05/10/27 02:21:08
>99
点ABCから成る三角形の内側に、点Pが存在しているか？
いくつか方法あるけど、
内積から以下の角度を求めて、成立していれば内側
( ∠ABC > ∠ABP ) && ( ∠BCA > ∠BCP )
あとは外積から法線の向きで判別する方法とかもある。
108:デフォルトの名無しさん
05/10/27 06:23:44
点 q を指定し 点p配列で指定した多角形の内側かどうか？
の次は、 URLﾘﾝｸ(www.tensyo.com)
・ 線分の上にあるか？
・ 線分が交わるか？
・ 線分と点の距離
・ 円を水平線で塗り潰す
・ 最小２乗法による直線推定
・ 最小２乗法による円弧推定
・ 面積/重心
・ スプライン
109:デフォルトの名無しさん
05/10/27 09:30:20
ｦｫ, ｻﾝｸｽ >>107 >>108
結構ムズいんですね。
110:デフォルトの名無しさん
05/10/27 12:27:06
>>109
コードは20行にもならないだろう
111:ハーピィ
05/10/28 14:05:04
E・∇・ﾖﾉｼ ＜111ｹﾞｯﾄ♫
112:デフォルトの名無しさん
05/11/02 16:26:06
あるn次元ベクトルxとある対称行列A(nxn)の二次形式 x'Ax を
O(n)で計算できる夢のようなアルゴリズムはありますか？
113:デフォルトの名無しさん
05/11/02 17:17:52
ありますよ。
でもここでは余白が狭すぎて書けません。ごめんなさい。
114:デフォルトの名無しさん
05/11/02 17:33:49
>>112
存在しない．
x = (x_1, ..., x_n) としたとき，Σ_{i,j} (x_i x_j) という二次形式がありうるが，
これは項数が n^2 なので，それより小さなオーダーにはできない．
115:デフォルトの名無しさん
05/11/02 17:53:58
ご返答ありがとうございます。
では一歩譲ってn^2オーダーだとしても、その中でなんとか
効率よく計算量を減らす方法などはありますでしょうか？
Aが対称行列なので、行列の半分だけを使って2倍しながら計算、
それにxi*a_iiの二乗和を加えるという方法で、なんとか半分程度に
減らすことはできたのですが、もはや削減もここまででしょうか？
116:デフォルトの名無しさん
05/11/02 18:48:19
FFTみたいのが使えたらいいのにね・・・・って事？
117:デフォルトの名無しさん
05/11/03 00:53:28
てゆうか、最低限やらなあかん計算量ってのがある罠。
それ以下にはできんでしょ。
118:112
05/11/03 01:46:51
>>116
FFTのアルゴリズムを理解してないんでなんとも言えませんが、
nが2の累乗みたいな特定の条件下のみで最適化可能というものでも
もしあればありがたいと思いましたが。。
>>117
ごもっともです。
必要なデータを読み出さずに計算なんて神の所業ですよね。
自分の書いたＣ言語のプログラムが、二次形式を計算する箇所の
for文二重ループたったひとつのせいでむやみやたらと遅くなったもので。。
だいたいnが数百～数千くらいなんで当たり前っちゃ当たり前なんですが。
二次形式をn*100回以上繰り返し計算するわけですが、今回の場合、
Aはいつも定数で、xは要素のどれか一つだけが更新されているという
条件があって、もう少し計算が省けそうなのでがんばってみます。
119:112
05/11/03 01:51:08
間違いました。訂正です。
> xは要素のどれか一つだけが更新されているという条件
どれかひとつじゃなくてxの要素はまるごとそっくり
入れ替わっている必要がありました。失礼。
120:デフォルトの名無しさん
05/11/03 06:53:34
そもそも計算しないで済ませる
121:120
05/11/03 07:16:43
途中で書き込んじゃった．で，どんな問題解いてるの？
行列処理だったら本質的に O(N^2) は避けられないので，それが許せないなら問題に合わせた解法を用意するしかない．
例えば A が問題設定の時点でわかってるならそれを対角化するような座標を選んで O(N) の反復に落とすとか．
122:デフォルトの名無しさん
05/11/03 08:08:58
>112
１．SIMD命令で最適化する
２．ループを展開する
123:デフォルトの名無しさん
05/11/03 10:23:41
>>122 >>122 >>122 >>122 >>122 >>122 >>122 >>122
124:デフォルトの名無しさん
05/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つの交点を求めて、そのセル内での光線の通過距離を計算しようとしています。
125:デフォルトの名無しさん
05/11/03 16:26:47
数学板で聞いたとの事ですが
最終的に作りたいのはプログラムコードなわけですか？
126:デフォルトの名無しさん
05/11/03 16:42:16
そうです。今のとこ考えてるのはセルの6つの面全部で切っちゃう方法
・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点を計算、といった力技なのですが、もう少し手順を減らせそうな気がして･･･
127:デフォルトの名無しさん
05/11/03 16:53:50
俺は>>126に書いてあることが理解できていないんだが
まず隣接する直方体をまとめて大きい直方体を作ってその直方体と
光線が交わるならその直方体の中の小さい直方体を調べる、という
やりかたで計算量を減らせると思うよ（八分木、oct tree）。
128:デフォルトの名無しさん
05/11/03 17:02:22
DDAのように始点から追っていったらどう？
全体の直方体との交点のうち一方を始点に使って。
通過するセルの数は m + n + n よりも小さいし。
129:デフォルトの名無しさん
05/11/03 17:13:24
問題が分からん
1) あるセル(i, j, k)と直線が交わるか判別する
判別して通ると分かった場合に
2) その通るセルと直線との交点（２つ）を求めて、
そのセル内での光線の通過距離を計算する
ということ？
130:デフォルトの名無しさん
05/11/03 17:31:15
ええ。最終的に光線の通るセルが分かる→そのそれぞれのセル内での通過距離が分かる様な感じです。
A)全てのセル（m*n*n個)について光線と交わるか判別する→その通るそれぞれのセルについて光線との交点とセル内での光線の通過距離を計算
B）直線の式から通過するセルが分かる夢のような方法→その通るそれぞれのセルについて光線との交点とセル内での光線の通過距離を計算
のどちらかでしょうか。実はプログラミング自体限りなく初心者なので
オクトリー・DDAなどのアドバイスしていただいたアルゴリズムについて勉強してみようと思います。
131:デフォルトの名無しさん
05/11/03 17:57:31
2次元の正方格子で考えてみると、
光線を原点から方向ベクトル(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つから選ぶだけ。
132:デフォルトの名無しさん
05/11/03 18:16:16
>>131に賛成。あるセルが通るかどうかを全部のセルについてやるより
x,y,zにだらーって整数を入れてって交点を求めてから、その交点がどのセルに属すかやったほうがよさげ。
133:デフォルトの名無しさん
05/11/03 18:19:11
該当する格子の周囲(距離一)を探索すれば十分？
134:デフォルトの名無しさん
05/11/03 21:14:54
>>124
"ray march"のようなことがやりたいのかな？
135:124
05/11/03 23:48:11
沢山のアドバイス有難うございました。色々自分なりに調べてみたところ、>>128さんの仰ってくださったDDAや>>131さんの方法に似た方法で
CGの分野では直線描画の基本らしい「ブレゼンハムのアルゴリズム」というものがヒントになりそうです。
農学系の研究にCGの手法が役立つとは・・・本当に有難うございました。
136:デフォルトの名無しさん
05/11/04 13:11:07
>>135
農学って、単位空間あたりの光量の計算とかでもするのかな？
ＣＧでボクセル描画するのだとばっかりおもてたyo
137:フローチャート
05/11/08 17:16:52
自然数ｍ、ｎに対して、ｍのn乗を計算する効率のよいアルゴリズムを
フローチャートで書け。
138:デフォルトの名無しさん
05/11/08 17:22:24
>>137 フローチャートは勝手に書いてくれ
pow m n
| n == 0 = 1
| n `mod` 2 == 1 = m * pow m (n-1)
| otherwise = t * t where t = pow m (n `div` 2)
139:デフォルトの名無しさん
05/11/08 17:32:16
日本ＮＯ１プレミアムＭＭＯ
CreateGame～陸海空オンライン～
ただ今、鋭意開発中！力ある奴だけこい！
140:フローチャート
05/11/08 19:32:26
>>138
フローチャートを書け、という課題なので、フローチャートを書いてください
141:デフォルトの名無しさん
05/11/08 19:46:42
>>140
そのぐらいは自分でやりなさい。そもそも掲示板にどうやって
フローチャートを描けと。
142:デフォルトの名無しさん
05/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
143:デフォルトの名無しさん
05/11/08 20:55:31
>>142
もっと効率よくできるはずです。やり直しなさい。
144:デフォルトの名無しさん
05/11/08 20:56:13
>>142
あと、そのアルゴリズムにはバグが潜んでいます。なおしなさい。
145:デフォルトの名無しさん
05/11/11 00:09:51
晒しage
146:デフォルトの名無しさん
05/11/11 01:23:17
>>137
○pow(m, n)
│
□ ret ← 1
│
△ ループ( i=0 ; i<m ; i++)
│
□ ret ← ret*n;
│
▽
│
○ 戻り値 ← ret
147:デフォルトの名無しさん
05/11/12 04:00:38
巡回セールスマン問題をブルートフォースで解くソースコードってないですか？
擬似コードでもいいです。
148:デフォルトの名無しさん
05/11/12 07:15:53
>>147 枝刈りも何もなしでいいなら15分くらいで書けるでしょ
149:147
05/11/13 11:03:59
>>148
その枝刈りも何もなしでいい15分くらいで書ける奴をお願いします。m(__)m
150:デフォルトの名無しさん
05/11/13 11:38:37
>>149
その代わり解くのには数年間～数十年間(ry
151:147
05/11/13 12:02:13
>>150
ドサ回りする都市の数は5くらいまででいいです。
152:デフォルトの名無しさん
05/11/13 17:16:00
>>151 入力データの仕様をください
153:デフォルトの名無しさん
05/11/13 18:28:11
>>147
入力の仕様がわからなかったので，以下の仕様に従うことにした．標準入力から読み込む．
「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;
}
154:147
05/11/14 06:25:03
>>153
ありがとうございます。仕様はそのとおりでいきましょう。
走らせるために
#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
155:147
05/11/14 11:24:19
>>153
ダメダメな自分でもようやく分かりました。
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を超えない程度で)
ありがとうございました！
156:147
05/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
157:デフォルトの名無しさん
05/11/14 17:58:34
いくつか手はあるけど，手っ取り早いのは「各 visited の状態から次何を選んだか」を
グローバルの map<vector<bool>, int> にでも覚えさせておくこと．
表示するときは適当な visited からスタートして，visited = 全部 true になるまで覚えさせた map を辿っていく．
具体的には下みたいな感じにやる．
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
158:157
05/11/15 06:58:17
solve(i, start, adj, visited) を二回も呼んでるのが非効率なのでなんとかしといてください
159:147
05/11/15 15:43:57
>>157
ありがとうございます！m(__)mﾊﾊｧｰ m(__)mﾊﾊｧｰ m(__)mﾊﾊｧｰ m(__)mﾊﾊｧｰ m(__)mﾊﾊｧｰ
再帰の途中で覚えさせる方法が分からなくて困っていました。
なるほど、ああやって割り込むんですね。本当に勉強になります。
solve(i, start, adj, visited)を二回呼んでるのは後でなんとかします。
ああ、もっと賢くなりたい。←自分
160:フローチャート
05/11/23 20:25:34
価格Ａ，Ｂの商品をそれぞれＸ，Ｙ個、購入する場合の
支払い金額を計算するフローチャートを示せ。ただし、値引き率８％と
消費税５％を考慮すること
161:デフォルトの名無しさん
05/11/23 20:28:11
>>160
そりは難しい課題だねえ。
まずはフローチャートを描くルーチンを作成しないと。
環境は何？ まさか、線を引くルーチンから作らなくちゃいけない？
162:デフォルトの名無しさん
05/11/26 17:42:03
その前に有理数体での加減乗除を定義しないと。
また、有理数の円未満の端数処理をどうするか検討しないとな。
切捨て？切りage？四捨五入？設定で選択できるようにしないと
実用に耐えないかもよ。
163:デフォルトの名無しさん
05/11/26 20:15:28
意地悪なやつらめ。そんなおまえらが好きではあるけど。
164:デフォルトの名無しさん
05/11/26 21:21:57
まあ 137 あたりの経緯があるからな
165:デフォルトの名無しさん
05/11/27 18:06:06
>>162
有理数体上の加減乗除は自明じゃねーの？
166:デフォルトの名無しさん
05/11/27 21:26:38
ていうかコンピュータ上では有理数全てを表現できないし
167:デフォルトの名無しさん
05/11/27 21:35:56
ディジタルコンピュータ上ではできないね。
168:デフォルトの名無しさん
05/11/27 21:45:26
全ては表現できなくても適当な位相さえ入れば十分でしょ
169:デフォルトの名無しさん
05/12/01 12:06:34
てか、実数から見たら表現できる数値なんて穴だらけだよな。
170:デフォルトの名無しさん
05/12/01 18:13:16
つ 区間演算
171:デフォルトの名無しさん
05/12/04 01:41:03
配列nに対してn-1個の値があり、残りひとつはNULLでも0でもいいのでデータとしては何も入ってない状態。
その配列nの中のn-1個の数列を配列nの中だけでソートしたいのですが何かいいアイデアないでしょうか？
つまりデータ構造やポインタは勿論、
二分木や多分木を使ってヒープも駄目ということです。
172:デフォルトの名無しさん
05/12/04 02:00:23
バブルソートなりクイックソートなり
173:デフォルトの名無しさん
05/12/04 03:54:54
>171
状況がよくわからん。
具体的に。
174:デフォルトの名無しさん
05/12/05 16:33:28
カタカナの「ノ」の形の離散データの極率を求める数値計算法ってありますか？
書物で調べたりググったりしていますが、見つかりません。
175:174
05/12/05 16:35:59
極率 ではなく 曲率 でした。
176:デフォルトの名無しさん
05/12/05 16:40:06
二次回帰分析とかって話?
177:174
05/12/05 16:58:41
>>176
レスありがとうございます。
二次回帰分析ですと、y=a(x^2)+bx+c のa,b,cを決定するとこになると思われます。
今やりたいことは、例えば y = exp(-3*p)+q^2 に対応する離散データから
(p, q)を求めるというものです。
exp(x)は２次関数ではありませんが、例えばテイラー展開等で近似をすれば、
適応出来る物なのでしょうか？
178:デフォルトの名無しさん
05/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 を求めてやればいい．
で，それは結構難しくて，凸関数とか条件付かないと最良解が出る保証は無い．
ある程度の解でいいなら，「勾配法 + アニーリング」くらいで，それなりに求まってくれるはず．
179:デフォルトの名無しさん
05/12/05 19:50:09
画像調整のガンマをスクロールバーで実装したいのですが、
イマイチ正確な定義が分かりません。
それか、組み込めるライブラリどこかに落ちてないでしょうか？
180:174
05/12/05 20:15:07
>>178
詳しいレスありがとうございます。
今現在では、範囲と精度を与えて、全部の(p, q)について調べ、その誤差の二乗和が
最小になる(p, q)の組を解としています。
勾配法、アニーリングを調べてみて、検討してみます。
181:デフォルトの名無しさん
05/12/05 20:17:32
>>179
質問の意味がわからないけど多分スレ違い。
・言語と開発ツールは何を使ってるのか
・具体的にやりたいことは何か
・今自分は何がわからないのか
この三点をはっきりさせて、適切なスレに行って聞いてください。
182:デフォルトの名無しさん
05/12/05 21:10:48
あるデータ列に
Y = (A(X^3)+B(X^2))/(CX+D)
の最小自乗法を適応するばあい、
残差の２乗和 S に対して
A, B, C, Dそれぞれで偏微分したもの = 0
の連立方程式を解いて、
A = Σを含む式
B = ...
C = ...
D = ...
とすれば良いのでしょうか？
簡単な式の最小自乗法しか使っていなかったので、
そのまま適応して良いものかどうかが分かりません。
お願いします。
183:デフォルトの名無しさん
05/12/05 21:18:39
>>182
OK．
ただ偏微分したもの = 0 が陽に解ける保証はどこにもないし，解けたとしても解は一般に複数存在するので
出した解が本当に良いフィッティングになってるかは十分議論する必要がある．
184:182
05/12/05 21:30:11
>>183
ありがとうございます。勉強になります。
185:アルゴリズム
05/12/06 10:20:52
N人分のデータ（氏名、体重、身長、年齢）がＤＡＴＡ文で入力されているプログラムが
ある。これを用いて次のプログラムをＢＡＳＩＣで作成しなさい
年齢が３０歳以下の人の、体重と身長の平均値を計算し表示する
186:デフォルトの名無しさん
05/12/06 10:59:37
select average(weight), average(height) from DATA where (age <= 30);
187:デフォルトの名無しさん
05/12/06 12:50:40
>185
スレタイくらい嫁。
くだ質スレか宿題スレ池や。
188:デフォルトの名無しさん
05/12/06 20:36:58
>177
エクセルにデータを叩き込んでexpの形で近似曲線出すのが一番手軽な希ガス。
ところでexp（）の形になると判ってるなら、logを取ったらどうなる？
189:デフォルトの名無しさん
05/12/06 21:51:46
プチ統計学講座だなｗ
190:デフォルトの名無しさん
05/12/06 22:09:54
>>188
ヒント：Windowsとは限らない
191:デフォルトの名無しさん
05/12/06 22:28:03
ひんと：Excel以外にも統計処理できるソフトはあるし、そもそもMacでもExcelは動く。
192:デフォルトの名無しさん
05/12/06 22:34:45
>>190-191
ヒント：そもそも汎用機とも限らない 例：宇宙計算用スパコン
だからこそのアルゴリズムスレだろ？
193:デフォルトの名無しさん
05/12/06 23:14:51
だからlogとったらどうなるかと聞いてみたんだけど
194:デフォルトの名無しさん
05/12/06 23:30:44
だから前半にだけ突っこんだんだけど
195:デフォルトの名無しさん
05/12/07 19:22:24
まぁまぁ、次のネタを待ちましょう
196:デフォルトの名無しさん
05/12/07 19:55:37
上にも最小自乗法の話題が出ていますが･･･
y=(A(x^3)+B(x))/(C(x^2)+D)
の関数に最小自乗法を適応することは出来ますか？
残差の２乗和が最小になる(A,B,C,D)を見つけるわけですが、
例えばCで偏微分して=0となるCは、単なる極地のCであり、
それが極小かつ最小となるわけではありませんよね？
197:196
05/12/07 19:57:51
あれ！？
よく見たら>>182とまったく同じ式でした･･･。
当方、学生ではないので課題とかでもないのですが。
同じ書物を読んでいるのかしら。
>>183を参考にします。
無視してください。
198:デフォルトの名無しさん
05/12/07 20:29:05
フローチャートしか知らない
199:デフォルトの名無しさん
05/12/08 10:14:07
二次元配列と、
その中の３つの点で定義される三角形があって、
ある点がその中か外か判定するアルゴリズム教えて下さい。
200:デフォルトの名無しさん
05/12/08 11:58:18
>>199
(0,0), (0,2), (2,0) という要素数3個の2次元配列が与えられた場合、
(1,1) という点がその三角形の中にあるかどうかということだよな？
1)与えられた3点が三角形を構成するかどうかを吟味。
2)その3点から各々2点を取り出し(3通り)、2点を通る直線の式を求める。
3)その3本について、直線で座標平面を分割した場合、残りの頂点を含む領域を不等式(3通り)であらわす。
4)中か外かを判定したい点について、その3つの不等式を同時に満たせば中、そうでなければ外。
201:デフォルトの名無しさん
05/12/08 12:26:41
そのまんまじゃん
202:デフォルトの名無しさん
05/12/08 13:04:30
ナップザックを背負ったバックパッカー*がいるとする。ナップザックの中は、
できるだけ使い勝手の良いもので満たさなければならない。ナップザックの大きさは限られているので、
どのような荷物で満たすかが非常に大事な問題となる。ナップザック問題とは、ある目的のコストが
最大となるように限られたスペースにアイテム(item)を配置する問題のことである。次の問いに答えよ
*リュックサックに全ての荷物を入れて旅行する人のこと。
問1
0/1 ナップザック問題とは何か？
問2
全てのアイテムが(1)同じコストあるいは(2)同じサイズであればナップザック問題はどん
な問題となるのだろうか？
問3
アイテムのコストが大きさに比例する場合は、ナップザック問題はどんな問題となるの
か？
問4
ナップザックの大きさがアイテムに比べて非常に大きい場合は、一体何が起こるか？参考
書にあるプログラムを使って調べ、現象から生じた問題を指摘し、それが何故生じるのか
記述せよ．
203:デフォルトの名無しさん
05/12/08 15:35:02
>>202
ここは君が来るべきスレでは無いよ。
204:デフォルトの名無しさん
05/12/08 15:59:27
>>203
いいじゃんべつに。
お前の個人的な感情は出さなくてもいいよ。
そんなもの読んでいる人間には全く価値がないから。
文句があるならどのスレにいけ、ぐらいは言えよ。
あ、頭悪スレとかに誘導するのは全く無意味だからやめてね。
205:デフォルトの名無しさん
05/12/08 18:15:33
>>204
つまんないﾈﾀ書くのも自由だし
それを批判するのも自由。
206:デフォルトの名無しさん
05/12/08 18:37:18
座標３つ（どれがどの位置か不明）から、３角形の面積を計算する方法はありますか？
207:デフォルトの名無しさん
05/12/08 18:40:49
>>205
自重しろよ。
自由ではないんだよ？あまりひどいとアク禁だ。
208:デフォルトの名無しさん
05/12/08 19:52:21
>>206
3点から辺の長さ求めてHeronの公式、とか。
209:デフォルトの名無しさん
05/12/08 20:01:43
三点のベクトルが v1, v2, v3 のとき
[v1-v2, v3-v2]/2 の絶対値が面積になるね。
[x,y] は x と y の外積ね。
210:デフォルトの名無しさん
05/12/08 20:02:07
>>206
ある点を原点に移動させるように全体を並行移動させて、
(0,0),(a,b),(c,d)の三角形の面積が(1/2)*|a*d - b*c| であることを
使った方が簡単かも。
３点が三角形が作られない位置に無いことを確かめてからね。
211:デフォルトの名無しさん
05/12/08 20:03:50
実は
（>>182の式）≠（>>196の式）
である件について
212:デフォルトの名無しさん
05/12/08 20:55:54
>>206
URLﾘﾝｸ(www.tensyo.com)
の多角形の面積でやれば？
213:デフォルトの名無しさん
05/12/08 23:07:36
>>199
>>99,>>107-108
>>204
>>187
てか、質問する前にスレ内くらいは読もうぜ？
214:デフォルトの名無しさん
05/12/13 18:24:45
>>206
でも、3点とも座標がわかってて位置不明ってどゆこと？
215:デフォルトの名無しさん
05/12/13 19:24:25
>214
「固定座標じゃない」って意味だろ。
確かに意味は解らないが、気持ちは伝わってきた。
216:デフォルトの名無しさん
05/12/13 20:30:04
ヘロンの公式のことをたずねているの？
217:デフォルトの名無しさん
05/12/13 20:39:02
辺の長さが与えられてるわけじゃなく、頂点座標だから
ヘロンの公式をわざわざ使うより
素直に台形公式による閉曲線積分
218:デフォルトの名無しさん
05/12/13 20:56:04
>>217
頂点座標？閉曲線積分？言葉はちゃんと使おうぜ
219:デフォルトの名無しさん
05/12/14 01:18:24
>>214
任意の三点ってことだろ。
220:デフォルトの名無しさん
05/12/14 11:53:04
三角形なんだから、3点を P, Q, R として、
2つのベクトル a ＝ PQ、b ＝ PR を定義。
(1/2) |a × b|
ただし、×は3次元ベクトルの外積、|| はベクトルの絶対値。
っつーか、ぐぐれ。
URLﾘﾝｸ(homepage2.nifty.com)
221:BASIC
05/12/14 15:57:56
次のプログラムをＢＡＳＩＣで作成しなさい
データを１件ずつ、ユーザ定義関数を利用して
「公共料金」を計算させることにします
＜水道料金の計算＞
基本料金：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
222:デフォルトの名無しさん
05/12/14 15:58:42
作成しなさい、だってさ↓
223:デフォルトの名無しさん
05/12/14 16:01:00
｜ ∧＿∧
｜. (･ω･` )ｽﾙｰ
｜ｽｽ… /J J
↓ ,,, し―-J
224:デフォルトの名無しさん
05/12/14 16:51:10
アルゴリズムじゃねえな
225:デフォルトの名無しさん
05/12/14 19:15:46
アゴリズムだな
226:デフォルトの名無しさん
05/12/15 00:36:36
アルゴリズムじゃねえって！
227:デフォルトの名無しさん
05/12/15 04:40:03
アルゴリズム体操！アルゴリズム体操！
228:デフォルトの名無しさん
05/12/16 15:42:28
立方米って一般的なのか。
m^3と書かないの。
229:デフォルトの名無しさん
05/12/16 15:51:32
>>228
メートル=米、だからね。
他にも糎とか粍とか。
でも、普通は立方米と書かずに立米(りゅうべい)と書く希ガス。
#平米は割と一般的でしょ。
230:デフォルトの名無しさん
05/12/17 12:32:02
口頭ではよく「へーべー」と言うな。
俺の父親が。
231:デフォルトの名無しさん
05/12/17 12:34:10
なんでメートルが米なの？？その由来は？
232:デフォルトの名無しさん
05/12/17 12:58:32
亜米利加 と同じじゃないの？ メの元の漢字だと思ってたけど
URLﾘﾝｸ(www.fudemojiya.com)
によると 女 らしい
233:デフォルトの名無しさん
05/12/17 13:05:23
明治時代か江戸末期に「メートル(或いはメーター)」という音に似ているから当てたんじゃないの?
他にもグラムやインチなどにも当てられた漢字があることだし。
234:デフォルトの名無しさん
05/12/17 19:27:50
URLﾘﾝｸ(freett.com)
発案した人も途中からヤケクソになっていったのだと推測
235:デフォルトの名無しさん
05/12/17 22:42:29
>>234
そこまでして漢字にせんでもええやん…とおもた。
236:デフォルトの名無しさん
05/12/18 03:23:45
当時ハ送リ仮名ガ片仮名デアッタタメ
外来語ヲ片仮名ニ割リ当テルトイウ
発想ハ無カッタンダロウナ
237:デフォルトの名無しさん
05/12/18 04:08:19
質問なのですが、例えば、
1、２、３、４、５、４０、５０、６０、７０ といった代表値である数字があるとします。
で、例えばXがその代表値のどれに一番近いかを求めるとき
すべてを探索すれば答えはわかると思いますが、できるだけ高速に
求めたいと考えたとき、代表地を木にすればいいのではと私は考えました、
例えばXが6だとするとまず、5が一番近いことがわかります
これをどうやって木にしたらいいのかがわかりません。
また１，２、３・・・・といっていましたが
（X,Y,Z)と三次元に増えた場合、一番近い点を見つけるにはどうしたらいいのでしょう？
一致するのを探すのではなく一番近いものを探すので苦労しています。
近さの判定としてはユークリッド距離を用います。
どうぞよろしくお願いいたします
238:デフォルトの名無しさん
05/12/18 04:13:08
代表値の数列が整列されている前提ならバイナリサーチでいいのでは？
239:デフォルトの名無しさん
05/12/18 04:32:56
>>238
ありがとうございます。
バイナリサーチですと完全に一致する場合は問題ありませんが
完全に一致せず一番近いものを選択するときに問題がおきます
237の例で6に一番近いものをバイナリサーチで探そうとすると
40になると思われます
240:デフォルトの名無しさん
05/12/18 04:46:58
バイナリサーチで最終的に 40 がヒットするわけだけど、
この 40 と X を比較することによって 5 < X < 40 という関係はすぐにわかる。
あとはどちらに近いかを計算するだけじゃないのかな。
241:デフォルトの名無しさん
05/12/18 04:54:28
>239
最終段でヒットしなかった時、left/rightどちらの方が近いかチェックしろ。
n次の場合は、a=f(X,Y,...)で、aの値でソート。
242:デフォルトの名無しさん
05/12/18 05:01:13
>>240
>>241
ありがとうございます。
ｎ次の場合はうまくいかないように感じるのですが
できれば具体例を出していただけないでしょうか？
241さんのを自分なりに解釈すると、まずはXについてどれが一番近いか
しらべて次はY、Z・・・というふうなことだと感じているのですが
例えばXがかなり近くてもZ,Yがかなり遠いと総合的な距離は遠いわけで
Xが多少遠くてもY,Zが近ければ総合的な距離は近くなるので
あまりうまくいかなようなきがします。
間違っていたらすみません
243:241
05/12/18 05:37:33
>242
スマソ、完全に寝ぼけてた。
1次以上の距離で探したいのなら、総当りで検索するしかないんじゃね？
244:デフォルトの名無しさん
05/12/18 05:40:16
>>243
ありがとうございます。
総当りですか・・・それですと時間がかかるので
何かいい方法がないかなと思いまして
245:デフォルトの名無しさん
05/12/18 07:16:28
>>241
２次元（平面）ならボロノイ図・近傍で似たような問題がある
３次元以上だとできるかどうか知らない
総当りにしたら
246:245
05/12/18 07:17:31
>>245 の >>241 は >>237 の間違いです ｽﾏｿ
247:デフォルトの名無しさん
05/12/18 07:55:24
>>245
ありがとうございます。
ボロノイ図については知っていまして、三次元でも可能のようです。
ですが、これをどう木にすればいいのかよくわからなかったもので
何かいい方法があればと思って相談してみました、。
248:デフォルトの名無しさん
05/12/18 09:03:12
>>237
空間データベースって分野のお話だね．
望んだ形でデータを持ってていいなら，k-d tree を使うのが手軽かな．
空間に一点が追加されるたびに，その一点を通る超平面を引き，その超平面のどちら側に
点があるかで二分木を作る．探索は木を手繰りながら範囲を絞り込んで，
その中で全探索をする．最悪 O(n) だけど，適当にばらけてれば O(log n)．
ほかにも SR-tree とか SS-tree とか色々あるので，参考になりそうなのを挙げとく：
URLﾘﾝｸ(www.kecl.ntt.co.jp)
URLﾘﾝｸ(vision.unige.ch)
H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley
249:デフォルトの名無しさん
05/12/18 10:00:28
>>248
ありがとうございます
望んだ形でデータを持っていても大丈夫です。
K－ｄ tree についてなのですが、これでは一番近い代表値に近似することはできないと
考えられます。
例えば
URLﾘﾝｸ(www.kecl.ntt.co.jp)
のｋ－ｄ ｔｒｅｅ のところの図で説明しますと
代表地がＰと考えると、Ｐ４とＰ５の線の中に点があるのですがＰ９に
一番近い点（一番近い代表地に近似したい点）があったとすると
これはＰ４かＰ５に近似されることになります。
実際はＰ９に一番近いのにこれには近似されないとおいうことです
木を作る際にＰ７からでなくＰ６からはじめたとしても同様の問題はおきると考えられます
しかしＲ－ｔｒｅｅというのは使えそうな気がします
ちょっと読んでみますがいかんせん説明が少ないので理解できるかわかりませんが
なんとかがんばってみます
ありがとうございました
250:デフォルトの名無しさん
05/12/18 10:04:36
URLﾘﾝｸ(www.kecl.ntt.co.jp)
のＲ－ｔｒｅｅを読んでみましたがこれでも正確に一番近い代表地に
近似されないように感じます。
うーんどうしよう
251:デフォルトの名無しさん
05/12/18 10:05:18
一番近い点は一回では求まらないだろう。
求めた点までの距離を半径とした点で総当りをその後ですればいいだろう。
たとえば2次元なら x 座標がその範囲にある条件、次にy座標がその範囲にあるという条件で絞りこんで
矩形で絞り込めばいいでしょ
252:デフォルトの名無しさん
05/12/18 10:07:59
あと、この問題は、最悪の場合は、全数検索が必要になる。
たとえば円周上に点が並んでいて、中心に近似しようとした場合など
253:デフォルトの名無しさん
05/12/18 10:17:52
>>251
>>252
ありがとうございます。
自分の中で何か新しいアイデアが浮かんできそうな気がします
が、もう少し具体的にお願いできませんか。何かわかりそうな木がするんです
どうかおねがいします
254:デフォルトの名無しさん
05/12/18 10:25:28
データ構造として、各母点に、母点を中心に、一番遠いボロノイ点までの距離半径の円内にある
母点までのリンクを距離順に並べて持たせておいて
最初に検索した母点までの距離内にあるリンクだけ全検索する
検索する過程で、それより近い点を見つけたら、母点を移して同じ事をする
255:デフォルトの名無しさん
05/12/18 10:35:34
>>254
ありがとうございます
私の理解力不足のためわからなかったです すいませんが
もう少し簡単な説明をしていただけないでしょうか どうかお願いします
256:248
05/12/18 10:53:05
>>249
二つ目に挙げたテクニカルレポートも読んでね．ちゃんとそっちに作った木から kNN を絞り込む方法について
コメントが入ってるから．参考文献にもそれっぽいのが沢山あるので子引き，孫引きしましょう．
257:デフォルトの名無しさん
05/12/19 09:08:38
長いですが、NP完全について質問です。
アルゴリズムの本に
「図のどれが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は↓のサイトにも載っている一般的に知られているベン図ですから矛盾していません。
URLﾘﾝｸ(www.jyi.org)
で問題のcなんですが、これは↑のサイトに載っている図のPとNPCが
NPを真っ二つにして占めており、まったく隙間がありません。(想像できますか？)
これも矛盾してますよね？PでもNP完全でもないNP問題がないといけないんですから。
そうだとしたらこの本の間違いなんですが…。
ここの賢い人、どうか答えてください。せめてヒントだけでも…。
258:257
05/12/19 09:19:37
あまりの必死さに図を描いてしまいます。m(__)m
c. ＮＰ
┌───┬───┐
│ │ │
│ Ｐ │ ＮＰＣ │
│ │ │
└───┴───┘
てな感じです。
259:257
05/12/19 09:23:48
度々すみません。訳し間違えました。正しくは
「図のどれがP、NP、NP完全(NPCと呼びます)のクラスについての私たちの知識と矛盾して『いない』か？」
と
「これらのうちの二つのみが現在の私たちの知識と矛盾して『いない』」
です。もう後で逝ってくるつもりです。m(__)m
260:デフォルトの名無しさん
05/12/19 10:19:49
>>188
すみません
261:デフォルトの名無しさん
05/12/19 13:34:18
>>257
「PでもNP完全でもないNP問題がないといけない」はあくまで「P≠NPならば」
であって、「P≠NP」とは限らない。
262:257
05/12/20 12:17:51
>>261
ありがとうございます。
なるほど、「P≠NP」とは限りませんよね。
もしそうだとすれば選択肢は「P＝NP」しかない訳で
その場合は「PでもNP完全でもないNP問題があろうがなかろうが関係ない」
と解釈してよいのでしょうか？
友達の一人は「『P＝NP』は『現在の私たちの知識』に矛盾していないか？
図a, bはP=NPだから簡単に矛盾していると判断できたんじゃないか。
cがP=NPとするなら矛盾していると判断するべきだろう？」と問いかけてきました。うーむ。
すみません、自分、人より脳が少し足りないようです。
また説明お願いします。m(__)m
263:デフォルトの名無しさん
05/12/20 14:31:12
>>262
現在の多くの人たちの『考え』には矛盾しているが、それは『知識』ではない。
P=NPは、我々が馬鹿なだけですべてのNP問題は実は多項式時間で
とくことが出来ると言うこと。そんなことはないだろうと思うかもしれないが、
多項式時間で解くことの出来ない問題があることを証明できていない現在、
P=NPは矛盾しているとはいえない。
264:257
05/12/21 12:01:14
>>263
なるほど、ようやく分かりました。
すべてのNP問題が(近似解とかではなく)
多項式時間で解けるようになったら面白いでしょうね。
天寿を全うするまでに見たいものです。
ありがとうございました！
265:デフォルトの名無しさん
06/01/09 00:12:14
age
266:BASIC
06/01/09 16:12:52
N人分のデータ（氏名、体重、身長、年齢）がＤＡＴＡ文で入力されているプログラムが
ある。これを用いて次のプログラムをＢＡＳＩＣで作成しなさい
体重が６０ｋｇ以上で、身長が１５０ｃｍ未満の人の名前を表示する
267:デフォルトの名無しさん
06/01/09 17:34:00
宿題は自分でやれ
268:デフォルトの名無しさん
06/01/09 17:54:08
BASICなんて記憶の彼方だな
269:デフォルトの名無しさん
06/01/09 18:15:01
何ベーシックかは指定していないな。
VBとかでもいいとすれば随分アレだ
270:デフォルトの名無しさん
06/01/09 19:08:23
>>266
URLﾘﾝｸ(www.sagami.ne.jp)
271:デフォルトの名無しさん
06/01/11 03:29:11
ヤコビ行列の計算を効率良く行う工夫は何かあるでしょうか？
(n*m)回の微分演算という時間を喰う処理を少しでも短くしたいです
もしくは優れたJacobianMatrixクラスの例をご存じであれば是非！
272:デフォルトの名無しさん
06/01/11 06:49:10
Jacobian の成分が nm 個ある以上，本質的にそれよりオーダーが落ちることはありえない．
定数オーダーでの最適化は計算モデルに依存するので議論できん．そもそもおまいが微分をどう実装してるかもわからんし．
O(nm) すら許せないなら，問題に応じてアドホックに解決するっきゃ無いと思うがなあ．どんな問題解いてるんだ？
273:デフォルトの名無しさん
06/01/11 10:57:45
>271
LZのスライド辞書みたいに、演算した組み合わせを辞書に登録しておいて、
次回以降は演算を省くってのはどうだろう？
辞書の検索にかかる時間を何らかの方法（連想配列とか）で短縮する必要はあるだろうけど。
274:271
06/01/12 12:31:26
>>272-273
早いレスどうもです！
>>272
やはりO(nm)回は「本質的に」避けられないわけですよねー・・・
微分の差分近似をループでnm回やるつまらない実装なんで、
工夫できないかなと思った次第だったのですが。
ちなみに問題は非線形関数の最小値探査みたいな感じです
>>273
んー、いいアイディアなんですが今回は
適用できないような気がします、ゴメンナサイ
ただ、そのうち他の問題で使えそうな気がするんで、
そのネタはもらって覚えておきます！ ありがとう！
275:デフォルトの名無しさん
06/01/14 00:48:34
>>274
最小化したい非線型関数になんか条件付けないと定数レベルの最適化もつらいような
276:デフォルトの名無しさん
06/01/31 17:55:55
最小二乗法のライブラリきぼんゅ。
277:デフォルトの名無しさん
06/02/01 03:14:47
>>276
ライブラリも何も、大した計算じゃないじゃん。
278:デフォルトの名無しさん
06/02/01 12:32:21
>>277
世の中に存在するアルゴリズムの中で複雑と言えるものがどれだけある？
279:276
06/02/01 12:44:24
最小二乗法おしえて欲しいぉ。
280:デフォルトの名無しさん
06/02/01 13:38:16
残差平方和が最小になるようにパラメータを決定するのです
このスレでも簡単な例がいくつか
>>178
>>182
>>196
非線形になってくるとちょっとめんどい
URLﾘﾝｸ(en.wikipedia.org)
URLﾘﾝｸ(en.wikipedia.org)
ここら辺を参考に
281:デフォルトの名無しさん
06/02/02 02:20:31
>>278
FFTになると、ライブラリが欲しい程度には複雑だと思う。
282:デフォルトの名無しさん
06/02/02 08:51:05
>>281
どれだけある？という問いにＦＦＴ１個かよ。
283:デフォルトの名無しさん
06/02/02 09:25:21
>>282
世の中に存在するアルゴリズムがどれくらいあるのか教えてくれたら答えてあげるよ。
284:デフォルトの名無しさん
06/02/02 13:43:21
行列計算もだいたい書く気がしないな．条件数が悪い場合とか考え出すと相当面倒くさい．
285:デフォルトの名無しさん
06/02/02 14:58:57
あとは圧縮＆展開と多倍長演算あたりかね？ 汎用的なのは。
各分野毎にはいろいろとあるだろうけど。
画像エフェクト、サウンドエフェクト、3D系演算とか。
286:デフォルトの名無しさん
06/02/02 15:52:22
>>281
難しくはないが複雑ではあるよな。
287:デフォルトの名無しさん
06/02/02 22:26:58
各種関数なんかは、大概簡単なことをやっていても、実装は面倒だなぁ。
288:デフォルトの名無しさん
06/02/05 09:27:32
最小二乗法は
円に適用するだけでも、厄介だし、
直線に適用しようとしたって、実はけっこう難しいよ。
たとえば、2次元画像から直線部を取りたいとしたら、学校でやるようなXとかYでの偏微分じゃ、それこそ偏る。
残差って何って所から取り掛からないとね。
そして、余程単純じゃないと、たいていは方程式1発で解けるという事にはならない。
数値解で求める事になるだろうな
289:デフォルトの名無しさん
06/02/06 07:09:38
>>288
ただの偏微分でしか説明しないのって，相当ひどい学校だと思う
290:276
06/02/06 10:04:37
>>288
じゃ、何を使うのさ？？？？？
>>289
詳しく！！！！！
291:デフォルトの名無しさん
06/02/06 14:14:46
>>288
最小二乗法はロバストでないのでそのあたりは考慮しないと。
例えば、y=x上に完全に点が並んでいる状態で、
たった一点(1,10000)が入ってきただけでy=2xとかになると困るわけだ。
292:276
06/02/06 14:22:51
今回の開発では点の数に関しては、決めウチできます。
293:288
06/02/07 06:30:36
>>290
だから、最小2乗法を使うなら、何を最小にするのかって所が肝心って事さ
直線を求めるのにしたって、数表上と2次元データとは誤差の意味が違う
数表上なら結果の誤差を最小にしたいし
2次元なら直線からの誤差を最小にすると同時に回転変換で結果が変わらない必要がある
294:デフォルトの名無しさん
06/02/09 11:57:07
最小2乗法ｱｹﾞ
295:sage
06/02/09 21:45:42
sage
296:デフォルトの名無しさん
06/02/11 17:31:27
n個の要素の2番目に小さい要素は最悪n+logn－2回の比較で求められることを証明しなさい。
順序統計量を使うのだと思うのですが、帰納法を使って証明するのかどうか分かりません。
どなかか説明してもらえないでしょうか？よろしくお願いします。
高校の時に教師が言っていたんだけど急に思い出して・・・・おねがいします。
297:デフォルトの名無しさん
06/02/11 18:07:41
／￣￣￣￣＼
／ ● ●
|Y Y ＼
| | | ▼ | ﾊﾟｸｯ
| ＼／ ＿＿＿＿人__|
| |∨∨∨∨∨ ←296
＼ ＼∧∧ ）
｜ ｜ |＼ ￣￣＼＼＼
｜ ｜ | ￣￣￣ し し/
（_＿）＿）
298:デフォルトの名無しさん
06/02/11 18:33:39
最悪 n - 1じゃないか? 何番目でも最悪 n - 1回でいけそうだ。
今適当に考えただけだから間違ってるかもしれないけど。
299:デフォルトの名無しさん
06/02/11 18:40:59
違った、最悪 n回か。
300:デフォルトの名無しさん
06/02/11 18:45:05
>>298
いや、漏れが覚えている限りでは違うと思われ。
MITだかどっかの教科書の奴に載ってた。二番目を求めるけども一番最小を求めてからだったはず
院試にでてたかも。
301:デフォルトの名無しさん
06/02/11 18:57:23
>>300
やっぱり違ってた。考え直したら、
nが偶数なら (3/2)*n - 2,
奇数なら (3/2)*n - 3/2 回だった。
302:デフォルトの名無しさん
06/02/11 20:58:20
>>296
ソートアルゴリズムのところとかかな？学部生の時に必死こいてやったけどもう忘れた・・・。
あの教科書は原書で読んだ方がいいかもしれんな。英語だからかなりめんどくさいが。半期でやるのを英語でやったら一年半かかったよ。
303:デフォルトの名無しさん
06/02/12 00:24:16
証明になってないｗ
304:デフォルトの名無しさん
06/02/12 03:01:20
>>296
完全二分木でトーナメントを考えよう。
一番小さい要素を見つけるのに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の小数点以下切り上げの関数
305:デフォルトの名無しさん
06/02/13 00:39:26
>>304
なるほど。
それは比較は少ないけどコピーがメモリが多く必要になりそうなんだけど
どうなんだろう。
306:デフォルトの名無しさん
06/02/13 06:11:40
２分木にする必要性が感じられないってかなってないｗ
307:デフォルトの名無しさん
06/02/14 10:30:15
>>305
実装の話はしてないんだよね。実際にこの比較回数で動くプログラムを作るのは
結構困難な気がするし、普通の 2n 回比較に定数倍で負けそう。
308:デフォルトの名無しさん
06/02/27 09:33:06
３２ビットの符号無整数型で３２個のビットのうち
N個をランダムに選んで１にするアルゴリズム。
（残りの３２－N個は０）
賢い人教えて。
309:デフォルトの名無しさん
06/02/27 11:33:45
>>308
そのサイズの乱数を一個生成するだけじゃいかんの？ C なら rand() とかで。
それとも乱数生成のアルゴリズム自体を聞いてるの？
310:デフォルトの名無しさん
06/02/27 12:12:40
たぶん
１）組み合わせの数の計算方法が判らない
２）乱数と、その全部の組み合わせを対応させる方法が判らない
のだろうと思うんだけどね
311:デフォルトの名無しさん
06/02/27 12:28:33
1U << (rand() & 31)
とか、そういうことではないの？
312:デフォルトの名無しさん
06/02/27 12:35:07
>>311
rand って完全にランダムじゃなくて、
下位ビットほど短い周期性持ってるから、
rand() & 31 はあんまりよくない。
(rand() >> 16) & 31 とか、何ビットかシフトするの推奨。
313:デフォルトの名無しさん
06/02/27 12:38:20
分かってて書いてたつもりだけど…アルゴリズムの質問だし。
random()でもMTでも好きなの使えばいいんじゃない？
314:デフォルトの名無しさん
06/02/27 12:41:56
>>313
まあそうだけどね。
>>308 がそんな判断できると思えなかったんで、一応補足のつもり。
315:308
06/02/27 13:09:41
MTとかで生成された乱数の立っているビットの数は
１６本を中心にした正規分布になってると思うんだけど、
必ずN本になるようにしたい。
３本とか３０本とかってのはたまにしか発生しないし。
N回ループで一度使った数は記憶させとくとかっていう
愚直なのは思いついたんだけど遅そうなので聞いてみた。
316:デフォルトの名無しさん
06/02/27 15:31:21
32個の数字から N個取り出して順不同というのと 問題は同じでしょ
317:デフォルトの名無しさん
06/02/27 20:50:08
>>316
ですね。
1～32の間で離散一様乱数発生させたものをa_0、
1～31の間の乱数をa_1、1～30の間をa_2として、
初期値は0で左からa_0番目のビットを1にする。
以降左からa_k番目の0のビットを1にする。
~~
318:308
06/02/28 09:54:13
>>317
今はそれでやってます。
みなさん聞いてくれてありがとう。
319:308
06/02/28 09:58:33
あ、ついでに言っとくとNが17以上の場合は32-N個のビットを立てて反転してる。
連投ごめん。
320:308
06/03/01 16:40:57
やっぱりもっと速いのないかな。
321:デフォルトの名無しさん
06/03/01 17:19:36
>>320
これ以上議論するなら，「速い」をきっちり定義してもらわないと．
特に乱数生成のコスト，各ビットを参照するコストなどが無いと，
どっちが速いかなんて比較できんよ．
322:デフォルトの名無しさん
06/03/02 11:59:32
もっと早い方法は、全部の組み合わせのテーブルを作っておいて
それの配列番号を乱数で選ぶ事だね
323:デフォルトの名無しさん
06/03/02 12:53:16
>>322
2^32 / 2 (0≤N≤16 だから半分) = 2G×4Byte = 8GB
何を使って動かすつもり？
324:デフォルトの名無しさん
06/03/02 16:39:38
>>317
それは、順番を考慮した場合のアルゴリズムだから違うようだけど
結果はN個のビットだから、どの組み合わせも等確率で発生するから問題ないのか
>>323
Nを固定すれば 最大の組合せ数は N=16の時で その1/4程度の容量だから最近のPCなら入るんじゃないの？
組み合わせの数ってどの程度だろ？
32!/N!/2^N では大きすぎるな
325:デフォルトの名無しさん
06/03/02 16:43:14
たとえば32個中3個が１の組み合わせを F(32,3) のように書くと
先頭ビットが0 なら 残りは F(31,3)
先頭ビットが1 なら 残りは F(31,2)
という事で
F(N,M)=F(N-1,M)+F(N-1,M-1)
326:デフォルトの名無しさん
06/03/02 17:23:15
>>324,325 高校数学の教科書読み直したら？
URLﾘﾝｸ(ja.wikibooks.org)
327:デフォルトの名無しさん
06/03/02 18:34:31
という事は 32 C 16
URLﾘﾝｸ(www.google.co.jp)(16!*16!)
601 080 390
って事か
Σ M C n =2^M って事になるんだな
328:デフォルトの名無しさん
06/03/02 18:39:51
で 32個中16個の組み合わせ は 32!/(16!*16!)
なのに >>317の方法は 順列 で 32!/16! という事で、16! の重複があるから、なんか重そうに見えるという事？
329:デフォルトの名無しさん
06/03/03 07:29:43
配列のソートではなく、上位2者と下位2者を高速にシークするアルゴリズムを教えて＞＜
330:デフォルトの名無しさん
06/03/03 07:50:10
var max1,max2 min1,min2;
max1:=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;
こんな感じでは？
331:デフォルトの名無しさん
06/04/18 07:42:35
いわゆる○×。ただし、ちょっと特殊。
ban(0) ban(1) ban(2)
ban(3) ban(4) ban(5)
ban(6) ban(7) ban(8) //盤面 位置関係はこんな感じ
turn //ターン数 最初は1
プレイヤーＡのターン開始
↓
Ａが指定しかつその場所に当たる変数（真ん中ならban(4)）が0であるならばそれに（turn×１０）＋プレイヤーの番号
（Ａは１、Ｂは２とする。）を代入。
↓
turn>6ならば、次のことを行う。
banの中で下１桁がプレイヤーの番号と等しいもののなかで、一番小さいものに0を代入
↓
banに縦横斜めに自分の番号が並んでいるならば勝利
↓
turnに１を足し、Ａのターンを終了、Ｂのターンになる。
で、できるだけ強いCOMのアルゴリズムを考えてほしいのです。
お願いします。
332:デフォルトの名無しさん
06/04/18 13:54:18
あぶらあげ
333:デフォルトの名無しさん
06/04/22 16:23:12
>>331
ゲーム木使って実際に解いてみたら。
EXPTIME完全か知らんが、3×3ぐらいなら解けるだろ。
終盤6個そろってからの場合の数は
9*8*7*6*5*4 = 60480
回転と対称で重なるものを除くと
60480/8 = 7560
リーチがかかってかつ自分の手番のような自明な場面を除けばもっと少なくなる。
自分の手番でダブルリーチをかけられる状態であれば勝ち。
双方最善を尽くしたとき、ループに陥れば引き分け。
334:デフォルトの名無しさん
06/04/22 17:08:22
消してから勝利判定だとダブルリーチにならないんじゃない？
335:デフォルトの名無しさん
06/05/22 17:26:54
楕円近似ライブラリなんてありまつか？
336:デフォルトの名無しさん
06/05/22 17:37:12
楕円近似というのは
１、点列を楕円の一部として近似する事
２、楕円の周長を近似計算する事
どっち？１はとても難しい 円ならまだ方法があるが
337:デフォルトの名無しさん
06/05/22 17:56:27
＞１、点列を楕円の一部として近似する事
これをやりたいです。
338:デフォルトの名無しさん
06/05/22 18:20:03
円なら
URLﾘﾝｸ(www.tensyo.com)
ここの円弧推定が良い方法だと思える。
普通は、円との誤差を ｓ＝√｛（ｘ－ｘ0）^2 ＋（ｙ－ｙ0）^2｝－ｒ と置くが
これだと非線形で解かなければならない。
（ｘ－ｘ0）^2 ＋（ｙ－ｙ0）^2－r^2 とすれば数値解が簡単に求まるというものだ。
楕円の場合は、検索すれば出ると思うが、円よりさらに厄介だ
339:AVL木
06/05/22 20:52:10
18,7,35,13,16,10,40,21,22,50,46,3,5 を
からっぽのAVL木に入れていくとどうなりますか？誰か教えてください。
340:デフォルトの名無しさん
06/05/22 21:41:44
教科書読め
341:デフォルトの名無しさん
06/05/25 18:54:44
繰り返し二乗法のプログラムをご教授お願い出来ますでしょうか？
342:デフォルトの名無しさん
06/05/25 20:20:09
デジタル回路の閾値関数を考えたのですが、既知ですか？
f:=x->cos(PI/2*x)^2
f(f(f(x))), x=-0.5..1.5
343:デフォルトの名無しさん
06/05/31 01:36:13
>>335
Direct least-squares fitting of ellipses
Andrew W. Fitzgibbon, Maurizio Pilu, and Robert B. Fisher
IEEE Transactions on Pattern Analysis and Machine Intelligence,
21(5), 476--480, May 1999
URLﾘﾝｸ(research.microsoft.com)
URLﾘﾝｸ(research.microsoft.com)
一応 Java 実装もあるけどコードがちょっと汚いかも。
344:デフォルトの名無しさん
06/07/28 23:01:36
fla板から来ました以下の解答お願いします。
プレーヤの歩いた軌跡が、あらかじめ引いてある直線にどれくらい近いかを数値化するにはどうしたらいいでしょうか？
(x,y)座標を取って計算をすればよいらしいっていうのはなんとなくわかるんですが
具体的にどういった計算をすればいいかご教授願います
ちなみに最小二乗法だと、
＼
／
＼
／
このように蛇行した場合も直線に近似されてしまうのでダメですよね・・・
345:デフォルトの名無しさん
06/07/28 23:26:48
>>344
軌跡が直線に近いってのは、どういうこと?
346:デフォルトの名無しさん
06/07/28 23:37:46
>>344
最小二乗法で相関係数みりゃいいだろ。
347:デフォルトの名無しさん
06/07/29 00:13:17
>344
数値を求めたいんだろう？
最後の行が意味不明だぞ
348:344
06/07/29 00:16:20
>>345
URLﾘﾝｸ(www.uploda.org)
この画像のように、どれだけ直線に近い動きをしたか、ということを
直線との接触時間などからではなく、座標から軌跡と直線との近さを計算したいのです。
>>346
相関係数ですか、調べてみます
ありがとうございます
349:デフォルトの名無しさん
06/07/29 15:15:39
もしかして、344は「軌跡から最小自乗法で直線を求めて、与えられている直線と比較する」とか考えているのだろうか。
「軌跡と与えられた直線の距離の自乗を最小にする」でいいんじゃないの？
350:デフォルトの名無しさん
06/08/10 08:08:24
あらかじめ引いてある直線が X 軸に合うように回転させて
Σ(Yi^2)/N とか
軌跡の2次モーメントとか
351:デフォルトの名無しさん
06/09/15 13:37:19
軌跡に沿って所与の直線との距離を積分すればいいじゃないの。
352:デフォルトの名無しさん
06/09/16 00:36:41
随分とまた遅い進行だな
353:デフォルトの名無しさん
06/10/18 22:34:05
ベクトルを正規化する式は
float x, y, z;//元のベクトル
float vx, vy, vz;//正規化したベクトル
float s;
s=sqrt(x*x+y*y+z*z);
vx=x/s;
vy=y/s;
vz=z/s;
で求まると思いますが、sqrtを使わずに正規化するにはどうすればいいのでしょうか？
どうしても速度が気になります。
自分でも考えてみましたが分かりませんでした。よろしく御願いします。
354:age
06/10/18 22:38:49
age
355:デフォルトの名無しさん
06/10/18 23:04:16
f(u0,v0)=
ΣΣf(uk,vl)C(uk-u0)C(vl-v0)
k l
ここで
C(x)= 1-2|x|^2+|x|^3 (0<|x|<1)
4-8|x|+5|x|^2-|x|^3 (1<|x|<2)
0 (2<|x|)
3次補間法の計算式なのですが，どのようにプログラムで書いたら良いのでしょうか?
356:デフォルトの名無しさん
06/10/19 00:02:01
>>353
>どうしても速度が気になります。
本当に気になる速度なのかどうか、まず実測してみたらどうでしょう。
sqrtを使わなければできないと思いますけど。
本当にsqrtが速度的にネックであれば、高速のsqrtを自前で作るとか。
ただし、精度を犠牲にしてのことですけど。
Newton法でのsqrtの近似の場合、ループは高々20回くらいです。（誤差1.0e-15で）
まずは実測です。
357:デフォルトの名無しさん
06/10/19 00:08:31
脳味噌ぶら～んにでも行って速そうなの探してこいよ。
358:デフォルトの名無しさん
06/10/19 01:37:21
>353
まず環境晒そうや。
CPU、使用言語、必要精度、それらの情報も無しでアドバイスなんて出来ん。
359:デフォルトの名無しさん
06/10/19 10:20:45
>>356
精度にもよるけどせいぜい３－５回ぐらいじゃなかったか？
20回もまわすか。
360:デフォルトの名無しさん
06/10/19 10:52:10
double sqrt(double x) {
double a = 1.0;
double eps = 1.0E-10; /* 精度 */
while (abs(a * a - x) > 1.0E-10) {
a = 0.5 * (a + x / a);
}
return a;
}
361:デフォルトの名無しさん
06/10/19 10:56:57
>>353
URLﾘﾝｸ(www.google.co.jp)
362:デフォルトの名無しさん
06/10/19 12:32:48
>>360
そのコードで３－５回
1.0E-15で9回ってところ
確かに20回もありえるけど、極端な言いぐさは信用されないな。
363:デフォルトの名無しさん
06/10/19 13:16:19
>>360
Intel系ならニュートン法使うより、素直に浮動小数点命令を使った方が速いだろ。
SSE乗ってるならaddss/mulss/rsqrtps辺りでまとめて計算できるし。
364:デフォルトの名無しさん
06/10/19 13:44:45
>>355
その計算式のままだと思うけど…
アルゴリズムの入力と出力は理解できてる?
(入力は格子状の標本点における f の値 (二次元の double 配列) と補間すべき点の座標 (u0, v0) で、出力は (u0, v0) における補間値)
365:デフォルトの名無しさん
06/10/19 16:36:19
式は分かってるんですがプログラムにできないんです・・・
366:デフォルトの名無しさん
06/10/19 17:01:18
>>365
具体的なコードが欲しいなら
具体的な入力形式を指定した方がいいと思うよ。
(これは大学の宿題か何かですか?)
367:デフォルトの名無しさん
06/10/19 17:19:03
初心者なもですいません．大学のC言語の画像処理の宿題です．
#include <stdio.h>
#include <rasterfile.h>
#include <math.h>
#include "bitshift.h"
void Disp_Ras(struct rasterfile ras);
void cercle(struct rasterfile ras, unsigned char **r, unsigned char **g, unsigned char **b, int point[2]);
void tri(struct rasterfile ras, unsigned char **r, unsigned char **g, unsigned char **b, int point[2]);
void sq(struct rasterfile ras, unsigned char **r, unsigned char **g, unsigned char **b, int point[2]);
void satr(struct rasterfile ras, unsigned char **r, unsigned char **g, unsigned char **b, int point[2]);
int height;
int width;
int main(int argc,char *argv[]){
/*変数宣言*/
int i=0;
int j=0;
int point[2];
struct rasterfile ras;
unsigned char **R,**G,**B;
unsigned char **r,**g,**b;
FILE *fp1,*fp2;
int nt,nn;
double p,q;
double bai;
int tmp_nt,tump_nn;
368:デフォルトの名無しさん
06/10/19 17:22:41
続き
printf("倍率を入力");
scanf("%lf",&bai);
/* 入力画像 */
if((fp1 = fopen("hane256.ras","rb")) == NULL){
fprintf(stderr,"can't open file!!\none more check it!!\n");
exit(1);}
/* ヘッダ読み込み */
ras.ras_magic = readtoInt(fp1);
ras.ras_width = readtoInt(fp1);
ras.ras_height = readtoInt(fp1);
ras.ras_depth = readtoInt(fp1);
ras.ras_length = readtoInt(fp1);
ras.ras_type = readtoInt(fp1);
ras.ras_maptype = readtoInt(fp1);
ras.ras_maplength = readtoInt(fp1);
369:デフォルトの名無しさん
06/10/19 17:23:35
続き
height =bai*ras.ras_height;
width = bai*ras.ras_width;
height = height - height%4;
width = width - width%4;
/* 出力画像 */
fp2 = fopen("out.ras","wb");
/* ヘッダ書き込み */
writetoInt(fp2,ras.ras_magic);
writetoInt(fp2,width);
writetoInt(fp2,height);
writetoInt(fp2,ras.ras_depth);
writetoInt(fp2,ras.ras_length);
writetoInt(fp2,ras.ras_type);
writetoInt(fp2,ras.ras_maptype);
writetoInt(fp2,ras.ras_maplength);
370:デフォルトの名無しさん
06/10/19 17:24:06
続き
/* メモリ確保 */
R = (unsigned char**)calloc(ras.ras_height,sizeof(unsigned char *));
G = (unsigned char**)calloc(ras.ras_height,sizeof(unsigned char *));
B = (unsigned char**)calloc(ras.ras_height,sizeof(unsigned char *));
r = (unsigned char**)calloc(height,sizeof(unsigned char *));
g = (unsigned char**)calloc(height,sizeof(unsigned char *));
b = (unsigned char**)calloc(height,sizeof(unsigned char *));
for(i=0;i<ras.ras_height;i++){
R[i]=(unsigned char*)calloc(ras.ras_width,sizeof(unsigned char));
G[i]=(unsigned char*)calloc(ras.ras_width,sizeof(unsigned char));
B[i]=(unsigned char*)calloc(ras.ras_width,sizeof(unsigned char));
}
for(i=0;i<height;i++){
r[i]=(unsigned char*)calloc(width,sizeof(unsigned char));
g[i]=(unsigned char*)calloc(width,sizeof(unsigned char));
b[i]=(unsigned char*)calloc(width,sizeof(unsigned char));
}