9桁の正の整数で左から3桁ずつの和、つまり 1桁目+2桁目+3桁目、 2桁目+3桁目+4桁目、 ..... ..... ...... ..... 7桁目+8桁目+9桁目
がそれぞれ6以下であるものは いくつあるでしょうか。
|
No.84236 - 2022/12/10(Sat) 19:12:14
| ☆ Re: 場合の数 / らすかる | | | 簡単に求められる方法が思いつかないので、とりあえず n(n≧3)桁目までの各連続3桁の和が6以下で n-1桁目の数字がp, n桁目の数字がq(0≦p≦6,0≦q≦6-p)であるものの個数をa(n,p,q)とすると a(1,p,q)=1(p=0かつq≧1), a(1,p,q)=0(その他) a(n+1,p,q)=Σ[k=0〜6-p-q]a(n,k,p) これに従って表を作っていくと n=1(↓p→q) 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 n=2 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 n=3 6 5 4 3 2 1 0 5 4 3 2 1 0 4 3 2 1 0 3 2 1 0 2 1 0 1 0 0 n=4 21 21 20 18 15 11 6 15 15 14 12 9 5 10 10 9 7 4 6 6 5 3 3 3 2 1 1 0 n=5 56 56 55 52 46 36 21 56 55 52 46 36 21 50 48 43 34 20 40 37 30 18 28 24 15 16 11 6 n=6 252 246 230 202 162 112 56 231 220 196 159 111 56 195 180 150 107 55 150 132 98 52 102 82 46 57 36 21 n=7 1008 987 930 828 678 483 252 896 860 778 646 466 246 720 674 576 426 230 520 468 361 202 328 273 162 168 112 56 n=8 3696 3640 3472 3144 2624 1904 1008 3374 3262 2989 2521 1847 987 2807 2645 2284 1708 930 2102 1900 1474 828 1374 1144 678 729 483 252 n=9 14334 14082 13353 11979 9877 7070 3696 13074 12591 11447 9547 6902 3640 10897 10219 8745 6461 3472 8201 7373 5665 3144 5401 4471 2624 2891 1904 1008 n=10 55806 54798 51907 46506 38305 27408 14334 50640 48736 44265 36892 26673 14082 41834 39210 33545 24800 13353 31131 27987 21526 11979 20251 16779 9877 10710 7070 3696 a(11,0,0)=55806+50640+41834+31131+20251+10710+3696=214068 というわけで答えは214068通りです。
|
No.84237 - 2022/12/10(Sat) 20:55:29 |
| ☆ Re: 場合の数 / GA | | | 難しい解答有り難うございました。 左から各桁をa,b,cなどとして 連立不等式に持ちこんでソフトを使って 解くことはできますでしょうか。
|
No.84238 - 2022/12/10(Sat) 21:56:18 |
| ☆ Re: 場合の数 / IT | | | プログラムで計算するなら単純に counter = 0
For a = 1 To 6 For b = 0 To 6 - a For c = 0 To 6 - a - b For d = 0 To 6 - b - c For e = 0 To 6 - c - d For f = 0 To 6 - d - e For g = 0 To 6 - e - f For h = 0 To 6 - f - g For i = 0 To 6 - g - h counter = counter + 1 Next Next Next Next Next Next Next Next Next
MsgBox counterで らすかるさんと同じ値になります。
最後の For は除去できます。
|
No.84239 - 2022/12/10(Sat) 22:35:49 |
| ☆ Re: 場合の数 / GA | | | わかりやすいプログラム有り難うございました。両氏に感謝です。
|
No.84240 - 2022/12/10(Sat) 23:07:49 |
| ☆ Re: 場合の数 / らすかる | | | 十数桁までならITさんのプログラムが最も簡単ですね。 それ以上になると時間がかかりすぎますので、 私が書いたような何かしらの工夫が必要になると思います。 ちなみにわかりにくかったと思いますので表の作り方を書きます。 例えばn=4の表は 21 21 20 18 15 11 6 15 15 14 12 9 5 10 10 9 7 4 6 6 5 3 3 3 2 1 1 0 となっていますが、これからn=5の表をなるべく簡単に作るには (1)行・列を反転する 21 15 10 6 3 1 0 21 15 10 6 3 1 20 14 9 5 2 18 12 7 3 15 9 4 11 5 6 (2)左端を除き、順に左の数を足していく 例えば1行目の21 15 10 6 3 1 0ならば 15に21を足して 21 36 10 6 3 1 0 10に36を足して 21 36 46 6 3 1 0 6に46を足して 21 36 46 52 3 1 0 3に52を足して 21 36 46 52 55 1 0 1に55を足して 21 36 46 52 55 56 0 0に56を足して 21 36 46 52 55 56 56 全部の行を同じように計算すると 21 36 46 52 55 56 56 21 36 46 52 55 56 20 34 43 48 50 18 30 37 40 15 24 28 11 16 6 (3)左右を反転する 56 56 55 52 46 36 21 56 55 52 46 36 21 50 48 43 34 20 40 37 30 18 28 24 15 16 11 6 これでn=5の表ができました。 n=1の初期状態を 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 として上の処理を順次行えば、何桁でも高速に計算できます。 しかも上の処理では一つの表を順次更新していくだけでよく、 複数の表を持つ必要もありません。 ただしnが大きいとき多倍長演算が必要です。 k桁のときのパターン数はn=k+2の表の左上端の値です。 上記の処理より、9桁,18桁,27桁,36桁,45桁,54桁の各値が 9: 214068 18: 40177233243 27: 7540463649658374 36: 1415202118478886214578 45: 265606614233948847492320132 54: 49849327246187261472795717801139 のようになることがわかります。
|
No.84241 - 2022/12/11(Sun) 08:58:54 |
| ☆ Re: 場合の数 / GA | | | No.84246 - 2022/12/12(Mon) 18:01:45 |
| ☆ Re: 場合の数 / GA | | | 追伸 お世話になっています。 初期状態の表の作り方がわかりません。 例えば問題を8桁の整数でひだりから 4桁ずつの和が5以下とした場合 表の初期状態はどうなるのでしょうか。 お疲れのところ心苦しいのですが かまわなければご教授ください。
|
No.84247 - 2022/12/12(Mon) 18:54:41 |
| ☆ Re: 場合の数 / らすかる | | | 最初の問題の初期状態の表の各数字の意味は 0 1 1 1 1 1 1 ← 最後の2桁が00〜06 0 0 0 0 0 0 ← 最後の2桁が10〜15 0 0 0 0 0 ← 最後の2桁が20〜24 0 0 0 0 ← 最後の2桁が30〜33 0 0 0 ← 最後の2桁が40〜42 0 0 ← 最後の2桁が50〜51 0 ← 最後の2桁が60 のようになっています。つまり3桁ずつの和の場合は 次の1桁が決まるためにはそれ以前の2桁の情報が必要なので 2桁の組合せであり得る場合を表にしています。 先頭桁の前に「0」を補うとあり得るのは01〜06であるため、 初期状態は上の表のようになります。
「4桁ずつの和」となると次の1桁が決まるためにはそれ以前の3桁が必要となり、 表が三次元になってしまいますので見やすい表で書き表すのは難しいですが、 あえて表すとしたら初期状態は (1段目) 0 1 1 1 1 1 ← 最後の3桁が000〜005 0 0 0 0 0 ← 最後の3桁が010〜014 0 0 0 0 ← 最後の3桁が020〜023 0 0 0 ← 最後の3桁が030〜032 0 0 ← 最後の3桁が040〜041 0 ← 最後の3桁が050 (2段目) 0 0 0 0 0 ← 最後の3桁が100〜104 0 0 0 0 ← 最後の3桁が110〜113 0 0 0 ← 最後の3桁が120〜122 0 0 ← 最後の3桁が130〜131 0 ← 最後の3桁が140 (3段目) 0 0 0 0 ← 最後の3桁が200〜203 0 0 0 ← 最後の3桁が210〜212 0 0 ← 最後の3桁が220〜221 0 ← 最後の3桁が230 (4段目) 0 0 0 ← 最後の3桁が300〜302 0 0 ← 最後の3桁が310〜311 0 ← 最後の3桁が320 (5段目) 0 0 ← 最後の3桁が400〜401 0 ← 最後の3桁が410 (6段目) 0 ← 最後の3桁が500 のようになります。これも前回と同様に表を機械的に処理することで 1桁増やしたときの表が作れますが、言葉で表すのは難しいですね。 ひとことで言うと、「行・列を反転する」の部分が 「行・列・段を段→列→行→段のように回転する」になります。 上の表で例を作ると大変なので3段に減らして回転を具体的に書くと、 (1段目) a b c d e f (2段目) g h i (3段目) j のとき回転結果は (1段目) a g j b h c (2段目) d i e (3段目) f のようになります。実際に試して確認してはいませんので 100%の自信はありませんが、多分合っているでしょう。
|
No.84249 - 2022/12/12(Mon) 21:59:19 |
| ☆ Re: 場合の数 / GA | | | 素晴らしい解答有り難うございました。 お手数をおかけしました。
|
No.84251 - 2022/12/12(Mon) 23:57:23 |
|