Хвостовой рекурсивный метод Scala имеет ошибку деления и остатка - PullRequest
Новая
       72

Хвостовой рекурсивный метод Scala имеет ошибку деления и остатка

0 голосов
/ 13 октября 2018

В настоящее время я вычисляю биномиальный коэффициент двух натуральных чисел, написав хвостовую рекурсию в Scala.Но в моем коде что-то не так с делением чисел, делением целых чисел на k, как я сделал, так как это даст вам ненулевой остаток и, следовательно, приведет к ошибкам округления.Так может кто-нибудь помочь мне разобраться, как это исправить? 

 def binom(n: Int, k: Int): Int = {
    require(0 <= k && k <= n)
    def binomtail(n: Int, k: Int, ac: Int): Int = {
      if (n == k || k == 0) ac
      else binomtail(n - 1, k - 1, (n*ac)/k)
    }
    binomtail(n,k,1)
  }

1 Ответ

0 голосов
/ 13 октября 2018

В общем случае оно содержит: 

binom(n, k) = if (k == 0 || k == n) 1 else binom(n - 1, k - 1) * n / k

Если вы хотите вычислить его за линейное время, то вы должны убедиться, что каждый промежуточный результат является целым числом.Теперь 

binom(n - k + 1, 1)

, безусловно, является целым числом (это просто n - k + 1).Начиная с этого числа и увеличивая оба аргумента на один, вы можете получить binom(n, k) со следующими промежуточными шагами: 

binom(n - k + 1, 1)
binom(n - k + 2, 2)
...
binom(n - 2, k - 2)
binom(n - 1, k - 1)
binom(n, k)

Это означает, что вы должны «накапливать» в правильном порядке, начиная с 1 до k, а не от k до 1 - тогда гарантируется, что все промежуточные результаты соответствуют фактическим биномиальным коэффициентам и, следовательно, являются целыми числами (не дробями).Вот как выглядит хвостовая рекурсивная функция: 

def binom(n: Int, k: Int): Int = {
  require(0 <= k && k <= n)
  @annotation.tailrec 
  def binomtail(nIter: Int, kIter: Int, ac: Int): Int = {
    if (kIter > k) ac
    else binomtail(nIter + 1, kIter + 1, (nIter * ac) / kIter)
  }
  if (k == 0 || k == n) 1
  else binomtail(n - k + 1, 1, 1)
}

Небольшой визуальный тест: 

val n = 12
for (i <- 0 to n) {
  print(" " * ((n - i) * 2))
  for (j <- 0 to i) {
    printf(" %3d", binom(i, j))
  }
  println()
}

Отпечатки: 

                           1
                         1   1
                       1   2   1
                     1   3   3   1
                   1   4   6   4   1
                 1   5  10  10   5   1
               1   6  15  20  15   6   1
             1   7  21  35  35  21   7   1
           1   8  28  56  70  56  28   8   1
         1   9  36  84 126 126  84  36   9   1
       1  10  45 120 210 252 210 120  45  10   1
     1  11  55 165 330 462 462 330 165  55  11   1
   1  12  66 220 495 792 924 792 495 220  66  12   1

Выглядит нормально, сравнитес это , если хотите.

...