C言語のきほん「組合せの数」

今回は、「組合せの数」を求めるプログラムである。

異なるn個の整数からr個の整数を取り出す組合せの数$_{n}C_{r}$を求める。

なお、$_{n}C_{r}$は、次のように定義される。↓

$_{n}C_{r} =$ $ _{n-1}C_{r-1} $ + $_{n-1}C_{r} $
ただし、$_{n}C_{0}=_{n}C_{n}=1$ 、 $ _{n}C_{1}=n$

なお、本プログラムは、Windows 11 Home（23H2）上で、 Visual Studio Code（1.87.2）を使用して作成し、gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0　でコンパイルしている。

C言語のインストールについてはこちらをご参照ください。↓

C言語をMacにインストールしよう

MacでC言語プログラミングの学びを始めよう。 WindowsパソコンだけじゃなくてMacでもプログラミング環境を整えてみる。使用したMacは下記のとおり。 使用マシンスペック ハードウェアの概要:機種名: MacBook Airプロセッサ...

my-studies.org

2022.06.06

C言語をパソコンにインストールしよう（Windows編）

なぜインストールが必要なのか Windowsパソコンを購入したあるいは、インストールした状態のままではC言語の開発環境はインストールされていない。ご自分でインストールする必要がある。C言語のテキストにはプログラムコードが掲載されているはずで...

my-studies.org

2022.05.26

組合せの数を求めるプログラム

//組合せの数を求めるプログラム

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

}

実行結果

異なるn個からr個の整数を取り出す組合せの数を求めます。
n:5
r:3
組合せの数は10です。

なお、念のため「keisan」サイトで検算してみた。

組合せ

異なる n個のものから r個を選ぶ組み合わせの総数 nCr を求めます。

keisan.casio.jp

（参考）新・解きながら学ぶC言語 第2版　柴田望洋 （監修・著）、 由梨かおる（著）SBクリエイティブ