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

1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ] 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉 >プログラム板の皆さん、こんにちは。 >無謀にもこんなスレを立ててみました。 >四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。 >人間にとって計算しやすい方法についても別途語ることにしましょう。 前スレ↓ pc8.2ch.net/test/read.cgi/tech/1090227743/ 116 名前：デフォルトの名無しさん mailto:sage [2005/11/02(水) 18:48:19 ] FFTみたいのが使えたらいいのにね・・・・って事？ 117 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 00:53:28 ] てゆうか、最低限やらなあかん計算量ってのがある罠。 それ以下にはできんでしょ。 118 名前：112 mailto:sage [2005/11/03(木) 01:46:51 ] >>116 FFTのアルゴリズムを理解してないんでなんとも言えませんが、 nが2の累乗みたいな特定の条件下のみで最適化可能というものでも もしあればありがたいと思いましたが。。 >>117 ごもっともです。 必要なデータを読み出さずに計算なんて神の所業ですよね。 自分の書いたＣ言語のプログラムが、二次形式を計算する箇所の for文二重ループたったひとつのせいでむやみやたらと遅くなったもので。。 だいたいnが数百〜数千くらいなんで当たり前っちゃ当たり前なんですが。 二次形式をn*100回以上繰り返し計算するわけですが、今回の場合、 Aはいつも定数で、xは要素のどれか一つだけが更新されているという 条件があって、もう少し計算が省けそうなのでがんばってみます。 119 名前：112 mailto:sage [2005/11/03(木) 01:51:08 ] 間違いました。訂正です。 > xは要素のどれか一つだけが更新されているという条件 どれかひとつじゃなくてxの要素はまるごとそっくり 入れ替わっている必要がありました。失礼。 120 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 06:53:34 ] そもそも計算しないで済ませる 121 名前：120 mailto:sage [2005/11/03(木) 07:16:43 ] 途中で書き込んじゃった．で，どんな問題解いてるの？ 行列処理だったら本質的に O(N^2) は避けられないので，それが許せないなら問題に合わせた解法を用意するしかない． 例えば A が問題設定の時点でわかってるならそれを対角化するような座標を選んで O(N) の反復に落とすとか． 122 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 08:08:58 ] >112 １．SIMD命令で最適化する ２．ループを展開する 123 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 10:23:41 ] >>122 >>122 >>122 >>122 >>122 >>122 >>122 >>122 124 名前：デフォルトの名無しさん [2005/11/03(木) 15:59:19 ] 数学板で質問させていただいたのですが、ム板で伺ったらよいアドバイスが聞けるのではとの誘導を受けたので質問させていただきます。 直方体の空間をm*n*n個の直方体にさいの目状に分割したとします。で一個一個の直方体をセルとします。 例えば一つのセルの大きさを1とすると、 セル（i ,j ,k）は八つの点（i, j, k),(i+1, j, k),(i, j+1, k), (i, j+1, k), (i, j, k+1),, (i, j+1, k+1), (i+1, j, k+1), (i+1, j+1, k+1) を頂点とする直方体です。(i, j, k = 0, 1, 2, 3...) この空間内に単位方向ベクトルA(u, v, w)と通る点P(p, q, r)で表される直線を与えたとします。 すると直線は媒介変数表示でP + t*Aとかけると思います。 この直線がどのセルを通過するのか、 またはあるセル(i,　j,　k)とこの直線が交わるか判別するには どのように考えたら宜しいでしょうか？ 実際には、光線が通過するセルとの2つの交点を求めて、そのセル内での光線の通過距離を計算しようとしています。 125 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 16:26:47 ] 数学板で聞いたとの事ですが 最終的に作りたいのはプログラムコードなわけですか？ 126 名前：デフォルトの名無しさん mailto:sage [2005/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 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 16:53:50 ] 俺は>>126に書いてあることが理解できていないんだが まず隣接する直方体をまとめて大きい直方体を作ってその直方体と 光線が交わるならその直方体の中の小さい直方体を調べる、という やりかたで計算量を減らせると思うよ（八分木、oct tree）。 128 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 17:02:22 ] DDAのように始点から追っていったらどう？ 全体の直方体との交点のうち一方を始点に使って。 通過するセルの数は m + n + n よりも小さいし。 129 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 17:13:24 ] 問題が分からん 1) あるセル(i,　j,　k)と直線が交わるか判別する 判別して通ると分かった場合に 2) その通るセルと直線との交点（２つ）を求めて、 　　そのセル内での光線の通過距離を計算する ということ？ 130 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 17:31:15 ] ええ。最終的に光線の通るセルが分かる→そのそれぞれのセル内での通過距離が分かる様な感じです。 A)全てのセル（m*n*n個)について光線と交わるか判別する→その通るそれぞれのセルについて光線との交点とセル内での光線の通過距離を計算 B）直線の式から通過するセルが分かる夢のような方法→その通るそれぞれのセルについて光線との交点とセル内での光線の通過距離を計算 のどちらかでしょうか。実はプログラミング自体限りなく初心者なので オクトリー・DDAなどのアドバイスしていただいたアルゴリズムについて勉強してみようと思います。 131 名前：デフォルトの名無しさん mailto:sage [2005/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 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 18:16:16 ] >>131に賛成。あるセルが通るかどうかを全部のセルについてやるより x,y,zにだらーって整数を入れてって交点を求めてから、その交点がどのセルに属すかやったほうがよさげ。 133 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 18:19:11 ] 該当する格子の周囲(距離一)を探索すれば十分？ 134 名前：デフォルトの名無しさん mailto:sage [2005/11/03(木) 21:14:54 ] >>124 "ray march"のようなことがやりたいのかな？ 135 名前：124 mailto:sage [2005/11/03(木) 23:48:11 ] 沢山のアドバイス有難うございました。色々自分なりに調べてみたところ、>>128さんの仰ってくださったDDAや>>131さんの方法に似た方法で CGの分野では直線描画の基本らしい「ブレゼンハムのアルゴリズム」というものがヒントになりそうです。 農学系の研究にCGの手法が役立つとは・・・本当に有難うございました。 136 名前：デフォルトの名無しさん mailto:sage [2005/11/04(金) 13:11:07 ] >>135 農学って、単位空間あたりの光量の計算とかでもするのかな？ ＣＧでボクセル描画するのだとばっかりおもてたyo 137 名前：フローチャート [2005/11/08(火) 17:16:52 ] 自然数ｍ、ｎに対して、ｍのn乗を計算する効率のよいアルゴリズムを フローチャートで書け。 138 名前：デフォルトの名無しさん mailto:sage [2005/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 名前：デフォルトの名無しさん [2005/11/08(火) 17:32:16 ] 日本ＮＯ１プレミアムＭＭＯ CreateGame〜陸海空オンライン〜 ただ今、鋭意開発中！力ある奴だけこい！ 140 名前：フローチャート mailto:fh [2005/11/08(火) 19:32:26 ] >>138 フローチャートを書け、という課題なので、フローチャートを書いてください 141 名前：デフォルトの名無しさん mailto:sage [2005/11/08(火) 19:46:42 ] >>140 そのぐらいは自分でやりなさい。そもそも掲示板にどうやって フローチャートを描けと。 142 名前：デフォルトの名無しさん mailto:sage [2005/11/08(火) 20:29:36 ] こんなもんかな。 ○pow(m, n) │ │n==0 ◇─┐ │　 ○return 1 │ │n%2==1 ◇─┐ │　 ○return m * pow(m, n - 1) │ □t = pow(m, n / 2) │ ○return t * t 143 名前：デフォルトの名無しさん mailto:sage [2005/11/08(火) 20:55:31 ] >>142 もっと効率よくできるはずです。やり直しなさい。 144 名前：デフォルトの名無しさん mailto:sage [2005/11/08(火) 20:56:13 ] >>142 あと、そのアルゴリズムにはバグが潜んでいます。なおしなさい。 145 名前：デフォルトの名無しさん [2005/11/11(金) 00:09:51 ] 晒しage 146 名前：デフォルトの名無しさん mailto:sage [2005/11/11(金) 01:23:17 ] >>137 ○pow(m, n) │ □　ret　←　1 │ △　ループ(　i=0 ; i<m ; i++) │ □　ret ← ret*n; │ ▽ │ ○　戻り値 ← ret 147 名前：デフォルトの名無しさん mailto:sage [2005/11/12(土) 04:00:38 ] 巡回セールスマン問題をブルートフォースで解くソースコードってないですか？ 擬似コードでもいいです。 148 名前：デフォルトの名無しさん mailto:sage [2005/11/12(土) 07:15:53 ] >>147 枝刈りも何もなしでいいなら15分くらいで書けるでしょ 149 名前：147 mailto:sage [2005/11/13(日) 11:03:59 ] >>148 その枝刈りも何もなしでいい15分くらいで書ける奴をお願いします。m(__)m 150 名前：デフォルトの名無しさん mailto:sage [2005/11/13(日) 11:38:37 ] >>149 その代わり解くのには数年間〜数十年間(ry 151 名前：147 mailto:sage [2005/11/13(日) 12:02:13 ] >>150 ドサ回りする都市の数は5くらいまででいいです。 152 名前：デフォルトの名無しさん mailto:sage [2005/11/13(日) 17:16:00 ] >>151 入力データの仕様をください 153 名前：デフォルトの名無しさん mailto:sage [2005/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 mailto:sage [2005/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 mailto:sage [2005/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 mailto:sage [2005/11/14(月) 11:58:32 ] 仕様を少し変更しました。パスの数をユーザーから求めて、その数だけ入力がされたら終了、としました。 #include <iostream> #include <vector> #include <algorithm> #define min(a,b) (((a)<(b))?(a):(b)) using namespace std; const int inf = 1 << 30; // brute force using recursion ( O(n!) ) int solve(int pos, int start, vector< vector<int> >& adj, vector<bool>& visited) { visited[pos] = true; int d = inf; if (find(visited.begin(), visited.end(), false) == visited.end()) d = adj[pos][start]; for (int i = 0; i < visited.size(); ++i) if (!visited[i]) d = min(d, adj[pos][i] + solve(i, start, adj, visited)); //←ここで何か記録しないといけないんでしょうが… visited[pos] = false; return d; } void main() { int cities, paths; cout << "Number of Cities: "; cin >> cities; cout << "Number of Paths: "; cin >> paths; vector< vector<int> > adj(cities, vector<int>(cities, inf)); int a, b, d; cout << " S D Distance" << endl; for (int i = 0; i < paths; ++i) { cout << "Path" << i+1 << ": "; cin >> a >> b >> d; adj[a][b] = adj[b][a] = d; } vector<bool> visited(cities, false); int start = 0; visited[start] = true; cout << "The minimum distance is " <<solve(start, start, adj, visited) << endl; } あの、で、最短のルートを表示するにはどうしたらいいんでしょうか？本当にしつこくてすみません。m(__)m 157 名前：デフォルトの名無しさん mailto:sage [2005/11/14(月) 17:58:34 ] いくつか手はあるけど，手っ取り早いのは「各 visited の状態から次何を選んだか」を グローバルの map<vector<bool>, int> にでも覚えさせておくこと． 表示するときは適当な visited からスタートして，visited = 全部 true になるまで覚えさせた map を辿っていく． 具体的には下みたいな感じにやる． kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/1082.cpp 158 名前：157 mailto:sage [2005/11/15(火) 06:58:17 ] solve(i, start, adj, visited) を二回も呼んでるのが非効率なのでなんとかしといてください 159 名前：147 mailto:sage [2005/11/15(火) 15:43:57 ] >>157 ありがとうございます！m(__)mﾊﾊｧｰ　m(__)mﾊﾊｧｰ　m(__)mﾊﾊｧｰ　m(__)mﾊﾊｧｰ　m(__)mﾊﾊｧｰ 再帰の途中で覚えさせる方法が分からなくて困っていました。 なるほど、ああやって割り込むんですね。本当に勉強になります。 solve(i, start, adj, visited)を二回呼んでるのは後でなんとかします。 ああ、もっと賢くなりたい。←自分 160 名前：フローチャート mailto:fh [2005/11/23(水) 20:25:34 ] 価格Ａ，Ｂの商品をそれぞれＸ，Ｙ個、購入する場合の 支払い金額を計算するフローチャートを示せ。ただし、値引き率８％と 消費税５％を考慮すること 161 名前：デフォルトの名無しさん mailto:sage [2005/11/23(水) 20:28:11 ] >>160 そりは難しい課題だねえ。 まずはフローチャートを描くルーチンを作成しないと。 環境は何？　まさか、線を引くルーチンから作らなくちゃいけない？ 162 名前：デフォルトの名無しさん mailto:sage [2005/11/26(土) 17:42:03 ] その前に有理数体での加減乗除を定義しないと。 また、有理数の円未満の端数処理をどうするか検討しないとな。 切捨て？切りage？四捨五入？設定で選択できるようにしないと 実用に耐えないかもよ。 163 名前：デフォルトの名無しさん mailto:sage [2005/11/26(土) 20:15:28 ] 意地悪なやつらめ。そんなおまえらが好きではあるけど。 164 名前：デフォルトの名無しさん mailto:sage [2005/11/26(土) 21:21:57 ] まあ 137 あたりの経緯があるからな 165 名前：デフォルトの名無しさん mailto:sage [2005/11/27(日) 18:06:06 ] >>162 有理数体上の加減乗除は自明じゃねーの？ 166 名前：デフォルトの名無しさん mailto:sage [2005/11/27(日) 21:26:38 ] ていうかコンピュータ上では有理数全てを表現できないし 167 名前：デフォルトの名無しさん mailto:sage [2005/11/27(日) 21:35:56 ] ディジタルコンピュータ上ではできないね。 168 名前：デフォルトの名無しさん mailto:sage [2005/11/27(日) 21:45:26 ] 全ては表現できなくても適当な位相さえ入れば十分でしょ 169 名前：デフォルトの名無しさん mailto:sage [2005/12/01(木) 12:06:34 ] てか、実数から見たら表現できる数値なんて穴だらけだよな。 170 名前：デフォルトの名無しさん mailto:sage [2005/12/01(木) 18:13:16 ] つ 区間演算 171 名前：デフォルトの名無しさん mailto:sage [2005/12/04(日) 01:41:03 ] 配列nに対してn-1個の値があり、残りひとつはNULLでも0でもいいのでデータとしては何も入ってない状態。 その配列nの中のn-1個の数列を配列nの中だけでソートしたいのですが何かいいアイデアないでしょうか？ つまりデータ構造やポインタは勿論、 二分木や多分木を使ってヒープも駄目ということです。 172 名前：デフォルトの名無しさん mailto:sage [2005/12/04(日) 02:00:23 ] バブルソートなりクイックソートなり 173 名前：デフォルトの名無しさん mailto:sage [2005/12/04(日) 03:54:54 ] >171 状況がよくわからん。 具体的に。 174 名前：デフォルトの名無しさん mailto:age [2005/12/05(月) 16:33:28 ] カタカナの「ノ」の形の離散データの極率を求める数値計算法ってありますか？ 書物で調べたりググったりしていますが、見つかりません。 175 名前：174 mailto:age [2005/12/05(月) 16:35:59 ] 極率　ではなく　曲率　でした。 176 名前：デフォルトの名無しさん mailto:sage [2005/12/05(月) 16:40:06 ] 二次回帰分析とかって話? 177 名前：174 mailto:age [2005/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 名前：デフォルトの名無しさん mailto:sage [2005/12/05(月) 19:46:30 ] 最小二乗フィッティングだね． 理論的には，s_1, ..., s_n をパラメータとする関数 f(x; s_1, ..., s_n) を データ列 (x_1, y_1), ..., (x_N, y_N) にフィッティングするときは誤差の二乗和 φ(s_1, ..., s_n) = Σ(f(x_i; s_1, ..., s_n) - y_i)^2 を最小化する s_1, ..., s_n を求めてやればいい． で，それは結構難しくて，凸関数とか条件付かないと最良解が出る保証は無い． ある程度の解でいいなら，「勾配法 + アニーリング」くらいで，それなりに求まってくれるはず． 179 名前：デフォルトの名無しさん [2005/12/05(月) 19:50:09 ] 画像調整のガンマをスクロールバーで実装したいのですが、 イマイチ正確な定義が分かりません。 それか、組み込めるライブラリどこかに落ちてないでしょうか？ 180 名前：174 mailto:age [2005/12/05(月) 20:15:07 ] >>178 詳しいレスありがとうございます。 今現在では、範囲と精度を与えて、全部の(p, q)について調べ、その誤差の二乗和が 最小になる(p, q)の組を解としています。 勾配法、アニーリングを調べてみて、検討してみます。 181 名前：デフォルトの名無しさん mailto:sage [2005/12/05(月) 20:17:32 ] >>179 質問の意味がわからないけど多分スレ違い。 ・言語と開発ツールは何を使ってるのか ・具体的にやりたいことは何か ・今自分は何がわからないのか この三点をはっきりさせて、適切なスレに行って聞いてください。 182 名前：デフォルトの名無しさん [2005/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 名前：デフォルトの名無しさん mailto:sage [2005/12/05(月) 21:18:39 ] >>182 OK． ただ偏微分したもの = 0 が陽に解ける保証はどこにもないし，解けたとしても解は一般に複数存在するので 出した解が本当に良いフィッティングになってるかは十分議論する必要がある． 184 名前：182 [2005/12/05(月) 21:30:11 ] >>183 ありがとうございます。勉強になります。 185 名前：アルゴリズム mailto:fh [2005/12/06(火) 10:20:52 ] N人分のデータ（氏名、体重、身長、年齢）がＤＡＴＡ文で入力されているプログラムが ある。これを用いて次のプログラムをＢＡＳＩＣで作成しなさい 年齢が３０歳以下の人の、体重と身長の平均値を計算し表示する 186 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 10:59:37 ] select average(weight), average(height) from DATA where (age <= 30); 187 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 12:50:40 ] >185 スレタイくらい嫁。 くだ質スレか宿題スレ池や。 188 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 20:36:58 ] >177 エクセルにデータを叩き込んでexpの形で近似曲線出すのが一番手軽な希ガス。 ところでexp（）の形になると判ってるなら、logを取ったらどうなる？ 189 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 21:51:46 ] プチ統計学講座だなｗ 190 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 22:09:54 ] >>188 ヒント：Windowsとは限らない 191 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 22:28:03 ] ひんと：Excel以外にも統計処理できるソフトはあるし、そもそもMacでもExcelは動く。 192 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 22:34:45 ] >>190-191 ヒント：そもそも汎用機とも限らない　例：宇宙計算用スパコン だからこそのアルゴリズムスレだろ？ 193 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 23:14:51 ] だからlogとったらどうなるかと聞いてみたんだけど 194 名前：デフォルトの名無しさん mailto:sage [2005/12/06(火) 23:30:44 ] だから前半にだけ突っこんだんだけど 195 名前：デフォルトの名無しさん mailto:sage [2005/12/07(水) 19:22:24 ] まぁまぁ、次のネタを待ちましょう 196 名前：デフォルトの名無しさん [2005/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 [2005/12/07(水) 19:57:51 ] あれ！？ よく見たら>>182とまったく同じ式でした･･･。 当方、学生ではないので課題とかでもないのですが。 同じ書物を読んでいるのかしら。 >>183を参考にします。 無視してください。 198 名前：デフォルトの名無しさん mailto:sage [2005/12/07(水) 20:29:05 ] フローチャートしか知らない 199 名前：デフォルトの名無しさん [2005/12/08(木) 10:14:07 ] 二次元配列と、 その中の３つの点で定義される三角形があって、 ある点がその中か外か判定するアルゴリズム教えて下さい。 200 名前：デフォルトの名無しさん mailto:sage [2005/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 名前：デフォルトの名無しさん [2005/12/08(木) 12:26:41 ] そのまんまじゃん 202 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 13:04:30 ] ナップザックを背負ったバックパッカー*がいるとする。ナップザックの中は、 できるだけ使い勝手の良いもので満たさなければならない。ナップザックの大きさは限られているので、 どのような荷物で満たすかが非常に大事な問題となる。ナップザック問題とは、ある目的のコストが 最大となるように限られたスペースにアイテム(item)を配置する問題のことである。次の問いに答えよ *リュックサックに全ての荷物を入れて旅行する人のこと。 問1 0/1 ナップザック問題とは何か？ 問2 全てのアイテムが(1)同じコストあるいは(2)同じサイズであればナップザック問題はどん な問題となるのだろうか？ 問3 アイテムのコストが大きさに比例する場合は、ナップザック問題はどんな問題となるの か？ 問4 ナップザックの大きさがアイテムに比べて非常に大きい場合は、一体何が起こるか？参考 書にあるプログラムを使って調べ、現象から生じた問題を指摘し、それが何故生じるのか 記述せよ． 203 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 15:35:02 ] >>202 ここは君が来るべきスレでは無いよ。 204 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 15:59:27 ] >>203 いいじゃんべつに。 お前の個人的な感情は出さなくてもいいよ。 そんなもの読んでいる人間には全く価値がないから。 文句があるならどのスレにいけ、ぐらいは言えよ。 あ、頭悪スレとかに誘導するのは全く無意味だからやめてね。 205 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 18:15:33 ] >>204 つまんないﾈﾀ書くのも自由だし それを批判するのも自由。 206 名前：デフォルトの名無しさん [2005/12/08(木) 18:37:18 ] 座標３つ（どれがどの位置か不明）から、３角形の面積を計算する方法はありますか？ 207 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 18:40:49 ] >>205 自重しろよ。 自由ではないんだよ？あまりひどいとアク禁だ。 208 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 19:52:21 ] >>206 3点から辺の長さ求めてHeronの公式、とか。 209 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 20:01:43 ] 三点のベクトルが v1, v2, v3 のとき [v1-v2, v3-v2]/2 の絶対値が面積になるね。 [x,y] は x と y の外積ね。 210 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 20:02:07 ] >>206 ある点を原点に移動させるように全体を並行移動させて、 (0,0),(a,b),(c,d)の三角形の面積が(1/2)*|a*d - b*c| であることを 使った方が簡単かも。 ３点が三角形が作られない位置に無いことを確かめてからね。 211 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 20:03:50 ] 実は （>>182の式）≠（>>196の式） である件について 212 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 20:55:54 ] >>206 www.tensyo.com/urame/prog/linealgo.htm の多角形の面積でやれば？ 213 名前：デフォルトの名無しさん mailto:sage [2005/12/08(木) 23:07:36 ] >>199 >>99,>>107-108 >>204 >>187 てか、質問する前にスレ内くらいは読もうぜ？ 214 名前：デフォルトの名無しさん mailto:sage [2005/12/13(火) 18:24:45 ] >>206 でも、3点とも座標がわかってて位置不明ってどゆこと？ 215 名前：デフォルトの名無しさん mailto:sage [2005/12/13(火) 19:24:25 ] >214 「固定座標じゃない」って意味だろ。 確かに意味は解らないが、気持ちは伝わってきた。 216 名前：デフォルトの名無しさん mailto:sage [2005/12/13(火) 20:30:04 ] ヘロンの公式のことをたずねているの？

---

---

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

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