c - 一个范围内具有完美数字的完美平方

Question

获得范围 [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
}

Answer 1

您提供的伪代码似乎是正确的 - 除了像 i 这样的拼写错误和n在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^n n 位数字，而只有 3^n有 n 个完美数字。这比上面的想法更好，因为 3^n =9^(n/2) <10^(n/2)

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