Числа фибоначчи. Не понятно почему выбраны числа 1 и 2

@Undisputed · Регистрация: 10.06.2014

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

Есть код фибоначчи:

C++

unsigned int fibonacci( unsigned int n )
{
    return n < 2 ? n : fibonacci( n - 2 ) + fibonacci( n - 1 );
}
 
int main() 
{
    const unsigned int N = 6;
 
    std::cout << fibonacci(N);
 
    return 0;
}

http://rextester.com/CJINE90819

Как это работает мне понятно. Передаем число в функцию, относительно которого нужно получить число по принципу фибоначчи. Упираемся в единички и нули а далее прекращается рекурсия и единички/нули всех вызовов складываются.
Но не понятно почему выбраны именно следующие вычисления n - 2 и n - 1. Почему не n-5 например?
Не получается уловить общую суть. С точки зрения вычислений все ясно. Но с логической точки зрения не понятно.

Допустим код выше для числа 6 выводит 8. Единственный вариант который пришел в голову по поводу (n - 2) + (n - 1) это получение двух предыдущих чисел от переданного числа. Давайте считать.(6 - 2) + (6 - 1) = (4 + 5) = 9 но никак не 8.

Отсюда возникает вопрос, что происходит на самом деле?

Добавлено через 24 минуты
По логике подходит следующее:

C++

int n = 6;
int n1 = n - 1;//(6 -1) = 5
int n2 = n1 - 2;//5 - 2 = 3
int result = n1 + n2;//5 + 3 = 8

но в примере выше изменения производятся над копией и поэтому получается 9 а не 8...

@afront · 13.10.2017, 21:17

C++

1	int result = fibonacci(n1) + fibonacci(n2);

@Undisputed · 13.10.2017, 21:25 **[ТС]**

afront,
Посмотрел... а можно словами?

Байт · 13.10.2017, 21:44

Undisputed, вы путаете 2 разные вещи. n и fibonacci(n). А это ведь вещи разные

@Undisputed · 13.10.2017, 21:51 **[ТС]**

Байт,
Да, разные. Вот я пытаюсь просто разобраться почему именно n - 2 и n - 1. В чем заключается логика...)

Байт · 13.10.2017, 21:54

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

почему именно n - 2 и n - 1. В чем заключается логика...)

В определении чисел фибоначчи.
F_n = F_n-1 + F_n-2

@mat_for_c · 13.10.2017, 22:03

сама последовательность выглядит так: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
рекурсия же возвращается от вашего числа N к самым первым элементам последовательности, а потом их суммирует в восходящем порядке.

@Undisputed · 13.10.2017, 22:22 **[ТС]**

Байт,
mat_for_c,
То, что вы сказали я понимаю и сам писал об этом в первом сообщении

Вопрос был немного другой

@mat_for_c · 13.10.2017, 22:40

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

Давайте считать.(6 - 2) + (6 - 1) = (4 + 5) = 9 но никак не 8.

ваша логика соответствует этому коду:

C++

1
2
3

foo(int N) {
   return N < 2 ? N : N-2 + N-1;
}

Замечаете разницу?

@Undisputed · 13.10.2017, 22:50 **[ТС]**

mat_for_c,
Да, вы правы.
В функцию мы передаём количество чисел, которое нужно вывести используя рекурсию. Ок с этим разобрались.

Но какова логика вычисления? На чем она основана?
Вот пришло в функцию 6, то есть хотим выстроить последовательность из 6 чисел.
Почему выбраны именно эти числа n-1 и n-2? Что это даёт?
Дерево вызовов я уже смотрел.
Не методом "тыка" же подобраны эти числа?
Вот мне интересно на чем основан выбор этих чисел при рекурсивных вызовах.

@mat_for_c · 13.10.2017, 23:07

Байт вам это уже написал: $https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{n}={F}_{n-2}+{F}_{n-1}$ - рекуррентная формула чисел Фибоначчи
вызов fibonacci(N) соответствует $https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{n}$ , а дальше все понятно, откуда берется fibonacci(N-1) и fibonacci(N-2)

@Undisputed · 13.10.2017, 23:58 **[ТС]**

mat_for_c,
В том то и дело что не понятно. Может быть у вас математический уклон поэтому вам и понятно...
Но в моем случае это не так. Не могу понять на чем основан выбор чисел n - 1 и n - 2 для рекурсивных вызовов и как эти цифры связаны с количеством чисел в результирующем наборе (т.е с аргументом функции).
тот кто писал эту функцию наверное сделал сначала вывод основываясь на чем то конкретном а потом уже ему стало "понятно" и была написана такая функция...
Вот именно это и интересует. Интересует основание, исходя из которого можно сделать вывод об оптимальности данных операций для рекурсивного решения.

Добавлено через 1 минуту
Сначала думаю была идея а потом формула а не наоборот...

@mat_for_c · 14.10.2017, 00:29

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

на чем основан выбор чисел n - 1 и n - 2

просто примите факт того, что каждое последующее n-ное число равно сумме двух предыдущих чисел, n-1 и n-2 - это как раз их номера.

0;
1;
0 + 1 = 1; $https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{0} + {F}_{1} = {F}_{2}$
1 + 1 = 2; $https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{1} + {F}_{2} = {F}_{3}$
1 + 2 = 3; $https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{2} + {F}_{3} = {F}_{4}$
2 + 3 = 5; $https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{3} + {F}_{4} = {F}_{5}$
3 + 5 = 8; $https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{4} + {F}_{5} = {F}_{6}$
5 + 8 = 13; $https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{5} + {F}_{6} = {F}_{7}$
и т.д.

@Undisputed · 14.10.2017, 00:45 **[ТС]**

mat_for_c,
Возможно я уже надоел, но реально не понятно...
Вот есть входящее число 6 которое определяет количество чисел в результирующей последовательности.

1) Не получается уловить то, как связано количество нужных чисел в результирующем наборе и само вычисление.
2) Можно конечно тупо "знать" что это работает, потому что есть такая формула... но понимания при этом не будет...

6 - 1 это первое число которое идёт перед 6, 6 - 2 это второе число которое находится перед 6.
Итого получаем 4 5 и 6. (При первом вызове).
Но это два предыдущих числа относительно исходного числа 6, которое определяет количество чисел в результирующем наборе.
А фибоначчи подразумевает то, что каждое число равно сумме двух предыдущих чисел.

При 4 5 и 6 к которому я пришёл выше, вместо 6 должно быть 9 т.к сумма двух предыдущих чисел равна 9.
Значит это вычисление не имеет прямого отношения к Фибоначчи, ну не похоже ни разу.

Не понимаю что стоит за этим самым "спуском до единичек" и их суммированием. Ведь кто то просчитал какое дерево должно получиться и что единички как раз будут в том количестве что бы выдать правильный результат... Но как он это просчитал?
Вот основной вопрос...

Пока не могу додуматься

Добавлено через 3 минуты
Возможно тут какой то простой нюанс который просто ускользнул от меня....

@mat_for_c · 14.10.2017, 01:18

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

6 - 1 это первое число которое идёт перед 6, 6 - 2 это второе число которое находится перед 6.

вы опять возвращаетесь к своей логике

C++

1
2
3

foo(int N) {
   return N < 2 ? N : N-2 + N-1;
}

вы подаете на вход программе 6. вызывается fibonacci(6) - это соответствует $https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{6}$ , где 6 - это номер числа в последовательности, а не просто число 6 из множества натуральных чисел.
имеем:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{6} = {F}_{4} + {F}_{5} = {F}_{2} + {F}_{3} + {F}_{5} = {F}_{0} + {F}_{1} + {F}_{3} + {F}_{5}=<br /> 0 + 1 + {F}_{1} + {F}_{2} + {F}_{5} = 1 + 1 + {F}_{0} + {F}_{1} + {F}_{5} = 2 + 0 + 1 + {F}_{5} = <br /> 3 + {F}_{3} + {F}_{4} = 3 + {F}_{1} + {F}_{2} + {F}_{4} = 3 + 1 + {F}_{0} + {F}_{1} + {F}_{4} = <br /> 4 + 0 + 1 + {F}_{2} + {F}_{3} = 5 + {F}_{0} + {F}_{1} + {F}_{3} = 5 + 0 + 1 + {F}_{1} + {F}_{2} = <br /> 6 + 1 + {F}_{0} + {F}_{1} = 7 + 0 + 1 = 8$
вот ваша рекурсия для шестого числа фибоначчи

@likehood · 14.10.2017, 08:54

Чтобы понять рекурсию, нужно понять рекурсию ...

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

Ведь кто то просчитал какое дерево должно получиться и что единички как раз будут в том количестве что бы выдать правильный результат... Но как он это просчитал?

Думаю, ничего он не считал. Он просто познал дао рекурсии.

А если серьёзно, то для меня прелесть рекурсии в том и состоит, что можно не думать о том как именно будут разворачиваться рекурсивные вызовы на низком уровне. Достаточно написать рекурсивную формулу и граничные значения, основываясь на математическом описании задачи. А остальное за нас сделает компилятор. Как именно сделает - это его проблемы, но если мы правильно перенесли математические формулы на язык С++, то результат обязательно будет верным.

Другое дело, если нам важна оптимальность - в этом случае знание деталей реализации действительно может быть полезным. Но это уже тема для отдельного разговора.

@Undisputed · 14.10.2017, 10:30 **[ТС]**

mat_for_c,
Номер числа какой последовательности?
Например когда считается Фибоначчи для 6, в результирующей последовательности это число отсутствует

Добавлено через 1 минуту
Ааа сори понял. Речь идет о последовательности Фибоначчи. Совсем запутался... Спасибо

@mat_for_c 223 / 213 / 80 Регистрация: 26.04.2013 Сообщений: 972
	13.10.2017, 23:07	11
	Байт вам это уже написал: $https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{n}={F}_{n-2}+{F}_{n-1}$ - рекуррентная формула чисел Фибоначчи вызов `fibonacci(N)` соответствует $https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{n}$ , а дальше все понятно, откуда берется `fibonacci(N-1)` и `fibonacci(N-2)` 0

@Undisputed 875 / 461 / 91 Регистрация: 10.06.2014 Сообщений: 2,669
	13.10.2017, 23:58 [ТС]	12
	mat_for_c, В том то и дело что не понятно. Может быть у вас математический уклон поэтому вам и понятно... Но в моем случае это не так. Не могу понять на чем основан выбор чисел n - 1 и n - 2 для рекурсивных вызовов и как эти цифры связаны с количеством чисел в результирующем наборе (т.е с аргументом функции). тот кто писал эту функцию наверное сделал сначала вывод основываясь на чем то конкретном а потом уже ему стало "понятно" и была написана такая функция... Вот именно это и интересует. Интересует основание, исходя из которого можно сделать вывод об оптимальности данных операций для рекурсивного решения. Добавлено через 1 минуту Сначала думаю была идея а потом формула а не наоборот... 0

@likehood 1272 / 1029 / 470 Регистрация: 25.12.2016 Сообщений: 3,333
	14.10.2017, 08:54	16
	Чтобы понять рекурсию, нужно понять рекурсию ... Сообщение от Undisputed Ведь кто то просчитал какое дерево должно получиться и что единички как раз будут в том количестве что бы выдать правильный результат... Но как он это просчитал? Думаю, ничего он не считал. Он просто познал дао рекурсии. А если серьёзно, то для меня прелесть рекурсии в том и состоит, что можно не думать о том как именно будут разворачиваться рекурсивные вызовы на низком уровне. Достаточно написать рекурсивную формулу и граничные значения, основываясь на математическом описании задачи. А остальное за нас сделает компилятор. Как именно сделает - это его проблемы, но если мы правильно перенесли математические формулы на язык С++, то результат обязательно будет верным. Другое дело, если нам важна оптимальность - в этом случае знание деталей реализации действительно может быть полезным. Но это уже тема для отдельного разговора. 1

@Undisputed 875 / 461 / 91 Регистрация: 10.06.2014 Сообщений: 2,669
	13.10.2017, 21:25 [ТС]	3
	afront, Посмотрел... а можно словами? 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	13.10.2017, 21:44	4
	Undisputed, вы путаете 2 разные вещи. n и fibonacci(n). А это ведь вещи разные 1

@Undisputed 875 / 461 / 91 Регистрация: 10.06.2014 Сообщений: 2,669
	13.10.2017, 21:51 [ТС]	5
	Байт, Да, разные. Вот я пытаюсь просто разобраться почему именно n - 2 и n - 1. В чем заключается логика...) 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	13.10.2017, 21:54	6
	Сообщение от Undisputed почему именно n - 2 и n - 1. В чем заключается логика...) В определении чисел фибоначчи. F_n = F_n-1 + F_n-2 0

@mat_for_c 223 / 213 / 80 Регистрация: 26.04.2013 Сообщений: 972
	13.10.2017, 22:03	7
	сама последовательность выглядит так: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... рекурсия же возвращается от вашего числа N к самым первым элементам последовательности, а потом их суммирует в восходящем порядке. 0

@Undisputed 875 / 461 / 91 Регистрация: 10.06.2014 Сообщений: 2,669
	13.10.2017, 22:22 [ТС]	8
	Байт, mat_for_c, То, что вы сказали я понимаю и сам писал об этом в первом сообщении Вопрос был немного другой 0

@Undisputed 875 / 461 / 91 Регистрация: 10.06.2014 Сообщений: 2,669
	13.10.2017, 22:50 [ТС]	10
	mat_for_c, Да, вы правы. В функцию мы передаём количество чисел, которое нужно вывести используя рекурсию. Ок с этим разобрались. Но какова логика вычисления? На чем она основана? Вот пришло в функцию 6, то есть хотим выстроить последовательность из 6 чисел. Почему выбраны именно эти числа n-1 и n-2? Что это даёт? Дерево вызовов я уже смотрел. Не методом "тыка" же подобраны эти числа? Вот мне интересно на чем основан выбор этих чисел при рекурсивных вызовах. 0

@mat_for_c 223 / 213 / 80 Регистрация: 26.04.2013 Сообщений: 972
	14.10.2017, 00:29	13
	Сообщение от Undisputed на чем основан выбор чисел n - 1 и n - 2 просто примите факт того, что каждое последующее `n-ное` число равно сумме двух предыдущих чисел, `n-1` и `n-2` - это как раз их номера. 0; 1; 0 + 1 = 1; $https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{0} + {F}_{1} = {F}_{2}$ 1 + 1 = 2; $https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{1} + {F}_{2} = {F}_{3}$ 1 + 2 = 3; $https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{2} + {F}_{3} = {F}_{4}$ 2 + 3 = 5; $https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{3} + {F}_{4} = {F}_{5}$ 3 + 5 = 8; $https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{4} + {F}_{5} = {F}_{6}$ 5 + 8 = 13; $https://www.cyberforum.ru/cgi-bin/latex.cgi?{F}_{5} + {F}_{6} = {F}_{7}$ и т.д. 1

@Undisputed 875 / 461 / 91 Регистрация: 10.06.2014 Сообщений: 2,669
	14.10.2017, 00:45 [ТС]	14
	mat_for_c, Возможно я уже надоел, но реально не понятно... Вот есть входящее число 6 которое определяет количество чисел в результирующей последовательности. 1) Не получается уловить то, как связано количество нужных чисел в результирующем наборе и само вычисление. 2) Можно конечно тупо "знать" что это работает, потому что есть такая формула... но понимания при этом не будет... 6 - 1 это первое число которое идёт перед 6, 6 - 2 это второе число которое находится перед 6. Итого получаем 4 5 и 6. (При первом вызове). Но это два предыдущих числа относительно исходного числа 6, которое определяет количество чисел в результирующем наборе. А фибоначчи подразумевает то, что каждое число равно сумме двух предыдущих чисел. При 4 5 и 6 к которому я пришёл выше, вместо 6 должно быть 9 т.к сумма двух предыдущих чисел равна 9. Значит это вычисление не имеет прямого отношения к Фибоначчи, ну не похоже ни разу. Не понимаю что стоит за этим самым "спуском до единичек" и их суммированием. Ведь кто то просчитал какое дерево должно получиться и что единички как раз будут в том количестве что бы выдать правильный результат... Но как он это просчитал? Вот основной вопрос... Пока не могу додуматься Добавлено через 3 минуты Возможно тут какой то простой нюанс который просто ускользнул от меня.... 0

@Undisputed 875 / 461 / 91 Регистрация: 10.06.2014 Сообщений: 2,669
	14.10.2017, 10:30 [ТС]	17
	mat_for_c, Номер числа какой последовательности? Например когда считается Фибоначчи для 6, в результирующей последовательности это число отсутствует Добавлено через 1 минуту Ааа сори понял. Речь идет о последовательности Фибоначчи. Совсем запутался... Спасибо 0