一种方法是用
考虑伪代码：
read n (non-zero natural number)
x <- 1
y <- n
d <- 2
while x < y
{
if n % d = 0
{
x <- d
y <- [n / d]
}
d <- d + 1
}
if x = y
{
write 'D', x
}
else
{
write 'N'
}
我必须修改这个伪代码，使其中没有循环，所以我必须去掉顶部的while循环。我看了一些例子，即数字{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100}，代码显示了数字{2, 3, 5, 6, 7, 8}的N，而对于{1, 4, 9, 100}，它显示了D，然后是它们各自的平方根(分别为{1, 2, 3, 10}(。
所以我得出结论，只有当n是一个完美的平方时，代码才会输出D，然后它会显示它的平方根。对于不是完美平方的数字，它输出N。
这意味着我必须更改上面的伪代码，以便它检查数字n是否是完美平方。但是，如果不使用ANY循环，我怎么能做到这一点呢？特别是因为这是伪代码，所以我没有像sqrt(n)这样的函数。我从一个通常有简单问题的来源得到了这个练习，所以它一定是我看不到的简单的东西，没有什么复杂的。但我看不出有任何方法可以使用给定的变量，或者创建新的变量来检查给定的数字n是否是一个没有任何循环的完美正方形。
recursive function替换while expression。
作为的一个例子
read n (non-zero natural number)
// recursive function loop, inside of method read
loop(num,x,y,d)
if x < y
if num % d = 0
loop(num, d, n / d, d + 1) // recursive function call
else
loop(num, x, y, d + 1) // recursive function call
else // exit of the loop function
if x = y
return d - 1 // it is a perfect square
else
return -1 // it is not a perfet square
// recursive function call
res = loop(n,1,n,2)
if res = -1
write 'N'
else
write res
用Scala编写
object PerfetSquare {
def read(n: Int): Int = {
@tailrec
def loop(num: Int,x: Int,y: Int, d: Int): Int = {
if(x < y) {
if(num % d == 0) {
loop(num, d, n / d, d + 1)
} else {
loop(num, x, y, d + 1)
}
} else if (x == y){
d - 1 // it is a perfect square
} else {
-1 // it is not a perfect square
}
}
loop(n,1,n,2)
}
def main(args: Array[String]): Unit = {
val res = read(64)
if(res == -1) println("N")
else println(s"D $res")
val res2 = read(65)
if(res2 == -1) println("N")
else println(s"D $res2")
}
}
输出
D 8
N