Числа фибоначчи c цикл

Числа фибоначчи c цикл

Числа Фибоначчи – это ряд чисел, в котором каждое последующее число равно сумме двух предыдущих:

1, 1, 2, 3, 5, 8, 13 и т. д.

То есть последовательность всегда начинается с двух единиц. А каждое следующее число является определяется по формуле:


Для определения чисел Фибоначчи часто используется рекурсивный алгоритм:

  • Если n = 1 или n = 2, вернуть 1 (поскольку первый и второй элементы ряда Фибоначчи равны 1).
  • Вызвать рекурсивно функцию с аргументами n-1 и n-2.
  • Результат двух вызовов сложить и вернуть полученное значение.

Реализация с использованием рекурсии

Реализация на Си

Результат выполнения

У решения с рекурсией есть большая проблема: пересекающиеся вычисления. Когда вызывается fibonacci(N) , то подсчитываются значения функции N-1 и для N-2 . Но если требуется вычислить fibonacci(N-1) , то значения для N-2 и N-3 вычисляются заново.

Поэтому поставленную задачу определения чисел Фибоначчи можно решить без использования рекурсии.

Реализация с использованием цикла

В этом алгоритме используется свойство, что для определения следующего числа Фибоначчи используются только два предыдущих значения.

Алгоритм при этом будет следующий

  • Ввести номер N определяемого элемента.
  • Проинициализировать два первых элемента a и b значениями 1, и если N Реализация на Си

Числа Фибоначчи – это ряд чисел, в котором каждое следующее число равно сумме двух предыдущих: 1, 1, 2, 3, 5, 8, 13, . . Иногда ряд начинают с нуля: 0, 1, 1, 2, 3, 5, . . В данном случае мы будем придерживаться первого варианта.

Формула:

Пример вычисления:

Вычисление n-го числа ряда Фибоначчи с помощью цикла while

  1. Присвоить переменным fib1 и fib2 значения двух первых элементов ряда, то есть присвоить переменным единицы.
  2. Запросить у пользователя номер элемента, значение которого он хочет получить. Присвоить номер переменной n .
  3. Выполнять следующие действия n — 2 раз, так как первые два элемента уже учтены:
  1. Сложить fib1 и fib2 , присвоив результат переменной для временного хранения данных, например, fib_sum .
  2. Переменной fib1 присвоить значение fib2 .
  3. Переменной fib2 присвоить значение fib_sum .
Читайте также:  Справка антиплагиат как сделать
  • Вывести на экран значение fib2 .
  • Примечание. Если пользователь вводит 1 или 2, тело цикла ни разу не выполняется, на экран выводится исходное значение fib2 .

    Компактный вариант кода:

    Вывод чисел Фибоначчи циклом for

    В данном случае выводится не только значение искомого элемента ряда Фибоначчи, но и все числа до него включительно. Для этого вывод значения fib2 помещен в цикл.

    Рекурсивное вычисление n-го числа ряда Фибоначчи

    1. Если n = 1 или n = 2, вернуть в вызывающую ветку единицу, так как первый и второй элементы ряда Фибоначчи равны единице.
    2. Во всех остальных случаях вызвать эту же функцию с аргументами n — 1 и n — 2. Результат двух вызовов сложить и вернуть в вызывающую ветку программы.

    Допустим, n = 4. Тогда произойдет рекурсивный вызов fibonacci(3) и fibonacci(2). Второй вернет единицу, а первый приведет к еще двум вызовам функции: fibonacci(2) и fibonacci(1). Оба вызова вернут единицу, в сумме будет два. Таким образом, вызов fibonacci(3) возвращает число 2, которое суммируется с числом 1 от вызова fibonacci(2). Результат 3 возвращается в основную ветку программы. Четвертый элемент ряда Фибоначчи равен трем: 1 1 2 3.

    Предыстория задач Фибоначчи

    Леонардо Фибоначчи (1170-1250) — итальянский математик, положивший начало введения в Европе арабской системы чисел. В 1202 году он опубликовал следующую задачу: "Пара кроликов находится в загороженном месте. Сколько их потомков появится в течении года? Каждая пара кроликов каждый месяц производит новую пару, которая во втором месяце становится продуктивной".

    Число кроликов в каждом месяце соответствует числам Фибоначчи, каждое из которых получается как сумма двух предыдущих чисел. Числа Фибоначчи для бесконечной последовательности можно вычислить по формуле:

    , если .

    Кроме того, определяется, что f(1)=1 (соответствует новой паре кроликов к), f(2)=1 (соответствует взрослой паре кроликов К).

    Читайте также:  Titan quest просит диск

    Сколько пар кроликов в течении года появится в питомнике? Для решения этой задачи вычисляют первые 13 чисел Фибоначчи. Результат отражает ситуацию в начале следующего года.

    1к 1
    2К 1
    3Кк 2
    4КкК 3
    5КкККк 5
    6КкККкКкК 8
    7итд. 13
    8 21
    9 34
    10 55
    11 89
    12 144
    13 233

    Видим, что в начале следующего года кроликов должно быть 233 пары. На этом данная задача исчерпывается. Но ряды чисел Фибоначчи продолжают изучаться применительно к различным задачам.

    Программные реализации

    Программные реализации рядов чисел Фибоначчи различаются в зависимости от того, сколько членов последовательности нужно вычислить и вывести в программе, выводятся ли все числа или только одно с каким-либо номером, нужно ли предусмотреть возможность пользователя определить количество членов последовательности.

    Если в программе определено, что все числовые значения относятся к целому типу (int), то следует считаться с тем, что максимальное значение для целочисленного типа составляет 32 767. Но программа в этом случае выводит корректно весь ряд чисел Фибоначчи до 46 члена включительно. Дело в том, что происходит преобразование типа данных от int к long int. Только времени такое вычисление и вывод чисел занимает больше, чем в случае, если определить для чисел Фибоначчи тип данных long int.

    Если же определён тип данных long int, все члены последовательности Фибоначчи начиная с 47-го будут вычислены некорректно, поскольку максимальное значение для этого типа составляет 2 147 483 647. В случае типа double корректно выводятся числа Фибоначчи от 0 до 300 включительно.

    Наиболее простая реализация для рядов чисел Фибоначчи с целочисленным типом данных выглядит так:

    Ссылка на основную публикацию
    Adblock detector