どーも、みつおです。
問題
五角数は 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
コメント