[C言語] 組合せの数(nCr)を求めるプログラムの作成方法

#include <stdio.h>
// 階乗を計算する再帰関数
int factorial(int n) {
    if (n == 0) {
        return 1; // 0! は 1
    }
    return n * factorial(n - 1); // n! = n * (n-1)!
}
int main() {
    int num = 5;
    printf("%dの階乗は %d です。\n", num, factorial(num));
    return 0;
}

5の階乗は 120 です。

#include <stdio.h>
// 階乗を計算するループ関数
int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i; // result に i を掛ける
    }
    return result; // 階乗の結果を返す
}
int main() {
    int num = 5;
    printf("%dの階乗は %d です。\n", num, factorial(num));
    return 0;
}

5の階乗は 120 です。

#include <stdio.h>
#define MAX 100
// パスカルの三角形を生成する関数
void generatePascalTriangle(int triangle[MAX][MAX], int n) {
    for (int i = 0; i < n; i++) {
        triangle[i][0] = 1; // 各行の最初の要素は 1
        triangle[i][i] = 1; // 各行の最後の要素も 1
        for (int j = 1; j < i; j++) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]; // 上の2つの要素の和
        }
    }
}
int main() {
    int n = 5;
    int triangle[MAX][MAX];
    generatePascalTriangle(triangle, n);
    // 結果を表示
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            printf("%d ", triangle[i][j]);
        }
        printf("\n");
    }
    return 0;
}

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1

#include <stdio.h>
#define MAX 100
int memo[MAX][MAX]; // メモ化用の配列
// 組合せの数を計算する関数
int nCr(int n, int r) {
    if (r == 0 || r == n) {
        return 1; // nC0 または nCn は 1
    }
    if (memo[n][r] != -1) {
        return memo[n][r]; // 計算済みの結果を返す
    }
    // 組合せの数を再帰的に計算
    memo[n][r] = nCr(n - 1, r - 1) + nCr(n - 1, r);
    return memo[n][r];
}
int main() {
    int n = 5, r = 2;
    // メモ化用の配列を初期化
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            memo[i][j] = -1; // 未計算の状態を示す
        }
    }
    printf("%dC%d は %d です。\n", n, r, nCr(n, r));
    return 0;
}

5C2 は 10 です。

#include <stdio.h>
// 階乗を計算する関数
int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i; // result に i を掛ける
    }
    return result; // 階乗の結果を返す
}
// 組合せの数を計算する関数
int nCr(int n, int r) {
    return factorial(n) / (factorial(r) * factorial(n - r)); // nCr の計算
}
int main() {
    int n, r;
    printf("n と r の値を入力してください (n >= r): ");
    scanf("%d %d", &n, &r);
    printf("%dC%d は %d です。\n", n, r, nCr(n, r));
    return 0;
}

n と r の値を入力してください (n >= r): 5 2
5C2 は 10 です。

#include <stdio.h>
#define MAX 100
// パスカルの三角形を生成する関数
void generatePascalTriangle(int triangle[MAX][MAX], int n) {
    for (int i = 0; i < n; i++) {
        triangle[i][0] = 1; // 各行の最初の要素は 1
        triangle[i][i] = 1; // 各行の最後の要素も 1
        for (int j = 1; j < i; j++) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]; // 上の2つの要素の和
        }
    }
}
// 組合せの数を取得する関数
int nCr(int n, int r, int triangle[MAX][MAX]) {
    return triangle[n][r]; // パスカルの三角形から nCr を取得
}
int main() {
    int n = 5;
    int triangle[MAX][MAX];
    generatePascalTriangle(triangle, n + 1); // n+1 行の三角形を生成
    int r;
    printf("r の値を入力してください (r <= %d): ", n);
    scanf("%d", &r);
    printf("%dC%d は %d です。\n", n, r, nCr(n, r, triangle));
    return 0;
}

r の値を入力してください (r <= 5): 2
5C2 は 10 です。

#include <stdio.h>
#define MAX 100
int memo[MAX][MAX]; // メモ化用の配列
// 組合せの数を計算する関数
int nCr(int n, int r) {
    if (r == 0 || r == n) {
        return 1; // nC0 または nCn は 1
    }
    if (memo[n][r] != -1) {
        return memo[n][r]; // 計算済みの結果を返す
    }
    // 組合せの数を再帰的に計算
    memo[n][r] = nCr(n - 1, r - 1) + nCr(n - 1, r);
    return memo[n][r];
}
int main() {
    int n, r;
    // メモ化用の配列を初期化
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            memo[i][j] = -1; // 未計算の状態を示す
        }
    }
    printf("n と r の値を入力してください (n >= r): ");
    scanf("%d %d", &n, &r);
    printf("%dC%d は %d です。\n", n, r, nCr(n, r));
    return 0;
}

n と r の値を入力してください (n >= r): 5 2
5C2 は 10 です。