数学＠ふたば保管庫 [戻る]
|
>いつまでたっても終わらない いいえ終わりますバーカ |
|
集合だから当然なんだけと念のため補足 ・同じ数字は使えない（96+2+2など） ・順不同（99+1と1+99は同じ） |
|
190569292 |
|
加算のみは条件にしていないな |
|
444793 |
|
つまり、足して１００になる数字の組み合わせが全部で 何通りあるかだろ？ たとえば １＋２＋３＋４＋５・・・ これで数字を並べられる最大数がわかってしまえば、 どこか１か所省いたパターンが最大数-1 どこか２か所省いたパターンが最大数-2 という感じで最大数-2回？くらい繰り返せばいいのだから、 答えはちょっと考えればすぐわかるな。 |
|
これ？ https://oeis.org/A000009 |
|
1+2+3+…+14=105だから 最大並べられるのは13個だが 例えば5個の数の総和が100になるパターンを探すのも大変な気がする |
|
>No.94649 どうしてそうなった？ >No.94651 正解 >No.94652 「１つ１つ数えているといつまでたっても終わらない」って言ったでしょ >No.94658 これと同じようだけど、ここで解説されていることは俺には理解できないorz |
|
N集合の個数 11 249 3784 45952 525337 665827 7108869 8116263 979403 1033401 117972 12905 1330 合計444793 |
|
N, 集合の個数 1, 1 2, 49 3, 784 4, 5952 5, 25337 6, 65827 7, 108869 8, 116263 9, 79403 10, 33401 11, 7972 12, 905 13, 30 合計, 444793※タブが死んでた |
|
うまい求め方でもあるの？ 普通にやるとめちゃくちゃ面倒くさいんだが |
|
こういうのは数の少ない方から順に攻めて それらの結果をさらに武器とするのだよ 要素の合計がnの場合の集合をS(n)として S(1)、S(2)、S(3)・・・と順に考えてみたまへ 早漏なとっしーならばS(10)、遅漏なキミたちでもS(20)もやれば規則性とそれを利用した戦術が見えてくるであ漏 |
|
>190569292 これは重複ありの時の答えだな |
|
ざっくり解説 F(a,b)を「要素が1以上b以下の整数で、要素の合計がaとなる組み合わせの数」とすると、この問題はF(100,100)と書ける。 F(a,b)はbを使うときと使わないときの2パターンあるので、F(a,b)=F(a-b,b-1)+F(a,b-1) a>(b*(b+1))/2ならばF(a,b)=0、a<bならばF(a,b)=F(a,a)、F(a,a)=F(a,a-1)+1 あとはF(1,1)=1、F(2,1)=0、F(2,2)=1、F(3,1)=0、F(3,2)=F(1,1)+F(3,1)=1、F(3,3)=F(3,2)+1=2･･･ と小さい数字から攻めれば5000回くらいの計算でF(100,100)が求められる。 ちなみにF(1000,1000)=8635565795744155161506。1つずつ集合を求めるとスパコン使っても無理。 しかしこの手法なら普通のPCで数秒で解ける。 |
|
プログラムで解けてこと？ |