計算アルゴリズム【�U】

1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ] 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉 >プログラム板の皆さん、こんにちは。 >無謀にもこんなスレを立ててみました。 >四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。 >人間にとって計算しやすい方法についても別途語ることにしましょう。 前スレ↓ pc8.2ch.net/test/read.cgi/tech/1090227743/ 2 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:52:57 ] 2 get 3 名前：デフォルトの名無しさん [2005/10/15(土) 21:10:02 ] やれやれ、 プログラミングの為の数学と算数 vol.2 pc8.2ch.net/test/read.cgi/tech/1094368921/ を使ってクレって言ったのに、たてちゃったか。 ようし、前スレで我慢してたけど、　精度ネタいっちゃうぞ。 まずは、「2直線の角度を求める」ネタだ。 前スレでは、ベクトルの内積A・B　 A・B　＝　cos(φ) *|A|*|B| 　から、角度を求める。 こいつは2つのベクトルの角度の定義でもあるから王道のように見えるだろう。 しかし、問題はcos(φ)が１に近い時、つまり２直線が平行に近くなると精度が悪いという事だ。 解決は簡単で、Aに垂直な線で同じことをやれば　sin(φ）が求まるという事を利用して cos と sin から atan2 で求ればいい。 さあ、↓　まずは2次元で公式を作ってみよう 4 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 21:15:50 ] キモイ↑ 5 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 21:28:05 ] ながい　　　↑ 6 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 21:41:28 ] まとめサイトまだー 7 名前：デフォルトの名無しさん [2005/10/15(土) 21:57:53 ] おまえらノリ悪いぞ。 方向ベクトル　[dx,dy] を90度回転させれば [dy, -dx] になる つまりx,yを入れ替えて片方負数にすればいい　 内積 (dx1*dx2+dy1*dy2) 　90度回転させた相手との内積　 (dy1*dx2-dx1*dy2) で　この比の　ArcTanを取ればいいことになる。　実際にはatan2を使えば良い。 8 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 22:55:06 ] 4つの1から9までの数字と、+、-、*、/とカッコを組み合わせて、 ある自然数が作れるかどうかを判定するプログラムを書いてみたい（出来ればCで)と思います。 数字の方はfor文使って順に変えていけばいいんですが、演算やカッコは 数値じゃないから、色々と変えていく作業をループで回せませんよね? だから組み合わせの場合わけが膨大になってしまいます。 いい案があれば教えてください。 9 名前：デフォルトの名無しさん [2005/10/15(土) 23:02:18 ] 別に、ループで回せばいいじゃない 四則演算は優先順位を付けるの？　だったら計算は再起下降で処理させればいい 10 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 23:10:59 ] >9 「カッコの組み合わせ」とあるから、頭っからの総当りで十分だろ。 [0-9][+-*/][0-9][+-*/][0-9][+-*/][0-9] 10*4*10*4*10*4*10=640000通り 実際は被るパターンがあるけど、まぁいいか。 11 名前：デフォルトの名無しさん [2005/10/15(土) 23:37:36 ] たぶん 1+2*3+4 というような計算式をランダムに作った時に、どう計算させればいいかって部分で悩んでると見た 12 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 23:54:11 ] 12+34は除外？ 13 名前：デフォルトの名無しさん [2005/10/15(土) 23:59:40 ] 左の数を10倍にして右に足すという演算子を入れたら？ >>12 14 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 00:04:21 ] 同じ数は二回以上使えないよね？ 使えるなら1+1+1+...+1で終了だし。 15 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 00:05:07 ] すまん「４つ使う」というのを見てなかった 16 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 00:08:27 ] >>10 a/(b+c/d)みたいなのは括弧無しだと無理じゃない？ 17 名前：デフォルトの名無しさん mailto:sage [2005/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 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 01:09:22 ] まず2つの数でできる数をすべて列挙して表にする。もちろん分数も考慮。 3つの数の表は2つの数の表から1個と数1数を演算子でつなぐだけ。 4つの数の表は2つの数の表から2個とってくるか、3つの数の表から1個と数1個でつくることができる。 指数オーダーだけど、4つぐらいならなんとかならないか。 19 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 01:15:18 ] >18 同じ数字を複数回使えないという制限がある場合にはその方法は難しいな。 >8の文面だけではその制限があるのかどうかわからないが。 20 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 02:15:28 ] 切符の４桁シリアル番号で10を作る遊びだろ？ (9*9+9)/9 (1/9+1)*9 この２つだけ解れば十分な希ガス。 21 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 02:16:35 ] 一般的な切符のあれでいいんじゃないの？ 22 名前：デフォルトの名無しさん [2005/10/16(日) 02:49:12 ] 後置記法 23 名前：デフォルトの名無しさん mailto:sage [2005/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 名前：デフォルトの名無しさん [2005/10/16(日) 06:39:30 ] >>23 それじゃ、優先順位を表現出来ないから悩んでるんだろ？ 　文字配列にして再帰下降で処理すればいいよ 25 名前：デフォルトの名無しさん [2005/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 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 08:12:07 ] そんなめんどいことしないでも後置記法で表現しとけば式の全生成を含めても瞬殺 27 名前：デフォルトの名無しさん [2005/10/16(日) 08:13:31 ] >>26 1234+++ てな感じで書いてから処理させるわけね。 じゃ、コード書いてみて。　　>>25と比べてみたい 28 名前：デフォルトの名無しさん mailto:sage [2005/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 名前：デフォルトの名無しさん [2005/10/16(日) 08:39:31 ] スタックが簡単に書ける C++ でないと1レスに入るくらいに簡単にはイカンだろう それでも、結構めんどくさい。　瞬殺ってわけにはいかんと思うよ。 30 名前：29 [2005/10/16(日) 08:40:44 ] と思ったら、>>28　がんばってくれた。 31 名前：29 [2005/10/16(日) 08:46:35 ] 後置記法なら、 9999XXX という文字列を作って .... X は + - * / 全スキャンをすれば 括弧つき四則演算は全て網羅出来るというわけで 後は、後置記法から逆変換するコードさえ書けば完成って所だね 32 名前：28 mailto:sage [2005/10/16(日) 08:57:37 ] >>31 それで表せる式は (a ? (b ? (c ? d))) だけだから駄目． (1 + 2) * (3 + 4) が表せない． 33 名前：29 [2005/10/16(日) 09:05:05 ] >>32 なるほどね。99X99XX も必要なのか 34 名前：29 [2005/10/16(日) 09:19:38 ] もしかして 9999XXX 999X9XX 99X9X9X 99X99XX 全部必要か？　なら　逆変換しなくていい　再起下降もそう悪くないな 35 名前：28 mailto:sage [2005/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 mailto:sage [2005/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 [2005/10/16(日) 10:53:47 ] >>35 確かに括弧の対応考えるとめんどくさいけど、 　括弧の対応は再起下降処理中にチェック出来るから全部の組み合わせをやる方針なら 　ややこしさは同じ程度だろう ただ計算量は、後置だと組み合わせが少ないから探索目的ならそれで探すべきだな 38 名前：28 mailto:sage [2005/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 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 13:35:14 ] 「計算アルゴリズム」ってどういう意味? 40 名前：検索したら見つけた mailto:sage [2005/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 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 14:46:55 ] >>39 前スレの>>1に聞いてください。 42 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 16:24:41 ] >>39 理系・数学板の任意のスレでKingと呼べばいつでも出てきてくれます。 43 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 17:34:59 ] 3つの円(半径・中心座標はわかっている)に接する円の半径・中心座標を求めるには どうすればいいんでしょうか？計算方法を教えてください。 44 名前：デフォルトの名無しさん mailto:sage [2005/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 名前：デフォルトの名無しさん [2005/10/16(日) 18:04:18 ] 接するというのは、組み合わせが多数あると思う。 外包円＝ぴったり３つの円が収まる状態なら 外包円との接点と、中心を結ぶ線上に、接する円の中心もあるというのが拘束条件に出来ると思う 俺なら、厳密解を出すのはメンドクサイから、 一つの円にまず接しておいて、のこり１つの円に接するとした時の求まる　外包円の中心で 外包円を描いて、　最後の一つの円との距離で2分法かニュートン法的に解くかな 46 名前：デフォルトの名無しさん [2005/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 [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 48 名前：46 [2005/10/16(日) 18:54:02 ] ダメ。解けそうなのに解けんな。　数値解法に一票いれるよ。 49 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 18:57:01 ] >>47 あってると思う。 (上)-(中) と (中)-(下) と (下)-(上) で連立させれば 3元1次方程式が出てきてめでたしめでたしじゃないの？ 50 名前：46 [2005/10/16(日) 19:05:40 ] >>49 うーん途中までやってみたけど、自分の仕事じゃないしな。 51 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 20:15:50 ] 3つの方程式に4つのパラメタだから解は全然一意じゃないよね． 外接円の中で半径最小のもの，とかしないと求まんないと思う． 52 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 20:20:12 ] 円だから未知数は３つだろう　中心と半径 53 名前：デフォルトの名無しさん [2005/10/16(日) 20:33:32 ] >>7 外積のほうが説明楽だろ、θ=tan＾-1(|a x b|/|a ・ b|) 54 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 20:34:10 ] ごめんなさい r, x, y, z とか数えてました……． 55 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 20:34:50 ] 数値解も案外厄介だな　 56 名前：デフォルトの名無しさん mailto:sage [2005/10/16(日) 20:35:51 ] >>53 元ネタは2次元だから外積持ち出すのは・・・・ 57 名前：デフォルトの名無しさん mailto:sage [2005/10/17(月) 16:22:40 ] ていうか、3つの円の大きさとか位置関係とかどうなっているの？ 58 名前：デフォルトの名無しさん mailto:sage [2005/10/17(月) 18:14:48 ] そりゃ色々あるんだろう。　だから厄介みたいだね。 59 名前：デフォルトの名無しさん mailto:sage [2005/10/17(月) 20:20:52 ] 最悪ケースとして同心円×3 みたいな場合もあるから何も考えずに連立方程式を解くのは危ないかも 60 名前：デフォルトの名無しさん mailto:sage [2005/10/17(月) 20:39:42 ] 点の包含球だったらドロニー図書くのと似た技法使うんだっけか。 もう覚えてないや 61 名前：デフォルトの名無しさん mailto:sage [2005/10/17(月) 22:11:56 ] >>60 凸包だね。ドロネー図を求める手法なのは確かだが、凸包の方がはるかに 有名だと思うんだけど。 62 名前：デフォルトの名無しさん mailto:sage [2005/10/17(月) 22:31:30 ] ベジェでかかれた複合パスを分割するアルゴリズムへのポインタを 教えてください。 63 名前：デフォルトの名無しさん mailto:sage [2005/10/17(月) 23:33:21 ] >>56 複素数の導入をはじめとして 次元をひとつ上げると関係が急にシンプルになるケースは非常に多いので その突っ込み方はおかしいと思うす 64 名前：デフォルトの名無しさん [2005/10/18(火) 02:06:23 ] >>56 情報科学では、２次元の外積を定義することがありますよ 65 名前：デフォルトの名無しさん [2005/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 名前：デフォルトの名無しさん mailto:sage [2005/10/18(火) 12:20:44 ] 宿題スレ行きなよ。 67 名前：65 mailto:sage [2005/10/18(火) 12:23:16 ] 質問する前に「divide and conquer "a^n"」でググって "a^n"の部分がうまく引っ掛からずに質問したんですが キーワードをexponentiationにしたら擬似コード見つかりました。あらら。 例えばここ: ttp://www.math.grin.edu/~rebelsky/Courses/CS152/2000S/Outlines/outline.22.html#simplerecursiveexponentiation 失礼しました。 でも(b)(c)で分からなかったらまたここに来ますね。 (ということで多分戻ってくることになると思います…) 68 名前：デフォルトの名無しさん mailto:sage [2005/10/18(火) 14:14:12 ] ていうか、とりあえず代数的に解いて、 出た解を吟味するのがアルゴリズム的には簡単。 69 名前：デフォルトの名無しさん mailto:sage [2005/10/18(火) 14:17:01 ] 残り時間12時間って、提出期限は夜中？ 真夜中の専門学校？？？ 70 名前：65 mailto:sage [2005/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 mailto:sage [2005/10/18(火) 14:40:59 ] >>69 海外なものですから。 もう図書館が閉まるので8時間後くらいにまた来ます。 それまでも自分で考えてみますが、よろしくお願いします。 72 名前：デフォルトの名無しさん mailto:sage [2005/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 名前：デフォルトの名無しさん mailto:sage [2005/10/18(火) 15:45:09 ] >>69 うちの大学は情報系の課題は"日付が変わるまで"の先生が多かったけど。 74 名前：65 mailto:sage [2005/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 名前：デフォルトの名無しさん mailto:sage [2005/10/19(水) 10:13:17 ] ３点を通る円すら計算できない俺は終ったな。嗚呼 76 名前：デフォルトの名無しさん mailto:sage [2005/10/19(水) 11:58:19 ] 3点を通る円なら ttp://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) にあった。　数値計算なら、３つの円周上の点から半径が最大になる点を求めれば良さそうだが・・・・ 77 名前：デフォルトの名無しさん mailto:sage [2005/10/19(水) 23:19:46 ] 弦の垂直二等分線の交点だろ 78 名前：デフォルトの名無しさん mailto:sage [2005/10/19(水) 23:22:46 ] 幾何の話になるとどうしても図が欲しくなるな 79 名前：62 mailto:sage [2005/10/20(木) 00:34:12 ] 一般的にはないんでしょうか？企業機密？ 80 名前：デフォルトの名無しさん mailto:sage [2005/10/20(木) 01:59:03 ] ちいとは手前で考えろよ。 81 名前：デフォルトの名無しさん [2005/10/20(木) 17:26:42 ] ２点定義されてる直線のある距離の点から垂線を引きたいんですが、 簡単に引く方法はありますか？ 82 名前：デフォルトの名無しさん mailto:sage [2005/10/20(木) 17:45:14 ] プログラミングの前に数学勉強しろよ 83 名前：デフォルトの名無しさん mailto:sage [2005/10/20(木) 17:47:37 ] >>81 方向ベクトル求めれば直交する方向ベクトルが自明に定まるのでそれを使う 84 名前：デフォルトの名無しさん mailto:sage [2005/10/20(木) 22:01:41 ] >>81 >>76のページに　２点の中点を通りそれに直行する直線　というのがある また、 ＞　3)点(X1,Y1)に一番近い点 {c(cX1-sY1)-s*d,-s(cX1-sY1)-c*d} を使えば、その点と結べば垂線だ 85 名前：デフォルトの名無しさん [2005/10/20(木) 23:56:47 ] >>81 3角定規をあてる。 86 名前：デフォルトの名無しさん mailto:sage [2005/10/21(金) 01:16:51 ] 寧ろコンパスかと。 87 名前：デフォルトの名無しさん [2005/10/21(金) 10:33:10 ] >>85 代数学では、３角定規は平行線を描く以外に使っちゃダメだろ習わなかったか？ そもそもアレは９０ﾟなのか？ 88 名前：デフォルトの名無しさん mailto:sage [2005/10/21(金) 10:36:15 ] >>87 ﾊｧ? 代数学? 89 名前：デフォルトの名無しさん mailto:sage [2005/10/21(金) 11:20:04 ] >>62　だと、何を聞きたいのか判らん。 >>79 90 名前：デフォルトの名無しさん mailto:sage [2005/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 名前：デフォルトの名無しさん mailto:sage [2005/10/23(日) 10:35:15 ] >>90 証明のヒントを下さい。 92 名前：90 mailto:sage [2005/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 名前：デフォルトの名無しさん mailto:sage [2005/10/23(日) 15:32:04 ] >>92 ありがとうございました。 94 名前：デフォルトの名無しさん mailto:sage [2005/10/23(日) 18:48:38 ] ゼロと比較する時は要注意だ。 95 名前：デフォルトの名無しさん mailto:sage [2005/10/23(日) 19:07:39 ] >>90 複素平面上だと Im((z1-z3)/(z2-z3)*(z2-z4)/(z1-z4))=0 96 名前：デフォルトの名無しさん [2005/10/25(火) 22:00:04 ] アルゴリズムC・新版―基礎・データ構造・整列・探索 R. セジウィック (著), Robert Sedgewick (原著), 野下 浩平 (翻訳), 佐藤 創 (翻訳), 星 守 (翻訳), 田口 東 (翻訳) この本って買い？ 内容とか翻訳の質とか教えてください。 97 名前：デフォルトの名無しさん [2005/10/25(火) 23:15:47 ] 買いです。 Cのコーディングスタイルは疑問なんで、丸写ししたい人向けじゃないです。 98 名前：デフォルトの名無しさん mailto:sage [2005/10/26(水) 00:05:01 ] 新版はコードましになってると聞いたけど不明。 99 名前：デフォルトの名無しさん [2005/10/26(水) 16:52:05 ] 平面座標に座標配列で定義された閉じたポリゴンがあるとして、 そこにある座標がポリゴン内か外か、どういうアルゴリズムになりますか？ 100 名前：デフォルトの名無しさん mailto:sage [2005/10/26(水) 17:05:56 ] なんで >>76 のリンク先に丁度ある話題ばかりでるのだろう？ どっかの学校があそこみて課題出してる？

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef