ЛАБОРАТОРНАЯ РАБОТА № 8

ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ

ВПРОЦЕССЕ ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ ФОРМИРУЮТСЯ СЛЕДУЮЩИЕ УМЕНИЯ И НАВЫКИ:

1.Составлять алгоритмы решения задачи.

2.Записывать алгоритмы с помощью блок-схем.

3.Решать задачи с линейными алгоритмами.

4.Решать задачи с разветвляющимися алгоритмами.

5.Решать задачи с циклическими алгоритмами.

6.Создавать и обрабатывать массивы данных.

7.Использовать процедуры.

8.Программировать на языке высокого уровня.

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1.Дайте определение алгоритма.

2.Для чего нужны блок-схемы?

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

4.Привести пример разветвляющегося алгоритма.

5.Привести пример циклического алгоритма с предусловием.

6.Привести пример циклического алгоритма с постусловием.

7.Как работают команды ветвления?

8.В чем заключается компиляция исходного модуля?

9.В чем разница между транслятором и компилятором?

10.Перечислить этапы решения задач на ЭВМ.

109

БЛОК ОСНОВНЫХ ЗАДАНИЙ

ЗАДАНИЕ 1. ЛИНЕЙНЫЕ АЛГОРИТМЫ

НАЧАЛЬНЫЙ УРОВЕНЬ

1. Записать словесный алгоритм нахождения значения выражения:

a * b − a +c c

2. Построить блок-схему алгоритма.

БАЗОВЫЙ УРОВЕНЬ

1.Записать словесный алгоритм определения значения переменных a и b после вычисления выражения a := 15 div (16 mod 7)

2.Построить блок-схему алгоритма.

ПОВЫШЕННЫЙ УРОВЕНЬ

1.Записать словесный алгоритм определения значения переменных a и b после вычисления выражения b := 34 mod a*5 – 29 mod 5*2.

2.Построить блок-схему алгоритма.

СПРАВОЧНЫЙ МАТЕРИАЛ

Алгоритм указывает последовательность действий по переработке исходных данных в результаты.

Команды – отдельные указания исполнителю на каждом шаге алгоритма.

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

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

Действия в арифметическом выражении выполняются слева направо с соблюдением приоритета операций (по убыванию):

1.действия в скобках;

2.вычисление функций;

3.NOT;

4.*, /, DIV, MOD, AND;

5.+, -, OR;

6.=, <>, <, >, <=, >=.

110

При одинаковом приоритете, выполняется операция, стоящая левее. Алгоритмы можно представлять как некоторые жесткие структуры,

состоящие из отдельных базовых элементов.

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

Величины делятся на постоянные, значения которых остаются неизменными в процессе исполнения алгоритма, и переменные.

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

Рис. 1 Функциональный блок простой команды

Команда следования образуется из последовательности команд. Любой алгоритм может быть построен с использованием только

базовых конструкций: следования, развилки и цикла.

Построение алгоритма может происходить двумя путями:

1.Базовые элементы могут соединяться в последовательность, образуя конструкцию следования.

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

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

Пример. Вычислить площадь квадрата. Исходные данные: а – сторона квадрата. Выходные данные: S – площадь.

Ввод а

S := а * а

Вывод S

Для работы с целыми числами в языках программирования используются стандартные функции div – деление нацело и mod – остаток от деления нацело.

Результатом выполнения операции x div y будет целое число, округленное по направлению к 0, например, 17 div 8 = 2; 3 div 5 = 0.

111

Результатом выполнения операции x mod y = x – (x div y)*y будет целое число – остаток от деления нацело x на y, например, 17 mod 8 = 1; 3 mod 5 = 3.

Операции *, /, div, mod имеют одинаковый приоритет.

ЗАДАНИЕ 2. РАЗВЕТВЛЯЮЩИЕСЯ АЛГОРИТМЫ

НАЧАЛЬНЫЙ УРОВЕНЬ

1.Записать словесный алгоритм проверки числа при вводе. Вывести результат проверки в виде текста «число не отрицательное» или «число отрицательное».

2.Построить блок-схему алгоритма.

БАЗОВЫЙ УРОВЕНЬ

1. Записать словесный алгоритм нахождения значения выражения:

2. Построить блок-схему алгоритма.

ПОВЫШЕННЫЙ УРОВЕНЬ

1.Записать словесный алгоритм проверки числа при вводе. Вывести результат проверки в виде текста «отлично» для диапазона 75-100, «хорошо» для диапазона 50-74, «удовлетворительно» для диапазона 25-49.

2.Построить блок-схему алгоритма.

СПРАВОЧНЫЙ МАТЕРИАЛ

Составные команды образуются из простых команд и команды проверки условий.

С помощью команды ветвления (рис. 2-а) осуществляется выбор одного из двух возможных действий в зависимости от условия: если условие соблюдено, то выполняется действие 1, в противном случае – действие 2.

а) развилка б) коррекция

Рис. 2 Функциональные блоки команды ветвления

112

Под действием понимается простая, или составная команда. Существует команда ветвления в сокращенной форме (рис. 2-б).

Пример. Проверить два числа при вводе. Если первое число меньше 100, то проверить второе число. Если второе число окажется больше 10 – выполнить умножение исходных чисел. В противном случае – сложение. Вывести результат.

Приведенному фрагменту алгоритма соответствует фрагмент блок-

схемы

ЗАДАНИЕ 3. ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ (СЧЕТНЫЙ ЦИКЛ)

НАЧАЛЬНЫЙ УРОВЕНЬ

1.Используя счетный цикл выполнить сложение пяти введенных чисел.

2.Составить словесный алгоритм.

3.Построить блок-схему алгоритма.

БАЗОВЫЙ УРОВЕНЬ

1.Используя счетный цикл вычислить факториал числа (N!= 1*2*3*…*N).

2.Составить словесный алгоритм.

3.Построить блок-схему алгоритма.

ПОВЫШЕННЫЙ УРОВЕНЬ

1.Используя счетный цикл вычислить значение числа 3 в десятой степени.

2.Составить словесный алгоритм.

3.Построить блок-схему алгоритма.

СПРАВОЧНЫЙ МАТЕРИАЛ

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

113

Пример. Напечатать 10 символов *. Блок-схема и фрагмент алгоритма.

ЗАДАНИЕ 4. ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ (УСЛОВНЫЙ ЦИКЛ)

НАЧАЛЬНЫЙ УРОВЕНЬ

1. Построить блок-схему для фрагмента программы.

Program pr4; Var n: integer; Begin

n:=1;

while n<10 do begin

If n=1 then writeln(n,’ год’)

Else If n<5 then writeln(n,’ года’)

Else If n<9 then writeln(n,’ лет’);

n:=n+1;

End;

End.

БАЗОВЫЙ УРОВЕНЬ

1. Дан фрагмент алгоритма, в котором переменные a, b, c имеют тип «строка», переменные i, k – тип «целое». Значения строк записываются в одинарных кавычках, например, b:= ‘память’.

а:= ‘ИНФОРМАТИКА’ i:= Длина(а) – 5

k:= 1 b:=’A’

пока i > 2 нц

с:= Извлечь(a,i) b:= Склеить(с,b) i:= i – k

кц

114

Используются функции:

Длина(а) — возвращает количество символов в строке а (тип «целое»). Извлечь(a,i) — возвращает i-ый символ в строке а, начиная слева (тип

«строка»).

Склеить(a,b) — возвращает строку, в которой записаны подряд символы строки а, затем строки b.

2.Определить значение переменной b после завершения работы алгоритма.

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

ПОВЫШЕННЫЙ УРОВЕНЬ

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

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

СПРАВОЧНЫЙ МАТЕРИАЛ

Команда повторения с предусловием (рис. 3-а). Исполнение команды состоит в том, что сначала проверяется условие, и если оно соблюдено, то выполняется действие. После этого снова проверяется условие. Выполнение цикла завершается, когда условие перестает соблюдаться.

Команда повторения с постусловием (рис. 3-б). Условие проверяется после выполнения команды. Повторное выполнение команды происходит, если условие не соблюдено.

Рис. 3 Функциональные блоки команды повторения

Замечание. Действие, выполняемое в цикле, должно влиять на условие.

115

ЗАДАНИЕ 5. ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ВЫСОКОГО УРОВНЯ

1.Для заданий 1-4 в соответствии с уровнями составить программы.

2.Набрать текст программ в среде АВСPascal (Free Pascal).

3.Сохранить текст программ на диске С: в каталоге \TEMP.

4.Произвести компиляцию и отладку программ.

5.Выполнить программы в режиме тестирования.

СПРАВОЧНЫЙ МАТЕРИАЛ

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

Компиляция (интерпретация) – процедура перевода исходного модуля (ИМ) в последовательность команд ЭВМ.

Компилятор транслирует весь текст ИМ в машинный (объектный) код за один непрерывный процесс.

Исполняемый файл – это файл, который может быть выполнен компьютером без предварительной трансляции.

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

Интерпретатор выполняет ИМ программы в режиме «оператор за оператором», переводя каждый оператор языка программирования в машинные команды.

Для решения задачи на ЭВМ необходимо выполнить такие этапы как:

1.Формализация данных (определяются исходные данные).

2.Создание математической модели (модель решения).

3.Детальное описание алгоритма (блок-схема).

4.Реализация на языке программирования.

5.Отладка (устранение явных некорректных ситуаций реализации алгоритма).

6.Тестирование программы (устранение скрытых и явных недостатков исходной задачи).

7.Анализ результатов работы (исследование полученных результатов).

Компиляция исходного модуля – Ctrl+F9. Выполнение программы – F9.

Возврат результата на экран – Alt+F5.

116

БЛОК ВАРИАТИВНЫХ ЗАДАНИЙ

ЗАДАНИЕ 1. ИСПОЛЬЗОВАНИЕ ПРОЦЕДУР

1. Дана программа для вычисления площади различных геометрических фигур.

program pr1; uses wincrt;

var a,b,s:integer; p:real; begin

{Вычисление площади прямоугольного треугольника} writeln;

write('Введите стороны a, b: '); readln(a,b);

s:= 0.5*a*b;

writeln('площадь прямоугольного треугольника:',s:2:1);

{Вычисление площади равностороннего треугольника} writeln;

write('Введите стороны a, b: '); readln(a,b);

p:=(a+a+b)/2;

s:= sqrt(p*(p-a)*(p-a)*(p-b));

writeln('площадь равностороннего треугольника: ',s:2:2);

{Вычисление площади прямоугольника} writeln;

write('Введите стороны a, b: '); readln(a,b);

s:=a*b;

writeln('площадь прямоугольника:',s);

end.

2.Для повторяющихся действий написать процедуру.

3.Модифицировать программу, вставив обращение к процедуре для выполнения повторяющихся действий.

СПРАВОЧНЫЙ МАТЕРИАЛ

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

пошаговой детализации или метод “сверху вниз”. При построении алгоритма по принципу «сверху вниз» задача разбивается на более простые подзадачи. Если для какой-то подзадачи уже построен алгоритм, то он может быть включен в разрабатываемый алгоритм.

117

Готовые алгоритмы, целиком включаемые в состав разрабатываемого алгоритма, называют вспомогательными или подчиненными алгоритмами.

Подпрограммы — вспомогательные алгоритмы, записанные на языках программирования.

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

procedure имя_процедуры;

var {описание локальных переменных процедуры} begin

{тело процедуры}

end; {конец процедуры} begin

{тело главной программы} end. {конец программы}

Вызов процедуры для последующего выполнения записывается в теле главной программы.

Пример 1. Создание таблицы 5х1 шириной 10 знаков средствами псевдографики.

Program tabl;

var i, k:integer; procedure line; var i:integer; begin

for i:=1 to 10 do write('*'); writeln;

end;

begin {начало программы} line;

for k:=1 to 5 do begin

write('*');

for i:=1 to 8 do write(' '); write('*');

line;

end;

end.

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

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

118

подпрограммы, и фактические параметры – выражения, задающие конкретные значения при обращении к подпрограмме.

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

Пример 2. Передача параметров в процедуру.

Проверка введенного пользователем целого числа на знак. Если число отрицательное, то выдать сообщение и прервать выполнение программы.

Program pr2; var a:integer;

procedure znak(x:integer); begin

if x<0 then writeln(‘число отрицательное’); halt; {прерывание программы}

end;

begin

write(‘Введите число: ’); readln(a);

znak (a); end.

Пример 3. Возврат параметров из процедуры.

Проверка введенного пользователем целого числа на знак. Если число отрицательное, то выдать сообщение и возвратить модуль числа.

Program pr2;

var a,b: integer;

procedure znak (var x:integer):integer; begin

if x<0 then begin writeln(‘число отрицательное’); x:=abs(x);

end;

begin

write(‘Введите число: ’); readln(a);

znak (a); b:=sqrt(a);

writeln(‘корень из введенного числа = ’,b); end.

119

ЗАДАНИЕ 2. СОЗДАНИЕ ОДНОМЕРНЫХ МАССИВОВ

1. Набрать и выполнить программу ввода целочисленных данных в векторстроку размерностью не более 10 элементов.

Program pr1;

Var n, I: integer;

X: array [1..10] of integer; Begin

Write(‘Введите размерность массива’); Readln(n);

Writeln(‘Введите элементы массива через пробел’); For i:=1 to n do Read(x[i]);

Writeln(‘Получена вектор-строка’); For i:=1 to n do write(x[i]);

End.

2. Написать, набрать и выполнить программу ввода целочисленных данных в вектор-столбец размерностью не более 10 элементов.

СПРАВОЧНЫЙ МАТЕРИАЛ

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

Объявление массива: <имя>:Array [n1..k1] [n2..k2] .. [nn..kn] of <тип>

Пример 1.

Одномерный массив х: array [1..5] of integer; Двумерный массив х: array [1..5,1..5] of integer;

Обращение к элементу массива: x[i], x[i,j].

ЗАДАНИЕ 3. СОЗДАНИЕ ДВУМЕРНЫХ МАССИВОВ

1. Набрать и выполнить программу ввода целочисленных данных в квадратную матрицу размерностью не более 5х5.

Program pr3;

Var n, I, j: integer;

X: array [1..5,1..5] of integer; Begin

Write(‘Введите размерность матрицы’); Readln(n);

Writeln(‘Введите элементы массива через пробел’); For i:=1 to n do

120

begin

For j:=1 to n do Read(x[i,j]); Readln;

End;

Writeln(‘Получена матрица’); For i:=1 to n do

begin

For j:=1 to n do write(x[i,j]); writeln;

End;

End.

ЗАДАНИЕ 4. ОБРАБОТКА ЭЛЕМЕНТОВ ДВУМЕРНОГО МАССИВА

1. Набрать и выполнить программу.

Задача. Ввести элементы двумерного массива размерностью не более 5х5. Умножить элементы второго столбца на 10. Вывести результат.

Program pr4;

Var n, m, I, j: integer;

X: array [1..5,1..5] of integer; Begin

Write(‘Введите размерность матрицы n- количество строк, m- количество столбцов: ’);

Readln(n, m);

Writeln(‘Введите элементы массива через пробел’); For i:=1 to n do

begin

For j:=1 to m do Read(x[I,j]); Readln;

End;

For i:=1 to n do x[I,2]:=x[I,2]*10; Writeln(‘Результат:’);

For i:=1 to n do begin

For j:=1 to m do write(x[I,j]); writeln;

End;

End.

2. Модифицировать программу обработки элементов двумерного массива. Задача. Ввести элементы двумерного массива размерностью не более 5х5. Умножить элементы второй строки на 10. Вывести результат.

121

СОДЕРЖАНИЕ

122