計算アルゴリズム【Ⅱ】

計算アルゴリズム【Ⅱ】 at TECH

1:デフォルトの名無しさん
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);

次ページ