2022-12-11

C#で組み合わせを求める

C# 算数プログラミング

いわゆる_nC_k

　「色違いの5個のボールが袋に入っている。その袋から3つ取り出す場合の組み合わせの数を求めよ」
という中学数学に出てきそうな問題を解くためのやつ。
表記としては₅C₃と書く。

計算

　₅C₃では次のようになる。

₅C₃ = (5×4×3)/(3×2×1) = 10

　_nC_k = _nC_n-k なので、計算量が少ない方を選べばいい。

できたもの

/// <summary>
/// 組み合わせの数を求める
/// </summary>
/// <param name="n">要素数</param>
/// <param name="k">選ぶ数</param>
/// <returns>nCk</returns>
public BigInteger Count(long n, long k)
{
    if (k > n - k) k = n - k;

    var numerator = new BigInteger(1);
    var denominator = new BigInteger(1);
    var tmp = 1L;

    for (int count = 1; count <= k; count++)
    {
        numerator *= n;
        n--;

        denominator *= tmp;
        tmp++;
    }

    return numerator / denominator;
}

なんでおっさんはすぐBigIneger使うん？

　答えがすぐに爆発するからやで。

Count(600, 25) = 110400461164029879580081326850533034570953024

　こんなふうに、ちょっと大きい数字を与えただけでintの範囲を軽く超えてくる。
もうBigInteger使うしかないでしょ。

組み合わせとは

ja.wikipedia.org

Combinationの語源

www.etymonline.com

組合せ数学 (岩波科学ライブラリー)

作者:ロビン・ウィルソン
岩波書店

Amazon

組合せ論の精選102問 (数学オリンピックへの道)

作者:アンドレースク,T.,フェング,Z.
朝倉書店

Amazon

ヴァン・リント&ウィルソン組合せ論上

丸善出版

Amazon

2022-12-09

C#で総乗を求める

C# プログラミング

　総乗を求めたかったので作った。

総乗とは

ja.wikipedia.org
　総和が全部の値を足し算するように、総乗は全部の値を掛け算する。
要はそれだけ。

例えば1から10までの総乗をPI(1,5)と表現する。
この場合、実際の計算は次のようになる。

PI(1,5) = 1×2×3×4×5 = 120

他にも、PI(5,12)だとこのようになる。

PI(5,12) = 5×6×7×8×9×10×11×12 = 19958400

さらに数列を突っ込んで総乗を求める場合もある。

できたもの

class MyMath
{
    /// <summary>
    /// 総乗
    /// </summary>
    /// <typeparam name="T">総乗に使う値の型</typeparam>
    /// <param name="start">開始する値</param>
    /// <param name="limit">上限値(含む)</param>
    /// <returns>startからlimitの総乗</returns>
    public T Product<T>(T start, T limit) where T : IComparable
    {
        if (start.CompareTo(limit) > 0) Swap<T>(ref start, ref limit);

        var p = start;
        for (var v = (dynamic)start + 1; v <= limit; v++) p *= v;

        return p;
    }

    /// <summary>
    /// 総乗(答えが大きくなりそうならこっち)
    /// </summary>
    /// <typeparam name="T">総乗に使う値の型</typeparam>
    /// <typeparam name="U">戻り値の型</typeparam>
    /// <param name="start">開始する値</param>
    /// <param name="limit">上限値(含む)</param>
    /// <returns>startからlimitの総乗</returns>
    public U Product<T, U>(T start, T limit)
    where T : IComparable
    {
        if (start.CompareTo(limit) > 0) Swap<T>(ref start, ref limit);

        var p = default(U);
        p = (dynamic)start;
        for (var v = (dynamic)start + 1; v <= limit; v++) p *= v;

        return p;
    }

    /// <summary>
    /// 総乗
    /// </summary>
    /// <typeparam name="T">引数の型</typeparam>
    /// <param name="nums">総乗する値の配列</param>
    /// <returns>配列内の総乗</returns>
    public T Product<T>(T[] nums)
    {
        return nums.Aggregate((result, current) => result * (dynamic?)current);
    }

    /// <summary>
    /// 総乗(大きくなりそうな場合)
    /// </summary>
    /// <typeparam name="T">引数の型</typeparam>
    /// <typeparam name="U">戻り値の型</typeparam>
    /// <param name="nums">総乗する値の配列</param>
    /// <returns>配列内の総乗</returns>
    public U Product<T, U>(T[] nums)
    {
        var e = default(U);
        e = (dynamic)1;
        foreach (var n in nums) e = e * (dynamic?)n;

        return e;
    }

    public void Swap<T>(ref T a, ref T b)
    {
        var tmp = a;
        a = b;
        b = tmp;
    }
}

実行結果1

var m = new MyMath();
Console.WriteLine($"PI(1, 100) = {m.Product<int, BigInteger>(1,100)}");

PI(1, 100) = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

実行結果2

var m = new MyMath();
int[] a = new int[] { 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25 };
Console.WriteLine($"PI(a) = {m.Product<int, BigInteger>(a)}");

PI(a) = 2635284526875

実行結果3

var m = new MyMath();
decimal[] a = new decimal[] { 1.1M, 2.2M, 3.3M, 4.4M, 5.5M, 6.6M, 7.7M, 8.8M, 9.9M };
Console.WriteLine($"PI(a) = {m.Product<decimal, decimal>(a)}");