Problem33 桁消去分数

問題

49/98は面白い分数である.
「分子と分母からそれぞれ9を取り除くと, 49/98 = 4/8 となり, 簡単な形にすることができる」
と誤って思い込んでしまうかもしれないからである.
(方法は正しくないが，49/98の場合には、たまたま正しい約分になってしまう．)

ただし、30/50 = 3/5 のような、分子または分母が10の倍数のタイプは自明な例だとする.

このような分数のうち, 1より小さく,
分子・分母がともに2桁の数になるような自明でないものは, 4個ある.
その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ.

ソース

using System;

class Program
{
    static void Main()
    {
        int ZentaiBunshi = 1, ZentaiBunbo = 1;

        for (int Bunshi = 11; Bunshi <= 99; Bunshi++) {
            //10の倍数は対象外
            if (Bunshi % 10 == 0) continue;

            string StrBunshi = Bunshi.ToString();
            //同じ数字が2つな2桁の数は対象外
            if (StrBunshi[0] == StrBunshi[1]) continue;

            for (int Bunbo = Bunshi + 1; Bunbo <= 99; Bunbo++) {
                //10の倍数は対象外
                if (Bunbo % 10 == 0) continue;

                string StrBunbo = Bunbo.ToString();

                //同じ数字が2つな2桁の数は対象外
                if (StrBunbo[0] == StrBunbo[1]) continue;

                int CorrectYakubunBunshi = Bunshi;
                int CorrectYakubunBunbo = Bunbo;
                ExecCorrectYakubun(ref CorrectYakubunBunshi, ref CorrectYakubunBunbo);

                //既約分数だった場合
                if (CorrectYakubunBunshi == Bunshi
                 && CorrectYakubunBunbo == Bunbo) continue;

                string StrWrongYakubunBunshi = StrBunshi;
                string StrWrongYakubunBunbo = StrBunbo;
                ExecWrongYakubun(ref StrWrongYakubunBunshi, ref StrWrongYakubunBunbo);

                //空文字になった場合
                if (StrWrongYakubunBunshi == "") continue;

                //共通文字がなくて間違った約分ができなかった場合
                if (StrWrongYakubunBunshi == StrBunshi
                && StrWrongYakubunBunbo == StrBunbo) continue;

                int IntWrongYakubunBunshi = int.Parse(StrWrongYakubunBunshi);
                int IntWrongYakubunBunbo = int.Parse(StrWrongYakubunBunbo);

                //分子か分母が0になった場合
                if (IntWrongYakubunBunshi == 0 || IntWrongYakubunBunbo == 0) continue;

                //たまたま正しい約分になった場合
                ExecCorrectYakubun(ref IntWrongYakubunBunshi, ref IntWrongYakubunBunbo);
                if (CorrectYakubunBunshi == IntWrongYakubunBunshi
                && CorrectYakubunBunbo == IntWrongYakubunBunbo) {
                    Console.WriteLine("面白い分数 {0,2}/{1,2}を発見", Bunshi, Bunbo);

                    ZentaiBunshi *= Bunshi;
                    ZentaiBunbo *= Bunbo;
                    ExecCorrectYakubun(ref ZentaiBunshi, ref ZentaiBunbo);
                }
            }
        }
        Console.WriteLine("解は{0}", ZentaiBunbo);
    }

    //正しい約分を行う
    static void ExecCorrectYakubun(ref int pBunshi, ref int pBunbo)
    {
        int GCD = DeriveGCD(pBunshi, pBunbo);
        pBunshi /= GCD;
        pBunbo /= GCD;
    }

    //間違った約分を行う
    static void ExecWrongYakubun(ref string pBunshi, ref string pBunbo)
    {
        for (int I = pBunshi.Length - 1; 0 <= I; I--) {
            int Ind = pBunbo.IndexOf(pBunshi[I]);
            if (Ind >= 0) {
                pBunshi = pBunshi.Remove(I, 1);
                pBunbo = pBunbo.Remove(Ind, 1);
            }
        }
    }

    //ユークリッドの互除法で2数の最大公約数を求める
    static int DeriveGCD(int pVal1, int pVal2)
    {
        int WarareruKazu = Math.Max(pVal1, pVal2);
        int WaruKazu = Math.Min(pVal1, pVal2);

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

実行結果

面白い分数 16/64を発見
面白い分数 19/95を発見
面白い分数 26/65を発見
面白い分数 49/98を発見
解は100

解説

String.Removeメソッドを使って間違った約分を実装してます。