Рекурсивные структурированные программы

Предыдущие способы получения структурированных программ могут быть недостаточно понятными и эффективными. Для их усовершенствования вводится другой способ, исключающий излишние установки и проверки счетчика L. Идея заключается в том, чтобы для каждого j>0 заменить все присваивания вида L:= j соответствующей программой g_j.

Поскольку значение j тем самым никогда не будет присвоено счетчику L, проверка L= j может быть вынесена за пределы последовательности структур if then else. Допустим, имелась последовательность программ g₁; g₂;… g_n. Один шаг, описанной выше замены, приводит к новой последовательности программ . Здесь  при необходимости могут быть перенумерованы. Единственным препятствием продолжению этого процесса может быть рекурсивное обращение, когда некоторые  будут содержать присваивание L=i.

Таким образом, процесс замещения можно продолжать до тех пор, пока:

1) все присваивания счетчику L, кроме L:=0, не будут замещены;

2) каждая оставшаяся программа  будет содержать лишь присваивания L= i.

Если программа ациклическая, то на каждом пути появится присваивание L:=0. Следовательно, в этом случае счетчик L и цикл whilе L>0 do могут быть исключены.

 Рассмотрим в качестве примера следующую структурированную программу с программным счетчиком:

 

 

 

На первом шаге присваивание L:=4 заменим программой, стоящей на пути L:=4 (последовательность h, L:=1). Поскольку после этого присваивание L:=4 нигде не будет встречаться, проверку L=4 можно будет исключить. В результате получим следующую программу:

Далее производим замену узла L:=2 на последовательность е, L:=0, а узел L:=3 заменяем на программу, стоящую на пути L=3. В результате будем иметь:

Здесь можно заметить, что присваивание L:=1 и проверку L=1 можно также исключить, так как L становится равным 1 только на выходе из цикла. Поэтому программа будет выглядеть следующим образом:

Тема 5. Методы Доказательства правильности программ

Математический аппарат доказательства

Принцип простой индукции

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

Согласно простой математической индукции для этого необходимо:

1) доказать, что справедливо высказывание .

2) Доказать, что если для справедливо высказывание , то справедливо и высказывание .

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

1) Используя простую индукцию, необходимо доказать, что . Это высказывание справедливо.

2) Предположим, что справедливо высказывание

Покажем, что справедлива формула и для .

 

⇐ Предыдущая234567891011Следующая ⇒

Поделиться: