Лабораторная работа №7
Тема: Алгоритмы. Основы разработки алгоритмов. Блок-схемы алгоритмов.
Цель работы: Получить практические навыкиразработки алгоритмов решения вычислительных задач в виде блок-схем.
Краткие сведения из теории
Алгоритм - это точное предписание исполнителю совершить последовательность действий, направленных на достижение поставленной цели. Алгоритм, составленный для некоторого исполнителя, можно представить различными способами: с помощью графического или словесного описания, в виде псевдокодов, формул, или записанным на каком-либо языке программирования.
Наиболее популярным для решения задач на ЭВМ является графическая форма представления алгоритма в виде блок-схем. Графическое изображение алгоритма широко используется перед программированием задачи вследствие его наглядности, что облегчает процесс написания программы, ее корректировки при возможных ошибках.
Алгоритм любой сложности может быть представлен комбинацией трех базовых структур:
· линейная;
· разветвляющая (альтернатива);
· циклическая.
Характерной особенностью этих структур является наличие у них одного входа и одного выхода.
Базовая структура "линейная" (следование) означает, что несколько операторов должны быть выполнены последовательно друг за другом и только один раз за время выполнения данной программы (рис. 1). Под оператором понимается формальная запись команды для выполнения некоторого действия.
 | |||
 | |||
Рисунок 1- Базовая структура «Линейная»
Базовая структура "разветвляющая" обеспечивает, в зависимости от результата проверки условия (истинна или ложь), выбор одного из альтернативных путей работы алгоритма (рис. 2).
 |  |
Рисунок 2- Базовая структура «Разветвляющая»
Алгоритм, в состав которого входит базовая структура " альтернатива или разветвляющая", называется разветвляющимся.
Третья базовая структура "циклическая" обеспечивает повторное выполнение или, другими словами, циклическую работу операторов.
Различают три разновидности этой структуры:
· "цикл - пока" (рис. 3 а);
· "цикл - до" (рис. 3 в);
· Цикл с заданным числом повторений (рис. 3 с).
 | |||||
 | |||||
 | |||||
а) в) с)
а) – цикл - пока;
в) – цикл - до;
с) – цикл с заданным числом повторений.
Рисунок 3- Базовая структура «Циклическая»
Группа операторов, повторяющихся в цикле, называются телом цикла. Основное отличие структуры "цикл - пока" от структуры "цикл - до" заключается в том, что в первой структуре операторы тела цикла в зависимости от условия могут не выполняться совсем, тогда как в структуре "цикл - до" тело цикла будет выполняться хотя бы один раз. Можно заметить, что в структуре "цикл - пока" проверка выполнения условия осуществляется перед выполнением операторов тела цикла, а в структуре "цикл - до" - после прохождения тела цикла.
Цикл с заданным числом повторений обозначает повторение некоторых действий указанное число раз.
Циклы могут содержать внутри себя другие циклы. Такие структуры называются вложенными циклами. Алгоритмы, имеющие в своем составе базовую структуру "цикл", называются циклическими.
Реальные алгоритмы представляют собой совокупность всех рассмотренных базовых структур.
Основные свойства алгоритмов: дискретность, определенность, конечность, повторяемость и универсальность (массовость).
Дискретность означает, что выполнение алгоритма разбивается на последовательность законченных действий - шагов.
Определенность означает, что каждое правило алгоритма настолько четко и однозначно, что значения величин, получаемые на каком-либо шаге, однозначно определяются значениями величин, полученными на предыдущем шаге, и при этом точно известно какой шаг будет выполнен следующим.
Конечность (результативность) алгоритма предполагает, что его исполнение сводится к выполнению конечного числа шагов и всегда приводит к некоторому результату. Бесконечных алгоритмов не бывает.
Повторяемость алгоритма предполагает, что при многократных расчетах с одними и теми же исходными данными результат должен повторяться.
Массовость (универсальность) означает, что алгоритм решения задачи разрабатывается в общем виде так, чтобы его можно было применить для множества задач одного класса, различающихся лишь набором исходных данных.
При блок-схемном описании алгоритм изображается различными геометрическими фигурами (блоками), связанными по управлению линиями (направлениями потока) со стрелками. В блоках записывается последовательность действий, проверка выполнения условия, ввод или вывод данных и др. Для каждого действия предусмотрена своя геометрическая фигура. В таблице 1 представлены основные блоки и их назначение.
Таблица 1. Основные блоки
| Наименование | Обозначение | Функции |
| Процесс |  
| Выполнение операций, в результате которых изменяется значение, форма представления или расположение данных. |
| Ввод-вывод (данные) |   
| Ввод данных в программу, или отображение (вывод) результатов работы программы на экране дисплея. |
| Условие (решение) |   
| Выбор направления выполнения алгоритма в зависимости от некоторых переменных условий. |
| Модификация | 
| Отображает цикл. В блоке указываются начальное значение цикла, его шаг и условие окончания цикла. |
| Предопределённый (типовой) процесс | 
| Использование ранее созданных и отдельно написанных программ (подпрограмм). |
| Документ | 
| Вывод данных на бумажный носитель. |
| Пуск (начало) | 
| Начало процесса обработки данных (алгоритма). |
| Стоп (конец) | 
| Конец (завершение) процесса обработки данных (алгоритма). |
| Соединитель (узел) |   
| Указание связи между прерванными линиями, соединяющими блоки. N – номер связи. |
Содержание работы:
1. Выбрать вариант задания.
2. Изучить теоретическую часть.
3. Для каждого задания выполнить постановку задачи.
4. Разработать алгоритмы задач в виде блок-схем.
5. Составить описание блок-схем алгоритмов.
Содержание отчета:
1. Постановка задач.
2. Разработка алгоритмов в виде блок-схемы.
3. Описание блок-схем алгоритмов.
4. Ответы на контрольные вопросы
Варианты заданий:
Задание 1. Системы счисления.
| Вариант | Действия |
| 1. | Перевести целое десятичное число, введенное с клавиатуры, в двоичную систему счисления. |
| 2. | Перевести целое десятичное число, введенное с клавиатуры, в восьмеричную систему счисления. |
| 3. | Перевести целое десятичное число, введенное с клавиатуры, в шестнадцатеричную систему счисления. |
| 4. | Перевести целое двоичное число, введенное с клавиатуры, в десятичную систему счисления. |
| 5. | Перевести целое двоичное число, введенное с клавиатуры, в восьмеричную систему счисления. |
| 6. | Перевести целое двоичное число, введенное с клавиатуры, в шестнадцатеричную систему счисления. |
| 7. | Перевести целое восьмеричное число, введенное с клавиатуры, в десятичную систему счисления. |
| 8. | Перевести целое восьмеричное число, введенное с клавиатуры, в двоичную систему счисления. |
| 9. | Перевести целое восьмеричное число, введенное с клавиатуры, в шестнадцатеричную систему счисления. |
| 10. | Перевести целое шестнадцатеричное число, введенное с клавиатуры, в десятичную систему счисления. |
| 11. | Перевести целое шестнадцатеричное число, введенное с клавиатуры, в двоичную систему счисления. |
| 12. | Перевести целое шестнадцатеричное число, введенное с клавиатуры, в восьмеричную систему счисления. |
Задание 2. Измерение количества информации.
Вариант 1.
Текст занимает 3 страницы по 25 строк. В каждой строке записано по 60 символов. Сколько символов в используемом алфавите, если все сообщение содержит 1125 байт?
Вариант 2.
Письмо состояло из 30 строк. В каждой строке вместе с пробелами по 48 символов. Письмо содержало 900 байт информации. Какова мощность алфавита (количество символов), которым было написано письмо?
Вариант 3.
Цветное изображение на мониторе имеет 8 оттенков цвета. Размер изображения 10*15 см. Разрешение 300 точек на дюйм (1 дюйм = 2,5 см). Сколько Кбайт памяти требуется для хранения изображения в несжатом виде?
Вариант 4.
Для шифрования информации был использован код, состоящий из 64 различных знаков. Какое количество байт содержит шифровка, состоящая из 110 групп по 12 знаков в каждой группе?
Вариант 5.
В коробке находятся кубики трех цветов: красного, желтого и зеленого. Причем желтых в два раза больше красных, а зеленых на 6 больше чем желтых. Сообщение о том, что из коробки случайно вытащили желтый кубик, содержало 2 бита информации. Сколько было зеленых кубиков?
Вариант 6.
Студенты группы изучают один из трех языков: английский, немецкий или французский. Причем 12 студентов не учат английский. Сообщение, что случайно выбранный студент Петров изучает английский, несет log23 бит информации, а что Иванов изучает французский – 1 бит. Сколько студентов изучают немецкий язык?
Вариант 7.
Шифровка состояла из 36 групп символов по 6 символов в группе и содержала 81 байт информации. С помощью скольких различных знаков была закодирована шифровка?
Вариант 8.
Даны два текста, содержащих одинаковое количество символов. Первый текст состоит из алфавита мощностью 16 символов, а второй текст – из 256 символов. Во сколько раз информации во втором тексте больше, чем в первом?
Вариант 9.
В составе 16 вагонов, среди которых К – купейные, П – плацкартные и СВ – спальные. Сообщение о том, что ваш друг приезжает в СВ несет 3 бита информации. Определите, сколько в поезде вагонов СВ.
Вариант 10.
Ученики класса, состоящего из 21 человека, изучают немецкий или французский языки. Сообщение о том, что ученик A изучает немецкий язык, несет log23 бит информации. Сколько человек изучают французский язык?
Вариант 11.
Телеграфистка в течение пяти минут передавала информационное сообщение со скоростью 20 байт в секунду. Сколько символов содержало данное сообщение, если она использовала алфавит из 32 символов?
Вариант 12.
Для записи письма был использован алфавит мощностью в 16 символов.
Письмо состояло из 25 строк. В каждой строке вместе с пробелами было 64 символа. Сколько байт информации содержало письмо?
Задание для всех вариантов (творческое):
- Придумать задачу на тему «Измерение количества информации»;
- Составить блок-схему алгоритма.
Задачи для самостоятельного решения на тему «Измерение количества информации»:
Задача 1. Сколько информации несет сообщение о том, что было угадано число в диапазоне целых чисел от 684 до 811?
Задача 2. Какое наименьшее число символов должно быть в алфавите, чтобы при помощи всевозможных трёхбуквенных слов, состоящих их символов данного алфавита, можно было передать не менее 9 различных сообщений?
Задача 3. Световое табло состоит из лампочек, каждая из которых может находиться в двух состояниях («включено» или «выключено»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 50 различных сигналов?
Задание 3. Работа с координатами геометрических фигур.
Задача. Определить попадание точки, заданной координатами в треугольник, заданный координатами вершин.
- Решить задачу с использованием площадей треугольников;
- Составить блок-схему алгоритма;
- Решить задачу с использованием цвета заливки фигур;
- Составить блок-схему алгоритма;
- Решить задачу с помощью определения точки пересечения двух отрезков прямых линий;
- Составить блок-схему алгоритма.
На рис. 4 представлен демонстрационный пример решения задачи с использованием цвета заливки треугольника.
Рисунок 4- Решения задачи с использованием цвета заливки треугольника
Задание для всех вариантов (творческое):
- Придумать задачу на тему «Работа с координатами геометрических фигур»;
- Составить блок-схему алгоритма.
Задачи для самостоятельного решения на тему «Работа с координатами геометрических фигур»:
Задача 1. Определить попадание точки, заданной координатами в прямоугольник, заданный координатами вершин.
Задача 2. Даны две окружности заданного радиуса R. Найти координаты точки пересечения окружностей.
Задача 3. Дана окружность заданного радиуса R и отрезок, заданный координатами концов. Найти координаты точки пересечения окружности и отрезка.
Задание 4. Логические операции
Выбрать вариант задания. Составить блок-схему алгоритма, моделирующего работу устройства на логических элементах. Определить при каких значениях входных сигналов А, В, С сигнал на выходе будет равен “1”.
 |
 | ||||||
 | ||||||
 | ||||||
 | ||||||
 | ||||||
 |
 | ||||||
 | ||||||
 | ||||||
 | ||||||
 |
Задание для всех вариантов (творческое):
- Придумать электрическую схему устройства на логических элементах. Устройство содержит три двухпозиционных переключателя и 8 лампочек. В зависимости от положения переключателей загорается только одна из 8-ми лампочек;
- Составить блок-схему алгоритма, моделирующего работу устройства на логических элементах.
Задачи для самостоятельного решения на тему «Логические операции»:
Задача 1. Найти значение приведённых ниже логических выражений:
1) A OR B AND NOT C при A = False, B = True, C = False;
2) (x < y) OR (x = z) при a) x = 0, y = 0, z = 0;
б) x = 0, y = -8, z = 0;
3) (a £ z) AND (z>2) AND (a ≠ 5) при a) a = 2, z = 4;
б) a = -5,z = 0;
Задача 2. Компьютер вышел из строя. Известно, что:
- если монитор неисправен, то исправна видео карта, но не исправна оперативная память,
- если видео карта исправна, то исправна оперативная память, но не исправен монитор,
- если оперативная память исправна, то исправна видео карта, но не исправен монитор.
Исправен ли монитор?
Задача 3. Найти значение функции
Y=x1×x2Úx1×x2 при х1=1,х2=1.
Задание 5. Обработка массивов данных.
Таблица 2.
| Вариант | Массив | Действия |
| X(75) | Вычислить сумму нечетных элементов массива Xи их количество. | |
| A(42) | Вычислить среднее арифметическое значение четных элементов массива A. | |
| X(70) | Найти элементы массива больше 25. Выдать их сумму и количество на печать. | |
| B(50) | Найти минимальный элемент массива B и его порядковый номер. Вывести результат на печать. | |
| C(40) | Найти максимальный элемент массива C и его порядковый номер. Вывести результат на печать. | |
| D(80) | Найти максимальный и минимальный элементы массива D и поменять их местами. | |
| Y(20) | Вычислить сумму и произведение положительных элементов массива Y. | |
| А(5,8) | Найти сумму и количество элементов массива А меньше 15 и вывести на печать. | |
| A(8,8) | Определить сумму элементов массива А, стоящих выше главной диагонали и выдать их на печать. | |
| X(5, 5) | Определить сумму элементов матрицы X, стоящих выше дополнительной диагонали и выдать их на печать. | |
| Y(8, 8) | Определить сумму элементов матрицы Y, стоящих на дополнительной диагонали и выдать их на печать. | |
| Y(9, 6) | Найти сумму элементов нечетных столбцов и нечетных строк матрицы Y. |
Задание для всех вариантов (творческое):
- Придумать задачу на тему «Обработка массивов данных»;
- Составить блок-схему алгоритма.
Задачи для самостоятельного решения на тему «Обработка массивов данных»:
Задача 1. Составить блок-схему алгоритма закрашивания ячеек таблицы 8Х8 в шахматном порядке.
Задача 2. Заполнить таблицу размером 5*5 целыми числами от 1 до 25, как показано на рисунке.
Задача 3. Создать одномерный массив А(25) целых случайных чисел в диапазоне от 1 до 100. Отсортировать его в порядке возрастания.
Контрольные вопросы:
1. Что такое алгоритм?
2. Назовите формы представления алгоритма.
3. Назовите основные базовые структуры алгоритма.
4. Откуда появилось слово алгоритм?
5. Что такое итерация?
6. Перечислите основные свойства алгоритма.
7. Какая геометрическая фигура предназначена для проверки условия в блок-схеме?
8. Что такое определенность алгоритма?
9. Какая геометрическая фигура предназначена для организации цикла в блок-схеме?
10. Назовите разновидности циклических структур.