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

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Откат вандализма
Нет описания правки
Строка 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


=== Искусственное дыхание «рот-в-рот» ===
== Рекурсивное решение ==
[[Изображение: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>

Версия от 08:25, 8 ноября 2009

Искусственное дыхание — комплекс мер, направленных на поддержание оборота воздуха через легкие у человека (или животного), переставшего дышать. Может производиться с помощью аппарата искусственного дыхания, либо человеком (дыхание изо рта в рот). Обычно совмещается с искусственным массажем сердца. Типичные ситуации, в которых требуется искусственное дыхание: несчастные случаи в результате автомобильных аварий, происшествия на воде, поражение электрическим током, утопление. Аппарат искусственного дыхания используется также в хирургических операциях.

Искусственное дыхание «рот-в-рот»

Файл:ArificialBreath.JPG
Искусственное дыхание «рот-в-рот»

Наиболее эффективный способ искусственного дыхания.

  1. Спасите пострадавшего, уберите от него ток, если он им поражён, вытащите из воды при утоплении, обеспечьте его безопасность.
  2. Положите пострадавшего на спину. Откройте ему рот, следите, чтобы язык не закрывал гортань.
  3. Одной рукой удерживайте голову и шею пострадавшего, другой зажмите его нос. Глубоко вдохните и, плотно прижавшись ртом ко рту, сделайте выдох.
  4. Первые 5—10 выдохов делайте быстро (за 20—30 с), следующие— со скоростью 12—15 выдохов в минуту.
  5. Следите за движением грудной клетки пострадавшего: если после вашего выдоха в рот его грудная клетка поднялась, значит, дыхательные пути проходимы и искусственное дыхание вы делаете правильно.
  6. Если нет пульса, параллельно с искусственным дыханием необходимо делать массаж сердца.

Искусственное дыхание «рот-в-нос»

Проводится, если рот спасаемого повреждён или по каким-либо причинам нельзя использовать метод «рот-в-рот». Не так эффективно, как искусственное дыхание «рот-в-рот», «рот-в-нос» также способно спасти человека.

См. также