Контрольная по ОКП 10 вариант
.docМинистерство образования Республики Беларусь
Учреждение образования
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Контрольная работа по курсу
"ОСНОВЫ КОНСТРУИРОВАНИЯ ПРОГРАММ"
вариант № 10
Сплендер Елена Игоревна
Группа № 902322, шифр № 10
Адрес: 220092, город Минск
улица Одоевского, дом № 56, кв. № 8
e-mail: splender_elena@mail.ru
Минск, 2010
Определение алгоритма. Свойства алгоритмов. Способы описания алгоритма. Базовые структуры блок-схем. Структурированные блок-схемы и их построение. Линейные и разветвляющиеся структуры. Циклические структуры. Типы циклов. Предопределенные процессы. Рекурсия.
Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi – латинского написания имени Мухаммеда аль-Хорезми (787-850), выдающегося математика средневекового Востока. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение столбиком, деление уголком многозначных чисел – вот первый алгоритм в математике. Правила алгебраических преобразований, способы вычисления корней также можно отнести к математическим алгоритмам.
Алгоритм – это конечная последовательность точно сформулированных правил, формальное исполнение которых позволяет за конечное время получить искомый результат, основываясь на варьируемых исходных данных.
Свойства алгоритмов
-
Понятность алгоритма – все действия, описанные в алгоритме, должны быть понятны исполнителю. Исполнитель должен уметь их выполнять, т.е. эти действия должны входить в набор его действий. Т.о., предполагается, что исполнитель всегда знает, как использовать указания алгоритма.
-
Массовость алгоритма – каждый алгоритм предполагает наличие некоторых исходных данных и приводит к получению определенного искомого результата. Массовость алгоритма состоит в том, что алгоритм служит не для решения какой-либо одной конкретной задачи, а для решения целого класса однотипных задач путем варьирования исходных данных.
-
Определенность алгоритма – каждое действие алгоритма должно быть четко определено и однозначно выполнено, не оставляя места произволу. Алгоритм может быть сообщен другому исполнителю, и будет в точности выполнен.
-
Конечность алгоритма – т.е. выполнение алгоритма завершается после конечного числа шагов.
-
Дискретность – исполнение алгоритма должно распадаться на выполнение отдельных шагов. Выполнение следующего шага происходит только после выполнения предыдущего шага.
-
Результативность алгоритма – т.е. завершение алгоритма за конечное число шагов и получение искомого результата. Сообщение о том, что алгоритм не имеет решения, тоже является результатом.
Пример. Дано трехзначное число. Найти сумму его цифр. С этой задачей каждый справится очень быстро. Суть программирования состоит в том, чтобы научить формального исполнителя – компьютер, решить эту задачу.
Процедура подготовки и решения задачи на ЭВМ - достаточно сложный и трудоемкий процесс, состоящий из следующих этапов:
-
Анализ задачи;
-
Разработка и обоснование алгоритма;
-
Выбор и обоснование наборов тестов;
-
Описание разрабатываемых алгоритмов;
-
Выбор представления данных;
-
Кодирование программы(написание программы на языке программирования);
-
Тестирование и отладка;
-
Составление отчета;
Анализ - это исследование объектов или явлений, путем изучения составляющих его элементов.
Анализ задачи позволяет установить:
Что является входом и выходом будущего алгоритма, при этом следует явно описывать класс входных данных.
Выделить основные решения между входными и выходными данными.
Выделить модули необходимые для выполнения задачи и определить методы их решений.
Класс входных данных определяется наложением ограничений. Определение отношений между входными и выходными данными определяется математической постановкой решаемой задачи. Содержание постановки задачи - это определение правильности конечных результатов, т.е. чем содержательней и правильнее поставим задачу, тем больше вероятность, что программа будет написана правильно, т.е. она будет делать то, что от нее требуется.
Математическая постановка задачи дает ответ на 4 вопроса:
-
Что дано?
-
Что требуется?
-
Какие результаты будут считаться правильными?
-
Какие данные будут считаться допустимыми?
В разделе Дано - Перечисляются все исходные данные.
В разделе Требуется - Перечисление всех выходных данных с указанием их названий и математического обозначения.
В разделе 3 - Устанавливается система математических утверждений, связывающая входные и выходные данные с объяснением каждой записи.
В разделе 4 - Устанавливается система математических утверждений, накладывающих ограничения на область допустимых исходных данных.
Сценарий работы программы
Сценарий представляет собой описание внешних формул при выполнении программы.
Сценарий должен разрабатываться после анализа и постановки задачи, в некоторых случаях после алгоритма.
Требования к сценарию:
-
Простота, т.е.:
-
подсказка на экране
-
сложно сделать ошибку
-
фиксация кадра - смена кадра должна происходить не сразу
-
обычно любая операция должна выполняться после запроса
-
В сценарии описываются:
-
форма ввода исходных данных
-
форма вывода результатов
-
контроль прохождения программы и промежуточного результата при отладке и если это необходимо
Пример:
Сценарий программы нахождения наиболее удаленных точек.
-
На экран выводится: Введите общее количество точек
-
В ответ пользователь вводит число N
-
N раз на экране повторяется:
Введите координаты i-ой точки x="
Ввод координаты Xi;
К выведенной строке дописывается Y=
Ввод Yi
На экране выводится наиболее удаленные друг от друга точки с координатами (<Xa>,<Ya>) и (<Xb>,<Yb>)
Данный сценарий не включает контроля ограничения на входные данные.
Выбор представления данных (ВПД)
ВПД - является одним из важных этапов представления программы. В одних случаях ВПД является решающим и определяет алгоритм. Данные можно разделить на три типа:
-
Входные данные
-
Промежуточные
-
Выходные данные
Входные и выходные данные определяются интерфейсом с пользователем. Интерфейс - внешнее представления данных. Промежуточные данные определяются алгоритмом. Входные и выходные данные могут быть представлены в виде внешней и внутренней формулы. Внешние данные определяются удобством взаимодействия пользователя с программой, а внутренние удобством для программирования.
Для описания алгоритмов существует множество способов. Основные способы описания следующие:
- словесный;
- алгоритмический язык;
- схема;
- псевдокод.
Под схемой программы будем понимать графическое представление последовательности шагов алгоритма, которое наглядно показывает очередность и взаимосвязь операций, осуществляемых в алгоритме на каждом его шаге.
Иначе говоря, схема программы служит для графического изображения структуры алгоритма. Любая схема содержит набор геометрических фигур или блоков. Последовательность действий указывается с помощью стрелок, соединяющих отдельные блоки.
Основные блоки, используемые при изображении схемы программы:
Блок, обозначающий начало или конец алгоритма.
Функциональный блок.
Логический блок.
Блок, обозначающий операции ввода-вывода.
Изображение цикла
Базовые алгоритмические структуры. Используя исходные элементы блок-схем можно собрать более крупные кирпичики, которые называют базовыми структурами. Базовые структуры (конструкции):
- следование;
- ветвление (полное и не полное);
- повторение (цикл с предусловием или постусловием);
- вход;
-выход.
Каждая базовая структура имеет один вход и один выход. Схемы основных базовых алгоритмических структур:
Следование Повторение (Цикл )
Ветвление (полное)
Выбор (оператор switch)
Дан массив А состоящий из k целых положительных чисел. Записать все четные по значению элементы массива А в массив В.
Решение задачи заключается в следующем. Последовательно перебираются элементы массива А. Если среди них находятся четные, то они записываются в массив В. На рисунке видно, что первый четный элемент хранится в массиве А под номером три, второй и третий под номерами пять и шесть соответственно, а четвертый под номером восемь. В массиве В этим элементам присваиваются совершенно иные номера. Поэтому для их формирования необходимо определить дополнительную переменную. Операция, выполняемая в блоке 2, означает, что в массиве может не быть искомых элементов. Если же условие в блоке 5 выполняется, то переменная m увеличивается на единицу, а значение элемента массива А записывается в массив В под номером m (блок 6). Условный блок 7 необходим для того, чтобы проверить выполнилось ли хотя бы раз условие поиска (блок 5).
Вычислить количество положительных элементов квадратной матрицы, расположенных по ее периметру и на диагоналях. Напомним, что в квадратной матрице число строк равно числу столбцов.
Для обращения к элементам главной диагонали вспомним, что номера строк этих элементов всегда равны номерам столбцов. Поэтому, если параметр i изменяется циклически от 1 до N, то Ai,i - элемент главной диагонали. Воспользовавшись свойством, характерным для элементов побочной диагонали получим: i+j-1 = n > j = n-i+1, следовательно, для i=1,2,…,n элемент Аi,n-i+1 - элемент побочной диагонали. Элементы, находящиеся по периметру матрицы записываются следующим образом: А1,i - первая строка, АN,i - последняя строка и соответственно Аi,1 - первый столбец, Аi,N - последний столбец.
В блоке 1 организуется цикл для обращения к диагональным элементам матрицы. Причем в блоках 2-3 подсчитывается количество положительных элементов на главной диагонали, а в блоках 5-6 на побочной. Цикл в блоке 6 задает изменение параметра i от 2 до N-1. Это необходимо для того, чтобы не обращать к элементам, которые уже были рассмотрены: A11, A1N, AN,1 и AN,N. Блоки 7-8 подсчитывают положительные элементы в первой строке, 9 и 10 - в последней строке, 11 и 12 - в первом столбце, а 13 и 14 в последнем. Блок 15 проверяет, не был ли элемент, находящийся на пересечении диагоналей, подсчитан дважды. Напомним, что это могло произойти только в том случае, если N - нечетное число и этот элемент был положительным. Эти условия и проверяются в блоке 16, который уменьшает вычисленное количество положительных элементов на единицу.
|
|
Даны длины катетов прямоугольного треугольника (a,b). Составить алгоритм, определяющий его гипотенузу, площадь, радиус описанной окружности. (линейные алгоритмы).
program triangle;
var
a,b,c,s,r : real;
begin
writeln('Программа вычисляет гипотенузу, площадь и радиус описанной окружности'+
'прямоугольного треугольника по длинам катетов');
repeat
write('Введите длины катетов прямоугольного треугольника ');
readln(a,b);
if ((a<=0)or(b<=0)) then
writeln('Ошибка! Длины катетов не могут быть нулевыми или '+
'отрицательными. Повторите ввод.');
until (a>0)and(b>0);
c := sqrt(a*a+b*b);
r:=a*b*c/4*s;
writeln('Гипотенуза этого треугольника = ', c:8:3);
writeln('Площадь этого треугольника = ', (0.5*a*b):8:3);
writeln('Радиус описанной окружности = ', r:8:3);
writeln('Нажмите [Enter] для завершения программы');
readln;
end.
Определить, является ли треугольник со сторонами a, b и c равнобедренным.(разветвляющиеся алгоритмы).
program triangle;
const EPSILON = 1E-6;
var
a,b,c : real;
begin
writeln( 'Введите длины сторон треугольника');
read (a,b,c);
begin
if (b=c) and (a=b) and (a=c) then
write ('Треугольник является равнобедренным');
begin
else
if (a+b<=c) or (a+c<=b) or (b+c<=a) then
writeln ('Треугольника со сторонами ', a,b,c, 'не существует');
end;
end.
Алгоритм Евклида. Даны натуральные числа N и M. Найти наибольший общий делитель (НОД) и наименьшее общее кратное (НОК).(задача целочисленной арифметики).
program Evklid;
var
a, b: integer;
function NOD_Evklid (a, b : integer) : integer;
var
r : integer;
begin
if ((a=0)or(b=0)) then begin
NOD_Evklid := abs(a+b);
exit;
end;
r := a-b*(a div b);
while r <> 0 do begin
a := b;
b := r;
r := a-b*(a div b);
end;
NOD_Evklid := b;
end;
begin
writeln('Программа находит максимальный общий делитель '+
'двух заданных целых чисел, используя алгоритм Евклида');
write('Введите первое число ');
readln(a);
write('Введите второе число ');
readln(b);
writeln('НОД(',a,',',b,') = ',NOD_Evklid(abs(a),abs(b)));
writeln('Нажмите [Enter] для завершения программы');
readln;
end.
program Evklid2;
var
a, b: integer;
function NOD_Evklid (a, b : integer) : integer;
var
r : integer;
begin
if ((a=0)or(b=0)) then begin
NOD_Evklid := abs(a+b);
exit;
end;
{оба числа ненулевые}
r := a-b*(a div b);
while r <> 0 do begin
a := b;
b := r;
r := a-b*(a div b);
end;
NOD_Evklid := b;
end;
function NOK_Evklid (a, b : integer) : integer;
begin
NOK_Evklid := (a*b) div NOD_Evklid(a,b);
end;
begin
writeln('Программа находит наименьшее общее кратное '+
'двух заданных целых чисел, используя алгоритм Евклида '+
'для нахождения НОД');
write('Введите первое число ');
readln(a);
write('Введите второе число ');
readln(b);
writeln('НОК(',a,',',b,') = ',NOK_Evklid(abs(a),abs(b)));
writeln('Нажмите [Enter] для завершения программы');
readln;
end.