Вывести все числа фибоначчи которые в записи имеют не более n цифр задается с клавиатуры

Обновлено: 04.05.2024

1. Вывести на экран n первых чисел ряда Фибоначчи.

Решение: первый алгоритм поиска чисел Фибоначчи.
Ответ:
n=6
1 1 2 3 5 8

2. Вывести на экран n-ый элемент ряда Фибоначчи.

Решение: первый алгоритм поиска чисел Фибоначчи.
Ответ:
n=10
ch=55

program fib_02;
uses crt;
var ch, ch1, n, i, ch2: integer;

3. Вывести на экран n1-ый и n2-ой элементы ряда Фибоначчи и их сумму

Решение: первый алгоритм поиска чисел Фибоначчи.

Ответ:
n1=5
n2=10
5 55
S=60

или

Ответ:
n1=10
n2=5
5 55
S=60

Program fib_03;
Uses CRT;
var n1, n2, ch, ch1,ch2, i, max, s:integer;

n1, n2 - номера чисел Фибоначчи;
ch - число Фибоначчи;
ch1, ch2 - вспомогательные переменные алгоритма поиска чисел Фибоначчи;
max - наибольший номер числа Фибоначчи;
S - сумма чисел>

begin
clrscr;
s:=0;
write('n1='); readln(n1);
write('n2='); readln(n2);

if n2 > n1 then max:=n2 else max:=n1;

6. 10 случайных чисел генерируются компьютером в интервале [5,10].
Вывести на экран числа ряда Фибоначчи. Найти их среднее арифметическое.

Решение: первый алгоритм поиска чисел Фибоначчи (рациональнее было бы применить второй алгоритм поиска чисел Фибоначчи. )

Ответ может быть:
Количество чисел Фибоначчи равно 0.

ch=8 ch=8 ch=8
Sred=8.

if kch< >0 then begin Sred:=s/kch ; write ('Sred=':5, sred) end
else writeln('Количество чисел Фибоначчи равно 0.');
end.

7. Число x вводится с клавиатуры. Проверить, является оно числом ряда Фибоначчи. Программа с тестированием.

Решение: второй алгоритм поиска чисел Фибоначчи.

Ответ:
x=5
1. ch1=1 ch2=0 ch=1
2. ch1=0 ch2=1 ch=1
3. ch1=1 ch2=1 ch=2
4. ch1=1 ch2=2 ch=3
5. ch1=2 ch2=3 ch=5
Цикл закончен
x - число Фибоначчи

x=6
1. ch1=1 ch2=0 ch=1
2. ch1=0 ch2=1 ch=1
3. ch1=1 ch2=1 ch=2
4. ch1=1 ch2=2 ch=3
5. ch1=2 ch2=3 ch=5
6. ch1=3 ch2=5 ch=8
Цикл закончен
x - не число Фибоначчи

8. Найти количество чисел Фибоначчи в интервале [2, 6].
Программа с тестированием.

Решение: второй алгоритм поиска чисел Фибоначчи.

Ответ:
x=2
число Фибоначчи= 2 k=1

x=3
число Фибоначчи= 3 k=2

x=4
x - не число Фибоначчи

x=5
число Фибоначчи= 5 k=3

x=6
x - не число Фибоначчи

9. Найти количество чисел Фибоначчи в интервале [a, b].

Решение: второй алгоритм поиска чисел Фибоначчи.

Ответ:
первое число в заданном интервале=10
последнее число в заданном интервале=1000
число Фибоначчи= 13
число Фибоначчи= 21
число Фибоначчи= 34
число Фибоначчи= 55
число Фибоначчи= 89
число Фибоначчи= 144
число Фибоначчи= 233
число Фибоначчи= 377
число Фибоначчи= 610
число Фибоначчи= 987
k=10

program fib_09;
uses crt;
var ch, ch1, ch2, a, b, x, k :integer;

begin writeln('число Фибоначчи= ',ch-1); inc(k) end;

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

Иногда ряд начинают с нуля.

В данном случае мы будем придерживаться первого варианта.

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

Присвоим переменным fib1 и fib2 значения двух первых элементов ряда, то есть единицы.

Получим от пользователя номер элемента, значение которого требуется вычислить. Присвоим номер элемента переменной n .

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

Если пользователь вводит 1 или 2, тело цикла ни разу не выполняется, на экран выводится исходное значение fib2 .

Сложить fib1 и fib2 , присвоив результат переменной для временного хранения данных, например, fib_sum .
Переменной fib1 присвоить значение fib2 .
Переменной fib2 присвоить значение fib_sum .

После окончания работы цикла вывести значение fib2 на экран.

Пример выполнения программы:

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

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

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

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

Если n = 1 или n = 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.

Ряд чисел Фибоначчи представляет собой последовательность. Первый и второй элементы последовательности равны единице. Каждый последующий элемент равен сумме двух предыдущих. Рассмотрим разные способы нахождения элементов по номеру и генерацию списка с помощью Python 3.

Введение

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

Рассмотрим варианты получения ряда Фибоначчи на Python 3:

С помощью рекурсии.
Используя оператор цикла.

Также сгенерируем список чисел и создадим генератор с помощью которого можно поочередно получать числа.

Будем искать с помощью цикла for. В переменных prew и cur будут предыдущий элемент последовательности и текущий, их проинициализируем в 1. Если пользователь запросит первый или второй элемент, то мы так и не попадём внутрь тела цикла. И будет выведена единица из переменной cur .

Если же запросят 3-ий или какой либо последующий элемент последовательности Фибоначчи, то мы зайдем в цикл. Во временную переменную tmp сохраним следующее число последовательности. После этого заполним prew и cur новыми значениям. Когда пройдет нужное количество итераций, выведем значение cur в консоль.

В предыдущем коде нам пришлось воспользоваться переменной tmp . Но можно код внутри цикла переписать следующим образом:

Теперь вместо трех строк кода получилась одна строка! И пропала необходимость использования дополнительной переменной.

В этом примере мы использовали цикл for , но можно эту программу реализовать, немного изменив код, с помощью цикла while .

Рекурсия

В случае с рекурсией напишем функцию, аргументом которой будет требуемое число ряда Фибоначчи. Текущему значению последовательности cur вначале присвоим 1. После этого воспользуемся условным оператором языка Python – if . В нем проверим аргумент функции. Если он больше 2, то функция вызовет саму себя и вычислит предыдущее значение ряда, а так же то, которое было еще раньше и запишет в переменную cur их сумму.

Конечно, пример с рекурсией интересен. Но он будет работать гораздо медленнее.

А если вы решите вычислить, допустим 1000-ый элемент последовательности. Используя цикл, мы его очень быстро рассчитаем. А вот в случае с рекурсией получим ошибку превышения максимального количества рекурсий:

Генератор списка

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

Здесь fibonacci(10) это генератор объекта ряда размерностью 10. При каждом последующем вызове он будет с помощью yield возвращать очередной элемент. Мы создаём из него список. Затем выводим список в консоль с помощью функции print .

Если нам надо будет поочередно получать числа ряда, а не держать в памяти сразу весь список, то можно поступить следующим образом:

Здесь мы создали с помощью Python 3 генератор чисел Фибоначчи. При помощи функции next мы получаем поочередно числа ряда.

Программистам числа Фибоначчи должны уже поднадоесть. Примеры их вычисления используются везде. Всё от того, что эти числа предоставляют простейший пример рекурсии. А ещё они являются хорошим примером динамического программирования. Но надо ли вычислять их так в реальном проекте? Не надо. Ни рекурсия, ни динамическое программирование не являются идеальными вариантами. И не замкнутая формула, использующая числа с плавающей запятой. Сейчас я расскажу, как правильно. Но сначала пройдёмся по всем известным вариантам решения.

Код предназначен для Python 3, хотя должен идти и на Python 2.

Для начала – напомню определение:

Замкнутая формула

Пропустим детали, но желающие могут ознакомиться с выводом формулы. Идея в том, чтобы предположить, что есть некий x, для которого F_n = x n , а затем найти x.

Решаем квадратное уравнение:

Откуда и растёт «золотое сечение» ϕ=(1+√5)/2. Подставив исходные значения и проделав ещё вычисления, мы получаем:

что и используем для вычисления F_n.

Хорошее:
Быстро и просто для малых n
Плохое:
Требуются операции с плавающей запятой. Для больших n потребуется большая точность.
Злое:
Использование комплексных чисел для вычисления F_n красиво с математической точки зрения, но уродливо — с компьютерной.

Рекурсия

Самое очевидное решение, которое вы уже много раз видели – скорее всего, в качестве примера того, что такое рекурсия. Повторю его ещё раз, для полноты. В Python её можно записать в одну строку:

Хорошее:
Очень простая реализация, повторяющая математическое определение
Плохое:
Экспоненциальное время выполнения. Для больших n очень медленно
Злое:
Переполнение стека

Запоминание

У решения с рекурсией есть большая проблема: пересекающиеся вычисления. Когда вызывается fib(n), то подсчитываются fib(n-1) и fib(n-2). Но когда считается fib(n-1), она снова независимо подсчитает fib(n-2) – то есть, fib(n-2) подсчитается дважды. Если продолжить рассуждения, будет видно, что fib(n-3) будет подсчитана трижды, и т.д. Слишком много пересечений.

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

(В Python это можно также сделать при помощи декоратора, functools.lru_cache.)

Хорошее:
Просто превратить рекурсию в решение с запоминанием. Превращает экспоненциальное время выполнение в линейное, для чего тратит больше памяти.
Плохое:
Тратит много памяти
Злое:
Возможно переполнение стека, как и у рекурсии

Динамическое программирование

После решения с запоминанием становится понятно, что нам нужны не все предыдущие результаты, а только два последних. Кроме этого, вместо того, чтобы начинать с fib(n) и идти назад, можно начать с fib(0) и идти вперёд. У следующего кода линейное время выполнение, а использование памяти – фиксированное. На практике скорость решения будет ещё выше, поскольку тут отсутствуют рекурсивные вызовы функций и связанная с этим работа. И код выглядит проще.

Это решение часто приводится в качестве примера динамического программирования.

Хорошее:
Быстро работает для малых n, простой код
Плохое:
Всё ещё линейное время выполнения
Злое:
Да особо ничего.

Матричная алгебра

И, наконец, наименее освещаемое, но наиболее правильное решение, грамотно использующее как время, так и память. Его также можно расширить на любую гомогенную линейную последовательность. Идея в использовании матриц. Достаточно просто видеть, что

А обобщение этого говорит о том, что

Два значения для x, полученных нами ранее, из которых одно представляло собою золотое сечение, являются собственными значениями матрицы. Поэтому, ещё одним способом вывода замкнутой формулы является использование матричного уравнения и линейной алгебры.

Так чем же полезна такая формулировка? Тем, что возведение в степень можно произвести за логарифмическое время. Это делается через возведения в квадрат. Суть в том, что

где первое выражение используется для чётных A, второе для нечётных. Осталось только организовать перемножения матриц, и всё готово. Получается следующий код. Я организовал рекурсивную реализацию pow, поскольку её проще понять. Итеративную версию смотрите тут.

Хорошее:
Фиксированный объём памяти, логарифмическое время
Плохое:
Код посложнее
Злое:
Приходится работать с матрицами, хотя они не так уж и плохи

Сравнение быстродействия

Сравнивать стоит только вариант динамического программирования и матрицы. Если сравнивать их по количеству знаков в числе n, то получится, что матричное решение линейно, а решение с динамическим программированием – экспоненциально. Практический пример – вычисление fib(10 ** 6), числа, у которого будет больше двухсот тысяч знаков.

n = 10 ** 6
Вычисляем fib_matrix: у fib(n) всего 208988 цифр, расчёт занял 0.24993 секунд.
Вычисляем fib_dynamic: у fib(n) всего 208988 цифр, расчёт занял 11.83377 секунд.

Теоретические замечания

Не напрямую касаясь приведённого выше кода, данное замечание всё-таки имеет определённый интерес. Рассмотрим следующий граф:

Подсчитаем количество путей длины n от A до B. Например, для n = 1 у нас есть один путь, 1. Для n = 2 у нас опять есть один путь, 01. Для n = 3 у нас есть два пути, 001 и 101. Довольно просто можно показать, что количество путей длины n от А до В равно в точности F_n. Записав матрицу смежности для графа, мы получим такую же матрицу, которая была описана выше. Это известный результат из теории графов, что при заданной матрице смежности А, вхождения в А n — это количество путей длины n в графе (одна из задач, упоминавшихся в фильме «Умница Уилл Хантинг»).

Почему на рёбрах стоят такие обозначения? Оказывается, что при рассмотрении бесконечной последовательности символов на бесконечной в обе стороны последовательности путей на графе, вы получите нечто под названием "подсдвиги конечного типа", представляющее собой тип системы символической динамики. Конкретно этот подсдвиг конечного типа известен, как «сдвиг золотого сечения», и задаётся набором «запрещённых слов» . Иными словами, мы получим бесконечные в обе стороны двоичные последовательности и никакие пары из них не будут смежными. Топологическая энтропия этой динамической системы равна золотому сечению ϕ. Интересно, как это число периодически появляется в разных областях математики.

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

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

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

Сколько пар кроликов в течении года появится в питомнике? Для решения этой задачи вычисляют первые 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 включительно.

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

Читайте также: