что такое инвариант цикла

Урок 35
Доказательство правильности программ
(§37. Доказательство правильности программ)

Содержание урока

Инвариант цикла

Инвариант цикла

Таким образом, для алгоритма Евклида существует условие НОД(а, b) = НОД(m, n), которое остаётся справедливым на протяжении всего выполнения алгоритма: перед началом цикла, после каждого шага цикла и после окончания работы цикла. Такое условие называется инвариантом цикла (англ. invariant — неизменный).

Инвариант цикла — это соотношение между значениями переменных, которое остаётся справедливым после завершения любого шага цикла.

Выделив в явном виде инвариант каждого цикла, мы избегаем многих возможных ошибок на начальной стадии и делаем первый шаг к доказательству правильности всей программы. Как писал академик Андрей Петрович Ершов, один из первых теоретиков программирования в СССР, «программиста бьют по рукам, если он посмеет написать оператор цикла, не найдя перед этим его инварианта».

Рассмотрим несколько примеров.

Пример 1. Двое играют в следующую игру: перед ними лежат в ряд N + 1 камней, сначала N белых, и в конце цепочки — один чёрный. За один ход каждый может взять от 1 до 3 камней. Проигрывает тот, кто берет чёрный («несчастливый») камень.

Таким образом, для своего выигрыша игрок должен каждым своим ходом восстанавливать инвариант: число оставшихся белых камней должно быть кратно 4. Если инвариант выполнен в начальной позиции, положение проигрышное и первый игрок может надеяться только на ошибку соперника.

Пример 2. Пусть задан массив А длины n. Найдём инвариант цикла в программе суммирования элементов массива:

нц для i от 1 до n

Здесь на каждом шаге к переменной Sum добавляется элемент массива A[i], так что при любом i после окончания очередного шага цикла в Sum накоплена сумма всех элементов массива с номерами от 1 до i. Это и есть инвариант цикла. Поэтому сразу можно сделать вывод о том, что после завершения цикла в переменной Sum будет записана сумма всех элементов массива.

Аналогично можно показать, что в алгоритме поиска наименьшего значения в массиве:

нц для i от 2 до n

если А[i] Пример 3. Для того же массива найдем инвариант цикла в программе сортировки элементов массива методом пузырька:

нц для i от 1 до n-1

если A[j] > A[j+l] то

с:= А[j); А(j]:= А[j+1]; A[j + 1]:= с;

До начала алгоритма элементы расположены произвольно. На каждом шаге внешнего цикла на свое место «всплывает» один элемент массива. Поэтому инвариант этого цикла можно сформулировать так: «После выполнения i-ro шага цикла первые i элементов массива отсортированы и установлены на свои места».

Теперь построим инвариант внутреннего цикла. В этом цикле очередной «лёгкий» элемент поднимается вверх к началу массива. Перед первым шагом внутреннего цикла элемент, который будет стоять на i-м месте в отсортированном массиве, может находиться в любой ячейке от А[i] до А[n]. После каждого шага его «зона нахождения» сужается на одну позицию, так что инвариант внутреннего цикла можно сформулировать так: «Элемент, который будет стоять на i-м месте в отсортированном массиве, может находиться в любой ячейке от A[i] до А[j]». Очевидно, что когда в конце этого цикла j = i, элемент A[i] встаёт на своё место.

В предыдущих примерах мы определяли инвариант готового цикла. Теперь покажем, как можно строить цикл с помощью заранее выбранного инварианта.

Пример 4. Рассмотрим алгоритм быстрого возведения в степень, основанный на использовании операций возведения в квадрат и умножения. Он использует две очевидные формулы:

(1) a k = a k-l • а при нечётной степени k и

(2) а к = (а 2 ) k/2 при чётной степени k.

Покажем, как работает алгоритм, на примере возведения числа а в степень 7:

Здесь поочерёдно применяются первая и вторая формулы. Заметим, что на каждом этапе выражение а n можно представить в виде а n = b к • р, где через р обозначена часть, взятая выше в квадратные скобки. Если нам каким-то образом удастся уменьшить k до нуля, сохранив это равенство, то мы получим а n = р, т. е. задача будет решена, а результат будет находиться в переменной р.

Таким образом, равенство а n = b к • р можно использовать как инвариант цикла. Для того чтобы обеспечить выполнение этого равенства в начальный момент, можно принять, например, b = а, k = n и р = 1. Далее в цикле применяются формулы (1) и (2) (в зависимости от чётности k на данном шаге). Цикл заканчивается, когда k = 0. В результате получаем следующее решение:

нц пока к <> 0

если mod(k,2)=0 то

иначе

Заметим, что инвариант цикла а n = b к • р выполняется до начала цикла, после каждого шага, а также после завершения цикла. Таким образом, мы написали код программы и одновременно доказали правильность этого блока.

Следующая страница Спецификация

Cкачать материалы урока

Источник

Что такое инвариант цикла?

Я читаю» введение в алгоритм » CLRS. и авторы говорят об инвариантах цикла в главе 2 (сортировка вставки). Я понятия не имею, что это значит.

15 ответов

мне нравится очень простое определение: (источник)

инвариант цикла-это условие [среди переменных программы], которое обязательно верно непосредственно перед и сразу после каждой итерации цикла. (Обратите внимание, что это ничего не говорит о его истинности или ложности частично через итерацию.)

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

есть одна вещь, которую многие люди не понимают сразу при работе с петлями и инвариантами. Они путаются между инвариантом цикла и условным циклом ( условием, которое управляет завершением цикла ).

как указывают люди, инвариант цикла должен быть истинным

( хотя он может временно быть ложным во время тела цикла ). С другой стороны, условный цикл должны будет false после завершения цикла, иначе цикл никогда не завершится.

таким образом, инвариант цикла и условного цикла должны быть разные условия.

хорошим примером инварианта комплексного цикла является двоичный поиск.

таким образом, цикл условный кажется довольно прямо вперед-когда start > end цикл завершается. Но почему петля правильная? Что такое инвариант цикла, который доказывает его правильность?

инвариантом является логическое утверждение:

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

если мы вернемся, потому что мы нашли элемент в массиве, то утверждение очевидно, так как если A[mid] == a затем a находится в массиве и mid должна быть между началом и концом. И если цикл завершается, потому что start > end тогда не может быть такого числа, что start и mid и поэтому мы знаем, что заявление A[mid] == a должно быть false. Однако в результате общее логическое утверждение остается истинным в нулевом смысле. ( В логике утверждение if (false ) тогда ( something) всегда истинно. )

предыдущие ответы очень хорошо определили инвариант цикла.

теперь позвольте мне попытаться объяснить, как авторы CLRS использовали инварианты цикла для доказательства достоверность рода вставки.

алгоритм сортировки вставки(как указано в книге):

инвариант цикла в этом случае (источник: CLRS book): Subarray[1 to j-1] всегда сортируется.

теперь давайте проверим это и докажем, что алгоритм правильный.

Мейнтаненс: Это можно легко проверить, проверив инвариант после каждой итерации.В этом случае он удовлетворен.

прекращение: это шаг, на котором мы докажем правильность алгоритм.

когда цикл завершается, то значение j=n+1. Снова выполняется инвариант цикла.Это означает, что Подрешетка[от 1 до n] должна быть отсортирована.

Это то, что мы хотим сделать с нашим алгоритмом.Таким образом, наш алгоритм верен.

помимо всех хороших ответов, я думаю, отличный пример из Как думать об алгоритмах, Джефф Эдмондс может проиллюстрировать концепцию очень хорошо:

пример 1.2.1 «алгоритм двух пальцев Find-Max»

1) Технические характеристики: входной экземпляр состоит из списка L (1..n) элементы. Выход состоит из индекса i такого, что L (i) имеет максимум значение. Если есть несколько записей с этим же значением, то любые один из них возвращается.

2) основные шаги: вы принимаете решение о методе двух пальцев. На пальце правой руки пробегает по списку.

3) мера прогресса: мера прогресса, как далеко вдоль список ваш правый палец.

4) Инвариант Цикла: инвариант петли заявляет, что ваш левый палец указывает на одну из самых больших записей, встреченных до сих пор вашим правый палец.

5) Основные шаги: каждая итерация, ты двигаешь правым пальцем вниз. запись в списке. Если ваш правый палец теперь указывает на запись это больше, чем вход левого пальца, а затем переместите левый палец, чтобы быть с правым пальцем.

6) прогресс: вы делаете прогресс, потому что ваш правый палец движется одна запись.

7) Поддерживать Инвариант Цикла: вы знаете, что инвариант цикла сохраняется следующим образом. Для каждого шага новый элемент левого пальца есть Max (старый элемент левого пальца, новый элемент). По инварианту цикла, это Max (Max (shorter list), новый элемент). Математически, это Макс(длинный список).

8) установление инварианта цикла: вы изначально устанавливаете инвариант петли, указывая обоими пальцами на первый элемент.

9) условие выхода: вы сделаны когда ваш правый палец заканчивал просматриваю список.

10) конец: в конце концов, мы знаем задача решается следующим образом. От при условии выхода, ваш правый палец столкнулся со всеми вступления. По инварианту петли ваш левый палец указывает на максимум из этих. Верните эту запись.

11) прекращение и продолжительность: требуемое время некоторая константа умножьте длину списка.

12) особые случаи: проверьте, что происходит, когда есть несколько записей с тем же значением, или, когда n = 0 или N = 1.

14) формальное доказательство правильности алгоритма вытекает из вышеупомянутые шаги.

следует отметить, что инвариант цикла может помочь в разработке итерационных алгоритмов при рассмотрении утверждения, которое выражает важные отношения между переменными, которые должны быть истинными в начале каждой итерации и когда цикл завершается. Если это так, то расчет находится на пути к эффективности. Если false, то алгоритм не удалось.

инвариант в этом случае означает условие, которое должно быть истинным в определенной точке каждой итерации цикла.

в контрактном программировании инвариантом является условие, которое должно быть истинным (по контракту) до и после вызова любого открытого метода.

значение инварианта никогда не меняется

здесь инвариант цикла означает » изменение, которое происходит с переменной в цикле (инкремент или декремент), не изменяет условие цикла i.e условие удовлетворяет » так, что пришло инвариантное понятие цикла

трудно отслеживать, что происходит с петель. Циклы, которые не заканчиваются или заканчиваются без достижения их поведения цели, являются общей проблемой в компьютерном программировании. Помогают инварианты цикла. Инвариант цикла-это формальное утверждение о взаимосвязи между переменными в вашей программе, которое выполняется непосредственно перед запуском цикла (установление инварианта) и снова выполняется в нижней части цикла, каждый раз через цикл (поддержание инварианта). Вот общий шаблон использования инвариантов цикла в вашем коде:

. // инвариант цикла должен быть истинным здесь
while (условие тестирования ) <
// top of the loop
.
// нижняя часть петли
// инвариант цикла должен быть истинным здесь
>
// Завершение + Инвариант Цикла = Цель
.
Между верхней и нижней частью петли, прогресс предположительно делается к достижению петли цель. Это может нарушить (сделать ложным) инвариант. Точка инвариантов цикла-это обещание, что инвариант будет восстановлен перед повторением тела цикла каждый раз. В этом есть два преимущества:

работа не переносится на следующий проход сложными, зависящими от данных способами. Каждый проход через петлю независим от всех других, с инвариантом, служащим для связывания проходов вместе в рабочее целое. Рассуждение о том, что ваш цикл работает, сводится к рассуждению что инвариант цикла восстанавливается с каждым проходом через цикл. Это разбивает сложное общее поведение цикла на небольшие простые шаги, каждый из которых можно рассматривать отдельно. Тестовое условие цикла не является частью инварианта. Это то, что заставляет цикл завершаться. Вы рассматриваете отдельно две вещи: почему цикл должен когда-либо завершаться и почему цикл достигает своей цели, когда он завершается. Цикл завершится, если каждый раз через цикл вы приближаетесь к удовлетворяющ условие прекращения. Часто это легко гарантировать: например, шагая переменную счетчика по одному, пока она не достигнет фиксированного верхнего предела. Иногда причина прекращения сложнее.

инвариант цикла должен быть создан таким образом, чтобы при достижении условия окончания и истинности инварианта была достигнута цель:

инвариант + увольнение => цель
Требуется практика для создания инвариантов, которые просты и связаны которые охватывают все достижения цели, кроме прекращения. Лучше всего использовать математические символы для выражения инвариантов цикла, но когда это приводит к чрезмерно сложным ситуациям, мы полагаемся на ясную прозу и здравый смысл.

Извините, у меня нет разрешения на комментарий.

@Tomas Petricek, как вы упомянули

более слабый инвариант, который также истинен, заключается в том, что i >= 0 && i

Как это инвариант цикла?

свойство инварианта цикла является условием, которое выполняется для каждого шага выполнения циклов(т. е. для петли, а петли и т. д.)

Это важно для доказательства инварианта цикла, где можно показать, что алгоритм выполняется правильно, если на каждом шаге его выполнения это свойство инварианта цикла выполняется.

чтобы алгоритм был правильным, инвариант цикла должен иметь значение:

инициализации (the начало)

техническое обслуживание (каждый шаг)

прекращение (когда он закончил)

Это используется для оценки множества вещей, но лучшим примером являются жадные алгоритмы для обхода взвешенного графика. Чтобы жадный алгоритм дал оптимальное решение (путь по графу), он должен достичь соединения всех узлов в наименьшем возможном пути веса.

таким образом, свойство инварианта цикла состоит в том, что выбранный путь имеет наименьший вес. На начало мы не добавили ребер, поэтому это свойство true (в данном случае это не false). At каждый шаг, мы следуем за самым низким краем веса (жадный шаг), поэтому снова мы принимаем самый низкий путь веса. At конец, мы нашли самый низкий взвешенный путь, поэтому наше свойство также верно.

Если алгоритм этого не делает, мы можем доказать, что он не является оптимальным.

простыми словами, это условие цикла, которое истинно в каждой итерации цикла:

в этом мы можем сказать, что состояние i i =0

инвариант цикла-это утверждение, которое истинно до и после выполнения цикла.

в линейном поиске (согласно упражнению, приведенному в книге), нам нужно найти значение V в данном массиве.

его просто, как сканирование массива из 0

содержание: На следующей итерации V, не найденный в k-1, имеет значение true

Terminatation: Если V найдено в K позиции или k достигает длины массива, завершите цикл.

Источник

Инвариант цикла

Программисты часто составляют циклы, как правило, чтобы достичь какой-то конкретной цели: найти элемент с заданными свойствами, выполнить сортировку и т. п. Но как убедиться в том, что цель будет достигнута, не выполняя цикл непосредственно? В этом нам поможет инвариант цикла.

Рассмотрим использование инварианта цикла на примере поиска индекса наименьшего элемента в целочисленном массиве.

Инвариант цикла будет выглядеть так:

Инициализируем переменные, входящие в инвариант, так, чтобы он был истинным до начала выполнения цикла:

Инвариант цикла && Условие_окончания_цикла => Цель цикла

Вместо условия окончания можно использовать условие выполнения цикла. В нашем случае это: nextToCheck (пока есть элементы для проверки). Как только оно будет нарушено (станет ложным), выполнение цикла прекратится

Таким образом, подобрав инвариант цикла и обеспечив его сохранение, мы можем гарантировать достижение цели, не выполняя сам цикл.

Вопросы для самопроверки при составлении циклов:

При составлении циклов может оказаться удобным понятие области неопределенности, используемое в вычислительных методах математики. Область изменения параметров задачи (в нашем примере: [0,n)) можно разделить на две части: исследованную область (для которой найден TemporarySmallest : [0,nextToCheck) ) и область неопределенности ( [nextToCheck,n) ). Необходимо составлять цикл так, чтобы на каждой итерации область неопределенности сокращалась.

Инвариант цикла будет таким:

Непосредственно перед циклом инициализируем значение numSorted :

что делает инвариант цикла истинным.

На каждой итерации количество numSorted увеличивается на единицу. Чтобы этого достичь, выбирается наименьший среди первых [0,n-numSorted) неотсортированных элементов, и меняется местами (с помощью функции swap() ) c элементом n-numSorted

Таким образом, отсортированный «хвост» массива всякий раз удлиняется на один элемент, а неотсортированная «голова» уменьшается.

Что почитать

Вирт Н. Алгоритмы + структуры данных = программы

Источник

Инвариант (программирование)

Инвариа́нтом в программировании называется логическое выражение, истинное после каждого прохода тела цикла (после выполнения фиксированного оператора) и перед началом выполнения цикла, зависящее от переменных, изменяющихся в теле цикла. [1]

Инварианты используются в теории верификации программ для доказательства правильности выполнения цикла. Порядок доказательства работоспособности цикла с помощью инварианта сводится к следующему:

Также инварианты используют при проектировании и оптимизации циклических алгоритмов. Например, чтобы убедиться, что оптимизированный цикл остался корректным, достаточно доказать, что инвариант цикла не нарушен и условие завершения цикла достижимо.

Понятие инварианта также используется в объектно-ориентированном программировании для обозначения непротиворечивого состояния объекта. Подразумевается, что вызов любого метода оставляет объект в состоянии инварианта.

Примечания

Полезное

Смотреть что такое «Инвариант (программирование)» в других словарях:

Инвариант — или инвариантность термин, обозначающий нечто неизменяемое. Конкретное значение термина зависит от той области, где он используется: Инвариант (математика) Инвариант узла в топологии Инвариант (физика) Инвариант (программирование) Инвариант … Википедия

ПРОГРАММИРОВАНИЕ ТЕОРЕТИЧЕСКОЕ — математическая дисциплина, изучающая математич. абстракции программ, трактуемых как объекты, выраженные на формальном языке, обладающие определенной информационной и логич. структурой и подлежащие исполнению на автоматич. устройствах. П. т.… … Математическая энциклопедия

Конструктор (программирование) — У этого термина существуют и другие значения, см. Конструктор. В объектно ориентированном программировании конструктор класса (от англ. constructor, иногда сокращают ctor) специальный блок инструкций, вызываемый при создании объекта.… … Википедия

ДРАКОН — Эта статья предлагается к удалению. Пояснение причин и соответствующее обсуждение вы можете найти на странице Википедия:К удалению/28 сентября 2012. Пока процесс обсуждения не завершён, статью мож … Википедия

ДРАКОН (алгоритмический язык) — У этого термина существуют и другие значения, см. Дракон (значения). Пример блок схемы алгоритма на языке ДРАКОН дракон схемы ДРАКОН (Дружелюбный Русский Алгоритмический язык, Который Обеспечивает Наглядность) визуальный… … Википедия

Конструктор класса — В объектно ориентированном программировании конструктор класса (от англ. constructor, иногда сокращают ctor) специальный блок инструкций, вызываемый при создании объекта, причём или при его объявлении (располагаясь в стеке или в статической… … Википедия

Конструктор объекта — В объектно ориентированном программировании конструктор класса (от англ. constructor, иногда сокращают ctor) специальный блок инструкций, вызываемый при создании объекта, причём или при его объявлении (располагаясь в стеке или в статической… … Википедия

Ковариантность и контравариантность — Ковариантность и контравариантность математическое и физическое понятие, которое описывает то, как величины изменяются при преобразовании системы координат. Координаты геометрического вектора измеряются в какой нибудь конкретной системе… … Википедия

КУЛЬТУРА — (лат. cultura возделывание, воспитание, почитание) универсум искусственных объектов (идеальных и материальных предметов; объективированных действий и отношений), созданный человечеством в процессе освоения природы и обладающий структурными,… … Философская энциклопедия

Шаблон — О шаблонах в Википедии смотрите страницу Википедия:Шаблоны. Шаблон в технике пластина (лекало, трафарет и т. п.) с вырезами, по контуру которых изготовляются чертежи или изделия либо инструмент для измерения размеров. Шаблон в… … Википедия

Источник

Что такое инвариант цикла

Начнем, как обычно, с задачки. В строке, содержащей цепочки одинаковых символов, нужно их обнаружить и заменить на счетчик повторений и один такой символ. Например, из строки « abcdddddddddefggggggggggggggggggx » получить « abc 9 def 18 gx ». Извечный вопрос русской интеллигенции: «Что делать?».

Типичный ход рассуждений: «Будем просматривать строку в цикле. Если обнаружим повторяющийся фрагмент…» содержит одну существенную недосказанность: как процесс обнаружения повторяющегося фрагмента связан с циклом посимвольного просмотра неповторяющихся символов. Это отдельный процесс – цикл, или он является частью предыдущего.

// «Склеивание» повторяющихся символов строки.

// Использование счетчика повторений. «Грязная программа»

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

Здесь есть еще один «заяц». Вспомните, что любой цикл нужно проверять на первый и последний шаг. Они могут «вписаться» в имеющийся текст, а могут и нет. В нашем случае, когда текущий символ – последний в строке, мы сравниваем его с символом «конец строки», т.е. заведомо будет несовпадение и программа сработает правильно. В других случаях, например, когда строка задана объектом или типом данных, состоящим из массива символов и текущей размерности, придется в явном виде записывать условие – последний символ строки. В классическом Си это выглядит так:

if (i!=strlen(in) && in[i]==in[i+1]) k++; // Символ не последний и за ним такой же

Перейдем теперь к решению задачи. Технологически возможны два варианта обработки строки: переписывание в новую или сжатие текущей. Вариант с п ереписыванием будет проще. Мы сможем сохранить «грязную» программу, добавив в нее процесс переписывания – массив и индекс в нем. И не только. Чтобы записать счетчик в виде числа, необходимо перевести его во внешнюю форму представления, в виде цепочки символов-цифр (см.4.5).

// Использование счетчика повторений. Переписывание строки

void F2(char in[], char out[])<

int k1,j1; // Записать k в виде символов-цифр

for (k1=k; k1!=0;k1=k1/10,j++);

out[j++]=in[i]; // Переписать текущий символ

out[j]=0;> // Добавить «конец строки»

Инвариант цикла

// Отдельный цикл «измерения» повторений. «Грязная программа»

for(k=1;in[i]==in[i+k];k++); // Измерить длину цепочки

i=i+k; // Шаг цикла – длина цепочки

// Отдельный цикл «измерения» повторений. «Сжатие строки»

for(k=1;in[i]==in[i+k];k++); // Измерить длину цепочки

j=i+k; // Запомнить начало «хвоста»

int k1,j1; // Записать k в виде символов-цифр

for (k1=k; k1!=0;k1=k1/10,i++);

in[j1]=k%10+’0′; // Затереть символы цифрами числа

i++; // «Оставить» один символ

j1=i; // i – начало следующего шага

Обратите внимание, мы пилим сук, на котором сидим: сдвигаем содержимое части строки, которую еще будем просматривать. Но «пилить» нужно аккуратно, сохраняя свойство, которое мы установили в «грязной» программе: за один шаг цикла мы просматриваем (и преобразуем) фрагмент. Следовательно, по окончании этого шага индекс i должен устанавливаться сразу после сжатого фрагмента (на символе e).

Инвариант цикла и метод математической индукции

Есть еще одна неожиданная параллель между программированием и математикой. В математических доказательствах иногда используется метод математической индукции ( ММИ). Звучит он примерно так: если утверждение верно при i=0, и если из того, что оно верно при произвольном i, можно вывести, что оно будет верно при i+1, то оно будет верно всегда.

На первый взгляд, метод достаточно очевиден: некоторое свойство сохраняется на всей цепочке (последовательности), если оно выполняется в первой точке и сохраняется при переходе из каждой точки в следующую. Но в самом доказательстве есть элемент диалектики общего и частного. Метод определен для последовательности частных шагов, а доказательство проводится в общем виде для произвольного перехода от i-го шага к i+1.

Инвариант цикла может быть разным. Самым простым является утверждение типа: «в начале каждого шага цикл находится в…». Например, программа обработки слов в строке может быть построена по принципу «один шаг = одно слово». Тогда инвариантным утверждением будет: «в начале шага программа находится на начале очередного слова».

// Пословная обработка: «1 шаг = 1 слово». «Грязная программа»

while (in[i]==’ ‘)i++; // ДЛЯ ПЕРВОГО ШАГА

В соответствии с ММИ необходимо обеспечить справедливость утверждения (инварианта) на первом шаге. Для контекста суммирования это естественно: сумма последовательности из 0 элементов равна 0. Для контекста поиска максимума максимальное значение последовательности из 0 элементов или не определено, или не должно быть «меньше меньшего». Поэтому следует в качестве максимума выбирать значение первого элемента, либо использовать «защелку» для первого шага.

for (s=A[0],i=1;i if (A[i]>s) s=A[i];

for (k=-1,i=0; i // поиск минимального из положительных

if (A[i] // пропуск отрицательных

if (k==-1) k=i; // «защелка» на первый положительный

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

· для решения задачи в общем виде (например, вывода формулы последовательности) первоначально рассматривается одна или несколько конкретных (частых) последовательностей шагов;

· на этой последовательности формально-логически или интуитивно формулируется искомая зависимость;

· справедливость установленной зависимости доказывается (или, наоборот, опровергается) с использованием ММИ.

Снова проведем аналогию с программированием:

· как правило, проектирование цикла начинается с анализа частного случая его работы на конкретной последовательности данных;

· на конкретном примере определяются составные части цикла и из них составляется фрагмент циклической программы;

· определяется инвариант цикла;

· проверяется, во всех ли случаях сохраняется инвариант при переходе от текущего шага к следующему, при необходимости в цикл вводятся коррективы.

При проектировании циклов часто встречаются два вида ошибок, которые имеют прямое отношение к индуктивному принципу его построения:

Источник