Верификация программ. Алгоритм вычисления 10-ой степени числа (Контрольная работа № 15)

Алтайский краевой детско-юношеский центр

Алтайский государственный технический университет им. И. И. Ползунова

Краевая заочная школа НОУ, секция информатики и компьютерной математики

Первый год обучения. Тема: Верификация программ.

Контрольная работа №15.

Верификация - это процесс доказательства того, что программа удовлетворяет или не удовлетворяет требованиям такого рода.

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

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

Задача: вычислить Х

Дано: Х - исходное число

Требуется: Y - степень числа

Связь: Y= Х

Результаты: V1=X*X

V2=V1*V1

V3=V2*X

Y=V3*V3

При любом х.

АЛГ "Степень числа"

АРГ X: вещ

РЕЗ Y: вещ

НАЧ

V:=X*X

V:=V*V

V:=V*X

Y:=V*V

КОН

Утверждение: при любом аргументе х конечное значение, вычисленное данным алгоритмом, будет равно

Y= X.

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

Y=V3*V3=(V3)= (V2*X)= (V1*V1*X)= ((V1)*X )= ((X*X)*X )= (X)=X.

Что и требовалось доказать.

Задания.

№1. Выясните, являются ли правильными следующие алгоритмы и докажите правильность или неправильность.

АЛГ "Вычисление У=Х/(1+ Х)"

АРГ X: вещ

РЕЗ Y: вещ

НАЧ

Y:= Х

Y:=V/(1+V)

КОН

АЛГ "Вычисление min (X[1]…X[n])"

АРГ n: цел

X[1:n]: вещ

РЕЗ min: вещ

НАЧ

р:=1

ДЛЯ к ОТ 1 ДО n

НЦИКЛ

ЕСЛИ X[к]<Х[р] ТО р:=к

КЦИКЛ

min:= X[р]

КОН

№2. Составьте алгоритм определения количества целых чисел среди N чисел.

Докажите его правильность.

№3. Составьте алгоритм и программу определения третьей стороны треугольника, его площади и радиуса вписанной окружности, если даны две стороны треугольника и угол между ними. Докажите его правильность.

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

№4. "Кто виноват?"

По обвинению в ограблении перед судом предстали Иванов, Петров, Сидоров.

Следствие установило следующее:

1) Если Иванов не виновен или Петров виновен, то Сидоов виновен;

2) Если Иванов не виновен, то Сидоров не виновен.

Виновен ли Иванов?

Если ты решил эту задачу, то принимай наши поздравления. Желаем дальнейших успехов!