Лабораторная работа №7

Тема: Алгоритмы. Основы разработки алгоритмов. Блок-схемы алгоритмов.

Цель работы: Получить практические навыки разработки алгоритмов решения вычислительных задач в виде блок-схем.

Краткие сведения из теории

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

Наиболее популярным для решения задач на ЭВМ является графическая форма представления алгоритма в виде блок-схем. Графическое изображение алгоритма широко используется перед программированием задачи вследствие его наглядности, что облегчает процесс написания программы, ее корректировки при возможных ошибках.

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

• линейная;

• разветвляющая (альтернатива);

• циклическая.

Характерной особенностью этих структур является наличие у них одного входа и одного выхода.

Базовая структура "линейная" (следование) означает, что несколько операторов должны быть выполнены последовательно друг за другом и только один раз за время выполнения данной программы (рис. 1). Под оператором понимается формальная запись команды для выполнения некоторого действия.

Рисунок 1- Базовая структура «Линейная»

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

Рисунок 2- Базовая структура «Разветвляющая»

Алгоритм, в состав которого входит базовая структура " альтернатива или разветвляющая", называется разветвляющимся.

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

Различают три разновидности этой структуры:

• "цикл - пока" (рис. 3 а);

• "цикл - до" (рис. 3 в);

• Цикл с заданным числом повторений (рис. 3 с).

а) в) с)

а) – цикл - пока;

в) – цикл - до;

с) – цикл с заданным числом повторений.

Рисунок 3- Базовая структура «Циклическая»

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

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

Циклы могут содержать внутри себя другие циклы. Такие структуры называются вложенными циклами. Алгоритмы, имеющие в своем составе базовую структуру "цикл", называются циклическими.

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

Основные свойства алгоритмов: дискретность, определенность, конечность, повторяемость и универсальность (массовость).

Дискретность означает, что выполнение алгоритма разбивается на последовательность законченных действий - шагов.

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

Конечность (результативность) алгоритма предполагает, что его исполнение сводится к выполнению конечного числа шагов и всегда приводит к некоторому результату. Бесконечных алгоритмов не бывает.

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

Массовость (универсальность) означает, что алгоритм решения задачи разрабатывается в общем виде так, чтобы его можно было применить для множества задач одного класса, различающихся лишь набором исходных данных.

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

Таблица 1. Основные блоки

Наименование	Обозначение	Функции
Процесс		Выполнение операций, в результате которых изменяется значение, форма представления или расположение данных.
Ввод-вывод (данные)		Ввод данных в программу, или отображение (вывод) результатов работы программы на экране дисплея.
Условие (решение)		Выбор направления выполнения алгоритма в зависимости от некоторых переменных условий.
Модификация		Отображает цикл. В блоке указываются начальное значение цикла, его шаг и условие окончания цикла.
Предопределённый (типовой) процесс		Использование ранее созданных и отдельно написанных программ (подпрограмм).
Документ		Вывод данных на бумажный носитель.
Пуск (начало)		Начало процесса обработки данных (алгоритма).
Стоп (конец)		Конец (завершение) процесса обработки данных (алгоритма).
Соединитель (узел)		Указание связи между прерванными линиями, соединяющими блоки. N – номер связи.

Содержание работы:

1. Выбрать вариант задания.

2. Изучить теоретическую часть.

3. Для каждого задания выполнить постановку задачи.

4. Разработать алгоритмы задач в виде блок-схем.

5. Составить описание блок-схем алгоритмов.

Содержание отчета:

1. Постановка задач.

2. Разработка алгоритмов в виде блок-схемы.

3. Описание блок-схем алгоритмов.

4. Ответы на контрольные вопросы

Варианты заданий:

Задание 1. Системы счисления.

Вариант	Действия
	Перевести целое десятичное число, введенное с клавиатуры, в двоичную систему счисления.
	Перевести целое десятичное число, введенное с клавиатуры, в восьмеричную систему счисления.
	Перевести целое десятичное число, введенное с клавиатуры, в шестнадцатеричную систему счисления.
	Перевести целое двоичное число, введенное с клавиатуры, в десятичную систему счисления.
	Перевести целое двоичное число, введенное с клавиатуры, в восьмеричную систему счисления.
	Перевести целое двоичное число, введенное с клавиатуры, в шестнадцатеричную систему счисления.
	Перевести целое восьмеричное число, введенное с клавиатуры, в десятичную систему счисления.
	Перевести целое восьмеричное число, введенное с клавиатуры, в двоичную систему счисления.
	Перевести целое восьмеричное число, введенное с клавиатуры, в шестнадцатеричную систему счисления.
	Перевести целое шестнадцатеричное число, введенное с клавиатуры, в десятичную систему счисления.
	Перевести целое шестнадцатеричное число, введенное с клавиатуры, в двоичную систему счисления.
	Перевести целое шестнадцатеричное число, введенное с клавиатуры, в восьмеричную систему счисления.

Задание 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 студентов не учат английский. Сообщение, что случайно выбранный студент Петров изучает английский, несет log₂3 бит информации, а что Иванов изучает французский – 1 бит. Сколько студентов изучают немецкий язык?

Вариант 7.

Шифровка состояла из 36 групп символов по 6 символов в группе и содержала 81 байт информации. С помощью скольких различных знаков была закодирована шифровка?

Вариант 8.

Даны два текста, содержащих одинаковое количество символов. Первый текст состоит из алфавита мощностью 16 символов, а второй текст – из 256 символов. Во сколько раз информации во втором тексте больше, чем в первом?

Вариант 9.

В составе 16 вагонов, среди которых К – купейные, П – плацкартные и СВ – спальные. Сообщение о том, что ваш друг приезжает в СВ несет 3 бита информации. Определите, сколько в поезде вагонов СВ.

Вариант 10.

Ученики класса, состоящего из 21 человека, изучают немецкий или французский языки. Сообщение о том, что ученик A изучает немецкий язык, несет log₂3 бит информации. Сколько человек изучают французский язык?

Вариант 11.

Телеграфистка в течение пяти минут передавала информационное сообщение со скоростью 20 байт в секунду. Сколько символов содержало данное сообщение, если она использовала алфавит из 32 символов?

Вариант 12.

Для записи письма был использован алфавит мощностью в 16 символов.

Письмо состояло из 25 строк. В каждой строке вместе с пробелами было 64 символа. Сколько байт информации содержало письмо?

Задание для всех вариантов (творческое):

- Придумать задачу на тему «Измерение количества информации»;

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