Урок 35
Доказательство правильности программ
(§37. Доказательство правильности программ)
Содержание урока
Задачи
Задачи
1. Докажите, что следующие операторы дают одинаковый результат при любых значениях L и R (рассмотрите чётные и нечётные значения обеих переменных):
Какие достоинства и недостатки есть у каждого метода вычисления этой величины?
2. Докажите, что в результате выполнения следующего фрагмента программы в переменной М не всегда будет записано максимальное из трёх чисел (а, 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. Определите инвариант цикла для следующего алгоритма двоичного поиска (предполагается, что элементы массива А отсортированы по неубыванию):
Следующая страница 
§37. Доказательство правильности программ
Cкачать материалы урока
Учитель информатики
Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.
Доказательство правильности программ. ГДЗ по Информатике 11 класс.
Информатика. 11 класс. Углубленный уровень. В 2 ч. Поляков К.Ю., Еремин Е.А.
§ 37. Доказательство правильности программ
Вопросы и задания
1. Зачем нужно доказывать правильность программ?
2. Расскажите о двух подходах к проверке правильности программ.
3. Почему с помощью тестирования сложно доказать правильность программы? В каких случаях это всё же можно сделать? Приведите примеры.
4. Что изменится в доказательстве алгоритма Евклида, если тип — это произвольные натуральные числа (неравенство m ≥ n может не выполняться)?
5. Что такое инвариант цикла?
6. Зачем нужно определять инвариант цикла?
7. Что такое спецификация? Почему желательно формулировать её в виде формальных утверждений, а не на естественном языке?
8. Объясните запись S
9. Какая программа называется корректной?
10. Как вы думаете, можно ли назвать корректной программу, которая «зависает» при неверных входных данных? Обсудите этот вопрос в классе.
11. Что такое верификация программы?
12. Как вы думаете, что сложнее — доказывать правильность готовой программы или сразу писать программу, доказывая правильность отдельных блоков? Почему? Обсудите этот вопрос в классе.
Задача
1. Докажите, что следующие операторы дают одинаковый результат при любых значениях L и R (рассмотрите чётные и нечётные значения обеих переменных):
Какие достоинства и недостатки есть у каждого метода вычисления этой величины?
2. Докажите, что в результате выполнения следующего фрагмента программы в переменной М не всегда будет записано максимальное из трёх чисел (а, 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. Определите инвариант цикла для следующего алгоритма двоичного поиска (предполагается, что элементы массива А отсортированы по неубыванию):
Урок 63
Доказательство правильности программ
(§37. Доказательство правильности программ)
Содержание урока
Задачи
Задачи
1. Докажите, что следующие операторы дают одинаковый результат при любых значениях L и R (рассмотрите чётные и нечётные значения обеих переменных):
Какие достоинства и недостатки есть у каждого метода вычисления этой величины?
2. Докажите, что в результате выполнения следующего фрагмента программы в переменной М не всегда будет записано максимальное из трёх чисел (а, 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. Определите инвариант цикла для следующего алгоритма двоичного поиска (предполагается, что элементы массива А отсортированы по неубыванию):
Следующая страница §37. Доказательство правильности программ
Cкачать материалы урока
Сегодня будем тренироваться решать 19 задание из ЕГЭ по информатике.
В девятнадцатом задании ЕГЭ по информатике обычно даются задачи, в которых есть программный код на пяти языках программирования, и нужно показать умение работать с массивами.
Все примеры буду рассматривать на языке программирования Паскаль, который популярен на уроках информатики.
Пусть у нас есть пять переменных, и их первоначальные значения нужно увеличить в два раза. Тогда без массива код будет выглядеть следующим образом:
Видим, что приходится каждую переменную умножать отдельно.
Теперь тоже самое сделаем с помощью массива.
Обратите внимание, что удвоение во втором случае идёт с помощью двух строчек, когда в первом случае, удвоение получается с помощью пяти строчек. Если бы переменных было 1000, то выигрыш в объёме кода, был бы ещё большим.
Схематично наш массив можно представить так:
Это те же 5 переменных, но они объединены общем именем A. К каждому элементу массива можно обратится по индексу A[1], A[2] и т.д.
Здесь мы задали нумерацию элементов массива от 1 до 5. В паскале можно задать нумерацию элементов массива и от нуля. Например A:array[0..24] of integer;
Удобство использования массива заключается в том, что его элементы можно перебирать и обрабатывать с помощью ЦИКЛОВ! Значит, обычно массив и цикл работают в связке.
Не терпится уже разобрать первый пример из предположительных задач ЕГЭ по информатике.
Примеры решения задач 19 задания из ЕГЭ по информатике
В программе используются целочисленный массив A с индексами от 0 до 9. Значения элементов массива равны 4; 5; 4; 7; 6; 3; 9; 11; 7; 8 соответственно, т.е. A[0] = 4; A[1] = 5 и т.д.
Определите значение переменной k после выполнения следующего фрагмента программы, записанной ниже на разных языках программирования.
| Бейсик | Python |
|---|---|
| Паскаль | Алгоритмический язык |
| Си++ | |
Решение:
Рассмотрим программу на языке Паскаль.
В начале переменная k = 0.
Затем начинается ЦИКЛ. Цикл будет выполнятся, пока переменная i «бежит» от 0 до 8.
При первом проходе ЦИКЛА i = 0, при втором i = 1 и т.д.
Внутри цикла проверяется условие (A[i] > A[i+1]). Если условие ВЕРНО, то программа прибавляет к переменной k единицу, и плюс, меняет значения ячеек массива A[i] и A[i+1] с помощью дополнительной переменной t.
Про замену значений двух переменных у меня на сайте написана целая статья!
Чтобы понять, чему равна переменная k после окончания программы, нужно понять, сколько раз будет верно условие внутри цикла.
Сам массив нам дан! (4; 5; 4; 7; 6; 3; 9; 11; 7; 8).
На рисунке показана каждая итерация ЦИКЛА при всех значениях переменной i. Зелёной галочкой отмечены те итерации, где сработает условие, и, значит, переменная k будет увеличена на 1.
Важно: После первого срабатывания условия, программа меняет значения элементов A[1] и A[2]. И наш массив принимает следующий вид: 4; 4; 5; 7; 6; 3; 9; 11; 7; 8. И при следующем проходе A[2] снова принимает значение «5», а не «4»! И так во всех случаях, когда условие срабатывает!
Таким образом, значение k после выполнения программы равна 5.
Продолжаем подготовку к 19 заданию из ЕГЭ по информатике.
Задача (ЕГЭ по информатике, 2019, Москва)
Определите значение переменной s после выполнения фрагмента этой программы (записанной ниже на разных языках программирования)
| Бейсик | Python |
|---|---|
| Паскаль | C++ |
Решение:
В ЦИКЛЕ i проходит каждое значение от 0 до 9. В теле Цикла только условие! А в условии проверяется: будет ли элемент массива A с индексом i больше, чем A[n].
В первый раз n=6 (A[6] = 8). Напоминаю, что в этой задаче номера индексов массива начинаются с нуля! Но если условие «сработает», то A[n] поменяется.
Если условие выполнится, то значение A[n] станет равно A[i]. Опять присутствует блок, где элементы массива A[n] и A[i] меняются значениями (Найдите этот кусок кода сами!). И, соответственно, сравнивать в условии будем тоже с новым значением.
Причем, сначала происходит суммирование для переменной s, а потом уже замена значения для A[n].
| i | A[i] | A[n] | A[i] > A[n] | A[i] mod A[n] | s |
| 0 | 2 | 8 | 2 > 8 | — | 0 |
| 1 | 3 | 8 | 3 > 8 | — | 0 |
| 2 | 5 | 8 | 5 > 8 | — | 0 |
| 3 | 6 | 8 | 6 > 8 | — | 0 |
| 4 | 10 | 8 | 10 > 8 | 2 | 2 |
| 5 | 4 | 10 | 4 > 10 | — | 2 |
| 6 | 10 | 10 | 10 > 10 | — | 2 |
| 7 | 6 | 10 | 6 > 10 | — | 2 |
| 8 | 12 | 10 | 12 > 10 | 2 | 4 |
| 9 | 9 | 12 | 9 > 12 | — | 4 |
Таким образом, по окончании данного фрагмента программы, получится в переменной s значение 4.
Ещё один пример 19 задания из реального экзамена, который был в 2020 году в Москве!
Задача (ЕГЭ по информатике, 2020, Москва)
Представленный ниже фрагмент программы обрабатывает элементы одномерного целочисленного массива A c индексами от 0 до 11. Перед началом выполнения данного фрагмента эти элементы массива имели значения согласно таблице:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 5 | 43 | 20 | 7 | 13 | 7 | 20 | 13 | 2 | 33 | 15 | 5 |
Определите значение переменной s после выполнения фрагмента этой программы (записанного ниже на разных языках программирования).
| Бейсик | Python |
|---|---|
| Паскаль | C++ |
Решение:
| i | A[i-1] | A[i] | A[i-1] div A[i] 0 | 43 | 43 (в конце итерации) |
| 2 | 43 | 20 | 2 | 43 | 40 (в конце итерации) |
| 3 | 40 | 7 | 5 | 43 | 21 (в конце итерации) |
| 4 | 21 | 13 | 1 | 56 | 13 (в конце итерации) |
| 5 | 13 | 7 | 1 | 63 | 7 (в конце итерации) |
| 6 | 7 | 29 | 0 | 92 | 29 (в конце итерации) |
| 7 | 29 | 13 | 2 | 92 | 91 (в конце итерации) |
| 8 | 91 | 2 | 45 | 92 | 16 (в конце итерации) |
| 9 | 16 | 33 | 0 | 125 | 33 (в конце итерации) |
| 10 | 33 | 15 | 2 | 125 | 150 (в конце итерации) |
| 11 | 150 | 5 | 30 | 125 | 55 (в конце итерации) |
Ответ: 125
На этом всё! Счастливого ЕГЭ по информатике!
Информатика. 11 класс
Индекс в одномерном массиве
Что такое индекс в одномерном массиве?
порядковый номер элемента массива
наибольший номер элемента массива
Описания массивов
Какие описания массивов записаны верно, а какие — нет?
Правильные
Неправильные
Фрагменты программы
Значения двух массивов A[1..100] и B[1..100] задаются с помощью следующего фрагмента программы:
Сколько элементов массива B будут иметь положительные значения?
Целочисленный массив
Имеется описание одномерного целочисленного массива с индексами от 0 до 10 и фрагменты трех программ, в которых массив сначала заполняется, а потом изменяется. Определите соответствие между фрагментами программ и результатами их работы.
1 2 3 4 5 6 5 4 3 2 1
10 9 8 7 6 5 6 7 8 9 10
11 10 9 8 7 6 7 8 9 10 11
Алгоритмы обработки массивов
Расставьте строки программы в правильном порядке.
var a:array[1..100] of integer
Алгоритмы обработки массивов
Обработка массивов
Результат работы программы
В массиве Dat хранятся данные измерений среднесуточной температуры за 10 дней в градусах (Dat[1] — данные за первый день, Dat[2] — за второй и т. д.). Определите, какое число будет напечатано в результате работы следующей программы.
Dat: array[1..10] of integer;
if Dat[k] > 3 then m := m+1;
Значение переменной s
В программе описан одномерный целочисленный массив с индексами от 0 до n. Известно, что в массиве есть несколько элементов с максимальным значением. Дан фрагмент программы:
if A[i] > A[j] then j:= i;
Чему будет равно значение переменной s после выполнения этого фрагмента программы?
значению максимального элемента
количеству элементов в массиве A, имеющих максимальное значение
индексу первого элемента в массиве A, имеющего максимальное значение
индексу последнего элемента в массиве A, имеющего максимальное значение
Одномерный целочисленный массив
Выполнение программ
В программе описан одномерный целочисленный массив с индексами от 1 до 10, элементы которого вычисляются по формуле:
Ниже представлен фрагмент программы, обрабатывающей данный массив:
for i := 1 to n do begin
Какие (одно или несколько) из представленных ниже чисел будут встречаться в массиве после выполнения программы два и более раз?
Элементы массива
В программе описан одномерный целочисленный массив A с индексами от 0 до 10. Ниже представлен фрагмент этой программы, в котором значения элементов массива сначала задаются, а затем меняются.