Последовательность Фибоначчи: что-то не так в моих кодах вывод результатов? - PullRequest
Новая
       15

Последовательность Фибоначчи: что-то не так в моих кодах вывод результатов?

1 голос
/ 29 октября 2019

первый вход 5 и второй вход 13 и выход предполагается равным 5, 8, 13 

#include<stdio.h>

int main() {
    int lim_up, lim_low, A=5, B=13, C=8;

    printf("\n\n\t ENTER THE LOWER LIMIT: ");
    scanf("%d", &lim_low);
    printf("\n\n\t ENTER THE UPPER LIMIT: ");
    scanf("%d", &lim_up);
    printf("\n\n\t FIBONACCI NUMBERS ARE: ");


    do{
         lim_up++;

         printf("\n\n\t\t\t%d", A);
         A = C+B;
         B = c;
         C= A;
    }while(A<lim_up);
    getch();
}

я ожидаю, что выход будет 5 8 13

Ответы [ 2 ]

2 голосов
/ 29 октября 2019

Следующий код выводит последовательность Фибоначчи в интервале [lim_low ... lim_up] : 

#include<stdio.h>

int main(void)
{
    unsigned int lim_up, lim_low;
    printf("ENTER THE LOWER LIMIT: ");
    scanf("%u", &lim_low);
    printf("ENTER THE UPPER LIMIT: ");
    scanf("%u", &lim_up);
    printf("FIBONACCI NUMBERS ARE: ");

    unsigned int t1 = 0, t2 = 1, nextTerm = 0;

    while(nextTerm <= lim_up){
        if (nextTerm >= lim_low)
            printf("%u ",  nextTerm);

        t1 = t2;
        t2 = nextTerm;
        nextTerm = t1 + t2;
    }
    return 0;
}

Мы должны вычислить все Серия Фибоначчи , и когда мы достигаем интересующего нас интервала, мы начинаем выводить результаты.

Примечание : Это не самый эффективный способ сделать это. Существует O (1) математическая формула , которая может сделать это сразу без цикла.

ПРИЛОЖЕНИЕ: Делать это математическим способом Вот код для вычисления F (n) напрямую: 

unsigned fib(unsigned int n) { 
  double phi = (1 + sqrt(5)) / 2; 
  return round(pow(phi, n) / sqrt(5)); 
}

Теперь, чтобы получить n из F (n) васпотребуется следующий код: 

unsigned reverseFib(unsigned int fn) { 
  double phi = (1 + sqrt(5)) / 2; 
  return round(log(sqrt(5) * fn) / log(phi)); 
}

Обратите внимание:

  1. Функция выше будет работать для всех ожидаемых чисел Фибоначчи fn = 1 . Почему не работает fn = 1 ? Потому что fn = 1 можно почитать, чтобы дать 1 или 2, что сделает невозможным знать n , так как есть две возможности (Математически: F (n) не биективная функция для n в [1, 2]).
  2. Ошибка с плавающей запятой может теоретически происходят потому, что наши компьютеры не имеют бесконечной точности, но это случается редко.
  3. Я проверил эту функцию для первых 12 чисел Фибоначчи, и она работала нормально, за исключением fn = 2 , как объяснено выше в пункте 1 .
0 голосов
/ 29 октября 2019

Фибоначчи начинается с двух чисел. 

unsigned previous = 0;
unsigned current  = 1;

Следующий член задается суммой. 

unsigned next = previous + current;

Тогда мы можем сдвинуть все. 

previous = current;
current  = next;

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

#include <stdio.h>

/* **********

Fibonacci:
  F[0] = 0
  F[1] = 1
  F[n] = F[n-2] + F[n-1]

********** */

int main(void) {
   unsigned min = 5;
   unsigned max = 13;

   unsigned previous = 0;
   if (previous >= min)
      print("%u\n", current);

   unsigned current = 1;
   while (current <= max) {
      if (current >= min)
         printf("%u\n", current);

      unsigned next = previous + current;
      previous = current;
      current  = next;
   }

   return 0;
}

Но есть более простое решение. 

#include <stdio.h>

/* **********

Fibonacci:
  F[0] = 0
  F[1] = 1
  F[n] = F[n-2] + F[n-1]

If we don't print the first element, this is the same as
  F[0] = 1
  F[1] = 0
  F[n] = F[n-2] + F[n-1]

Taking this approach simplifies the code. 

********** */

int main(void) {
   unsigned min = 5;
   unsigned max = 13;

   unsigned previous = 1;
   unsigned current  = 0;
   while (current <= max) {
      if (current >= min)
         printf("%u\n", current);

      unsigned next = previous + current;
      previous = current;
      current  = next;
   }

   return 0;
}

Наконецоптимизированное решение с использованием функций, предоставляемых @ Omarito. 

#include <math.h>
#include <stdio.h>

const double phi = (1 + sqrt(5)) / 2;

unsigned fib(unsigned n) {
   return round(pow(phi, n) / sqrt(5));
}

unsigned reverse_fib(unsigned fn) {
   return round(log(sqrt(5) * fn) / log(phi));
}

int main(void) {
   unsigned min = 5;
   unsigned max = 13;

   unsigned previous;
   unsigned current;
   if (min == 0) {
      previous = 1;
      current  = 0;
   }
   else if (min == 1) {
      previous = 0;
      current  = 1;
   }
   else {
      current  = min;
      previous = fib(reverse_fib(current)-1);
   }

   while (current <= max) {
      printf("%u\n", current);

      unsigned next = previous + current;
      previous = current;
      current  = next;
   }

   return 0;
}
...