Рекурсивный метод для каталонских чисел в R - PullRequest
Новая
       44

Рекурсивный метод для каталонских чисел в R

0 голосов
/ 21 мая 2018

Я пытаюсь написать функцию в R, которая будет принимать входные данные numb и выводить соответствующее каталонское число.К вашему сведению, рекурсивная формула для каталонских номеров : 

C_0 = 1; 
C_n = {(4n - 2)*C_(n-1)}/(n+1)

Мой код выглядит следующим образом: 

catalan_num_recr <- function(numb){
  if (numb == 0){
    return(1)
  }
  else
    return(((4*numb-2)*catalan_num_recr(numb-1))/(numb+1))
}

Когда я запускаю функцию, я получаю, 

> catalan_num_recr(3)
[1] 5

Что правильно.

AIM : Тем не менее, я пытаюсь найти каталонские числа для диапазона, я хотел бы найти что-то вроде catalan_num_recr(1:10).

ПРОБЛЕМА : Это не работает с моей функцией, я получаю следующее предупреждение, 

Warning messages:
1: In if (numb == 0) { :
  the condition has length > 1 and only the first element will be used

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

> catalan_num_recr(1:15)
 [1] 1.000000 2.000000 2.500000 2.800000 3.000000 3.142857 3.250000
 [8] 3.333333 3.400000 3.454545 3.500000 3.538462 3.571429 3.600000
[15] 3.625000

Может ли кто-нибудь помочь мне изменить мою функцию или помочь мне разобраться в проблеме?

С уважением.

Ответы [ 5 ]

0 голосов
/ 21 мая 2018

Во-первых, вы получите предупреждение о том, что в numb == 0 R будет просто оцениваться numb[1] == 0.

Хотя остальные ответы верны, они не очень эффективны, потому что вам нужно вычислять каждое каталонское число несколько раз.(Для Catalan (15) вам нужно вычислить Catalan (14), который вы уже вычислили)

Я думаю, что это лучшая версия, которая вычисляет каждое каталонское число до максимального числа, а затем возвращаетте, которые вы просили.

catalan <- function(numbs) {
   cat <- vector("numeric", length(max(numbs)) + 1)
   for (i in 0:max(numbs)) {
      if (i == 0) {
         cat[i+1] <- 1
      } else {
         cat[i+1] <- ((4*i - 2)*cat[i])/(i + 1)
      }
   }
   cat[numbs + 1]
}

> catalan(1:15)
 [1]       1       2       5      14      42     132     429
 [8]    1430    4862   16796   58786  208012  742900 2674440
[15] 9694845

Вот небольшой тест, где catrvect = Vectorize(catalan_num_recr)

microbenchmark::microbenchmark(catalan(1:100), catvect(1:100))
Unit: microseconds
           expr      min        lq      mean    median       uq
 catalan(1:100)   86.515   98.7565  127.3139  122.7665  141.423
 catvect(1:100) 4764.728 4947.3070 5661.0624 5124.3385 5647.238
       max neval
   276.825   100
 11009.428   100

Конечно, функция теперь не рекурсивная.

0 голосов
/ 21 мая 2018

Вы можете использовать sapply (или lapply) для вашего вектора чисел 

sapply(c(0:15), catalan_num_recr)

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

data.frame("n" = c(0:5), "cnr" = sapply(c(0:5), catalan_num_recr))

  n cnr
1 0   1
2 1   1
3 2   2
4 3   5
5 4  14
6 5  42
0 голосов
/ 21 мая 2018

Ваша функция в настоящее время не принимает векторный ввод.Это может немного сбивать с толку, потому что многие функции, такие как математические операторы, по умолчанию векторизованы.Вам необходимо применить функцию к каждому элементу вектора с помощью функции map или apply.Это, по сути, быстрый цикл, и пакет purrr обладает преимуществом согласованного синтаксиса и стабильности типов. 

catalan_num_recr <- function(numb){
  if (numb == 0){
    return(1)
  }
  else
    return(((4*numb-2)*catalan_num_recr(numb-1))/(numb+1))
}

purrr::map_dbl(1:15, catalan_num_recr)
#>  [1]       1       2       5      14      42     132     429    1430
#>  [9]    4862   16796   58786  208012  742900 2674440 9694845

Создан в 2018-05-21 пакетом prex (v0.2.0).

0 голосов
/ 21 мая 2018

Вам просто нужно использовать векторизованную функцию, такую ​​как sapply из семейства apply.

sapply(1:10,catalan_num_recr,USE.NAMES = F)

0 голосов
/ 21 мая 2018

Используйте Vectorize, который принимает функцию и возвращает новую функцию, которая по сути является оберткой для вашей функции, которая принимает векторизованный ввод.Вычисление фактически выполняется многократно с помощью mapply, поэтому оно не будет таким быстрым, как написание функции, векторизованной вручную. 

Vectorize(catalan_num_recr)(1:15)
 [1]       1       2       5      14      42     132     429    1430    4862
[10]   16796   58786  208012  742900 2674440 9694845
...