プログラミングの為の数学と算数 vol.3

1 ：07/12/08 〜 最終レス ：11/10/23

プログラムに必要な数学、算数に関する話題について語りましょう。
TIPS/Q&Aスレです。
宿題は自分で解き終わってから持ってきましょう。
前：プログラミングの為の数学と算数 vol.2
http://pc11.2ch.net/test/read.cgi/tech/1094368921/

2 ：

それと社会と美術も頼む

3 ：

>>1 おつかれ〜
過去ログ
プログラミングの為の数学と算数
http://pc.2ch.net/tech/kako/997/997150743.html
関連過去ログ
フーリエ変換について教えてください
http://piza2.2ch.net/tech/kako/996/996929748.html
交差判定アルゴリズム
http://piza2.2ch.net/tech/kako/996/996157997.html
最速の素数判定アルゴリズム
http://pc.2ch.net/tech/kako/993/993457354.html

4 ：

3次元ベクトルの外積についての質問なんですが、
a×bの外積は
a×b = (a.y * b.z - a.z * b.y a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x)
で求められると思うのですが、始めに教えてもらったときに
dot = DotProduct(a, b)とするとき、
a×b = (a.x - dot * b.x, a.y - dot * b.y, a.z - dot * b.z)
と教えてもらったのですが、これでも外積を求められるのでしょうか?

5 ：

a×b = a + (a・b) b
を主張してると思うけど、
この式の左辺は a と b の外積だから
当然 a と b の張る平面内にない
いっぽう右辺は a と b の一次結合
何かのまちがいかと

6 ：

>4
試算すりゃ一発でわかんだろ？

7 ：

>>5
やっぱり違いますよね。「これでもいける」と力説されてちょっと不安だったので安心しました。
>>6
一応計算はしてみたのですが、最近ベクトルについて勉強し始めたばかりで、
どっちがあっているかわからなかったもので…
もっと勉強しなきゃ orz
ありがとうございました。

8 ：

>>7
力説した奴は誰？

9 ：

3次元空間において各離散点(x,y,z)がスカラーを持つとき、ある任意平面で切った断面図を計算する
一般的な方法はあるんでしょうか？どんな探索・補間をすればいいのかいまいち分かりません。

10 ：

なんつうか、思ったんだが、スレタイとしては、「数学のためのプログラミング」ってのが
いいんじゃない？？

11 ：

>>10
それはそれで面白いと思うけど、でも別のスレだな

12 ：

>>9
任意平面への投影図ではなくて？
点たちはばらばらに存在しているの？
断面にはまれにしか点が乗らなくね？

13 ：

>>12
対象は、4面体や6面体が混ざった有限要素で、離散点は綺麗な格子状ではなくバラバラです。
↓のような感じで断面図を出したいのですが、どうやるのが一般的なんでしょうか？
ttp://infoshako.sk.tsukuba.ac.jp/ShakoDoc/MATLAB5/jhelp/techdoc/ref/slice.html
おそらく私が知らないだけで、すごいコモンな手法が既にあると思うのですが・・・

14 ：

>>13
Matlab は使ったことないんだけど、それは、連続なスカラー場の断面図？
離散点で値を持ってるなら、補間とかしないと無理かな。
4面体だと、バイリニア補間とかバイキュービック補間でいいと思うけど。
6面体だとどうしたもんだろう。ニアレストネイバーでいけそうな気もするか。

15 ：

>>13
そこにある例題のように、空間内のスカラー値関数 v = f(x, y, z) に対して
特定の断面に沿った v の値の分布が見たいということ？
そしてその関数 f は具体的な式などでは与えられていなくて、サンプルとして
いくつかの点における値だけがわかっているということか
補間する前に、空間全体に回転行列をかまして、断面が xy 平面になる
ようにすると処理が楽になったり？

16 ：

>>15
空間の方を回転するのは無駄だと思う。
補完って、逆から座標変換するような感じでするのが普通。
表示される xy 平面のこの点は元の空間ではこの点にあるはずだから・・・
というように。

17 ：

>>14,15
＞Matlab は使ったことないんだけど、それは、連続なスカラー場の断面図？
そうだと思います。私も使ったことはなくて、ググってたら見つけたページです・・
すいません言い忘れましたが、求めたいのは断面図だけでなく、
断面積で重み付けした値の和（つまり全断面の積分値）もでした。
要素内のある１点の値を補間で求めるのは教科書などにあり、4面体内の点(x,y,z)の場合
x=x1+ξ(x2-x1)+η(x3-x1)+ζ(x4-x1),y=・・・,z=・・・から要素内座標ξ,η,ζを求めて
p=p1+ξ(p2-p1)+η(p3-p1)+ζ(p4-p1)で補間値pが求まります。ですが、
その点の位置(x,y,z)をそもそもどうやって決めるんでしょうか？
もしかして要素との断面の重心？

18 ：

例えばよ、基底ベクトル a と b で張られる平面
P ＝ x a + y b
上の断面図を求めたければ、
P 上の点 (1, 1) に相当する三次元空間上の点は a + b だから、
この点の値を求めればいい。
この点に一番近い格子点4点を探して、
その4点に対してその補完式を使う。

19 ：

あっ、言葉足らずかも。
＞ P 上の点 (1, 1) に相当する三次元空間上の点は a + b だから
この作業を (x, y) に関して繰り返すのね。
一定範囲決めておいて。
積分したいんなら、↑の (x, y) の探索を十分広い範囲でやって、
求めたい有限要素の外にある場合は値を 0 にでもしておいて、
総和を求めればいいんじゃないかと。
あくまで、離散近似になるけど。

20 ：

ちょっと気になって前スレ950の
> |(PA×PB)・PC| / |AC・BC|
を試してみたんだけど、
a(0,0,0) b(1,0,0) c(0,1,0) p(1,1,0)
で計算したら距離0になったんだけど、俺の計算が間違ってる？

21 ：

>>20
その式、分母が間違ってるね。
四面体の体積 ÷ 底面積 ＝ 四面体の高さ ＝ 点から面への距離
と計算したいんだと思うんだけど、
その式だと分母が底面積にならない。
底面積は 1/2 |AC| |BC| cos∠ACB だ。
AC = (a, b), BC ＝ (c, d) とすると、(ad - bc) / 2
あと、分子も、それだと四面体じゃなくて
PA, PB, PC を辺とする並行6面体の体積になるから、
1/6 掛けないとだめかも。

22 ：

っていうか、平面までの距離って、
(CA × CB）・CP / |CA| |CB| な気がする。
(CA × CB） / |CA| |CB| が平面の単位法線。
CP に単位法線掛けると、平面から P までの距離。

23 ：

>>21-22
ああ、そういうことか。
どのみち、体積から求めてるなら三角形からの距離ではないし、
�僊BC平面上に点Pがあるときは求まらないか。
世の中には都合のいい公式があるもんだなぁ、とちょっと感心したんだけどそんな甘くはないかｗ

24 ：

ごめん、21 にも 22 にもちょっとずつミスが。
22 の分母は |CA×CB|。

25 ：

Pが平面状にあるときはちゃんと0になるはず。

26 ：

>25
http://pc11.2ch.net/test/read.cgi/tech/1094368921/948-950

27 ：

あ、すまそ、ポリゴンへの距離と勘違いした・・・

28 ：

      ttp://blog.livedoor.jp/dankogai/archives/50962361.html
の冒頭のグラフにあるような、実験結果のプロットからy=j+kxのj,kや、y=j+kln(x)のj,kを
求めるのって、どういうアルゴリズムでやるのでしょうか？最小二乗法でしょうか？
おねがいします。

29 ：

>>28
単にグラフ化したいなら普通に補間。
その式で言う j や k などの定数を求めたいなら最小二乗法。
ただ、もちろん、その式が j + k x の形になるとか j + k ln(x) の形になる
って当たりがついてるのが前提。
当たりつけるのは、グラフの形眺めて見て主観で決めるか、
いくつかのパターン試して二乗誤差が一番小さい奴を選ぶ。

30 ：

>>29
ありがとうございます。
「補間」というのは、単にプロットした点を直線で結ぶということでしょうか？

31 ：

線形補完ならそうだし、
非線形の補完も、2次補完とか、3次とか色々ある。

32 ：

まあ、>>28 みたいなのは補間ではないけどね。
フィッティングって言うかな。

33 ：

ある程度実践的な例で、動的計画法を勉強してみたいんですが、よい例題が載ってる
簡単な入門書やサイトってありませんか？

34 ：

>>33
実践的で簡単つーのはなかなか難しそうだが、
TopCoderやPKU JudgeOnlineの問題を解いてみてはどうだろう？
動的計画法を扱う問題を見つけるのが少し面倒だが、
TopCoderのSRMなら、Problem Set & Analysisにアルゴリズム名が載ってるから探しやすい。
（最新のはhttp://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm386）

35 ：

(A&&B)||(C&&D)は
(A||C)&&(A||D)&&(B||C)&&(B&&D)に
変形できると聞いたのですが、やりかたがよくわかりません。公式などあったら教えてください。

36 ：

最後は B||D だよね？
単なる分配法則だが、
ややこしくなるだけなのでやる必要性はない。

37 ：

分配法則
(a && b) || c = (a || c) && (b || c)

38 ：

>>36
ごめんなさい。最後は||です。
>>36-37
ありがとうございました。

39 ：

(A||(C&&D))&&(B||(C&&D))
=
((A||C)&&(A||D))&&((B||C)&&(B||D))
=
(A||C)&&(A||D)&&(B||C)&&(B||D)

40 ：

C系言語だと、||と&&は、
副作用によって結果が変わるかもしれないので注意すべし。

41 ：

適当なスレが無かったんで、ここでｵﾅｶﾞｲｼﾏｽ
Excelでグラフを作成すると、Y軸の補助目盛りが上手い具合に、自動的に
振り分けられるますよね、そのアルゴリズムってどうなってるんだろう？
今、VCでグラフを描画するソフトを書いてるんだけど、そこでちょっと
悩んでるところです、Excelにこだわらず、補助目盛りの振り方の、いいアイデアを
知っていたら教えてﾎｽｲ
条件として
負数の値はありません
最大値、最小値は同じ桁の場合もあれば、そうでない場合もあります
グラフのY軸の描画エリアは、グラフの下限値は0ではなく
要素の中の最小値（付近の値）として、最大値は要素の最大値（付近）の値です
この様な条件で、理想的な数式を教えてください

42 ：

なんかそれは理論があったはず
階級幅の適切な取り方とか

43 ：

>>42thxです
階級幅　適切　グラフ
でググッたら
地理学調査研究法（第３年度）2004年度
http://www2.ipcku.kansai-u.ac.jp/~moto/KyozaiContents/43.htm
ここに、ヒストグラムの書き方で（目的は折れ線グラフだけど数式は同じなんでしょうね・・・多分？）
階級数＝1+log(n)/log2 階級幅＝(最大値 - 最小値)/階級数で得ることができる。
こういうのがありましたが、これのことでしょうか？

44 ：

あーうん多分俺が見たのもそんな感じだったと思う

45 ：

>>44
比較的簡単そうなので、実装できそうです
ありがとう

46 ：

大きさNの配列をヒープ構造に変換する処理の計算時間がオーダーNというのがよくわかりません。
難しい数式なしで、なるべく直観的な説明をしているサイトや本は無いでしょうか？
変換処理はインプレイスでなくてもかまいません。よろしくおねがいします。

47 ：

http://zoomtv.web.fc2.com/?1xecu@StageOnAirMiku

48 ：

最小二乗法の直線Aでうまく近似できる、n個の点の集合n'があるとします。
最小二乗法の直線Bでうまく近似できる、m個の点の集合m'があるとします。
もしn'とm'が混ざってしまっているとき、直線Aと直線Bを求める方法としては
どのようなものがあるのでしょうか。
また、直線ではなく多項式近似などの場合もできればヒントなどをお願いします。
具体的には、×や§みたいな形に点の分布している場合を想像して
悩みまくり・・・どうすればー。

49 ：

最初てきとうに二つのグループに分けておいて回帰直線求める
１個の点を選んで他のグループに移した方が適合度上がるなら移す
それをずっとやる

50 ：

>>48
それ基本的に不可能だよ
クラスタリングすれば綺麗にわかれるとか特殊な場合に求められる

51 ：

>>49-50
ありがとうございます。やってみます。

52 ：

3組以上の可能性は考えなくて良いのだろうか？

53 ：

点と近傍点k個を繋いだ線分の傾きと切片を新たなxyとして係数空間にマッピングして
山をみるとかかな。ハフ変換の亜種になるのだろうか。

54 ：

２本の直線を表現する式があれば、それに対して最小２乗法を適用すればいけるんじゃないかな？
a*|x+d|+b*y+c=0
とかさ。

55 ：

何本混じっているか不明だし不可能だろう
2点ずつ1000本とかもできる

56 ：

まあ課題は２本の直線だから
媒介変数表示で 0〜∞が直線A 負数が直線Bになるような表現が出来れば
いけそうに思えてきた

57 ：

>>53が筋が良さげに見えるな

58 ：

(ax + by)^2 = (cx + dy)^2
みたいな式が、交差する2直線になるんで、
これをベースに最小二乗法つか使ってみたら？

59 ：

ああ、2直線の交点が原点でない場合、
(ax + by)^2 = (cx + dy + e)^2 とかね。

60 ：

一般の2次式を取り扱ったほうが簡明

61 ：

>>59
その式から誤差はどう計算するの？

62 ：

>>60
課題らしいから、2直線以外の結果が得られるのはまずいのでは？
>>61
a, b, c, ... 等で微分。
最小二乗法は、式さえ分かってれば直線に限らずどんな関数でもフィッティングできる。

63 ：

ああ、そうか x1,y1 って点があったら、その式のxに x1を代入して
yを求めて、複数の答えが出るから、それぞれ (y-y1)^2　出して小さい方を採用すればいいのか
でも、小さい方を採用するって事は非線形だから、解を出すのに
普通の直線みたいに楽に出せないな。

64 ：

うーん、そうか・・・
任意の関数をフィッティングできるっていっても、
陽関数形（y = f(x) みたいな形）になってないと、単純な方法では出来ないのか。
でも、
f(x, y) = (ax + by)^2 - (cx + dy + e)^2
として、求めたい直線が f(x, y) = 0 だから、
Σ_{i = 1}^N f(x_i, y_i)^2
を最小化するものとして、
これをパラメータ a, b, c, ... で微分したのが 0 って条件で式立たない？

65 ：

yについて解いたおけばいいだろ

66 ：

あと、この式だと、パラメータ a 〜 e のうち、1つは冗長かな。
f(x, y) = 0 が必要な条件式なんで、全体を a^2 で割って、
f(x, y) = (x + b'y)^2 - (c'x + d'y + e')^2
としていいはずなんで。

67 ：

>>65
それは無理。
y = ±(ax + b)
みたいな式が出てくるはず。
“2直線”みたいな変な関数を、
1価の陽関数ではあらわせない。

68 ：

yについて解けば2解出る　それぞれについて調べる

69 ：

>>68
それだと最小二乗法的な結果得られないって。

70 ：

>>68 それについて調べるといっても、サンプル点１点毎に、
どっちが小さいかって関数が必要になるから、結局は数式で解けなくて
数値解として、微分して０の箇所を探す事になる。
つまり、２直線の方程式のまま、誤差の小さい方を選択するのと全く同じ事。
でも、微分ゼロ点は複数あるのが確実だから、ランダムにシャッフルしては前回より小さくなってないか
調べる事になるわけで、コレがホントに最小かどうかってのは難しいだろな。

71 ：

2式を　f(x) g(x) としたときに、距離関数 d(y) を y = f(x) および g(x) において極小値を持つような
4次関数として定義できれば、可能なのかな。
自分には数学的に解く自信がないけど。

72 ：

h(x) = (f(x) + g(x))/2 として、
d_n = ∫[0, y_n] (y-f(x_n))(y-g(x_n))(y-h(x_n)) dy
D = Σ d_n
として、Dを最小化する f(x) g(x) を求めればいい気がする。
ただ、最終的に出てくる連立方程式はかなり複雑になりそう。
h(x) の定義も妥当かちょっと迷う。

73 ：

>>71
そんな凝るなら、>>64でよくね？

74 ：

>>73
自分には>>64の式が理解できない。
というか、バグってる気がしてならない。

75 ：

Longest Increasing Subsequence問題をDPで解くってのがさっぱりわかんない。
だれか解説して。

76 ：

diff も　Longest Increasing Subsequence問題というやつなのかな。
以前、予備知識もなしに diff もどきを作ったことがあるけど、最終的にはパート図で
クリティカルパスを求めるアルゴリズムになって、ちょっと意外な感じがした。もっと効率的な
アルゴリズムも在るんだろうけど。

77 ：

diffをdpを利用して取る論文って調べりゃいくつか出てきそうな希ガス・キセノン・クリプトン

78 ：

N+N/2+N/4+N/8+...+1回の比較処理を行うときの計算時間はO(N)だと聞いたのですが、
kNの係数kはどれくらいの大きさになるのでしょうか？どうやって計算したらいいか教えてください。

79 ：

N が 2 の累乗のときは
　(1)　　　S = N + N/2 + N/4 + N/8 + ... + 4 + 2 + 1
とおくと
　(2)　　　2S = 2N + N + N/2 + N/4 + N/8 + ... + 4 + 2
となる
(2)から(1)をひいて
. 　 　　　 2S - S = 2N - 1
つまり S = 2N となる

80 ：

>>79
どうやったらそんな発想が・・・。limとか使うのかと思いました。
どうもありがとうございます。
。。。Nが2の累乗じゃないときはどうしたらいいでしょうか

81 ：

>>78
何が知りたいかわからんが、
1+1/2+1/4/+...=、についてなら、
四角形の半分を塗りつぶして、残りの半分を塗りつぶして、残りの…と続ければわかるよね？

82 ：

うあ、遅かった。ちゃんとリロードしないとな。

83 ：

> 四角形の半分を塗りつぶして、残りの半分を塗りつぶして、残りの…と続ければわかるよね？
わからん

84 ：

>>83
わかりづらかったかな。
半分ずつってのが、1/2, 1/4, 1/8,..に対応していて、
半分ずつ塗りつぶしていく→最終的に全部塗りつぶされる≒1
ということなんだけど、説明下手でごめんなさい。

85 ：

>84
SUGEEE

86 ：

>>84
計算時間と面積は関係無いだろ？

87 ：

>>84==81
それだといつまでも塗りつぶしが終わらないのでは

88 ：

2Nの話をしてるんじゃないのか？

89 ：

離散の世界だから有限で終わる

90 ：

>>80
79じゃないけど、そういうのは高校数学の「数列の和」とか
そのあたりでやる気がする。

91 ：

>>90
kwskお願いします

92 ：

１から１００までの数を全部足すと
S = 1 + 2 + .... + 99 + 100
S = 100 + 99 + ... + 2 + 1
2S = 101 + 101 + ... + 101 + 101
2S = 101 x 100 = 10100
S = 5050
では１から１０１までの数を全部足すといくつですか？

93 ：

5050 + 101 = 5151

94 ：

>>91
等比級数の総和とかやらんかった？
1 + r + r^2 + r^3 + ... + r^n を求めるとか。
こんなやつ。
M　= 1 + r + r^2 + r^3 + ... + r^n
rM = 　　 r + r^2 + r^3 + ... + r^n + r^(n+1)
rM-M = r^(n+1) - 1
∴ M = {r^(n+1) -1} / (r-1)
r=1/2なら解き方も全部そのままなんだけどさ。
まだ習ってないっていうなら、そのうち習う。
文系だとやらんかもしれんけど、そんときは数学の先生に聞いてみるといい。

95 ：

-100 x -99 x .... x 99 x 100
を求めなさい

96 ：

>>86
N + N/2 + N/4 + N/8 + ... = N (1 + 1/2 + 1/4 + 1/8 + ...) → 2N

97 ：

>>95
0

98 ：

1/2! - 1/3! + 1/4! - 1/5! ....

99 ：

>>98
わからん。計算方法まとめてあるページ教えて。

100read 1read

1read 100read

TOP カテ一覧 スレ一覧 削除依頼 ▲
・　次のスレ
.netグレープシティコンポーネント
著作権フリーのC++高速汎用多倍長演算を作るｽﾚ
【.net】MSにS#をおねだりするスレッド【Scheme】
HSPだって