質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.03%

1,2,3を複数回出力し、合計nになるためのパターンの数を求めるプログラム。

解決済

回答 6

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 1,850
退会済みユーザー

退会済みユーザー

 課題

ランダムで数字が表示される機械があります。
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通りとなる。

1point1point1point1point
1point1point2point
1point2point1point
1point3point
2point1point1point
2point2point
3point1point

 組み合わせについて

#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);
}

0からコードを作るほど、まだ力がないので、ネットにあるコードを参考にしてプログラムを作ろうと思っていますが、
出力される数字が1or2or3という様に3つのパターンがあるところが今難しく、どういう風にプログラムにしようか考えています。
ご教授やご助言いただける方、いらっしゃったらよろしくお願いします。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • defghi1977

    2018/01/22 14:52

    とりあえずアルゴリズム的にアプローチする方法と数学的に考える方法の二つを思いついたけれど, 何れにせよ組み合わせ論は必要ですな

    キャンセル

  • Lhankor_Mhy

    2018/01/22 15:18

    軽くググって見た感じ、これは一般化できる公式が発見されていないようですね。それどころか、順序を考慮しない分割についても一般化できる公式がないようです( https://ja.wikipedia.org/wiki/%E5%88%86%E5%89%B2%E6%95%B0 )。整数マジかよって感じですが。

    キャンセル

  • a_saitoh

    2018/01/23 12:10

    何通りかの数がわかればそれでいいんでしょうか?それぞれを具体的に書き出さないといけないのでしょうか?前者なら、maisumakunさんの解答のとおりで非常に簡単になります。

    キャンセル

回答 6

checkベストアンサー

+9

ほぼ答えに近いですが、結果はトリボナッチ数列の一般項に相当します。

例えば、10ポイントが必要な場合、

  • 最初に1ポイント獲得して、残り9ポイントを取りに行く
  • 最初に2ポイント獲得して、残り8ポイントを取りに行く
  • 最初に3ポイント獲得して、残り7ポイントを取りに行く

という流れなので、n≧4では、パターン数は(n-3のときのパターン数)+(n-2のときのパターン数)+(n-1のときのパターン数)となります。

数学的に一般項も計算できますが、いちばん簡単な計算法としては配列を用意して1から順に計算していくことです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/22 15:29

    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通りでは。

    キャンセル

  • 2018/01/22 15:41

    1回に4ポイント以上は取れないので、「1+4」「4+1」「5」の3つが抜けて13通りのはずです。

    キャンセル

  • 2018/01/22 15:43

    うわ、条件を誤読してました。「もしくは」だったのか……

    キャンセル

  • 2018/01/26 16:40

    maisumakunさん、Lhankor_Mhyさん、ありがとうございました。ハイレベルなやりとりに目が点になっていますが、私自身も数学をもう一度やり直して、いつかついていけるようになりたいです。。。皆さまとにかく凄すぎです。

    キャンセル

+3

学校の宿題っぽいので、プログラムそのものを示すのはやめておきます。

おそらく、3+1+3と3+3+1は重複してはいけないのでしょうね?
ならば「3x+2y+1z=nにするようなx,y,zを列挙する」ととらえた方が楽にプログラムが書けると思います。問題の性質から3、2,1の順に個数を確定していった方が楽。
3重forで書けます。

3+1+3と3+3+1は別の答えとしてそれぞれ出力しろと言われたら、深さ優先探索的に再起呼び出しするのがプログラミングは楽そう。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/22 16:18

    計算量の見積りには詳しくないのですが、素直に再帰で行う方法でも引数に応じて値をメモしておけば(いわゆるメモ化再帰)、漸化式で解くのとそう変わらない計算量になりそうですね。

    ...ただ、中身の処理が軽すぎるので、むしろ再帰呼び出しのコストが高くつきそうです。

    キャンセル

  • 2018/01/22 22:25

    3重もいらないかと。
    3の個数、2の個数が確定すれば1の個数は自動的に確定するので。

    キャンセル

  • 2018/01/23 10:13

    あ、そうですね。1の個数を確定させるのを最後にするのがキモ

    キャンセル

+3

順序つき分割、あるいは、結合、だそうですよ。

分割とは、例えば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 14:58

    あれ? 質問が変わってる……

    キャンセル

+2

組み合わせです。
組合せ (数学)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/22 14:39

    Zuishinさん、ありがとうございます。高校の頃やりました。なかなか覚えてないので調べつつ頑張ってみますね!

    キャンセル

+2

とりあえず、シェル芸でやってみました。先頭のnに求めたい値を設定します。

$ 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
1point,1point,1point,1point,1point
1point,1point,1point,2point
1point,1point,2point,1point
1point,1point,3point
1point,2point,1point,1point
1point,2point,2point
1point,3point,1point
2point,1point,1point,1point
2point,1point,2point
2point,2point,1point
2point,3point
3point,1point,1point
3point,2point

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+2

「何通りか」さえ数えられればいいのなら以下で。

例えば「10ポイント」で考える。
まずは1~3ポイントがそれぞれ何回か、その組み合わせを考える。
3ポイントの回数は最大で[10/3]=3回。だから3ポイントの回数として0~3でループする。
仮に3ポイントが2回とする。残りは10-3*2=4ポイントで、これを1ポイントと2ポイントに割り振る。
2ポイントの回数は最大[4/2]=2回。2ポイントの回数として0~2でループ。
2ポイントを1回とすれば、残りは4-2*1=2ポイント。よって1ポイントは2回。

3ポイントが2回、2ポイントが1回、1ポイントが2回で、あとはこれの並び順の問題。
合計5回分の同じものを含む順列と考えれば、このパターンは
5!/(2!1!2!)=30通り。
これをループしながらカウントしていき、総和を取ればいい。
ただし階乗計算のオーバーフローに注意。
階乗が嫌なら5C2*3C1で。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.03%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る