2015年10月11日日曜日

累乗和の公式をプログラムで導出してみる(分数編)[C#]

 こっちのプログラムに,こっちで実装したFractionクラスを適用してみる。と言っても一昨日のやつのdoubleをFractionに変えてちょこっと調整しただけだけれども。

 ソースコードの前に実行結果を出しておきます。
 一乗和の公式:(1/2)*n^1+(1/2)*n^2
 二乗和の公式:(1/6)*n^1+(1/2)*n^2+(1/3)*n^3
 三乗和の公式:(0/1)*n^1+(1/4)*n^2+(1/2)*n^3+(1/4)*n^4
 四乗和の公式:(-1/30)*n^1+(0/1)*n^2+(1/3)*n^3+(1/2)*n^4+(1/5)*n^5
 五乗和の公式:(0/1)*n^1+(-1/12)*n^2+(0/1)*n^3+(5/12)*n^4+(1/2)*n^5+(1/6)*n^6
 六乗和の公式:(1/42)*n^1+(0/1)*n^2+(-1/6)*n^3+(0/1)*n^4+(1/2)*n^5+(1/2)*n^6+(1/7)*n^7
 七乗和の公式:(0/1)*n^1+(1/12)*n^2+(0/1)*n^3+(-7/24)*n^4+(0/1)*n^5+(7/12)*n^6+(1/2)*n^7+(1/8)*n^8
 八乗和の公式:出力はされるものの,間違っている。オーバーフローしてるっぽい。
 九乗和の公式:例外が発生する

 本当は100乗和の公式とか出してみたかったんだけれどなぁ。残念。int型は2^31-1までしか扱えないから,おそらくそのせい。BigInteger使うのもありかもしれないけれど,それをやるのはまた今度かな。

 ソースコード。昨日のFractionクラスは省略しています。必ず追加してくださいね。
using System;

class Program
{
    static void Main()
    {
        Console.WriteLine("何乗和の公式を求めますか?");
        var N = int.Parse(Console.ReadLine()) + 1;
        // 係数を求める連立方程式の拡大係数行列を作る
        var formula = MakeFormula(N);
        // 連立方程式をガウス消去法で計算
        Solve(formula, N);
        // 結果を表示
        Show(formula, N);
    }

    // 連立方程式を解くメソッド
    static void Solve(Fraction[,] formula, int N)
    {
        Fraction temp;

        // ガウス消去法

        // 前進消去
        for (int i = 0; i < N; i++)
        {
            // 対角対角成分をを1にする
            temp = formula[i, i];
            for (int j = 0; j < N + 1; j++)
                formula[i, j] /= temp;

            // i+1行以降のi列目を0にする
            for (int j = i + 1; j < N; j++)
            {
                temp = formula[j, i];
                for (int k = 0; k < N + 1; k++)
                    formula[j, k] -= temp * formula[i, k];
            }
        }

        // 後進消去
        for (int i = N - 1; i >= 0; i--)
        {
            // 対角成分以外を0にする
            for (int j = i - 1; j >= 0; j--)
            {
                formula[j, N] -= formula[j, i] * formula[i, N];
                formula[j, i] = 0;
            }
        }
    }

    // 累乗和の公式を表示するメソッド
    static void Show(Fraction[,] d, int N)
    {
        Console.WriteLine("{0}乗和の公式は……", N - 1);
        for (int i = 0; i < N; i++)
        {
            Console.Write("({0})*n^{1}", d[i, N], i + 1);
            if (i + 1 < N)
                Console.Write("+");
        }
        Console.WriteLine();
    }

    // 累乗和の公式を求める連立方程式の拡大係数行列を作るメソッド
    static Fraction[,] MakeFormula(int N)
    {
        var ret = new Fraction[N, N + 1];
        var sum = 0;

        for (int i = 0; i < N; i++)
        {
            // 係数部分を作る
            for (int j = 0; j < N; j++)
                ret[i, j] = (int)(Math.Pow(i + 1, j + 1));

            // 答えの部分を作る
            sum = sum + (int)(Math.Pow(i + 1, N - 1));
            ret[i, N] = sum;
        }

        return ret;
    }
}

 ソースコードほぼ同じじゃねーか。ページ数稼ぎかよ,とは言わないで。

追記:
 255乗和の公式のような,任意のべき乗和を求めるプログラムが完成しました→BigIntegerを使って累乗和の公式を計算[C#]

分数を扱うFractionクラスの実装[C#]

 昨日作った累乗和の公式を求めるプログラムでは,分数を扱えなかったのでdouble型で実装した。今日は分数のクラスを定義したのでソースコードを貼っておく。

 基本的なオペレーターは定義したけれども足りないとか間違っているとかあるかもしれないので指摘or温かい目でご覧ください。

 だけどソースコード長い。GitHubとか始めたほうがいいかもしれんな……。
using System;

class Fraction
{
    /// <summary>
    /// 分子
    /// </summary>
    public int Upper
    {
        get { return _Upper; }
        set { this._Upper = value; CheckFraction(); }
    }
    /// <summary>
    /// 分母
    /// </summary>
    public int Lower
    {
        get { return _Lower; }
        set { this._Lower = value; CheckFraction(); }
    }
    /// <summary>
    /// 分子の値を格納する変数
    /// </summary>
    private int _Upper;
    /// <summary>
    /// 分母の値を格納する変数
    /// </summary>
    private int _Lower;

    public Fraction(int Upper, int Lower)
    {
        Assignment(Upper, Lower);
    }
    public Fraction(int n)
    {
        Assignment(n, 1);
    }
    public Fraction(Fraction f)
    {
        Assignment(f.Upper, f.Lower);
    }

    /// <summary>
    /// double型に変換するメソッド
    /// </summary>
    /// <returns>double型に変換した値</returns>
    public double ToDouble()
    {
        return 1.0 * Upper / Lower;
    }

    /// <summary>
    /// float型に変換するメソッド
    /// </summary>
    /// <returns>float型に変換した値</returns>
    public float ToFloat()
    {
        return 1.0f * Upper / Lower;
    }

    /// <summary>
    /// 約分や分母が0などのミスが無いか確認するメソッド
    /// </summary>
    private void CheckFraction()
    {
        int u = _Upper;
        int l = _Lower;
        int temp;
        bool sign;


        if (l == 0)
        {
            // 分母が0なのでゼロ除算の例外をぶん投げる
            throw new DivideByZeroException();
        }
        else if (u == 0)
        {
            // 分母が0ならばこうする
            _Upper = 0;
            _Lower = 1;
        }
        else
        {
            // 分数の値が負ならsign = true となる
            sign = l * u < 0;
            // とりあえずl,uを正にする(余りの計算をするため)
            l = Math.Abs(l);
            u = Math.Abs(u);

            // 常にu <= lとなるようにする
            if (u > l)
            {
                temp = u;
                u = l;
                l = temp;
            }

            // ユークリッドの互除法
            while (l % u != 0)
            {
                temp = l % u;
                l = u;
                u = temp;
            }

            // 約分
            _Upper = Math.Abs(_Upper)/u;
            _Lower = Math.Abs(_Lower)/u;

            // 正負を直す
            if (sign)
                _Upper = -_Upper;
        }
    }

    /// <summary>
    /// クラス内で代入を行うメソッド(ただしCheckFractonから呼んではならない)
    /// </summary>
    /// <param name="Upper">分母</param>
    /// <param name="Lower">分子</param>
    private void Assignment(int Upper, int Lower)
    {
        this._Upper = Upper;
        this._Lower = Lower;
        CheckFraction();
    }

    public static Fraction operator +(Fraction left, Fraction right)
    {
        int l = left.Lower * right.Lower;
        int u = left.Upper * right.Lower + right.Upper * left.Lower;

        return new Fraction(u, l);
    }

    public static Fraction operator -(Fraction left, Fraction right)
    {
        right.Upper = -right.Upper;

        return left + right;
    }

    public static Fraction operator *(Fraction left, Fraction right)
    {
        int l = left.Lower * right.Lower;
        int u = left.Upper * right.Upper;

        return new Fraction(u, l);
    }

    public static Fraction operator /(Fraction left, Fraction right)
    {
        // 逆数にする(0除算ならここで例外が発生する)
        right = new Fraction(right.Lower, right.Upper);
        return right * left;
    }
    public static Fraction operator /(Fraction f, int n)
    {
        return new Fraction(f.Upper, f.Lower * n);
    }

    public static Fraction operator *(Fraction f, int n)
    {
        return new Fraction(f.Upper * n, f.Lower);
    }
    
    public static implicit operator Fraction(int n)
    {
        return new Fraction(n);
    }

    public static bool operator <(Fraction left, Fraction right)
    {
        return left.ToDouble() < right.ToDouble();
    }

    public static bool operator >(Fraction left, Fraction right)
    {
        return left.ToDouble() > right.ToDouble();
    }

    public static bool operator <=(Fraction left, Fraction right)
    {
        return left.ToDouble() <= right.ToDouble();
    }

    public static bool operator >=(Fraction left, Fraction right)
    {
        return left.ToDouble() >= right.ToDouble();
    }

    public static implicit operator double (Fraction f)
    {
        return f.ToDouble();
    }

    public static implicit operator float (Fraction f)
    {
        return f.ToFloat();
    }

    public static bool operator ==(Fraction left, Fraction right)
    {
        if (left.Upper == null || right.Upper == null)
            return false;
        return left.Upper == right.Upper && left.Lower == right.Lower;
    }

    public static bool operator !=(Fraction left, Fraction right)
    {
        return !(left == right);
    }

    public override bool Equals(object obj)
    {
        if (obj == null || this.GetType() != obj.GetType())
            return false;

        return (this == (Fraction)obj);
    }

    public override int GetHashCode()
    {
        return this.Upper * this.Lower;
    }

    public override string ToString()
    {
        return String.Format("{0}/{1}", this.Upper, this.Lower);
    }
}

 サンプルコードはまた今度。

追記:
このプログラムを使って累乗和の公式を導出しました→累乗和の公式をプログラムで導出してみる(分数編)