Информатика
Алгоритм — это система точных и понятных предписаний о содержании и последовательности выполнения конечного числа действий, необходимых для решения любой задачи данного типа.
Примеры: правила сложения, умножения, решения алгебраических уравнений и т.п.
1.Универсальность (массовость) — применимость алгоритма к различным наборам исходных данных.
2.Дискретность — процесс решения задачи по алгоритму разбит на отдельные действия.
3.Конечность — каждое из действий и весь алгоритм в целом обязательно завершаются.
4.Результативность — по завершении выполнения алгоритма обязательно получается конечный результат.
5.Выполнимость (эффективность) — результата алгоритма достигается за конечное число шагов.
6.Детерминированность (определенность) — алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно. Т.е. одно и то же предписание после исполнения должно давать один и тот же результат.
7.Последовательность – порядок исполнения команд должен быть понятен исполнителю и не должен допускать неоднозначности.
1. вычислительные алгоритмы , работающие со сравнительно простыми видами данных, такими как числа и матрицы, хотя сам процесс вычисления может быть долгим и сложным;
2. информационные алгоритмы , представляющие собой набор сравнительно простых процедур, работающих с большими объемами информации (алгоритмы баз данных);
3. управляющие алгоритмы , генерирующие различные управляющие воздействия на основе данных, полученных от внешних процессов, которыми алгоритмы управляют.
По типу передачи управления алгоритмы бывают: основные (главные выполняемые программы) и вспомогательные (подпрограммы).
Для задания алгоритма необходимо описать следующие его элементы:
1.набор объектов, составляющих совокупность возможных исходных данных, промежуточных и конечных результатов;
3.правило непосредственной переработки информации (описание последовательности действий);
5.правило извлечения результатов.
Способы описания алгоритмов.
Символьный, когда алгоритм описывается с помощью специального набора символов (специального языка).
Словесная форма записи алгоритмов обычно используется для алгоритмов, ориентированных на исполнителя-человека. Команды такого алгоритма выполняются в естественной последовательности, если не оговорено противного.
Графическая запись с помощью блок-схем осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками. Графическая запись алгоритма имеет ряд преимуществ: каждая операция вычислительного процесса изображается отдельной геометрической фигурой и графическое изображение алгоритма наглядно показывает разветвления путей решения задачи в зависимости от различных условий, повторение отдельных этапов вычислительного процесса и другие детали.
Правила создания блок – схем:
1.Линии, соединяющие блоки и указывающие последовательность связей между ними, должны проводится параллельно линиям рамки.
2.Стрелка в конце линии может не ставиться, если линия направлена слева направо или сверху вниз.
3.В блок может входить несколько линий, то есть блок может являться преемником любого числа блоков.
4.Из блока (кроме логического) может выходить только одна линия.
5.Логический блок может иметь в качестве продолжения один из двух блоков, и из него выходят две линии.
6.Если на схеме имеет место слияние линий, то место пересечения выделяется точкой. В случае, когда одна линия подходит к другой и слияние их явно выражено, точку можно не ставить.
7.Схему алгоритма следует выполнять как единое целое, однако в случае необходимости допускается обрывать линии, соединяющие блоки.
В линейном алгоритме операции выполняются последовательно, в порядке их записи. Каждая операция является самостоятельной, независимой от каких-либо условий. На схеме блоки, отображающие эти операции, располагаются в линейной последовательности.
В алгоритме с ветвлением предусмотрено несколько направлений (ветвей). Каждое отдельное направление алгоритма обработки данных является отдельной ветвью вычислений. Направление ветвления выбирается логической проверкой, в результате которой возможны два ответа:
1.«да» — условие выполнено.
2.«нет» — условие не выполнено.
Циклические алгоритмы содержат цикл – это многократно повторяемый участок алгоритма.Различают циклы с предусловием и постусловием.Также циклы бывают детерминированные и итерационные.Цикл называется детерминированным, если число повторений тела цикла заранее известно или определено. Цикл называется итерационным, если число повторений тела цикла заранее неизвестно, а зависит от значений параметров (некоторых переменных), участвующих в вычислениях.
Решения блок-схем алгоритмов
Если дать определение схеме, можно отметить основной момент: в первую очередь подразумевается абстракция какого-нибудь процесса (системы), при которой наиболее важные части отображаются наглядно (визуально). Схемы использовались на протяжении всей истории человечества: это и чертежи пирамид, и карты сухопутных и морских путей, и принципиальные электрические схемы.
Те же мореплаватели, создавая карты, делали это в соответствии с единой системой обозначений — это позволяло обмениваться информацией друг с другом. То же самое справедливо и для визуального отображения схем алгоритмов — существуют правила, единые обозначения и стандарты, регламентирующие их применение. В России это ГОСТ 19.701-90 «Схемы алгоритмов программ, данных и систем», который близок к международному стандарту ISO 5807:1985.
Главные элементы блок-схем алгоритмов
Прежде чем продолжить, стоит дать определение блок-схемы в соответствии со стандартом — речь идёт о совокупности символов, которые отвечают этапам работы алгоритма, причём эти символы имеют соединяющие линии: — пунктирную — для соединения с комментарием; — сплошную — отображает зависимости по управлению, допускается наличие на ней стрелки. В соответствии со стандартом составитель может не указывать стрелку, если дуга направляется сверху вниз или слева направо.
Также существуют и дополнительные виды линий, которые применяются, когда надо дать описание блок-схемам параллельных алгоритмов, однако в этой статье мы их рассматривать не будем, как и ряд других дополнительных спецсимволов.
В таблице ниже дан перечень основных символов, используемых при описании алгоритмов:
Задача и блок-схема алгоритма
На картинке ниже дан алгоритм в виде схемы. В нем мы видим оператор присваивания := , то есть X := 1 будет означать, что переменная Х примет значение 1. По результату алгоритмических действий надо определить итог работы представленного алгоритма, используя следующие входные данные: Х = 7, Y = 12.
Схема этого алгоритма и решение задачи будут выглядеть следующим образом:
Решение алгоритма сортировки пузырьком
В этом примере давайте попробуем дать описание решению алгоритма сортировки по методу пузырьком (метод сортировки вставками). Здесь применяются 2 цикла. Во вложенном цикле осуществляется попарное сравнение элементов. Если нарушается порядок, происходит перестановка. По итогу выполнения одной итерации во внутреннем цикле, наибольший элемент будет смещён в самый конец массива. Внешний цикл будет выполняться, пока полностью весь массив не отсортируется.
На схеме отображено применение символов конца и начала цикла. Здесь условие внешнего цикла (А) проверяется в конце (с постусловием), а функционирует он до тех пор, пока переменная hasSwapped является true. Во внутреннем цикле используется предусловие для перебора пар элементов, которые сравниваются. Если они располагаются в неправильном порядке, они переставляются путём вызова внешней процедуры (swap). Для понимания назначения внешней процедуры, как и порядка следования аргументов этой процедуры, нужно оставлять комментарии. Если функция возвращает значение, то комментарий можно написать к символу-терминатору конца.
В этой статье мы постарались дать ответ, зачем нужны блок-схемы, каковы их основные элементы, как с их помощью решить алгоритмическую задачу. При подготовке материала использовались следующие источники:
Как решать блок-схемы по информатике
Блок-схемы – это способ графического изображения алгоритма, при котором его шаги изображаются в виде различной формы блоков, которые соединены между собой стрелками.
Введение
Блок-схема, по сути, является алгоритмом разрешения заданной специалистам проблемы. Понятие алгоритма появилось благодаря Мухаммеду аль-Хорезми, жившему в восьмом — девятом веках нашей эры. Он считается автором правил осуществления четырёх основных арифметических операций. Если брать более современные определения алгоритма, то по ГОСТ от 1974 года алгоритмом является: точное и однозначное представление очерёдности процедур, которое определяет процесс вычислений. При этом существуют некоторые переменные с определёнными параметрами, приводящие вычисления к требуемому итогу. Алгоритм ясно предписывает его исполнителю осуществлять в строгой очерёдности конкретные действия для разрешения указанной задачи и достижения необходимой цели. Создание алгоритма заключается в подразделении решения единой большой задачи на некоторую последовательную цепь действий. Проектировщик алгоритма должен обладать знаниями по методике и правилам этой работы.
Статья: Как решать блок-схемы по информатике
Поможем написать реферат за 48 часов
Особенности алгоритма
Для практически всех типов разрабатываемых алгоритмов, следует подчеркнуть следующие их особенности:
- Всегда в составе алгоритма должна быть в наличии операция занесения исходных данных.
- После окончания работы основной части алгоритма должен выдаваться окончательный итоговый результат, поскольку это и есть основная цель создания алгоритма.
- Алгоритм должен иметь дискретную структуру. То есть, его возможно представить в форме последовательных шагов. Очередной шаг всегда начинается после окончания действий предыдущего шага.
- Толкование операций алгоритма всегда однозначно. Любой этап имеет чёткое определение, не допускающее другой трактовки.
- Конструкция алгоритма предполагает конечность его процедур, то есть он должен осуществляться за чётко назначенное число шагов.
- Корректность алгоритма должна быть абсолютной, то есть он выдаёт только правильное разрешение исходной задачи.
- Алгоритм должен быть способен функционировать с разными начальными данными.
- Время выполнения алгоритма должно быть минимизировано, что даёт более эффективное разрешение исходной задачи.
«Как решать блок-схемы по информатике» ��
Готовые курсовые работы и рефераты
Решение задач по учебе за 24 часа
Реферат по этой теме за 48 часов
Далее рассмотрим возможные методики и формы представления алгоритмов.
Словесная запись
Этот тип используется при определении очерёдности осуществления действий для людей: «Сходи туда, не знаю куда, найди то, не знаю что». Естественно, это лишь шуточный пример, но он выражает суть словесного описания алгоритма. Более достоверным примером является надпись на автобусном стекле: «При аварии, выдерните шнур и выдавите стекло». Тут уже ясно прописано условие, при появлении которого необходимо осуществить две операции, соблюдая их очерёдность. Это несложные алгоритмы, но есть и гораздо сложнее. Часто применяются в алгоритмах разные формулы и специальные обозначения, но только с обязательным условием, что их поймёт исполнитель алгоритма.
Графическая запись алгоритма
При интерпретации алгоритма в виде графики используются компоненты блок-схем. Они стандартизированы и у всех команд существует некоторое определение в формате графики. А, собственно, текст команды пишется внутри графического блока. Блоки соединены при помощи линий, которые определяют очерёдность исполняемых команд. Такой тип описания алгоритма больше применим при программировании, чем словесная запись. Когда выстроенный алгоритм служит для его реализации программой на компьютере, то он может быть записан специальными кодами. Для этих целей есть большое количество языков программирования. Но и алгоритм в таком случае имеет название программы.
Базовой графической формой записи алгоритма является блок-схема. Все операции и действия представляются в виде геометрических фигур. В этих фигурах расположен перечень подлежащих исполнению в этом блоке операций. Связи отображаются обычными линиями, и, если это нужно, то со стрелками. Правила формирования блок-схем алгоритмов прописаны в ГОСТ 19.701-90. Он предписывает законы и правила проектирования алгоритмов в формате графики и методику их решения. Необходимо подчеркнуть следующие главные правила формирования любых блок-схем:
- Всегда предполагается присутствие блоков «Начало» и «Конец». И они не должны повторяться.
- Первый и последний блоки соединяются связующими элементами и линиями.
- От любого блока, кроме последнего, отходят потоковые линии.
- Блоки имеют нумерацию сверху вниз и слева направо.
- Блоки алгоритма соединяются линиями, которые назначают очерёдность исполнения операций. В случае движения потока в другом направлении (снизу вверх или справа налево), оно должно быть указано стрелками.
- Все линии могут быть входными и выходными. Причём одна и та же линия для одного блока будет входной, а для другого выходной.
- Начальный блок имеет только выходную линию потока, поскольку он первый.
- Последний (конечный) блок обладает только входящей линией.
- Для более удобного отображения блок-схем, все входящие линии располагаются сверху, а выходящие снизу.
- Возможно присутствие разрывных потоковых линий, но они всегда отмечаются специальными соединителями.
- Для большей наглядности блок-схемы, позволительно дополнительную информацию располагать в комментариях.
Линейные алгоритмы
Наиболее простым видом алгоритмов считается линейный. Он предполагает фиксированную очерёдность действий, которая не зависит от начальных данных. В нём имеется набор команд, выполняемых однократно и только по завершению предыдущей команды. Линейную блок-схему модно представить в следующем виде:
Рисунок 1. Линейный алгоритм. Автор24 — интернет-биржа студенческих работ.
При этом связи, как указывалось выше, идут сверху вниз или слева направо. Такой тип блок-схем применяется для представления алгоритмов расчётов по несложным формулам, не имеющих ограничений на величины переменных, которые есть в расчётных формулах. Линейный алгоритм является составляющим компонентом более сложных вычислительных алгоритмов.
Разветвляющиеся алгоритмы
Блок-схемы этих алгоритмов более сложные, чем линейные, но исходный смысл остаётся прежним. Разветвляющийся алгоритм является процессом, в котором последующие операции определяются выполнением некоторых условий или итогов решений. Все возможные операции являются ветвями алгоритма.
Рисунок 2. Разветвляющиеся алгоритмы. Автор24 — интернет-биржа студенческих работ
Схемы отображают блоки, имеющие название «Решение». У них есть пара выходов и записанное в блоке некоторое условие логики. Это условие определяет, по какой ветви алгоритма пойдёт дальнейшее продвижение. Алгоритмы с ветвлениями подразделяются на следующие типы:
- С «обходом». В одной ветви нет команд. Выполняется проход мимо некоторых процедур соседней ветви.
- С «разветвлением». Во всех ветвях есть некоторый комплекс операций, подлежащих выполнению.
- С «множественным выбором». Это ветвление, при котором имеется набор ветвей и во всех содержится некоторый комплекс процедур.
Замечание 1
Следует заметить, что определение ветви, по которой пойдёт далее процесс, находится в прямой зависимости от заданных величин параметров, включённых в алгоритм.
1. Алгоритмы
Алгоритм — это предписание исполнителю совершать определённую последовательность действий для получения решения задачи за конечное число шагов.
Алгоритмизация — процесс разработки алгоритма для решения задачи.
Свойства алгоритмов
1. Понятность — алгоритм должен быть написан на понятном для исполнителя языке.
2. Дискретность (прерывность, раздельность) — алгоритм должен представлять запись отдельных шагов. Необходимо использовать минимальное количество шагов. Каждый шаг должен приносить определённый результат.
3. Определённость — алгоритм должен быть чётким и восприниматься однозначно.
4. Результативность (или конечность) — алгоритм должен обязательно приводить к результату.
5. Массовость — алгоритм решения задачи применим для некоторого класса задач, различающихся лишь входными данными.
Способы записи алгоритмов
- Словесный (описание алгоритма на естественном языке).
- Графический (алгоритм составляется из специальных блоков — геометрических фигур).
- Псевдокоды (описания алгоритмов на условном алгоритмическом языке).
- Программный (тексты на различных языках программирования).