Контрольная по ОКП 10 вариант

Министерство образования Республики Беларусь

Учреждение образования

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Контрольная работа по курсу

"ОСНОВЫ КОНСТРУИРОВАНИЯ ПРОГРАММ"

вариант № 10

Сплендер Елена Игоревна

Группа № 902322, шифр № 10

Адрес: 220092, город Минск

улица Одоевского, дом № 56, кв. № 8

e-mail: [e-mail]

Минск, 2010

Определение алгоритма. Свойства алгоритмов. Способы описания алгоритма. Базовые структуры блок-схем. Структурированные блок-схемы и их построение. Линейные и разветвляющиеся структуры. Циклические структуры. Типы циклов. Предопределенные процессы. Рекурсия.

Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi – латинского написания имени Мухаммеда аль-Хорезми (787-850), выдающегося математика средневекового Востока. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение столбиком, деление уголком многозначных чисел – вот первый алгоритм в математике. Правила алгебраических преобразований, способы вычисления корней также можно отнести к математическим алгоритмам.

Алгоритм – это конечная последовательность точно сформулированных правил, формальное исполнение которых позволяет за конечное время получить искомый результат, основываясь на варьируемых исходных данных.

Свойства алгоритмов

1. Понятность алгоритма – все действия, описанные в алгоритме, должны быть понятны исполнителю. Исполнитель должен уметь их выполнять, т.е. эти действия должны входить в набор его действий. Т.о., предполагается, что исполнитель всегда знает, как использовать указания алгоритма.

2. Массовость алгоритма – каждый алгоритм предполагает наличие некоторых исходных данных и приводит к получению определенного искомого результата. Массовость алгоритма состоит в том, что алгоритм служит не для решения какой-либо одной конкретной задачи, а для решения целого класса однотипных задач путем варьирования исходных данных.

3. Определенность алгоритма – каждое действие алгоритма должно быть четко определено и однозначно выполнено, не оставляя места произволу. Алгоритм может быть сообщен другому исполнителю, и будет в точности выполнен.

4. Конечность алгоритма – т.е. выполнение алгоритма завершается после конечного числа шагов.

5. Дискретность – исполнение алгоритма должно распадаться на выполнение отдельных шагов. Выполнение следующего шага происходит только после выполнения предыдущего шага.

6. Результативность алгоритма – т.е. завершение алгоритма за конечное число шагов и получение искомого результата. Сообщение о том, что алгоритм не имеет решения, тоже является результатом.

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

Процедура подготовки и решения задачи на ЭВМ - достаточно сложный и трудоемкий процесс, состоящий из следующих этапов:

1. Анализ задачи;

2. Разработка и обоснование алгоритма;

3. Выбор и обоснование наборов тестов;

4. Описание разрабатываемых алгоритмов;

5. Выбор представления данных;

6. Кодирование программы(написание программы на языке программирования);

7. Тестирование и отладка;

8. Составление отчета;

Анализ - это исследование объектов или явлений, путем изучения составляющих его элементов.

Анализ задачи позволяет установить:

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

Выделить основные решения между входными и выходными данными.

Выделить модули необходимые для выполнения задачи и определить методы их решений.

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

Математическая постановка задачи дает ответ на 4 вопроса:

1. Что дано?

2. Что требуется?

3. Какие результаты будут считаться правильными?

4. Какие данные будут считаться допустимыми?

В разделе Дано - Перечисляются все исходные данные.

В разделе Требуется - Перечисление всех выходных данных с указанием их названий и математического обозначения.

В разделе 3 - Устанавливается система математических утверждений, связывающая входные и выходные данные с объяснением каждой записи.

В разделе 4 - Устанавливается система математических утверждений, накладывающих ограничения на область допустимых исходных данных.

Сценарий работы программы

Сценарий представляет собой описание внешних формул при выполнении программы.

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

Требования к сценарию:

1. Простота, т.е.:

2. подсказка на экране

3. сложно сделать ошибку

4. фиксация кадра - смена кадра должна происходить не сразу

5. обычно любая операция должна выполняться после запроса

6. В сценарии описываются:

7. форма ввода исходных данных

8. форма вывода результатов

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

Пример:

Сценарий программы нахождения наиболее удаленных точек.

1. На экран выводится: Введите общее количество точек

2. В ответ пользователь вводит число N

3. N раз на экране повторяется:

Введите координаты i-ой точки x="

Ввод координаты Xi;

К выведенной строке дописывается Y=

Ввод Yi

На экране выводится наиболее удаленные друг от друга точки с координатами (<Xa>,<Ya>) и (<Xb>,<Yb>)

Данный сценарий не включает контроля ограничения на входные данные.

Выбор представления данных (ВПД)

ВПД - является одним из важных этапов представления программы. В одних случаях ВПД является решающим и определяет алгоритм. Данные можно разделить на три типа:

1. Входные данные

2. Промежуточные

3. Выходные данные

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

Для описания алгоритмов существует множество способов. Основные способы описания следующие:

- словесный;

- алгоритмический язык;

- схема;

- псевдокод.

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

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

Основные блоки, используемые при изображении схемы программы:

Блок, обозначающий начало или конец алгоритма.

Функциональный блок.

Логический блок.

Блок, обозначающий операции ввода-вывода.

Изображение цикла

Базовые алгоритмические структуры. Используя исходные элементы блок-схем можно собрать более крупные кирпичики, которые называют базовыми структурами. Базовые структуры (конструкции):

- следование;

- ветвление (полное и не полное);

- повторение (цикл с предусловием или постусловием);

- вход;

-выход.

Каждая базовая структура имеет один вход и один выход. Схемы основных базовых алгоритмических структур:

Следование Повторение (Цикл )

Ветвление (полное)

Выбор (оператор 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. Это необходимо для того, чтобы не обращать к элементам, которые уже были рассмотрены: A₁₁, A_1N, A_N,1 и A_N,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.