X

C#でプロジェクトオイラーを解く(問題33「桁消去分数」)

どーも、みつおです。

1の位と10の位を文字列として、同じ数値か判定した。 %10で各桁をとる方法でもよかったけど、

2桁という縛りがあったから、文字列のほうが簡単な気がしたので、そっちを採用。

問題

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

我々は 30/50 = 3/5 のようなタイプは自明な例だとする.

このような分数のうち, 1より小さく分子・分母がともに2桁の数になるような自明でないものは, 4個ある.

その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ.

出典:Problem33

解答

using System;

namespace Problem33
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Solve());
            Console.ReadLine();
        }

        private static int Solve()
        {
            int ret = 0;
            //桁消去の分子、分母
            int delbunshi, delbunbo;

            //分子の積、分母の積
            int sekibunshi = 1, sekibunbo = 1;
            
            //桁消去した文字列の分子、分母
            string strbunshi, strbunbo;
            
            //割り算結果、桁消去した割り算結果
            double dev,deldev;

            //分子のループ
            for(int bunshi = 11; bunshi <= 99; bunshi++)
            {
                //10の倍数は自明 または同じ数値(11,22,33...)は取り除く桁が不明なため除外
                if (bunshi % 10 == 0 || bunshi % 11 == 0) continue;

                //分母のループ
                for(int bunbo = 11; bunbo <= 99; bunbo++)
                {
                    //10の倍数は自明 または同じ数値(11,22,33...)は取り除く桁が不明なため除外
                    if (bunbo % 10 == 0 || bunbo % 11 == 0) continue;

                    // 分子/分母 が 1 より大きいものは除外 
                    if (bunbo <= bunshi) continue;

                    //文字列に変換
                    strbunshi = bunshi.ToString();
                    strbunbo = bunbo.ToString();

                    //消去できる数値があるか判定
                    if (strbunshi[0] != strbunbo[1] && strbunshi[1] != strbunbo[0]) continue;

                    //元のデータの割り算
                    dev = (double)bunshi / (double)bunbo;

                    //同じ数値か判定
                    if(strbunshi[0] == strbunbo[1])
                    {
                        //同じ数値じゃない方を取得
                        delbunshi = int.Parse(strbunshi[1].ToString());
                        delbunbo = int.Parse(strbunbo[0].ToString());
                    }
                    else
                    {
                        //同じ数値じゃない方を取得
                        delbunshi = int.Parse(strbunshi[0].ToString());
                        delbunbo = int.Parse(strbunbo[1].ToString());
                    }

                    //同じ数値を消去したデータの割り算
                    deldev = (double)delbunshi / (double)delbunbo;

                    //桁消去した分数が元の分数と同じか判定
                    if(dev == deldev)
                    {
                        //分子の積と分母の積を求める
                        sekibunshi *= delbunshi;
                        sekibunbo *= delbunbo;
                    }
                }
            }

            //分母の積 / 分子の積 を求める
            ret = sekibunbo / sekibunshi;

            return ret;
        }
    }
}

 

出力

100

みつお: