Задача: Fibonacci
Къде е грешката в кода ми задачата е:
0.Числа на Фибоначи
Напишете програма, която въвежда цяло число n и пресмята n-тото число на Фибоначи. Нулевото число на Фибоначи е 1, първото е също 1, а всяко следващо е сумата от предходните две. Примери:
|
вход |
изход |
|
вход |
изход |
|
вход |
изход |
|
вход |
изход |
|
вход |
изход |
|
0 |
1 |
1 |
1 |
2 |
2 |
5 |
8 |
10 |
89 |
using System;
namespace ConsoleInputOutput
{
public static class Fibonachi
{
public static void Main()
{
int n = int.Parse(Console.ReadLine());
if (n < 1) Console.WriteLine(0);
else
{
int first = 0;
int second = 1;
Console.WriteLine(first);
Console.WriteLine(second);
int third = 0;
for (int i = 2; i < n; i++)
{
third = first + second;
Console.Write(third + " ");
first = second;
second = third;
}
}
}
}
}
И колко неподходяща е за този проблем. Като при рекурсивното решение без memoization, ако трябва да изчислим F(7) => F(5) се изчислява 2 пъти, F(4) => 3 пъти, F(2) => 8 пъти и т.н. Представи си ако трябва да изчислим F(45) какво се случва.
Не се изразих много окей. Че е бавна, бавна е, но фибоначи е перфектната задача за да се разбере рекурсията.
Да. Мога да се съглася, че е една от задачите с които може да се демонстрира рекурсията :)
Работи се лесно, защото редицата на Фибоначи е частен случай на т. нар. "числа на Лукас", които се задават чрез рекурентна релация. Когато такава отсъства в описанието на задачата, приложението на рекурсията се усложнява значително. Освен това, редицата на Фибоначи не е добър пример за приложението на рекурсията, поради експоненциалната изчислителна сложност и измамно лесното й написване, което прикрива неприятните детайли. По-добър пример би бил употребата й при обхождането на двойчно дърво, където са на показ ефективността на рекурсията и елегантността на решението.