Метод математической индукции — различия между версиями

Материал из ALL
Перейти к: навигация, поиск
Строка 25: Строка 25:
 
*[[машина Поста]];
 
*[[машина Поста]];
 
*[[машина Тьюринга]];
 
*[[машина Тьюринга]];
*[[составление перестановок]];
+
*[[Составление перестановок|комбинаторные алгоритмы]];
*[[составление лексикографических перестановок]];
+
*[[составление сочетаний]];
+
*[[составление лексикографических сочетаний]];
+
*[[составление размещений]];
+
*[[составление лексикографических размещений]];
+
*[[составление разбиений]];
+
*[[составление лексикографических разбиений]];
+
 
*[[сортировка]];
 
*[[сортировка]];
 
*[[алгоритм определения мест]].
 
*[[алгоритм определения мест]].

Версия 06:17, 14 февраля 2016

Метод математической индукции - это метод доказательства формул c целочисленной переменной, состоящий в проверке формулы при некотором начальном значении этой переменной, затем в предположении верности формулы при некотором значении переменной и в доказательстве верности формулы при следующем значении переменной. В этом случае метод математической индукции доказывает верность формулы при всех целочисленных значениях переменной, начиная с проверенного.

Алгоритм

Входные данные: n0; Sn=f(n).

ММИ01.JPG

Примеры

Пример 1

ММИ11.JPG

Формула доказана, ч.т.д.

Пример 2

ММИ12.JPG

Формула доказана, ч.т.д.

Другие алгоритмы:

Ссылки