トップページに戻る
次のC#のサンプルへ
前のC#のサンプルへ
Cマガ電脳クラブ(第105回) 平方小町式
問題
下の式は、左辺が平方数の和、右辺がひとつの平方数となっており、成立している。
4*4 + 12*12 + 36*36 +87*87 = 95*95
さらによく見ると、この式に登場している平方数の根 (ここでいう4、12、36、87、95) を構成する数字は全部で9個、
しかも1〜9が1個ずつすべて使われている。
このように、「いくつかの平方数の和 (左辺) がひとつの平方数 (右辺) と等しく、
そこに登場する平方数の根は1〜9(0は使わない)の数字をダブりなく1個ずつすべて使っている」
という式を平方小町式と呼ぶことにする。この平方小町式をすべて見つけてほしい。
もちろん、左辺の各項を入れ換えたものは別の解とはしない。また、左辺が4項の和とは限らないことに注意。
ソース
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
struct KouhoInfoDef
{
internal int Val;
internal int[] NumArr;
}
struct JyoutaiDef
{
internal int CurrP;
internal List<int> ValList;
internal HashSet<int> UsedNumSet;
}
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
KouhoInfoDef[] KouhoInfoArr = CreateKouhoInfoArr();
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrP = 0;
WillPush.ValList = new List<int>();
WillPush.UsedNumSet = new HashSet<int>();
stk.Push(WillPush);
var AnswerValArrList = new List<int[]>();
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
//クリア判定
if (Popped.UsedNumSet.Count == 9) {
int LeftVal = 0;
for (int I = 0; I <= Popped.ValList.Count - 2; I++) {
LeftVal += Popped.ValList[I] * Popped.ValList[I];
}
int RightVal = Popped.ValList.Last() * Popped.ValList.Last();
if (LeftVal == RightVal) {
AnswerValArrList.Add(Popped.ValList.ToArray());
}
continue;
}
for (int I = Popped.CurrP; I <= KouhoInfoArr.GetUpperBound(0); I++) {
if (Popped.UsedNumSet.Count + DeriveKetasuu(KouhoInfoArr[I].Val) > 9) break;
//最初に4桁以上は不適
if (Popped.ValList.Count == 0 && DeriveKetasuu(KouhoInfoArr[I].Val) >= 4) break;
//2番目に5桁以上は不適
if (Popped.ValList.Count == 1 && DeriveKetasuu(KouhoInfoArr[I].Val) >= 5) break;
//最初が3桁で次に4桁以上は不適
if (Popped.ValList.Count == 1) {
if (DeriveKetasuu(Popped.ValList[0]) == 3
&& DeriveKetasuu(KouhoInfoArr[I].Val) >= 4) break;
}
//左辺が2桁 + 3桁は不適
if (Popped.ValList.Count == 1) {
if (DeriveKetasuu(Popped.ValList[0]) == 2
&& DeriveKetasuu(KouhoInfoArr[I].Val) == 3)
break;
}
//3桁,3桁の場合
if (Popped.ValList.Count == 1) {
if (DeriveKetasuu(Popped.ValList[0]) == 3
&& DeriveKetasuu(KouhoInfoArr[I].Val) == 3) {
int wkSum = Popped.ValList[0] * Popped.ValList[0];
wkSum += KouhoInfoArr[I].Val * KouhoInfoArr[I].Val;
if (Array.Exists(KouhoInfoArr, A => A.Val == wkSum) == false)
continue;
}
}
//2桁,2桁,2桁の場合
if (Popped.ValList.Count == 2) {
if (DeriveKetasuu(Popped.ValList[0]) == 2
&& DeriveKetasuu(KouhoInfoArr[1].Val) == 2
&& DeriveKetasuu(KouhoInfoArr[I].Val) == 2) {
int wkSum = Popped.ValList[0] * Popped.ValList[0];
wkSum += KouhoInfoArr[1].Val * KouhoInfoArr[1].Val;
wkSum += KouhoInfoArr[I].Val * KouhoInfoArr[I].Val;
if (Array.Exists(KouhoInfoArr, A => A.Val == wkSum) == false)
continue;
}
}
//1桁,4桁の場合
if (Popped.ValList.Count == 1) {
if (DeriveKetasuu(Popped.ValList[0]) == 1
&& DeriveKetasuu(KouhoInfoArr[I].Val) == 4) {
int wkSum = Popped.ValList[0] * Popped.ValList[0];
wkSum += KouhoInfoArr[I].Val * KouhoInfoArr[I].Val;
if (Array.Exists(KouhoInfoArr, A => A.Val == wkSum) == false)
continue;
}
}
//同じ数字は使用不可
if (Popped.UsedNumSet.Overlaps(KouhoInfoArr[I].NumArr)) {
continue;
}
WillPush.CurrP = I + 1;
WillPush.ValList = new List<int>(Popped.ValList) { KouhoInfoArr[I].Val };
WillPush.UsedNumSet = new HashSet<int>(Popped.UsedNumSet);
WillPush.UsedNumSet.UnionWith(KouhoInfoArr[I].NumArr);
//桁数が広義の単調増加でなかったら枝切り
int RestNumCnt = 9 - WillPush.UsedNumSet.Count;
if (RestNumCnt > 0) {
if (RestNumCnt < DeriveKetasuu(WillPush.ValList.Last())) break;
}
stk.Push(WillPush);
}
}
//辞書順でソート
AnswerValArrList.Sort((A, B) =>
{
int UB_A = A.GetUpperBound(0);
int UB_B = B.GetUpperBound(0);
for (int I = 0; I <= Math.Min(UB_A, UB_B); I++) {
if (A[I] < B[I]) return -1;
if (A[I] > B[I]) return 1;
}
return UB_A.CompareTo(UB_B);
});
var sb = new System.Text.StringBuilder();
for (int I = 0; I <= AnswerValArrList.Count - 1; I++) {
sb.AppendFormat("解{0} ", I + 1);
int UB = AnswerValArrList[I].GetUpperBound(0);
for (int J = 0; J <= UB; J++) {
sb.AppendFormat("{0}*{0}", AnswerValArrList[I][J]);
if (J <= UB - 2) sb.Append(" + ");
if (J == UB - 1) sb.Append(" = ");
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
Console.WriteLine("経過時間={0}", sw.Elapsed);
}
//各項の候補を作成
static KouhoInfoDef[] CreateKouhoInfoArr()
{
var WillReturn = new List<KouhoInfoDef>();
for (int I = 1; I <= 98765; I++) {
var NumSet = new HashSet<int>();
bool IsValid;
DeriveNumList(I, out NumSet, out IsValid);
if (IsValid)
WillReturn.Add(new KouhoInfoDef() { Val = I, NumArr = NumSet.ToArray() });
}
return WillReturn.ToArray();
}
//数字のリストを作成
static void DeriveNumList(int pTargetVal, out HashSet<int> pNumSet, out bool pIsValid)
{
pNumSet = new HashSet<int>();
pIsValid = false;
int CopiedVal = pTargetVal;
do {
int ModVal = CopiedVal % 10;
if (ModVal == 0) return;
if (pNumSet.Add(ModVal) == false) return;
CopiedVal /= 10;
} while (CopiedVal > 0);
pIsValid = true;
}
//桁数を求める
static int DeriveKetasuu(int pTargetNum)
{
if (pTargetNum < 10) return 1;
if (pTargetNum < 100) return 2;
if (pTargetNum < 1000) return 3;
if (pTargetNum < 10000) return 4;
if (pTargetNum < 100000) return 5;
return 6;
}
}
実行結果
解1 2*2 + 7*7 + 9*9 + 41*41 + 53*53 = 68*68
解2 4*4 + 12*12 + 36*36 + 87*87 = 95*95
解3 5*5 + 19*19 + 43*43 + 67*67 = 82*82
解4 8*8 + 14*14 + 39*39 + 62*62 = 75*75
経過時間=00:00:45.3535840
解説
計算量を減らすのに、必要条件での絞込みや、枝切りを使ってます。
左辺に5桁以上の数を含むと
10000*10000 >= 9876*9876 なので
左辺の数は全て、4桁以下
右辺が8桁で左辺の最大値を考えると、
9*9 = 81
右辺が7桁で左辺の最大値を考えると、
9*9+9*9 = 162
99*99 = 9801
右辺が6桁で左辺の最大値を考えると、
9*9+9*9+9*9 = 243
9*9+99*99 = 9882
999*999 = 998001
右辺の最小値は、100000*100000= 100億
よって、各項は全て5桁以下
左辺が2桁 + 3桁 で 右辺が4桁の場合を考えると、
左辺の最大値は、98*98+987*987 = 983773
右辺の最小値は、1234*1234 = 1522756
なので、左辺が2桁 + 3桁は不適