許容される各行列は [0,9] からの 9 つの数値の実行であるため、000000000 から 999999999 までの 9 桁の数値はすべて、チェックする行列の 1 つに対応します。したがって、これらの行列を反復処理するということは、基本的には 9 桁の数字を数え、数字を読み取って行列要素を取得することを意味します。問題は、これらの数字の読み取りに時間がかかり、10^9 回実行していることです。をインクリメントしてカウントする場合はint
、毎回文字列に変換して文字を読み取るか、フロアとモジュロ除算を使用して毎回 1 桁を選択する必要がありますが、どちらも受け入れられません。
解決策は、行列を 9int
の配列として表し、その 9 桁の数字の各桁に 1 つずつ、それらint
の をインクリメントしてカウントすることです。次に、数字の読み取りは、配列要素にアクセスするのと同じくらい簡単です。再帰関数を使用して、次のように数えることができます。
void count(int * matrix, int pos, int * magicCount)
{
do
{
if(pos<8)
{
count(matrix, pos+1, magicCount);
}
else
{
if(isMagic(matrix))
{
(*magicCount)++;
}
}
matrix[pos] += 1;
}
while(matrix[pos] < 10);
for(; pos<9; pos++)
{
matrix[pos] = 0;
}
}
http://en.wikipedia.org/wiki/Binary_coded_decimal