Урок 35
Доказательство правильности программ
(§37. Доказательство правильности программ)
Содержание урока
Как доказать правильность программы?
Задачи
Задачи
1. Докажите, что следующие операторы дают одинаковый результат при любых значениях L и R (рассмотрите чётные и нечётные значения обеих переменных):
c:=div(L+R,2) с:=L+div(R-L,2)
Какие достоинства и недостатки есть у каждого метода вычисления этой величины?
2. Докажите, что в результате выполнения следующего фрагмента программы в переменной М не всегда будет записано максимальное из трёх чисел (а, b и с):
М:=а
если b>а то М:=b все
если с>b то М:=с все
Приведите контрпример, т. е. такие значения a, b и с, при которых значение М будет отличаться от max(a, b, с). Как можно исправить эту программу, заменив в ней всего один символ?
3. Докажите или опровергните правильность программы для выбора максимального из трёх значений, записанных в переменных a, b и с:
если a>b то М:=а
иначе если b>с то М:=b
иначе если с>а то М:=с
все; все; все
Если эта программа некорректная, приведите контрпример. Может ли быть, что при каких-то входных данных значение переменной М будет неопределённым?
4. Докажите, что следующий фрагмент программы правильно сортирует значения в переменных a, b и с по возрастанию, т. е. всегда получается а ≤ b ≤ с:
если а>b то поменять(а, b) все
если b>с то поменять(b, с) все
если а>b то поменять(а, b) все
Алгоритм поменять меняет местами значения переменных-параметров.
5. В игре «ним» двое игроков по очереди берут камни из двух кучек. За один ход можно взять любое ненулевое количество камней, но только из одной кучки. Тот, кому не осталось камней, проигрывает. Как определить, кто выиграет при правильной игре? Какой инвариант обеспечивает выигрыш?
6. Определите инвариант цикла для следующего алгоритма двоичного поиска (предполагается, что элементы массива А отсортированы по неубыванию):
L:=1; R:=n+1
нц пока L<R-1
с:=div(L+R,2)
если Х<А[с] то
R:=C
иначе
L:=c
все
кц
Используя найденный инвариант, определите, какой именно элемент массива будет найден, если в массиве есть несколько элементов, равных X. Как нужно изменить инвариант (и цикл), чтобы найти первый элемент, равный X?
7. Определите инварианты для следующих циклов. Что будет вычислено в переменной b?
8. Определите условия Q и R для алгоритмов:
а) нахождения суммы всех делителей числа;
б) проверки числа на простоту;
в) определения количества слов в символьной строке;
г) двоичного поиска элемента в отсортированном массиве;
д) перестановки элементов массива в обратном порядке;
е) преобразования числа из символьной записи в значение целого типа.
9. Предложите другие начальные значения переменных b, k и р в алгоритме быстрого возведения в степень. Инвариант цикла должен сохраниться.
10. Оцените сложность алгоритма быстрого возведения в степень при n = 2m, где m — натуральное число.
Следующая страница 
§37. Доказательство правильности программ
Cкачать материалы урока
