Вычисление чисел Фибоначчи: различия между версиями
Нет описания правки |
Drawiz (обсуждение | вклад) откат вандализма |
||
Строка 1: | Строка 1: | ||
== Постановка задачи == |
|||
'''Искусственное дыхание''' — комплекс мер, направленных на поддержание оборота воздуха через легкие у человека (или животного), переставшего дышать. Может производиться с помощью аппарата искусственного дыхания, либо человеком (дыхание изо рта в рот). Обычно совмещается с [[искусственный массаж сердца|искусственным массажем сердца]]. Типичные ситуации, в которых требуется искусственное дыхание: несчастные случаи в результате автомобильных аварий, происшествия на воде, поражение электрическим током, утопление. Аппарат искусственного дыхания используется также в хирургических операциях. |
|||
Вычислить <math>F_n</math>, где <math>F_n</math> — <math>n</math>-е [[w:Числа Фибоначчи|число Фибоначчи]], задаваемое [[w:Рекуррентная последовательность|рекуррентным]] соотношением: |
|||
* <math> F_1 = 1 </math> |
|||
* <math> F_2 = 1 </math> |
|||
* <math> F_n = F_{n - 1} + F_{n - 2}</math>, n > 2 |
|||
== Рекурсивное решение == |
|||
=== Искусственное дыхание «рот-в-рот» === |
|||
Если напрямую написать решение этой задачи, переписав рекурсию в код, то получим экспоненциальное время выполнения, ведущее себя примерно как <math> \Phi^n </math>, где <math> \Phi </math> — [[w:золотое сечение]]. |
|||
[[Изображение:ArificialBreath.JPG|thumb|260 px|right|Искусственное дыхание «рот-в-рот»]] |
|||
Наиболее эффективный способ искусственного дыхания. |
|||
# Спасите пострадавшего, уберите от него ток, если он им поражён, вытащите из воды при утоплении, обеспечьте его безопасность. |
|||
# Положите пострадавшего на спину. Откройте ему рот, следите, чтобы язык не закрывал гортань. |
|||
# Одной рукой удерживайте голову и шею пострадавшего, другой зажмите его нос. Глубоко вдохните и, плотно прижавшись ртом ко рту, сделайте выдох. |
|||
# Первые 5—10 выдохов делайте быстро (за 20—30 с), следующие— со скоростью 12—15 выдохов в минуту. |
|||
# Следите за движением грудной клетки пострадавшего: если после вашего выдоха в рот его грудная клетка поднялась, значит, дыхательные пути проходимы и искусственное дыхание вы делаете правильно. |
|||
# Если нет пульса, параллельно с искусственным дыханием необходимо делать массаж сердца. |
|||
Приведем [[C++]] — код этой функции: |
|||
=== Искусственное дыхание «рот-в-нос» === |
|||
<source lang="cpp"> |
|||
Проводится, если рот спасаемого повреждён или по каким-либо причинам нельзя использовать метод «рот-в-рот». Не так эффективно, как искусственное дыхание «рот-в-рот», «рот-в-нос» также способно спасти человека. |
|||
//Внимание: функция имеет экспоненциальное время выполнения и неэффективно использует стэк. |
|||
//Функция возвращает n-e число Фибоначчи по данному n. |
|||
int fib(int n) |
|||
{ |
|||
if (n <= 2) return 1; |
|||
else |
|||
{ |
|||
return fib(n - 1) + fib(n - 2); |
|||
} |
|||
} |
|||
</source> |
|||
== Решение с помощью динамического программирования == |
|||
== См. также == |
|||
В данном случае организовать запоминание перекрывающихся подзадач очень легко — заведем массив dp, dp[i] будет значением <math> F_i </math>. В этой задаче легко организовать восходящее [[Динамическое программирование|ДП]], так как мы знаем, что для вычисления <math>F_n</math> понадобятся <math>F_{n-1}</math> и <math>F_{n-2}</math>. Асимптотическая сложность алгоритма будет [[O-большое|O]](n) время и O(n) памяти.(Требуется массив и один проход по массиву). |
|||
* [[Реанимация]] |
|||
* [[Искусственный массаж сердца]] |
|||
Код функции, реализующий восходящее ДП: |
|||
[[Категория:Дыхание]] |
|||
<source lang="cpp"> |
|||
[[Категория:Медицина]] |
|||
//возвращает n-e число Фибоначчи |
|||
[[Категория:Первая помощь]] |
|||
int fib_n(int n) |
|||
[[Категория:Искусственное дыхание]] |
|||
{ |
|||
if (n <= 2) return 1; |
|||
std::vector<int> dp(n + 1); |
|||
dp[1] = 1; dp[2] = 1; |
|||
for (int i = 3; i <= n; i++) |
|||
{ |
|||
dp[i] = dp[i - 1] + dp[i - 2]; |
|||
} |
|||
return dp[n]; |
|||
} |
|||
</source> |
|||
== Элегантное решение == |
|||
Приведем ещё одно решение — оно использует также как и динамическое программирование O(n) времени, но обходится всего O(1) памяти. Решение основывается на том, что для вычисления следующего числа нужно помнить всего 2 предыдущих, а не все предыдущие. |
|||
Приведем С++ — код: |
|||
<source lang="cpp"> |
|||
//возвращает n-е число Фибоначчи |
|||
int fib_n(int n) |
|||
{ |
|||
if (n <= 2) return 1; |
|||
//F(n-2) |
|||
int x = 1; |
|||
//F(n-1) |
|||
int y = 1; |
|||
//F(n) |
|||
int ans = 0; |
|||
for (int i = 3; i <= n; i++) |
|||
{ |
|||
ans = x + y; |
|||
x = y; |
|||
y = ans; |
|||
} |
|||
return ans; |
|||
} |
|||
</source> |
Версия от 09:56, 8 ноября 2009
Постановка задачи
Вычислить , где — -е число Фибоначчи, задаваемое рекуррентным соотношением:
- , n > 2
Рекурсивное решение
Если напрямую написать решение этой задачи, переписав рекурсию в код, то получим экспоненциальное время выполнения, ведущее себя примерно как , где — w:золотое сечение.
Приведем C++ — код этой функции:
//Внимание: функция имеет экспоненциальное время выполнения и неэффективно использует стэк.
//Функция возвращает n-e число Фибоначчи по данному n.
int fib(int n)
{
if (n <= 2) return 1;
else
{
return fib(n - 1) + fib(n - 2);
}
}
Решение с помощью динамического программирования
В данном случае организовать запоминание перекрывающихся подзадач очень легко — заведем массив dp, dp[i] будет значением . В этой задаче легко организовать восходящее ДП, так как мы знаем, что для вычисления понадобятся и . Асимптотическая сложность алгоритма будет O(n) время и O(n) памяти.(Требуется массив и один проход по массиву).
Код функции, реализующий восходящее ДП:
//возвращает n-e число Фибоначчи
int fib_n(int n)
{
if (n <= 2) return 1;
std::vector<int> dp(n + 1);
dp[1] = 1; dp[2] = 1;
for (int i = 3; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
Элегантное решение
Приведем ещё одно решение — оно использует также как и динамическое программирование O(n) времени, но обходится всего O(1) памяти. Решение основывается на том, что для вычисления следующего числа нужно помнить всего 2 предыдущих, а не все предыдущие.
Приведем С++ — код:
//возвращает n-е число Фибоначчи
int fib_n(int n)
{
if (n <= 2) return 1;
//F(n-2)
int x = 1;
//F(n-1)
int y = 1;
//F(n)
int ans = 0;
for (int i = 3; i <= n; i++)
{
ans = x + y;
x = y;
y = ans;
}
return ans;
}