0

考虑伪代码：

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}和代码导致显示N数字，并且显示数字{2, 3, 5, 6, 7, 8}和它们各自的平方根（分别）。{1, 4, 9, 100}D{1, 2, 3, 10}

所以我得出结论，代码D只有在n是一个完美平方时才输出，然后它显示它的平方根。对于不是完全平方的数字，它输出N.

这意味着我必须更改上面的伪代码，以便它检查数字n是否是完美的正方形。但是我怎么能在不使用任何循环的情况下做到这一点呢？特别是因为这是伪代码，所以我没有像sqrt(n). 我从一个通常有简单问题的来源得到这个练习，所以它一定是一些我看不到的简单的东西，没有什么复杂的。但是我看不到任何使用给定变量的方法，或者创建新变量来检查给定数字n是否是没有任何循环的完美正方形。

4

1 回答 1

0

一种方法是while expression用recursive function.

举个例子

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
于 2020-05-04T13:18:36.717 回答