Изменить данный псевдокод так, чтобы он не содержал петель - PullRequest
Новая
       60

Изменить данный псевдокод так, чтобы он не содержал петель

0 голосов
/ 04 мая 2020

Рассмотрим псевдокод: 

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'
}

Мне нужно изменить этот псевдокод таким образом, чтобы в нем не было петель, поэтому я должен избавиться от него, пока l oop вверху. Я рассмотрел несколько примеров, а именно числа {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 является идеальным квадратом, а затем показывает его квадрат root. Для чисел, которые не являются идеальными квадратами, он выводит N.

Это означает, что я должен изменить приведенный выше псевдокод так, чтобы он проверял, является ли число n идеальным квадратом или нет. Но как я могу сделать это без использования ЛЮБЫХ циклов? Тем более, что это псевдокод, поэтому у меня нет такой функции, как sqrt(n). Я получил это упражнение из источника, у которого обычно есть простые проблемы, поэтому это должно быть что-то простое, чего я просто не вижу, ничего сложного. Но я не вижу никакого способа использования данных переменных или создания новых, чтобы проверить, является ли данное число n идеальным квадратом без каких-либо петель.

1 Ответ

0 голосов
/ 04 мая 2020

Один из подходов - заменить выражение while рекурсивной функцией.

В качестве примера 

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")
  }
}

output 

D 8
N

Надеюсь, это даст вам некоторые подсказки. С уважением.

...