1.1.Понятие алгоритма и его свойства
Алгоритм — описанная на некотором языке точная конечная система правил, определяющая содержание и порядок действий над некоторыми объектами, строгое выполнение которых дает решение поставленной задачи.Понятие алгоритма, являющееся фундаментальным в математике и информатике, возникло задолго до появления средств вычислительной техники. Слово «алгоритм» появилось в средние века, когда европейцы познакомились со способами выполнения арифметических действий в десятичной системе счисления, описанными узбекским математиком Муххамедом бен Аль-Хорезми .Слово алгоритм — есть результат европейского произношения слов Аль-Хорезми.Первоначально под алгоритмом понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи.Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя (человека, робота, компьютера, языка программирования и т.д.).Значение слова «алгоритм» очень схоже со значениями слов «рецепт», «метод», «процесс». Однако, в отличие от рецепта или процесса, алгоритм характеризуется следующими свойствами:
дискретностью, массовостью, определенностью, результативностью, формальностью.
Дискретность ( разрывность) — это свойство алгоритма, характеризующее его структуру: каждый алгоритм состоит из отдельных законченных действий, говорят «Делится на шаги».
Массовость — применимость алгоритма ко всем задачам рассматриваемого типа, при любых исходных данных. Например,алгоритм решения квадратного уравнения в области действительных чисел должен содержать все возможные исходы решения, т.е.,рассмотрев значения дискриминанта, алгоритм находит либо два различных корня уравнения, либо два равных, либо делает вывод о том, что действительных корней нет.
Определенность (детерминированность, точность) — свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не допускать различных толкований. Также строго должен быть определен порядок выполнения отдельных шагов.
Результативность — свойство, состоящее в том, что любой алгоритм должен завершаться за конечное (может быть очень большое) число шагов. Формальность — это свойство указывает на то, что любой исполнитель, способный воспринимать и выполнять инструкции алгоритма, действует формально, т.е. отвлекается от содержания поставленной задачи и лишь строго выполняет инструкции. Рассуждать «что, как и почему?» должен разработчик алгоритма, а исполнитель формально (не думая) поочередно исполняет предложенные команды и получает необходимый результат.
1.2.Способы описания (виды) алгоритмов.
Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.
Словесное описание представляет структуру алгоритма на естественном языке. Например, любой прибор бытовой техники (утюг,электропила, дрель и т.п.) имеет инструкцию по эксплуатации, т.е.словесное описания алгоритма, в соответствии которому данный прибор должен использоваться. Никаких правил составления словесного описания не существует. Запись алгоритма осуществляется в произвольной форме на естественном, например, русском языке. Этот способ описания не имеет широкого распространения, так как строго не формализуем (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения); допускает неоднозначность толкования при описании некоторых действий; страдает многословностью.
Псевдокод — описание структуры алгоритма на естественном, частично формализованном языке, позволяющее выявить основныеэтапы решения задачи, перед точной его записью на языке программирования. В псевдокоде используются некоторые формальные конструкции и общепринятая математическая символика. Строгих синтаксических правил для записи псевдокода не существует. Это облегчает запись алгоритма при проектировании и позволяет описать алгоритм, используя любой набор команд. Однако в псевдокоде обычно используются некоторые конструкции, присущие формальным языкам, что облегчает переход от псевдокода к записи алгоритма на языке программирования. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором используемых слов и конструкций.
Блок-схема — описание структуры алгоритма с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения отдельных инструкций. Этот способ имеет ряд преимуществ. Благодаря наглядности, он обеспечивает «читаемость»алгоритма и явно отображает порядок выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур.
Описания алгоритма в словесной форме, на псевдокоде или в виде блок-схемы допускают некоторый произвол при изображении команд. Вместе с тем они настолько достаточны, что позволяет человеку понять суть дела и исполнить алгоритм. На практике исполнителями алгоритмов выступают компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке, такой формализованный язык называютязыком программирования.
Программа — описание структуры алгоритма на языке алгоритмического программирования.
Задание алгоритмов с помощью блок-схем оказалось очень удобным средством изображения алгоритмов и получило широкое распространение.
Блок-схема алгоритма — графическое изображение алгоритма в виде связанных между собой с помощью стрелок (линий перехода) и блоков — графических символов, каждый из которых соответствует одному шагу алгоритма. Внутри блока дается описание соответствующего действия.
В таблице приведены наиболее часто употребляемые символы.
Способы описания алгоритмов
К основным способам описания алгоритмов можно отнести следующие:
структурный или блок-схемный;
с помощью граф-схем;
с помощью сетей Петри.
Перед составлением программ чаще всего используются словесно-формульный и блок-схемный способы.
а) При словесно-формульном способе алгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий.
Пусть, например, необходимо найти значение следующего выражения:
Словесно-формульным способом алгоритм решения этой задачи может быть записан в следующем виде:
1. Ввести значения а и х.
2. Сложить х и 6.
3. Умножить a на 2.
4. Вычесть из 2а сумму (х+6).
5. Вывести у как результат вычисления выражения.
б) При блок-схемном описании алгоритм изображается геометрическими фигурами (блоками), связанными по управлению линиями (направлениями потока) со стрелками. В блоках записывается последовательность действий.
Данный способ по сравнению с другими способами записи алгоритма имеет ряд преимуществ. Он наиболее нагляден: каждая операция вычислительного процесса изображается отдельной геометрической фигурой. Кроме того, графическое изображение алгоритма наглядно показывает разветвления путей решения задачи в зависимости от различных условий, повторение отдельных этапов вычислительного процесса и другие детали.
Оформление программ должно соответствовать определенным требованиям. В настоящее время действует единая система программной документации (ЕСПД), которая устанавливает правила разработки, оформления программ и программной документации. В ЕСПД определены и правила оформления блок-схем алгоритмов (ГОСТ 10.002-80 ЕСПД, ГОСТ 10.003-80 ЕСПД).
Операции обработки данных и носители информации изображаются на схеме соответствующими блоками. Большая часть блоков по построению условно вписана в прямоугольник со сторонами а и b. Минимальное значение а = 10 мм, увеличение а производится на число, кратное 5 мм. Размер b=1,5a. Для от дельных блоков допускается соотношение между а и b, равное 1:2. В пределах одной схемы рекомендуется изображать блоки одинаковых размеров. Все блоки нумеруются. Виды и назначение основных блоков приведены в таблице 1.
Таблица 1. Условные обозначения блоков схем алгоритмов
Выполнение операции или группы операций, в результате которых изменяется значение, форма представления или расположение данных.
Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод).
Выбор направления выполнения алгоритма в зависимости от некоторых переменных условий.
Использование ранее созданных и отдельно написанных программ (подпрограмм).
Вывод данных на бумажный носитель.
Ввод-вывод данных, носителем которых служит магнитный диск.
Начало, конец, прерывание процесса обработки данных.
Указание связи между прерванными линиями, соединяющими блоки.
Указание связи между прерванными линиями, соединяющими блоки, расположенные на разных листах.
Связь между элементом схемы и пояснением.
Линии, соединяющие блоки и указывающие последовательность связей между ними, должны проводиться параллельно линиям рамки. Стрелка в конце линии может не ставиться, если линия направлена слева направо или сверху вниз. В блок может входить несколько линий, то есть блок может являться преемником любого числа блоков. Из блока (кроме логического) может выходить только одна линия. Логический блок может иметь в качестве продолжения один из двух блоков, и из него выходят две линии. Если на схеме имеет место слияние линий, то место пересечения выделяется точкой. В случае, когда одна линия подходит к другой и слияние их явно выражено, точку можно не ставить.
Схему алгоритма следует выполнять как единое целое, однако в случае необходимости допускается обрывать линии, соединяющие блоки.
Для того чтобы посмотреть каждый шаг в алгоритме, рассмотрим несколько задач.
1. Задание: Вычислить значение y по формуле у = (7x — 4) / (5x + 3).
Язык блок — схем
На языке программирования
INPUT "Введите переменную", X
PRINT "ВывестиY", Y
2. Задание: Решить систему уравнений:
Составление блок-схемы, соответствующей всем требованиям ГОСТов, – небыстрый и кропотливый процесс. Если у вас возникли проблемы с проектированием блок-схемы или вы запутались в том, какой элемент блок-схемы нужно использовать в конкретном месте, то записывайтесь ко мне на репетиторский урок. На частном занятии вы сможете задать мне абсолютно любой вопрос, касающийся визуализации блок-схемы.
Ключевые элементы блок-схемы
Если вы новичок в мире информационных технологий и только-только начали изучать область построения блок-схем, то я рекомендую вам потратить 5 минут и познакомиться с тем, что такое блок-схема и зачем она нужна.
Что такое схема? Схема – графическая интерпретация некоторого термина, события, анализа, действия, в котором применяются различные элементы для отображения данных.
Что такое блок-схема? Блок-схема – один из видов обыкновенной схемы, описывающая алгоритмы, в которой дискретные шаги изображаются в виде блоков, представляющих собой геометрические фигуры, и эти блоки соединены между собой линиями, которые указывают направление последовательности выполнения алгоритма.
Основные элементы, использующиеся при проектировании блок-схем
Название элемента
Графическое отображение
Функция
Терминатор или блок начало-конец
Обозначает начало или конец программы. Данный блок отделяет границы программы от внешней среды. Как правило, в данный элемент вписывают фразы «Начало», «Старт» или «Конец», «Финиш».
Блок команды, процесса, действия
Данный блок отвечает за выполнение одной или нескольких операций. Как правило, в данный элемент блок-схемы вписывают команды, которые меняют данные, значения переменных. Например, арифметическая операция над двумя переменными будет записана в данном блоке.
Блок логического условия
Напомню, что результатом логического условия всегда является одно из двух предопределенных значения: истина или ложь. Внутри данного элемента-ромба записывается логическое условие, а из вершин ромба выходят альтернативные ветви решения. Обязательно следует подписывать ветви словами «Да», «Нет», чтобы не вводить в заблуждение читателя блок-схемы.
Если ваша программа предусматривает наличие подпрограмм: процедур или функций, то вызов подпрограммы записывается внутри данного элемента.
Блок ввода-вывода данных
Отвечает за форму подачи данных, например, за пользовательский ввод данных с клавиатуры или за вывод данных на монитор персонального компьютера. Очень важно понимать, что данный элемент блок-схемы не определяет носителя данных.
Блок цикла со счетчиком
Отвечает за выполнение циклических команд цикла for. Внутри элемента записывается заголовок цикла со счетчиком, а операции тела цикла располагаются ниже элемента. При каждой итерации цикла программа возвращается к заголовку цикла, используя левую стрелку. Выход из цикла for осуществляется по правой стрелке.
Парный блок для циклов с пред- и постусловием
Данный блок состоит из двух частей. Операции тела цикла размещаются между ними. Заголовок цикла и изменения счетчика цикла записываются внутри верхнего или нижнего блока – в зависимости от архитектуры цикла.
Применяется для обрыва линии связи между элементами блок-схемы. Например, если вы строите масштабную блок-схему на листе формата А4, и она не помещается на один лист, то вам придется осуществить перенос блок-схемы на второй лист. В этом случае необходимо будет воспользоваться данным соединителем. Как правило, внутри окружности указываются уникальный идентификатор, который является натуральным числом.
Мы рассмотрели восемь базовых элементов блок-схемы, оперируя которыми вы сможете без труда реализовать абсолютно любую блок-схему, исходя из требований школьной или вузовской программы.
Если вы хотите углубить познания в области построения блок-схем или не до конца разобрались с каким-либо элементом блок-схемы, то записывайтесь ко мне на индивидуальный урок. На данном уроке мы детально разберем все ваши вопросы, а также проведем составление колоссального количества блок-схем различной степени сложности.
