0

範囲 [a,b] の間の完全な数字を持つすべての完全な正方形を取得する最良の方法は何ですか? 完全な数字の完全な正方形は、すべての数字が完全な正方形を持つものです。私は次のようにしました

for j=a to b
    do if(checkPerfectSquare(j) && checkPerfectDigit(j))
        then ctr++
print ctr

int checkPerfectSquare(n)
{
if n<0
    return 0
root=round(sqrt(n))
return (n==root*root)
}

int checkPerfectDigit(n)
{
while n>0
    do rem=n%10
       n=n/10
    if(!checkPerfectSquare(rem))
        return 0
return 1
}
4

2 に答える 2

1

あなたが提供する疑似コードは正しいようです - のようなタイプミスを除いiて. 実装によって予期しない結果が得られる場合は、実際のコードを示してください。ncheckPerfectSquare

ここで、目的を確認しましょう。範囲 [a,b] 内に完全な数字がある完全な正方形を選択することです。ここに簡単なアイデアがあります：

  • 範囲 [a,b] を反復処理し、各数値をテストします。実際、これはまさにあなたがしていることです。aもちろん、これで正しい答えが得られますが、問題が大きくなるとb、非常に低い効率に悩まされることに注意してください。

範囲内のすべての数値よりも常に正方形が少ないことに注意してください。これを行うことができます。

  • [a,b] 内のすべての完全な正方形を反復処理し、それらが完全な数字で構成されているかどうかをテストします。これはどうですか？[10^(n-1), 10^n-1](すべての n 桁の数の範囲)の範囲内には、ほぼ10^(n/2) - 10^((n-1)/2)完全な正方形しかありません。これは、この範囲全体の数値の量よりもはるかに小さいため、プログラムの実行速度が向上します。

上記の考えに同意するなら、もっと良いプログラムを書くかもしれません。でも待って、今度は順番を逆にしてみましょう。実際には 3 つの完全な数字しかないことに注意してください:1 4と9、元のアイデアを次のように最適化できます。

  • [a,b] の範囲内の完全な数字 (例: 1111111、149149149、111144449999) で構成されるすべての数値を繰り返し処理し、それらが完全な正方形であるかどうかをテストします。n 桁の数字があり、n 桁の完全な数字10^nしかないため、これは明らかに高速に実行されます。= <なので3^n、これは上記のアイデアよりも優れています。3^n9^(n/2)10^(n/2)

ここでは、疑似コードや実際のコードは提供していません。アイデアを理解し、最初にコードを書いてみることをお勧めします。

于 2013-11-03T19:07:31.923 に答える