1. Линейные алгоритмы и алгоритмы с ветвлениями
Линейный алгоритм (следование) — это алгоритм, который описывает последовательно выполняющиеся действия.
Рассмотрим простой пример линейного алгоритма.
Алгоритм «Открой дверь».
- Начало.
- Достань ключ из кармана.
- Вставь ключ в замочную скважину.
- Поверни ключ два раза.
- Вытащи ключ.
- Конец.
Изобразим данный алгоритм графически, с помощью блок-схемы.
Алгоритм с ветвлением (разветвляющийся) — это алгоритм, в котором в зависимости от результатов проверки условия выполняется либо одно действие, либо другое.
Редко в нашей жизни встречаются ситуации, когда известна чёткая последовательность действий. Часто мы стоим перед выбором и принимаем решение в зависимости от ситуации. Если на улице светит солнце, то зонт и дождевик оставим дома, иначе всё это возьмем с собой. Но выбор не всегда бывает таким простым.
Упрощение логических выражений
Для написания любой логической функции может быть использовано логическое выражение, после чего можно составить логическую схему. Как правило, все логические выражения упрощают для получения максимально простой и дешевой логической схемы. В сущности, логическая схема, выражение и логическая функция, являются тремя различными языками, повествующими об одном и том же.
Логические выражения упрощают при помощи различных законов алгебры логики. Часть преобразований напоминает преобразования формул, выполняемые в классической алгебре (например, применение сочетательного и переместительного законов, вынесение за скобки равенства общего множителя и так далее). Для других преобразований используют свойства, которых лишены операции классической алгебры.
Любые законы алгебры логики выводят для главных логических операций следующим образом: НЕ — инверсия (то есть, отрицание); ИЛИ — дизъюнкция (то есть, логическое сложение); И — конъюнкция (то есть, логическое умножение).
Закон двойного отрицания состоит в том, что операция НЕ является обратимой: если ее использовать два раза, логическое значение в результате останется неизменным.
Сущность закона исключенного третьего состоит в том, что каждое логическое выражение при любых условиях является истинным, либо ложным. Если A=1, тогда A=0, а также наоборот. Конъюнкция данных величин всегда равняется 0, дизъюнкция равна 1.
Закон повторения и операции с константами легко можно проверить, используя таблицы истинности операций ИЛИ и И.
Сочетательный и переместительный законы имеют такой же вид, как в математике. Аналогия с привычной всем классической алгеброй.
Для дизъюнкции распределительный закон состоит просто в раскрытии скобок. Для конъюнкции выражение неизвестно, в математике подобное равенство является неверным. Начнем доказывать с правой части. Сначала раскроем скобки:
Используем закон повторение, гласящий, что A⋅A=A,
A+A⋅B=A⋅(1+B)=A⋅1=A, следовательно, (A+B)⋅(A+C)=A+B⋅C.
Мы доказали равенство.
Правил, используемые для раскрытия инверсии сложных выражений, назвали именем известного логика и математика де Моргана. Суть состоит в том, что общее отрицание не только распространяется на отдельные выражения, а еще и дизъюнкция заменяется конъюнкцией (а также наоборот). Для доказательства данных правил используются таблицы истинности.
Основная часть аксиом и законов алгебры логики записаны попарно. Внимательно изучая пары, можно сформулировать принцип двойственности, звучащий следующим образом: если осуществить в тождестве замены конъюнкции, а также дизъюнкции. И также элементов 1 и 0 (при их наличии), получится тождество. Данное свойство именуют принципом двойственности.
Так и не нашли ответ на вопрос?
Просто напишите,с чем нужна помощь
Мне нужна помощь
Упрощения логических выражений в примерах
Формула, вытекающая из распределительного закона. При ее выведении применили вышеупомянутое правило де Моргана для дизъюнкции, а также использовали закон двойного отрицания, после чего сомножитель X, вынесли за скобку, тогда как в скобках получили закон исключённого третьего, а также применили операцию с константами.
Лень читать?
Задай вопрос специалистам и получи ответ уже через 15 минут
Задать вопрос
Примеры упрощения логических выражений
Пример первый
Кто из рабочих, обозначенных, как A, B, C, D работает на заводе, а кто нет, если нам даны следующие условия:
- если работает A либо работает B, тогда не работает C;
- если не работает B, тогда работает D, а также работает C.
Решение задачи. Обозначим несколько простых высказываний:
- A рабочий A на заводе работает;
- B рабочий B на заводе работает;
- C рабочий C на заводе работает;
- D рабочий D на заводе работает.
Сформулировав данные из условия при помощи этих простых высказываний, получим следующее:
Получаем следующую конъюнкцию: ((A+B)→C)⋅(B→C⋅D)⋅C.
После упрощения данной формулы получаем, что A равно 0, B равно 1, C равно 1, D равно 1.
Ответ: ученик A на заводе не работает, а ученики B, C, D играют.
В этом примере применено правило де Моргана, затем использован распределительный закон, после этого применен закон исключенного третьего, потом использован переместительный закон. За ним реализован закон повторения, потом опять применен переместительный закон и, наконец, использован закон поглощения.
Чтобы отыскать решения логического уравнения можно также применить упрощение логических выражений.
Нужно отыскать все решения данного уравнения
Применив правило де Моргана, получим
а затем применяем закон поглощения и получаем
Чтобы логическая сумма равнялась нулю, все слагаемые должны равняться нулю, из чего следует, что
A равно 1, B равно 0, C равно 0, D равно 0.
Логика
f) символ 1 используется для обозначения истины (истинного высказывания); символ 0 – для обозначения лжи (ложного высказывания).
1.2. Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А → В и (¬А) \/ В равносильны, а А /\ В и А \/ В – нет (значения выражений разные, например, при А = 1, В = 0).
1.3. Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), тождество. Таким образом, ¬А \/ В \/ С \/ D означает то же, что и
Возможна запись А \/ В \/ С вместо (А \/ В) \/ С. То же относится и к конъюнкции: возможна запись А /\ В /\ С вместо (А /\ В) /\ С.
2. Свойства
Приведенный ниже список НЕ претендует на полноту, но, надеемся, достаточно представителен.
2.1. Общие свойства
- Для набора из n логических переменных существует ровно 2n различных значений. Таблица истинности для логического выражения от n переменных содержит n+1 столбец и 2n строк.
2.2.Дизъюнкция
- Если хоть одно из подвыражений, к которым применяется дизъюнкция, истинно на некотором наборе значений переменных, то и вся дизъюнкция истинна для этого набора значений.
- Если все выражения из некоторого списка истинны на некотором наборе значений переменных, то дизъюнкция этих выражений тоже истинна.
- Если все выражения из некоторого списка ложны на некотором наборе значений переменных, то дизъюнкция этих выражений тоже ложна.
- Значение дизъюнкции не зависит от порядка записи подвыражений, к которым она применяется.
2.3. Конъюнкция
- Если хоть одно из подвыражений, к которым применяется конъюнкция, ложно на некотором наборе значений переменных, то и вся конъюнкция ложна для этого набора значений.
- Если все выражения из некоторого списка истинны на некотором наборе значений переменных, то конъюнкция этих выражений тоже истинна.
- Если все выражения из некоторого списка ложны на некотором наборе значений переменных, то конъюнкция этих выражений тоже ложна.
- Значение конюнкции не зависит от порядка записи подвыражений, к которым она применяется.
2.4. Простые дизъюнкции и конъюнкции
Назовем (для удобства) конъюнкцию простой, если подвыражения, к которым применяется конъюнкция, – различные переменные или их отрицания. Аналогично, дизъюнкция называется простой, если подвыражения, к которым применяется дизъюнкция, – различные переменные или их отрицания.
- Простая конъюнкция принимает значение 1 (истина) ровно на одном наборе значений переменных.
- Простая дизъюнкция принимает значение 0 (ложь) ровно на одном наборе значений переменных.
2.5. Импликация
- Импликация A →B равносильна дизъюнкции (¬А) \/ В. Эту дизъюнкцию можно записать и так: ¬А \/ В.
- Импликация A →B принимает значение 0 (ложь) только если A=1 и B=0. Если A=0, то импликация A →B истинна при любом значении B.
Основы программирования на языке Python. Часть 2
На минутку представим себя богами. В первой части этой статьи мы с вами разобрали самые базовые элементы программирования. Или на нашем, на «божественном» — мы научились создавать самый простой мир, в котором живут разные человечки со своими особенностями, но без целей в жизни. Пора заставить их что-то делать и использовать свой потенциал по максимуму. Для этого переходим на новый уровень.
Условная конструкция. Табуляция
В этой статье мы будем переводить с алгоритмического языка на язык Python то, что выучили в одной из предыдущих статей — «Основы алгоритмов». Также мы успели изучить создание и применение переменных в Python, и то, какие типы данных могут быть им присвоены, в статье «Основы программирования на языке Python. Часть 1». Но далеко на этом не уедешь — нет никакой гибкости, никаких дополнительных возможностей, ничего интересного.
Условная конструкция if-elif-else — первый шаг на пути к разнообразию. Ее цель — совершать конкретные действия при конкретных обстоятельствах.
Эта логическая конструкция расшифровывается так — «если-иначе». Даже без нашего четкого осознания она появляется в повседневной жизни везде. Самая простая идея алгоритма с ветвлением (с условием): «Если в холодильнике нет продуктов, их надо купить, прежде чем начать готовить ужин, иначе можно сразу начинать готовку».
Как в программе Python выглядят ветвления?
Подробно разберем строение этой конструкции:
- if — главная команда создания условия, ее одной уже достаточно. С ней конструкция будет выглядеть так:
Если выполнится, то будет запущено , иначе не произойдет ничего.
| x = 25 if x > 0: print(“x больше 0”) Вывод программы: х больше 0 |
x = -6 if x > 0: print(“x больше 0”) Вывод программы: ничего не будет выведено |
- else — команда, задающая альтернативу.
if :
else:
Если выполнится, то будет запущен блок , а если оно не выполнится — запустится .
- elif — команда для создания сложного условия, когда у нас есть не два исхода, а больше.
if :
elif :
elif :
…
else:
В зависимости от выполнения какого-то из будет запущено соответствующее . Команда else в данном случае не обязательна: если она есть, при невыполнении всех условий выполнится ее тело, а если ее нет — просто не произойдет ничего.
Табуляцию можно проставить либо нажатием клавиши Tab, либо используя несколько идущих подряд пробелов. Традиционно табуляции соответствует 4 пробела. Но нельзя одновременно использовать и пробелы, и Tab — в одном блоке должно быть только что-то одно.
Про табуляцию вообще нельзя забывать и нужно быть с ней аккуратнее:
- если ее проставить неправильно — программа будет выполняться не так, как мы задумали;
- если не проставить совсем — программа не сможет даже запуститься.
А чем вообще может быть условие команды?
Это должна быть такая конструкция, про которую определенно можно сказать, истинна она или ложна. Например, 5 > 1 — истина (True), а 5 > 10 — ложь (False).
Для записи условий в Python предусмотрены как математические операторы сравнения, так и логические операторы:
Математические операторы сравнения работают так же, как и в школьном курсе алгебры. Только обратите внимание, что большинство из них записывается иначе, и могут применяться не только для чисел, а и для других типов данных.
Когда мы попробуем вывести на экран результат выполнения условия, мы увидим, что он может вернуть:
- либо значение True, которое соответствует выполнению записанного условия;
- либо False, соответствующее невыполнению условия.
x = 15
y = 16
print(x == y)
print((y > x) and (x > 5))
Это как раз и есть тот самый тип данных bool из предыдущей части статьи.
А ниже приведен пример кода, в котором разная расстановка отступов дает нам совершенно разное поведение программ.
Циклы. Тип range
Как в программе Python выглядят циклы?
Циклы используются для многократного повторения определенной команды или набора команд. Для выделения тела цикла также используется табуляция.
В Python есть два цикла — while и for.
Цикл while будет повторять команды своего тела до тех пор, пока выполняется условие, записанное для него.
Структура записи этого цикла:
Например, нам нужно уменьшать значение переменной a в 2 раза нацело до тех пор, пока она не станет меньше или равной переменной b. Для этого в условии цикла прописываем сравнение переменных, а в теле цикла — уменьшение значения переменной a. Пока условие выполняется (то есть принимает значение True), будет выполняться тело цикла, а когда оно перестанет выполняться — свою работу продолжит основной блок кода.
a = 1000000
b = 16
while a > b:
a //= 2
print(a)
После первой итерации (запуска содержимого цикла) переменная а будет равна 500 000, после второй — 250 000 и т.п. Итерации будут повторяться, пока будет продолжать быть истинным выражение a > b. Когда итерации цикла завершаются, мы видим итоговое значение переменной а после всех делений — 15.
Бесконечный цикл — ситуация, когда цикл while сам по себе никогда не сможет завершить свою работу, то есть значение его условия никогда не перестанет быть равным True.
Но как вообще можно в него попасть?
- Случайно, когда в записи условия работы цикла была допущена ошибка.
В приведенном примере цикл будет работать до тех пор, пока значение переменной b больше 0. Но никакого изменения этой переменной не происходит, она не меняет своего значения, и, соответственно, никогда не станет меньше или равной 0. А значит, цикл никогда не завершит свою работу.
- Специально. Редко, но это имеет смысл. Например, когда условие работы цикла зависит от большого количества параметров, проще будет прямо в цикле указать, что ему стоит прекратить свою работу.
Для создания бесконечного цикла в условии работы нужно прописать выражение, результат которого всегда будет равен True. Например, это может быть само значение True или условие сравнения 0 == 0, также возвращающее всегда True (0 действительно всегда равен 0).
Для остановки цикла используется команда break. Когда цикл натыкается на нее, он моментально прекращает свою работу. Не сработает и последующий блок кода, не будет и следующего шага цикла — программа сразу перескакивает в основной блок кода после цикла.
В примере мы создали бесконечный цикл, но, как только значение a станет меньше или равным b, выполнится условие if и сработает команда break, которая завершит цикл.
Цикл for необходим для выполнения команды или набора команд определенное количество раз или перебора набора данных.
Этот цикл похож на человека, выкладывающего продукты на кассе в магазине. Сколько бы ни было продуктов в корзине — он каждый достанет из корзины и положит на ленту, перебирая по очереди все продукты.
Структура записи цикла for:
Здесь мы сталкиваемся с понятием коллекции — той самой нашей «корзины с покупками», то есть какой-то структуры данных, содержащей много различных значений в себе. Пока что мы из таких типов структур данных знакомы со строками и списками из первой части статьи, а ниже в этой статье разберем еще одну — range.
Как работает цикл for? На каждом шаге цикла будет принимать новое значение из , после чего будет выполняться .
По традиции, если перебираемая переменная не несет в себе особой смысловой нагрузки, ее называют i, j или k.
может принимать любое значение, которое можно перебрать.
| a = «abcd» for i in a: print(i) |
Вывод: a b c d |
- перебор списка:
| a = [12, 34, 567, 8910] for i in a: print(i) |
Вывод: 12 34 567 8910 |
- перебор диапазона range, который создает набор целых чисел.
Команда range позволяет создавать диапазоны — последовательности целых чисел, отличающихся друг от друга на одно и то же число — разницу или шаг диапазона.
Есть несколько способов создания диапазона:
- range(a) — диапазон целых чисел от 0 до (a — 1) с шагом 1.
Например: range(5) — 0, 1, 2, 3, 4.
- range(a, b) — диапазон чисел от a до (b — 1) с шагом 1.
Например: range(2, 7) — 2, 3, 4, 5, 6.
- range(a, b, step) — диапазон чисел от a до (b — 1) с разницей между соседними числами, равной step.
Например: range(1, 17, 3) — 1, 4, 7, 10, 13, 16.
| for i in range(2, 6): print(i) |
Вывод: 2 3 4 5 |
Взаимозаменяемость циклов
Сейчас мы будем заниматься практикой, а заодно посмотрим, как с помощью разных циклов можно решить одну и ту же задачу.
Задача.
У нас есть список чисел a. Нужно вывести на экран его содержимое, по одному числу в строке.
Решение №1.
Чтобы выполнить задачу, нам необходимо перебрать каким-то циклом все его элементы и каждый вывести на экран. Тогда напрашивается самое очевидное решение:
for i in a:
print(i)
Мы берем каждый элемент списка и выводим его, все просто. Но это не единственный способ.
Решение №2.
Мы можем вместо элементов списка перебирать числа-позиции элементов в списке а и выводить на экран элементы на соответствующих позициях. Это можно сделать, например, так:
for i in range(len(a)):
print(a[i])
Здесь len(a) — это длина списка а. Мы используем ее, чтобы понять, до какого числа надо перебирать i, чтобы на i-тых позициях списка все еще были элементы. Это же можно тоже записать другим способом:
Разные подходы к применению циклов позволяют всегда выбирать наиболее удобный под конкретные задачи. Например, здесь нам не важны позиции элементов списка и проще всего было использовать первое решение. Но в разных контекстах задач могут быть разные преимущества и недостатки каждого из циклов.
Вложенные структуры
После знакомства с условными конструкциями и циклами разброс наших возможностей сильно возрастает. Но он возрастет еще сильнее, если мы научимся правильно их комбинировать и использовать одно в другом.
Для этого можем воспользоваться вложенными структурами, когда одна конструкция находится внутри другой.
Такой пример уже мелькнул — когда мы говорили о бесконечном цикле и команде break. Мы сделали так, что внутри цикла команда break выполнится только при истинности условия, для чего прямо внутри цикла while мы использовали условную конструкцию if.
Чтобы программа «не сошла с ума», пытаясь понять, где тело цикла, а где тело условия, мы продолжили использовать табуляцию.
Весь блок условия находится в цикле, поэтому табуляция цикла никуда не делась. Тело вложенного условия получает свою собственную табуляцию прямо поверх предыдущей. Эти разные табуляции отмечены зеленым и синим цветом.
Вложенные структуры — удобный способ повысить возможности программы. Здесь мы никак не ограничены: мы можем вкладывать циклы в циклы, условия в условия, циклы в условия и так далее. Количество вложений также ничем не ограничено.
| Важно запомнить: если друг в друга вкладывается несколько циклов for, их переменные должны иметь разные имена. |
Разберем в качестве примера следующий код:
n = 1
for i in range(3):
for j in range(2):
n += 2
n *= 3
print(n)
Какое число на экране будет в результате этой программы?
У нас есть внутренний цикл и внешний. Тело внутреннего цикла запускается дважды: при j = 0 и j =1. Каждый раз значение n увеличивается на 2. Значит, в процессе работы внутреннего цикла значение n увеличивается на 2 * 2 = 4.
Тогда тело внешнего цикла — прибавление к n 4 и умножение на 3. Цикл повторяется трижды — i принимает значения 0, 1, 2. Тогда после первой итерации внешнего цикла n=(1+4)*3=15, после второй итерации n=(15+4)*3=57, после третьей — n=(57+4)*3=183.
На экран будет выведено 183.
Импорт модулей
Для еще большего увеличения мощи нашей программы мы можем использовать модули — наборы инструментов с готовыми решениями части наших задач.
Это легко сравнить с проведением ремонта в квартире. Мы можем что-то сделать простыми инструментами, которые лежат на балконе. Но гораздо эффективнее будет съездить в магазин за специальными инструментами. Так мы не только шкаф — ракету соберем.
Какие есть модули и какие в них есть инструменты — мы будем изучать по мере необходимости. Сейчас главное — узнать, как именно это делается. И делать мы это будем на примере модуля math, в котором лежит прекрасная функция sqrt. Она умеет извлекать корни чисел.
Если вдруг случилось так, что вы совсем забыли, как извлекаются корни чисел, то советуем обратиться к нашей статье по математике «Понятие корня».
Для получения инструментов модуля необходимо произвести его импорт — добавление модуля или его частей в программу. Сделать это можно несколькими способами:
import math
При такой записи доступ к конкретной функции мы получим, прописав название этого модуля, после него через точку — название необходимой функции.
- Импорт всех функций модуля:
from math import *
При такой записи в нашу программу попадают вообще все функции модуля, для доступа к которым теперь не нужно прописывать название самого модуля.
- Импорт конкретных функций модуля:
from math import sqrt
Такая запись даст нам доступ только к конкретным функциям из всего модуля, которые мы импортируем.
Понимание условий и циклов необходимо для решения любых задач на программирование. Разберем пример задачи №6 ОГЭ.
Дана программа на языке программирования Python:
a = int(input())
b = int(input())
if a == 15 or b == 50:
print(“Да”)
else:
print(“Нет”)
Было проведено 9 запусков. В качестве переменных a и b пользователь вводил следующие значения. Первое значение – переменная a, второе значение – переменная b.
(15; 19); (19; 50); (10; 26); (10; 56); (8; 50); (10; 10); (50; 50); (10; 2); (10; 40).
Определите количество запусков, при которых программа выведет «Да».
Решение.
Заметим, что программа печатает «Да», если a = 15 или b = 50, то есть выполнение хотя бы одного из равенств говорит о том, что программа выведет «Да».
Проверим пары чисел на условия:
— (15; 19) — выполнено a = 15;
— (19; 50) — выполнено b = 50;
— (10; 26) — не выполнено;
-(10; 56) — не выполнено;
— (8; 50) — выполнено b = 50;
— (10; 10) — не выполнено;
— (50; 50) — выполнено b = 50;
— (10; 2) — не выполнено;
— (10; 40) — не выполнено.
Нам подойдут все пары, кроме тех, где написано «не выполнено». Их всего 4 штуки.
Ответ: 4
Существует математическое доказательство того, что с помощью циклов и условий можно реализовать совершенно любой алгоритм. Но использование циклов и условий — только самый базовый уровень программирования, и какие-то сложные вещи нам останутся недоступны.
Это все равно что собирать автомобиль, имея под рукой только листы металла. Дальше вы узнаете про много особенностей языка, упрощающих создание алгоритмов, чтобы заменить эти листы металла на заготовки деталей и прочие более удобные для сборки элементы. Но прежде чем работать с более высокоуровневыми конструкциями, надо попрактиковаться в работе с уже пройденным материалом, например, в этой статье.
Фактчек
- Табуляция — способ структуризации кода, где отдельные блоки кода выделяются отступами.
- Условная конструкция if-elif-else необходима для выполнения определенных блоков кода при определенных исходах условия.
- Циклы нужны для многократного повторения блока кода. Цикл while выполняет блок кода, пока выполняется переданное ему условие; цикл for перебирает переданные ему значения.
- Импортируя модули, мы можем получить доступ к функциям, которые изначально в программе доступны не были.
Проверь себя
Задание 1.
Без запуска кода определите, что будет выведено на экран в результате выполнения программы:
Задание 2.
Без запуска кода определите, что будет выведено на экран в результате выполнения программы:
x = 250
if x < 100:
print(x + 25)
elif x print(x — 100)
Задание 3.
Без запуска кода определите, что будет выведено на экран в результате выполнения программы:
b = 0
for i in range(5):
b = b + i
print(b)
Задание 4.
Без запуска кода определите, что будет выведено на экран в результате выполнения программы:
x = 50
y = 20
while x < y:
x -= 20
print(x)
Ответы: 1. — 4; 2. — 3; 3. — 3; 4. — 3.