Следование в информатике это кратко

Обновлено: 05.07.2024

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

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

Конъюнкция

A ˄ B = F

Таблица истинности для этого выражения будет выглядеть так:

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

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

Дизъюнкция

А ˅ B = F

Таблица истинности для этого выражения будет выглядеть так:

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

Импликация

Импликацию можно обозначить как связь начальника и исполнителя. Приведём пример.

A → B = F

Таблица истинности для этого выражения выглядит так:

Если учитель ничего не задал, и ученик ничего не сделал – учитель двойку не поставит. Если учитель не задал, а ученик сделал – двойки также не будет. Если учитель задал, и ученик выполнил – оценка будет положительной. Но если учитель задал, а ученик не сделал – оценка будет отрицательной.

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

Эквиваленция

Таблица истинности для выражения A≡B выглядит так:

Инверсия

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

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

Пример линейного алгоритма, который может выполнять исполнитель Робот .

Он знает команды: вверх, вниз, вправо, влево, закрасить.

С помощью операции div вычисляется целое частное, с помощью операции mod — остаток.

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

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

Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобретя в каталоге.

Получите невероятные возможности

Конспект урока "Основные алгоритмические конструкции. Следование"

· Составление линейных алгоритмов.

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

1. Прочитать условие задачи.

2. Выяснить, значения каких величин известны и значения каких величин нужно найти.

3. Составить план решения задачи.

4. Записать решение задачи.

5. Записать ответ.

На уроках русского языка ученики часто выполняют алгоритм разбора слова по составу:

1. Определить окончание слова и обозначить его.

2. Определить основу слова.

3. Подобрать однокоренные слова.

4. Определить корень слова и обозначить его.

5. Обозначить приставку слова.

6. Обозначить суффикс слова.

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

1. Определить назначение будущего изделия, основные требования к нему, условия использования.

2. Проанализировать уже существующие аналогичные изделия.

3. Создать эскизный проект.

4. Разработать технический проект.

5. Разработать техническую документацию.

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

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

Эту идею предложил и доказал Э́дсгер Ви́бе Де́йкстра нидерландский учёный, известный своими работами в области алгоритмики. Труды Де́йкстра оказали влияние на развитие информатики и информационных технологий; он является одним из разработчиков концепции структурного программирования.

Следование – это основная алгоритмическая конструкция, которая показывает естественный, последовательный порядок действий.

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

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

Количество блоков процесс определяется количеством команд в алгоритме.

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

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

Нам необходимо загадать число в диапазоне от 1 до 5. Загадаем, например, число 3. теперь переходим к блоку процесс. Здесь нам нужно прибавить к задуманному - число 20. Получаем 23. Следующее действие – нужно прибавить к полученному числу, первоначально задуманное число. Получим 26.

Следующее действие, нужно разделить полученное число на 2 и отнять от частного наше задуманное число. Получим 10. Конец. Алгоритм выполнен.

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

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

Перейдём к практической части урока.

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

Системой команд исполнителя робот являются четыре команды перемещения – это вверх, вниз, влево и вправо. При выполнении данных команд робот перемещается на одну клетку в выбранном направлении. По команде Закрасить робот закрасит клетку в которой находится.

Выполним наш алгоритм пошагово, с помощью пульта. На панели инструментов нажимаем кнопку Робот пульт.

Итак, смотрим на поле робота. Он находится в клетке А, которая отмечена, значит первая команда будет закрасить.

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

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

Рассмотрим следующее задание.

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

Для решения задачи достаточно найти число сотен и число единиц в заданном числе и сложить их.

Чтобы вычислить количество единиц, необходимо исходное число разделить на 10 и взять остаток. Чтобы вычислить количество сотен, необходимо разделить исходное число на 100 и взять целую часть.

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

Операция деления нацело div. Целочисленное деление отличается от обычной операции деления тем, что делит число нацело с отбрасыванием остатка.

Результат целочисленного деления равен нулю, если делимое меньше делителя. Например, значением выражения 5 div 7=0.

Или другой пример: переменной x:=67div10. Здесь переменная x получит значение 6, то есть 6 – это целая часть от деления числа 67 на 10.

И операция остаток от деления mod. Деление по модулю вычисляет остаток, полученный при выполнении целочисленного деления.

Например, переменной y:=65 mod 10. Здесь переменная y получит значение 5, то есть 5 – это остаток от деления числа 65 на 10.

Значит для решения нашей задачи нам нужно

Исполним команды алгоритма для числа 468.

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

Пришло время подвести итоги урока.

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

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

Операция деления нацело div, с помощью данной операции вычисляется целое частное.

И операция остаток от деления mod, с помощью этой операции вычисляется остаток.

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

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

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

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

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

Пример 3.1. Блок-схемы алгоритмических конструкций.

1. Цикл с параметром (значение параметра изменяется от 1 до N):

2. Цикл с предусловием:

3. Цикл с постусловием:

Кроме блок-схем, для графического представления алгоритмов используют структурограммы ( N — S -диаграммы, диаграммы Насси — Шнейдермана).

Конспект по информатике "Алгоритмические конструкции" для самостоятельного изучения и подготовки к контрольным работам, экзаменам и ГИА.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение.

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

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

Цикл со счетчиком всегда выполняется i₁ – i₂ + 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]. Завершить алгоритм выводом результата.

Читайте также: