C#でプロジェクトオイラーを解く（問題４４「五角数」）

Tweet

Pocket

どーも、みつおです。

問題

五角数は Pn = n(3n-1)/2 で生成される. 最初の10項は

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …

である.

P4 + P7 = 22 + 70 = 92 = P8 である. しかし差 70 – 22 = 48 は五角数ではない.

五角数のペア Pj と Pk について, 差と和が五角数になるものを考える. 差を D = |Pk – Pj| と書く. 差 D の最小値を求めよ.

出典：Problem44

解答

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

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

        private static long Solve()
        {
            long ret = 0;
            List<long> gokakulist = new List<long>();

            long num = 0;
            long gokakucnt = 1;
            int pnt = 1;
            long max = 0;
            
            while (true)
            {
                //五角数を求める
                num = (gokakucnt * (3 * gokakucnt - 1)) / 2;

                //五角数のリストに追加
                gokakulist.Add(num);

                //カウントが2より少ない
                if (gokakulist.Count < 2)
                {
                    gokakucnt++;
                    continue;
                }

                //五角数の最大値が和より小さい
                max = gokakulist.Max();
                var tmpmax = gokakulist[pnt] + gokakulist[pnt - 1];

                //五角数の和が五角数のリストに無ければ、五角数のリストを増やす
                if (max < tmpmax)
                {
                    gokakucnt++;
                    continue;
                }

                //五角数の和・差が五角数のリストにあるか判定
                if(IsGokaku(gokakulist,pnt++,ref ret))
                { 
                    break;
                }
                
                //五角数の項をインクリメント
                gokakucnt++;
            }

            return ret;
        }

        private static bool IsGokaku(List<long> gokakulist,int cnt,ref long diff)
        {
            bool ret = false;
            long sum = 0;
            //long diff = 0;
            long max = gokakulist.Max();

            for(int i = cnt-1; i >= 0; i--)
            {
                //和
                sum = gokakulist[cnt] + gokakulist[i];

                //差
                diff = gokakulist[cnt] - gokakulist[i];

                //五角数の和・差が、五角数のリストにあるか検索
                var wa = gokakulist.IndexOf(sum);
                var sa = gokakulist.IndexOf(diff);

                //和と差がともに五角数であるか判定
                if (0 < sa && 0 < wa) return true;
            }

            return ret;
        }
    }   
}

出力

5482660