Вопросы с просьбами помочь с отладкой («почему этот код не работает?») должны включать желаемое поведение, конкретную проблему или ошибку и минимальный код для её воспроизведения прямо в вопросе. Вопросы без явного описания проблемы бесполезны для остальных посетителей. См. Как создать минимальный, самодостаточный и воспроизводимый пример.
Закрыт 4 месяца назад .
Задание: для натурального числа n (в данном случае это 8 и 11) найти значение результата равного первым n чисел Фибоначчи. Я пытался сделать по такому коду, но оно вместо этого выводит 32 и 143. Второй результат правильный но первый почему-то нет:
int n0 = 0; int n1 = 1; int n2 = 1; int result = n; for(int i=2; i return result;
Отслеживать
задан 17 мар в 19:56
Maksym Morkhovskyi Maksym Morkhovskyi
Какой результат ожидается? Ну и выведи свои числа на экран, увидишь, что они совсем не числа Фиббоначчи.
17 мар в 20:11
3 ответа 3
Сортировка: Сброс на вариант по умолчанию
Как известно, сумма N чисел Фибоначчи от F(1) до F(N) равна F(N + 2) — 1, поэтому для её вычисления достаточно вызвать метод для вычисления обычного числа Фибоначчи.
Числа Фибоначчи. Решение задачи на Python
public static long sumF(long n) < return fib(n + 2) — 1; // или fibRec(n + 2) — 1 >// рекурсивное вычисление public static long fibRec(long n) < if (n < 2) return n; return fibRec(n — 1) + fibRec(n — 2); >// итеративное вычисление public static long fib(long n) < if (n < 2) return n; long a = 0, b = 1, f = 1; for (int i = 1; i < n; i++) < f = a + b; a = b; b = f; >return f; >
System.out.println(sumFib(8)); // -> 54 System.out.println(sumFib(11)); // -> 232
Для вычисления суммы N чисел, начиная с F(0) = 0, достаточно изменить формулу на F(N + 1) — 1 :
public static long sumFfrom0(long n) < return fib(n + 1) — 1; // или fibRec(n + 1) — 1 >
Отслеживать
ответ дан 17 мар в 21:26
Nowhere Man Nowhere Man
12.3k 20 20 золотых знаков 17 17 серебряных знаков 27 27 бронзовых знаков
Давайте посчитаем сумму первых чисел Фибоначчи.
У ряда есть два варианта, оба встречаются часто, поэтому мы можем выбрать любой. Первый ряд начинается с 0, 1, 1, 2. ; второй — с 1, 1, 2, 3.
Пусть у нас будет первый ряд.
| 1 | 1 | 1 |
| 2 | 1 | 2 |
| 3 | 2 | 4 |
| 4 | 3 | 7 |
| 5 | 5 | 12 |
| 6 | 8 | 20 |
| 7 | 13 | 33 |
| 8 | 21 | 54 |
| 9 | 34 | 88 |
Числа Фибоначчи
Числа Фибоначчи – это ряд чисел, в котором каждое последующее число равно сумме двух предыдущих:
7.3 Последовательность Фибоначчи. «Поколение Python»: курс для начинающих. Курс Stepik
1, 1, 2, 3, 5, 8, 13 и т. д.
То есть последовательность всегда начинается с двух единиц. А каждое следующее число является определяется по формуле:
Для определения чисел Фибоначчи часто используется рекурсивный алгоритм:
- Если n = 1 или n = 2, вернуть 1 (поскольку первый и второй элементы ряда Фибоначчи равны 1).
- Вызвать рекурсивно функцию с аргументами n-1 и n-2.
- Результат двух вызовов сложить и вернуть полученное значение.
Реализация с использованием рекурсии
Реализация на Си
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define _CRT_SECURE_NO_WARNINGS
#include
int fibonacci( int N) // рекурсивная функция
if (N == 1 || N == 2)
return 1; // первые 2 числа равны 1
return fibonacci(N — 1) + fibonacci(N — 2); // складываем предыдущие 2 числа
>
int main()
int N;
printf( «N=» );
scanf( «%d» , // вводим число N
for ( int i = 1; i printf( «%d » , fibonacci(i));
getchar(); getchar();
return 0;
>
Результат выполнения
У решения с рекурсией есть большая проблема: пересекающиеся вычисления. Когда вызывается fibonacci(N) , то подсчитываются значения функции N-1 и для N-2 . Но если требуется вычислить fibonacci(N-1) , то значения для N-2 и N-3 вычисляются заново.
Поэтому поставленную задачу определения чисел Фибоначчи можно решить без использования рекурсии.
Реализация с использованием цикла
В этом алгоритме используется свойство, что для определения следующего числа Фибоначчи используются только два предыдущих значения.
Алгоритм при этом будет следующий
- Ввести номер N определяемого элемента.
- Проинициализировать два первых элемента a и b значениями 1, и если N
- Выполнять нижеследующие действия N-2 раза
- Сложить a и b, присвоив результат третьей переменной c.
- Поменять начальные значения: a = b, b = c
Реализация на Си
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include
int main()
int N;
printf( «N=» ); // вводим число N
scanf( «%d» ,
int a = 1, b = 1, c;
if (N printf( «1 » );
else
for ( int i = 3; i c = a + b; // вычисляем следующее число как сумму двух предыдущих
a = b; b = c; // перемещаем два предыдущих числа
>
printf( «%d » , b); // выводим последнее число
>
getchar(); getchar();
return 0;
>
Источник: prog-cpp.ru
Числа Фибоначчи на Python
Статьи
Автор Admin На чтение 3 мин Просмотров 193к. Опубликовано 27.05.2022
Введение
В статье разберём 3 способа получения ряда Фибоначчи на Python. Первые два способа будут с использованием циклов, а третий – рекурсивный.
Числа Фибоначчи – бесконечная последовательность чисел, каждое из которых является суммой двух предыдущих и так до бесконечности.
F_ = F_+F_
Числа Фибоначчи циклом while
Для начала создадим переменную, в которую будет вводиться длина ряда:
n = int(input(‘Введите длину ряда: ‘))
Далее создадим две переменные (f1 и f2), которые будут равняться начальным единицам и выведем их:
f1 = f2 = 1 print(f1, f2, end=’ ‘)
Создадим переменную i, которая будет равняться двум:
i = 2
Добавим цикл, который не закончится, пока переменная i будет меньше переменной n:
while i < n: f1, f2 = f2, f1 + f2 # f1 приравнивается к f2, f2 приравнивается к f1 + f2 print(f2, end=’ ‘) # Выводится f2 i += 1 print()
Числа Фибоначчи на Python:
n = int(input(‘Введите длину ряда: ‘)) f1 = f2 = 1 print(f1, f2, end=’ ‘) i = 2 while i < n: f1, f2 = f2, f1 + f2 # f1 приравнивается к f2, f2 приравнивается к f1 + f2 print(f2, end=’ ‘) # Выводится f2 i += 1 print()
Числа Фибоначчи циклом for
Создадим переменную, в которую будет вводиться длина ряда:
n = int(input(‘Введите длину ряда: ‘))
Далее создадим две переменные (f1 и f2), которые будут равняться начальным единицам и выведем их:
f1 = f2 = 1 print(f1, f2, end=’ ‘)
Добавим цикл, который начинается с 2, и заканчивается на n:
for i in range(2, n): f1, f2 = f2, f1 + f2 # f1 приравнивается к f2, f2 приравнивается к f1 + f2 print(f2, end=’ ‘) # Выводится f2
Числа Фибоначчи на Python:
n = int(input(‘Введите длину ряда: ‘)) f1 = f2 = 1 print(f1, f2, end=’ ‘) for i in range(2, n): f1, f2 = f2, f1 + f2 print(f2, end=’ ‘)
Числа Фибоначчи рекурсией
Для начала создадим рекурсивную функцию, назовём её fibonacci и добавим ей параметр n:
def fibonacci(n):
Добавим условие, что если n = 1, или n = 2, то возвращается единица, так как первый и второй элементы ряда Фибоначчи равны единице. Если же условие не срабатывает, то элементы складываются:
def fibonacci(n): if n == 1 or n == 2: # Если n = 1, или n = 2, вернуть в вызывающую ветку единицу, так как первый и второй элементы ряда Фибоначчи равны единице. return 1 return fibonacci(n — 1) + fibonacci(n — 2)
Числа Фибоначчи на Python:
def fibonacci(n): if n == 1 or n == 2: return 1 return fibonacci(n — 1) + fibonacci(n — 2) n = int(input()) print(fibonacci(n))
В данной статье мы научились вычислять n-ное число ряда Фибоначчи на Python. Надеюсь Вам понравилась статья, удачи!
Источник: it-start.online