Q&A
とりあえずアルゴリズム的にアプローチする方法と数学的に考える方法の二つを思いついたけれど, 何れにせよ組み合わせ論は必要ですな
課題
ランダムで数字が表示される機械があります。
1回につき1point、2point、もしくは3pointを出力します。
合計{N}point得るためには、何通りの組み合わせがあるか、プログラムを考えなさい。
例：合計{n}が1pointの場合、答は下記の1通りとなる。
1point
###例：合計{n}が2pointの場合、答は下記の2通りとなる。
1point,1point 2point
###例：合計{n}が3pointの場合、答は下記の4通りとなる。
1point,1point,1point 1point,2point 2point,1point 3point
###例：合計{n}が4pointの場合、答は下記の7通りとなる。
1point、1point、1point、1point 1point、1point、2point 1point、2point、1point 1point、3point 2point、1point、1point 2point、2point 3point、1point
組み合わせについて
#include <stdio.h> /*--- 異なるn個からr個の整数を取り出す組み合わせの数を返す ---*/ int combination(int n, int r) { if (r == 0 || r == n) return (1); else if (r == 1) return (n); return (combination(n - 1, r - 1) + combination(n - 1, r)); } int main(void) { int n, r; puts("異なるn個からr個の整数を取り出す組合せの数を求めます。"); printf("n："); scanf("%d", &n); printf("r："); scanf("%d", &r); printf("組合せの数は%dです。\n", combination(n, r)); return (0); }
０からコードを作るほど、まだ力がないので、ネットにあるコードを参考にしてプログラムを作ろうと思っていますが、
出力される数字が1or2or3という様に３つのパターンがあるところが今難しく、どういう風にプログラムにしようか考えています。
ご教授やご助言いただける方、いらっしゃったらよろしくお願いします。
軽くググって見た感じ、これは一般化できる公式が発見されていないようですね。それどころか、順序を考慮しない分割についても一般化できる公式がないようです（ https://ja.wikipedia.org/wiki/%E5%88%86%E5%89%B2%E6%95%B0 ）。整数マジかよって感じですが。
何通りかの数がわかればそれでいいんでしょうか？それぞれを具体的に書き出さないといけないのでしょうか？前者なら、maisumakunさんの解答のとおりで非常に簡単になります。
回答6件
0
ベストアンサー
ほぼ答えに近いですが、結果はトリボナッチ数列の一般項に相当します。
例えば、10ポイントが必要な場合、
- 最初に1ポイント獲得して、残り9ポイントを取りに行く
- 最初に2ポイント獲得して、残り8ポイントを取りに行く
- 最初に3ポイント獲得して、残り7ポイントを取りに行く
という流れなので、n≧4では、パターン数は（n-3のときのパターン数）+（n-2のときのパターン数）+（n-1のときのパターン数）となります。
数学的に一般項も計算できますが、いちばん簡単な計算法としては配列を用意して1から順に計算していくことです。
投稿2018/01/22 06:11
総合スコア145184
T7＝13のようですが、5pointのときは、
1+1+1+1+1
1+1+1+2
1+1+2+1
1+1+3
1+2+1+1
1+2+2
1+3+1
1+4
2+1+1+1
2+1+2
2+2+1
2+3
3+1+1
3+2
4+1
5
の16通りでは。
1回に4ポイント以上は取れないので、「1+4」「4+1」「5」の3つが抜けて13通りのはずです。
うわ、条件を誤読してました。「もしくは」だったのか……
maisumakunさん、Lhankor_Mhyさん、ありがとうございました。ハイレベルなやりとりに目が点になっていますが、私自身も数学をもう一度やり直して、いつかついていけるようになりたいです。。。皆さまとにかく凄すぎです。
0
順序つき分割、あるいは、結合、だそうですよ。
分割とは、例えば5という整数を4 + 1や2 + 2 + 1などと表す書き表し方のことをいい、実際に5の分割は、5,4 + 1,3 + 2,3 + 1 + 1,2 + 2 + 1,2 + 1 + 1 + 1,1 + 1 + 1 + 1 + 1の7通りある。分割を表す各正整数のことを和因子といい、ある分割の和因子の並びを入れ替えても同じ分割を表すものとする。従って、分割を表すときは、大きい和因子から小さい和因子へと並べることにする。それに対し、ある分割の和因子の並びを入れ替えたものを別の対象と考えた方がよいこともある。このように和因子の順序を考慮に入れた分割を結合という。例えば、分割で2 + 2 + 1としていたものは、結合では2 + 2 + 1,2 + 1 + 2,1 + 2 + 2の異なる3つの結合と見なす。
投稿2018/01/22 05:57
総合スコア36115
0
学校の宿題っぽいので、プログラムそのものを示すのはやめておきます。
おそらく、３＋１＋３と３＋３＋１は重複してはいけないのでしょうね？
ならば「3x+2y+1z=nにするようなx,y,zを列挙する」ととらえた方が楽にプログラムが書けると思います。問題の性質から3、２，１の順に個数を確定していった方が楽。
3重forで書けます。
３＋１＋３と３＋３＋１は別の答えとしてそれぞれ出力しろと言われたら、深さ優先探索的に再起呼び出しするのがプログラミングは楽そう。
投稿2018/01/22 05:49
総合スコア702
順番が違うものは別カウントのようです（3ポイント、4ポイントの場合を参照）。
おおそうですね。学校の課題ならそう効率が悪くても動けば合格になるでしょうから,素直に再帰でやるのがいいとおもいます。ていうか、それが説明が楽かな。
一番長い答えが1がn個の長さnだと事前に分かるので、対処しやすい。
再帰呼び出しに一票！
計算量の見積りには詳しくないのですが、素直に再帰で行う方法でも引数に応じて値をメモしておけば(いわゆるメモ化再帰)、漸化式で解くのとそう変わらない計算量になりそうですね。
...ただ、中身の処理が軽すぎるので、むしろ再帰呼び出しのコストが高くつきそうです。
3重もいらないかと。
3の個数、2の個数が確定すれば1の個数は自動的に確定するので。
あ、そうですね。１の個数を確定させるのを最後にするのがキモ
0
「何通りか」さえ数えられればいいのなら以下で。
例えば「10ポイント」で考える。
まずは13ポイントがそれぞれ何回か、その組み合わせを考える。3でループする。
3ポイントの回数は最大で[10/3]=3回。だから3ポイントの回数として0
仮に3ポイントが2回とする。残りは10-32=4ポイントで、これを1ポイントと2ポイントに割り振る。
2ポイントの回数は最大[4/2]=2回。2ポイントの回数として0~2でループ。
2ポイントを1回とすれば、残りは4-21=2ポイント。よって1ポイントは2回。
3ポイントが2回、2ポイントが1回、1ポイントが2回で、あとはこれの並び順の問題。
合計5回分の**同じものを含む順列**と考えれば、このパターンは
5!/(2!1!2!)=30通り。
これをループしながらカウントしていき、総和を取ればいい。
ただし階乗計算のオーバーフローに注意。
階乗が嫌なら5C2*3C1で。
投稿2018/01/22 15:14
総合スコア20651
0
とりあえず、シェル芸でやってみました。先頭のnに求めたい値を設定します。
bash
1$ n=5;for((i=1;i<=$n;i++));do echo -n 'echo ';jot -b"{1..3}" -s+ $i;done|sh|tr ' ' '\n'|xargs -I@ echo 'echo $((@)) @'|sh|grep "^$n "|sed -E -e's/^.+ (.+)$/\1/' -e's/+/point,/g' -e's/$/point/'|sort 21point,1point,1point,1point,1point 31point,1point,1point,2point 41point,1point,2point,1point 51point,1point,3point 61point,2point,1point,1point 71point,2point,2point 81point,3point,1point 92point,1point,1point,1point 102point,1point,2point 112point,2point,1point 122point,3point 133point,1point,1point 143point,2point
投稿2018/01/22 08:24
編集2018/01/22 08:28
総合スコア5737
あなたの回答
tips
プレビュー
