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和nin之类的拼写错误checkPerfectSquare。如果你的实现给出了意想不到的结果，请展示你的真实代码。

好的，在这里让我们回顾一下您的目的：选择范围 [a,b] 内具有完美数字的完美正方形。这是一个简单的想法：

  • 遍历范围 [a,b] 并测试每个数字。实际上，这正是您所做的。这当然给出了正确的答案，但是请注意什么时候你a的b问题变大了，效率会很低。

请注意，一个范围内的正方形总是少于所有数字，我们可以这样做：

  • 遍历 [a,b] 内的所有完美正方形并测试它们是否由完美数字组成。这会怎样？在[10^(n-1), 10^n-1]（所有n位数字的范围）范围内，只有大约10^(n/2) - 10^((n-1)/2)完美的正方形！这比整个范围内的数字量要小得多，因此您的程序会运行得更快。

好吧，如果您同意上述想法，您可能会编写一个更好的程序。但是等等，让我们这次尝试颠倒顺序。请注意，实际上只有三个完美数字：1 4和9，我们可以像这样优化原始想法：

  • 遍历 [a,b] 范围内由完美数字组成的所有数字（例如 1111111、149149149、111144449999），并测试它们是否是完美正方形。这显然会运行得更快，因为有10^nn 位数字，而只有3^nn 位完美数字。这会比上面的想法更好，因为3^n= 9^(n/2)<10^(n/2)

我暂时不在这里提供任何伪代码或真实代码。您可能想了解这些想法并尝试先编写一些代码。

于 2013-11-03T19:07:31.923 回答
0

您可以使用

count=((floor(sqrt(b))-ceil(sqrt(a)))+1);
于 2015-03-18T05:58:28.223 回答