Определите n-е число Фибоначчи

@nameee22 · Регистрация: 31.03.2022

Студворк — интернет-сервис помощи студентам

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

Yuri V · 27.09.2022, 01:12

Например,

Python
1
2
3
4
5
6
7
def fibo(n):
    if n < 1: return -1 # print('ОШИБКА')
    if n == 1: return 0
    if n == 2: return 1
    return fibo(n-1)+fibo(n-2)
    
for i in range(0,21):print(i,fibo(i))

@Catstail · 27.09.2022, 10:59

Yuri V, ох...

Yuri V · 27.09.2022, 13:46

Catstail, да ладно, для школы пойдёт, - главное, чтобы целые аргументы и правильные результаты, хотя можно и закешировать.

Ну и по-феншую заменить

Python
1
2
if n == 1: return 0
if n == 2: return 1

на if 0<n<3: return n.

Или же принципиальная ошибка?

@eaa · 27.09.2022, 13:49

Сообщение от Yuri V

0<n<3

а смысл, что больше нуля проверять?

@Catstail · 27.09.2022, 14:17

Сообщение от Yuri V

Или же принципиальная ошибка?

- Принципиальных ошибок нет. Просто код неэффективный. Да кэширование бы помогло.

Yuri V · 27.09.2022, 14:56

Кроме принципа правильности, для реального применения важна эффективность, а для учёбы - простота и наглядность.
Вроде логика простая и формула понятна, хотя зарекаться не буду.

Не по теме:

Как-то племяннику выдали "новую" книгу по математике, где вместо конкретной фразы "посчитайте/сделайте правильно" просто говорилось "посчитайте/сделайте". Формально верно, а по существу директору на родительском собрании пришлось несколько раз уточнять. А сейчас такое ощущение, будто большинство до сих пор соблюдают принцип "просто как-то сделать".

@Red white socks · 27.09.2022, 17:47

Сообщение от Yuri V

if n == 1: return 0

А каким указом первое число Фибоначчи стало нулем?
Упустил этот момент.

Сообщение от Yuri V

Ну и по-феншую заменить
...
на if 0<n<3: return n.

Очень странное у вас представление о феншуе.
Не говоря уже о том, что это просто неверно.

Yuri V · 27.09.2022, 19:58

А, я-то думал смущает обработка без исключений, а сам себя перехитрил.

Частично одобренный вариант без рекурсии

Python
1
2
3
4
5
6
7
8
9
10
11
12
def Fibi(n):
    if n < 1: return 0 # отсечение
    
    n = int(n) - 2
    f1 = f2 = 1
    
    while n>0:
        f1, f2 = f2, f1 + f2 # сумма
        n -= 1 # сдвиг
    return f2
 
for i in range(-2, 21): print(i, Fibi(i))

@Parramon · 28.09.2022, 12:26

Yuri V, вариант без рекурсии (и вообще без циклов)

Python
1
2
def fibo(n):
    return (((1+5**0.5)/2)**n-((1-5**0.5)/2)**n)/5**0.5

Yuri V · 28.09.2022, 13:23

Parramon, ряд с корнями красиво, но какая это тема в школе или вузе?

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

@Parramon · 28.09.2022, 15:02

Yuri V, естественно, не сам. Университетские знания еще пока остались. Но можно открыть Википедию, там есть эта формула (и её вывод, кстати, тоже).

@eaa · 28.09.2022, 15:06

пора вариант с бинарным возведением в степень матрицы за логорифм предлагать

@Red white socks · 28.09.2022, 15:30

Parramon, уверен, что эта формула не работает, начиная с некоторого n и думаю даже не очень большого

Добавлено через 3 минуты
Уточнение. Формула Бине конечно верна для любого n. Но по написанному коду результат вы получите так себе...

@Parramon · 28.09.2022, 15:42

Red white socks, что значит "так себе"? Я либо получу n-ный член ряда Фибоначчи, либо не получу. Я свой код запускал и получал. Что не так-то?
ПыСы Про время счета я еще молчу...

@Red white socks · 28.09.2022, 15:49

Сообщение от Parramon

Red white socks, что значит "так себе"?

Ну во-первых вы возвращаете результат float. Но это не главная беда.
Беда вот:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def fibo(n):
    return (((1+5**0.5)/2)**n-((1-5**0.5)/2)**n)/5**0.5
 
def fibo2(n):
 
    f1,f2 = 1, 1
    for _ in range(n-2):
        f1,f2 = f1+f2,f1
    return f1
 
n = 72
print('n = {}: Бине {}, истинный {}'.format(n, fibo(n), fibo2(n)))
 
#n = 72: Бине 498454011879265.2, истинный 498454011879264

Yuri V · 28.09.2022, 22:12

Red white socks, хотя вряд ли понадобятся такие большие значения, но for n in range(70,101):print(fibo(n)-fibo2(n)) наглядно.

Можно как-то формулу перетусовать или мантисса не для таких целей?

@Red white socks · 28.09.2022, 22:33

Yuri V, для прямого применения требуется вычислять корень из 5 с очень большой точностью, а затем с этой же точностью возводить в степень, а также производить деление. Так что про этот путь можно забыть.
Чисто теоретически с помощью этой формулы можно получать числа Фибоначчи, если вести вычисления в арифметике $https://www.cyberforum.ru/cgi-bin/latex.cgi?Z\left[\sqrt5 \right]$ . Но фишка в том, что по сути это сводится к матричному умножению. А через матричное умножение можно действовать напрямую из определения чисел Ф., без всякой формулы Бине.

Yuri V · 29.09.2022, 00:12

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

Python
1
2
3
4
5
6
7
8
9
from functools import lru_cache
 
@lru_cache
def fib(n):
    if n < 2: return n
    else: return fib(n - 1) + fib(n - 2);
    
for i in range(-1,101):print(i,fib(i)) 
print(fib.cache_info())

Можно даже @functools.lru_cache(maxsize=256), хотя сомневаюсь, что будет достаточно реальных попаданий.

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! в-строка - входное арифметическое выражение в инфиксной(обычной). . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@nameee22 0 / 0 / 0 Регистрация: 31.03.2022 Сообщений: 11

	Определите n-е число Фибоначчи 26.09.2022, 23:02. Показов 5176. Ответов 18 Метки python, python 1курс (Все метки) По введенному пользователю целым числом n, определите n-е число Фибоначчи. 0

@Catstail Супер-модератор 38173 / 21108 / 4307 Регистрация: 12.02.2012 Сообщений: 34,709 Записей в блоге: 14
	27.09.2022, 10:59
	Yuri V, ох... 0

Yuri V 259 / 205 / 60 Регистрация: 25.05.2022 Сообщений: 879
	27.09.2022, 14:56
	Кроме принципа правильности, для реального применения важна эффективность, а для учёбы - простота и наглядность. Вроде логика простая и формула понятна, хотя зарекаться не буду. Не по теме: Как-то племяннику выдали "новую" книгу по математике, где вместо конкретной фразы "посчитайте/сделайте правильно" просто говорилось "посчитайте/сделайте". Формально верно, а по существу директору на родительском собрании пришлось несколько раз уточнять. А сейчас такое ощущение, будто большинство до сих пор соблюдают принцип "просто как-то сделать". 0

Yuri V 259 / 205 / 60 Регистрация: 25.05.2022 Сообщений: 879
	28.09.2022, 13:23
	Parramon, ряд с корнями красиво, но какая это тема в школе или вузе? Я пока не записал в нормальной форме и не подставил контрольные значения не сразу понял, и что-то сомневаюсь, что вы сами к этому пришли. 0

@Parramon 740 / 622 / 151 Регистрация: 04.03.2022 Сообщений: 1,272
	28.09.2022, 15:02
	Yuri V, естественно, не сам. Университетские знания еще пока остались. Но можно открыть Википедию, там есть эта формула (и её вывод, кстати, тоже). 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	28.09.2022, 15:06
	пора вариант с бинарным возведением в степень матрицы за логорифм предлагать 1

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	28.09.2022, 15:30
	Parramon, уверен, что эта формула не работает, начиная с некоторого n и думаю даже не очень большого Добавлено через 3 минуты Уточнение. Формула Бине конечно верна для любого n. Но по написанному коду результат вы получите так себе... 0

@Parramon 740 / 622 / 151 Регистрация: 04.03.2022 Сообщений: 1,272
	28.09.2022, 15:42
	Red white socks, что значит "так себе"? Я либо получу n-ный член ряда Фибоначчи, либо не получу. Я свой код запускал и получал. Что не так-то? ПыСы Про время счета я еще молчу... 0

Yuri V 259 / 205 / 60 Регистрация: 25.05.2022 Сообщений: 879
	28.09.2022, 22:12
	Red white socks, хотя вряд ли понадобятся такие большие значения, но `for n in range(70,101):print(fibo(n)-fibo2(n))` наглядно. Можно как-то формулу перетусовать или мантисса не для таких целей? 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	28.09.2022, 22:33
	Yuri V, для прямого применения требуется вычислять корень из 5 с очень большой точностью, а затем с этой же точностью возводить в степень, а также производить деление. Так что про этот путь можно забыть. Чисто теоретически с помощью этой формулы можно получать числа Фибоначчи, если вести вычисления в арифметике $https://www.cyberforum.ru/cgi-bin/latex.cgi?Z\left[\sqrt5 \right]$ . Но фишка в том, что по сути это сводится к матричному умножению. А через матричное умножение можно действовать напрямую из определения чисел Ф., без всякой формулы Бине. 2