Основные виды алгоритмических структур

Конспект

Основные виды алгоритмических структур

Код ОГЭ: 1.3.2. Алгоритмические конструкции

Различают три основных вида алгоритмов (базовые алгоритмические конструкции, или структуры): линейные, с разветвлениями и с циклами.

В самом простом случае алгоритм предписывает поочередное выполнение всех заданных действий независимо от значений входных данных. Например, чтобы умножить две обыкновенные дроби, необходимо перемножить отдельно их числители и знаменатели и записать их соответственно в числитель и знаменатель результата. Такие действия необходимо выполнять для умножения любых двух обыкновенных дробей.

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

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

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

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

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

Хотя алгоритм ветвления содержит описание действий для обоих возможных вариантов, но при каждом его выполнении реализуется только один из них, какой именно — зависит от заданного набора входных данных. Следовательно, в отличие от линейного алгоритма, при реализации алгоритма с разветвлением будут выполнены не все действия, а только те, что выбраны по условию.

Третий вид алгоритмов (с циклами) обеспечивает многократное выполнение некоторой совокупности действий.

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

Затем аналогично следует вычислить разность предпоследних цифр чисел и так далее. Процедура повторяется, пока все цифры исходных чисел не будут исчерпаны. Количество повторений зависит от количества цифр в заданных числах.

Алгоритм, предписывающий повторное выполнение действий, называется циклическим алгоритмом (алгоритмом с повторением, или структурой цикла).

Повторяемое действие или группа действий называется телом цикла. Количество повторений тела цикла определяется поставленным условием, которое называется условием цикла. По результату проверки условия осуществляется выбор: еще раз повторить тело цикла или перейти к другим действиям.

Наличие возврата к ранее произведенным действиям является характерным отличием алгоритмов с циклами от линейных и разветвленных.

Линейные алгоритмические конструкции

В блок–схемах линейные алгоритмы представляют с помощью последовательности функциональных блоков:

В алгоритмическом языке линейным структурам соответствует последовательность команд языка:

Команда 1Команда 2

Команда 3

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

■ Пример 1. Определить значение целой переменной n после выполнения следующего алгоритма:m := 3n := 4m := 6 + m*n

n := n + m/3

Решение. Первые две команды присваивания определяют начальные значения переменных. Для выполнения третьей команды сначала надо вычислить правую часть выражения: 6 + 3 х 4 = 18. Это значение будет присвоено переменной m. Для выполнения последней команды также сначала вычисляется правая часть выражения: 4 + 18/3 = 10. Результат будет присвоен переменной п.

Ответ: 10.

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

■ Пример 2. Вычислить значение выражения x2 – 3 × х – 10, используя только операции сложения и умножения.

Для решения задачи в той последовательности, что определяет само выражение, потребуется 2 операции умножения, 2 вычитания и 3 переменных (х, y, z). Однако можно вычислить то же выражение как (х — 2) × х – 10. Такой алгоритм расчета потребует 1 умножение, 2 вычитания и 2 переменных (х, у).

Решение.

Алгоритмические конструкции ветвления

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

Существует две реализации структуры ветвления: полная и неполная (краткая). Обе формы ветвления являются замкнутыми: каждая из них имеет один вход и один выход.

Полная форма ветвления означает, что осуществляется выбор между двумя действиями. Если проверка условия дает результат «да», то выбирается действие 1; в противоположном случае (то есть если проверка условия дает результат «нет») — выбирается действие 2.

Таким образом, полная форма команды если определяет две ветви команд: первая выполняется, если условие истинно, вторая — если условие ложно. Каждая ветвь в итоге ведет к общему выходу, так что работа алгоритма будет продолжаться при выборе любого пути.

■ Пример 3. Для извлечения квадратного алгебраического корня из числа B необходимо проверить, положительно ли это число. Если проверка дает значение «истина» («да»), извлечь корень; если результат проверки — «ложь» («нет»), выдать соответствующее сообщение пользователю.

Краткая форма ветвления предполагает, что в случае истинности условия будет выполнена команда 1, а иначе — никакие действия не выполняются.

■ Пример 4. Для расчета значений гиперболы по формуле y = 2/x необходимо проверить, что значение х не равно нулю. Если проверка условия дает значение «истина», — вычислить результат. В противном случае (если проверка условия дает значение «ложь», т. е. х равно нулю) — не выполнять никаких действий, поскольку деление на ноль запрещено.

если 2/х ≠ 0то y := 2/x

всё

■ Пример 5. Для приведенного фрагмента блок–схемы алгоритма выбрать соответствующий ему фрагмент на алгоритмическом языке.

Решение. Ромбу на блок–схеме соответствует структура ветвление (команда если): проверяется условие «отрицательное». Если условие истинно, выполняется ветвь «да» (строка то на алгоритмическом языке) с двумя действиями: «умножить на –1»; «извлечь корень».

Если условие ложно, выполняется ветвь «нет» (строка иначе на алгоритмическом языке) с одним действием: «разделить на 2». После обоих вариантов структура завершается, что соответствует служебному слову всё. Такому положению соответствует вариант алгоритма 4.
Ответ: 4.

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

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

Полная и краткая формы структуры выбор различаются действиями после проверки последнего условия. Если проверка последнего условия выдает «ложь» («нет»), — в полной форме выполняют заданную команду; в краткой форме ничего не делают.

Во всех формах структур ветвления важную роль играют условия выбора. Часто в них используются операторы сравнения или другие отношения. Результатом условия может быть только одно из двух логических значений — Ложь или Истина.

В языках программирования эти значения обычно записывают как True и False. В учебном алгоритмическом языке используют чаще значения «да» и «нет». В компьютерной форме эти значения обычно представлены битовыми значениями 0 и 1.

Простые условия обычно содержат только одну операцию — например, X > 0, А ≠ В или s = «отец». Объединение нескольких простых условий образует составное условное выражение (или составное условие). Для объединения простых условий используются логические операторы:

and (логическое И),
or (логическое ИЛИ),
xor (исключающее ИЛИ),
not (отрицание).

Например, чтобы задать условие принадлежности числовой величины Z промежутку (10;20), следует записать составное условие Z > 10 and Z < 20.

Циклические конструкции

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

Цикл с предусловием (или цикл «пока»)

Заголовок этой структуры содержит условие, которое называется предусловием. Эта структура предписывает повторять тело цикла до тех пор, пока выполняется условие в его заголовке (т. е. пока оно остается истинным).

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

Снова проверяется условие заголовка (поскольку оно могло измениться в результате работы команд цикла) — если оно истинно, опять выполняется тело цикла. Так происходит до тех пор, пока проверка условия в заголовке не выдаст результат «нет».

Тогда управление будет передано команде, следующей непосредственно за циклом.

Возможна ситуация, когда команды тела цикла не будут выполнены ни разу — если условие в заголовке сразу же выдает результат проверки «нет».

Также возможна ситуация, когда условие заголовка всегда выдает положительный результат проверки — это приведет к бесконечному выполнению цикла, так называемому «зацикливанию» алгоритма.

Таким образом, при создании цикла «пока» следует обращать особое внимание на формулировку условия в его заголовке.

■ Пример 6. Записать на алгоритмическом языке алгоритм получения остатка от деления целого числа а на целое число b с помощью вычитания.

Решение. Если число а меньше b, то остатком от деления служит само число а. В ином случае необходимо вычитать b из числа а до тех пор, пока результат не станет меньше b — он и будет остатком от деления.

Цикл с постусловием (или цикл «до»)

Постусловие формулируется противоположным образом по отношению к предусловию. Цикл «до» предписывает повторять команды тела цикла до тех пор, пока не выполнится условие в его заголовке (т. е. пока оно остается ложным).

Работа цикла с постусловием начинается с выполнения команд тела цикла. Затем проверяется условие цикла. Если условие ложно (проверка условия дает результат «нет») — происходит возврат к выполнению команд тела цикла.

Затем снова проверяется условие (поскольку оно могло измениться в результате работы команд цикла). Так происходит до тех пор, пока проверка условия не выдаст результат «да».

Тогда происходит выход из цикла и управление будет передано команде, следующей непосредственно за циклом.

В отличие от цикла с предусловием, тело цикла «до» всегда выполняется хотя бы один раз (до первой проверки). Тело цикла «пока» может не выполниться ни разу, если условие при первой же проверке выдаст «нет». Поэтому цикл с постусловием можно заменить циклом с предусловием, а наоборот — нет.

■ Пример 7. Записать алгоритм примера 6 с помощью цикла «до».

Решение.

Цикл с параметром (цикл со счетчиком, или цикл «для»)

Эта структура предписывает повторять команды тела цикла для всех значений некоторой переменной (параметра, или счетчика цикла).

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

Работа цикла «для» начинается с присвоения параметру начального значения. Если оно не превышает конечного значения, выполняются команды тела цикла. Затем значение параметра цикла увеличивается на единицу.

Если оно снова не превышает конечного значения, опять происходит выполнение тела цикла.

Если же полученное значение параметра превысит конечное, цикл будет завершен и управление передано следующей за циклом команде.

Цикл со счетчиком всегда выполняется i1 – i2 + 1 раз.

■ Пример 8. Записать алгоритм вычисления факториала числа N.

Решение. Факториал числа вычисляется по формуле N! = 1 × 2 × … × N. Следовательно, для расчета факториала надо организовать цикл со счетчиком, в котором перемножить последовательные целые числа от 2 до N. Значение 1!, равное 1, можно присвоить результирующей переменной до цикла.

Таблицы и массивы

Табличный способ организации данных позволяет удобно обрабатывать наборы однотипных данных. В языках программирования наборы табличных данных принято называть массивами. В алгоритмическом языке используют название «таблица».

■ Массив — конечный набор пронумерованных однотипных данных, имеющий имя.

Величины, которые входят в массив, называются его элементами. Количество элементов массива называется его размерностью.

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

Имя массива (таблицы) относится ко всему набору данных. Элементы массива различают по порядковому номеру, который называется индексом. Для обращения к элементу его индекс указывают в квадратных скобках сразу вслед за именем массива.

Например, если массив имеет имя D, то третий его элемент обозначается D[3]. Такие имена называются индексированными именами. Индексы могут быть не только константами, но и переменными или целочисленными выражениями: D[j], D[k+1].

Различают одномерные и многомерные массивы.

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

В одномерных таблицах или массивах могут быть записаны данные, относящиеся только к какому–либо одному факту. Например, результаты соревнований спортсменов по одному виду спорта, или регулярные показания температуры в одной местности, или оценки учащихся по одному предмету, или названия альбомов одного исполнителя.

Одномерная таблица, содержащая расстояния от Солнца до планет Солнечной системы (в астрономических единицах), может выглядеть как табличная строка:

Названия планет в этой таблице отсутствуют (иначе они бы образовали вторую строку). Чтобы узнать расстояние от Солнца до Марса, надо обратиться к четвертому элементу этой таблицы. Если, например, в программе такой массив расстояний от Солнца был поименован как Dist, то для обращения к 4–му элементу массива надо указать Dist[4].

Многомерные таблицы и массивы могут содержать данные о нескольких фактах — например, результаты соревнований спортсменов в нескольких видах спорта; измерения температуры, давления и влажности в разные месяцы в разных городах; оценки разных учащихся по разным предметам в разные дни; названия альбомов исполнителей, выпущенных в разные годы.

В отличие от индексированных элементов массива обычные переменные иногда называют скалярными.

Для описания таблицы в алгоритмическом языке используется служебное слово таб. Необходимо указать по порядку: тип элементов таблицы, служебное слово таб, имя таблицы, а затем в квадратных скобках через двоеточие начальный и конечный номера элементов таблицы.

Общий вид описания таблицы:
тип элементов таб имя таблицы [наименьший индекс : наибольший индекс]

Например, для описания таблицы расстояний от Солнца необходимо учесть, что в ней содержатся нецелые числа, следовательно, тип данных таблицы — вещественный, и количество элементов равно 9:
вещ таб Dist[1:9]

Для присвоения значений элементам таблицы (массива) используют операторы присваивания или процедуру ввода данных, как и для обычных переменных.

Например, присвоение значений элементам таблицы Dist можно описать на алгоритмическом языке следующим образом:

Зачастую ввод данных в массив или задачи их обработки связаны с перебором элементов массива. Для этих целей обычно используют циклы с параметром (со счетчиком).

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

Например, если необходимо обработать все 20 значений массива Т, то следует записать цикл нц для i от 1 до 20 … кц и в теле цикла задать обработку для элемента T[i].

Пример 10. По данным о территории некоторых стран Европы (см. первую строку примера многомерной таблицы) рассчитать суммарную площадь этих стран.

Решение. В алгоритме необходимо предусмотреть ввод вещественных данных в таблицу (например, Terr) из 9 элементов.

Для будущего суммарного результата необходимо отвести переменную (например, S), первоначально присвоить этой переменной нулевое значение.

Затем организовать цикл с параметром, изменяющимся от 1 до 9 (количество элементов в таблице) и поочередно сложить предыдущее значение S с очередным элементом таблицы Terr[i]. Завершить алгоритм выводом результата.

Конспект урока по информатике «Алгоритмические конструкции».

Вернуться к Списку конспектов по информатике.

Источник: https://uchitel.pro/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5-%D0%BA%D0%BE%D0%BD%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%86%D0%B8%D0%B8/

Алгоритмы. Типы алгоритмических структур

Основные виды алгоритмических структур
Важно! Узнайте, чем закончилась проверка учебного центра “Инфоурок”? ✖

.

Запустите файл

1. Сохраните файл

2. Кликните на скачанный файл

3. Нажмите Запустить

1. Кликните на значок ↓

2. Появится файл, дважды кликните на него

1. Нажмите Сохранить

2. Кликните на значок ↓

3. Появится файл, кликните на него

Описание презентации по отдельным слайдам:

1 слайдОписание слайда:

Алгоритм. Основные типы алгоритмических структур.

2 слайдОписание слайда:

IХ в. Мухаммеда аль-Хорезми узбекский математик определенные приемы выполнения математических вычислений с многозначными числами Аль Хорезми «АЛГОРИФМ»  «АЛГОРИТМ»

3 слайдОписание слайда:

Понятие алгоритма Алгоритм — это метод (способ) решения задачи, записанный по определенным правилам, обеспечивающим однозначность его понимания и механического исполнения при всех значениях исходных данных (из некоторого множества значений) Алгоритм — точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомо­му результату.(в толковом словаре по информатике (1991 г.) Алгоритм –последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд.

4 слайдОписание слайда:

Примеры алгоритмов Инструкция по эвакуации во время пожара Решение математических задач Рецепт блюда ПДД Распорядок дня Вывод: Алгоритм – это способ фиксации и передачи знаний, накопленных человечеством

5 слайдОписание слайда:

Исполнителем алгоритма может быть человек или автоматическое устройство – компьютеры, роботы, станки, спутники, сложная бытовая техника и даже детские игрушки.

Каждый алгоритм создается в расчете на вполне конкретного исполнителя.

Исполнителя характеризуют: Среда (или обстановка) Элементарные действия Система команд – строго заданный набор команд Отказы – команда вызывается при недопустимом состоянии среды Исполнитель выполняет алгоритм формально

6 слайдОписание слайда:

Свойства алгоритмов Понятность алгоритма Дискретность алгоритма Определенность алгоритма Результативность алгоритма Массовость алгоритма

7 слайдОписание слайда:

Для создания алгоритма необходимо знать: полный набор исходных данных задачи (начальное состояние объекта) цель создания алгоритма (конечное состояние объекта) систему команд исполнителя (то есть набор команд, которые исполнитель понимает и может выполнить)

8 слайдОписание слайда:

Способы задания (описания) алгоритмов Описание словами и формулами Описание на алгоритмическом языке Графическое описание

9 слайдОписание слайда:

Описание алгоритма словами и формулами Пример 1 Правила (алгоритм) перехода пешеходом дороги на нерегулируемого пешеходном переходе Подойти к краю догори Посмотреть налево Убедиться, что нет транспортного средства Перейти дорогу до середины Посмотреть направо Убедиться, что нет транспортного средства Перейти дорогу

10 слайдОписание слайда:

Описание алгоритма словами и формулами Пример 2 Вычисление площади круга, если известен его радиус Ввести значение радиуса R, перейти в п. 2. Вычислить S= r2, перейти в п. 3. Вывести (отпечатать) значение S, перейти в п. 4. Вычисления прекратить.

11 слайдОписание слайда:

Описание алгоритма на алгоритмическом языке Пример Задача на расчет площади круга (при исходных дан­ных r = 8 м) на алгоритмическом языке будет выглядеть: Алгоритм-программа на языке ВАSIС 10 R1 = 8 20 Р = 3.14 30 R2 = R1 * R1 40 S = Р*R2 50 РRINT S 60 END Программа – это алгоритм, записанный на языке Программирования.

12 слайдОписание слайда:

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

Прямоугольник, применяется для описания линейной последовательности команд, имеет один вход вверху и один выход внизу. Ромб, служит для обозначения условий в алгоритмических структурах «ветвление» и «выбор», имеет один вход верху и два выхода (налево, если условие выполняется, и направо, если условие не выполняется).

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

13 слайдОписание слайда:

Графическое описание алгоритма

14 слайдОписание слайда:

Пример Даны длины сторон треугольника A, B, C. Найти площадь треугольника S. Составьте блок-схему алгоритма решения поставленной задачи.

15 слайдОписание слайда:

Правила построения схемы алгоритма Выявить исходные данные, результаты, дать им имена Выбрать порядок (метод) решения задачи Разбить метод решения задачи на этапы Изобразить каждый этап в виде соответствующей блок-схемы и указать стрелкам порядок их выполнения В полученной схеме предусмотреть выдачу результатов или сообщений об их отсутствии

16 слайдОписание слайда:

Основные типы алгоритмических структур Линейные Разветвляющиеся Циклические

17 слайдОписание слайда:

Линейные алгоритмы Блоки выполнятся последовательно друг за другом, в порядке, заданном схемой Действие 1 Действие n Действие 2

18 слайдОписание слайда:

Разветвляющиеся алгоритмы Блоки выполнятся в зависимости от некоторого логического условия Полное ветвление Неполное ветвление Условие Действие 1 Действие 2 Да Нет Да Нет Условие Действие 1

19 слайдОписание слайда:

Пример: Вычислите модуль числа х Математическая запись: Блок-схема Начало Ввод х х

Источник: https://infourok.ru/algoritmi-tipi-algoritmicheskih-struktur-782114.html

Основные алгоритмические структуры

Основные виды алгоритмических структур

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

Алгоритм линейной структуры — алгоритм, в котором предписываемые действия выполняются последовательно: Оператор1 — Оператор2 — … — Оператор N. Такой порядок выполнения действий называется естественным.

Алгоритм разветвленной структуры— алгоритм, в котором предусмотрено разветвление выполняемой последова­тельности действий в зависимости от результата проверки какого-то условия. Условие — это некоторое логическое выражение.

Если условие (логическое выражение) принимает значение «истина», то выполняется Оператор1, в противном случае — значение «ложь» — выполняется Оператор2. Oпeратор1 и Оператор2 могут представлять собой группу операторов, а также могут быть условными операторами.

В случае отсутствия Оператора2 получаем конструкцию с неполным ветвлением.

Алгоритм циклической структуры(цикл с повторением) — алгоритм, в котором предусмотрено неоднократное выполнение одной и той же последовательности действий. Эту последовательность действий называют телом цикла.

Если количество повторений известно, то используют цикл со счетчиком, иначе – цикл с предварительной или последующей проверкой условия повторения.

Циклическую структуру реализуют операторы трех типов.

Оператор FOR…DOдействует следующим образом. Тело цикла выполняется для каждого значения параметра цикла I от его начального M1 до конечного значения М2 включительно. I, Ml, M2 — чаще всего переменные целого типа. Шаг изменения переменной цикла I равен +1 или -1.

Оператор WHILE… DOдействует следующим образом. Каждый раз предварительно проверяется значение логического выражения. Пока оно истинно, выполняется тело цикла. Как только оно становится ложным, происходит выход за пределы цикла. Если с самого начала значение логического выражения является ложным, то тело цикла не выполняется ни разу.

Оператор REPEAT…UNTILдействует следующим образом. Тело цикла выполняется, пока значение логического выраже­ния ложно. Тело цикла выполняется как минимум один раз.

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

Язык программирования. Типы данных. Реализация основных алгоритмических структур на языке программирования. Основные этапы разработки программ.

Языки программирования

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

Сегодня компьютеры позволяют обрабатывать информацию всех видов — текстовую, графическую, числовую, мультимедийную. Для решения задачи на компьютере необходимо создать программу, т. е.

последовательность команд, входящих в систему команд компьютера.

Для первых компьютеров программисты писали программы в двоичных кодах, т. е. на машинном языке. Каждая команда машинного языка задает некоторое элементарное действие центрального процессора.

Важным этапом в развитии программирования явилась разработка языков программирования высокого уровня(ЯПВУ) — специальных искусственных языков, приближенных к обычному разговорному языку (английскому). Примеры таких языков: FORTRAN, Basic, Pascal, С. Большинство языков высокого уровня универсальны, т. е. предназначены для решения широкого круга задач.

Первая цель создания ЯПВУ — облегчить создание программ. Вторая цель — сделать программы переносимыми, т. е. уменьшить количество труда по адаптации программ для новых типов компьютеров.

Поскольку компьютер (а точнее, его процессор) оперирует не конструкциями ЯПВУ, а двоичными командами, то перед выполнением программа должна быть превращена в машинный код. Выполняют эту операцию программы-трансляторы. В зависимости от порядка подготовки программы на языке высокого уровня к исполнению, трансляторы делятся на компиляторы и интерпретаторы.

Компилятор — это программа, автоматически преобразующая (компилирующая) исходный код ЯПВУ в машинный код и создающая таким образом исполняемый файл. Он может быть запущен на исполнение операционной системой. В ОС Microsoft такие файлы могут иметь расширения ехе, com, dll.

Интерпретатор — это программа, преобразующая код ЯПВУ в машинный код шаг за шагом, т. е.

каждая коман­да преобразуется интерпретатором и сразу выполняется компьютером, затем интерпретатор преобразует следую­щую команду, компьютер ее выполняет и т. д. (интерпретатор — «синхронный переводчик»).

Недостаток интерпретаторов — низкая скорость выполнения программ. Примеры: интерпретаторы языков Basic и Java Script. Для языка Basic в настоящее время существуют как интерпретаторы, так и компиляторы.

Типы данных

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

Языки высокого уровня организуют обработку данных с помощью переменных. Переменная— это именованная область оперативной памяти, в которой может храниться нужная информация (данные). Способ хранения определяется типом переменной.

Константа — это именованное значение, которое остается неизменным на протяжении всего времени выполнения программы. Числовая константа представляет собой какое-либо число (7; 3.14), а строковая константа – произвольную строку (“количество учеников в классе“).

В любом ЯПВУ переменные и константы характеризуются своими типами. Тип данных — это правила хранения и формат данных.

Во время работы программы тип данных будет определять, каким образом данные будут извлекаться из оперативной памяти (ОП), интерпретироваться и сохраняться в ОП.

Например, величины 205 и -45 относятся к целочисленному типу и их можно складывать, вычитать, перемножать и делить. Величины “цвет” и “ок” относятся к строковому типу, их можно сцеплять, но над ними нельзя выполнять арифметические операции.

В языке Basic существуют следующие типы данных.

Простые Структурированные
Целые: Integer (2 байта) LONG (4 байта)Массивы: DIM (могут быть целыми, вещественными, логическими)
Вещественные: SINGLE (4 байта) DOUBLE (8 байтов)Строковые: STRING (1 байт на символ)
Логические: BOOLEAN (2 байта)

Примечание: Массив – индексированный набор элементов одного типа; STRING – ряд, последовательность, цепочка; строка – последовательность символов.



Источник: https://infopedia.su/5x2cfb.html

Основные типы алгоритмических структур

Основные виды алгоритмических структур

Презентацию составила учитель первой категории МБОУ СОШ №14 имени К.С.Федоровского г.Юрги Кемеровской области

Яковлева Ирина Владимировна

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

Начало

Команда 1

Команда 2

…… .

Команда №

Конец

В алгоритмической структуре «ветвление» та или иная серия команд выполняется в зависимости от истинности условия .

Условие

Серия 1

Серия 2

, Например: 5 3, 2*8=4*4 и т.д. Сложное – последовательность простых условий, объединенных между собой знаками логических операций. Например: 5 3 And 2*8=4*4 . Алгоритмическая структура ветвление может быть выполнена на языке программирования с использованием специальной инструкции ветвления (оператора условного перехода) ” width=”640″

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

Условные выражения могут быть простыми и сложными .

Простое – два числа, две переменных или два арифметических выражения, которые сравниваются между собой с использованием операций сравнения (= , , Например: 5 3, 2*8=4*4и т.д.

Сложное – последовательность простых условий, объединенных между собой знаками логических операций. Например:5 3 And 2*8=4*4.

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

После первого ключевого слова If ( если ) должно быть размещено условие.

После второго ключевого слова Then ( то ) последовательность команд ( серия 1 ), которая должна выполняться, если условие принимает значение « истина ».

После третьего ключевого слова Else ( иначе ) размещается последовательность команд ( серия 2 ), которая должна выполняться, если условие принимает значение « ложь ».

If Условие Then

Серия 1

[ Else

Серия 2]

End if

If Условие _

Then Серия 1 _

[ Else Серия 2 ]

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

Условие 1

Условие 2

Серия

Серия 1

Серия 2

На языке программирования Visual Basic инструкция выбора начинается с ключевых слов Select Case , после которых записывается выражение (переменная, арифметическое выражение и т.д.).

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

Заканчивается инструкция ключевыми словами End Select .

Select Case Выражение

Case Условие 1

Серия 1

Case Условие 2

Серия 2

CaseElse

Серия

End Select

В алгоритмической структуре «цикл» серия команд (тело цикла) выполняется многократно.

Циклические алгоритмические структуры бывают двух типов:

  • Циклы со счетчиком , в которых тело цикла выполняется определенное количество раз;
  • Циклы с условием , в которых тело цикла выполняется, пока условие истинно.

Когда заранее известно, какое число повторений тела цикла необходимо выполнить, можно воспользоваться циклической инструкцией (оператором цикла со счетчиком) For …. Next

For –заголовок цикла;

Next – конец цикла;

Между ними располагаются операторы, являющиеся телом цикла.

For Счетчик=НачЗнач To КонЗнач [ Step шаг ]

Тело цикла

Next [ Счетчик ]

В начале выполнения цикла значение переменной Счетчик устанавливается равным НачЗнач . При каждом проходе цикла переменная Счетчик увеличивается на величину шага. Если она достигает величины, большей КонЗнач , то цикл завершается и выполняются следующие за ним операторы.

Счетчик

Тело цикла

Цикл с предусловием: когда условие выхода из цикла ставится в начале, перед телом цикла: Do ….. Loop . Проверка условия выхода из цикла проводится с помощью ключевых слов While или Until . Эти слова придают одному и тому же условию противоположный смысл.

Ключевое слово While обеспечивает выполнение цикла, пока выполняется условие, т.е пока условие имеет значение « истина ». Как только условие примет значение « ложь », выполнение цикла закончится. В этом случае условие является условием продолжения цикла .

Ключевое слово Until обеспечивает выполнение цикла, пока не выполняется условие, т.е. пока условие имеет значение « ложь ». Как только условие примет значение « истина », выполнение цикла закончится. В этом случае условие является условием завершения цикла .

Условие

Тело цикла

Do While Условие

Тело цикла

Loop

DoUntil Условие

Тело цикла

Loop

Цикл с постусловием : условие выхода из цикла ставится в конце, после тела цикла. Этот цикл реализуется также с помощью инструкции Do ….. Loop. Цикл с постусловием, в отличие от цикла с предусловием, выполняется обязательно как минимум один раз, независимо от того, выполняется условие или нет.

Do

Тело цикла

Loop While Условие

Do

Тело цикла

Loop Until Условие

Тело цикла

Условие

ЗАДАНИЕ:

Какой тип алгоритмической структуры необходимо применить, если:

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

Используемые источники:

Н.Угринович, учебник «Информатика и ИКТ», БИНОМ, 2010г.

Источник: https://videouroki.net/razrabotki/osnovnye-tipy-algoritmicheskikh-struktur-1.html

Информатика и ИКТ – Алгоритмические структуры

Основные виды алгоритмических структур

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

Линейной структурой или следованием называют последовательное однократное выполнение двух или более операторов. Например:

readln(a ,b);c := sqrt(a * a + b * b);writeln(c);

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

if логическое выражение then оператор1 else оператор2

Если значение логического выражения — истина, выполняется «оператор1», иначе (т.е. при ложности логического выражения) — «оператор2».

Пример:

if x > 0 then y := sqrt(x) else y := 0;

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

Если нужно выбирать более чем из 2 вариантов, используют вложенные условные операторы, например:

if x > 0 then y := sqrt(x) else if x > -10 then y := 0 else y := -sqrt(-x-10);

При выполнении этого фрагмента программы x сначала сравнивается с нулем, если условие в первом условном операторе не выполнено, то затем сравнивается с -10. В зависимости от результата проверки выбирается одно из трех возможных действий. В общем случае, количество условных операторов оказывается на 1 меньше числа возможных вариантов.

Второй вариант реализации ветвления — оператор множественного выбора:

case дискретное выражение of значение1: оператор1; значение2: оператор2;… значениеN: операторN;end;

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

В ряде реализаций языка может быть также указан оператор, выполняемый при несовпадении выражения ни с одним из перечисленных значений (эта часть, начинающаяся вместо значения словом «otherwise» или, в зависимости от реализации, «else», всегда записывается последней).

Пример:

write('Введите операцию');readln(c);case c of '+': write(x + y); '-': write(x – y); '*': write(x * y); '/': write(x / y); else write('Недопустимая операция')end;

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

В программе циклическая структура реализуется с помощью операторов цикла. В Pascal имеется 3 типа таких операторов: цикл с предусловием, цикл с постусловием и цикл с параметром. Они отличаются друг от друга тем, как определяется число повторений.

Циклы с условием

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

Если условие проверяется перед выполнением действий тела цикла, то такой цикл называют циклом с предусловием или циклом «пока» («повторять пока истинно условие»). В Pascal он выглядит следующим образом:

while условие do оператор;

Пример:

while a > 10 do a := sqrt(a);

Такая запись обозначает: пока значение переменной a превосходит 10, из него следует извлекать квадратный корень. Предположим, что до начала цикла переменная имела значение 10000. Поскольку 10000 > 10, из него будет извлечен корень; переменная получит значение 100.

С этим значением вновь проверяется условие повторения. 100 больше 10, поэтому квадратный корень извлекается еще раз; переменная получает значение 10.

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

Другой тип цикла с условием — цикл с постусловием, в котором проверка условия происходит после выполнения операторов тела цикла. Действия повторяются до того момента, когда условие станет истинным. В Pascal он записывается следующим образом:

repeat операторыuntil условие;

Пример:

repeat write('Введите положительное число:'); readln(x)until x > 0;

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

Цикл с параметром

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

В Pascal оператор цикла с параметром выглядит следующим образом:

for параметр := начальное to конечное do оператор;

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

for параметр := начальное downto конечное do оператор;

Пример 1:

for i := 1 to 20 do writeln(i:3, i*i*i:5);

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

В результате получится таблица кубов первых двадцати натуральных чисел.

Чтобы значения выводились ровными колонками, в процедуре вывода указан формат (на значение переменной i отведено 3 позиции, для куба — 5).

Пример 2:

for c := 'z' downto 'a' do write(c);

Этот фрагмент программы выведет на экран английский алфавит в обратном порядке —от «z» до «a»:

Источник: https://www.sites.google.com/site/415ict/textbooks/pascal/alg-struct

Book for ucheba
Добавить комментарий