Project Euler 34
最大何桁まで求めたら良いのか。
[1] pry(main)> def f(n) n < 1 ? 1 : n*f(n-1) end => :f [2] pry(main)> (1..12).each { |i| puts "i:#{i} #{i*f(9)}" } i:1 362880 i:2 725760 i:3 1088640 i:4 1451520 i:5 1814400 i:6 2177280 i:7 2540160 i:8 2903040 i:9 3265920 i:10 3628800 i:11 3991680 i:12 4354560 => 1..12
9! = 362880
だから、1 桁増えても、最大で 362880 しか増えない。8 * 9! = 2903040
で 8 桁にとどかないので、7 まで調べればよい。
using System; using System.Collections.Generic; using System.Linq; class PE034 { static int Fact(int n) { return n < 1 ? 1 : n * Fact(n-1); } static int Calc1(int p, int[] digits) { if (p == digits.Length) { int sum = digits.Select(e => Fact(e)).Sum(); int[] xs = sum.ToString().Select(e => e - '0').OrderBy(e => e).ToArray(); if (xs.SequenceEqual(digits)) { Console.WriteLine("found:{0}", sum); return sum; } return 0; } int ret = 0; int start = p == 0 ? 0 : digits[p-1]; for (int i = start; i < 10; i++) { digits[p] = i; ret += Calc1(p+1, digits); } return ret; } static int Calc() { int ans = 0; for (int i = 2; i < 9; i++) { ans += Calc1(0, new int[i]); } return ans; } static void Main() { Console.WriteLine(Calc()); } }