Өгсөн тоог Фибоначчийн дарааллын гишүүн эсэхийг шалгаж харгалзах логик утга буцаах is.fibonacci нэртэй функц зохиож бич. Жич: Дараалал 1,1,2, ... гэж эхэлнэ.

Гаргаж хэлэх гэсэн санаагаа тодруулах үүднээс дээрх ердийн нэг програмчлалын бодлого авч үзье. Харин програм бичихдээ R хэл ашиглая.

Эхлээд Фибоначчийн дарааллын хэдэн гишүүн гаргаж авъя. Ингэхдээ уг дарааллын тухайн нэг гишүүн нь өмнөх хоёр гишүүний нийлбэрээр тодорхойлогддог болохыг анхаарна.

## function
fibonacci <- function (n = 47, fib = c(1,1)) {         # n - дарааллын хэмжээ
  if (n > 47) {
    stop("It will be reach to the integer overflow.")
  }
  size <- length(fib)
  if (size >= n) {                                     # дарааллын урт заасан хэмжээнд хүрсэн эсэхийг шалгах
    return(fib[1:n])                                   # функцийн буцаах утга
  }
  fib[size + 1] <- fib[size - 1] + fib[size]           # дарааллын шинэ гишүүн
  fibonacci(n, fib)                                    # рекурс
}

## run
f <- fibonacci(46)                                     # Фибоначчийн дарааллын эхний 46 гишүүн

## print
print(f)                                               # дараалал хэвлэх

Одоо үндсэн ажилдаа оръё. Өөрөөр хэлбэл өгсөн тоо тухайлбал дарааллын 46 дугаар гишүүнийг өгөөд үнэхээр Фибоначчийн дарааллын гишүүн мөн эсэхийг шалгах функц бичье. Энэ тохиолдолд Фибоначчийн дарааллын талаар, түүний математик шинж чанарын талаар мэдлэггүй хүнд уг дарааллын тодорхойлолт буюу тухайн гишүүн өмнөх хоёрынхоо нийлбэртэй тэнцүү гэдгээс өөр ашиглаад байх зүйл төдийлөн санаанд нь орохгүй болов уу. Ингээд яг ийм зарчмын дагуу ажиллах функцийг дараах байдлаар бичиж болно.

## function
is.fibonacci <- function (f) {   # f - гараас өгөх тоо
  fib <- 0:1                     # дарааллын эхний хоёр гишүүн
  while(fib[2] < f) {            # дарааллын сүүлийн гишүүн өгсөн тоог давсан эсэхийг шалгах
    fib[3] <- sum(fib)           # дарааллын шинэ гишүүн
    fib <- fib[-1]               # хэрэгцээгүй болсон гишүүнийг устгах
  }
  fib[2] == f                    # өгсөн тоог Фибоначчийн дарааллын гишүүн эсэхийг шалгах
}

## run
is.fibonacci(f[46])              # дээр гарган авсан дарааллын 46 дугаар гишүүнийг Фибоначчийн дарааллын гишүүн эсэхийг шалгах

## output
TRUE

Дээр бичсэн функц өгсөн тоог Фибоначчийн дарааллын гишүүн эсэхийг шалгах үйлдлийг дарааллын гишүүн нэг бүрчлэн авч үзэх замаар хийж байна. Гэтэл энэ нь хэтэрхий "үрэлгэн" арга зам юм. Тэгвэл үүнээс өөр хялбар, үр ашигтай арга зам юу байна вэ? Чухам энд л гарчиг дээрх асуулт холбогдох буюу математик л тэр ашигтай арга замыг зааж өгнө. Ингээд Фибоначчийн дарааллын чанар ашиглаж үүнийг илүү хялбар шийдэж болно.

## function
is.fibonacci.alt <- function (f) {
  any(sqrt((5 * f ** 2) + c(-4, 4)) %% 1 == 0)
}

## run
is.fibonacci.alt(f[46])

## output
TRUE

Ийнхүү ямар ч тоо өгөхөд маш хурдан ажиллаж чадах функц бичиж чадлаа. Сүүлд бичсэн кодын хувьд илүү тайлбар шаардлагагүй биз ээ. Ердөө ганц мөр юм чинь. Хоёр функцийг Фибоначчийн дарааллын 46 дугаар гишүүний хувьд бенчмарк хийхэд сүүлд бичсэн функц өмнөхөөс 13 дахин хурдан ажиллаж байна. Мэдээж энэ ялгаа дээр дурдсан математикийн чанарын л ач тус юм. Тэгэхээр сайн код бичихэд, сайн програмист болоход математик хэрэгтэй байгаа биз?