大学学部レベル質問スレ 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/ 641 名前：１３２人目の素数さん [2022/10/17(月) 16:33:41.35 ID:E3JR+M03.net] もっと分かりやすく書き直しました： 命題2.4： 始点 s から各頂点へ最短路が存在すると仮定する。このとき、 s を根とする 有向全域木 T が存在して、 T における s から頂点 v への有向路は、 s から 頂点 v への最短路となっている。 証明： 始点 s から各頂点 v への最短路（の枝集合）を P_v とし、 T = ∪_{v ∈ V} P_v とおく。 定理2.3と命題2.2より、 P_v は単純有向路としてよい。 T の要素数がちょうど n - 1 であれば、 これは有向全域木であり、各頂点への最短路を含む。一方、 T の要素数が n 以上の場合は、 以下の手順で最短路を繰り返し修正することにより、所望の有向全域木を求めることができる。 T の要素数が n 以上と仮定する。このとき、ある頂点 v_* ∈ V - {s} が存在して、 T の中には v_* に向かう枝が2つ以上ある。 … v_* に向かう枝が2つ以上あることの証明ですが、どのような証明が典型的なものと考えられますか？ 証明： T を無向グラフと考えたとき、 T は連結であり、 #T = n だから無向閉路が存在する。 仮に、上の v_* が存在しないと仮定する。 v を上の無向閉路上の任意の頂点とする。 T の定義により、 T の中には v へ向かう枝が存在するが、 仮定により、そのような枝は唯一つしか存在しない。ゆえに、この無向閉路を有向グラフとして考えた とき、有向閉路である。この有向閉路を C とする。 T の作り方から s に向かう枝は存在しないから、 s は C 上にはない。 T の作り方から、 s から v への有向路 P が存在する。 s は C 上にはなく、 v は C 上にあることに注意する。 P 上の頂点で最初に C 上の頂点ともなる頂点を w とする。 w は s とは異なるから、 P 上には、 w の直前の頂点 u が存在する。u は w についての仮定から、 C 上の頂点ではない。 w は C 上の頂点であるから、 w へ向かう C 上の枝が存在する。 以上から、 w へ向かう少なくとも2つ以上の枝が存在することになる。 これは矛盾である。 642 名前：１３２人目の素数さん [2022/10/17(月) 19:16:34.13 ID:uCeLdhKm.net] >>615 君に聞いたんじゃ無いけど？ 分かんないなら口出さないでね 643 名前：１３２人目の素数さん mailto:sage [2022/10/17(月) 19:17:42.47 ID:xXilSQkW.net] だな 644 名前：１３２人目の素数さん mailto:sage [2022/10/21(金) 19:20:50.27 ID:SO5fgyTN.net] 微分積分の教科書で最初の数章に必ずある「実数と連続」や「関数」 などをより詳しく学びたい場合はどういうジャンルの本を学べばいいんですか？ 「微分積分」というジャンルではないですよね？ でも「実数、連続」みたいなジャンルのコーナーは書籍に存在しないし、総当たりで探しても全く見つかりません 645 名前：１３２人目の素数さん [2022/10/21(金) 19:22:52.38 ID:f5ITm ] [ここ壊れてます] 646 名前：dZ2.net mailto: 数学基礎論とかどうでしょう 実数とか関数の話ではないですけど、実数とか関数とか、普通の微積に載ってるレベルで満足できないあなたは好きそうなトピックだと思いますよ [] [ここ壊れてます] 647 名前：１３２人目の素数さん [2022/10/21(金) 19:25:59.42 ID:POBo4qaZ.net] >>622 よく分からないからもっと詳しい説明が書いてある本を探しているということですか？ 648 名前：１３２人目の素数さん [2022/10/21(金) 19:39:20.80 ID:GFb/PGdE.net] >>622 descriptive set theoryで検索したら貴方好みのページが見つかるかも 649 名前：１３２人目の素数さん mailto:sage [2022/10/21(金) 19:53:40.42 ID:T0X1VZyu.net] そんなに突っ込んだ話じゃなくちょっと詳しくやりたい程度なら 東大出版の「数学の基礎」あたりで十分かと 650 名前：１３２人目の素数さん mailto:sage [2022/10/21(金) 20:08:39.09 ID:ScNOTOVp.net] 連続性なら「ホモトピー」だろ 651 名前：１３２人目の素数さん mailto:sage [2022/10/21(金) 20:15:35.47 ID:ScNOTOVp.net] テレビ版旧エヴァの最終回は ホモトピー代数とかのニワカが拘束力学系の解析力学をゲージ理論方面から眺めたわかってんだかわかってないんだかな議論みたく見える。 源平討魔伝のエンディングの「神は死んだ、悪魔は去った」の神と名字が被る深谷賢治あたりの同時代感がある論説記事にテーマが近く感じる。 まあ違うナムコのDDS2のエンディング前に「プログラムドバイナカジマ」を確認できるエビラの人と同時期両看板なイメージだが。 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) で出力する方法を述べよ。

---

---

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

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