トップページに戻る    次のC#のサンプルへ    前のC#のサンプルへ

Cマガ電脳クラブ(第096回) +,−,×,÷,or nothing

問題

1 2 3 4 5 6 7 8 9 = N
この1〜9のすき間(8か所)に、+、−、×、÷のどれかひとつを入れる。何も入れなくてもよい。
たとえばN=100の場合、これを満たす式は、
 123+45-67+8-9=100
 1+23-4+56÷7+8×9=100
など、全部で101通り作れる。

では、もっとも多くの式が作れるのは、Nがいくつのときか。
なお、Nは1以上の整数とし、また、カッコは使わないものとする。


ソース

using System;
using System.Collections.Generic;
using System.Linq;

internal class CKabunSuu
{
    private long mBunshi; //分子
    private long mBunbo; //分母

    //コンストラクタ (値指定)
    internal CKabunSuu(long pBunshi, long pBunbo)
    {
        mBunshi = pBunshi;
        mBunbo = pBunbo;
    }

    //コンストラクタ (インスタンス指定)
    internal CKabunSuu(CKabunSuu pIns)
    {
        mBunshi = pIns.mBunshi;
        mBunbo = pIns.mBunbo;
    }

    //加算用メソッド (インスタンス指定)
    internal void Add(CKabunSuu pIns)
    {
        long SavedBunbo = mBunbo; //通分する前の分母

        //通分してから、加算
        mBunbo *= pIns.mBunbo;
        mBunshi = this.mBunshi * pIns.mBunbo + pIns.mBunshi * SavedBunbo;
        Yakubun();
    }

    //減算用メソッド (インスタンス指定)
    internal void Subtract(CKabunSuu pIns)
    {
        Add(new CKabunSuu(-pIns.mBunshi, pIns.mBunbo));
    }

    //乗算用メソッド (インスタンス指定)
    internal void Prod(CKabunSuu pIns)
    {
        this.mBunshi *= pIns.mBunshi;
        this.mBunbo *= pIns.mBunbo;
        Yakubun();
    }

    //除算用メソッド (インスタンス指定)
    internal void Div(CKabunSuu pIns)
    {
        this.mBunshi *= pIns.mBunbo;
        this.mBunbo *= pIns.mBunshi;
        Yakubun();
    }

    //約分
    private void Yakubun()
    {
        if (mBunshi == 0) return;

        long GCD = DeriveGCD(mBunshi, mBunbo);
        if (GCD == 1) return;
        mBunshi /= GCD;
        mBunbo /= GCD;
    }

    //ユークリッドの互除法で2数の最大公約数を求める
    private long DeriveGCD(long pVal1, long pVal2)
    {
        pVal1 = Math.Abs(pVal1);
        pVal2 = Math.Abs(pVal2);

        long WarareruKazu = Math.Max(pVal1, pVal2);
        long WaruKazu = Math.Min(pVal1, pVal2);

        while (true) {
            long Amari = WarareruKazu % WaruKazu;
            if (Amari == 0) return WaruKazu;
            WarareruKazu = WaruKazu;
            WaruKazu = Amari;
        }
    }

    //仮分数の値を返す
    internal decimal DecimalValue
    {
        get { return (decimal)mBunshi / mBunbo; }
    }

    //仮分数が整数か返す
    internal bool IsSeisuu()
    {
        return mBunbo == 1;
    }
}

class Program
{
    static void Main()
    {
        var SuusikiList = new List<string>();

        var stk = new Stack<string>();
        stk.Push("1□2□3□4□5□6□7□8□9");

        while (stk.Count > 0) {
            string Popped = stk.Pop();

            int Ind = Popped.IndexOf('□');
            if (Ind == -1) {
                SuusikiList.Add(Popped);
                continue;
            }

            string wkStr = Popped.Remove(Ind, 1);
            stk.Push(wkStr);
            stk.Push(wkStr.Insert(Ind, "+"));
            stk.Push(wkStr.Insert(Ind, "-"));
            stk.Push(wkStr.Insert(Ind, "*"));
            stk.Push(wkStr.Insert(Ind, "/"));
        }

        var CntDict = new Dictionary<decimal, int>();

        foreach (string EachStr in SuusikiList) {
            decimal DecimalValue; bool IsSeisuu;
            CalcFromRPN(ToRPN(EachStr), out DecimalValue, out IsSeisuu);

            //1以上の整数でなければ不適
            if (IsSeisuu == false) continue;
            if (DecimalValue <= 0) continue;

            if (CntDict.ContainsKey(DecimalValue))
                CntDict[DecimalValue]++;
            else CntDict[DecimalValue] = 1;
        }
        foreach (var EachPair in CntDict.OrderBy(X => X.Value).ThenBy(X => X.Key)) {
            Console.WriteLine("結果が{0}になるのは{1}通り",
                EachPair.Key, EachPair.Value);
        }
    }

    //数式を逆ポーランド記法にした配列を返す
    static string[] ToRPN(string pTargetStr)
    {
        var stk = new Stack<string>();
        var WillReturn = new List<string>();

        string[] wkStrArr = MakeNumAndExpArr(pTargetStr);
        foreach (string EachStr in wkStrArr) {
            if (EachStr == "+" || EachStr == "-" || EachStr == "*" || EachStr == "/") {
                int Priority = DerivePriority(EachStr);

                while (stk.Count > 0 && Priority <= DerivePriority(stk.Peek())) {
                    WillReturn.Add(stk.Pop());
                }
                stk.Push(EachStr);
            }
            else WillReturn.Add(EachStr);
        }
        while (stk.Count > 0) WillReturn.Add(stk.Pop());
        return WillReturn.ToArray();
    }

    //数式から数値と演算子の配列を作成
    static string[] MakeNumAndExpArr(string pTargetStr)
    {
        var WillReturn = new List<string>();
        var sb = new System.Text.StringBuilder();

        foreach (Char EachChar in pTargetStr) {
            if (EachChar == '+' || EachChar == '-' || EachChar == '*' || EachChar == '/') {
                WillReturn.Add(sb.ToString()); sb.Length = 0;
                WillReturn.Add(EachChar.ToString());
            }
            else sb.Append(EachChar);
        }
        WillReturn.Add(sb.ToString());
        return WillReturn.ToArray();
    }

    //演算子のプライオリティを返す
    static int DerivePriority(string pOperator)
    {
        if (pOperator == "+") return 1;
        if (pOperator == "-") return 1;
        if (pOperator == "*") return 2;
        if (pOperator == "/") return 3;
        return 0;
    }

    //逆ポーランド記法のListの計算結果を返す
    static void CalcFromRPN(string[] pRPNArr, out decimal pDecimalValue, out bool pIsSeisuu)
    {
        var stk = new Stack<CKabunSuu>();

        foreach (string EachStr in pRPNArr) {
            if (EachStr == "+" || EachStr == "-" || EachStr == "*" || EachStr == "/") {
                CKabunSuu exp2 = stk.Pop(); //exp2は中身を変更しないので参照でOK
                CKabunSuu exp1 = new CKabunSuu(stk.Pop());
                if (EachStr == "+") { exp1.Add(exp2); stk.Push(exp1); }
                if (EachStr == "-") { exp1.Subtract(exp2); stk.Push(exp1); }
                if (EachStr == "*") { exp1.Prod(exp2); stk.Push(exp1); }
                if (EachStr == "/") { exp1.Div(exp2); stk.Push(exp1); }
                continue;
            }
            stk.Push(new CKabunSuu(long.Parse(EachStr), 1));
        }
        CKabunSuu ResultKabunSuu = stk.Pop();
        pDecimalValue = ResultKabunSuu.DecimalValue;
        pIsSeisuu = ResultKabunSuu.IsSeisuu();
    }
}


実行結果

省略
結果が55になるのは156通り
結果が11になるのは157通り
結果が1になるのは161通り
結果が19になるのは161通り
結果が10になるのは162通り


解説

8-21 小町算をベースにしてます。