авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 || 4 | 5 |   ...   | 7 |

«министерство образования российской федерации московский государственный индустриальный университет кафедра информационные системы и технологии центр компьютерных ...»

-- [ Страница 3 ] --

§6. Спецификация программ и преобразователь предикатов 3. Определение простейших операторов языка Java. До сих пор все наши манипуляции с wp основывались на том, что мы считали извест ным, как именно выполняются те или иные команды, из которых состоит программа S.

Сейчас мы полностью изменим точку зрения. Будем считать первич ным предикат wp и условия, которым он удовлетворяет. Это позволит нам определить в терминах wp все команды языка, а затем доказывать всевозможные утверждения о программах.

Первым оператором, который мы определим, будет пустой оператор.

Определение 6.6. wp(";

", R) = R.

Определение не требует доказательства, однако полезно убедиться, что оно не противоречит нашему внутреннему пониманию того, как имен но работает пустой оператор. Проверьте это сами.

Определение 6.7. wp("System.exit(0);

", R) = F.

Выполнение вызова метода "System.exit(0)" приводит к немедлен ному завершению выполнения программы. Поэтому вполне естественно, что ни при каком начальном состоянии после его выполнения предикат R истинным не будет.

Следующее определение связано с последовательным выполнением двух операторов одного за другим.

Определение 6.8. wp("S1;

S2;

", R) = wp("S1;

", wp("S2;

", R)).

В случае последовательного выполнения нескольких операторов дан ным определением нужно воспользоваться многократно.

Более сложным и интересным является определение оператора при сваивания, которое будет рассмотрено нами в двух вариантах. Сначала рассмотрим случай присваивания простой переменной.

Определение 6.9. wp("x = e;

", R) = domain(e)&&Re, где domain(e) x предикат, описывающий множество всех состояний, в которых может быть вычислено значение e (т.е., где e определено), а R e обозначает под x становку в предикат R выражения e вместо всех свободных вхождений переменной x.

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

wp("x = 5;

", x = 5) = (T &&(5 = 5)) = T, что вполне правильно, так как присваивание переменной x числа 5 всегда делает x = 5.

84 Глава I. Введение в информатику и программирование wp("x = 5;

", x = 5) = (T &&(5 = 5)) = F, что тоже правильно, ибо присваивание переменной x числа 5 никогда не может сделать x = 5.

Часто можно позволить себе опустить предикат domain(e) и считать, x что wp("x = e;

", R) = Re, так как присваивание всегда должно выпол няться только в тех ситуациях, когда e может быть вычислено. В случае сомнений, однако, лучше воспользоваться исходным определением.

wp("x = 1/y;

", x 0) = (y = 0)&&(1/y 0) = (y 0).

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

Определение 6.10. Для присваивания элементу массива слабейшее b[i] предусловие wp("b[i] = e;

", R) = inrange(b, i)&&domain(e)&&Re.

В качестве примера рассмотрим массив b[0..9] и вычислим слабейшее предусловие wp("b[i] = i;

", b[i] = i) = (inrange(b, i)&&domain(i)&&i = i) = ((0 i 10)&&T &&T ) = (0 i 10).

4. Оператор if и слабейшее предусловие. Перед тем, как дать фор мальное определение оператора if-else в терминах wp, заметим, что управляющая конструкция if (без else части) эквивалентна использова нию пустого оператора в else-ветви. Оператор switch также может быть заменен несколькими вложенными друг в друга операторами if-else.

Таким образом, для того чтобы задать все основные конструкции выбора языка Java, достаточно дать определение только одной из них, кон струкции "if (e) S1;

else S2;

".

Определение 6.11. wp("if (e) S1;

else S2;

", R) = domain(e)&& (e wp("S1;

", R)) (!e wp("S2;

", R)).

В качестве примера использования этого определения убедимся в том, что wp("if (x = y) z=x;

else z=y;

", z = max(x, y)) = T.

В самом деле, wp("if (x = y) z=x;

else z=y;

", z = max(x, y)) = (((x y) wp("z=x;

", z = max(x, y)))!(x y) "z=y;

", z = max(x, y)) = (((x y) (x = max(x, y)))!(x y) (y = max(x, y))) = ((!(x y) (x = max(x, y)))!(!(x y)) (y = max(x, y))) = (((x y) (x = max(x, y))) (x y) (y = max(x, y))).

Покажем, что каждый из двух членов получившейся конъюнкции является тавтологией. Рассмотрим, например, первый из них ((x y) (x = max(x, y)). Если x y, то истинен первый член дизъюнкции.

§6. Спецификация программ и преобразователь предикатов В противном случае x y и поэтому истинен ее второй член, что и до казывает требуемое. Аналогичные рассуждения можно провести и для выражения (x y) (y = max(x, y))), что и завершает доказательство.

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

Теорема 6.1. Пусть предикат Q удовлетворяет условию ((Q e) wp(S1, R)) ((Q!e) wp(S2, R)).

Тогда (и только тогда) Q wp("if (e) S1;

else S2;

", R).

Доказательство. ((Q e) wp(S1, R)) = (!(Q e) wp(S1, R)) = (!Q!e wp(S1, R)) = (!Q (e wp(S1, R))) = (Q (e wp(S1, R))).

Аналогично получаем ((Q!e) wp(S2, R)) = (Q (!e wp(S2, R))), и, следовательно, (((Q e) wp(S1, R)) ((Q!e) wp(S2, R))) = ((Q (e wp(S1, R))) (Q (!e wp(S2, R)))) = (Q ((e wp(S1, R)) (!e wp(S2, R)))) = (Q wp("if (e) S1;

else S2;

", R)).

5. Циклы в терминах wp. В терминах слабейшего предусловия мож но определить все оставшиеся еще неопределенными конструкции языка, но мы ограничимся только определением цикла while. Дело в том, что уже даже это определение оказывается достаточно бесполезным с точки зрения практики. Именно оно, однако, позволяет предложить несколь ко вполне конструктивных подходов к построению цикла, которые будут изучаться в следующей главе.

Для определения слабейшего предусловия wp("while(e)S;

", R) нам потребуются следующие вспомогательные определения:

Определение 6.12. H0 (R) = domain(e)&&(!eR), Hk (R) = Hk1 (R) (domain(e)&&wp(S, Hk1 (R))), где предикат Hk (R) описывает множество всех состояний, в которых выполнение цикла "while(e)S;

" заканчивается не более, чем за k итераций, в состоянии, удовлетворяющем R.

Теперь можно дать основное определение.

Определение 6.13. wp("while(e)S;

", R) = (k 0Hk (R)).

Для цикла "while (i1) i=i+1;

" и постусловия R = (i = 1) имеем H0 (R) = (i 1 i = 1) = (i = 1). Действительно, именно при таком предусловии выполнение цикла завершится за ноль итераций и даст ре зультат R.

86 Глава I. Введение в информатику и программирование Далее, легко посчитать wp("i=i+1;

", H0 (R)) = (i + 1 = 1) = (i = 0) и H1 (R) = (i = 1) (i 1 i = 0) = (i = 1 i = 0).

Аналогично находим H2 (R) = (i = 1 i = 0 i = 1) и т.д.

6. Вычисление слабейшего предусловия. Покажем на ряде приме ров, как решаются задачи на вычисление слабейшего предусловия.

Задача 6.9. Вычислите и упростите wp("i=i+2;

j=j-2;

", i + j = 0).

Решение. Для вычисления воспользуемся определениями слабейше го предусловия для последовательного выполнения операторов и опера тора присваивания. Так как в данном случае все выражения заведомо яв ляются определенными, то истинный предикат domain(e) будет опущен изначально.

wp("i=i+2;

j=j-2;

", i + j = 0) = wp("i=i+2;

", wp("j=j-2;

", i + j = 0)) = wp("i=i+2;

", i + j 2 = 0) = (i + 2 + j 2 = 0) = (i = j).

Задача 6.10. Вычислите и упростите wp("x=(x+y)*(x-y);

", x + y 2 = 0).

Решение. wp("x=(x+y)*(x-y);

", x + y 2 = 0) = (x2 y 2 + y 2 = 0) = (x2 = 0) = (x = 0).

Задача 6.11. Вычислите и упростите wp("x=a/b;

", x2 0).

Решение. В данном случае ответ T является ошибочным, так как wp("x=a/b;

", x2 0) = (domain(a/b)&&(a/b)2 0) = (b = 0).

Задача 6.12. Вычислите и упростите wp("i=1;

s=b[0];

", 1 i n s = b[0] +... + b[i 1]).

Решение. wp("i=1;

s=b[0];

", 1 i n s = b[0] +... + b[i 1]) = wp("i=1;

", wp("s=b[0];

", 1 i n s = b[0] +... + b[i 1])) = wp("i=1;

", 1 i n b[0] = b[0] +... + b[i 1]) = (1 1 n (b[0] = b[0])) = (1 n (b[0] = b[0])) = (n 1).

Задача 6.13. Вычислите и упростите wp("if(true);

", R) для произ вольного предиката R.

Решение. wp("if(true);

", R) = wp("if(true);

else ;

", R) = ((T wp(";

", R))(F wp(";

", R))) = ((F R)(T R)) = (RT ) = R.

Рассмотрим в заключение задачу на решение уравнения, связанного со слабейшим предусловием.

Задача 6.14. Найдите такое значение выражения x, включающее дру гие переменные, для которого спецификация {Q} S {R} становится тав тологией: {T } "a=a+1;

b=x;

" {b = a + 1}.

§6. Спецификация программ и преобразователь предикатов Решение. Вспомним, что имеет место эквивалентность {Q} S {R} = (Q wp(S, R)). Таким образом, нам необходимо подобрать такое x, для которого (T wp("a=a+1;

b=x;

", b = a + 1)) = T. Вычислим сначала слабейшее предусловие, входящее в этот предикат: wp("a=a+1;

b=x;

", b = a + 1) = wp("a=a+1;

", wp("b=x;

", b = a + 1)) = wp("a=a+1;

", x = a + 1) = (x = a + 2).

Легко убедиться, однако, что мы получили неверный результат! И все дело в том, что переменная x зависит от a. Проведем вычисле ния повторно, заменив x на x(a): wp("a=a+1;

b=x(a);

", b = a + 1) = wp("a=a+1;

", wp("b=x(a);

", b = a + 1)) = wp("a=a+1;

", x(a) = a + 1) = (x(a + 1) = a + 2).

Вернемся к исходной задаче. Нам нужно выяснить, при каких значе ниях x выражение (T (x(a + 1) = a + 2)) = T окажется тавтологией.

Упростим данное выражение: ((T (x(a + 1) = a + 2)) = T ) = (T (x(a + 1) = a + 2)) = (F (x(a + 1) = a + 2)) = (x(a + 1) = a + 2).

Теперь ответ очевиден: x(a) = a + 1 или просто x = a + 1.

7. Задачи для самостоятельного решения.

Задача 6.15. Запишите предикат, утверждающий, что самое большее одно из следующих утверждений истинно: a b, b c.

Задача 6.16. Запишите предикат, утверждающий, что следующие утверждения не являются истинными одновременно: a b, b c и x = y.

Задача 6.17. Запишите предикат, утверждающий следующее: когда x y, y z означает, что v = w, но если x y, то y z не может выполняться;

однако если v = w, то x y.

Задача 6.18. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 все нули массива находятся в вырезке b[j..k].

Задача 6.19. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 некоторые нули массива находятся в вырезке b[j..k].

Задача 6.20. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 справедливо высказывание: неверно, что все нули массива находятся в вырезке b[j..k].

Задача 6.21. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 справедливо высказывание: неверно, что не все нули массива находятся в вырезке b[j..k].

Задача 6.22. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} является инъективной и отрицание этого факта. Упростите получившиеся предикаты, если это возможно.

88 Глава I. Введение в информатику и программирование Задача 6.23. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} является биективной и отрицание этого факта. Упростите получившиеся предикаты, если это возможно.

Задача 6.24. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} все существует единственный элемент x {1, 2, 3, 4, 5}, который функция f уменьшает, и отрицание этого факта. Не используйте при этом квантора !.

Задача 6.25. Основываясь на определении 6.4 и спецификации про граммы 6.1, докажите истинность эквивалентности {Q} S {R} = (Q wp(S, R)).

Задача 6.26. Основываясь на определении 6.4, докажите закон мо нотонности (Q R) (wp(S, Q) wp(S, R)).

Задача 6.27. Основываясь на определении 6.4, докажите закон дис трибутивности дизъюнкции wp(S, Q) wp(S, R) = wp(S, Q R).

Задача 6.28. Вычислите и упростите wp("i=i+1;

j=j-1;

", i · j = 0).

Задача 6.29. Вычислите и упростите wp("x=x+y;

", x 2y).

Задача 6.30. Вычислите и упростите wp("i=i+1;

j=j+1;

", i = j).

Задача 6.31. Вычислите и упростите wp("a=0;

n=1;

", a2 n (a + 1)2 n).

Задача 6.32. Вычислите и упростите wp("s=s+b[i];

i=i+1;

", i n s = b[0] +... + b[i 1]).

Задача 6.33. Вычислите и упростите следующее слабейшее предусло вие wp("if (a b) a=a-b;

else b=b-a;

", a 0 b 0).

Задача 6.34. Найдите такое значение выражения x, включающее дру гие переменные, для которого спецификация {Q} S {R} становится тав тологией: {T } "b=x;

a=a+1;

" {b = a + 1}.

Задача 6.35. Найдите такое значение выражения x, включающее дру гие переменные, для которого спецификация {Q} S {R} становится тав тологией: {i = j} "i=i+1;

j=x;

" {i = j}.

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

Бльшая часть задач позаимствована из различной литературы, среди о которой хочется отметить книги [9] и [14].

1. Задачи на составление алгоритмов.

Задача 7.1. Придумайте алгоритм, вводящий натуральное число, большее единицы, который находит наименьший простой делитель это го числа.

Задача 7.2. Придумайте алгоритм, вводящий три целых числа и определяющий, есть ли среди введенных чисел одинаковые или нет.

Задача 7.3. Придумайте алгоритм, вводящий три целых числа, ко торый находит второе по величине число, если оно существует.

Задача 7.4. Придумайте алгоритм, вводящий три целых числа, опре деляющий количество максимальных чисел среди введенных.

Задача 7.5. Придумайте алгоритм, вводящий действительное число, который рассматривает это число, как координаты точки на прямой, и находит расстояние от этой точки до отрезка [0, 1].

Задача 7.6. Придумайте алгоритм, находящий n-ое простое число.

2. Простейшие задачи на программирование.

Задача 7.7. Напишите программу, выводящую на экран строку тек ста Здравствуй, мир!.

Задача 7.8. Напишите программу, печатающую на экране красивое поздравление с новым учебным годом.

Задача 7.9. Напишите программу, вводящую имя пользователя (с применением метода inputChars), которая затем приветствует его.

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

Задача 7.11. Напишите программу, вводящую два целых числа a и b, печатающую их, затем обменивающую значения этих переменных (так, чтобы новое значение a стало равно старому значению b, и наоборот) и вновь их печатающую.

Задача 7.12. Напишите программу, вводящую два целых числа a и b, печатающую их, затем обменивающую значения этих переменных (так, 90 Глава I. Введение в информатику и программирование чтобы новое значение a стало равно старому значению b, и наоборот) и вновь их печатающую, которая не использовала бы иных переменных, кроме a и b.

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

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

Задача 7.15. Напишите программу, вводящую три целых числа, и пе чатающую Yes в том случае, если среди введенных чисел есть одинаковые, и No иначе.

Задача 7.16. Напишите программу, вводящую три целых числа, и печатающую второе по величине, если оно существует, и No иначе.

Задача 7.17. Напишите программу, вводящую действительное число, которая рассматривает это число, как координаты точки на прямой, и печатает расстояние от этой точки до отрезка [0, 1].

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

Задача 7.19. Напишите программу, вводящую действительные коэф фициенты a, b и c квадратного уравнения ax2 +bx+c = 0 с положительным дискриминантом, находящую оба корня этого уравнения.

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

Задача 7.21. Напишите программу, которая вводит действительные координаты (x, y) и (a, b) двух точек на плоскости, и печатает расстояние от точки M (x, y) до единичной окружности с центром в точке C(a, b).

Задача 7.22. Напишите программу, которая вводит действительные координаты (x, y) и (a, b) двух точек на плоскости, и печатает расстояние от точки M (x, y) до прямой OA, где O начало координат, а A(a, b) отличная от O точка.

Задача 7.23. Напишите программу, вводящую три целых числа a, b и c, печатающую мощность множества решений уравнения ax2 + bx + c = 0.

§7. Все задачи главы 3. Задачи на предикаты.

Задача 7.24. Докажите, что выражение ((a b) = (b a)) является предикатом.

Задача 7.25. Докажите, что выражение a a не предикат.

Задача 7.26. Докажите, что выражение ((e1 (e2 e3 )) = ((e1 e2 ) (e1 e3 ))) является предикатом.

Задача 7.27. Докажите, что выражение ((e1 (e2 e3 )) = ((e1 e2 )e3 )) является предикатом.

Задача 7.28. Докажите, что выражение ((a a) не предикат.

Задача 7.29. Докажите, что выражение ((a b)) не предикат.

Задача 7.30. Изобразите деревья вывода для каждого из законов эк вивалентности (см. страницу 42).

Задача 7.31. Вычислите значения предикатов P1 = (x = 0 x/(y 2) = 0) и P2 = (x = 0 && x/(y 2) = 0) в состоянии s = {(x, 7), (y, 2)}.

9 (i Задача 7.32. Вычислите значения предиката P = (i 0 i 0)) (j j 2 k) в состоянии s = {(k, 0)}.

Задача 7.33. Вычислите значения предиката P = (!(x y b)(b x y))!(x y b) в состоянии s = {(x, 3), (y, 2), (b, F )}.

Задача 7.34. Вычислите значения предиката P = (b (x y)) ((b (x y))||(!(x y) !b)) в состоянии s = {(x, 2), (y, 3), (b, T )}.

Задача 7.35. Покажите, что все законы эквивалентности (см. стр. 42) являются тавтологиями.

Задача 7.36. Запишите предикат, утверждающий, что если i j, а m n, то u = v.

Задача 7.37. Запишите предикат, утверждающий, что самое большее одно из следующих утверждений истинно: a b, b c.

Задача 7.38. Запишите предикат, утверждающий, что ни одно из сле дующих утверждений не является истинным: a b, b c и x = y.

Задача 7.39. Запишите предикат, утверждающий, что следующие утверждения не являются истинными одновременно: a b, b c и x = y.

Задача 7.40. Запишите предикат, утверждающий следующее: когда x y, y z означает, что v = w, но если x y, то y z не может выполняться;

однако если v = w, то x y.

92 Глава I. Введение в информатику и программирование Задача 7.41. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 все элементы вырезки b[j..k] являются нулевыми.

Задача 7.42. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 ни один из элементов вырезки b[j..k] не нулевой.

Задача 7.43. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 некоторые из элементов вырезки b[j..k] нулевые.

Задача 7.44. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 все нули массива находятся в вырезке b[j..k].

Задача 7.45. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 некоторые нули массива находятся в вырезке b[j..k].

Задача 7.46. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 справедливо высказывание: неверно, что все нули массива находятся в вырезке b[j..k].

Задача 7.47. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 справедливо высказывание: неверно, что не все нули массива находятся в вырезке b[j..k].

Задача 7.48. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 справедливо высказывание: если в b[0..n 1] есть нуль, то он есть и в вырезке b[j..k].

Задача 7.49. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 справедливо высказывание: если в вырезке b[j..k] есть два нуля, то j = 1.

Задача 7.50. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 справедливо высказывание: элементы в вырезке b[j..k] расположены в возрастающем порядке.

Задача 7.51. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 справедливо высказывание: j является степенью двойки, если j встречается в вырезке b[j..k].

Задача 7.52. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 справедливо высказывание: если b[1], b[2] и b[3] есть соответственно 3, 4 и 5, то j = 3.

Задача 7.53. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} является сюръективной и отрицание этого факта. Упростите получившиеся предикаты, если это возможно.

§7. Все задачи главы Задача 7.54. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} является инъективной и отрицание этого факта. Упростите получившиеся предикаты, если это возможно.

Задача 7.55. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} является биективной и отрицание этого факта. Упростите получившиеся предикаты, если это возможно.

Задача 7.56. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} все элементы, не превосходящие трех, не увеличивает, и отрицание этого факта. Упростите получившиеся преди каты, если это возможно.

Задача 7.57. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} все существует единственный элемент x {1, 2, 3, 4, 5}, который функция f уменьшает, и отрицание этого факта. Не используйте при этом квантора !.

Задача 7.58. Основываясь на определении 6.4 и спецификации про граммы 6.1, докажите истинность эквивалентности {Q} S {R} = (Q wp(S, R)).

Задача 7.59. Основываясь на определении 6.4, докажите закон мо нотонности (Q R) (wp(S, Q) wp(S, R)).

Задача 7.60. Основываясь на определении 6.4, докажите закон дис трибутивности дизъюнкции wp(S, Q) wp(S, R) = wp(S, Q R).

Задача 7.61. Вычислите и упростите wp("i=i+2;

j=j-2;

", i + j = 0).

Задача 7.62. Вычислите и упростите wp("i=i+1;

j=j-1;

", i · j = 0).

Задача 7.63. Вычислите и упростите wp("x=x+y;

", x 2y).

Задача 7.64. Вычислите и упростите wp("x=(x+y)*(x-y);

", x + y 2 = 0).

Задача 7.65. Вычислите и упростите wp("i=i+1;

j=j+1;

", i = j).

Задача 7.66. Вычислите и упростите wp("x=a/b;

", x2 0).

Задача 7.67. Вычислите и упростите wp("i=1;

s=b[0];

", 1 i n s = b[0] +... + b[i 1]).

Задача 7.68. Вычислите и упростите wp("a=0;

n=1;

", a2 n (a + 1)2 n).

Задача 7.69. Вычислите и упростите wp("s=s+b[i];

i=i+1;

", i n s = b[0] +... + b[i 1]).

94 Глава I. Введение в информатику и программирование Задача 7.70. Вычислите и упростите wp("if(true);

", R) для произ вольного предиката R.

Задача 7.71. Вычислите и упростите следующее слабейшее предусло вие wp("if (a b) a=a-b;

else b=b-a;

", a 0 b 0).

Задача 7.72. Найдите такое значение выражения x, включающее дру гие переменные, для которого спецификация {Q} S {R} становится тав тологией: {T } "a=a+1;

b=x;

" {b = a + 1}.

Задача 7.73. Найдите такое значение выражения x, включающее дру гие переменные, для которого спецификация {Q} S {R} становится тав тологией: {T } "b=x;

a=a+1;

" {b = a + 1}.

Задача 7.74. Найдите такое значение выражения x, включающее дру гие переменные, для которого спецификация {Q} S {R} становится тав тологией: {i = j} "i=i+1;

j=x;

" {i = j}.

Задача 7.75. Найдите такое значение выражения x, включающее дру гие переменные, для которого спецификация {Q} S {R} становится тав тологией: {i = j} "j=x;

i=i+1;

" {i = j}.

Задача 7.76. Задача о банке с кофейными зернами. В банке имеет ся несколько черных и белых кофейных зерен. Следующий процесс надо повторять, пока это возможно:

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

– если они разного цвета, поместите белое зерно обратно в бан ку и отбросьте черное зерно.

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

Задача 7.77. Замыкание кривой. Двое играют на листе клетчатой бу маги произвольной формы и размера в следующую игру. Игроки делают ходы поочередно и начинает игрок A. Ход игрока A состоит в том, что он соединяет горизонтальным или вертикальным отрезком два соседних узла решетки, проводя непрерывную линию по границе одного из квадра тиков (клеточек) бумаги. Ход игрока B сводится к проведению пунктир ной линии, обладающей теми же свойствами. Проводить линию по уже нарисованной противником нельзя.

§7. Все задачи главы Игрок A выигрывает, если ему удается получить полностью замкну тую кривую, состоящую из непрерывных линий. Если игрок A не сумеет получить замкнутую кривую, то считается, что победил игрок B. Суще ствует ли стратегия, гарантирующая выигрыш на произвольной доске для одного из игроков?

4. Задачи на особенности представления чисел в ЭВМ.

Задача 7.78. Предъявите целое число x такое, что x + 1 x.

Задача 7.79. Предъявите действительное (типа double) число x та кое, что x + 1 = x, а (x · 2)/2 = x. Воспользуйтесь тем, что класс java.lang.Double определяет константу MAX_VALUE.

Задача 7.80. Предъявите такие действительные (типа double) числа a, b и c такие, что a + (b + c) = (a + b) + c.

Задача 7.81. Явно перечислите и изобразите на числовой прямой все точки множества RM, сделав следующие допущения: числа хранятся в нормализованной форме с плавающей точкой;

для хранения как мантис сы, так и порядка числа отводится по три бита (из которых в обоих слу чаях один является знаковым);

никаких особых значений нет.

Задача 7.82. Предъявите действительное (типа double) число x та кое, что (x/2) · 2 = x. Воспользуйтесь тем, что класс java.lang.Double определяет константу MIN_VALUE.

Задача 7.83. Определите (приближенно) M ACHEP S (машинное эп силон) для типов double и float. Машинным эпсилоном называется наи большее число x данного типа, удовлетворяющее соотношению 1 + x = 1.

Задача 7.84. Предъявите последовательность чисел (типа float), при суммировании которой в прямом и обратном порядке результаты бу дут отличаться не менее, чем вдвое.

Задача 7.85. Напишите программу, вводящую действительные коэф фициенты a, b и c квадратного уравнения ax2 + bx + c = 0 с положитель ным дискриминантом, находящую оба корня этого уравнения достаточно точно во всех случаях.

5. Задачи на рекурсию и итерацию.

Задача 7.86. Напишите рекурсивную программу, вычисляющую фак ториал введенного натурального числа.

Задача 7.87. Напишите рекурсивную программу, печатающую n-ое число Фибоначчи.

96 Глава I. Введение в информатику и программирование Задача 7.88. Напишите итерационную программу, вычисляющую факториал введенного натурального числа.

Задача 7.89. Напишите программу, печатающую n-ое число Фибо наччи, которая имела бы линейную сложность.

Задача 7.90. Напишите программу, печатающую n-ое число Фибо наччи, которая имела бы логарифмическую сложность.

Задача 7.91. Напишите программу, вычисляющую факториал вве денного натурального числа, не использующую ни итерации, ни рекурсии (имеющую сложность (1)).

Указание. Воспользуйтесь тем, что факториал очень быстро рас тущая функция, а множество ZM ограничено, и поэтому любая про грамма, работающая с величинами типа int, способна вычислить факто риал только очень небольших чисел.

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

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

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

Задача 7.94. Напишите программу, вводящую целое число a и нату ральное n, вычисляющую и печатающую степень an без использования вызова функции возведения в степень.

Задача 7.95. Напишите программу (быстрое возведение в степень), возводящую целое число a в целую неотрицательную степень b без вызова функции возведения в степень с временнй сложностью (log b).

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

Задача 7.97. Напишите программу, вводящую натуральное число, и печатающую Yes, если оно является простым и No иначе.

Задача 7.98. Напишите программу, печатающую n-ое простое число.

§7. Все задачи главы Задача 7.99. Напишите рекурсивную программу, печатающую бино k минальный коэффициент Cn для целых n и k, где 0 k n. Для неотри n цательных n и k имеют место следующие соотношения: Cn = Cn = 1, k+1 k+1 k Cn+1 = Cn + Cn.

Задача 7.100. Напишите программу, печатающую старшую цифру в десятичной записи введенного натурального числа.

Задача 7.101. Напишите программу, печатающую количество цифр в десятичной записи введенного натурального числа.

Задача 7.102. Напишите программу, печатающую десятичную запись введенного натурального числа, использующую только операции печати цифр от 0 до 9.

Задача 7.103. Напишите программу, печатающую количество нату ральных решений неравенства x2 + y 2 n для введенного натурального числа n.

Задача 7.104. Напишите программу, вводящую натуральное число R, и печатающую количество точек с целочисленными координатами внутри замкнутого шара радиуса R с центром в начале координат.

Задача 7.105. Напишите программу, вводящую целые коэффициенты многочлена пятой степени в порядке убывания его степеней, и печатаю щую последовательность коэффициентов его куба.

Задача 7.106. Напишите программу, вводящую натуральное число x, и печатающую наиболее близкую к x простую дробь вида m/n со зна менателем n, не превосходящем 100.

Задача 7.107. Напишите программу, печатающую первые k пар про стых чисел. Два числа a и b образуют пару простых чисел, если они оба простые и b = a + 2.

Задача 7.108. Напишите программу, находящую сумму 1 1 1 + + +...+, 0! 1! 2! n!

сложность которой была бы линейной.

Задача 7.109. Напишите программу, находящую наибольший общий делитель gcd(X, Y ) двух натуральных чисел X и Y.

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

98 Глава I. Введение в информатику и программирование Задача 7.111. Напишите программу, находящую количество счастли вых билетов с шестизначными номерами. Билет называется счастливым, если сумма его первых трех цифр равна сумме трех последних.

6. Задачи на массивы.

Задача 7.112. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, печатает его, затем инвертирует (то есть меняет местами первый элемент с последним, второй с предпоследним и т.д.), и вновь печатает.

Задача 7.113. Напишите программу, печатающую максимальный элемент непустого массива.

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

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

Задача 7.116. Напишите программу, вводящую фразу русского языка (с использованием метода inputChars), которая определяет, является ли введенная фраза палиндромом.

Указание. Палиндром эта фраза, инвертирование которой не из меняет ее. При этом все пробелы во фразе игнорируются.

Задача 7.117. Напишите программу, печатающую количество нуле вых элементов в заданном целочисленном массиве.

Задача 7.118. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, и печатает Yes, если массив симметричен, и No иначе.

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

Задача 7.120. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, циклически сдвигает элементы массива вправо на k позиций, и печатает результат. Число k вводится с клави атуры, а сложность программы должна быть (n).

§7. Все задачи главы Задача 7.121. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, заменяет все элементы массива, кроме крайних, на полусумму соседей, и печатает результат.

Задача 7.122. Напишите программу (линейный поиск), определяю щую первое вхождение заданного целого числа x в массив целых чисел, заведомо содержащий это число.

Задача 7.123. Напишите программу, которая вводит с клавиатуры два непустых массива целых чисел в диапазоне от нуля до девяти, и, считая эти массивы десятичным представлением двух чисел, печатает их разность.

Задача 7.124. Напишите программу, которая вводит с клавиатуры два непустых неубывающих массива целых чисел, и печатает те и только те элементы, которые встречаются хотя бы в одном из массивов (объеди нение множеств).

Задача 7.125. Напишите программу, которая вводит с клавиатуры два непустых неубывающих массива целых чисел, и печатает те и только те элементы, которые встречаются в обоих массивах (пересечение мно жеств).

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

Задача 7.127. Напишите программу, печатающую значение много члена степени n 0 в заданной точке x0. Коэффициенты многочлена хранятся в массиве a в порядке убывания степеней и являются целыми числами, также как и значение x0. Величины n, x0 и элементы массива a изменять в программе нельзя.

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

Указание. Воспользуйтесь методом деления пополам, известным из курса математического анализа.

Задача 7.129. Напишите программу, заносящую в массив первые натуральных чисел, делящихся на 13 или на 17, и печатающую его.

100 Глава I. Введение в информатику и программирование Задача 7.130. Напишите программу, которая в массиве целых чисел длины m + n, рассматриваемом как соединение двух его частей нача ла длины m и конца длины n, обменивает начало и конец, не используя дополнительных массивов.

Задача 7.131. Напишите программу, вводящую целые коэффициенты многочлена и находящую все его рациональные корни.

Указание. Воспользуйтесь теоремой Безу, согласно которой числи p тель p любого рационального корня многочлена x = является делителем q свободного члена, а знаменатель q делителем старшего коэффициента.

Задача 7.132. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, и печатает число локальных максимумов (элемент является локальным максимумом, если он не имеет соседей, больших, чем он сам).

7. Задачи на последовательности.

Задача 7.133. Напишите программу, вводящую последовательность целых чисел, и печатающую количество ее максимальных элементов.

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

Задача 7.135. Напишите программу, вводящую последовательность вещественных чисел, и печатающую среднее арифметическое ее элементов (для непустой последовательности).

Задача 7.136. Напишите программу, вводящую последовательность целых чисел, и печатающую максимальное число идущих подряд одина ковых элементов.

Задача 7.137. Напишите программу, вводящую последовательность целых чисел, и печатающую номера первого и последнего ее максималь ных элементов.

Задача 7.138. Напишите программу, вводящую последовательность целых чисел, и печатающую номер первого элемента, равного нулю, и нуль при отсутствии такого элемента в последовательности.

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

§7. Все задачи главы Задача 7.140. Напишите программу, вводящую последовательность целых чисел, и печатающую второй по величине ее элемент и No, если такого элемента нет.

Задача 7.141. Напишите программу, вводящую последовательность целых чисел, и печатающую три ее таких (не обязательно различных) элемента x, y и z, что xy = z, или No, если таких элементов нет.

Задача 7.142. Напишите программу, вводящую последовательность целых чисел, и печатающую максимальную длину монотонного участка ее элементов.

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

Задача 7.144. Напишите программу, вводящую последовательность целых чисел, и печатающую количество вхождений в нее фрагмента 1, 2, 3, 4, 5, 6.

Задача 7.145. Напишите программу, вводящую последовательность целых чисел, и печатающую количество вхождений в нее фрагмента 1, 2, 1, 2, 1, 2.

Глава II Построение программ Основная цель данной главы показать, как теория помогает прак тике. Красивые и эффективные алгоритмы решения многих непростых задач при правильном подходе к ним будут получаться как бы сами собой. Процесс создания программ при этом в значительной мере авто матизируется, а вместе с решением мы получаем еще и доказательство правильности построенных программ.

В качестве дополнительного источника информации к данной главе можно порекомендовать книги [4] и [9].

§ 1. Базисные схемы обработки информации Все задачи на написание программ можно разделить на следующие три группы.

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

2. Задачи на программирование в малом. Бльшая часть за о дач, которые уже были нами рассмотрены, относятся именно к этой ка тегории. Кроме совсем простых к ней относятся и более сложные, при решении которых оправдано применение различных методов разработки программ типа проектирования сверху вниз.

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

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

Глава II. Построение программ $$¦#C§ A     B #¤¦$¤2!#7!'¤$$¤¤( 4§ %( 0  3&(D§%D #!¤¦¤  "  © § #!¤#¤'E$  "  © § #$¦'$¤'$¦¤$% @  §©(%&3( ¤!'$¦#$$# )( & §%§© $$#'!¤6!# )( ©&31F 2¤8¤67¤6¤!#¤ 9((5 %5 §3 ¤$!¤ 43 1 #¤!$$ 43 '$¦#$$# §& §%§© Рис. 1. Базисные схемы обработки информации Объектно-ориентированное проектирование в значительной мере по могает справиться со сложностью подобных задач, позволяя свести их к решению многих значительно более простых. Проекты, которые мы рас смотрим в следующей главе, позволят проиллюстрировать это на прак тике.

Предложенное деление задач на группы является достаточно услов ным и некоторые из них могут быть отнесены как ко второй, так и к третьей. В данной главе мы сосредоточимся на методах решения наибо лее простых задач из второй категории, программная реализация кото рых не превосходит 10–20 строк текста. Все подобные задачи можно рас сматривать, как задачи на обработку информации, что и поясняет назва ние классификации методов их решения схемы обработки информации, графическая иллюстрация взаимосвязи которых приведена на рисунке 1.

1. Рекурсия и итерация. Как определения этих двух базисных схем обработки информации, так и их взаимосвязь уже были рассмотрены на ми ранее. Напомним самое главное.

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

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

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

Некоторые особенности применения рекурсии уже были рассмотрены при решении задачи 5.1. Сейчас мы продолжим исследование данного §1. Базисные схемы обработки информации вопроса, уделяя особое внимание процессу построения программы и до казательству ее правильности. Рекурсивная программа обычно возникает, как результат вычисления рекурсивно определенной функции на множе стве программных переменных, а доказательство ее правильности требует исследования двух вопросов:

1) всегда ли и почему программа заканчивает работу?

2) почему после окончания работы программы будет получен требуемый результат?

Рассмотрим следующую задачу.

Задача 1.1. Напишите рекурсивную программу, перемножающую два целых числа, одно из которых неотрицательно, без использования операции умножения. Точные пред- и постусловия требуемой программы, времення сложность которой не должна превосходить (log b), таковы:

а Q = (a ZM b ZM b 0), R = (z = ab). Числа a и b в программе изменять нельзя.

Решение. Фиксировав a, рассмотрим функцию mula (b) : ZM ZM, задаваемую следующим рекурсивным определением:

mula (0) = 0, mula (b) = 2 · mula (b/2), когда b положительно и четно, mula (b) = mula (b 1) + a, когда b положительно и нечетно.

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

Текст программы.

public class MulR { static int mul(int x, int y) { // Xterm.print(" Вызов mul(" + x + "," + y + ")\n");

return (y == 0) ? 0 :

((y&1) == 0) ? mul(x,y 1) 1 : mul(x,y-1) + x;

} public static void main(String[] args) throws Exception { int a = Xterm.inputInt("a - ");

int b = Xterm.inputInt("b - ");

Xterm.println("a * b = " + mul(a,b));

} } Эта программа заканчивает работу, так как каждый следующий ре курсивный вызов уменьшает значение аргумента y функции mul a не ме нее, чем на единицу (нечетное число уменьшается ровно на один, а четное делится пополам, что при y = 2 приводит к уменьшению на один, а при 106 Глава II. Построение программ бльших значениях y к бльшему уменьшению). В результате конечно о о го числа таких операций y гарантированно станет нулем, что приведет к завершению цепочки рекурсивных вызовов.

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

Доказательство правильности получаемого результата проведем с по мощью метода математической индукции, показав, что при фиксирован ном a и 0 n является тавтологией предикат P (b) = (данная про b грамма печатает a · b).

Справедливость базы индукции P (0) следует непосредственно из тек ста программы, а индуктивный переход P (n) P (n + 1) осуществляется следующим образом. Если предположить, что программа правильна при b = n, то mula (n) = a · n. Рассмотрим далее два возможных случая.

Пусть сначала число y = n + 1 четно. Тогда результатом работы программы будет mula (n + 1) = 2 · mula ((n + 1)/2) = 2 · a · ((n + 1)/2) = a · (n + 1). Первое равенство здесь следует из текста программы, а второе из предположения индукции. Если число y = n + 1 является нечетным, то mula (n + 1) = mula (n) + a = a · n + a = a · (n + 1). Обоснование этих равенств проводится аналогично.

Таким образом, нами проверена истинность индуктивного перехода P (n) P (n + 1), что и завершает доказательство.

Для того чтобы увидеть цепочку рекурсивных вызовов функции mul a достаточно убрать символы комментария из первой строки этого мето да. Это позволяет понять, почему программа имеет сложность порядка (log b). Докажем аккуратно, что глубина рекурсии (количество рекур сивных вызовов) для нашей программы не превосходит 2 · [log b] + 1 (здесь [x] целая часть от x).

Каждый рекурсивный вызов функции mula уменьшает значение аргу мента y либо на единицу, либо вдвое. Два последовательных вызова этой функции всегда приводят к уменьшению величины y более, чем в два раза, поэтому y обратится в нуль после не более, чем после 2 · [log b] + рекурсивных вызовов. Обратите внимание, что мы не учитываем в наших рассуждениях самый первый, нерекурсивный вызов функции mul a.

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

Рассмотрим еще одну задачу.

§1. Базисные схемы обработки информации Задача 1.2. Напишите программу, печатающую значение многочлена степени n 0 в заданной точке x0. Коэффициенты многочлена хранятся в массиве a в порядке убывания степеней и являются целыми числами, также как и значение x0. Величины n, x0 и элементы массива a изменять в программе нельзя.

Решение. Заметим, что Pn (x) = a0 xn + a1 xn1 +... + an1 x + an = x·Pn1 (x)+an, где Pn1 (x) = a0 xn1 +a1 xn2 +...+an1. Воспользовавшись этим, определим функцию f : ZM ZM следующим образом:

f (0) = a0, f (n) = x0 · f (n 1) + an, при n 0.

Теперь можно написать программу, реализующую вычисление этой функции.

Текст программы.

public class PolVal { static int a[], x0;

static int p(int k) { return (k == 0) ? a[0] : x0 * p(k-1) + a[k];

} public static void main(String[] args) throws Exception { int n = Xterm.inputInt("n - ");

a = new int[n+1];

for (int i=0;

i=n;

i++) a[i] = Xterm.inputInt("a[" + i + "] - ");

x0 = Xterm.inputInt("x0 - ");

Xterm.println("P(" + x0 + ") = " + p(n));

} } Завершение программы за конечное число шагов следует из уменьше ния на единицу при каждом рекурсивном вызове аргумента функции p, а ее правильность получается из доказательства по индукции следующего утверждения R(n) = (программа печатает значение P (x0 ) многочлена Pn (x) = a0 xn + a1 xn1 +... + an1 x + an степени n в точке x0 ).

База индукции проверяется непосредственно, ибо при нулевом значе нии аргумента функция p(k) возвращает a[0], что совпадает с P 0 (x0 ). Ин дуктивный переход удается осуществить благодаря формуле, приведенной в начале решения данной задачи, которая позволяет выразить значение Pn (x0 ) через Pn1 (x0 ).

Рекурсивное решение задачи зачастую является менее эффективным, чем эквивалентное ему по другим параметрам итерационное решение.

Обычным способом программной реализации итерации является цикл, и 108 Глава II. Построение программ X T T T XQ T XR Рис. 2. Математическая модель итерации поэтому мы будем считать, что спецификация задачи на итерацию имеет вид {Q} "S0;

while(e)S;

" {R}.

Рассмотрим X множество значений всех программных переменных (прямое произведение множеств значений отдельных переменных), его подмножества XQ X и XR X, определяемые предикатами Q и R, и преобразование T : X X, соответствующее однократному выполне нию тела цикла S. Тогда построение условия продолжения цикла e и его тела S сводится к нахождению предиката e и преобразования T таких, что x XQ k 0 T k (x) XR.


Именно этот факт является основным результатом, вытекающим из определения слабейшего предусловия wp для оператора цикла (см. §6 пер вой главы). Геометрическая интерпретация математической модели ите рации, сводящейся к многократному применению преобразования T, при ведена на рисунке 2.

К сожалению эта математическая модель итерации является слиш ком общей и трудно применимой на практике, так как она не дает кон кретных рекомендаций по нахождению условия продолжения цикла e и тела цикла S по заданным Q и R. К рассмотрению более частных и более полезных схем мы сейчас и перейдем.

2. Инвариант и ограничивающая функция цикла. Основная идея метода проектирования цикла при помощи инварианта выражение вза имосвязи между меняющимися в теле цикла объектами в виде неизмен ного условия. Польза инварианта состоит в том, что такое описание взаи мосвязи легко понимаемо и позволяет, зная, как меняются одни объекты, §1. Базисные схемы обработки информации выводить, как должны изменяться другие. Тем самым инвариант помо гает сконструировать команды S0 и S.

Определение 1.1. Инвариант цикла I : X {T, F } предикат, ко торый истинен перед выполнением цикла и после каждой его итерации.

Любая тавтология является инвариантом произвольного цикла, одна ко такие инварианты бесполезны для целей проектирования программ.

Вопросы построения инвариантов будут исследованы в следующем па раграфе, а сейчас рассмотрим определение еще одного важнейшего поня тия.

Для построения корректного условия продолжения цикла e использу ется ограничивающая функция h. При каждом шаге цикла значение h(x) должно уменьшаться по крайней мере на единицу и оставаться положи тельным до завершения цикла. Ограничивающая функция позволяет га рантировать завершение цикла.

Определение 1.2. Ограничивающая функция h : X Z неотрица тельная функция, являющаяся верхней границей числа оставшихся ите раций цикла.

Схема проектирования цикла при помощи инварианта. На первом этапе выполняются простые присваивания S0, делающие инва риант I истинным, а в качестве условия продолжения цикла e берется предикат h 0. На втором этапе конструируется тело цикла S, ре ализующее преобразование T : сначала обеспечивается уменьшение огра ничивающей функции h, а затем сохранение инварианта I.

Геометрическая интерпретация данной схемы приведена на рисунке 3, где через XS0 обозначено множество, получающееся из XQ с помощью совокупности присваиваний S0.

Рассмотрим применение этой схемы для решения следующей задачи.

Задача 1.3. Напишите программу, перемножающую два целых чис ла, одно из которых неотрицательно, без использования операции умно жения. Точные пред- и постусловия требуемой программы, времення а сложность которой не должна превосходить (log b), таковы: Q = (a 0), R = (z = ab). При написании программы ве ZM b Z M b личины a и b изменять не разрешается, следует использовать инвариант I = (y 0 z + xy = ab) и ограничивающую функция h = y.

Решение. Для написания программы надо сконструировать S0 (со вокупность присваиваний, осуществляющих начальную инициализацию), условие продолжения e и тело цикла S.

Начальные присваивания должны сделать истинным инвариант (в случае истинности предусловия) и при этом быть максимально простыми 110 Глава II. Построение программ X T XR T T XS0 T X!e XI Рис. 3. Проектирование цикла при помощи инварианта и легко находимыми. В данном случае достаточно быстро можно обнару жить, что хорошим кандидатом на роль S0 является следующая совокуп ность присваиваний "x=a;

y=b;

z=0;

".

Условие продолжения цикла e нам уже по существу дано, так как очередная итерация цикла должна происходить только при h 0. По этой причине логично предположить, что наша программа должна содержать оператор "while(y0)S;

", тело которого S пока неизвестно.

Мы обязаны обеспечить завершение цикла, следовательно величина y должна уменьшаться на каждой его итерации. Уменьшение y каждый раз на единицу заведомо не позволит получить достаточно эффективную программу. По этой причине необходимо уменьшать величину y более бы стро. Хорошей мыслью является попытка делить величину y пополам то гда, когда это можно (при четных y). Легко оценить, что если бы деление пополам происходило на каждом шаге цикла, то количество его итераций было бы примерно равно log b. Это вполне согласуется с тем, что требуется в решаемой задаче.

Так как после итерации цикла инвариант должен остаться истинным, то уже зная, как меняется y, вычисляем, как следует изменять z (ибо по условию задачи мы не можем изменять a и b). В результате находим (либо в уме, либо формально вычисляя wp), что при четных y величину x следует удваивать, а при нечетных необходимо увеличивать значение переменной z на x.

Программа написана!

Текст программы.

public class MulI { §1. Базисные схемы обработки информации public static void main(String[] args) throws Exception { int a = Xterm.inputInt("a - ");

int b = Xterm.inputInt("b - ");

int x = a, y = b, z = 0;

while (y 0) { if ((y&1) == 0) { y = 1;

x += x;

} else { y -= 1;

z += x;

} } Xterm.println("a * b = " + z);

} } 3. Схема вычисления инвариантной функции. Общая схема ите рации значительно упрощается для случая вычисления значений инвари антных функций.

Определение 1.3. Пусть X некоторое множество, F : X Y заданная на нем функция, а P предикат такой, что P (x) = (F (x) лег ко вычислить). Обозначим через XP то подмножество множества X, где P (x) = T. Если существует преобразование T : X \ XP X такое, что x X \ XP F (T (x)) = F (x), то функция F называется T -инвариантной или просто инвариантной функцией.

Простейшим примером инвариантной функции является хорошо из вестная еще из средней школы функция f : R R, f (x) = sin x. Она яв ляется T -инвариантной относительно преобразования T : R R, T (x) = x + 2.

Наибольший общий делитель двух целых чисел (greatest common divisor, gcd(x, y) или просто НОД(x,y)) инвариантен относительно пре образования T : Z Z Z Z, задаваемого формулой (x y, y), если x y, T (x, y) = (x, y x), иначе.

Доказательство этого факта, основанное на основной теореме ариф метики о разложении числа на простые множители, является достаточно простым и оставляется читателю. Обратите только внимание на то, что функция gcd(x, y) не определена в точке (0, 0).

Для вычисления значения T -инвариантной функции F в точке x 0 X применяется следующая схема.

Схема вычисления инвариантной функции. Многократно выполняется преобразование T, дающее последовательность точек 112 Глава II. Построение программ X T T T XQ T XR XI XP Рис. 4. Схема вычисления инвариантной функции x0, x1,... Если очередная точка xn попадaет в подмножество XP, то итерации завершаются. По определению инвариантной функции F (xn ) легко вычисляется и совпадает с искомым F (x0 ).

Рисунок 4 содержит графическую иллюстрацию этой схемы.

Схема вычисления инвариантной функции значительно облегчает про ектирование программы "S0;

while(e)S;

S1;

", так как нам изначально известны инвариант I = (F (x) = F (x0 )) и условие продолжения цикла e(x) =!P (x). Тело цикла S конструируется, как программная реализация известного преобразования T, а написание S1, вычисляющей F (x n ), не может представлять трудностей в силу самого определения инвариант ной функции.

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

Задача 1.4. Напишите программу, находящую наибольший общий де литель gcd(x, y) двух целых неотрицательных чисел x и y, не равных од новременно нулю. Воспользуйтесь следующими свойствами наибольшего общего делителя (не забудьте научиться доказывать все эти свойства):

gcd(x, y) = gcd(x, y x) = gcd(x y, y), gcd(x, y) = gcd(x, y + x) = gcd(x + y, y), gcd(x, x) = x, gcd(x, y) = gcd(y, x), gcd(x, 0) = gcd(0, x) = x.

Решение. Если через Z+ обозначить множество всех неотрицатель M ных целых чисел, представимых в ЭВМ, то X = Z+ Z+ \ {(0, 0)}, Y = M M §1. Базисные схемы обработки информации Z+, XP = {(x, y) X x = 0 y = 0}, F (x, y) = gcd(x, y). В качестве преоб M (x y, y), если x y, разования T : X\XP X можно взять T (x, y) = (x, y x), иначе.

Таким образом, нам известны инвариант I = (gcd(x, y) = gcd(x0, y0 )) и условие продолжения e = (x = 0 y = 0). Начальные присваивания S в данном случае не нужны, тело цикла S пишется по определению T, a программа S1, вычисляющая gcd(x, y) для (x, y) XP, реализуется с помощью справедливой для этих значений аргумента формулы gcd(x, y) = x + y.

Текст программы.

public class Gcd { public static void main(String[] args) throws Exception { int x = Xterm.inputInt("x - ");

int y = Xterm.inputInt("y - ");

Xterm.print("gcd(" + x + "," + y + ") =");

while ( (x != 0) && (y != 0) ){ if (x = y) x -= y;

else y -= x;

} Xterm.println(" " + (x+y));

} } Обратите внимание на тот факт, что в построенной программе не пона добилось наличие переменной, соответствующей значению инвариантной функции gcd(x, y).

Рассмотрим еще одну задачу.

Задача 1.5. Напишите программу, перемножающую два целых чис ла, одно из которых неотрицательно, без использования операции умно жения. Точные пред- и постусловия требуемой программы, времення а сложность которой не должна превосходить (log b), таковы: Q = (a ZM b Z M b 0), R1 = (z = ab). При написании программы вели чины a и b изменять не разрешается. Воспользуйтесь тем, что функция F : ZM ZM ZM ZM, F (x, y, z) = z + xy является инвариантной отно сительно преобразования T : ZM ZM ZM ZM ZM ZM, задаваемого (2x, y/2, z), если y четно, формулой T (x, y, z) = (x, y 1, z + x), иначе.

В данном случае X = ZM Z+ ZM, Y = ZM, P = (y = 0), XP = M {(x, y, z) X : y = 0}. Функция F и преобразование T заданы в условии задачи.


114 Глава II. Построение программ Таким образом, нам известны инвариант I = (F (x, y, z) = F (a, b, 0)) и условие продолжения e = (y = 0). Начальные присваивания S0 очевидны ("x=a;

y=b;

z=0;

"), тело цикла S пишется по определению T, a програм ма S1, вычисляющая F (x, y, z) для (x, y, z) XP, в данном случае вы рождается в пустой оператор ";

", так как для этих значений аргумента F (x, y, z) = z. В результате получаем уже знакомую нам программу.

Текст программы.

public class MulInv { public static void main(String[] args) throws Exception { int a = Xterm.inputInt("a - ");

int b = Xterm.inputInt("b - ");

int x = a, y = b, z = 0;

while (y 0) { if ((y&1) == 0) { y = 1;

x += x;

} else { y -= 1;

z += x;

} } Xterm.println("a * b = " + z);

} } 4. Функции на пространстве последовательностей. Еще одной си туацией, в которой общая схема итерации значительно упрощается, явля ется задача вычисления индуктивных функций. Такие функции опреде лены на последовательностях X элементов из некоторого алфавита X.

Напомним важнейшие из определений §3.

произвольное непустое множество.

Алфавит X Символом алфавита X называют любой его элемент, а цепочкой над произвольную последовательность символов. Цепочки алфавитом часто называют также словами, фразами и предложениями. Пустая це почка обозначается специальным символом, а множество всех цепочек над алфавитом X принято обозначать X.

Длиной || цепочки X называется количество входящих в нее символов. Множество всех цепочек длины не менее k обозначают через Xk. Справедлива следующая последовательность включений:

X X1 X2 X3...

Операция : X X X конкатенации (или сцепления) двух цепочек определена следующем образом. Пусть 1 = a1 a2... an, 2 = b1 b2... bm, тогда 1 w2 = a1 a2... an b1 b2... bm.

§1. Базисные схемы обработки информации X G G G G XQ XR XI Рис. 5. Схема вычисления индуктивной функции Теперь можно дать определение индуктивной функции.

Определение 1.4. Функция f : X Y называется индуктивной, если f ( x) можно вычислить, зная f () и x, т.е. если G : Y X Y такое, что X x X f ( x) = G(f (), x).

Одним из простейших примеров индуктивной функции является функция длина цепочки || : X Z+. Она индуктивна, так как для нее существует функция G : Z+ X Z+, определенная формулой G(y, x) = y + 1, удовлетворяющая предыдущему определению.

Для вычисления значения f () индуктивной функции f на цепочке = a1 a2... an применяется следующая схема.

Схема вычисления индуктивной функции. Рассматривается последовательность цепочек, a1, a1 a2,..., a1 a2... an =. Сначала вы числяется значение f () функции f на пустой цепочке, а затем ис пользуется отображение G, позволяющее найти значение функции f на удлиненной цепочке, что дает возможность последовательно опре делить все требуемые величины вплоть до f ().

На рисунке 5 приведена графическая иллюстрация схемы вычисления индуктивной функции.

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

Схема вычисления индуктивной функции позволяет легко построить программу вида "S0;

while(e)S;

", получающую на каждой следующей 116 Глава II. Построение программ итерации цикла очередной элемент ai цепочки (последовательности) = a1 a2... an, которая находит значение f (). Инвариантом данного цикла является I = (0 i n f = f (a1 a2... ai )), условием продолжения e = (i n), S0 должно вычислять f (), а S быть программной реализацией функции G.

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

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

Заметим, что Pn (t) = a0 tn + a1 tn1 +...+ an1 t + an = t · Pn1 (t) + an, где Pn1 (t) = a0 tn1 + a1 tn2 +... + an1. Поэтому функция f : (ZM ) ZM, определенная, как f () = f (a0 a1... an ) = Pn (t), удовлетворяет соотноше нию f ( x) = t·f ()+x, что доказывает ее индуктивность. Отображение G : ZM ZM ZM действует по формуле G(y, x) = ty + x, а f () = 0, что приводит к следующей программе.

Текст программы.

public class Pol { public static void main(String[] args) throws Exception { int t = Xterm.inputInt("t - ");

int y = 0;

try { while (true) { int x = Xterm.inputInt("x - ");

y = t*y + x;

} } catch (Exception e) { Xterm.println("\ny = " + y);

} } } Этот эффективный метод вычисления значения многочлена в точке носит имя схемы Горнера.

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

5. Задачи для самостоятельного решения. При решении задач на рекурсию необходимо обосновать как то, почему программа заканчивает §1. Базисные схемы обработки информации работу, так и то, почему после ее завершения будет получен требуемый результат.

При использовании схемы вычисления инвариантной функции необ ходимо указать множества X, Y и XP, функцию F и преобразование T (см. определение инвариантной функции) и объяснить программную ре ализацию преобразования T.

Задача 1.7. Напишите рекурсивную программу, печатающую значе ние производной многочлена степени n 0 в заданной точке x 0. Коэффи циенты многочлена хранятся в массиве a в порядке убывания степеней и являются целыми числами, так же как и значение x0. Величины n, x0 и элементы массива a изменять в программе нельзя.

Указание. Пусть Pn (x) = a0 xn + a1 xn1 +... + an1 x + an. Продиф ференцируем по x равенство Pn (x) = x · Pn1 (x) + an и подставим затем x = x0. Мы получим следующие соотношения:

P0 (x0 ) = 0, Pn (x0 ) = x0 · Pn1 (x0 ) + Pn1 (x0 ).

Воспользовавшись ими и формулами P0 (x0 ) = a0, Pn (x0 ) = x0 · Pn1 (x0 ) + an, легко определить рекурсивную функцию неотрицательного целого аргу мента g : ZM ZM ZM, g(n) = (Pn (x0 ), Pn (x0 )) для вычисления которой и пишется программа.

Задача 1.8. Напишите программу, возводящую целое число в целую неотрицательную степень. Точные пред- и постусловия требуемой про 0), R = (z = ab ).

граммы таковы: Q = (a ZM b ZM a 0 b При написании программы величины a и b изменять не разрешается, сле дует использовать инвариант I = (y 0 z · xy = ab ) и ограничивающую функцию h = y.

Задача 1.9. Напишите программу, находящую наибольший общий де литель gcd(x, y) двух целых неотрицательных чисел x и y, не равных од новременно нулю. Воспользуйтесь следующим свойством наибольшего об щего делителя (докажите его!):

gcd(x%y, y), если x y, gcd(x, y) = gcd(x, y%x), иначе.

Здесь операция x%y позволяет найти остаток от деления x на y.

Задача 1.10. Напишите программу, возводящую целое число в це лую неотрицательную степень. Точные пред- и постусловия требуемой программы таковы: Q = (a ZM b ZM a 0 b 0), R1 = (z = ab ).

118 Глава II. Построение программ При написании программы величины a и b изменять не разрешается. Вос пользуйтесь тем, что функция F : ZM ZM ZM ZM, F (x, y, z) = zxy является инвариантной относительно преобразования T : Z M ZM ZM ZM ZM ZM, задаваемого формулой T (x, y, z) = (x, y 1, xz).

Задача 1.11. Напишите программу, находящую наибольший общий делитель gcd(x, y) двух целых неотрицательных чисел x и y, не равных одновременно нулю. Программа должна иметь временню сложность по у рядка (log max(x, y)) и не использовать операций деления и нахождения остатка от деления (допустимо деление пополам, реализуемое с помощью операции сдвига). Воспользуйтесь следующими свойствами наибольшего общего делителя (докажите их!):

gcd(2x, 2y) = 2gcd(x, y), gcd(2x, 2y + 1) = gcd(x, 2y + 1).

Указание. Воспользуйтесь инвариантностью функции F (x, y, z) = z · gcd(x, y) относительно следующего преобразования T :

(x/2, y/2, 2z), если оба числа x и y четны, если x четно, а y нечетно, (x/2, y, z), T (x, y, z) = (x, y/2, z), если x нeчетно, а y четно, если x и y нечетны и x y, (x y, y, z), если x и y нечетны и x y.

(x, y x, z), Не забудьте доказать T -инвариантность функции F.

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

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

Теорема 2.1. Если 1) {Q} "S0;

" {I}, 2) {I e} "S;

" {I}, 3) (I!e) R, 4) Ieh0 и 5) {I e} "h1=h;

S;

" {h h1}, §2. Проектирование цикла при помощи инварианта то спецификация программы {Q} "S0;

while(e)S;

" {R} является тав тологией.

Докажем с помощью этой теоремы правильность некоторых программ, построенных в предыдущем параграфе.

Текст программы.

public class MulI { public static void main(String[] args) throws Exception { int a = Xterm.inputInt("a - ");

int b = Xterm.inputInt("b - ");

int x = a, y = b, z = 0;

while (y 0) { if ((y&1) == 0) { y = 1;

x += x;

} else { y -= 1;

z += x;

} } Xterm.println("a * b = " + z);

} } 1) (Q wp(S0, I)) = (b 0 wp("x=a;

y=b;

z=0;

", y 0 z + xy = ab)) = ((b 0) ((b 0) T )) = (b 0 b 0) = T.

2) Для того чтобы проверить, что предикат I e wp(S, I) является тавтологией, вычислим предварительно wp(S, I).

wp(S, I) = wp("if((y&1)==0){y/=2;

x+=x;

} else{y-=1;

z+=x;

}", y 0 z + xy = ab) = ((y четно wp("y/=2;

x+=x;

", y 0 z + xy = ab)) (y нечетно wp(" y-=1;

z+=x;

", y 0 z + xy = ab))) = ((y нечетно (y 0 z + xy = ab)) (y четно (y 1 z + xy = ab))) = ((y нечетно y четно) (y нечетно (y 1 z + xy = ab)) (y четно (y 0 z + xy = ab)) ((y 0 z + xy = ab) (y 1 z + xy = ab))) = (F ((z + xy = ab) (y нечетно y 1)) ((z + xy = ab) (y четно y 1))) = ((z + xy = ab) (y нечетно y 0)) ((z + xy = ab) (y 1 y четно y 0 y 1)) = ((z + xy = ab) (y 0)) = I.

Далее имеем (Ie wp(S, I)) = (!I!eI) = (!e(I!I)) = (!eT ) = T.

3) (I!e R) = (!I e R) = (y 0 z + xy = ab y 0 z = ab) = (y 0 y 0 z = ab z + xy = ab).

Получившийся предикат представляет собой дизъюнкцию четырех членов и, очевидно, истинен, если истинны первый или второй из этих членов. В противном случае y = 0, и предикат принимает вид (z = abz = ab) = T. Таким образом, (I!e R) тавтология.

4) (I e h 0) = (!I!eh 0) = (!I (y 0y 0)) = (!I T ) = T.

120 Глава II. Построение программ 5) Для проверки последнего условия найдем wp("h1=h;

S;

", h h1) = wp("h1=y;

", wp("if((y&1)==0){y/=2;

x+=x;

} else{y-=1;

z+=x;

}", y h1)) = wp("h1=y;

", (y четно wp("y/=2;

x+=x;

", y h1)) (y нечетно wp("y-=1;

z+=x;

", y h1))) = wp("h1=y;

", (y нечетноy 2 h1) (y четно y h1 + 1)) = ((y нечетно y 2 y) (y четно y y + 1)) = ((y нечетно y 2 y) (y четно T )) = ((y нечетно y 2 y) T ) = (y нечетно y 2 y) = (y нечетно y 0).

Тогда имеем (I e wp("h1=h;

S;

", h h1)) = (y 0 z + xy = ab y 0 y нечетно y 0) = ((y 0 z + xy = ab y нечетно) (y 0 y 0)) = ((y 0 z + xy = ab y нечетно) T ) = T, что завершает доказательство правильности написанной программы.

Докажем частично правильность еще одной построенной в предыду щем параграфе программы.

Текст программы.

public class Gcd { public static void main(String[] args) throws Exception { int x = Xterm.inputInt("x - ");

int y = Xterm.inputInt("y - ");

Xterm.print("gcd(" + x + "," + y + ") =");

while ( (x != 0) && (y != 0) ){ if (x = y) x -= y;

else y -= x;

} Xterm.println(" " + (x+y));

} } Если в качестве ограничивающей функции взять h = x · y, то правиль ность полученной программы легко может быть доказана. Обозначим че рез x0 и y0 начальные значения переменных x и y, удовлетворяющих пре дусловию Q = (x Z+ y Z+ (x, y) = (0, 0)). Заметим также, что M M постусловие программы в целом может быть записано в виде предика та R1 = (напечатан gcd(x, y)), а постусловием цикла является предикат R = (x = 0 y = 0).

1) (Q wp(";

", gcd(x, y) = gcd(x0, y0 ))) =!Q T = T.

2) Сохранение инварианта после выполнения тела цикла следует из T -инвариантности gcd(x, y). Формальную проверку проведите самостоя тельно.

3) ((I!e) R) = (!I (x = 0 y = 0) (x = 0 y = 0)) = (!I ((x = 0 y = 0)!(x = 0 y = 0))) = (!I T ) = T.

4) Формальное доказательство проведите самостоятельно.

5) Формальное доказательство проведите самостоятельно.

§2. Проектирование цикла при помощи инварианта 6) Для завершения доказательства правильности программы необхо димо еще показать, что является тавтологией R wp("S1", R1). Так как формального определения операторов печати мы не рассматривали, бу дем считать, что предикат R1 = (z = gcd(x, y)), а S1 имеет вид "z=x+y;

".

(R wp("S1", R1)) = ((x = 0 y = 0) (x + y = gcd(x, y))) = (!(x = 0 y = 0) (gcd(x, y) = x + y)).

Полученная дизъюнкция истинна, если ложно условие (x = 0 y = 0).

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

2. Теория воздушного шарика. До сих пор мы использовали для по строения программ готовые, не ясно откуда взявшиеся инварианты. На практике, конечно, постановка задачи не включает в себя инвариант. Од нако любая корректная постановка задачи содержит ее пред- и посту словия: {Q} "S0;

while(e)S;

" {R}, поэтому они и должны послужить основой для построения инварианта.

Теперь нужно понять, какой именно из двух предикатов Q и R бо лее важен для построения инварианта. Приведем два аргумента в пользу постусловия R.

Первый таков: предусловие Q достаточно часто имеет вид T, что со ответствует отсутствию ограничений на начальные условия, в которых должна правильно работать программа. Понятно, что в этом случае ин вариант можно строить только исходя из постусловия R.

Второй аргумент: представим себе R в виде цели, которой должен до стичь путник на местности, а Q в виде точки его начального расположе ния. Инвариант, который мы хотим построить, должен помочь путнику достичь нужной ему цели. Можно ли надеяться на это, полностью про игнорировав R?

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

Именно по этой причине программирование называют целенаправлен ной деятельностью, а за основу для построения инварианта берут посту словие R.

Рассмотрим геометрическую иллюстрацию стоящей перед нами зада чи, изобразив на множестве X всех значений программных переменных подмножества XS0 и XR, второе из которых задается постусловием R, а первое представляет собой множество, которое может быть получено из 122 Глава II. Построение программ X XS... XR XP XP0 XP Рис. 6. Теория воздушного шарика XQ после выполнения совокупности простых присваиваний S0. Искомо му инварианту цикла I на рисунке 6 должно соответствовать какое-то неизвестное нам пока множество XI.

Существует весьма красивое описание того, что происходит с множе ством переменных программы в процессе выполнения цикла, называемое теорией воздушного шарика. Рассмотрим последовательность предикатов P0, P1,..., Pn, описывающих множества переменных до начала цикла, по сле его первой итерации,..., после n-ой (последней) итерации.

Множества, определяемые этими предикатами, представляют после довательность вложенных друг в друга множеств, причем X P0 = XI, а XPn = XR. Удобно представлять себе эти множества как последователь ные состояния изначально надутого воздушного шарика, из которого на каждой очередной итерации цикла выпускают немного воздуха.

Используя эту модель, можно сказать, что построение инварианта тре бует так надуть шарик, находящийся в состоянии XR, чтобы он стал содержать множество XS0. С математической точки зрения необходимо ослабить предикат R до такой степени, чтобы истинность этого ослаб ленного предиката (который и будет взят в качестве инварианта I) могла быть получена из истинного Q с помощью простых начальных присваи ваний S0.

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

§2. Проектирование цикла при помощи инварианта Реально применяются три первых из следующих ниже приведенных методов построения инварианта.

1) Устранение конъюнктивного члена. Предикат A B C можно осла бить до A C.

2) Замена константы переменной. Предикат (j 0 j n x b[j]) мо жет быть ослаблен до (0 i n) (j 0 j i x b[j]), где i новая переменная.

3) Расширение области значений переменной. Предикат 5 i 10 мож но ослабить до 0 i 10.

4) Добавление дизъюнктивного члена. Предикат A можно ослабить до A B, где B некоторый другой предикат.

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

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

Рассмотрим в качестве примера следующую задачу.

Задача 2.1. Напишите программу, находящую приближенное зна чение квадратного корня a Z+ из заданного неотрицательного це M лого числа n. Вот более точная формулировка пред- и постусловия:

Q = (n ZM n 0), R = (a ZM a 0 a2 n (a + 1)2 n). При написании программы величину n изменять нельзя.

Решение. Построим инвариант с помощью метода устранения конъ юнктивного члена (a + 1)2 n из постусловия: I = (a 0 a2 n).

В качестве условия продолжения цикла e может быть взято отрицание удаленного конъюнктивного члена: e = ((a + 1)2 n), что эквивалентно выбору ограничивающей функции h = n (a + 1)2 + 1. Истинность инва рианта перед началом выполнения цикла легко устанавливается присваи ванием "a=0;

" и нам остается только понять, как реализовать тело цикла S.

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

124 Глава II. Построение программ Текст программы.



Pages:     | 1 | 2 || 4 | 5 |   ...   | 7 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.