大学学部レベル質問スレ 19単位目

1 名前：１３２人目の素数さん mailto:sage [2022/08/04(木) 23:29:28.02 ID:0Ho6Owof.net] 大学で習う数学に関する質問を扱うスレ ・質問する前に教科書や参考書を読むなりググるなりして ・ただの計算は wolframalpha.com ・数式の表記法は mathmathmath.dote ra.net ・質問のマルチポストは非推奨 ・煽り、荒らしはスルー ※前スレ 大学学部レベル質問スレ 18単位目 https://rio2016.5ch.net/test/read.cgi/math/1651147986/ 652 名前：１３２人目の素数さん mailto:sage [2022/10/21(金) 21:29:12.30 ID:ScNOTOVp.net] これからの幾何学 深谷～広がりゆくトポロジーの世界 玉木 ぐらいの期間の印象。 653 名前：１３２人目の素数さん mailto:sage [2022/10/21(金) 21:31:28.62 ID:Wgp7wJ2y.net] >>622 Basic Analysis 1(Jiri Lebl)など そもそも最近の海外ででている解析学の教科書と比べて、和書の解析学(微分積分学)の教科書はちゃんと書かれていない(厳密ではなくイメージに依存した古い感覚で書かれている) だから疑問に持つのもおかしくない 654 名前：１３２人目の素数さん [2022/10/21(金) 22:12:59.29 ID:fSYIhYE1.net] >>622 位相空間論？ 655 名前：１３２人目の素数さん [2022/10/21(金) 22:16:16.79 ID:fSYIhYE1.net] >>627 >連続性なら「ホモトピー」だろ バカ？ 656 名前：１３２人目の素数さん mailto:sage [2022/10/21(金) 22:24:12.08 ID:ScNOTOVp.net] https://www.sci.tohoku.ac.jp/news/2019/11/20191125_10.jpg 657 名前：１３２人目の素数さん mailto:sage [2022/10/21(金) 23:22:58.62 ID:WxIJeRy+.net] 以下の複素積分の問題の解法を教えて頂きたいです C:z=exp(it) (0≦t≦π)とするとき、 ∫_C(√z)dzの値を求めよ。 （√zは平方根の主値を表す） 答えは-2(1+i)/3です 658 名前：１３２人目の素数さん mailto:sage [2022/10/21(金) 23:29:53.56 ID:2SQbOIKX.net] >>634 ∫_C(√z)dz = ∫[0,π]exp(it/2)i exp(it)dt = i∫[0,π]exp(3/2it)dt = 2/3[exp(3/2it)]_0^π = 2/3exp(3π/2i) - 2/3exp(0) 659 名前：ともひこ mailto:age [2022/10/21(金) 23:44:59.51 ID:wmINIqH6.net] ふくそ数のびぶんなんて そんなこと、できてたまるか。 （ ' ‘ω‘ ) 660 名前：１３２人目の素数さん [2022/10/21(金) 23:54:45.60 ID:fSYIhYE1.net] >>634 [(2/3)z^(3/2)][1,-1]（ただし平方根は上半平面の分枝） =(2/3)(i^3-1) =-(2/3)(1+i) 661 名前：１３２人目の素数さん mailto:sage [2022/10/22(土) 00:42:23.39 ID:IJaKiA99.net] >>635 わかりました！ ありがとうございます！ >>637 zの範囲を出して解いた感じですかね？ 教科書の例題は 662 名前：>>635さんが書いてくれたやり方になってるんですが、こちらのやり方でも問題ないならこちらを使いたいです [] [ここ壊れてます] 663 名前：１３２人目の素数さん mailto:sage [2022/10/22(土) 12:23:13.12 ID:IJaKiA99.net] ∫[1, π+i] zcos2z dz =(cosh2-2sinh2+2πisinh2-1)/4 となるはずなのですが、途中の処理の仕方がわかりません {(2zsin2z+cos2z)/4}'=zcos2z という原始関数を利用すると答えが合いませんでした 664 名前：１３２人目の素数さん mailto:sage [2022/10/22(土) 12:45:16.87 ID:YZXAzKeC.net] https://www.wolframalpha.com/input?i=%E2%88%AB%5B1%2C+%CF%80%2Bi%5D+zcos2z+dz&lang=ja 665 名前：１３２人目の素数さん mailto:sage [2022/10/22(土) 14:40:48.29 ID:IJaKiA99.net] >>640 こんな便利なサイトがあったとは…… 教えて頂きありがとうございます！ 666 名前：１３２人目の素数さん [2022/10/23(日) 01:39:31.16 ID:7oDzHDGj.net] 複素積分で ∫_(|z|=1) tanz dz=0 を証明せよ。 という問題なのですが、tanzが正則であることを示すにはどうすればいいですかね？ |z|=1からz=exp(it) (0≦t≦2π)として代入して処理すべきですか？ 正則であることが言えればコーシーの積分定理を適用して証明できるはずなんです 667 名前：１３２人目の素数さん [2022/10/23(日) 02:01:58.45 ID:+nDVMN8I.net] >>642 coszの零点はどこか2次方程式を解いて調べると分かろうよ 668 名前：１３２人目の素数さん [2022/10/23(日) 07:18:36.60 ID:zyp/ASe3.net] >>642 t+t^{-1}=0-->t^2=-1-->t=\pmi e^{iz}=\pmi---> z=\pm\pi/2+2n\pi よってcoszは|z|<1でゼロ点を持たない。 669 名前：１３２人目の素数さん [2022/10/23(日) 12:58:00.62 ID:7oDzHDGj.net] >>643 tanz=sinz/coszで、分母であるcoszが0にならなければ正則だということですよね sinz,coszは正則だからtanzも正則になると わかりましたありがとうございます！ >>644 すみません自分の勉強不足で式の意味がよくわかりませんでした…… 670 名前：１３２人目の素数さん [2022/10/23(日) 13:40:37.82 ID:+nDVMN8I.net] >>645 チと違う >>644を 671 名前：１３２人目の素数さん [2022/10/23(日) 16:22:08.58 ID:7oDzHDGj.net] >>646 sinz,coszは複素数平面上で常に正則 cosz=0すなわちz=(2n+1)π/2のときは正則でないが、これは|z|=1を満たさない ゆえに|z|=1の範囲ではtanzは正則 という理解で合ってますかね……？ 672 名前：１３２人目の素数さん [2022/10/23(日) 16:28:26.59 ID:oIrBag/h.net] |z|=1ではないですよね 673 名前：ともひこ mailto:age [2022/10/23(日) 16:40:28.65 ID:RXvo6MCl.net] それは たしか確かな情報です。 674 名前：１３２人目の素数さん [2022/10/23(日) 16:53:01.69 ID:+NZEJ9WX.net] >>647 >>cosz=0すなわちz=(2n+1)π/2のときは正則でないが、これは|z|=1を満たさない >>ゆえに|z|=1の範囲ではtanzは正則 「cosz=0すなわちz=(2n+1)π/2」ここを2次方程式を解いて検証したのが644 \pmはプラスマイナス(複合) 675 名前：１３２人目の素数さん [2022/10/23(日) 16:57:13.41 ID:+NZEJ9WX.net] 訂正 複合ー−＞複号 676 名前：１３２人目の素数さん [2022/10/23(日) 17:13:04.06 ID:7oDzHDGj.net] >>650 なるほど！そういう意味でしたか 理解できましたありがとうございます！ 677 名前：１３２人目の素数さん [2022/10/23(日) 17:29:54.39 ID:F4feulSb.net] >>652 たぶんわかってない 「|z|=1の範囲ではtanzは正則」ではなく 「|z|≦1の範囲ではtanzは正則」を示さないといけない (うるさく言うと|z|≦1を含む開領域でtanzは正則を示す) 678 名前：１３２人目の素数さん [2022/10/23(日) 17:40:35.11 ID:xgrNemdI.net] github.com/E869120/math-algorithm-book/blob/main/editorial/chap3-4/chap3-4.pdf 問題3.4.4（クーポンコレクター問題）の解答は正しいでしょうか？ 679 名前：１３２人目の素数さん mailto:sage [2022/10/23(日) 17:54:01.93 ID:7IX/Ea5L.net] 回数の期待値がN/1+N/2+‥+N/Nになるのは正しい 途中は知らんけど 680 名前：１３２人目の素数さん [2022/10/23(日) 17:56:49.32 ID:xgrNemdI.net] 途中の解説がよく分かりません。その解説が正しいものなのかが知りたいです。 681 名前：１３２人目の素数さん mailto:sage [2022/10/23(日) 17:57:55.12 ID:7IX/Ea5L.net] まぁぱっと見あってるよ 682 名前：１３２人目の素数さん [2022/10/23(日) 18:02:46.28 ID:xgrNemdI.net] r種類のコインを既に持っている状態からr+1種類目のコインを手に入れるまでに必要なコインの購入回数が 1回以上である確率 = 1 2回以上である確率 = (r/N)^1 3回以上である確率 = (r/N)^2 4回以上である確率 = (r/N)^3 などとなるのはわかりますが、 これからN種類のコインを集めるのに必要な購入回数の期待値が、 1 + (r/N)^1 + (r/N)^2 + … + = N / (N - r) になるというのが分かりません。 683 名前：１３２人目の素数さん [2022/10/23(日) 18:09:35.57 ID:xgrNemdI.net] ちょうど1回である確率 = 1 - (r/N)^1 ちょうど2回である確率 = (r/N)^1 - (r/N)^2 ちょうど3回である確率 = (r/N)^2 - (r/N)^3 などとなるので、 1 * [1 - (r/N)^1] + 2 * [(r/N)^1 - (r/N)^2] + 3 * [(r/N)^2 - (r/N)^3] + … = 1 + (r/N)^1 + (r/N)^2 + … + = N / (N - r) となるという説明であれば納得がいきますが、いきなり最後の式を導出しています。 684 名前：１３２人目の素数さん [2022/10/23(日) 18:10:06.70 ID:+nDVMN8I.net] >>653 >うるさく言うと 五月蝿くない そこ重要 685 名前：１３２人目の素数さん [2022/10/23(日) 18:12:54.28 ID:7oDzHDGj.net] >>653 複素数平面上ではsinz,coszは常に正則なので、tanzもcosz=0の時以外は正則 そのcosz=0の時のzは|z|=1の内部に無い つまり|z|=1の内部ではtanzは正則 っていう書き方だと減点されますかね？ 686 名前：１３２人目の素数さん mailto:sage [2022/10/23(日) 18:29:07.66 ID:7IX/Ea5L.net] >>659 > ちょうど1回である確率 = 1 - (r/N)^1 > ちょうど2回である確率 = (r/N)^1 - (r/N)^2 > ちょうど3回である確率 = (r/N)^2 - (r/N)^3 > などとなるので、 > 1 * [1 - (r/N)^1] + 2 * [(r/N)^1 - (r/N)^2] + 3 * [(r/N)^2 - (r/N)^3] + … > = 1 + (r/N)^1 + (r/N)^2 + … + = N / (N - r) > となるという説明であれば納得がいきますが、いきなり最後の式を導出しています。 上の式変形して下の式になるので納得行くならそれでいいやん 687 名前：１３２人目の素数さん [2022/10/23(日) 19:04:29.96 ID:F4feulSb.net] >>660 状況に応じて厳密さを使い分けることを覚えましょう 688 名前：１３２人目の素数さん [2022/10/23(日) 19:09:18.60 ID:iiQM/xNP.net] >>661 |z|=1の境界ではどうなんだろうってちょっと気になりますね 689 名前：１３２人目の素数さん [2022/10/23(日) 20:52:23.95 ID:ESu0BzCm.net] ∫_C1/(z^3+4z)dz（C:|z|=3） これを解くとき被積分関数をどう変形すれば良いですか 690 名前：１３２人目の素数さん [2022/10/23(日) 20:53:57.42 ID:+nDVMN8I.net] >>663 立派なことですこと 691 名前：１３２人目の素数さん [2022/10/23(日) 21:01:04.75 ID:7oDzHDGj.net] >>664 なるほど…… 内部だけでなく境界にも含まないことを明示しないとまずいですか 692 名前：１３２人目の素数さん [2022/10/23(日) 21:33:31.86 ID:xgrNemdI.net] 事象が独立、確率変数が独立、試行が独立 これらが詳しく解説されている本はありますか？ 693 名前：１３２人目の素数さん [2022/10/23(日) 22:43:40.11 ID:F4feulSb.net] >>666 立派でもなんでもない普通の話。 単一の尺度しか使えない人間がおかしい。 694 名前：１３２人目の素数さん [2022/10/24(月) 00:41:20.74 ID:+y5g9lSl.net] Σ1/(n+i)って発散するんですか？ ダランベールの判定法を使うと収束しそうなんですが…… 695 名前：１３２人目の素数さん mailto:sage [2022/10/24(月) 00:53:24.28 ID:+apjz/4q.net] Σ1/(n+i)が収束→Σ1/(n+i)、1/(n-i)が収束→Σn/(n²+1)が収束→Σn/(n²+1) + 1/(n(n²+1))が収束→Σ( n/(n²+1) + 1/(n(n²+1)) ) = Σ1/nが収束 696 名前：１３２人目の素数さん [2022/10/24(月) 01:27:59.89 ID:gxR2VJPY.net] >>670 Σ1/nから有限個の項がないだけなので発散する。(これじゃ納得いかないか？ ダランベール判定法だと1になって収束発散は判定できないと思うが。 考えの詳細を書いてもらわないとこれ以上はコメントできないな。 697 名前：１３２人目の素数さん [2022/10/24(月) 06:36:25.48 ID:NqDJNPzo.net] >>669 他人をおかしいと言い切るのはご立派で無くてはできませんね 698 名前：１３２人目の素数さん [2022/10/24(月) 07:04:49.48 ID:GaDzP1V7.net] 自分に対するどんな批判も許さないというのは プーチンのように 老い先短いものにのみ許された特権かもしれない 699 名前：１３２人目の素数さん [2022/10/24(月) 09:20:07.31 ID:+y5g9lSl.net] >>672 Σ1/n自体は収束しますよね？ だから有限個の項を取り除いたΣ1/(n+i)も収束するんじゃ……？ ダランベールの判定法は1になると判定できないんですね 勘違いしてました 700 名前：１３２人目の素数さん [2022/10/24(月) 09:55:21.35 ID:RVVdPxf0.net] >>673 >>666については言いきれ 701 名前：る [] [ここ壊れてます] 702 名前：１３２人目の素数さん [2022/10/24(月) 10:41:00.43 ID:nK7uX7AC.net] >>675 2^k/leq n <2^{{k+1}}-->1+1/2+/cdots+1/n>(k+1)/2. n/to/inftyならk/to/inftyなので Σ1/n=/infty 703 名前：１３２人目の素数さん mailto:sage [2022/10/24(月) 10:55:22.47 ID:rexIrF14.net] さすがにネタ 704 名前：１３２人目の素数さん [2022/10/24(月) 10:57:17.82 ID:Y4d1F0jj.net] >>675 調和級数は発散します 高校生でも知ってると思いますけど 705 名前：１３２人目の素数さん [2022/10/24(月) 10:59:27.70 ID:+y5g9lSl.net] 調和級数を知らなかった……お恥ずかしい…… Σ1/nは発散するので有限個の項を抜いただけのΣ1/(n+i)も発散する、と 調和級数を使わずにΣ1/(n+i)単体で証明する方法とかって他にありますかね？ コーシーもダランベールも使えないので難しいですか 706 名前：１３２人目の素数さん [2022/10/24(月) 11:04:38.27 ID:ZMzmMyLF.net] >>676 >>663がご立派な方からのご指南であることも論を俟ちませんね 707 名前：１３２人目の素数さん [2022/10/24(月) 11:05:05.66 ID:nK7uX7AC.net] >>680 >>Σ1/nは発散するので有限個の項を抜いただけのΣ1/(n+i)も発散する iは自然数であって虚数単位ではなかった？ 708 名前：１３２人目の素数さん [2022/10/24(月) 11:13:53.19 ID:+y5g9lSl.net] >>682 iは虚数単位です あれ虚数単位だと有限個の項を抜いて調和級数になるわけじゃない……？ 頭がごちゃごちゃになってきた…… 709 名前：１３２人目の素数さん mailto:sage [2022/10/24(月) 12:07:43.74 ID:GwN+2kc1.net] 気持ち悪い文末の「…」をNGにした 710 名前：１３２人目の素数さん [2022/10/24(月) 12:41:11.28 ID:+y5g9lSl.net] >>684 癖でつけてました不快にさせてすみません 711 名前：１３２人目の素数さん [2022/10/24(月) 13:12:20.23 ID:WhN3UlUK.net] …のかわりに(´・ω・`)使うとキモさがパワーアップしていいよ 712 名前：１３２人目の素数さん [2022/10/25(火) 09:30:37.43 ID:PmjaftZ2.net] 二項分布B(n, p)がnが大きいとき、正規分布で近似できるという定理を証明するのに必要な 予備知識は何ですか？ 713 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 09:39:22.89 ID:wusYNZro.net] Levyの反転公式とか 714 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 09:41:08.17 ID:wusYNZro.net] イヤ, crtではなくて2項分布限定ならstiringの公式だけでもなんとかなるか 715 名前：１３２人目の素数さん [2022/10/25(火) 10:17:52.70 ID:PmjaftZ2.net] >>688-689 ありがとうございました。 純粋に解析学の結果だと思いますが、微分積分の本で演習問題か何かで証明している本はないですか？ 716 名前：１３２人目の素数さん [2022/10/25(火) 10:36:54.58 ID:R1CUsz0D.net] >>687 個数が多いと独立に近づいていく 717 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 10:47:35.28 ID:wusYNZro.net] >>690 Levy の反転公式はちょっと高度、教科書でさがすなら数学科の専門課程で読むレベルの教科書当たらないと難しい Stiringの公式はそうでもない、般教のレベルの教科書に載ってる 具体的にと言われると俺の読んだ教科書はもう絶版してる でも今の時代なら今のキーワードでググればアホほどネットに転がってる 718 名前：１３２人目の素数さん [2022/10/25(火) 13:04:36.00 ID:PmjaftZ2.net] >>691-692 ありがとうございました。 >>692 ネットで探してみます。 719 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 16:42:04.11 ID:NushXwQu.net] 三行目の式変形がわからなくて困ってる　どうしたら1/xが出てくるんだ 初歩的な質問で申し訳ない https://imgur.com/a/99y9zEX 720 名前：１３２人目の素数さん [2022/10/25(火) 17:11:46.34 ID:PmjaftZ2.net] 甘利俊一さんの情報理論の本ですね。 721 名前：１３２人目の素数さん [2022/10/25(火) 17:16:27.43 ID:PmjaftZ2.net] f(x + ε * x) = f(1 + ε) + f(x) f(x + ε * x) - f(x) = f(1 + ε) この両辺を ε * x で割ると、 [f(x + ε * x) - f(x)] / [ε * x] = (1/x) * f(1 + ε) / ε となる。 ということだと思います。 722 名前：１３２人目の素数さん [2022/10/25(火) 18:05:16.84 ID:PmjaftZ2.net] 以下のコードが配列 A を昇順にソートすることを証明せよ。 for i in range(N): 723 名前： ■■for j in range(N): ■■■■if A[i] < A[j]: ■■■■■■swap(A[i], A[j]) [] [ここ壊れてます] 724 名前：１３２人目の素数さん [2022/10/25(火) 18:24:25.90 ID:J3r5rMEr.net] >>694 左辺の分母εxじゃん 725 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 19:35:35.09 ID:x3m7p8p/.net] for loop でi はrange(A)(だよね)の小さい方から呼ばれるのは確定してるん？ 726 名前：１３２人目の素数さん [2022/10/25(火) 19:39:56.71 ID:PmjaftZ2.net] >>699 C++風に書くと、以下のコードになります。 vector<int> A(N); for (int i = 0; i < N; ++i) { ■■cin >> A[i]; } for (int i = 0; i < N; ++i) { ■■for (int j = 0; j < N; ++j) { ■■■■if (A[i] < A[j]) { ■■■■■■swap(A[i], A[j]); ■■■■} ■■} } 727 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 20:41:41.34 ID:qRcqF8Uu.net] >>700 Aのサイズに関するinduction ♯A = 1なら自明 ♯A<Nではよいとして♯A=Nとする i = 1 で内ループが終わった状態ではA[1]に最大元が移動する ここでi:2〜N-1でのステップでj=Nとなる時点では必ずA[i]は最大元が入ることになるので事実上A[N]は動かない よってループはサイズがひとつ小さいサイズのArrayに対して行なっている操作と同じになる、ただしiが2〜しか走っていないが、仮に改めてもう一度i:1〜N-1で走らせてもA[1]に最大元が入っている状態からスタートなのでどのみちi=1の時点では何も起こらない事に注意する よってi:2〜N-1まで走らせた時点で帰納法の仮定からA[1]〜A[N-1]は昇順に並んでいる この状態で最後のi=Nのステップで全て昇順になる事は容易である□ 728 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 00:30:01.50 ID:P3jpJ7pP.net] 補題　長さNのarray A[0]〜A[N-1]においてA[0]〜A[N-2]は昇順であるとする ここに次のコードをapplyすると全体が昇順にソートされる i = N-1; for (int j = 0; j < N; ++j) { 　if (A[i] < A[j]) { 　　swap(A[i], A[j]); 　} } (∵) Nについての帰納法 N=1なら自明 N<Mで成立するとしてN=Mとする j=0での処理を終えた時点でA[0]が最小元となるのは自明 またA[1]〜A[N-2]は昇順でここにi=1から始まるコードをapplyすればA[1]〜A[N-1]は帰納法の仮定により昇順にソートされる□ 729 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 00:30:40.36 ID:P3jpJ7pP.net] 主張の証明 ♯A < N で成立すると仮定して♯A = Nとする コードを次のように変更しても結果は変わらない i = 0; for (int j = 0; j < N; ++j) { 　if (A[i] < A[j]) { 　　swap(A[i], A[j]); 　} } for (int i = 0; i < N-1; ++i) { 　for (int j = 0; j < N-1; ++j) { 　　if (A[i] < A[j]) { 　　　swap(A[i], A[j]); 　　} 　} } i = N-1; for (int j = 0; j < N; ++j) { 　if (A[i] < A[j]) { 　　swap(A[i], A[j]); 　} } (∵ 元のコードでi=0の処理が終わった時点でA[0]には最大元が入っている 一方で各1≦i<N-1にたいしてj<N-1の処理が終わった段階ではA[i]にはA[0]〜A[N-2]の最大元が入る よってこの時点でA[i]には全体の最大元が入ることになる よって続くj=N-1のときの処理ではifの条件は常にFalseであり処理が行われる事はない よって1≦i<N-1, j=N-1の時の処理は省いても結果は変わらない) ここで帰納法の仮定により改変後のコードにおいて最後のループを始める前の時点ではA[0]〜A[N-2]は昇順になっている この状態で最後のループによって昇順になる事は既に補題で示されている□ 730 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 04:40:11.07 ID:cHlveV8v.net] >>696, 698 ありがとうございます、助かりました 731 名前：１３２人目の素数さん [2022/10/26(水) 06:56:09.62 ID:Vss1j+8B.net] >>701-703 多分正解だと思いますが、正当性を記述するのって面倒ですね。 732 名前：１３２人目の素数さん [2022/10/26(水) 10:15:21.88 ID:Vss1j+8B.net] >>697,700 著者の解答は以下です： github.com/E869120/math-algorithm-book/blob/main/editorial/chap3-6/chap3-6.pdf これって間違っていませんか？ 733 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 10:37:34.59 ID:rvp30j2k.net] まぁダメやろな i = 0〜N-2まで動く時もjは0〜N-1まで動いてしまうためにi:0〜N-2の時の動作結果は“帰納法の仮定”を適用できんからな 734 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 11:38:43.03 ID:8peJPiGV.net] >>706 735 名前： だいたい合ってるよ 細かいこと言うならこんな感じ↓ i=I-1の ”内側 j ループ終了の” 時点で、A[t−1] ≦ A[I] ”<” A[t]のとき .. . . • j=t+1,..., I−1でもswapされる。 結果は同じだが A[I]=A[j] の時は swapされない swap過程で A[1]≦A[2]≦...≦A[I-1] 順序に変化は起きないことは明らか • それ以降: A[I] の値が増える可能性はあるが、減ることはない j=I−1 直後は A[I-1] ≦ A[I] とは限らないが jループ終了後は A[I] に最大値が入ることは明らか その結果 A[1]≦A[2]≦...≦A[I-1] ≦A[I] となる. [] [ここ壊れてます] 736 名前：708 mailto:sage [2022/10/26(水) 14:06:51.89 ID:8peJPiGV.net] > j=I−1 直後は A[I-1] ≦ A[I] とは限らないが ↑ 少し訂正 I = 0 の場合: 明らかに内側 j ループ終了時点で A[I] に最大値が入る. I > 0 の場合: 内側 j ループ ”処理開始”時点で A[I-1] に最大値が入っている(※帰納法の仮定に加える)ので j=I-1 で swap が起きたら A[I-1] < A[I] , 起きなければ A[I-1] = A[I] のまま変わらない. いずれにしろ j=I-1 ”処理終了”時点で　A[I-1] ≦ A[I] が確定して A[I] に最大値が入る. j=I 以降で swap は生じない. 737 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 18:28:46.82 ID:i/+rfYjL.net] まぁ二重の帰納法で受験数学の問題だとかなり難問だよな 738 名前：１３２人目の素数さん [2022/10/26(水) 20:47:56.30 ID:KTa78anx.net] >>705 プログラムの正当性の証明を与える理論があったような気がする 帰納法で証明するなら 「内側のループ抜けた時点でそこまでのソートが終了している」 という命題にするのね 739 名前：１３２人目の素数さん [2022/10/27(木) 20:03:51.08 ID:dVXdGNpU.net] atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bi f : N → N を f(n) が n の約数の個数であるような関数とする。 1 * f(1) + 2 * f(2) + … + n * f(n) の値を O(n) で出力する方法を述べよ。 740 名前：１３２人目の素数さん [2022/10/27(木) 20:04:43.63 ID:dVXdGNpU.net] >>707-711 ありがとうございました。 741 名前：１３２人目の素数さん [2022/10/27(木) 20:06:25.53 ID:dVXdGNpU.net] リンク先を間違えました。訂正します。 atcoder.jp/contests/math-and-algorithm/tasks/abc172_d f : N → N を f(n) が n の約数の個数であるような関数とする。 1 * f(1) + 2 * f(2) + … + n * f(n) の値を O(n) で出力する方法を述べよ。 742 名前：１３２人目の素数さん [2022/10/27(木) 20:56:35.09 ID:dVXdGNpU.net] あ、分かりました。 農{d = 1}^{n} d * (floor(n/d) * (floor(n/d) + 1)) / 2 これで Θ(n) で計算できますね。 743 名前：１３２人目の素数さん mailto:sage [2022/10/27(木) 21:49:23.36 ID:TYQqpd07.net] >>715 どうしてこれで計算できるのか、誰か教えてください 744 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 01:21:30.81 ID:lv2p8O4G.net] 1 * f(1) + 2 * f(2) + … + n * f(n) = Σ[ m ≦ n ]Σ[ d ≦ n, d | m ] m = Σ[ d ≦ n ]Σ[ m ≦ n, d | m ] m = Σ[ d ≦ n ]( d + 2d + 3d + ... + ⌊n/d⌋d ) = Σ[ d ≦ n ] d⌊n/d⌋(⌊n/d⌋+1)/2 745 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 08:04:37.22 ID:7H6AX/lv.net] >>717 ありがとうございます、理解できました Σ[ m ≦ n ]Σ[ d ≦ m, d | m ] m = Σ[m ≦ n]Σ[d ≦ m] m * θ(d|m) { θ(expr) := expr ? 1 : 0 } = Σ[m ≦ n]Σ[d ≦ n ] m * θ(d|m) = Σ[d ≦ n]Σ[m ≦ n] m * θ(d|m) =Σ[d ≦ n] { d + 2d + ... + floor(n/d)*d } = ... 746 名前：１３２人目の素数さん [2022/10/28(金) 09:47:19.16 ID:Fb3X/X4M.net] 以下は、高校の教科書からの引用です。 (1) 次に、 U の中に、2つの事象 A, B がある場合を考えよう。 このとき、次のような事象を考えることが多い。 A, B がともに起こる事象 A ∩ B A, B の少なくとも一方が起こる事象 A ∪ B ----------------------------------------------------------- (2) 1枚の硬貨を投げる試行を T_1、1つのサイコロを投げる試行を T_2 とし、試行 T_1 と試行 T_2 を組み合わせた試行を考える。 この試行において、 硬貨では表が出る事象を A, サイコロでは 1 または 2 の目が出る事象を B とするとき、確率 P(A ∩ B) を求めてみよう。 ----------------------------------------------------------- (1)では、全事象 U というのがあって、 A, B はその中の事象です。 (2)では、 T_1 に対応する全事象 U_1 があり、 T_2 に対応する 全事象 U_2 があります。 A は U_1 の中の事象であり、 B は U_2 の中の事象です。それにもかかわらず、「確率 P(A ∩ B) を求めてみよう」 などと平然と書いています。 A ∩ B などというものは考えられないにもかかわらず。 747 名前：１３２人目の素数さん mailto:age [2022/10/28(金) 10:11:13.31 ID:lqOqCRZy.net] このスレを見ていると 3流の国立や私立大の理系への考えが変わったわ。 「3流大でも入学後にちゃんと勉強して単位をとってたら それなりに出来るようになるんやなぁ」 って。 であるならば、入学試験の6科目の受験勉強、 あれは何だったんだろうな。 過剰な学力の訓練・要求に思えてきた。 だって入学後にちゃんと大学レベルの数学、解析学についていけるやん？ ち、ちなみに謙虚な神戸大卒 TOEIC700です…( ; ‘ω‘) ﾊｧﾊｧ 748 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 10:25:55.37 ID:7H6AX/lv.net] >>719 高校数学は変な縛りがあるんで執筆者も雑なのは分かってて書いてると思います この場合の全事象 U は積空間の U_1 × U_2 に 事象 A は A × U_2, 事象 B は U_1 × B に読み替えるべきですね 749 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 10:30:44.97 ID:jgM6IsNM.net] >>720 三流大学や四流大学と認定される大学の学生さんが、ちゃんと学べていないのは、 入試ができない人が学ぶことができないというよりもむしろ、 「三流や四流の自分が勉強しても仕方ない」という意識を持つからだろうね 実際、日本の学力テストが素質を測れるという根拠は存在しない これは日本の人材の損失で、少子化で更に人材が減っていく以上、三流や四流みたいな固定観念を撤廃していかない限り日本が他の国々に差をつけられていくのは必定だと思う 750 名前：１３２人目の素数さん mailto:age [2022/10/28(金) 11:40:23.68 ID:lqOqCRZy.net] >>722 一般入試組が受験オタク、学力厨という事実が 明るみになってきてますし 今はAO入試・指定校推薦が 入学者の半分近くっていう大学も多いですね。 (下手したら、学力の高いはずの人々が 大学の成績でAO・指定校などの学力の低めの人に負けている場合さえある) 751 名前：１３２人目の素数さん [2022/10/28(金) 11:57:16.81 ID:FpKcJleB.net] また部外者君か 752 名前：１３２人目の素数さん [2022/10/28(金) 12:02:15.89 ID:FpKcJleB.net] >>723 AOと推薦がどうしようもないのは2流3流大の場合 1流と4流では大して違いない ていうか４流では入試機能しないからな

---

---

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

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