Q02 数列の四則演算

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        for (int I = 1000; I <= 9999; I++) {
            //10の倍数なら対象外
            if (I % 10 == 0) continue;

            int ReverseNum = DeriveReverseNum(I);

            List<int[]> SplitArrList = ExecSplit(I.ToString());
            foreach (int[] EachSplitArr in SplitArrList) {
                int ProdVal = 1;
                Array.ForEach(EachSplitArr, X => ProdVal *= X);

                if (ProdVal == ReverseNum) {
                    Console.WriteLine("解を発見");
                    Console.WriteLine(I);

                    Console.Write("計算式は");
                    for (int J = 0; J <= EachSplitArr.GetUpperBound(0); J++) {
                        Console.Write(EachSplitArr[J]);
                        if (J < EachSplitArr.GetUpperBound(0))
                            Console.Write("*");
                    }
                    Console.WriteLine("={0}", ReverseNum);
                }
            }
        }
    }

    struct JyoutaiDef
    {
        internal int CurrPos;
        internal List<int> SplitNumList;
    }

    //数値を引数として、数値の組み合わせに分割した配列のListを返す
    static List<int[]> ExecSplit(string pTargetNumStr)
    {
        var WillReturn = new List<int[]>();

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrPos = 0;
        WillPush.SplitNumList = new List<int>();
        stk.Push(WillPush);

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

            //クリア判定
            if (Popped.CurrPos > pTargetNumStr.Length - 1) {
                if (Popped.SplitNumList.Count > 1)
                    WillReturn.Add(Popped.SplitNumList.ToArray());
                continue;
            }

            for (int I = Popped.CurrPos; I <= pTargetNumStr.Length - 1; I++) {
                WillPush.CurrPos = I + 1;
                WillPush.SplitNumList = new List<int>(Popped.SplitNumList);
                string SplitStr = pTargetNumStr.Substring(Popped.CurrPos, I - Popped.CurrPos + 1);
                WillPush.SplitNumList.Add(int.Parse(SplitStr));
                stk.Push(WillPush);
            }
        }
        return WillReturn;
    }

    //数字を入れ替えた数値を求める
    static int DeriveReverseNum(int pTargetNum)
    {
        var NumList = new List<int>();
        int CopiedVal = pTargetNum;
        do {
            NumList.Add(CopiedVal % 10);
            CopiedVal /= 10;
        } while (CopiedVal > 0);

        int WillReturn = 0;
        foreach (int EachNum in NumList) {
            WillReturn *= 10;
            WillReturn += EachNum;
        }
        return WillReturn;
    }
}

実行結果

解を発見
5931
計算式は5*9*31=1395

解説

引き算を使うとすると、式はA-Bと表すことができる
Aは最大でも999であるため、A-Bは4桁にならない。
よって、引き算は使用できない。
同様に割り算も使用できない。

足し算を使うとすると、式はA+Bと表すことができる。
Aが2桁の場合は、Aの最大値は99で、Bの最大値も99なので、A+Bは4桁にならない。
Aが1桁の場合は、
1+999=1000 (解として不適)
2+998=1000 (解として不適)
2+999=1001 (解として不適)
3+997=1000 (解として不適)
省略
9+991=1000 (解として不適)
省略
9+999=1008 (解として不適)
となるので、足し算は使用できない。

よって掛け算のみの使用となるので、掛け算の式を数値ごとに列挙してます。