Алгоритм любой сложности может быть представлен комбинацией трех базовых структур:
• ветвление (альтернатива, если–то–иначе);
Особенностью этих структур является наличие у них одного входа и одного выхода.
Базовая структура следование (Рисунок 10) означает, что несколько операторов должны быть выполнены последовательно друг за другом и только один раз за время выполнения данной программы. Совокупность связанных базовых структур следование называется линейным вычислительным алгоритмом.
Под оператором понимается формальная запись предписания для выполнения некоторой последовательности действий. Второй базовой структурой является ветвление. Эта структура обеспечивает, в зависимости от результата проверки условия (истина или ложь), выбор одного из альтернативных путей работы алгоритма, причем каждый из путей ведет к общему выходу.
Возможные пути выполнения алгоритма помечают соответствующими метками: истина/ложь, да/нет, 1/0 и т.д.
В частном случае может оказаться, что для одного из выбранных путей действий предпринимать не нужно. Такая структура получила название обход или структура если–то (Рисунок 12).
Общая структура программ | Информатика Паскаль #7 | Инфоурок
Рисунок 11 Рисунок 12
Алгоритм, в состав которого входит базовая структура ветвление, называется разветвляющимся.
Если в алгоритме имеется три и более направления ветвления, то его можно представить в виде совокупности нескольких базовых структур если–то–иначе (Рисунок 11). Такую разновидность структуры разветвление часто называют множественный выбор.
Третья базовая структура цикл обеспечивает повторное выполнение или, другими словами, циклическую работу операторов.
Различают две разновидности этой структуры: цикл–пока и цикл–до.
Группа операторов, повторяющаяся в цикле, называется телом цикла. Основное отличие структуры цикл–пока (Рисунок 13) от структуры цикл–до (Рисунок 14) заключается в том, что в первой структуре операторы тела цикла в зависимости от условия могут не выполняться совсем, тогда как в структуре цикл–до тело цикла будет выполняться хотя бы один раз. Легко заметить, что в структуре цикл–пока проверка выполнения условия осуществляется перед выполнением операторов тела цикла, а в структуре цикл–до осуществляется после прохождения тела цикла.
Рисунок 13 Рисунок 14
Циклы могут содержать внутри себя другие циклы. Такие структуры называются вложенными циклами.
Алгоритмы, имеющие в своем составе базовую структуру «цикл», называются циклическими.
Рассмотренные выше базовые структуры рекомендуется применять для соблюдения структурного подхода к разработке алгоритмов.
Реальные алгоритмы представляют собой совокупность всех рассмотренных базовых структур
ЯЗЫКИ ПРОГРАММИРОВАНИЯ
Сначала всегда разрабатывается алгоритм действий, а потом он записывается на одном из таких языков. В итоге получается текст программы – полное законченное и детальное описание алгоритма на языке программирования. Затем этот текст программы специальными служебными приложениями, которые называются трансляторами, либо переводится в машинный код, либо исполняется.
Программирование разветвляющихся алгоритмов | Информатика 8 класс #24 | Инфоурок
Языки программирования являются искусственными языками, в них синтаксис и семантика строго определены. Поэтому языки программирования, в отличие от естественных языков, не допускают многозначных и произвольных толкований.
Синтаксис – это набор правил, которые определяют основные внутренние структуры и последовательности символов, допустимых в языке программирования.
Семантика – это значения языковых единиц (слов, словосочетаний, предложений).
Составление программ для ЭВМ первого поколения велось исключительно на машинном языке, который представляет собой свод правил кодирования действий ЭВМ с помощью чисел. Для всех цифровых ЭВМ «понятна» только двоичная система счисления (СС), которая для сокращения записи часто заменяется восьмеричной или шестнадцатеричной СС. Восьмеричная и шестнадцатеричная СС используются лишь для облегчения работы программистов. Для технической реализации ЭВМ нужна только двоичная СС.
Более высоким уровнем, по сравнению с машинными языками, являются машинно-ориентированные языки символического кодирования. Основной принцип создания языков символического кодирования состоит в замене машинных кодов на их буквенные обозначения, а также в автоматизации процесса распределения памяти и диагностики ошибок. Такой машинно-ориентированный язык получил название языка Ассемблера.
ЭВМ «понимает» только машинный язык, только команды, операнды и адреса, записанные с помощью двоичных чисел. Поэтому для преобразования программы, написанной на языке Ассемблера, в машинные коды необходим «переводчик».
Перевод программы, написанной на языке Ассемблера, на машинный язык осуществляется с помощью транслятора (переводчика) – специальной программы, которая имеет созвучное с именем языка название: ассемблер.
Недостатком машинно-ориентированных языков является невозможность выполнения программы, составленной для процессора одного типа, на ЭВМ, которая построена на процессоре другого типа. Другими словами, вид программы зависит от типа машины.
На следующем уровне развития языков находятся процедурно-ориентированные языки. В отличие от машинно-ориентированных языков, синтаксис и семантика этих языков не зависят от состава имеющихся команд конкретной ЭВМ (конкретного процессора). Привязку составленной программы к конкретному типу ЭВМ осуществляет транслятор (программа-переводчик).
После ввода в ОЗУ исходной программы, составленной на языке программирования высокого уровня, осуществляется ее трансляция. В результате создается программа на машинном языке, т.е. программа, состоящая из команд того процессора (той машины), с помощью которого будет решаться задача.
Процесс перевода программы и процесс ее исполнения могут происходить двумя способами.
Первый способ, называемый компиляцией, заключается в том, что процесс выполнения программы ЭВМ осуществляется после того, как процесс перевода полностью завершен. Для компиляции характерно то, что осуществляющая ее программа- транслятор во время выполнения программы уже не нужна и потому не находится в ОЗУ, тем самым достигается экономное использование ОЗУ.
Второй способ – интерпретация – предполагает, что отдельные операторы (или другие части исходной программы) сразу после трансляции выполняются, после чего та же процедура совершается над другими операторами и т.д. При интерпретации во время выполнения рабочей программы транслятор находится в ОЗУ, т.е. занимает дополнительный объем оперативной памяти. Кроме того, процесс решения задачи замедляется, так как между отдельными этапами выполнения рабочей программы управление передается транслятору.
Интерпретатор можно сравнить с переводчиком, который выполняет устный синхронный перевод с одного естественного языка на другой (например, перевод кинофильма с английского языка на русский язык). Интерпретатор переводит и сразу выполняет программу последовательно, строчку за строчкой.
Компилятор можно сравнить с переводчиком, который делает письменные перевод статьи или книги. Компилятор перед выполнением программы вначале полностью переводит весь текст программы на машинный язык.
Интерпретатор работает медленнее, чем компилятор, занимает больше места в оперативной памяти. Однако при отладке новых программ удобнее работать с интерпретатором, так как он позволяет после исправления ошибки продолжить выполнение программы с места остановки. При работе с компилятором после устранения ошибки необходимо повторно компилировать программу и запускать ее с самого начала, а не с места расположения обнаруженной ошибки.
Существуют комбинированные способы трансляции и выполнения программ. Например, язык Java позволяет сначала компилировать программу в некоторый промежуточный код (байт-код), а затем выполнять его с помощью интерпретатора (виртуальной Java-машины).
Источник: infopedia.su
Разветвляющиеся программы Оператор разветвляющейся структуры If … Then
Базовая структура разветвление (называемая также ЕСЛИ-ТО-ИНАЧЕ) обеспечивает в зависимости от результата проверки условия (истина или ложь) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу (продолжению алгоритма). Работа алгоритма продолжается независимо от того, какой путь будет выбран. Возможные пути выполнения алгоритма помечаются на схемах алгоритмов соответствующими метками: «да»/»нет» (или «1»/»0″). Алгоритм, в состав которого входит базовая структура разветвление, называется разветвляющимся алгоритмом, а реализуемый им вычислительный процесс – разветвляющимся вычислительным процессом.
If … Then … Else – управляющий оператор, осуществляющий условное ветвление операций, основанное на оценке логического выражения. Выражение может быть истинным или ложным. Оператор имеет две формы записи –линейную и блочную.
Линейный синтаксис оператора If … Then
При линейном синтаксисе весь оператор записывается в одну строчку(перенос на новую строку не допускается).
If логическое _ выражение Then операторы 1 [Else операторы 2]
– логическое _ выражение– выражение, возвращающее не нулевое значение (истина) или ноль (ложь) (если логическое выражение состоит из нескольких составных частей, то они соединяются друг с другом посредством логических функций);
– операторы 1– операторы, выполняющиеся при значении логического выражения «истина» (если операторов несколько штук, то один от другого отделяется двоеточием);
– операторы 2– операторы, выполняющиеся при значении логического выражения «ложь» (если операторов несколько штук, то один от другого отделяется двоеточием).
Выражение, стоящее в квадратных скобках является не обязательным параметром. Таким образом, можно выделить два вида записи линейной формы – краткую и полную.
Краткая формазаписи (Если … То …. ) не содержит частьElse операторы 2.
If логическое_выражение Then оператор1
– логическое _ выражение– любое логическое выражение, допустимое в Бейсике;
– оператор1– любой оператор (или группа операторов в одну строку через разделитель – двоеточие) Бейсика, который исполняется при выполнении условия, заданногологическим_выражением. Действие оператораIfпоясняется блок-схемой, приведенной на рис. 1.
Рис. 1. Краткая форма оператора If … Then
Полная формазаписи (Если … То …. Иначе) содержит частьElse операторы 2.
If логическое_выражение Then операторы 1 Else операторы 2
– операторы 2выполняется только тогда, когдалогическое_выражениеложно. Действие оператораIfпоясняется блок-схемой, приведенной на рис. 2.
Рис. 2. Полная линейная форма оператора If…Then
Пример 1. Определение количества знаков в числе от 0 до 1000
Sub lineynaya_forma_If()
Dim x As Single
Dim y As Integer
m1: x = InputBox(«Введите целое положительное число в интервале от 0 до 1000», «Запрос задачи»)
‘повтор ввода, если ввели не отвечающее требованиям число
If x < 0 Or x > 1000 Or x <> Int(x) Then GoTo m1
If x = 1000 Then y = 4
MsgBox «Число » » имеет » » знака», , «Решение задачи»
Источник: studfile.net
Алгоритмические структуры
Вне зависимости от выбранной формы записи элементарные шаги алгоритма объединяются в алгоритмические конструкции (структуры): последовательные, разветвляющиеся, циклические, вспомогательные и рекурсивные. Для записи любого алгоритма достаточно трёх основных алгоритмических структур: последовательной, разветвляющейся, циклической.
Алгоритм реализован через последовательную алгоритмическую конструкцию, если все команды алгоритма выполняются один раз, причём в том порядке, в котором они записаны в тексте программы.
Пример 1. Алгоритм, реализованный через последовательную алгоритмическую конструкцию, представлен блок-схемой на рисунке 2.4.
Рис. 2.4. Последовательная алгоритмическая конструкция
Выясните, какую задачу решает этот алгоритм. Чему равен результат работы алгоритма при х = 2?
Пример 2. Из курса информатики основной школы вам знаком исполнитель Вычислитель, выполняющий программы линейной структуры. Его система команд может содержать две и более команды с использованием арифметических операций.
Пусть исполнитель Вычислитель может выполнять следующие команды:
1) прибавь 2;
2) умножь на 3.
Подсчитаем, сколько разных программ, состоящих из трёх команд, можно составить для этого исполнителя, и выясним число различных значений, которые будут получены в результате их исполнения при начальном значении 2.
Так как каждую из команд вы можете выбрать одним из двух вариантов, а всего команд в программе три, общее число программ находится как N = 2 3 .
Для удобства поиска числа разных вариантов значений, которые будут получены по этим программам, составим дерево решений (рис. 2.5). В его корневой вершине (0-й уровень) записывается начальное значение. Ветви дерева соответствуют командам: левые — первой, правые — второй.
В каждой вершине дерева 1-го, 2-го и т. д. уровней записывается результат, полученный после применения команды к числу из вершины-предка. Путь к каждой из вершин соответствует последовательности команд (программе) для получения значения, находящегося в вершине. Таким образом в вершинах N-го уровня будут записанны результаты программ, состоящих из N команд.
В нашем примере все значения в вершинах третьего уровня различны. Иногда значения в вершинах одного уровня совпадают. Можно сказать, что в общем случае число различных значений на уровне не превышает числа его вершин.
Рис. 2.5. Пример дерева решений
Номер уровня, на котором впервые появляется необходимое число, равен минимальному количеству команд для его получения. В нашем примере число 8 записано в вершинах 2-го и 3-го уровней, следовательно, минимальное количество команд для его получения равно двум.
Для определения количества программ, с помощью которых требуемое число получается из заданного, можно подсчитать количество вершин дерева, в которых записано требуемое число.
Подумайте, почему при заданных условиях существует только две программы для получения из числа 2 числа 8.
Если количество уровней вершин в дереве решений превышает четыре, то строить такое дерево неудобно. Так же как и в случае, когда система команд исполнителя состоит из трёх и более команд.
Для некоторых задач удобнее строить обратное дерево решений: команды исполнителя меняются на «обратные», пути строятся от результата к начальному значению.
На рисунке 2.6 показан пример построения обратного дерева решений (из числа 8 получаем число 2; команды: 1) вычти 2; 2) раздели на 3).
Рис. 2.6. Пример обратного дерева
Этот приём удобно использовать, когда обратные команды неприменимы ко всем решений вершинам.
6.2. Алгоритмическая конструкция «ветвление»
Алгоритм реализован через алгоритмическую конструкцию «ветвление», если от входных данных зависит, какие команды алгоритма будут выполняться. При каждом конкретном наборе входных данных алгоритмическая конструкция «ветвление» сводится к выполнению последовательной алгоритмической конструкции.
Пример 3. Алгоритм, реализованный через алгоритмическую конструкцию «ветвление», представлен блок-схемой на рисунке 2.7.
Рис. 2.7. Алгоритмическая конструкция «ветвление»
Выясните, какую задачу решает этот алгоритм. К какой последовательной алгоритмической конструкции сводится эта разветвляющаяся конструкция при:
1) х= -10;
2) х = 2;
3) х = 10?
6.3. Циклическая алгоритмическая конструкция
Алгоритм реализован с использованием циклической алгоритмической конструкции, если некая группа подряд идущих шагов алгоритма может выполняться многократно в зависимости от входных данных. Любая циклическая алгоритмическая конструкция содержит в себе элементы алгоритмической конструкции «ветвление».
Рис. 2.8. Блок-схемы циклов
Пример 4. Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в которых параметры v и w обозначают цепочки цифр.
Команда нашлось (и) проверяет, встречается ли цепочка и в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.
Команда заменить (v, ш) заменяет в строке первое слева вхождение цепочки v на цепочку w.
Дана программа для исполнителя Редактор:
Выясним, какая строка получится в результате применения приведённой выше программы к строке, состоящей из N подряд идущих цифр 3 при:
Пусть N = 21. Исполнитель Редактор начинает работать со строкой, состоящей из одних только цифр 3: первые три цифры 3 сразу же заменяются цифрой 2, следующие три цифры 3 тоже заменяются цифрой 2, полученные две цифры 2 заменяются цифрой 3. После этого мы фактически возвращаемся к исходной задаче, которую должны решить для строки из 16 (21-3-3 + 1) подряд идущих троек:
Можно сказать, что при каждом повторении описанных выше действий из последовательности вычёркивается по пять цифр 3: 21[3] ? 16[3] ? 11[3] ? 6[3] ? 1[3] или 3.
Пусть N = 25. Тогда:
25[3] ? 20[3] ? 15[3] 10[3] ? 5[3] ? 1[2]2[3] или 233.
Итак, можно вычёркивать из последовательности по пять цифр 3, но только при условии, что в ней есть шесть и более идущих подряд троек.
Самостоятельно определите, какая строчка получится в результате применения приведённой выше программы к строке, состоящей из 22, 23 и 24 подряд идущих цифр 3.
Таким образом, можно сформулировать следующее правило преобразования строки из N подряд идущих цифр 3, соответствующее приведённому выше алгоритму:
1) если N mod 5 = 0, то N := 5, иначе N := N mod 5;
2) исполнить исходный алгоритм для строки, состоящей из N подряд идущих цифр 3.
Определите, какая строчка получится в результате применения приведённой выше программы к строке, состоящей из 2017, 12 345 подряд идущих цифр 3.
Определите, какая строчка получится в результате применения приведённой выше программы к строке, состоящей из 2015, 12 347 подряд идущих цифр 2.
Пример 5. Алгоритмы, реализованные через циклическую алгоритмическую конструкцию, представлены блок-схемами на рисунке 2.9.
Рис. 2.9. Циклическая алгоритмическая конструкция
Известно, что X, А, В, S — целые положительные числа. Выясните, какую задачу решает каждый из алгоритмов на рисунке 2.9.
Известно, что при некотором X результатом работы и первого, и второго алгоритмов является число 3. Укажите все значения X, при которых возможен такой результат.
САМОЕ ГЛАВНОЕ
Вне зависимости от выбранной формы записи элементарные шаги алгоритма объединяются в алгоритмические конструкции (структуры): последовательные, разветвляющиеся, циклические, вспомогательные и рекурсивные. Для записи любого алгоритма достаточно трёх основных алгоритмических структур: последовательной, разветвляющейся, циклической.
Алгоритм реализован через последовательную алгоритмическую конструкцию, если все команды алгоритма выполняются один раз, причём в том порядке, в котором они записаны в тексте программы.
Алгоритм реализован через алгоритмическую конструкцию «ветвление», если от входных данных зависит, какие команды алгоритма будут выполняться.
Алгоритм реализован с использованием циклической алгоритмической конструкции, если некая группа подряд идущих шагов алгоритма может выполняться многократно в зависимости от входных данных.
Источник: murnik.ru