分からない問題はここに書いてね 466

1 名前：１３２人目の素数さん mailto:sage [2021/02/17(水) 00:42:07.42 ID:pOGUunX7.net] さあ、今日も１日がんばろう★☆ 前スレ 分からない問題はここに書いてね 465 rio2016.5ch.net/test/read.cgi/math/1608546793/ (使用済です: 478) 445 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 02:01:15.88 ID:Eu8CzLjp.net] シミュレーション向きかどうか分からない問題です。 不等式 　x^2 - 4 ≦ y ≦ 0 で表されるxy平面上の領域に含まれる線分の中で、最長のものを求めよ。 446 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 02:38:02.88 ID:FT1ycNw8.net] シミュレーションとか必要ない √(71/4+2√2)≒4.53634512848683 >>427 447 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 02:44:33.29 ID:sQHcAkjP.net] f(x)=x^2-4としてmax{√((x-2)^2+f(x)^2)}の最大値が線分の長さの最大値 これはx=1/√2-1の時最大をとる よって求める線分は(2,0)と(1/√2-1,f(1/√2-1))を結ぶ線分とそのy軸対称の２つである https://www.wolframalpha.com/input/?i=maximize+sqrt%28%28x-2%29%5E2%2B%28x%5E2-4%29%5E2%29+in+-2+%3C%3D+x+%3C%3D+2&lang=ja 448 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 02:49:27.20 ID:sQHcAkjP.net] >>426 勘違いorz 449 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 04:19:47.88 ID:T+i43wxS.net] >>405 の解として (1/2, 0) からの距離が 1/2 未満の領域 という予想を置いておく 450 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 04:33:57.49 ID:T+i43wxS.net] 言い換えると、 正三角形を除く三角形の内心は、重心-垂心間の線分を直径とする円の内側に存在する ということになる 証明はまだ 451 名前：１３２人目の素数さん [2021/03/28(日) 06:05:12.70 ID:/jK5jGei.net] >>426 当たり前なのは、O(n^2)で計算できることです。 452 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 06:44:30.96 ID:Jul26fm0.net] >>425 n次の巡回行列とn次元のベクトルの積は、n次元ベクトルの巡回畳み込みに相当する n次元ベクトルの巡回畳み込みは、畳み込み定理(Convolution theorem)により 高速フーリエ変換(FFT)を使ってn*log(n)のオーダーで計算できる 453 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 08:57:46.20 ID:iiFYE3Wp.net] >>429 線分の一方の端点が(2,0)になるのは感覚的には分かるけど、証明できる？ 454 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 09:03:41.21 ID:iiFYE3Wp.net] ごめん自己解決 455 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 09:45:19.86 ID:sQHcAkjP.net] >>434 wikiにはnが2べきならnlon(n)って明言してるけどそれ以外でもnlog(n)でできるんですか？ 456 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 10:05:04.30 ID:/Dlncm5P.net] シミュレーション向きの問題です 不等式 x^2-4≦y≦0 で表されるxy平面上の領域に含まれる線分の中で、最長のものを求めよ。 457 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 10:09:51.08 ID:/Dlncm5P.net] 数値計算向けの問題です 方程式 x^3-x=3 の各実数解の小数点以下2桁目の数字を求めよ。 458 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 10:13:29.34 ID:/Dlncm5P.net] 数値計算向けの問題です 整数2nCnの桁数をnで表せ。 注：2nCn=C[2n,n] 459 名前：１３２人目の素数さん [2021/03/28(日) 10:50:33.87 ID:/jK5jGei.net] >>437 できます。 460 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 12:20:07.69 ID:/Dlncm5P.net] nを正の整数の定数とする。 xyz空間の立方体領域 D: -n≦x≦n,-n≦y≦n,-n≦z≦n を考える。 Dに含まれる格子点で、z=xyかつy=xzを満たすものの個数をnで表せ。 461 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 12:39:45.75 ID:sQHcAkjP.net] >>431 どうやってやるんですか？ とりあえずwikiに載ってるアルゴリズムはnが自明でない分解n=mlを持つとき周期mでの変換と周期lでの変換に還元して‥として行くとあるのでnが小さい素因子の積になってないと大して高速化できない、というか全然高速化できない 462 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 14:25:46.01 ID:Eu8CzLjp.net] >>442 条件式を辺々掛けて 　yz = xxyz, 　(x+1)(x-1)yz = 0, 　x=±1 または y=0 または z=0,　　(←整域) 後の2つは、条件式から y=z=0 　(1,y,y)　(-1,y,-y)　(x,0,0) ∴　6n+1 個 463 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 14:45:46.48 ID:Eu8CzLjp.net] >>439 　f(x) = x^3 - x - 3　とおく。 ニュートン法で 　x　→　x - f(x)/f '(x) = x - (x^3 -x-3)/(3xx-1), 　5/3　→　5/3 + 1/198　→　5/3 + 1/198 - 991/57316842　→　1.67169988 実数解は１つしかねぇ 464 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 15:22:16.93 ID:Eu8CzLjp.net] 　y = x^3 - x - 3 　　= (x-5/3)^3 + 5(x-5/3)^2 + (22/3)(x-5/3) - 1/27, x=5/3 で接線を曳く. 　y ≒ (22/3)(x-5/3) - 1/27, y=0　とおくと　x-5/3 ≒ 1/198 　x ≒ 5/3 + 1/198 = 1.671717… 465 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 17:10:01.34 ID:Eu8CzLjp.net] どうでもいいことだが 　X = (3/2 - 180/121)^{1/3} + (3/2 + 180/121)^{1/3} = 1.671698593 は 　X^3 - [1 - (1/242)^2]^{1/3}･X - 3 = 0, の実数解 466 名前：１３２人目の素数さん [2021/03/28(日) 17:58:38.66 ID:/jK5jGei.net] >>443 ゼロで埋めて、nが2の累乗になるようにすればいいのではないでしょうか？ 467 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 18:43:31.48 ID:Eu8CzLjp.net] >>435 　a = (1 + 1/√2)/2 = 0.8535534 　b = (5/2+√2)/2 = 1.95710678 　L = √(71/4 + 2√2) = 4.5363451285 とおく。 問題の領域は 直径がLである3円 　(x-a)^2 + (y+b)^2 ≦ (L/2)^2, 　(x+a)^2 + (y+b)^2 ≦ (L/2)^2, 　x^2 + (y+b-a√3)^2 ≦ (L/2)^2, により二重に被覆されている。doubly covered. どの点も 2つ以上の円に含まれる。 どの2点も同じ円に含まれるから 距離 ≦ L. 468 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 19:49:01.62 ID:fpb6SHPW.net] >>414 この方程式をプログラムで数値解を出して 重心が(0,0),垂心が(1,0)となる三角形をAの座標を乱数発生させて描いてみた。 https://i.imgur.com/RLXA6g8.png Gが重心、oが垂心、Iが内心 469 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 20:01:29.09 ID:gC1h70qb.net] >>448 無理でしょ？ (a,b,c,d,e)と(x,y,z,u,v)を周期5で考えて畳み込んだものと(a,b,c,d,e,0,0,0)と(x,y,z,u,v,0,0,0)を周期8で畳み込んだものは一致しないでしょ？ 470 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 20:10:43.19 ID:fpb6SHPW.net] >>450 乱数発生を1000回繰り返して内心となる座標を重ね合わせてみた。 https://i.imgur.com/njz826H.png 内心の分布は円形に収まりそう。(3,1)が内心となることはなさそうだな。 471 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 20:14:27.21 ID:fpb6SHPW.net] >>452 シミュレーションの結果は>432の予想を支持する。 プログラミングが楽しめた。 472 名前：１３２人目の素数さん [2021/03/28(日) 21:00:42.43 ID:/jK5jGei.net] >>451 0で埋めると巡回行列じゃなくなってしまいますね。 473 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 21:05:40.37 ID:iiFYE3Wp.net] >>452 おー分かりやすい 何個か円の外にはみ出てる点あるけどこれは何でなん？ 474 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 21:11:51.83 ID:gC1h70qb.net] >>454 少なくともFFTを使って高速化できるのはnに何の要件もなければ無理なんじゃないかな？ 少なくともwikiではnが小さい素因子をたくさんかけた形の高速化法しか載ってない 一般の場合でもできるなら方法そのものを載せるのは無理でも論文へのリファレンスがないのは考えられないし 出題ミスかな？ FFTでできないから一般にも無理とは言えないけど [] [ここ壊れてます] 476 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 21:20:31.38 ID:gC1h70qb.net] O:外心 I内心 H:垂心 OI^2/OH^2 https://www.wolframalpha.com/input/?i=+plot+%28%28sin%28x%2By%29%2Bsin%28x%29cos%282y%29%2Bsin%28y%29cos%282x%29%29%5E2%2B%28sin%28x%29sin%282y%29-sin%28y%29sin%282x%29%29%5E2%29%2F%28%281%2Bcos%282x%29%2Bcos%282y%29%29%5E2%2B%28sin%282x%29-sin%282y%29%29%5E2%29&lang=ja 477 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 21:31:11.30 ID:fpb6SHPW.net] >>455 多分、三角形を形成しないような乱数が選択されたのではと推測。 478 名前：１３２人目の素数さん mailto:sage [2021/03/28(日) 22:57:13.38 ID:9hClS6gi.net] >>458 プロおじは出禁だぞ。 479 名前：１３２人目の素数さん [2021/03/29(月) 00:35:57.63 ID:GgCLqWW4.net] 今回は役に立ってるからな おまえさんにゃ分が悪い 480 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 00:41:01.25 ID:PU1lRMXx.net] ミスリードしてるからあかんやろ 481 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 00:58:14.08 ID:JEuzD2OD.net] プロおじは期待値から勉強し直してきなさい。 482 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 01:22:09.05 ID:JXTeJTxs.net] 訂正 https://www.wolframalpha.com/input/?i=+plot+%28%28sin%28x%2By%29%2Bsin%28x%29cos%282y%29%2Bsin%28y%29cos%282x%29%29%5E2%2B%28sin%28x%29sin%282y%29-sin%28y%29sin%282x%29%29%5E2%29%2F%28%281%2Bcos%282x%29%2Bcos%282y%29%29%5E2%2B%28sin%282x%29-sin%282y%29%29%5E2%29%2F%28sin%28x%29%2Bsin%28y%29%2Bsin%28x%2By%29%29%5E2&lang=ja 483 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 02:37:12.22 ID:rt8CA3eO.net] 延々とプロおじ追い出そうとしてる奴いるけど正直うっとうしい レス内容が気に入らないなら見なきゃいいだけなのに 484 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 02:43:06.46 ID:aDVxIJBu.net] ハサミは使いよう等と言う 出禁にするのは勿体無い 485 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 02:48:42.75 ID:/r3M6nmW.net] 公園で遊んでたらオナニーしてる人がいて困ってる状況ですし コテつけてるならNGすればいいけど、そうしない時点で「プロおじ=公衆オナニー見せつけて喜んでるキチガイ」なんだもの 486 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 02:51:59.03 ID:9N6BVMjD.net] >>466 >>466 487 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 04:38:45.90 ID:JxT5eGiE.net] 五者択一の問題に連続４問正解したら合格の試験がある。 １問解答するのに１０００円を徴収される。 太郎君は１０万円を準備して試験に臨み、問題文は読まずにランダムに解答することにした。 (1)太郎君の合格する確率はいくらか？ (2)太郎君の合格確率を1/2にするにはいくら準備すればよいか？ 488 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 06:46:22.46 ID:Q46gHliY.net] wolframalpha>>(越えられない壁)>>プロおじ >>464 左翼は、よく左翼のふりをして外国贔屓の外国右翼に利用される｡ 下手にプロおじを静観しない方がスレの為｡ 489 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 13:29:04.38 ID:pDr3G3SZ.net] >>468 （１）は　表のでる確率が1/5のコインを100回投げて4回以上連続して表がでる確率と等しいかな？ 490 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 13:58:58.60 ID:lBxffmcv.net] プロおじは社会や家庭だけでなく5chにも居場所なんかないからな。 491 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 14:23:56.95 ID:5dpYUdde.net] >>445-447 更にどうでもいいことだが 　X = 5/3 + 1/198, は 　X^3 - (１ + 3/198^2)X - (３ - 2/198^3) = 0, の実数解 492 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 14:58:15.46 ID:5dpYUdde.net] 更に更にどうでもいいことだが 　X = 5/3, は 　X^3 - (１ - 1/45)X - 3 = 0, 　X^3 - X - (３ - 1/27) = 0, の実数解 493 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 15:02:28.77 ID:pDr3G3SZ.net] >>468 (１)　 0.1175311 (2) 542000円 494 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 15:14:24.79 ID:pDr3G3SZ.net] >>445 更にどうでもいいことだがｗ グラフ化 https://i.imgur.com/rQVl1Yv.png Newton-Raphson法での数値解 > f <- function(x) x^3 - x - 3 > curve(f(x),-5,5) > abline(h=0,lty=3) > uniroot(f,c(-5,5),tol=1e-24)$root [1] 1.67169988166 495 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 16:36:11.44 ID:c+KCNM8F.net] シミュレーション向きの問題です 以下の連立不等式で表される3次元空間の立体 x^2+y^2≦1 y^2+z^2≦1 z^2+x^2≧1 を図示せよ。 496 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 17:18:02.69 ID:5dpYUdde.net] >>468 (1)　0.1176679987 (2)　542000円 n問解答後に、最後のk問が正解の確率を Q_k(n) とする。 　(n-k が不正解で、n-k+1～n が正解) 漸化式 　Q0(n) = (1-p){Q0(n-1) + Q1(n-1) + Q2(n-1) + Q3(n-1)}, 　Q1(n) = p･Q0(n-1), 　Q2(n) = p･Q1(n-1), 　Q3(n) = p･Q2(n-1), n問目で合格する確率は 　P(n) = p･Q3(n-1), 特性方程式 (1/(1-p))･t^4 - t^3 - p･t^2 - p^2･t - p^3 = 0, 特性値 (p=1/5) 　α = 0.998713391320282 541問までで合格　0.49989971143 542問までで合格　0.50054314480 497 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 17:54:16.00 ID:JXTeJTxs.net] 単にn回目までに合格する確率S(n)求めるだけならk=4として S(n)=S(n-1)+qp^k(1-S(n-k-1)) の方が早いがな 特殊解S(n)=1もすぐ見つかるし この漸化式から求まるP(n)の特性方程式は x^(k+1)-x^k=p^(k+1)-p^k もうこのネタ何十回見たやろ 498 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 19:31:54.37 ID:5dpYUdde.net] >>435 この領域を平行線で挟んだときの幅を考える。 平行線の傾きが正のときは点 (-2,0) を通り、 傾きが負のときは点 (2,0) を通る。 ∴　どちらにしても　幅 ≦ L, ∴　この領域内の線分の長さ ≦ L, 参考 　支持関数 (support function) 　凸領域 499 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 20:43:18.88 ID:L8k5fESM.net] >470の確率と一致するはずと思っての答が>474でしたが、>477と一致しないので プログラムを見直したらインデックスがひとつずれておりました。 >474は撤回して以下に修正 > P(100,1/5,4) [1] 0.1176679986993025 （2）の方は> P(541:543) [1] 0.4998997114295112 0.5005431448015157 0.5011857503265590 なので542000円のまま。 シミュレーションプログラムを組んで検証してみよう。 500 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 21:00:28.87 ID:L8k5fESM.net] 100万回のシミュレーションだと太郎君の合格確率は > mean(y[,2]) [1] 0.117868 と出た。 ちなみに太郎君が合格したときに手元に残るお金の平均値は > (100-mean(z))/10 # 合格したときの残金 [1] 4.91万円になった。案外手元に残るもんだな。 オマケ（Rのコードはここ） https://egg.5ch.net/test/read.cgi/hosp/1612996282/849 オマケのおまけ：総解答数と合格確率のグラフ https://i.imgur.com/NBTEzhb.png 501 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 21:04:17.06 ID:L8k5fESM.net] >>476 罵倒厨が３D見取り図を作る練習問題にいいかもな。 粘土でつくるかもしれんが。 502 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 21:17:05.17 ID:c+KCNM8F.net] シミュレーション向きの問題です （1）A=C[20212022,2021],B=C[20211011,2020]とするとき、KA=LBを満たす正の奇数K,Lが存在することを示せ。 （2）Aを4で割った余りを求めよ。 503 名前：１３２人目の素数さん mailto:sage [2021/03/29(月) 21:21:53.39 ID:lBxffmcv.net] 誰にも相手にされてないプロおじ虚しくないのか？ 504 名前：１３２人目の素数さん mailto:sage [2021/03/3 ] [ここ壊れてます] 505 名前：0(火) 01:11:01.96 ID:9OPtgdh7.net mailto: https://www.wolframalpha.com/input/?i=binomialcoeff%2820212022%2C2021%29%2Fbinomialcoeff%2820211011%2C2020%29&lang=ja [] [ここ壊れてます] 506 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 01:11:15.54 ID:gtiIL6DW.net] >>432 0＜α＜π/2, -α＜β＜αとして、A(cos2α,sin2α), B(cos2β,sin2β), C(cos2α,-sin2α)をとる。 任意の三角形はこの形式に相似変換できる。 外心O=0, 重心G=((2cos2α+cos2β)/3,(sin2β)/3) 垂心H=(2cos2α+cos2β,sin2β) G-Hの中点M=(2(2cos2α+cos2β)/3,2(sin2β)/3) 内心I=(cos(β+α)+cos(β-α)-1,sin(β+α)+sin(β-α))=(2cosαcosβ-1,2cosαsinβ) 線分MHとMIの距離の二乗の差を考える。 MH^2-MI^2 =(((2cos2α+cos2β)/3)^2+((sin2β)/3)^2)-((2cosαcosβ-1-2(2cos2α+cos2β)/3)^2+(2cosαsinβ-2(sin2β)/3)^2) =4cosα(cosβ-cosα)((2cosα-cosβ)^2+1-(cosβ)^2)/3 ① 0＜cosα＜cosβ＜1 なので ①≧0、よって MH≧MI 等号は(2cosα-cosβ)^2+1-(cosβ)^2=0のときのみ。cosβ=1,cosα=1/2なのでこのとき△ABCは正三角形。 よって、 ＞正三角形を除く三角形の内心は、重心-垂心間の線分を直径とする円の内側に存在する □ 507 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 03:32:52.72 ID:1nCYsZUW.net] >>456 FFTは任意のnで行えるし実装もされている（rader's fft algorithmという）。 wikipediaの情報が誤っているのは執筆者の学が足りないだけ。 508 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 03:43:46.05 ID:9OPtgdh7.net] 外接円の半径を1、外心O、垂心H、内心Iとする OI^2=3-2cosA-2cosB-2cosC OH^2=3+2cos2A+2cos2B+2cos2C OI.OH=2cosA+2cosB+2cosC-cos(A-B)-cos(B-C)-cos(C-A) 3IG.IH =(OH-3OI).(OH-OI) =2(cos2A+2cos2B+2cos2C) -14(cosA+cosB+cosC) +4(cos(A-B)+cos(B-C)+cos(C-A)) +12 =4(cosA+cosB+cosC)^2-10(cosA+cosB+cosC)+6 ≦0 (∵ cosA+cosB+cosC≦3/2) 509 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 03:53:39.25 ID:9OPtgdh7.net] 訂正 1≦cosA+cosB+cosC≦3/2 510 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 06:17:06.69 ID:hjMIVqxL.net] >>483 >468で太郎が合格したときに手元に残る金の期待値の方がシミュレーション向きだと思う。 511 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 07:22:13.42 ID:Yc3/2/EC.net] >>486 力作の投稿ありがとうございます。 三角形の五心の座標を算出する関数をおもちゃ箱から取り出して 　正三角形を除く三角形の内心は、重心-垂心間の線分を直径とする円の内側に存在する を体感してみました。 https://i.imgur.com/nGyW1AK.gif もとを辿れば、 >414の連立方程式をプログラムで数値解を出そうと探索させてみたけどして最適解がみつからず、 プログラムが間違っているのかと訝っていましたが、題意を満たす三角形は存在しないことが証明されて感動しました。 512 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 08:46:53.71 ID:Jgfj8cZF.net] >>487 そりゃ離散フーリエ変換自体は任意のnで定義されてるでしょ？ 問題はその計算量 これもwikiだのみだけど 畳み込み積分の計算をゼロ埋めなしのFFTで行う場合、計算時間はNの性質に強く依存する。最悪の場合、N-1 が素数 N2 により N-1= N2 と表され、また N2–1が素数 N3 により N2–1 = N3 と表され、以下同様に続いていく場合である。このような場合、レーダーのアルゴリズムの再帰が連続することになり、O(N²)の計算時間がかかる可能性がある。このような性質をもつNは ソフィー・ジェルマン素数と呼ばれ、上記の数列は一次の Cunningham(ビル-カニンガム)チェーンと呼ばれる。しかしながら、これまでの研究ではカニンガムチェーンの成長はlog2(N)よりも遅いことが分かっているため、レーダーのアルゴリズムの再帰によりかかる計算時間はO(N²)よりかは速いと思われる。幸いにも、畳み込み計算にゼロ埋めを用いたFFTを使えば計算時間はO(N log N)のオーダーになることが保証されている。 とあるけど？ ゼロ埋め使えないし 513 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 11:04:46.46 ID:ux9g6nBw.net] >>492 イヤ、訂正 これはなんかwikiの方がおかしい気もする アルゴリズムの内容も読んでみたらnlog(n)で計算できる気もする 514 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 12:31:15.21 ID:1nCYsZUW.net] >>493 なぜゼロつめができないと決めつける？ 非巡回畳み込みはゼロつめで高々2倍のnで2^kの計算に持ち込めて定数を無視すると O(2n*log(2n))=O(n*log(n))で計算できる。 巡回畳み込みは非巡回畳み込みをn回足せばよいだけだからこれもn*log(n)オーダで計算できる。 したがって任意の非巡回、巡回畳み込みはn*log(n)オーダで計算でき、 任意のnの離散フーリエ変換もこのオーダーで計算できる。 またレーダーの方法以外にも素数nの離散フーリエ変換をO(n*log(n))で計算するアルゴリズムは少々技巧的だが存在する。 515 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 12:41:51.51 ID:85330UQl.net] >>494 イヤ、実際できないでしょ？ [[a,b,c],[b,c,a],[c,a,b]]と[p,q,r] のサイズが2冪になるように0詰めしたら [[a,b,c,0],[b,c,0,a],[c,0,a,b],[0,a,b,c]]と[p,q,r,0] になってこの積は高速に計算できるかもしれないけど、それは元の行列とベクトルの積とは一致しない オーディオ機器とかへの応用ででNのサイズに特に意味がないなら好きなだけ0詰めすればいいけど、今数学の問題で「行列とベクトルの積をFFTの理論を応用して高速に行いたい」というテーマなんだから0詰めなんてできないじゃん？ 516 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 12:49:56.29 ID:1nCYsZUW.net] >>495 訂正:高々2倍→高々4倍 (a,b,c)×(p,q,r)は (a,b,c,0,0,0,0,0)×(p,q,r,0,0,0,0,0)を計算して、 巡回してない部分を足し合わせることで計算可能 517 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 12:57:12.84 ID:85330UQl.net] >>496 どうやって？ もちろん(a,b,c,0,0,0,0,0)×(p,q,r,0,0,0,0,0)には元の(a,b,c)×(p,q,r)を計算するためのデータは揃ってるけどホントに求めたい(a,b,c)×(p,q,r)のn個あるデータそれぞれを計算するために高々logn回の計算で辿り着かなければいけない どうやってやるの？ 518 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 13:16:14.35 ID:1nCYsZUW.net] >>497 だから具体的に書くと (a,b,c,0,0,0,0,0)×(p,q,r,0,0,0,0,0)=(ap,bp+aq,cp+bq+ar,cq+br,cr,0,0,0) でさらに (第1要素+第4要素,第2要素+第5要素,第3要素)=(ap+cq+br,bp+aq+cr,cp+bq+ar) を計算すると完全に巡回畳み込みと一致する 519 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 13:25:28.33 ID:85330UQl.net] >>498 それ必要になる成分の数にちゃんと制限あるん？ 2冪でうまく行くのは後で足し合わせる時1,2,4,8‥成分だけ計算しておけば、残りはそれらのlog(n)回の足し引きで済むから早くなるけど、0埋めして、行列×ベクトルのlog(n)個以内の足し引きで必ず済むの？ 520 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 13:35:25.16 ID:85330UQl.net] あ、>>499の前半の早くなる理由はウソ しかし後半が自明でないのはその通りじゃない？ v×wを0埋めして(v,0..)×(w,0‥)の計算がnlog(n)で計算できたとして、目標のv×wの各成分は(v,0..)×(w,0‥)の各成分の高々log(n)個の線形結合になってるの？ 計算できるかどうかじゃないよ？ 計算量の問題だよ？、 521 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 13:49:25.85 ID:85330UQl.net] アレ 失礼しました 高々2個か 522 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 17:46:58.34 ID:Kuq1zeeQ.net] ⊿ABC の面積を S とおく。 　S = abc/(4R),　　　　　　(← 正弦定理) 　S = (a+b+c)/2・r, 辺々掛けて 　r/R = {8/[abc(a+b+c)]}SS 　= (a+b-c)(b+c-a)(c+a-b)/(2abc)　　(← ヘロン) 　= (bb+cc-aa)/(2bc) + (cc+aa-bb)/(2ca) + (aa+bb-cc)/(2ab) - 1 　= cos(A) + cos(B) + cos(C) - 1,　　(← 第二余弦定理) よって 523 名前： 　OI^2 = R (R-2r)　　　　　(← Chapple-Euler) 　= RR {3 - 2cos(A) - 2cos(B) - 2cos(C)}, [] [ここ壊れてます] 524 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 19:33:10.27 ID:Kuq1zeeQ.net] >>489 cos(A) + cos(B) + cos(C) = - cos(A+B+C) 　+ 4 cos(A/2) cos(B/2) cos(C/2) cos((A+B+C)/2) 　+ 4 sin(A/2) sin(B/2) sin(C/2) sin((A+B+C)/2), 　= 1 + 4 sin(A/2) sin(B/2) sin(C/2)　　　(← A+B+C=π) 　> 1, また sin(A/2) sin(C/2) sin(C/2) 　≦ {[sin(A/2) + sin(B/2) + sin(C)]/3}^3　(← GM-AM) 　≦ sin((A+B+C)/6)^3　　　　(← 上に凸 in [0,π]) 　= sin(π/6)^3　　　　　　　　(← A+B+C=π) 　= (1/2)^3 　= 1/8, ∴　1 < cos(A) + cos(B) + cos(C) ≦ 3/2 　　等号成立は A=B=C=π/3 (正三角形). 525 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 22:13:14.87 ID:B+2WTY4k.net] 筋肉関数M(n)を以下のように定義する。 M(0)=1 M(n+1)=M(n)+m(n)+i*fat(n) m(n)=1（筋トレをした場合）,-1（筋トレをしなかった場合） fat(n)=-1（筋トレをした場合）,1（筋トレをしなかった場合） いま各時刻t=0,1,2,...で筋トレをする確率は3/5とする。 M(31)の期待値を求めよ。 526 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 22:18:02.87 ID:mBXhg3m8.net] E(M(31)) =E(1)+E(m(0))+IE(f(0))+‥+E(m(30))+iE(f(30)) 527 名前：１３２人目の素数さん mailto:sage [2021/03/30(火) 23:25:20.15 ID:1dhgi6UX.net] >>488 これ読んでも理解がほとんど追い付いてないが 内積が負だから円内、と判断するのは面白いと思った 素人にはとても思い付かない 528 名前：１３２人目の素数さん mailto:sage [2021/03/31(水) 00:21:10.48 ID:QZ85spMB.net] 普通だろ 529 名前：１３２人目の素数さん mailto:sage [2021/03/31(水) 02:51:04.01 ID:/C5TwyyR.net] ゴリゴリ計算していけば答えにたどり着いた。動画解説の通り、図形をパズルにように 組み合わせれば小学生でも解けるが、ムズいな。 https://www.youtube.com/watch?v=PjLEjFdO2Gw 530 名前：１３２人目の素数さん mailto:sage [2021/03/31(水) 03:17:34.47 ID:pB24Au2w.net] >>508 勘のいい子は三平方を説明するときの、正方形の四辺に直角三角形の斜辺を貼り付けた図をすぐ思い付くんじゃないかな 531 名前：１３２人目の素数さん mailto:sage [2021/03/31(水) 03:31:17.45 ID:/C5TwyyR.net] >>508だけど、今の小学生はルート√は習うのかな？学習するのは中学生からだったかな？ いずれにせよ、小学生が解くならば√は知らないから、図形を組み合わせて解答するしかないか。 共通テストの第一問で出題したら、受験生の半分がテンパりそうな問題だな（笑） 532 名前：１３２人目の素数さん [2021/03/31(水) 08:23:45.68 ID:/UkXl8oK.net] アルゴリズムの世界的権威の著者らが書いた世界的権威のあるアルゴリズムの本に、以下が成り立つと証明なしで書いてあります。 Rが例えば整域でなくても、本当に以下が成り立ちますか？ Rを乗法に関する単位元1をもつ可換環とする。 ωをRの元とし、以下の条件を満たしているものとする。 ω ≠ 1 ω^n = 1 1 ≦ p ≦ n - 1に対して、1 + ω^p + (ω^p)^2 + (ω^p)^3 + … + (ω^p)^(n-1) = 0 このとき、 X^n - 1 = 0の解の集合は、{1, ω, ω^2, …, ω^(n-1)}である。 533 名前：１３２人目の素数さん mailto:sage [2021/03/31(水) 08:28:28.26 ID:4M8E3Zan.net] 成り立つ 534 名前：１３２人目の素数さん [2021/03/31(水) 08:56:55.28 ID:/UkXl8oK.net] >>512 証明してください。 535 名前：１３２人目の素数さん [2021/03/31(水) 09:36:18.57 ID:/UkXl8oK.net] >>512 成り立ちませんね。 536 名前：１３２人目の素数さん mailto:sage [2021/03/31(水) 10:17:08.29 ID:B295tPVx.net] 成り立つ 537 名前：１３２人目の素数さん [2021/03/31(水) 10:27:02.98 ID:/UkXl8oK.net] >>515 証明してください。 538 名前：１３２人目の素数さん mailto:sage [2021/03/31(水) 10:35:00.69 ID:B295tPVx.net] >>516 君に学問は無理です もう諦めなさい 539 名前：１３２人目の素数さん mailto:sage [2021/03/31(水) 10:38:43.45 ID:yyZA7esc.net] >>504 100万シミュレーション。 sim <- function(n=31){ M=complex() M[1]=1+ifelse(rbinom(1,1,3/5),1-1i,-1+1i) for(j in 1:(n-1)){ M[j+1]=M[j]+ifelse(rbinom(1,1,3/5),1-1i,-1+1i) } M[n] } re=replicate(1e6,sim()) 結果 > summary(cbind(m=Re(re),fat=Im(re))) m fat Min. :-18.000 Min. :-29.000 1st Qu.: 4.000 1st Qu.: -9.000 Median : 8.000 Median : -7.000 Mean : 7.196 Mean : -6.196 3rd Qu.: 10.000 3rd Qu.: -3.000 Max. : 30.000 Max. : 19.000 > 実数部をmuscle、虚数部をfatとしてグラフ化 https://i.imgur.com/cmXFXKe.png [] [ここ壊れてます] 541 名前：１３２人目の素数さん mailto:sage [2021/03/31(水) 10:53:12.54 ID:AgG38hC2.net] （　・∀・）＜ とぼけた顔して可換環 542 名前：イナ mailto:sage [2021/03/31(水) 10:53:29.37 ID:fqc5FMt5.net] 前>>373 >>508 x(1+√3)=20 x=20/(1+√3) x^2=400/(4+2√3) =200/(2+√3) V=x(x+x√3/2) =x^2(1+√3/2) =x^2(2+√3)/2 =200/2 =100(c㎡) 543 名前：イナ mailto:sage [2021/03/31(水) 11:20:11.34 ID:fqc5FMt5.net] 前>>520別解。 >>508 正方形と正三角形を円環状に並べると、 求める面積は、 同じ長さの辺を持つ正十二角形の面積の1/6 正十二角形の中の一辺20cmの正方形からはみ出した部分の面積は、 V/2の4つ分だから、 20×20+V/2×4=6V 4V=400 ∴V=100(平方cm) 544 名前：１３２人目の素数さん [2021/03/31(水) 11:34:45.03 ID:/UkXl8oK.net] >>511 反例がありますね。 アルゴリズムの世界的権威でも、専門分野から少し外れると、こんな初歩的なミスをするんですね。 545 名前：１３２人目の素数さん mailto:sage [2021/03/31(水) 11:55:30.04 ID:yyZA7esc.net] >>490 厳密解が出せるはず。

---

---

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

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