\input style

\chapter{8 формальное рассмотрение нескольких небольших примеров}
в ЭТОЙ ГЛАВЕ Я ПРОВЕДУ ФОРМАЛЬНОЕ ПОСТРОЕНИЕ НЕСКОЛЬКИХ НЕБОЛЬШИХ 
ПРОГРАММ ДЛЯ РЕШЕНИЯ ПРОСТЫХ ЗАДАЧ. нЕ СЛЕДУЕТ ПОНИМАТЬ ЭТУ ГЛАВУ 
КАК ПРЕДЛОЖЕНИЕ СТРОИТЬ ПРОГРАММЫ ТОЛЬКО ТАК И НЕ ИНАЧЕ: ТАКОЕ 
ПРЕДЛОЖЕНИЕ БЫЛО БЫ ДОВОЛЬНО  СМЕХОТВОРНЫМ. я ПОЛАГАЮ, ЧТО МНОГИМ 
ИЗ МОИХ ЧИТАТЕЛЕЙ ЗНАКОМО БОЛЬШИНСТВО ПРИМЕРОВ, А ЕСЛИ НЕТ, ОНИ, 
ВЕРОЯТНО, НЕ ЗАДУМЫВАЯСЬ СМОГУТ НАПИСАТЬ ЛЮБУЮ ИЗ ЭТИХ ПРОГРАММ. 

сЛЕДОВАТЕЛЬНО, ПОСТРОЕНИЕ ПРОГРАММ ПРОВОДИТСЯ ЗДЕСЬ СОВСЕМ ПО 
ДРУГИМ ПРИЧИНАМ. вО-ПЕРВЫХ, ЭТО БЛИЖЕ ПОЗНАКОМИТ НАС С ФОРМАЛИЗМОМ, 
РАЗВИТЫМ В ПРЕДЫДУЩИХ ГЛАВАХ. вО-ВТОРЫХ, УБЕДИТ НАС В ТОМ, ЧТО ПО 
КРАЙНЕЙ МЕРЕ В ПРИНЦИПЕ, ФОРМАЛИЗМ СПОСОБЕН СДЕЛАТЬ ЯСНЫМ И 
СОВЕРШЕННО СТРОГИМ ТО, ЧТО ЧАСТО ОБоЯСНЯЕТСЯ ПРИ ПОМОЩИ ЭНЕРГИЧНОЙ 
ЖЕСТИКУЛЯЦИИ. в-ТРЕТЬИХ, МНОГИЕ ИЗ НАС НАСТОЛЬКО ХОРОШО ЗНАЮТ ЭТИ 
ПРОГРАММЫ, ЧТО УЖЕ ЗАБЫЛИ, КАКИМ ОБРАЗОМ ДАВНЫМ-ДАВНО МЫ УБЕДИЛИСЬ 
В ИХ ПРАВИЛЬНОСТИ: В ЭТОМ ОТНОШЕНИИ НАСТОЯЩАЯ ГЛАВА НАПОМИНАЕТ 
НАЧАЛЬНЫЕ УРОКИ ПЛАНИМЕТРИИ, КОТОРЫЕ ПО ТРАДИЦИИ ПОСВЯЩАЮТСЯ 
ДОКАЗАТЕЛЬСТВУ ОЧЕВИДНОГО. в-ЧЕТВЕРТЫХ, МЫ МОЖЕМ СЛУЧАЙНО 
ОБНАРУЖИТЬ, К СВОЕМУ УДИВЛЕНИЮ, ЧТО МАЛЕНЬКАЯ ЗНАКОМАЯ ЗАДАЧКА НЕ 
ТАКАЯ УЖЕ ЗНАКОМАЯ. нАКОНЕЦ, ПРОЦЕСС ПОСТРОЕНИЯ ПРОГРАММ МОЖЕТ 
ПРОЛИТЬ СВЕТ НА ОСУЩЕСТВИМОСТЬ, ТРУДНОСТИ И ВОЗМОЖНОСТИ 
АВТОМАТИЧЕСКОГО СОСТАВЛЕНИЯ ПРОГРАММ ИЛИ ИСПОЛЬЗОВАНИЯ МАШИНЫ В 
ПРОЦЕССЕ ПРОГРАММИРОВАНИЯ. эТО МОЖЕТ ОКАЗАТЬСЯ ВАЖНЫМ, ДАЖЕ ЕСЛИ 
АВТОМАТИЧЕСКОЕ СОСТАВЛЕНИЕ ПРОГРАММ НЕ ВЫЗЫВАЕТ У НАС НИ МАЛЕЙШЕГО 
ИНТЕРЕСА, ПОТОМУ ЧТО МОЖЕТ ПОМОЧЬ НАМ ЛУЧШЕ ОЦЕНИТЬ ТУ РОЛЬ, 
КОТОРУЮ МОГУТ ИЛИ ДОЛЖНЫ ИГРАТЬ НАШИ ИЗОБРЕТАТЕЛЬСКИЕ СПОСОБНОСТИ.

в МОИХ ПРИМЕРАХ Я БУДУ ФОРМУЛИРОВАТЬ ТРЕБОВАНИЯ ЗАДАЧИ В ФОРМe "ДЛЯ 
ФИКСИРОВАННЫХ $x$, $y$, \dots", ЧТО ЯВЛЯЕТСЯ СОКРАЩЕННОЙ ЗАПИСЬЮ 
ФОРМЫ "ДЛЯ ЛЮБЫХ ЗНАЧЕНИЙ $x_0$, $y_0$, ... ПОСТУСЛОВИЕ ВИДА 
$x=x_0 \and y=y_0 \and \ldots$ ДОЛЖНО ВЫЗЫВАТЬ ПРЕДУСЛОВИЕ, ИЗ 
КОТОРОГО СЛЕДУЕТ, ЧТО $x=x_0 \and y=y_0 \and \ldots$". эТА 
СВЯЗЬ МЕЖДУ ПОСТУСЛОВИЕМ И ПРЕДУСЛОВИЕМ БУДЕТ ГАРАНТИРОВАНА ТЕМ, 
ЧТО МЫ БУДЕМ ОТНОСИТЬСЯ К ТАКИМ ВЕЛИЧИНАМ КАК К "ВРЕМЕННЫМ 
КОНСТАНТАМ"; ОНИ НЕ БУДУТ ВСТРЕЧАТЬСЯ В ЛЕВЫХ ЧАСТЯХ ОПЕРАТОРОВ 
ПРИСВАИВАНИЯ.

{\sl пЕРВЫЙ ПРИМЕР}

дЛЯ ФИКСИРОВАННЫХ $x$ И $y$ ОБЕСПЕЧИТЬ ИСТИННОСТЬ ОТНОШЕНИЯ $R(m)$. 
$$ 
(m=x \or m=y) \and m\ge x \and m\ge y 
$$

дЛЯ ЛЮБЫХ ЗНАЧЕНИЙ $x$ И $y$ ОТНОШЕНИЕ $m=x$ МОЖЕТ СТАТЬ ИСТИННЫМ 
ТОЛЬКО В РЕЗУЛЬТАТЕ ПРИСВАИВАНИЯ $m:=x$; СЛЕДОВАТЕЛЬНО, ИСТИННОСТЬ 
$(m=x \or m=y)$ ОБЕСПЕЧИВАЕТСЯ ТОЛЬКО ВЫПОЛНЕНИЕМ ЛИБО $m:=Х$, ЛИБО 
$m:=y$. в ВИДЕ БЛОК-СХЕМЫ:
\pict{8.1}

вСЕ ДЕЛО В ТОМ, ЧТО НА ВХОДЕ НУЖНО СДЕЛАТЬ ПРАВИЛЬНЫЙ ВЫБОР, 
КОТОРЫЙ ОБЕСПЕЧИТ ИСТИННОСТЬ $R(m)$ ПОСЛЕ ЗАВЕРШЕНИЯ ВЫЧИСЛЕНИЙ. 
дЛЯ ЭТОГО МЫ "ПРОТАЛКИВАЕМ ПОСТУСЛОВИЕ ЧЕРЕЗ АЛЬТЕРНАТИВЫ":
\pict{8.2}
И МЫ ПОЛУЧИЛИ ПРЕДОХРАНИТЕЛИ! тАК КАК 
$$ 
R(x) = ((x=x \or x=y) \and x\ge x \and x\ge y) = (x\ge y) 
$$ 
 И
$$ 
R(y)= ((y=x \or y=y) \and y \ge x \and y\ge y) = (y \ge x) 
$$ 
МЫ ПРИХОДИМ К НАШЕМУ РЕШЕНИЮ: 
\prg 
\.{if} x\ge y \to m:=x \wbox y\ge x \to m:=y \.{fi}
\grp
пОСКОЛЬКУ $(x\ge y \or y \ge x)=T$, ОТКАЗА НИКОГДА НЕ ПРОИЗОЙДЕТ 
(ПОПУТНО МЫ ПОЛУЧИЛИ ДОКАЗАТЕЛЬСТВО СУЩЕСТВОВАНИЯ: ДЛЯ ЛЮБЫХ 
ЗНАЧЕНИЙ $x$ И $y$ СУЩЕСТВУЕТ $m$, УДОВЛЕТВОРЯЮЩЕЕ $R(m)$). 
пОСКОЛЬКУ $(x\ge y \and y\ge x)\not=F$, НАША ПРОГРАММА НЕ 
ОБЯЗАТЕЛЬНО ДЕТЕРМИНИРОВАНА. еСЛИ ПЕРВОНАЧАЛЬНО $x=y$, ТО 
ОКАЗЫВАЕТСЯ НЕОПРЕДЕЛЕННЫМ, КАКОЕ ИЗ ДВУХ ПРИСВАИВАНИЙ БУДЕТ 
ВЫБРАНО ДЛЯ ИСПОЛНЕНИЯ; ТАКАЯ НЕДЕТЕРМИНИРОВАННОСТЬ СОВЕРШЕННО 
КОРРЕКТНА, ТАК КАК МЫ ПОКАЗАЛИ, ЧТО ВЫБОР НЕ ИМЕЕТ ЗНАЧЕНИЯ.

{\sl зАМЕЧАНИЕ.} еСЛИ БЫ СРЕДИ ДОСТУПНЫХ ПРИМИТИВОВ ИМЕЛАСЬ ФУНКЦИЯ 
"$\max$", МЫ МОГЛИ БЫ НАПИСАТЬ ПРОГРАММУ $m:=\max(Х,y)$, ПОСКОЛЬКУ 
$R(\max(x,y))=T$. {\sl(кОНЕЦ ЗАМЕЧАНИЯ.)}

пОЛУЧЕННАЯ ПРОГРАММА НЕ ПРОИЗВОДИТ ОЧЕНЬ СИЛЬНОГО ВПЕЧАТЛЕНИЯ; С 
ДРУГОЙ СТОРОНЫ, МЫ ВИДИМ, ЧТО В ПРОЦЕССЕ ВЫВОДА ПРОГРАММЫ ИЗ 
ПОСТУСЛОВИЯ НА ДОЛЮ НАШЕЙ ИЗОБРЕТАТЕЛЬНОСТИ ПОЧТИ НИЧero НЕ 
ОСТАЛОСЬ.

{\sl вТОРОЙ ПРИМЕР}

дЛЯ ФИКСИРОВАННОГО ЗНАЧЕНИЯ $n$ $(n>0)$ ЗАДАНА ФУНКЦИЯ $f(i)$ ДЛЯ 
$0\le i< n$. оБЕСПЕЧИТЬ ИСТИННОСТЬ $R$:
$$
 0 \le k< n \and (\forall i:0 \le i<n:f(k)\ge f(i)) 
$$
пОСКОЛЬКУ НАША ПРОГРАММА ДОЛЖНА РАБОТАТЬ ПРИ ЛЮБОМ  ПОЛОЖИТЕЛЬНОМ 
ЗНАЧЕНИИ $n$, ТРУДНО СЕБЕ ПРЕДСТАВИТЬ, КАК МОЖНО ОБЕСПЕЧИТЬ 
ИСТИННОСТЬ $R$, НЕ ПРИБЕГАЯ К ПОМОЩИ ЦИКЛА; ПОЭТОМУ МЫ ИЩЕМ 
ОТНОШЕНИЕ $P$, КОТОРОЕ ЛЕГКО МОЖНО СДЕЛАТЬ ИСТИННЫМ  В НАЧАЛЕ 
ПРОГРАММЫ И ТАКОЕ, ЧТО В КОНЦЕ $(P \and \non BB)\Rightarrow R$.  
сЛЕДОВАТЕЛЬНО, ОТЫСКИВАЯ $P$, МЫ ИЩЕМ ОТНОШЕНИЕ, БОЛЕЕ СЛАБОЕ, ЧЕМ 
$R$; ИНАЧЕ ГОВОРЯ, МЫ ХОТИМ ПОЛУЧИТЬ ОБОБЩЕНИЕ НАШЕГО КОНЕЧНОГО 
СОСТОЯНИЯ. сТАНДАРТНЫЙ СПОСОБ ОБОБЩЕНИЯ ОТНОШЕНИЯ --- ЭТО ЗАМЕНА 
КОНСТАНТЫ ПЕРЕМЕННОЙ (ВОЗМОЖНО, В ОГРАНИЧЕННОМ ИНТЕРВАЛЕ), И ЗДЕСЬ 
МОЙ ОПЫТ ПОДСКАЗЫВАЕТ МНЕ, ЧТО НУЖНО  ЗАМЕНИТЬ  КОНСТАНТУ $n$ НОВОЙ 
ПЕРЕМЕННОЙ, НАПРИМЕР $j$, И ВЗЯТЬ В КАЧЕСТВЕ $р$
$$
 0\le k<j\le n \and (\forall i:0\le i<j:f(k)\ge f(i))
$$

ГДЕ УСЛОВИЕ $j\le n$ ДОБАВЛЕНО ДЛЯ ТОГО, ЧТОБЫ ОБЛАСТЬ 
ОПРЕДЕЛЕНИЯ ФУНКЦИИ $f$ БЫЛА КОНЕЧНОЙ. тЕПЕРЬ, ИМЕЯ ТАКОЕ
ОБОБЩЕНИЕ, МЫ ЛЕГКО ПОЛУЧАЕМ
$$
(P \and j =n) \Rightarrow R
$$

чТОБЫ ПОДТВЕРДИТЬ ВОЗМОЖНОСТЬ ИСПОЛЬЗОВАНИЯ ТАКИМ
ОБРАЗОМ ВЫБРАННОГО р, МЫ ДОЛЖНЫ РАСПОЛАГАТЬ ЛЕГКИМ 
СРЕДСТВОМ ДЛЯ ОБЕСПЕЧЕНИЯ ИСТИННОСТИ р В НАЧАЛЕ ПРОГРАММЫ.
пОСКОЛЬКУ
$$
(k=0\and j=1) \Rightarrow P
$$
МЫ ОТВАЖИВАЕМСЯ ПРЕДЛОЖИТЬ СЛЕДУЮЩУЮ СТРУКТУРУ ДЛЯ
НАШЕЙ ПРОГРАММЫ (КОММЕНТАРИИ ДАЮТСЯ В СКОБКАХ):
\prg
k,j:=0, 1 \{P СТАЛО ИСТИННЫМ\};
\.{do} j\not= n \to НЕКИЙ ШАГ К j=n ПРИ ИНВАРИАНТНОСТИ P \.{od}
\{R СТАЛО ИСТИННЫМ\}
\grp

сНОВА МОЙ ОПЫТ ПОДСКАЗЫВАЕТ МНЕ ВЫБРАТЬ В КaЧЕСТВЕ
МОНОТОННО УБЫВАЮЩЕЙ ФУНКЦИИ $t$  ТЕКУЩЕГО СОСТОЯНИЯ ФУНКЦИЮ
$t=(n-j)$, КОТОРАЯ И В САМОМ ДЕЛЕ ТАКОВА, ЧТО $р\Leftarrow(t\ge 0)$.
чТОБЫ ГАРАНТИРОВАТЬ МОНОТОННОЕ УБЫВАНИЕ $t$, Я ПРЕДЛАГАЮ
УВЕЛИЧИВАТЬ $j$ НА 1, ПОСЛЕ ЧЕГО МЫ МОЖЕМ НАПИСАТЬ
$$
\displaylines{
\wp("j:=j+1", P)=\cr
0\le k<j+1\le n \and(\forall i:0\le i<j+1:f(k)\ge f(i))=\cr
0\le k<j+1\le n \and(\forall i:0\le i<j : f(k)\ge f(i))\and f(k)\ge f(j)\cr
}
$$

пЕРВЫЕ ДВА ЧЛЕНА СЛЕДУЮТ ИЗ $P \and j\not=n$  (ПОТОМУ ЧТО
$(j\le n \and j\not=n)\Rightarrow (j+1\le n)$, И ИМЕННО ПОЭТОМУ МЫ РЕШИЛИ УВЕЛИЧИТЬ 
$j$  ТОЛЬКО НА 1). сЛЕДОВАТЕЛЬНО,
$$
(P \and j\not=n \and f(k)\ge f(j)) \Rightarrow  \wp ("j:=j+1",P)
$$
И МЫ МОЖЕМ ИСПОЛЬЗОВАТЬ ПОСЛЕДНЕЕ УСЛОВИЕ В КАЧЕСТВЕ
ПРЕДОХРАНИТЕЛЯ. пРОГРАММА
\prg
k, j:=0,1;
\.{do} j \NE n\to \.{if} f(k)\ge f(j)\to j:=j+1 \.{fi} \.{od}
\grp
ДЕЙСТВИТЕЛЬНО ДАСТ ПРАВИЛЬНЫЙ ОТВЕТ, ЕСЛИ ОНА ЗАВЕРШИТСЯ
НОРМАЛЬНО. оДНАКО НОРМАЛЬНОЕ ЗАВЕРШЕНИЕ НЕ ГАРАНТИРОВАНО,
ПОСКОЛЬКУ КОНСТРУКЦИЯ ВЫБОРА МОЖЕТ ПРИВЕСТИ К ОТКАЗУ --- И
ЭТО ДЕЙСТВИТЕЛЬНО ТАК И БУДЕТ, ЕСЛИ $k=0$ НЕ УДОВЛЕТВОРЯЕТ $R$.
еСЛИ НЕВЕРНО, ЧТО $f(k) \ge f(i)$, МЫ МОЖЕМ СДЕЛАТЬ ЭТО ОТНОШЕНИЕ
ВЕРНЫМ ПРИ ПОМОЩИ ПРИСВАИВАНИЯ $k:=j$ И ПРОДОЛЖИТЬ
НАШИ ИССЛЕДОВАНИЯ:
$$
\displaylines{
\wp("k,j:=j,j+1", P)=\cr
0\le j<j+1\le n \and (\forall i: 0\le i<j+1:f(j)\ge f(i))=\cr
0\le j<j+1\le n \and (\forall i:0\le i<j:f(j)\ge f(i))\cr
}
$$
с ОГРОМНЫМ ОБЛЕГЧЕНИЕМ МЫ ЗАМЕЧАЕМ, ЧТО
$$
(P\and j\not=n\and f(k)\le f(j))\Rightarrow \wp("k,j:=j,j+1",P)
$$

И СЛЕДУЮЩАЯ ПРОГРАММА БУДЕТ РАБОТАТЬ, НЕ ПОДВЕРГАЯСЬ ОПАСНОСТИ 
ОТКАЗА.
\prg
k, j=0,1;
\.{do} j\NE n\to \.{if} f(k)\GE f(j)\to j:=j+1
\wbox f(k)\le f(j) \to k,j:=j,j+1 \.{fi} \.{od}
\grp

сЛЕДУЕТ СДЕЛАТЬ НЕСКОЛЬКО ПРИМЕЧАНИЙ. пЕРВОЕ: ПОСКОЛЬКУ
ПРЕДОХРАНИТЕЛИ КОНСТРУКЦИИ ВЫБОРА НЕ ОБЯЗАТЕЛЬНО ИСКЛЮЧАЮТ
ДРУГ ДРУГА, ПРОГРАММА ТАИТ В СЕБЕ ВНУТРЕННЮЮ НЕДЕТЕРМИНИРОВАННОСТЬ
ТОГО ЖЕ ТИПА, ЧТО И В ПЕРВОМ ПРИМЕРЕ. эТА 
НЕДЕТЕРМИРОВАННОСТЬ МОЖЕТ ПРОЯВИТЬСЯ И ВНЕШНЕ. фУНКЦИЯ
$f$ МОГЛА ОКАЗАТЬСЯ ТАКОЙ, ЧТО КОНЕЧНОЕ ЗНАЧЕНИЕ $k$ НЕОДНОЗНАЧНО;
В ЭТОМ СЛУЧАЕ НАША ПРОГРАММА МОЖЕТ ВЫРАБОТАТЬ ЛЮБОЕ
ДОПУСТИМОЕ ЗНАЧЕНИЕ!

вТОРОЕ ПРИМЕЧАНИЕ: ТО, ЧТО МЫ ПОСТРОИЛИ ПРАВИЛЬНУЮ ПРОГРАММУ,
НЕ ОЗНАЧАЕТ, ЧТО МЫ СПРАВИЛИСЬ С ЗАДАЧЕЙ. пРОГРАММИРОВАНИЕ
В РАВНОЙ СТЕПЕНИ ЯВЛЯЕТСЯ КАК МАТЕМАТИЧЕСКОЙ, ТАК И ИНЖЕНЕРНОЙ
ДИСЦИПЛИНОЙ; МЫ ДОЛЖНЫ ЗАБОТИТЬСЯ О ПРАВИЛЬНОСТИ В ТОЙ
ЖЕ МЕРЕ, КАК СКАЖЕМ, И ОБ ЭФФЕКТИВНОСТИ. иСХОДЯ ИЗ
ПРЕДПОЛОЖЕНИЯ, ЧТО НА ВЫЧИСЛЕНИЕ ЗНАЧЕНИЯ ФУНКЦИИ $f$ 
ДЛЯ ДАННОГО АРГУМЕНТА ЗАТРАЧИВАЕТСЯ ОТНОСИТЕЛЬНО МНОГО ВРЕМЕНИ,
ХОРОШИЙ ИНЖЕНЕР ДОЛЖЕН ОБРАТИТЬ ВНИМАНИЕ НА ТО, ЧТО В
ПРОГРАММЕ, ПО ВСЕЙ ВЕРОЯТНОСТИ, БУДЕТ МНОГОКРАТНО ВЫЧИСЛЯТЬСЯ
$f(k)$ ДЛЯ ОДНОГО И ТОГО ЖЕ ЗНАЧЕНИЯ $k$. в ЭТОМ СЛУЧАЕ
РЕКОМЕНДУЕТСЯ ПОЙТИ НА СДЕЛКУ И ПОЖЕРТВОВАТЬ НЕКОТОРЫМ
ОБоЕМОМ ПАМЯТИ, ЧТОБЫ СЭКОНОМИТЬ ЧАСТЬ ВРЕМЕНИ, ЗАТРАЧИВАЕМОГО
НА ВЫЧИСЛЕНИЕ. нО ПРИ ЭТОМ НАШИ УСИЛИЯ, НАПРАВЛЕННЫЕ НА
ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ПРОГРАММЫ И УМЕНЬШЕНИЕ
ЗАТРАТ ВРЕМЕНИ, НИ В КОЕЙ МЕРЕ НЕ ДОЛЖНЫ СЛУЖИТЬ ИЗВИНЕНИЕМ
ЗА ВНЕСЕНИЕ БЕСПОРЯДКА В ПРОГРАММУ. (эТО ОЧЕВИДНАЯ ВЕЩЬ, НО Я ХОЧУ
ПОДЧЕРКНУТЬ ЭТУ МЫСЛЬ, ПОТОМУ ЧТО ОЧЕНЬ ЧАСТО
ЗАПУТАННОСТЬ ПРОГРАММЫ ОПРАВДЫВАЕТСЯ ССЫЛКОЙ НА
ЭФФЕКТИВНОСТЬ. оДНАКО ПРИ БЛИЖАЙШЕМ РАССМОТРЕНИИ ТАКОЕ
ОПРАВДАНИЕ ВСЕГДА ОКАЗЫВАЕТСЯ НЕОБОСНОВАННЫМ, ДОЛЖНО БЫТЬ,
ПОТОМУ, ЧТО ЗАПУТАННОСТЬ ПРОГРАММЫ ВСЕГДА НЕОПРАВДАННА.)
чТОБЫ АККУРАТНО РЕАЛИЗОВАТЬ ОБМЕН ВРЕМЕНИ ВЫЧИСЛЕНИЙ НА
ПАМЯТЬ, МОЖНО ВОСПОЛЬЗОВАТЬСЯ МЕТОДОМ ВВЕДЕНИЯ ОДНОЙ ИЛИ
НЕСКОЛЬКИХ ДОПОЛНИТЕЛЬНЫХ ПЕРЕМЕННЫХ, ЧЬЕ ЗНАЧЕНИЕ МОЖНО
ИСПОЛЬЗОВАТЬ, ТАК КАК СОХРАНЯЕТСЯ ИНВАРИАНТНЫМ НЕКОТОРОЕ
ОТНОШЕНИЕ. в ДАННОМ ПРИМЕРЕ БЫЛО ЗАМЕЧЕНО, ЧТО ВОЗМОЖНЫ
ЧАСТЫЕ ПОВТОРНЫЕ ВЫЧИСЛЕНИЯ f(k) ДЛЯ ОДНОГО И ТОГО ЖЕ $k$, 
А ЭТО НАВОДИТ НА МЫСЛЬ О ВВЕДЕНИИ ДОПОЛНИТЕЛЬНОЙ 
ПЕРЕМЕННОЙ, СКАЖЕМ $max$, И РАСШИРЕНИИ ИНВАРИАНТНОГО ОТНОШЕНИЯ
ЗА СЧЕТ ДОПОЛНИТЕЛЬНОГО ЧЛЕНА
$$
max=f(k)
$$

эТО ОТНОШЕНИЕ ДОЛЖНО СТАТЬ ИСТИННЫМ, КОГДА k  ПОЛУЧИТ
НАЧАЛЬНОЕ ЗНАЧЕНИЕ, И ДОЛЖНО СОХРАНЯТЬСЯ ИНВАРИАНТНЫМ (ПРИ
ПОМОЩИ ЯВНОГО ПРИСВАИВАНИЯ ЗНАЧЕНИЯ ПЕРЕМЕННОЙ $max$) 
ПОСЛЕ ИЗМЕНЕНИЯ k. мЫ ПРИХОДИМ К СЛЕДУЮЩЕЙ ПpoГpaММЕ:
\prg
k,j, max:=0,1,f(0);
\.{do} j \NE n\to \.{if} max \GE f(j) \to j:=j+1
\wbox max\LE f(j) \to k, j, max:=j, j+1, f(j) \.{fi} \.{od}
\grp

вЕРОЯТНО, ЭТА ПРОГРАММА ГОРАЗДО БОЛЕЕ ЭФФЕКТИВНА, ЧЕМ
НАША ПРЕДЫДУШАЯ ВЕРСИЯ, в ТАКОМ СЛУЧАЕ ХОРОШИЙ ИНЖЕНЕР
НА ЭТОМ НЕ ОСТАНОВИТСЯ, ПОТОМУ ЧТО ТЕПЕРЬ ОН ОБНАРУЖИТ, ЧТО
МОГ БЫ РАСПОРЯДИТЬСЯ ПОВТОРНЫМИ ВЫЧИСЛЕНИЯМИ $f(j)$ ДЛЯ
ОДНОГО И ТОГО ЖЕ $j$. дЛЯ ЭТОГО МОЖНО ВВЕСТИ ДОПОЛНИТЕЛЬНУЮ
ПЕРЕМЕННУЮ, СКАЖЕМ $h$, И ОБЕСПЕЧИТЬ ИНВАРИАНТНОСТЬ
$$
h=f(j)
$$

оДНАКО МЫ Нe МОЖЕМ СДЕЛАТЬ ЭТО НА ТОМ ЖЕ ГЛОБАЛЬНОМ
УРОВНЕ, КАК ДЛЯ НАШЕГО ПРЕДЫДУЩЕГО ЧЛЕНА: ЗНАЧЕНИЕ $j=n$ НЕ
ИСКЛЮЧЕНО, А ПРИ ЭТОМ ЗНАЧЕНИЕ $f(j)$ НЕ ОБЯЗАТЕЛЬНО ОПРЕДЕЛЕНО.
сЛЕДОВАТЕЛЬНО, ИСТИННОСТЬ ОТНОШЕНИЯ $h=f(j)$ ДОЛЖНА
ЗАНОВО ОБЕСПЕЧИВАТЬСЯ ПОСЛЕ КАЖДОЙ ПРОВЕРКИ, ПОКАЗЫВАЮЩЕЙ,
ЧТО $j\not=n$, ПО ЗАВЕРШЕНИИ ВНЕШНЕЙ ОХРАНЯЕМОЙ КОМАНДЫ (ТАК
СКАЗАТЬ, "КАК РАЗ ПЕРЕД od") МЫ ИМЕЕМ $h=f(j-1)$, НО НАС ЭТО
НЕ ДОЛЖНО БЕСПОКОИТЬ, И ПУСТЬ ВСЕ ОСТАЕТСЯ ТАК, КАК ЕСТЬ.
\prg
k, j, max:= 0, 1, f(0);
\.{do} j\NE n\to h:=f(j);
         \.{if} max\GE h \to j:=j+1
\wbox max \LE h \to k, j, max:=j, j+1, h \.{fi} \.{od}
\grp

пОСЛЕДНЕЕ ПРИМЕЧАНИЕ КАСАЕТСЯ НЕ СТОЛЬКО НАШЕГО РЕШЕНИЯ
ЗАДАЧИ, СКОЛЬКО НАШИХ СООБРАЖЕНИЙ О ПОДХОДЕ К РЕШЕНИЮ.
мЫ ГОВОРИЛИ О МАТЕМАТИЧЕСКОМ ПОДХОДЕ, МЫ ГОВОРИЛИ ОБ
ИНЖЕНЕРНОМ ПОДХОДЕ И ПРОВЕЛИ РАЗДЕЛЕНИЕ МЕЖДУ ЭТИМИ ПОДХОДАМИ,
СОСРЕДОТОЧИВАЯ ВНИМАНИЕ ТО НА ОДНОМ, ТО НА ДРУГОМ АСПЕКТЕ.
хОТЯ РАЗДЕЛЕНИЕ ПОДХОДОВ АБСОЛЮТНО НЕОБХОДИМО,
КОГДА РЕЧЬ ИДЕТ О БОЛЕЕ СЛОЖНЫХ ЗАДАЧАХ, Я ДОЛЖЕН ПОДЧЕРКНУТЬ,
ЧТО, СОСРЕДОТОЧИВАЯ ВНИМАНИЕ НА ОДНОМ ИЗ АСПЕКТОВ, НЕ
СЛЕДУЕТ ПОЛНОСТЬЮ ИГНОРИРОВАТЬ ДРУГИЕ АСПЕКТЫ. рАЗРАБАТЫВАЯ
МАТЕМАТИЧЕСКУЮ ЧАСТЬ ПРОЕКТА, МЫ ДОЛЖНЫ ПОМНИТЬ, ЧТО ДАЖЕ
МАТЕМАТИЧЕСКИ ПРАВИЛЬНАЯ ПРОГРАММА МОЖЕТ ПОГИБНУТЬ,
ЕСЛИ ОНА ПЛОХА С ИНЖЕНЕРНОЙ ТОЧКИ ЗРЕНИЯ. аНАЛОГИЧНО, ОСУЩЕСТВЛЯЯ
"СДЕЛКУ" МЕЖДУ ПАМЯТЬЮ И ВРЕМЕНЕМ, МЫ ДОЛЖНЫ ДЕЛАТЬ
ЭТО АККУРАТНО И СИСТЕМАТИЧЕСКИ, ЧТОБЫ ПО НЕРЯШЛИВОСТИ
НЕ ВНЕСТИ ОШИБОК В ПРОГРАММУ; КРОМЕ ТОГО, ХОТЯ ПРЕДВАРИТЕЛЬНО
БЫЛ ПРОВЕДЕН МАТЕМАТИЧЕСКИЙ АНАЛИЗ, МЫ ДОЛЖНЫ
К ТОМУ ЖЕ ДОСТАТОЧНО ХОРОШО РАЗБИРАТЬСЯ В ЗАДАЧЕ, ЧТОБЫ
СУДИТЬ О ТОМ, ПРИВЕДУТ ЛИ ПРЕДПОЛАГАЕМЫЕ ИЗМЕНЕНИЯ К ЗНАЧИТЕЛЬНОМУ
УЛУЧШЕНИЮ ПРОГРАММЫ.

{\sl зАМЕЧАНИЕ.} дО ТОГО КАК Я НАЧАЛ ПОЛЬЗОВАТЬСЯ ЭТИМИ ФОРМАЛЬНЫМИ
ПОСТРОЕНИЯМИ, Я ВСЕГДА ИСПОЛЬЗОВАЛ "$j<n$" В КАЧЕСТВЕ 
ПРЕДОХРАНИТЕЛЯ В ЭТОЙ КОНСТРУКЦИИ ПОВТОРЕНИЯ, ТЕПЕРЬ Я
ДОЛЖЕН ОТУЧИТоСЯ ОТ ЭТОЙ ПРИВЫЧКИ, ТАК КАК В СЛУЧАЕ, ПОДОБНОМ
ДАННОМУ, КОНЕЧНО, ПРЕДПОЧТИТЕЛЬНЕЕ ПРЕДОХРАНИТЕЛЬ "$j\not= n$".
дЛЯ ЭТОГО ИМЕЮТСЯ ДВЕ ПРИЧИНЫ. пРЕДОХРАНИТЕЛЬ "$j\not=n$"
ПОЗВОЛЯЕТ НАМ СДЕЛАТЬ ВЫВОД, ЧТО ПО ЗАВЕРШЕНИИ ПРОГРАММЫ 
$j=n$, НЕ ССЫЛАЯСЬ ПРИ ЭТОМ НА ИНВАРИАНТНОЕ ОТНОШЕНИЕ $P$;
ТЕМ САМЫМ УПРОЩАЕТСЯ ДИСКУССИЯ О ТОМ, ЧТО ДАЕТ НАМ
ВСЯ КОНСТРУКЦИЯ В ЦЕЛОМ ПО СРАВНЕНИЮ С ПРЕДОХРАНИТЕЛЕМ "$j<n$".
гОРАЗДО ВАЖНЕЕ, ОДНАКО, ЧТО ПРЕДОХРАНИТЕЛЬ "$j\not=n$"
СТАВИТ ЗАВЕРШЕНИЕ ПРОГРАММЫ В ЗАВИСИМОСТЬ ОТ (ЧАСТИ) ИНВАРИАНТНОГО
ОТНОШЕНИЯ, А ИМЕННО $j\le n$, И ПОЭТОМУ ЕМУ СЛЕДУЕТ
ОТДАТЬ ПРЕДПОЧТЕНИЕ, ТАК КАК ЕГО ИСПОЛЬЗОВАНИЕ ПРИВЕДЕТ К
УСИЛЕНИЮ КОНСТРУКЦИИ. еСЛИ В РЕЗУЛЬТАТЕ ВЫПОЛНЕНИЯ $j:=j+1$
ЗНАЧЕНИЕ $j$ ТАК ВОЗРАСТЕТ, ЧТО СТАНЕТ СПРАВЕДЛИВЫМ ОТНОШЕНИЕ
$j>n$, ПРЕДОХРАНИТЕЛЬ "$j<n$" НЕ ПОДНИМЕТ ТРЕВОГУ, ТОГДА
КАК ПРЕДОХРАНИТЕЛЬ "$j\not=n$" ПО КРАЙНЕЙ МЕРЕ НЕ ДОПУСТИТ
НОРМАЛЬНОГО ЗАВЕРШЕНИЯ. тАКОЙ АРГУМЕНТ ПРЕДСТАВЛЯЕТСЯ ВПОЛНЕ
ВЕСОМЫМ, ДАЖЕ ЕСЛИ НЕ ПРИНИМАТЬ ВО ВНИМАНИЕ СБОЙ МАШИНЫ.
пУСТЬ В ПОСЛЕДОВАТЕЛЬНОСТИ $x_0$, $x_1$, $x_2$, \dots ЗНАЧЕНИЕ $x_0$ ЗАДАЕТСЯ,
А ЗНАЧЕНИЕ $x_i$ ДЛЯ $i>0$ ОПРЕДЕЛЯЕТСЯ КАК $x_i=f(x_{i-1})$, ГДЕ $f$ ---
НЕКОТОРАЯ ВЫЧИСЛИМАЯ ФУНКЦИЯ. бУДЕМ ВНИМАТЕЛЬНО И ТОЧНО
СЛЕДИТЬ ЗА ТЕМ. ЧТОБЫ СОХРАНЯЛОСЬ ИНВАРИАНТНЫМ ОТНОШЕНИЕ
$X=x_i$. пРЕДПОЛОЖИМ, ЧТО В ПРОГРАММЕ ИМЕЕТСЯ МОНОТОННО
ВОЗРАСТАЮЩАЯ ПЕРЕМЕННАЯ $n$, ТАКАЯ, ЧТО ДЛЯ НЕКОТОРЫХ 
ЗНАЧЕНИЙ $n$ НАС ИНТЕРЕСУЮТ $x_n$. пРИ УСЛОВИИ ЧТО $n\ge i$, МЫ ВСЕГДА
МОЖЕМ СДЕЛАТЬ ИСТИННЫМ ОТНОШЕНИЕ $X=x_n$ ПРИ ПОМОЩИ
\prg
\.{do} i\NE n \TO i, X:=i+1, f(X) \.{od}
\grp

еСЛИ ЖЕ ОТНОШЕНИЕ $n\ge i$ НЕ ОБЯЗАТЕЛЬНО ИМЕЕТ МЕСТО
(МОЖЕТ БЫТЬ, ПОСЛЕДУЮЩИЕ ИЗМЕНЕНИЯ В ПРОГРАММЕ ПРИВЕЛИ К
ТОМУ, ЧТО В ПРОЦЕССЕ ВЫЧИСЛЕНИЙ $n$ БУДЕТ НЕ ТОЛЬКО ВОЗРАСТАТЬ),
ПРИВЕДЕННАЯ ВЫШЕ КОНСТРУКЦИЯ (К СЧАСТЬЮ!) НЕ ПРИДЕТ К ЗАВЕРШЕНИЮ,
В ТО ВРЕМЯ КАК КОНСТРУКЦИЯ
\prg
\.{do} i<n\TO i, X:= i+1, f(X) \.{od}
\grp
НЕ ОБЕСПЕЧИТ ИСТИННОСТИ ОТНОШЕНИЯ $X=x_n$. мОРАЛЬ ЭТОЙ
ИСТОРИИ ТАКОВА, ЧТО ПРИ ПРОЧИХ РАВНЫХ УСЛОВИЯХ МЫ ДОЛЖНЫ
ВЫБИРАТЬ НАШИ ПРЕДОХРАНИТЕЛИ КАК МОЖНО БОЛЕЕ СЛАБЫМИ.
{\sl (кОНЕЦ ЗАМЕЧАНИЯ.)}

тРЕТИЙ ПРИМЕР

дЛЯ ФИКСИРОВАННЫХ $a(a\ge 0)\hbox{ И }d(d>0)$ ТРЕБУЕТСЯ
ОБЕСПЕЧИТЬ ИСТИННОСТЬ R:
$$
0\le r< d \and d|(a-r)
$$
(зДЕСЬ ВЕРТИКАЛЬНАЯ ЧЕРТА "$|$" ЗАМЕНЯЕТ СОБОЙ СЛОВА
"ЯВЛЯЕТСЯ ДЕЛИТЕЛЕМ".) иНАЧЕ ГОВОРЯ, НАМ ТРЕБУЕТСЯ ВЫЧИСЛИТЬ
НАИМЕНЬШИЙ НЕОТРИЦАТЕЛЬНЫЙ ОСТАТОК $r$, ПОЛУЧЕННЫЙ В РЕЗУЛЬТАТЕ
ДЕЛЕНИЯ $a$ НА $d$. чТОБЫ ЭТА ЗАДАЧА ДЕЙСТВИТЕЛЬНО БЫЛА ЗАДАЧЕЙ,
МЫ ДОЛЖНЫ ОГРАНИЧИТЬ ИСПОЛЬЗОВАНИЕ АРИФМЕТИЧЕСКИХ
ОПЕРАЦИЙ ТОЛЬКО ОПЕРАЦИЯМИ СЛОЖЕНИЯ И ВЫЧИТАНИЯ. пОСКОЛЬКУ
УСЛОВИЕ $d|(a-r)$ ВЫПОЛНЯЕТСЯ ПРИ $r=a$ И ПРИ ЭТОМ, ТАК КАК
$a\ge 0$, ВЕРНО, ЧТО $0\le r$, ПРЕДЛАГАЕТСЯ ВЫБРАТЬ В КАЧЕСТВЕ
ИНВАРИАНТНОГО ОТНОШЕНИЯ $P$:
$$
0 \le r \and d|(a-r)
$$

в КАЧЕСТВЕ ФУНКЦИИ $t$, УБЫВАНИЕ КОТОРОЙ ДОЛЖНО 
ОБЕСПЕЧИТЬ ЗАВЕРШЕНИЕ РАБОТЫ ПРОГРАММЫ, МЫ ВЫБИРАЕМ САМО $r$.
пОСКОЛЬКУ ИЗМЕНЕНИЕ $r$ ДОЛЖНО БЫТЬ ТАКИМ, ЧТОБЫ НЕИЗМЕННО
ВЫПОЛНЯЛОСЬ УСЛОВИЕ $d|(a-r)$, $r$ МОЖНО ИЗМЕНЯТЬ ТОЛЬКО НА ЧИСЛО,
КРАТНОЕ $d$, НАПРИМЕР НА САМО $d$. тАКИМ ОБРАЗОМ, НАМ, КАК
ОКАЗАЛОСЬ, ПРЕДЛАГАЕТСЯ ВЫЧИСЛИТЬ
$$
\wp("r:=r-d", P) \and \wdec("r:=r-d", r)=0\le r-d \and d|(a-r+d) \and d>0
$$

пОСКОЛЬКУ ЧЛЕН $d>0$ МОЖНО БЫЛО БЫ ДОБАВИТЬ К ИНВАРИАНТНОМУ
ОТНОШЕНИЮ $P$, ОБОСНОВАНИЯ ТРЕБУЕТ ТОЛЬКО ПЕРВЫЙ ЧЛЕН;
МЫ НАХОДИМ СООТВЕТСТВУЮЩИЙ ПРЕДОХРАНИТЕЛЬ "$r\ge d$"
И ПРОБУЕМ СОСТАВИТЬ ТАКУЮ ПРОГРАММУ:
\prg
\.{if} a \GE 0 \and d>0 \TO
  r:=a;
  \.{do} r \GE d \TO r:=r-d \.{od}
\.{fi}
\grp

пО ЗАВЕРШЕНИИ ПРОГРАММЫ СТАЛО ИСТИННЫМ ОТНОШЕНИЕ
$P\and\non r\ge d$, ИЗ ЧЕГО СЛЕДУЕТ ИСТИННОСТЬ $R$, И, ТАКИМ ОБРАЗОМ,
ЗАДАЧА РЕШЕНА.

пРЕДПОЛОЖИМ ТЕПЕРЬ, ЧТО НАМ, КРОМЕ ТОГО, ПОТРЕБОВАЛОСЬ БЫ
ПРИСВОИТЬ $q$  ТАКОЕ ЗНАЧЕНИЕ, ЧТОБЫ ПО ОКОНЧАНИИ ПРОГРАММЫ
БЫЛО БЫ ТАКЖЕ ВЕРНО, ЧТО
$$
a=d *q+r
$$
ИНАЧЕ ГОВОРЯ, ТРЕБУЕТСЯ НАЙТИ НЕ ТОЛЬКО ОСТАТОК, НО И ЧАСТНОЕ.
пОПРОБУЕМ ДОБАВИТЬ ЭТОТ ЧЛЕН К НАШЕМУ ИНВАРИАНТНОМУ ОТНОШЕНИЮ.
пОСКОЛЬКУ
$$
(a=d* q+r)\Rightarrow (a=d*(q+1)+(r-d))
$$
МЫ ПРИХОДИМ К ПРОГРАММЕ
\prg
\.{if} a \GE 0 \and d>0 \TO
 q, r:=0, a;
 \.{do} r \GE d \to q,  r:=q+1, r-d \.{od}
\.{fi}
\grp
нА ВЫПОЛНЕНИЕ ПРИВЕДЕННЫХ ВЫШЕ ПРОГРАММ БУДЕТ, КОНЕЧНО,
ЗАТРАЧИВАТЬСЯ ОЧЕНЬ МНОГО ВРЕМЕНИ, ЕСЛИ ЧАСТНОЕ ВЕЛИКО. мОЖЕМ
ЛИ МЫ СОКРАТИТЬ ЭТО ВРЕМЯ? оЧЕВИДНО, ЭТОГО МОЖНО ДОБИТЬСЯ,
ЕСЛИ УМЕНЬШАТЬ $r$ НА ВЕЛИЧИНУ, КРАТНУЮ И БОЛЬШУЮ $d$. вВОДЯ
ДЛЯ ЭТОЙ ЦЕЛИ НОВУЮ ПЕРЕМЕННУЮ, СКАЖЕМ $dd$, МЫ ПОЛУЧАЕМ
УСЛОВИЕ, КОТОРОЕ ДОЛЖНО НЕИЗМЕННО ВЫПОЛНЯТЬСЯ НА ПРОТЯЖЕНИИ
ВСЕЙ Рa6oТЫ ПРОГРАММЫ:
$$
d|dd \and dd \GE d
$$

мЫ МОЖЕМ УСКОРИТЬ НАШУ ПЕРВУЮ ПРОГРАММУ, ЗАМЕНИВ
"$r:=r-d$" УМЕНЬШЕНИЕМ, ВОЗМОЖНО ПОВТОРНЫМ, $r$ НА $dd$,
ПРЕДОСТАВЛЯЯ В ТО ЖЕ ВРЕМЯ ВОЗМОЖНОСТЬ $dd$, ПЕРВОНАЧАЛЬНО 
РАВНОМУ $d$, ДОВОЛЬНО БЫСТРО ВОЗРАСТАТЬ, НАПРИМЕР КАЖДЫЙ РАЗ
УДВАИВАЯ $dd$. тОГДА МЫ ПРИХОДИМ К СЛЕДУЮЩЕЙ ПРОГРАММЕ:
\prg
\.{if} a \ge 0 \and d>0\to
  r:=a;
  \.{do} r\ge d \to
    dd:=d;
    \.{do} r\ge dd\to r:=r-dd; dd:=dd+dd \.{od}
  \.{od}
\.{fi}
\grp
яСНО, ЧТО ОТНОШЕНИЕ $0\le r \and d|(a-r)$ СОХРАНЯЕТСЯ
ИНВАРИАНТНЫМ, И ПОЭТОМУ ПРОГРАММА ОБЕСПЕЧИТ ИСТИННОСТЬ $R$,
ЕСЛИ ОНА ЗАВЕРШИТСЯ НОРМАЛЬНО, НО ТАК ЛИ ЭТО? кОНЕЧНО, ТАК,
ПОСКОЛЬКУ ВНУТРЕННИЙ ЦИКЛ, КОТОРЫЙ ЗАВЕРШАЕТСЯ ПРИ $dd>0$,
ВОЗБУЖДАЕТСЯ ТОЛЬКО ПРИ НАЧАЛЬНЫХ СОСТОЯНИЯХ, УДОВЛЕТВОРЯЮЩИХ
УСЛОВИЮ $r\ge dd$, И ПОЭТОМУ УМЕНЬШЕНИЕ $r:=r-dd$
ВЫПОЛНЯЕТСЯ ПО КРАЙНЕЙ МЕРЕ ОДИН РАЗ ДЛЯ КАЖДОГО ПОВТОРЕНИЯ
ВНЕШНЕГО ЦИКЛА.

нО ТАКОЕ РАССУЖДЕНИЕ (ХОТЯ И ДОСТАТОЧНО УБЕДИТЕЛЬНОЕ!)
ЯВЛЯЕТСЯ ВЕСЬМА НЕФОРМАЛЬНЫМ, А ПОСКОЛЬКУ В ЭТОЙ ГЛАВЕ МЫ
ГОВОРИМ О ФОРМАЛЬНОМ ПОСТРОЕНИИ ПРОГРАММ, МЫ МОЖЕМ ПОПРОБОВАТЬ
СФОРМУЛИРОВАТЬ И ДОКАЗАТЬ ТЕОРЕМУ, КОТОРОЙ ИНТУИТИВНО 
ВОСПОЛЬЗОВАЛИСЬ.

пУСТЬ IF, DO И вв ПОНИМАЮТСЯ В ОБЫЧНОМ СМЫСЛЕ, И
$P$ --- ЭТО ОТНОШЕНИЕ, СОХРАНЯЮЩЕЕСЯ ИНВАРИАНТНЫМ, Т.Е.
$$
(P \and BB)\Rightarrow \wp (IF, P) \qquad\hbox{ДЛЯ ВСЕХ СОСТОЯНИЙ}
\eqno(1)
$$
И ПУСТЬ $t$ --- ЦЕЛОЧИСЛЕННАЯ ФУНКЦИЯ, ТАКАЯ, ЧТО ДЛЯ ЛЮБОГО 
ЗНАЧЕНИЯ $t_0$ И ДЛЯ ВСЕХ СОСТОЯНИЙ
$$
(P \and BB \and t\le t_0+1)\to \wp(IF, t\le t_0)
\eqno(2)
$$
ИЛИ, ЧТО ТО ЖЕ,
$$
(P \and BB)\Rightarrow \wdec(IF,t) \qquad\hbox{ДЛЯ ВСЕХ СОСТОЯНИЙ}
\eqno(3)
$$

тОГДА ДЛЯ ЛЮБОГО ЗНАЧЕНИЯ $t_0$ И ДЛЯ ВСЕХ СОСТОЯНИЙ
$$
(P \and BB \and \wp(DO, T) \and t\le t_0+1) \Rightarrow \wp (DO,t\le t_0)
\eqno(4)
$$
ИЛИ, ЧТО ТО ЖЕ,
$$
(P\and BB\and\wp(DO,T))\Rightarrow \wdec(DO,t)
\eqno(5)
$$
в СЛОВЕСНОЙ ФОРМУЛИРОВКЕ: ЕСЛИ СОХРАНЯЕМОЕ ИНВАРИАНТНЫМ
ОТНОШЕНИЕ $P$ ГАРАНТИРУЕТ, ЧТО КАЖДАЯ ВЫБРАННАЯ ДЛЯ ИСПОЛНЕНИЯ
ОХРАНЯЕМАЯ КОМАНДА ВЫЗЫВАЕТ ДЕЙСТВИТЕЛЬНОЕ УМЕНЬШЕНИЕ $t$,
ТО КОНСТРУКЦИЯ ПОВТОРЕНИЯ ВЫЗОВЕТ ДЕЙСТВИТЕЛЬНОЕ УМЕНЬШЕНИЕ
$t$, ЕСЛИ ОНА НОРМАЛЬНО ЗАВЕРШИТСЯ ПОСЛЕ ПО КРАЙНЕЙ МЕРЕ
ОДНОГО ВЫПОЛНЕНИЯ КАКОЙ-ЛИБО ОХРАНЯЕМОЙ КОМАНДЫ.
тЕОРЕМА НАСТОЛЬКО ОЧЕВИДНА, ЧТО БЫЛО БЫ ДОСАДНО, ЕСЛИ БЫ ЕЕ
ДОКАЗАТЕЛЬСТВО ОКАЗАЛОСЬ ТРУДНЫМ, НО, К СЧАСТЬЮ, ЭТО НЕ ТАК.
мЫ ПОКАЖЕМ, ЧТО ИЗ (1) И (2) СЛЕДУЕТ, ЧТО ДЛЯ ЛЮБОГО ЗНАЧЕНИЯ
$t_0$ И ДЛЯ ВСЕХ СОСТОЯНИЙ
$$
(P \and BB and H_k(T)) \and t\le t_0+1)\Rightarrow  H_k (t \le t_0)   
\eqno (6)
$$
ДЛЯ ВСЕХ $k \ge 0$. эТО СПРАВЕДЛИВО ДЛЯ $k=0$, ПОСКОЛЬКУ 
$(BB\and H_0(T))=F$, И, ИСХОДЯ ИЗ ПРЕДПОЛОЖЕНИЯ, ЧТО (6)
СПРАВЕДЛИВО ДЛЯ $k=K$, МЫ ДОЛЖНЫ ПОКАЗАТЬ, ЧТО (6) СПРАВЕДЛИВО
И ДЛЯ $k=K+1$.
$$
\displaylines{
(P \and BB \and H_{K+1}(T) \and t \le t_0+1)\cr
\eqalign{
&\Rightarrow \wp(IF, P) \and \wp(IF, H_K (T)) \and \wp(lF, t\le t_0)\cr
&=\wp(IF, P \and H_K(T) \and t\le t_0)\cr
&\Rightarrow \wp ((IF, (P \and BB \and H_K(T) \and t\le t0+1) \or (t\le t_0  \and \non BB))\cr
&\Rightarrow \wp(IF, H_K(t\le t_0) \or H_0(t\le t_0))\cr
&=\wp(IF, H_K(t\le t_0))\cr
&\Rightarrow \wp(IF, H_K(t\le t_0)) \or H_0(t\le t_0)\cr
&=H_{K+1}(t\le t_0)\cr
}\cr
}
$$

пЕРВАЯ ИМПЛИКАЦИЯ СЛЕДУЕТ ИЗ (1), ОПРЕДЕЛЕНИЯ 
$H_{K+1}(T)$ И (2);
РАВЕНСТВО В ТРЕТЬЕЙ СТРОКЕ ОЧЕВИДНО; ИМПЛИКАЦИЯ В ЧЕТВЕРТОЙ
СТРОКЕ ВЫВОДИТСЯ ПРИ ПОМОЩИ ПРИСОЕДИНЕНИЯ
$(BB \or\non BB)$ И ПОСЛЕДУЮЩЕГО ОСЛАБЛЕНИЯ ОБОИХ ЧЛЕНОВ;
ИМПЛИКАЦИЯ В ПЯТОЙ СТРОКЕ СЛЕДУЕТ ИЗ (6) ПРИ $k=K$ И ОПРЕДЕЛЕНИЯ
$H_0(t\le t_0)$; ОСТАЛЬНОЕ ПОНЯТНО. тАКИМ ОБРАЗОМ, МЫ ДОКАЗАЛИ
СПРАВЕДЛИВОСТЬ (6) ДЛЯ ВСЕХ $k>0$, А ОТСЮДА НЕМЕДЛЕННО
ВЫТЕКАЮТ (4) И (5).

{\bf уПРАЖНЕНИЕ}

иЗМЕНИТЕ НАШУ ВТОРУЮ ПРОГРАММУ ТАКИМ ОБРАЗОМ, ЧТОБЫ
ОНА ВЫЧИСЛЯЛА ТАКЖЕ И ЧАСТНОЕ, И ДАЙТЕ ФОРМАЛЬНОЕ ДОКАЗАТЕЛЬСТВО
ПРАВИЛЬНОСТИ ВАШЕЙ ПРОГРАММЫ. {\sl(кОНЕЦ УПРАЖНЕНИЯ.)}

пРЕДПОЛОЖИМ ТЕПЕРЬ, ЧТО ИМЕЕТСЯ МАЛЕНЬКОЕ ЧИСЛО,
СКАЖЕМ 3, НА КОТОРОЕ НАМ ПОЗВОЛЕНО УМНОЖАТЬ И ДЕЛИТЬ, И ЧТО
ЭТИ ОПЕРАЦИИ ВЫПОЛНЯЮТСЯ ДОСТАТОЧНО БЫСТРО, ТАК ЧТО ИМЕЕТ
СМЫСЛ ВОСПОЛЬЗОВАТЬСЯ ИМИ. бУДЕМ ОБОЗНАЧАТЬ ПРОИЗВЕДЕНИЕ
"$m*3$" (ИЛИ "$3*m$") И ЧАСТНОЕ "$m/3$"; ПОСЛЕДНЕЕ ВЫРАЖЕНИЕ
БУДЕТ ИСПОЛЬЗОВАТЬСЯ ТОЛЬКО ПРИ УСЛОВИИ, ЧТО ПЕРВОНАЧАЛЬНО
СПРАВЕДЛИВО $3|m$. (мЫ ВЕДЬ РАБОТАЕМ С ЦЕЛЫМИ ЧИСЛАМИ, НЕ
ТАК ЛИ?)

и ОПЯТЬ МЫ ПЫТАЕМСЯ ОБЕСПЕЧИТЬ ИСТИННОСТЬ ЖЕЛАЕМОГО
ОТНОШЕНИЯ $R$ ПРИ ПОМОЩИ КОНСТРУКЦИИ ПОВТОРЕНИЯ, ДЛЯ КОТОРОЙ
ИНВАРИАНТНОЕ ОТНОШЕНИЕ $P$ ВЫВОДИТСЯ ПУТЕМ ЗАМЕНЫ
КОНСТАНТЫ ПЕРЕМЕННОЙ. зАМЕНЯЯ КОНСТАНТУ $d$ ПЕРЕМЕННОЙ $dd$, ЧЬИ
ЗНАЧЕНИЯ БУДУТ ПРЕДСТАВЛЯТЬСЯ ТОЛЬКО В ВИДЕ $d * (\hbox{ СТЕПЕНЬ }3)$,
МЫ ПРИХОДИМ К ИНВАРИАНТНОМУ ОТНОШЕНИЮ $P$:
$$
0\le r < dd \and dd \ (А-r) \and (\exists i:i\ge 0:dd=d*3^i)
$$

мЫ ОБЕСПЕЧИМ ИСТИННОСТЬ ЭТОГО ОТНОШЕНИЯ И ЗАТЕМ,
ЗАМЕНЯЯ ЕГО ИНВАРИАНТНЫМ, ПОСТАРАЕМСЯ ДОСТИЧЬ СОСТОЯНИЯ,
ПРИ КОТОРОМ $d=dd$.

чТОБЫ ОБЕСПЕЧИТЬ ИСТИННОСТЬ $P$, НАМ ПОНАДОБИТСЯ ЕЩЕ ОДНА
КОНСТРУКЦИЯ ПОВТОРЕНИЯ: СНАЧАЛА МЫ ОБЕСПЕЧИМ ИСТИННОСТЬ
ОТНОШЕНИЯ
$$
0\le r \and dd \ (a-r) \and (\exists i:i\ge 0:dd=d*3^i)
$$
А ЗАТЕМ БУДЕМ УВЕЛИЧИВАТЬ $dd$, ПОКА ЕГО ЗНАЧЕНИЕ НЕ СТАНЕТ 
ДОСТАТОЧНО БОЛЬШИМ И ТАКИМ, ЧТО $r<dd$. пОЛУЧИМ СЛЕДУЮЩУЮ
ПРОГРАММУ:
\prg
\.{if} a\GE 0 \and d>0 \TO
        r, dd := a, d;
\.{do} r\GE dd \TO dd:=dd*3 \.{od};
\.{do} dd \NE d\TO dd:=dd/3;
 \.{do} r\GE dd\TO r:=r-dd \.{od}
\.{od}
\.{fi}
\grp

{\bf уПРАЖНЕНИЕ}

иЗМЕНИТЕ ПРИВЕДЕННУЮ ВЫШЕ ПРОГРАММУ ТАКИМ ОБРАЗОМ,
ЧТОБЫ ОНА ВЫЧИСЛЯЛА ТАКЖЕ И ЧАСТНОЕ, И ДАЙТЕ ФОРМАЛЬНОЕ
ДОКАЗАТЕЛЬСТВО ПРАВИЛЬНОСТИ ВАШЕЙ ПРОГРАММЫ, эТО 
ДОКАЗАТЕЛЬСТВО ДОЛЖНО НАГЛЯДНО ПОКАЗЫВАТЬ, ЧТО ВСЯКИЙ РАЗ, КОГДА
ВЫЧИСЛЯЕТСЯ $dd/3$, ИМЕЕТ МЕСТО $3|dd$. {\sl (кОНЕЦ УПРАЖНЕНИЯ.)}

дЛЯ ПРИВЕДЕННОЙ ВЫШЕ ПРОГРАММЫ ХАРАКТЕРНА ДОВОЛЬНО
РАСПРОСТРАНЕННАЯ ОСОБЕННОСТЬ. нА ВНЕШНЕМ УРОВНЕ ДВЕ КОНСТРУКЦИИ
ПОВТОРЕНИЯ РАСПОЛОЖЕНЬ ПОДРЯД; КОГДА ДВЕ ИЛИ
БОЛЬШЕ КОНСТРУКЦИЙ ПОВТОРЕНИЯ НА ОДНОМ И ТОМ ЖЕ УРОВНЕ
СЛЕДУЮТ ДРУГ ЗА ДРУГОМ, ОХРАНЯЕМЫЕ КОМАНДЫ БОЛЕЕ ПОЗДНИХ
КОНСТРУКЦИЙ ОКАЗЫВАЮТСЯ, КАК ПРАВИЛО, БОЛЕЕ СЛОЖНЫМИ, ЧЕМ
КОМАНДЫ ПРЕДЫДУЩИХ КОНСТРУКЦИЙ. (эТО ЯВЛЕНИЕ ИЗВЕСТНО КАК
"ЗАКОН дЕЙКСТРЫ", КОТОРЫЙ, ОДНАКО, НЕ ВСЕГДА ВЫПОЛНЯЕТСЯ.)
пРИЧИНА ТАКОЙ ТЕНДЕНЦИИ ЯСНА: КАЖДАЯ КОНСТРУКЦИЯ ПОВТОРЕНИЯ
ДОБАВЛЯЕТ СВОЕ "$\and \non BB$" К ОТНОШЕНИЮ, КОТОРОЕ ОНА
СОХРАНЯЕТ ИНВАРИАНТНЫМ, И ЭТО ДОПОЛНИТЕЛЬНОЕ ОТНОШЕНИЕ
СЛЕДУЮЩАЯ КОНСТРУКЦИЯ ТАКЖЕ ДОЛЖНА СОХРАНЯТЬ ИНВАРИАНТНЫМ.
еСЛИ БЫ НЕ ВНУТРЕННИЙ ЦИКЛ, ВТОРОЙ ЦИКЛ БЫЛ БЫ В ТОЧНОСТИ
ПРОТИВОПОЛОЖЕН ПЕРВОМУ; И ФУНКЦИЯ ДОПОЛНИТЕЛЬНОГО
ОПЕРАТОРА
\prg
\.{do} r\GE dd\TO r:= r-dd \.{od}
\grp
ИМЕННО В ТОМ И СОСТОИТ, ЧТОБЫ ВОССТАНАВЛИВАТЬ ВОЗМОЖНО НАРУШЕННОЕ
ОТНОШЕНИЕ $r<dd$, ДОСТИГАЕМОЕ ПРИ ВЫПОЛНЕНИИ ПЕРВОГО ЦИКЛА.

{\sl чЕТВЕРТЫЙ ПРИМЕР}

дЛЯ ФИКСИРОВАННЫХ $Q1$, $Q2$, $Q3$ И $Q4$ ТРЕБУЕТСЯ ОБЕСПЕЧИТЬ
ИСТИННОСТЬ $R$, ПРИЧЕМ $R$ ЗАДАЕТСЯ КАК $R1 \and R2$, ГДЕ

R1: ПОСЛЕДОВАТЕЛЬНОСТЬ ЗНАЧЕНИЙ (q1, q2, q3, q4) ЕСТЬ НЕКОТОРАЯ
      ПЕРЕСТАНОВКА ЗНАЧЕНИЙ (Ql, Q2, Q3, Q4)

R2: q1\LE q2 \LE q3 \LE q4

еСЛИ МЫ ВОЗЬМЕМ $R1$ В КАЧЕСТВЕ СОХРАНЯЕМОГО ИНВАРИАНТНЫМ
ОТНОШЕНИЯ $P$, ПОЛУЧИМ ТАКОЕ ВОЗМОЖНОЕ РЕШЕНИЕ:
\prg
q1, q2, q3, q4:=Q1, Q2, Q3, Q4;
\.{do} q1>q2 \TO q1, q2 := q2, q1
\wbox q2>q3 \TO q2, q3 := q3, q2
\wbox q3>q4 \TO q3, q4:=q4, q3
\.{od}
\grp
оЧЕВИДНО, ЧТО ПОСЛЕ ПЕРВОГО ПРИСВАИВАНИЯ $P$ СТАНОВИТСЯ
ИСТИННЫМ И НИ ОДНА ИЗ ОХРАНЯЕМЫХ КОМАНД НЕ НАРУШАЕТ ЕГО
ИСТИННОСТИ. пО ЗАВЕРШЕНИИ ПРОГРАММЫ МЫ ИМЕЕМ $\non BB$, А
ЭТО ЕСТЬ ОТНОШЕНИЕ $R2$. в ТОМ, ЧТО ПРОГРАММА ДЕЙСТВИТЕЛЬНО
ПРИДЕТ К ЗАВЕРШЕНИЮ, КАЖДЫЙ ИЗ НАС УБЕЖДАЕТСЯ ПО-РАЗНОМУ
В ЗАВИСИМОСТИ ОТ СВОЕЙ ПРОФЕССИИ: МАТЕМАТИК МОГ БЫ ЗАМЕТИТЬ,
ЧТО ЧИСЛО ПЕРЕСТАНОВОК УБЫВАЕТ, ИССЛЕДОВАТЕЛЬ ОПЕРАЦИЙ
БУДЕТ ИНТЕРПРЕТИРОВАТЬ ЭТО КАК МАКСИМИЗАЦИЮ $q1+2*q2+3*q3+4*q4$,
А Я --- КАК ФИЗИК --- СРАЗУ "ВИЖУ", ЧТО ЦЕНТР
ТЯЖЕСТИ СМЕЩАЕТСЯ В ОДНОМ НАПРАВЛЕНИИ (ВПРАВО, ЕСЛИ БЫТЬ
ТОЧНЫМ). пРОГРАММА ПРИМЕЧАТЕЛЬНА В ТОМ СМЫСЛЕ, ЧТО, КАКИЕ
БЫ ПРЕДОХРАНИТЕЛИ МЫ НИ ВЫБРАЛИ, НИКОГДА НЕ ВОЗНИКНЕТ
ОПАСНОСТИ НАРУШЕНИЯ ИСТИННОСТИ р: ПРЕДОХРАНИТЕЛИ,
ИСПОЛЬЗУЕМЫЕ В НАШЕМ ПРИМЕРЕ, ЯВЛЯЮТСЯ ЧИСТЫМ СЛЕДСТВИЕМ
НЕОБХОДИМОСТИ ЗАВЕРШЕНИЯ ПРОГРАММЫ.

{\sl зАМЕЧАНИЕ.} зАМЕТЬТЕ, ЧТО МЫ МОГЛИ БЫ ДОБАВИТЬ ТАКЖЕ И
ДРУГИЕ ВАРИАНТЫ, ТАКИЕ, КАК
\prg
q1>q3 \to q1, q3 := q3, q1
\grp
ПРИЧЕМ ИХ НЕЛЬЗЯ ИСПОЛЬЗОВАТЬ ДЛЯ ЗАМЕНЫ ОДНОГО ИЗ ТРЕХ,
ПЕРЕЧИСЛЕННЫХ В ПРОГРАММЕ. {\sl (кОНЕЦ ЗАМЕЧАНИЯ.)}

эТО ХОРОШИЙ ПРИМЕР ТОГО, КАКОГО РОДА ЯСНОСТИ МОЖНО
ДОСТИЧЬ ПРИ НАШЕЙ НЕДЕТЕРМИНИРОВАННОСТИ; ИЗЛИШНЕ ГОВОРИТЬ
ОДНАКО, ЧТО Я НЕ РЕКОМЕНДУЮ СОРТИРОВАТЬ БОЛЬШОЕ 
КОЛИЧЕСТВО ЗНАЧЕНИЙ АНАЛОГИЧНЫМ СПОСОБОМ.

{\sl пЯТЫЙ ПРИМЕР}

нАМ ТРЕБУЕТСЯ СОСТАВИТЬ ПРОГРАММУ АППРОКСИМАЦИИ
КВАДРАТНОГО КОРНЯ; БОЛЕЕ ТОЧНО: ДЛЯ ФИКСИРОВАННОГО $n$ $(n>0)$
ПРОГРАММА ДОЛЖНА ОБЕСПЕЧИТЬ ИСТИННОСТЬ
$$
R:              a^2\le n \and (a+1)^2>n
$$

чТОБЫ ОСЛАБИТЬ ЭТО ОТНОШЕНИЕ, МОЖНО, НАПРИМЕР,
ОТБРОСИТЬ ОДИН ИЗ ЛОГИЧЕСКИХ СОМНОЖИТЕЛЕЙ, СКАЖЕМ ПОСЛЕДНИЙ,
И СОСРЕДОТОЧИТЬСЯ НА
$$
P:                 a^2\le n
$$

оЧЕВИДНО, ЧТО ЭТО ОТНОШЕНИЕ ВЕРНО ПРИ $a=0$, ПОЭТОМУ
ВЫБОР НАЧАЛЬНОГО ЗНАЧЕНИЯ НЕ ДОЛЖЕН НАС БЕСПОКОИТЬ.
мЫ ВИДИМ, ЧТО ЕСЛИ ВТОРОЙ ЧЛЕН НЕ ЯВЛЯЕТСЯ ИСТИННЫМ, ТО ЭТО
ВЫЗЫВАЕТСЯ СЛИШКОМ МАЛЕНЬКИМ ЗНАЧЕНИЕМ $a$, ПОЭТОМУ МЫ МОГЛИ
БЫ ОБРАТИТЬСЯ К ОПЕРАТОРУ "$a:=a+1$". фОРМАЛЬНО МЫ
ПОЛУЧАЕМ
$$
\wp ("a := a + 1 ", P)=((a + 1)^2\le n)
$$

иСПОЛЬЗУЯ ЭТО УСЛОВИЕ В КАЧЕСТВЕ (ЕДИНСТВЕННОГО!)
ПРЕДОХРАНИТЕЛЯ, МЫ ПОЛУЧАЕМ $(P \and \non BB) =R$ И ПРИХОДИМ
К СЛЕДУЮЩЕЙ ПРОГРАММЕ:
\prg
\.{if} n\GE 0 \TO
a:=0  \{р СТАЛО ИСТИННЫМ\};
\.{do} (a+1)^2\LE n\to a:=a+1 \{P ОСТАЛОСЬ ИСТИННЫМ\} \.{od}
\{R СТАЛО ИСТИННЫМ \}
\.{fi} \{R  СТАЛО ИСТИННЫМ \}
\grp

пРИ СОСТАВЛЕНИИ ПРОГРАММЫ МЫ ИСХОДИЛИ ИЗ ПРЕДПОЛОЖЕНИЯ,
ЧТО ОНa ЗАВЕРШИТСЯ, И ЭТО ДЕЙСТВИТЕЛЬНО ТАК, ПОСКОЛЬКУ
КОРЕНЬ ИЗ НЕОТРИЦАТЕЛЬНОГО ЧИСЛА ЕСТЬ МОНОТОННО ВОЗРАСТАЮЩАЯ
ФУНКЦИЯ: В КАЧЕСТВЕ $t$ МЫ МОЖЕМ ВЗЯТЬ ФУНКЦИЮ $n-a^2$.

эТА ПРОГРАММА ДОВОЛЬНО ОЧЕВИДНА, К ТОМУ ЖЕ ОНА И НЕ
ОЧЕНЬ ЭФФЕКТИВНА: ПРИ БОЛЬШИХ ЗНАЧЕНИЯХ $n$ ОНА БУДЕТ РАБОТАТЬ
ДОВОЛЬНО ДОЛГО. дРУГОЙ СПОСОБ ОБОБЩЕНИЯ R --- ЭТО ВВЕДЕНИЕ
ДРУГОЙ ПЕРЕМЕННОЙ (СКАЖЕМ, $b$ --- И СНОВА В ОГРАНИЧЕННОМ
ИНТЕРВАЛЕ ИЗМЕНЕНИЯ), КОТОРАЯ ЗАМЕНИТ ЧАСТЬ $R$, НАПРИМЕР,
$$
P:\quad a^2 \le n \and b^2>n \and 0\le a<b
$$
бЛАГОДАРЯ ТАКОМУ ВЫБОРУ $P$ ОБЛАДАЕТ ТЕМ ПРИЯТНЫМ СВОЙСТВОМ, ЧТО
$$
(P \and (a+1=b))\Rightarrow R
$$

тАКИМ ОБРАЗОМ, МЫ ПРИХОДИМ К ПРОГРАММЕ, ПРЕДСТАВЛЕННОЙ
В ТАКОЙ ФОРМЕ (ЗДЕСЬ И ДАЛЕЕ КОНСТРУКЦИЯ \.{if} n\GE 0 \TO \dots \.{fi}
ОПУСКАЕТСЯ):
\prg
a,b:=0, n+1 \{р СТАЛО ИСТИННЫМ\};
\.{do} a+1\NE b \TO УМЕНЬШИТЬ b-a ПРИ ИНВАРИАНТНОСТИ P \.{od}
\{R СТАЛО ИСТИННЫМ\}
\grp

пУСТЬ $d$ БУДЕТ ВЕЛИЧИНОЙ, НА КОТОРУЮ УМЕНЬШАЕТСЯ РАЗНОСТЬ $b-a$
ПРИ КАЖДОМ ВЫПОЛНЕНИИ ОХРАНЯЕМОЙ КОМАНДЫ.
рАЗНОСТЬ МОЖЕТ УМЕНЬШАТЬСЯ ЛИБО ЗА СЧЕТ УМЕНЬШЕНИЯ $b$,
ЛИБО ЗА СЧЕТ УВЕЛИЧЕНИЯ $a$, ЛИБО ЗА СЧЕТ И ТОГО И ДРУГОГО. нЕ
ТЕРЯЯ ОБЩНОСТИ, МЫ МОЖЕМ ОГРАНИЧИТЬСЯ РАССМОТРЕНИЕМ ТАКИХ
ШАГОВ, КОГДА ИЗМЕНЯЕТСЯ ЛИБО $a$, ЛИБО $b$, НО НЕ $a$ И $b$ ОДНОВРЕМЕННО:
ЕСЛИ $a$ СЛИШКОМ МАЛО И $b$ СЛИШКОМ ВЕЛИКО И НА ОДНОМ ШАГЕ
ТОЛЬКО УМЕНЬШАЕТСЯ $b$, ТОГДА НА СЛЕДУЮЩЕМ ШАГЕ МОЖНО
УВЕЛИЧИТЬ $a$. эТИ СООБРАЖЕНИЯ ПРИВОДЯТ НАС К ПРОГРАММЕ В
СЛЕДУЮЩЕЙ ФОРМЕ:
\prg
a, b:=0, n+1 \{P СТАЛО ИСТИННЫМ\};
\.{do} a+1 \NE b \TO
d:=\dots \{d  ИМЕЕТ СООТВЕТСТВУЮЩЕЕ ЗНАЧЕНИЕ И P ПО-ПРЕЖНЕМУ ВЫПОЛНЯЕТСЯ\};
\.{if} \dots\TO a:=a+d  \{P ОСТАЛОСЬ ИСТИННЫМ\}
\wbox\dots \TO b:=b-d \{P ОСТАЛОСЬ ИСТИННЫМ\}
\.{fi} \{P СТАЛО ИСТИННЫМ\}
\.{od} \{R СТАЛО ИСТИННЫМ\}
\grp

тЕПЕРЬ
$$
\wp("a:=a+d", P)=((a+d)^2\le n \and b^2>n)
$$
пОСКОЛЬКУ ИСТИННОСТЬ ВТОРОГО ЧЛЕНА СЛЕДУЕТ ИЗ ИСТИННОСТИ $P$,
МЫ МОЖЕМ ИСПОЛЬЗОВАТЬ ПЕРВЫЙ ЧЛЕН В КАЧЕСТВЕ НАШЕГО
ПЕРВОГО ПРЕДОХРАНИТЕЛЯ; АНАЛОГИЧНО ВЫВОДИТСЯ ВТОРОЙ
ПРЕДОХРАНИТЕЛЬ, И МЫ ПОЛУЧАЕМ ОЧЕРЕДНУЮ ФОРМУ НАШЕЙ 
ПРОГРАММЫ:
\prg
a, b:= 0, n+1;
\.{do} a+1 \NE b \TO d:=\dots;
      \.{if}(a+d)^2 \LE n\TO a:=a+d
      \wbox (b-d)^2>n\TO b:= b-d
      \.{fi} \{р ОСТАЛОСЬ ИСТИННЫМ\}
\.{od} \{R СТАЛО ИСТИННЫМ\}
\grp

нАМ ОСТАЕТСЯ ЕЩЕ СООТВЕТСТВУЮЩИМ ОБРАЗОМ ВЫБРАТЬ $d$.
пОСКОЛЬКУ МЫ ВЗЯЛИ $b-a$ (НА САМОМ ДЕЛЕ, $b-А-1$) В КАЧЕСТВЕ
НАШЕЙ ФУНКЦИИ $t$, ЭФФЕКТИВНОЕ УБЫВАНИЕ ДОЛЖНО БЫТЬ ТАКИМ,
ЧТОБЫ d УДОВЛЕТВОРЯЛО УСЛОВИЮ $d>0$. кРОМЕ ТОГО, 
ПОСЛЕДУЮЩАЯ КОНСТРУКЦИЯ ВЫБОРА НЕ ДОЛЖНА ПРИВОДИТЬ К ОТКАЗУ, Т. Е.
ПО КРАЙНЕЙ МЕРЕ ОДИН ИЗ ПРЕДОХРАНИТЕЛЕЙ ДОЛЖЕН БЫТЬ
ИСТИННЫМ. эТО ЗНАЧИТ, ЧТО ИЗ ОТРИЦАНИЯ ОДНОГО, $(a+d)^2>n$, ДОЛЖЕН
СЛЕДОВАТЬ ДРУГОЙ, $(b-d)^2>n$; ЭТО ГАРАНТИРУЕТСЯ, ЕСЛИ
$$
a+d\le b-d
$$
ИЛИ
$$
2*d\le b-a
$$

нАРЯДУ С НИЖНЕЙ ГРАНИЦЕЙ МЫ УСТАНОВИЛИ ТАКЖЕ И ВЕРХНЮЮ
ГРАНИЦУ ДЛЯ $d$. мЫ МОГЛИ БЫ ВЗЯТЬ $d=1$, НО ЧЕМ БОЛЬШЕ $d$, ТЕМ
БЫСТРЕЕ РАБОТАЕТ ПРОГРАММА, ПОЭТОМУ МЫ ПРЕДЛАГАЕМ
\prg
a,b:=0,n+1;
\.{do} a+1 \NE b \TO d:=(b-a) \div 2;
             \.{if} (a+d)^2\LE n\TO a:=a+d
                \wbox (b-d)^2>n\TO b:=b-d
             \.{fi}          
\.{od}
\grp
ГДЕ $n\div 2$ ЕСТЬ $n/2$, ЕСЛИ $2|n$ И $(n-1)/2$, ЕСЛИ $2|(n-1)$.

иСПОЛЬЗОВАНИЕ ДЕЙСТВИЯ $\div$ ПОБУЖДАЕТ  НАС РАЗОБРАТСЯ
В ТОМ, ЧТО ПРОИЗОЙДЕТ, ЕСЛИ МЫ НАВЯЖЕМ СЕБЕ ОГРАНИЧЕНИЕ НА $b-a$,
ПОЛАГАЯ, ЧТО $b-a$ ЧЕТНО ПРИ КАЖДОМ ВЫЧИСЛЕНИИ $d$. вВОДЯ 
$c=(b-a)$ И ИСКЛЮЧАЯ $b$, МЫ ПОЛУЧАЕМ ИНВАРИАНТНОЕ ОТНОШЕНИЕ
$$
P:\qquad a^2\le n \and (a+c)^2 > n \and (\exists i: i\ge 0 : c=2^i)
$$
И ПРОГРАММУ (В КОТОРОЙ $c$ ИГРАЕТ РОЛЬ $d$)
\prg
a,c:=0, 1; \.{do} c^2\LE n\TO c:=2*c \.{od};
\.{do} c \NE 1 \TO c := c/2;
           \.{if} (a + c)^2 \LE n \TO a:=a+c
               \wbox (a-c)^2 > n \TO \var{ПРОПУСТИТЬ}
           \.{fi}
\.{od}
\grp

{\sl зАМЕЧАНИЕ.} эТА ПРОГРАММА ОЧЕНЬ ПОХОЖА НА ПОСЛЕДНЮЮ
ПРОГРАММУ ДЛЯ ТРЕТЬЕГО ПРИМЕРА, ГДЕ ВЫЧИСЛЯЛСЯ ОСТАТОК В
ПРЕДПОЛОЖЕНИИ, ЧТО МЫ ИМЕЕМ ПРАВО УМНОЖАТЬ И ДЕЛИТЬ НА 3.
в ПРИВЕДЕННОЙ ВЫШЕ ПРОГРАММЕ МОЖНО БЫЛО БЫ ЗАМЕНИТЬ КОНСТРУКЦИЮ
ВЫБОРА НА
\prg
\.{dО} (a+c)^2 \LE n \TO a:=a+c \.{od}
\grp
еСЛИ УСЛОВИЕ, КОТОРОМУ ДОЛЖЕН УДОВЛЕТВОРЯТЬ ОСТАТОК,
$0\le r < d$, ЗАПИСАТЬ КАК $r<d \and (r+d)\ge d$, СХОДСТВО СТАНЕТ
ЕЩЕ БОЛЕЕ ОТЧЕТЛИВЫМ. {\sl (кОНЕЦ ЗАМЕЧАНИЯ.)}

пОНИМАЯ, ЧТО ТАК МОЖНО ОКОНЧАТЕЛЬНО "ЗАМУЧИТЬ" ЭТОТ МАЛЕНЬКИЙ
ПРИИМЕР, Я БЫ ХОТЕЛ ТЕМ НЕ МЕНЕЕ ПРЕДЛОЖИТЬ ПОСЛЕДНИЙ
ВАРИАНТ ПРЕОБРАЗОВАНИЯ ПРОГРАММЫ. мЫ НАПИСАЛИ ПРОГРАММУ,
ИСХОДЯ ИЗ ПРЕДПОЛОЖЕНИЯ, ЧТО ОПЕРАЦИЯ ВОЗВЕДЕНИЯ ЧИСЛА В
КВАДРАТ ВХОДИТ В СОСТАВ ИМЕЮЩИХСЯ ОПЕРАЦИЙ; НО ПРЕДПОЛОЖИМ,
ЧТО ЭТО НЕ ТАК И ЧТО ЕДИНСТВЕННЫЕ ОПЕРАЦИИ ТИПА
УМНОЖЕНИЯ, ИМЕЮЩИЕСЯ В НАШЕМ РАСПОРЯЖЕНИИ,--- ЭТО УМНОЖЕНИЕ
И ДЕЛЕНИЕ НА (МАЛЫЕ) СТЕПЕНИ 2. тОГДА НАША ПОСЛЕДНЯЯ
ПРОГРАММА ОКАЗЫВАЕТСЯ НЕ ТАКОЙ УЖ ХОРОШЕЙ, Т. Е. ОНА
НЕХОРОША, ЕСЛИ МЫ ПРЕДПОЛАГАЕМ, ЧТО ЗНАЧЕНИЯ ПЕРЕМЕННЫХ,
С КОТОРЫМИ НЕПОСРЕДСТВЕННО ОПЕРИРУЕТ МАШИНА, ОТОЖДЕСТВЛЕНЫ
СО ЗНАЧЕНИЯМИ ПЕРЕМЕННЫХ $a$ И $c$, КАК ЭТО БЫЛО БЫ ПРИ 
"АБСТРАКТНЫХ" ВЫЧИСЛЕНИЯХ. дРУГИМИ СЛОВАМИ, МЫ МОЖЕМ
РАССМАТРИВАТЬ $a$ И $c$ КАК АБСТРАКТНЫЕ ПЕРЕМЕННЫЕ, ЧЬИ
ЗНАЧЕНИЯ ПРЕДСТАВЛЯЮТСЯ (В СООТВЕТСТВИИ С СОГЛАШЕНИЕМ, 
ПРЕДУСМАТРИВАЮЩИМ БОЛЕЕ СЛОЖНЫЕ УСЛОВИЯ, ЧЕМ ПРОСТО 
ТОЖДЕСТВЕННОСТЬ)
ЗНАЧЕНИЯМИ ДРУГИХ ПЕРЕМЕННЫХ, С КОТОРЫМИ
В ДЕЙСТВИТЕЛЬНОСТМ ОПЕРИРУЕТ МАШИНА ПРИ ВЫПОЛНЕНИИ
ПРОГРАММЫ. мЫ МОЖЕМ ПОЗВОЛИТЬ МАШИНЕ РАБОТАТЬ НЕ
НЕПОСРЕДСТВЕННО С $a$ И $c$, А С $Р$, $q$, $r$, ТАКИМИ, ЧТО
$$
\eqalign{
p &= a * c \cr
q &=c^2\cr
r &=n-a^2\cr
}
$$

мЫ ВИДИМ, ЧТО ЭТО --- ПРЕОБРАЗОВАНИЕ КООРДИНАТ, И КАЖДОЙ
ТРАЕКТОРИИ В НАШЕМ $(a, c)$-ПРОСТРАНСТВЕ СООТВЕТСТВУЕТ
ТРАЕКТОРИЯ В НАШЕМ $(p, q, r)$-ПРОСТРАНСТВЕ. оБРАТНОЕ НЕ ВСЕГДА
ВЕРНО, ТАК КАК ЗНАЧЕНИЯ $p$, $q$ И $r$  НЕ НЕЗАВИСИМЫ: В ТЕРМИНАХ
$p$, $q$  И $r$ МЫ ПОЛУЧАЕМ ИЗБЫТОЧНОСТЬ И, СЛЕДОВАТЕЛЬНО,
ПОТЕНЦИАЛЬНУЮ ВОЗМОЖНОСТЬ, ПОЖЕРТВОВАВ НЕКОТОРЫМ ОБоЕМОМ
ПАМЯТИ, НЕ  ТОЛЬКО ВЫИГРАТЬ ВРЕМЯ ВЫЧИСЛЕНИЙ, НО
ДАЖЕ ИЗБАВИТЬСЯ ОТ НЕОБХОДИМОСТИ ВОЗВОДИТЬ В КВАДРАТ!
(сОВЕРШЕННО ЯСНО, ЧТО ПРЕСЛЕДОВАЛАСЬ ИМЕННО ЭТА ЦЕЛЬ,
КОГДА СТРОИЛОСЬ ПРЕОБРАЗОВАНИЕ, ПЕРЕВОДЯЩЕЕ ТОЧКУ В
$(a,c)$-ПРОСТРАНСТВЕ В ТОЧКУ В $(Р, q, r)$-ПРОСТРАНСТВЕ.) тЕПЕРЬ МЫ
МОЖЕМ ПОПЫТАТЬСЯ ПЕРЕВЕСТИ ВСЕ БУЛЕВЫ ВЫРАЖЕНИЯ И 
ПЕРЕМЕЩЕНИЯ В $(a, c)$-ПРОСТРАНСТВЕ В СООТВЕТСТВУЮЩИЕ БУЛЕВЫ
ВЫРАЖЕНИЯ И ПЕРЕМЕЩЕНИЯ В $(p, q, r)$ -ПРОСТРАНСТВЕ. еСЛИ БЫ НАМ
УДАЛОСЬ СДЕЛАТЬ ЭТО В ТЕРМИНАХ ДОПУСТИМЫХ ОПЕРАЦИЙ, НАША
ЗАДАЧА БЫЛА БЫ УСПЕШНО РЕШЕНА. пРЕДЛАГАЕМОЕ ПРЕОБРАЗОВАНИЕ
И В САМОМ ДЕЛЕ ОТВЕЧАЕТ НАШИМ ТРЕБОВАНИЯМ, И РЕЗУЛЬТАТОМ
ЕГО ЯВЛЯЕТСЯ СЛЕДУЮЩАЯ ПРОГРАММА (ПЕРЕМЕННАЯ $h$ БЫЛА
ВВЕДЕНА ДЛЯ ОЧЕНЬ ЛОКАЛЬНОЙ ОПТИМИЗАЦИИ):
\prg
p,q,r:=0,1,n; \.{do} q\LE n \TO q:=q*4 \.{od};
\.{do} q \NE 1\TO q:=q/4; h:=p+q; p:=p/2 \{h=2*p+q\}
     \.{if} r \GE h \TO p,r:=p+q,r-h
       \wbox r<h \TO \var{ПРОПУСТИТЬ}
     \.{fi}
\.{od} \{ p ИМЕЕТ ЗНАЧЕНИЕ, ТРЕБУЕМОЕ ДЛЯ a \}
\grp

эТОТ ПЯТЫЙ ПРИМЕР БЫЛ ВКЛЮЧЕН БЛАГОДАРЯ ИСТОРИИ ЕГО
СОЗДАНИЯ (ПРАВДА, НЕСКОЛЬКО ПРИУКРАШЕННОЙ). кОГДА
МЛАДШЕЙ ИЗ ДВУХ НАШИХ СОБАК БЫЛО ВСЕГО НЕСКОЛЬКО МЕСЯЦЕВ,
Я ОДНАЖДЫ ВЕЧЕРОМ ПОШЕЛ ПОГУЛЯТЬ С НИМИ ОБЕИМИ. нАЗАВТРА
МНЕ ПРЕДСТОЯЛО ЧИТАТЬ ЛЕКЦИИ СТУДЕНТАМ, КОТОРЫЕ ВСЕГО ЛИШЬ
НЕСКОЛЬКО НЕДЕЛЬ НАЗАД НАЧАЛИ ЗНАКОМИТЬСЯ С ПРОГРАММИРОВАНИЕМ,
И МНЕ НУЖНА БЫЛА ПРОСТАЯ ЗАДАЧА, ЧТОБЫ НА ЕЕ 
ПРИМЕРЕ Я МОГ "МАССИРОВАТЬ" РЕШЕНИЯ. в ТЕЧЕНИЕ ЧАСОВОЙ ПРОГУЛКИ
Я ПРОДУМАЛ ПЕРВУЮ, ТРЕТЬЮ И ЧЕТВЕРТУЮ ПРОГРАММЫ, ПРАВДА,
ПРАВИЛЬНО ВВЕСТИ $h$ В ПОСЛЕДНЕЙ ПРОГРАММЕ Я СМОГ ТОЛЬКО
ПРИ ПОМОЩИ КАРАНДАША И БУМАГИ, КОГДА ВЕРНУЛСЯ ДОМОЙ. кО
ВТОРОЙ ПРОГРАММЕ, ТОЙ, КОТОРАЯ ОПЕРИРУЕТ С $a$ И $b$ И КОТОРАЯ
БЫЛА ЗДЕСЬ ПРЕДСТАВЛЕНА КАК ПЕРЕХОДНАЯ СТУПЕНЬ К НАШЕМУ
ТРЕТЬЕМУ РЕШЕНИЮ, Я ПРИШЕЛ ЛИШЬ НЕСКОЛЬКО НЕДЕЛЬ СПУСТЯ ---
И ОНА БЫЛА ТОГДА В ГОРАЗДО МЕНЕЕ ЭЛЕГАНТНОЙ ФОРМЕ, ЧЕМ ПРЕДСТАВЛЕНА
ЗДЕСЬ. вТОРАЯ ПРИЧИНА ДЛЯ ЕЕ ВКЛЮЧЕНИЯ В ЧИСЛО
ПРЕДСТАВЛЕННЫХ ПРОГРАММ --- ЭТО СООТНОШЕНИЕ МЕЖДУ ТРЕТЬЕЙ
ПРОГРАММАМИ: ПО ОТНОШЕНИЮ К ЧЕТВЕРТОЙ ПРОГРАММЕ ТРЕТЬЯ
ПРЕДСТАВЛЯЕТ СОБОЙ НАШ ПЕРВЫЙ ПРИМЕР ТАК НАЗЫВАЕМОЙ
"АБСТРАКЦИИ ПРЕДСТАВЛЕНИЯ".

{\sl шЕСТОЙ ПРИМЕР}

дЛЯ ФИКСИРОВАННЫХ $X\ (X>1)$ И $Y\ (Y\ge 0)$ ПРОГРАММА ДОЛЖНА
ОБЕСПЕЧИТЬ ИСТИННОСТЬ ОТНОШЕНИЯ
$$
R: \quad z=X^Y
$$
ПРИ ОЧЕВИДНОМ ПРЕДПОЛОЖЕНИИ, ЧТО ОПЕРАЦИЯ ВОЗВЕДЕНИЯ В СТЕПЕНЬ
НЕ ВХОДИТ В НАБОР ДОСТУПНЫХ ОПЕРАЦИЙ. эТА ЗАДАЧА МОЖЕТ БЫТЬ
РЕШЕНА ПРИ ПОМОЩИ "АБСТРАКТНОЙ ПЕРЕМЕННОЙ", СКАЖЕМ $h$;
ПРИ РЕШЕНИИ ЗАДАЧИ МЫ БУДЕМ ПОЛЬЗОВАТЬСЯ ЦИКЛОМ, ДЛЯ КОТОРОГО
ИНВАРИАНТНЫМ ЯВЛЯЕТСЯ ОТНОШЕНИЕ
$$
P:\qquad h * z=X^Y
$$
И НАША (В РАВНОЙ СТЕПЕНИ "АБСТРАКТНАЯ") ПРОГРАММА МОГЛА 
БЫ ВЫГЛЯДЕТЬ ТАК:
\prg
h,z:=х^Y,1 \{P СТАЛО ИСТИННЫМ\};
\.{do} h \NE 1\TO СЖИМАТЬ $h$ ПРИ ИНВАРИАНТНОСТИ $P$ \.{od}
\{ R СТАЛО ИСТИННЫМ \}
\grp

пОСЛЕДНЕЕ ЗАКЛЮЧЕНИЕ СПРАВЕДЛИВО, ПОСКОЛЬКУ $(P \and h=1)\Rightarrow R$.
пРИВЕДЕННАЯ ВЫШЕ ПРОГРАММА ПРИДЕТ К ЗАВЕРШЕНИЮ, ЕСЛИ
ПОСЛЕ КОНЕЧНОГО ЧИСЛА ПРИМЕНЕНИЙ ОПЕРАЦИИ "СЖИМАНИЯ" $h$
СТАНЕТ РАВНЫМ 1. пРОБЛЕМА, КОНЕЧНО, В ТОМ, ЧТО МЫ НЕ МОЖЕМ
ПРЕДСТАВИТЬ ЗНАЧЕНИЕ $h$ ЗНАЧЕНИЕМ КОНКРЕТНОЙ ПЕРЕМЕННОЙ, 
С КОТОРЫМ НЕПОСРЕДСТВЕННО ОПЕРИРУЕТ МАШИНА; ЕСЛИ БЫ МЫ
МОГЛИ ТАК СДЕЛАТЬ, МЫ МОГЛИ БЫ СРАЗУ ПРИСВОИТЬ $z$ ЗНАЧЕНИЕ
$X^Y$, НЕ ЗАТРУДНЯЯ СЕБЯ ВВЕДЕНИЕМ $h$. фОКУС В ТОМ, ЧТО
ДЛЯ ПРЕДСТАВЛЕНИЯ ТЕКУЩЕГО ЗНАЧЕНИЯ $h$ МЫ МОЖЕМ ВВЕСТИ ДВЕ ---
НА ЭТОМ УРОВНЕ КОНКРЕТНЫЕ --- ПЕРЕМЕННЫЕ, СКАЖЕМ $x$ И $y$,
И НАШЕ ПЕРВОЕ ПРИСВАИВАНИЕ ПРЕДЛАГАЕТ В КАЧЕСТВЕ СОГЛАШЕНИЯ
ОБ ЭТОМ ПРЕДСТАВЛЕНИИ
$$
h=x^y
$$

тОГДА УСЛОВИЕ "$h\not=1$" ПЕРЕХОДИТ В УСЛОВИЕ "$y\not=0$", И НАША
СЛЕДУЮЩАЯ ЗАДАЧА СОСТОИТ В ТОМ, ЧТОБЫ ПОДЫСКАТЬ ВЫПОЛНИМУЮ
ОПЕРАЦИЮ "СЖИМАНИЯ". пОСКОЛЬКУ ПРИ ЭТОЙ ОПЕРАЦИИ
ПРОИЗВЕДЕНИЕ $h*z$ ДОЛЖНО ОСТАВАТЬСЯ ИНВАРИАНТНЫМ, МЫ ДОЛЖНЫ
ДЕЛИТЬ $h$ НА ТУ ЖЕ ВЕЛИЧИНУ, НА КОТОРУЮ УМНОЖАЕТСЯ $z$.
иСХОДЯ ИЗ ПРЕДСТАВЛЕНИЯ $h$, НАИБОЛЕЕ ЕСТЕСТВЕННЫМ КАНДИДАТОМ НА
ЭТУ ВЕЛИЧИНУ МОЖНО СЧИТАТЬ ТЕКУЩЕЕ ЗНАЧЕНИЕ $x$. бЕЗ 
ДАЛЬНЕЙШИХ ЗАТРУДНЕНИЙ МЫ ПРИХОДИМ К ТАКОМУ ВИДУ НАШЕЙ
АБСТРАКТНОЙ ПРОГРАММЫ:
\prg
x,y,z:=X,Y,1 \{P СТАЛО ИСТИННЫМ\};
\.{do} y\NE 0 \TO y,z:=y-1, z*x \{P ОСТАЛОСЬ ИСТИННЫМ\} \.{od}
\{R СТАЛО ИСТИННЫМ\}
\grp

гЛЯДЯ НА ЭТУ ПРОГРАММУ, МЫ ПОНИМАЕМ, ЧТО ЧИСЛО 
ВЫПОЛНЕНИЙ ЦИКЛА РАВНО ПЕРВОНАЧАЛЬНОМУ ЗНАЧЕНИЮ $Y$, И МОЖЕМ
ЗАДАТЬ СЕБЕ ВОПРОС, НЕЛЬЗЯ ЛИ УСКОРИТЬ ПРОГРАММУ. яСНО, ЧТО
ЗАДАЧЕЙ ОХРАНЯЕМОЙ КОМАНДЫ ЯВЛЯЕТСЯ СВЕДЕНИЕ $y$ К НУЛЮ; НЕ
ИЗМЕНЯЯ \emph{ЗНАЧЕНИЯ} $h$, МЫ МОЖЕМ ПРОВЕРИТЬ, НЕЛЬЗЯ ЛИ ИЗМЕНИТЬ
\emph{ПРЕДСТАВЛЕНИЕ} ЭТОГО ЗНАЧЕНИЯ В НАДЕЖДЕ УМЕНЬШИТЬ ЗНАЧЕНИЕ
$y$. пОПЫТАЕМСЯ ВОСПОЛЬЗОВАТЬСЯ ТЕМ ФАКТОМ, ЧТО КОНКРЕТНОЕ
ПРЕДСТАВЛЕНИЕ ЗНАЧЕНИЯ $h$, ЗАДАННОЕ КАК $x^y$, ВОВСЕ НЕ ЯВЛЯЕТСЯ
ОДНОЗНАЧНЫМ. еСЛИ $y$ ЧЕТНО, МЫ МОЖЕМ РАЗДЕЛИТЬ $y$ НА 2 И
ВОЗВЕСТИ $x$ В КВАДРАТ, ПРИ ЭТОМ ЗНАЧЕНИЕ $h$ СОВСЕМ НЕ ИЗМЕНИТСЯ.
 нЕПОСРЕДСТВЕННО ПЕРЕД ОПЕРАЦИЕЙ СЖИМАНИЯ МЫ ВСТАВЛЯЕМ
ПРЕОБРАЗОВАНИЕ, ПРИВОДЯЩЕЕ К НАИБОЛЕЕ ПРИВЛЕКАТЕЛЬНОМУ
ПРЕОБРАЗОВАНИЮ $h$ И ПОЛУЧАЕМ СЛЕДУЮЩУЮ ПРОГРАММУ:
\prg
x,y,z:=X,Y,1;
\.{do} y\NE0 \TO \.{do} 2 | y\TO x, У:= x*x, y/2 \.{od};
              y,z:=y-1,z*x
\.{od} \{R СТАЛО ИСТИННЫМ \}
\grp

сУЩЕСТВУЕТ ТОЛЬКО ОДНА ВЕЛИЧИНА, КОТОРУЮ МОЖНО
БЕСКОНЕЧНО ДЕЛИТЬ ПОПОЛАМ И ОНА НЕ СТАНЕТ НЕЧЕТНОЙ, ЭТА
ВЕЛИЧИНА --- НУЛЬ; ИНАЧЕ ГОВОРЯ, ВНЕШНИЙ ПРЕДОХРАНИТЕЛЬ ГАРАНТИРУЕТ
НАМ, ЧТО ВНУТРЕННИЙ ЦИКЛ ПРИДЕТ К ЗАВЕРШЕНИЮ.

я ВКЛЮЧИЛ ЭТОТ ПРИМЕР ПО РАЗНЫМ ПРИЧИНАМ. мЕНЯ 
ПОРАЗИЛО ОТКРЫТИЕ, ЧТО ЕСЛИ ПРОСТО ВСТАВИТЬ В ПРОГРАММУ ЧТО-ТО,
ЧТО НА АБСТРАКТНОМ УРОВНЕ ДЕЙСТВУЕТ КАК ПУСТОЙ ОПЕРАТОР,
МОЖНО ТАК ИЗМЕНИТЬ АЛГОРИТМ, ЧТО ЧИСЛО ОПЕРАЦИЙ, КОТОРОЕ
РАНЬШЕ БЫЛО ПРОПОРЦИОНАЛЬНО $Y$, СТАНЕТ ПРОПОРЦИОНАЛЬНО
ТОЛЬКО $\log (Y)$. эТО ОТКРЫТИЕ БЫЛО ПРЯМЫМ СЛЕДСТВИЕМ ТОГО,
ЧТО Я ЗАСТАВИЛ СЕБЯ ДУМАТЬ В ТЕРМИНАХ ОТДЕЛЬНОЙ АБСТРАКТНОЙ
ПЕРЕМЕННОЙ. пРОГРАММА ВОЗВЕДЕНИЯ В СТЕПЕНЬ, КОТОРУЮ Я ЗНАЛ,
БЫЛА СЛЕДУЮЩЕЙ:
\prg
x,y,z:=х,Y,1;
\.{do} y<>0 \TO \.{if} \non 2| y\TO y,z:=y-1,z*x
                       \wbox 2|y \TO\var{ПРОПУСТИТЬ} \.{fi};
                   x,y:=x*x,y/2
\.{od}
\grp
эТА ПОСЛЕДНЯЯ ПРОГРАММА ОЧЕНЬ ХОРОШО ИЗВЕСТНА, МНОГИЕ ИЗ
НАС ПРИШЛИ К НЕЙ НЕЗАВИСИМО ДРУГ ОТ ДРУГА. пОСКОЛЬКУ ПОСЛЕДНЕЕ
ВОЗВЕДЕНИЕ $x$ В КВАДРАТ, КОГДА $y$ СТАЛ РАВНЫМ НУЛЮ, УЖЕ
ИЗЛИШНЕ, НА ЭТУ ПРОГРАММУ ЧАСТО ССЫЛАЛИСЬ КАК НА ПРИМЕР,
ПОДТВЕЖДАЮЩИЙ НЕОБХОДИМОСТЬ ИМЕТЬ ТО, ЧТО МЫ НАЗВАЛИ БЫ
"ПРОМЕЖУТОЧННЫМИ ВЫХОДАМИ". пРИНИМАЯ ВО ВНИМАНИЕ НАШУ
ПРОГРАММУ, Я ПРИХОЖУ К ЗАКЛЮЧЕНИЮ, ЧТО ЭТОТ ДОВОД СЛАБ.

{\sl сЕДЬМОЙ ПРИМЕР }

дЛЯ ФИКСИРОВАННОГО ЗНАЧЕНИЯ $n$ $(n\ge 0)$ ЗАДАНА ФУНКЦИЯ
$f(i)$ ДЛЯ $0\le i<n$. пРИСВОИТЬ БУЛЕВОЙ ПЕРЕМЕННОЙ "\var{ВСЕШЕСТЬ}"
ТАКОЕ ЗНАЧЕНИЕ, ЧТОБЫ В КОНЕЧНОМ РЕЗУЛЬТАТЕ СТАЛО СПРАВЕДЛИВЫМ
$$
R:\qquad \var{ВСЕШЕСТЬ} =  (\forall i: 0 \le i < n : f (i) = 6)
$$
(эТОТ ПРИМЕР ОБНАРУЖИВАЕТ НЕКОТОРОЕ СХОДСТВО СО ВТОРЫМ
ПРИМЕРОМ ДАННОЙ ГЛАВЫ. зАМЕТИМ, ОДНАКО, ЧТО В ЭТОМ ПРИМЕРЕ
ДОПУСКАЕТСЯ РАВЕНСТВО $n$ НУЛЮ. в ТАКОМ СЛУЧАЕ ИНТЕРВАЛ
ВОЗМОЖНЫХ ЗНАЧЕНИЙ ДЛЯ КВАНТОРА "$\forall$" ПУСТ И ДОЛЖНО БЫТЬ
ВЕРНЫМ, ЧТО  $\var{ВСЕШЕСТЬ}=\var{ИСТИНА}$.) пО АНАЛОГИИ СО ВТОРЫМ ПРИМЕРОМ
ВВЕДЕМ ИНВАРИАНТНОЕ ОТНОШЕНИЕ
$$
P:\qquad \var{ВСЕШЕСТЬ}=(\forall i: 0\le i<j :f(i)= 6)) \and 0\le j\le n
$$
ПОСКОЛЬКУ ЭТО ОТНОШЕНИЕ ЛЕГКО СДЕЛАТЬ ИСТИННЫМ ПРИ $j=0$
И К ТОМУ ЖЕ $(P \and j=n) \Rightarrow R$ . еДИНСТВЕННОЕ, ЧТО МЫ ДОЛЖНЫ
СДЕЛАТЬ, ЭТО ПОНЯТЬ, КАК УВЕЛИЧИВАТЬ $j$ ПРИ ИНВАРИАНТНОСТИ $р$.
пОЭТОМУ БЕРЕМ
$$
\wp("j:=j+1", P)=
(\var{ВСЕШЕСТЬ}= (\forall i: 0\le i<j+1: f(i)=6)) \and 0\le j+1\le n
$$
сПРАВЕДЛИВОСТЬ ПОСЛЕДНЕГО ЧЛЕНА СЛЕДУЕТ ИЗ СПРАВЕДЛИВОСТИ
$P \and j\not=n$; И В ЭТОМ НЕТ НИКАКОЙ ПРОБЛЕМЫ, ТАК КАК МЫ УЖЕ
РЕШИЛИ, ЧТО УСЛОВИЕ $j\not=n$, ВЗЯТОЕ В КАЧЕСТВЕ ПРЕДОХРАНИТЕЛЯ,
ЯВЛЯЕТСЯ ОСТАТОЧНО СЛАБЫМ, ЧТОБЫ ДЕЛАТЬ ВЫВОДЫ О ЗНАЧЕНИИ

\bye