Вычисление чисел Фибоначчи: различия между версиями

Нет описания правки
(Откат вандализма)
'''Искусственное дыхание''' — комплекс мер, направленных на поддержание оборота воздуха через легкие у человека (или животного), переставшего дышать. Может производиться с помощью аппарата искусственного дыхания, либо человеком (дыхание изо рта в рот). Обычно совмещается с [[искусственный массаж сердца|искусственным массажем сердца]]. Типичные ситуации, в которых требуется искусственное дыхание: несчастные случаи в результате автомобильных аварий, происшествия на воде, поражение электрическим током, утопление. Аппарат искусственного дыхания используется также в хирургических операциях.
== Постановка задачи ==
Вычислить <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
 
=== Искусственное дыхание «рот-в-рот» ===
== Рекурсивное решение ==
[[Изображение:ArificialBreath.JPG|thumb|260 px|right|Искусственное дыхание «рот-в-рот»]]
Если напрямую написать решение этой задачи, переписав рекурсию в код, то получим экспоненциальное время выполнения, ведущее себя примерно как <math> \Phi^n </math>, где <math> \Phi </math> — [[w:золотое сечение]].
Наиболее эффективный способ искусственного дыхания.
# Спасите пострадавшего, уберите от него ток, если он им поражён, вытащите из воды при утоплении, обеспечьте его безопасность.
# Положите пострадавшего на спину. Откройте ему рот, следите, чтобы язык не закрывал гортань.
# Одной рукой удерживайте голову и шею пострадавшего, другой зажмите его нос. Глубоко вдохните и, плотно прижавшись ртом ко рту, сделайте выдох.
# Первые 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>