Программирование линейных, разветвляющихся и циклических алгоритмов в PYTHON

Лекция №1. программирование линейных, разветвляющихся и циклических алгоритмов в python СОДЕРЖАНИЕ 1.1 Простейшие программы (линейные) 1.2 Вычисления 1.3 Ветвления 1.4 Циклические алгоритмы 1.1 Простейшие программы (линейные) Программы на языке Python чаще всего выполняются интерпретатором, который читает очередную команду и сразу её выполняет, не переводя всю программу в машинный код конкретного процессора. Можно работать в двух режимах: • через командную строку (в интерактивном режиме), когда каждая введённая команда сразу выполняется; • в программном режиме, когда программа сначала записывается в файл (обычно имеющий расширение .py), и при запуске выполняется целиком; такая программа на Python называется скриптом (от англ. script = сценарий). Мы будем говорить, главным образом, о программном режиме. Пустая программа – это программа, которая ничего не делает, но удовлетворяет требованиям выбранного языка программирования. Пустая программа на Pythоn (в отличие от многих других языков программирования) – действительно пустая, она не содержит ни одного оператора (команды). Можно добавить в программу комментарий – пояснение, которое не обрабатывается транслятором: # Это пустая программа Как вы уже увидели, комментарий начинается знаком #. Если в программе используются русские буквы, в самом начале обычно записывают специальный комментарий, определяющий кодировку: # -*- coding: utf-8 -*- В данном случае указана кодировка UTF‐8. В Python 3 она установлена по умолчанию, поэтому эту строчку можно не писать. Напишем программу, которая выводит на экран такие строки: 2+2=? Ответ: 4 Вот как она выглядит: Команда print выводит на экран символы, заключенные в апострофы или в кавычки. После выполнения той команды происходит автоматический переход на новую строчку. Строго говоря, print – это функция языка Python. В лекции №1 рассматривается версия языка Python 3, которая несколько отличается от предыдущих версий. Переменные Напишем программу, которая выполняет сложение двух чисел: 1) запрашивает у пользователя два целых числа; 2) складывает их; 3) выводит результат сложения. Программу на псевдокоде (смеси русского языка и Python) можно записать так: ввести два числа сложить их вывести результат Компьютер не может выполнить псевдокод, потому что команд «ввести два числа» и ей подобных нет в его системе команд. Поэтому нам нужно «расшифровать» все такие команды, выразив их через операторы языка программирования. В отличие от предыдущей задачи, данные нужно хранить в памяти. Для этого используют переменные. Переменная — это величина, которая имеет имя, тип и значение. Значение переменной может изменяться во время выполнения программы. Переменная (как и любая ячейка памяти) может хранить только одно значение. При записи в неё нового значения «старое» стирается и его уже никак не восстановить. В языке Python (в отличие от многих других языков) переменные не нужно предварительно объявлять. Они создаются в памяти при первом использовании, точнее, при первом присваивании им значения. Например, при выполнении оператора присваивания a = 4 в памяти создается новая переменная (объект типа «целое число») и она связывается с именем a. По этому имени теперь можно будет обращаться к переменной: считывать и изменять её значение. В именах переменных можно использовать латинские буквы (строчные и заглавные буквы различаются), цифры (но имя не может начинаться с цифры, иначе транслятору будет сложно различить, где начинается имя, а где – число) и знак подчеркивания «_». Желательно давать переменным «говорящие» имена, чтобы можно было сразу понять, какую роль выполняет та или иная переменная. Тип переменной в Python определяется автоматически. Программа a = 4 print(type(a)) выдаёт на экран тип (англ. type) переменной a: В данном случае переменная a целого типа, на это указывает слово int (сокращение от англ. Integer – целый). Говорят, что переменная a относится к классу int. Тип переменной нужен для того, чтобы • определить область допустимых значений переменной; • определить допустимые операции с переменной; • определить, какой объем памяти нужно выделить переменной и в каком формате будут храниться данные. В языке Python используется динамическая типизация, это значит, что тип переменной определяется по значению, которое ей присваивается (а не при объявлении переменной, как с языках Паскаль и C). Таким образом, в разных частях программы одна и та же переменная может хранить значения разных типов. Вспомним, что нам нужно решить три подзадачи: • ввести два числа с клавиатуры и записать их в переменные (назовём их a и b); • сложить эти два числа и записать результат в третью переменную c; • вывести значение переменной c на экран. Для ввода используется команда input, результат работы которой можно записать в переменную, например, так: a = input() При выполнении этой строки система будет ожидать ввода с клавиатуры и, когда пользователь введёт число и нажмёт клавишу Enter, запишет это значение в переменную a. При вызове функции input в скобках можно записать сообщение‐подсказку: a = input("Введите целое число: ") Сложить два значения и записать результат в переменную c очень просто: c = a + b Символ «=» – это оператор присваивания, с его помощью изменяют значение переменной. Он выполняется следующим образом: вычисляется выражение справа от символа «=», а затем результат записывается в переменную, записанную слева. Поэтому, например, оператор i = i + 1 увеличивает значение переменной i на 1. Вывести значение переменной c на экран с помощью уже знакомой функции print: print ( c ) Казалось бы, теперь легко собрать всю программу: a = input() b = input() c = a + b print ( c ) однако, после того, как мы запустим её и введём какие‐то числа, допустим 21 и 33, мы увидим странный ответ 2133. Вспомните, что при нажатии клавиши на клавиатуре в компьютер поступает её код, то есть код соответствующего символа. И входные данные воспринимаются функцией input именно как поток символов. Поэтому в той программе, которая приведена выше, переменные a и b – это цепочки символов, при сложении этих цепочек (с помощью оператора «+») программа просто объединяет их – приписывает вторую цепочку в конец первой. Чтобы исправить эту ошибку, нужно преобразовать символьную строку, которая получена при вводе, в целое число. Это делается с помощью функции int (от англ. integer – целый): a = int ( input() ) b = int ( input() ) Возможны еще другие варианты ввода, они будут рассмотрены позже. Итак, после того, как мы преобразовали введённые значения в формат целых чисел, программа работает правильно – складывает два числа, введённые с клавиатуры. Однако у неё есть два недостатка: 1) перед вводом данных пользователь не знает, что от него требуется (сколько чисел нужно вводить и каких); 2) результат выдается в виде числа, которое означает неизвестно что. Хотелось бы, чтобы диалог программы с пользователем выглядел так: Введите два целых числа: 2 3 2+3=5 Подсказку для ввода вы можете сделать самостоятельно. При выводе результата ситуация несколько усложняется, потому что нужно вывести значения трёх переменных и два символа: «+» и «=». Для этого строится список вывода, элементы в котором разделены запятыми: print ( a, "+", b, "=", c ) Мы почти получили нужный результат, но почему‐то знаки «+» и «=» отделены лишними пробелами, который мы «не заказывали»: 2 + 3 = 5 Действительно, функция print вставляет между выводимыми значениями так называемый разделитель (или сепаратор, англ. separator). По умолчанию разделитель – это пробел, но мы можем его изменить, указав новый разделитель после слова sep: print ( a, "+", b, "=", c, sep = "" ) Здесь мы установили пустой разделитель (пустую строку). Теперь все работает как надо, лишних пробелов нет. В принципе, можно было бы обойтись и без переменной c, потому что элементом списка вывода может быть арифметическое выражение, которое сразу вычисляется и на экран выводится результат: print ( a, "+", b, "=", a+b, sep = "" ) В Python можно использовать форматный вывод: указать общее количество знакомест, отводимое на число. Например, программа a = 123 print ( "{:5d}".format(a) ) выведет значение целой переменной a, заняв ровно 5 знакомест: ◦◦123 Поскольку само число занимает только 3 знакоместа, перед ним выводятся два пробела, которые обозначены как «◦». Фигурные скобки в строке перед словом format показывают место, где будет выведено значение, записанное в скобках после этого слова (это аргумент функции format – данные, которые ей передаются). Запись «:5d» означает, что нужно вывести целое число в десятичной системе счисления (англ. decimal – десятичный) в пяти позициях. Можно выводить сразу несколько значений, например, так a = 5 print ( "{:5d}{:5d}{:5d}".format (a, a*a, a*a*a) ) Значения, которые должна вывести функция format, перечислены в скобках через запятую. Результат будет такой: ◦◦◦◦5◦◦◦25◦◦125 Контрольные вопросы (для ответа на тест) 1. Опишите правила построения имён переменных в языке Python. 2. Как записываются комментарии на Python? Подумайте, как комментирование можно использовать при поиске ошибок в алгоритме? 3. Расскажите о работе оператора вывода Python. 4. Что такое переменная? Как транслятор определяет тип переменной? 5. Зачем нужен тип переменной? 6. Как изменить значение переменной? 7. Что такое оператор присваивания? 8. Почему желательно выводить на экран подсказку перед вводом данных? 9. Подумайте, когда можно вычислять результат прямо в операторе вывода, а когда нужно заводить отдельную переменную. 10. Что такое форматный вывод? Как вы думаете, где он может быть полезен? 1.2 Вычисления В курсе программирования можно выделить две важнейшие составляющие – алгоритмы и способы организации данных. В этом параграфе мы познакомимся с простейшими типами данных. В следующих разделах рассматриваются основные алгоритмические конструкции: ветвления, циклы, подпрограммы. В конце главы подробно изучаются сложные (составные) типы данных: списки, символьные строки, а также работа с файлами. Типы данных Перечислим основные типы данных в языке Python: • int – целые значения; • float – вещественные значения (могут быть с дробной частью); • bool – логические значения, True (истина, «да») или False (ложь, «нет»); • str – символ или символьная строка, то есть цепочка символов. Кроме них есть ещё и другие, с ними мы познакомимся позже. Тип переменной определяется в тот момент, когда её присваивается новое значение. Для определения типа переменной можно использовать стандартную функцию type. Например, программа a = 5 print(type(a)) a = 4.5 print( type(a) ) a = True print( type(a) ) a = "Вася" print( type(a) ) выдаст на экран такой результат: Сначала в переменной a хранится целое значение 5, и её тип – целый (int). Затем мы записываем в неё вещественное значение 4.5, переменная будет вещественного типа (float, от англ. floating point – с плавающей точкой). Третье присваивание – логическое значение (bool, от англ. boolean – булевская величина, в честь Дж. Буля). Последнее значение – символьная строка (str, от англ. string – строка), которая записывается в апострофах или в кавычках. Целые переменные в Python могут быть сколь угодно большими (или, наоборот, маленькими, если речь идет об отрицательных числах): транслятор автоматически выделяет область памяти такого размера, который необходим для сохранения результата вычислений. Поэтому в Python легко (в отличие от других языков программирования) точно выполнять вычисления с большим количеством значащих цифр. Вещественные переменные, как правило, занимают 8 байтов, что обеспечивает точность 15 значащих десятичных цифр. Большинство вещественных чисел хранится в памяти неточно, и в результате операций с ними накапливается вычислительная ошибка. Поэтому для работы с целочисленными данными не стоит использовать вещественные переменные. Логические переменные относятся к типу bool и принимают значения True (истина) или False (ложь). Знакомство с символьными строками мы отложим на следующий раздел. Как вы увидели, одна и та же переменная в различных частях программы может хранить значения различных типов. Дело в том, что в Python имя переменной связывается с некоторым объектом, этот объект имеет определённый тип и содержит данные. При выполнении оператора a = 5 в памяти создаётся объект – ячейка для хранения целого числа, которая связывается с именем a (рис. а). Затем команда a = 4.5 создаёт в памяти другой объект (для хранения вещественного числа) и переставляет ссылку для имени a (рис. б). Объект, на который не ссылается ни одно имя, удаляется из памяти «сборщиком мусора». Если выполнить оператор b = a то два имени будут связаны с одним и тем же объектом (рис. в). Можно было бы подумать, что изменение одной из переменных приведет к такому же изменению другой. Однако для чисел это не так. Дело в том, что при присваивании a = 10 в памяти будет создан новый объект – целое число 10, который связывается с именем a (рис. г). Это отличается от других языков программирования, где в таких случаях просто изменяется значение той же самой ячейки памяти. Арифметические выражения и операции Арифметические выражения в любом языке программирования записываются в строчку, без многоэтажных дробей. Они могут содержать числа, имена переменных, знаки арифметических операций, круглые скобки (для изменения порядка действий) и вызовы функций. Например, a =(c + 5 - 1) / 2*d Если запись длинного выражения не поместилась в одной строке на экране, её можно перенести на следующую с помощью знака «\» (он называется «обратный слэш»): a =(c + 5 - 1) \ / 2*d При переносе внутри скобок знак «\» вставлять не обязательно: a =(c + 5 - 1) / 2*d Эти правила переноса справедливы и для других операторов языка Python. При определении порядка действий используется приоритет (старшинство) операций. Они выполняются в следующем порядке: • действия в скобках; • возведение в степень (**), справа налево; • умножение (*) и деление (/), слева направо; • сложение и вычитание, слева направо. Таким образом, умножение и деление имеют одинаковый приоритет, более высокий, чем сложение и вычитание. Поэтому в приведенном примере значение выражения, заключенного в скобки, сначала разделится на 2, а потом – умножится на d. В Python разрешено множественное присваивание. Запись a = b = 0 равносильна паре операторов b = 0 a = b Так же, часто используют сокращенную запись арифметических операций: сокращенная запись полная запись Если в выражение входят переменные разных типов, в некоторых случаях происходит автоматическое приведение типа к более «широкому». Например, результат умножения целого числа на вещественное – это вещественное число. Переход к более «узкому» типу автоматически не выполняется. Нужно помнить, что результат деления (операции «/») – это вещественное число, даже если делимое и делитель – целые и делятся друг на друга нацело. Часто нужно получить целый результат деления целых чисел и остаток от деления. В этом случае используют соответственно операторы «//» и «%»(они имеют такой же приоритет, как умножение и деление): d = 85 a = d // 10 # = 8 b = d % 10 # = 5 Обратим внимание на результат выполнения этих операций для отрицательных чисел. Программа print ( -7 // 2 ) print ( -7 % 2 ) выдаст на экран числа «–4» и 1. Дело в том, что с точки зрения теории чисел остаток – это неотрицательное число, поэтому –7 = (–4)‧2+1, то есть частное от деления (–7) на 2 равно –4, а остаток равен 1. Поэтому в Python (в отличие от многих других языков, например, Паскаля и Си) эти операции выполняются математически правильно. В Python есть операция возведения в степень, которая обозначается двумя звездочками: «**». Например, выражение y = 2x2 + z3 запишется так: y = 2*x**2 + z**3 Возведение в степень имеет более высокий приоритет, чем умножение и деление. Вещественные значения При записи вещественных чисел в программе целую и дробную часть разделяют не запятой (как принято в отечественной математической литературе), а точкой. Например x = 123.456 Вещественные значения по умолчанию выводятся на экран с большим количеством значащих цифр, например: x = 1/3 print ( x ) # 0.3333333333333333 При выводе очень больших или очень маленьких чисел используется так называемый научный (или экспоненциальный) формат. Например, программа: x = 100000000000000000/3 print ( x ) выведет 3.3333333333333332e+16 что означает 3,3333333333333332‧1016 , то есть до буквы «e» указывают значащую часть числа, а после нее – порядок. Часто используют форматный вывод: все данные, которые нужно вывести, сначала преобразуют в символьную строку с помощью функции format: a = 1/3 print ( "{:7.3f}".format(a) ) В данном случае использован формат «7.3f», который определяет вывод числа с фиксированной запятой (f от англ. fixed – фиксированный) в 7 позициях с тремя знаками в дробной части: ◦◦0.333 Поскольку эта запись занимает 5 позиций (а под нее отведено 7), перед числом добавляются два пробела, обозначенные знаком «◦». Можно использовать форматный вывод для нескольких значений сразу (список этих значений заключается в круглые скобки): a = 1/3 b = 1/9 print ( "{:7.3f} {:7.3f}".format(a, b) ) #◦◦0.333◦◦◦0.111 Запись «%e» обозначает экспоненциальный формат: print ( "{:10.3e} {:10.3e}".format(a, b) ) Здесь числа 10 и 3 – это общее количество позиций и число знаков после десятичной точки в записи значащей части: ◦3.333e-01◦◦1.111e-01 Стандартные функции Библиотека языка Python содержит большое количество готовых функций, которые можно вызывать из программы. Некоторые функции встроены в ядро языка, например, для вычисления модуля числа используется функция abs: print ( abs(-1.2) ) # 1.2 Существуют встроенные функции для перехода от вещественных значений к целым: • int(x) – приведение вещественного числа x к целому, отбрасывание дробной части; • round(x) – округление вещественного числа x к ближайшему целому. Большинство стандартных функций языка Python разбиты на группы по назначению, и каждая группа записана в отдельный файл, который называется модулем. Математические функции собраны в модуле math: • sqrt(x) – квадратный корень числа x ; • sin(x) – синус угла x , заданного в радианах; • cos(x) – косинус угла x , заданного в радианах; • exp(x) – экспонента числа x ; • log(x) – натуральный логарифм числа x . Для подключения этого модуля используется команда импорта (загрузки модуля): import math После этого для обращение к функциям используется так называемая точечная запись: указывают имя модуля и затем через точку название функции: print ( math.sqrt(x) ) Можно поступить по‐другому: загрузить в рабочее пространство все функции модуля: from math import * Теперь к функциям модуля math можно обращаться так же, как к встроенным функциям: print ( sqrt(x) ) Этот способ обладает серьёзным недостатком: в рабочем пространстве появляется много дополнительных имён, которые могут совпасть с именами функций, объявленных в других модулях. Поэтому без острой необходимости лучше так не делать. Третий вариант – загрузить только нужные функции from math import sqrt, sin, cos В этом случае все функции модуля math, кроме перечисленных (sqrt, sin, cos) будут недоступны. Случайные числа В некоторых задачах необходимо моделировать случайные явления, например, результат бросания игрального кубика (на нём может выпасть число от 1 до 6). Как сделать это на компьютере, который по определению «неслучаен», то есть строго выполняет заданную ему программу? Случайные числа – это последовательность чисел, в которой невозможно предсказать следующее число, даже зная все предыдущие. Чтобы получить истинно случайные числа, можно, например, бросать игральный кубик или измерять какой‐то естественный шумовой сигнал (например, радиошум или электромагнитный сигнал, принятый из космоса). На основе этих данных составлялись и публиковались таблицы случайных чисел, которые использовали в разных областях науки. Вернёмся к компьютерам. Ставить сложную аппаратуру для измерения естественных шумов или космического излучения на каждый компьютер очень дорого, и повторить эксперимент будет невозможно – завтра все значения будут уже другие. Существующие таблицы слишком малы, когда, скажем, нужно получать 100 случайных чисел каждую секунду. Для хранения больших таблиц требуется много памяти. Чтобы выйти из положения, математики придумали алгоритмы получения псевдослучайных («как бы случайных») чисел. Для «постороннего» наблюдателя псевдослучайные числа практически неотличимы от случайных, но они вычисляются по некоторой математической формуле: зная первое число («зерно») можно по формуле вычислить второе, затем третье и т.п. Функции для работы с псевдослучайными числами собраны в модуле random. Для получения псевдослучайных чисел в заданном диапазоне используют функции: • random() – случайное вещественное число из полуинтервала [0,1); • randint(a,b) – случайное целое число из отрезка [a,b] . Для того, чтобы записать в переменную n случайное число в диапазоне от 1 до 6 (результат бросания кубика), можно использовать такие операторы: from random import randint n = randint(1,6) Вещественное случайное число в полуинтервале от 5 до 12 (не включая 12) получается так: from random import random x = 7*random() + 5 Контрольные вопросы (для ответа на тест) 1. Какие типы данных вы знаете? 2. Какие данные записываются в логические переменные? 3. Расскажите об особенностях переменных в языке Python. Почему может получиться, что изменение одной переменной автоматически приводит к изменению другой? 4. Что такое приоритет операций? Зачем он нужен? 5. В каком порядке выполняются операции, если они имеют одинаковый приоритет? 6. Зачем используются скобки? 7. Что происходит, если в выражения входят переменные разных числовых типов? Какого типа будет результат? 8. Опишите операции // и %. 9. Расскажите о проблеме вычисления остатка от деления в различных языках программирования. 10. Какие стандартные математические функции вы знаете? В каких единицах задается аргумент тригонометрических функций? 11. Как выполнить округление вещественного числа к ближайшему целому? 12. Какие числа называют случайными? Зачем они нужны? 13. Как получить «естественное» случайное число? Почему такие числа почти не используются в цифровой технике? 14. Чем отличаются псевдослучайные числа от случайных? 15. Какие функции для получения псевдослучайных чисел вы знаете? 1.3. Ветвления Условный оператор Возможности, описанные в предыдущих параграфах, позволяют писать линейные программы, в которых операторы выполняются последовательно друг за другом, и порядок их выполнения не зависит от входных данных. В большинстве реальных задач порядок действий может несколько изменяться, в зависимости от того, какие данные поступили. Например, программа для системы пожарной сигнализации должна выдавать сигнал тревоги, если данные с датчиков показывают повышение температуры или задымленность. Для этой цели в языках программирования предусмотрены условные операторы. Например, для того, чтобы записать в переменную M максимальное из значений переменных a и b, можно использовать оператор: if a > b: M = a else: M = b Слово if переводится с английского языка как «если», а слово else – как «иначе». Если верно (истинно) условие, записанное после ключевого слова if, то затем выполняются все команды (блок команд), которые расположены до слова else. Если же условие после if неверно (ложно), выполняются команды, стоящие после else. В Python, в отличие от других языков, важную роль играют сдвиги операторов относительно левой границы (отступы). Обратите внимание, что слова if и else начинаются на одном уровне, а все команды внутренних блоков сдвинуты относительно этого уровня вправо на одно и то же расстояние. Это позволяет не использовать особые ограничители блоков (слова begin и end в языке Паскаль, фигурные скобки в Си‐подобных языках). Для сдвига используют символы табуляции (которые вставляются при нажатии на клавишу Tab) или пробелы. Если в блоке всего один оператор, иногда бывает удобно записать блок в той же строке, что и ключевое слово if (else): if a > b: M = a else: M = b В приведенных примерах условный оператор записан в полной форме: в обоих случаях (истинно условие или ложно) нужно выполнить некоторые действия. Программа выбора максимального значения может быть написана иначе: M = a if b > a: M = b Здесь использован условный оператор в неполной форме, потому что в случае, когда условие ложно, ничего делать не требуется (нет слова else и блока операторов после него). Поскольку операция выбора максимального из двух значений нужна очень часто, в Python есть встроенная функция max (аналогично min), которая вызывается так: M = max ( a, b ) Если выбирается максимальное из двух чисел, можно использовать особую форму условного оператора в Python: M = a if a > b else b которая работает так же, как и приведённый выше условный оператор в полной форме: записывает в переменную M значение a, если выполняется условие a > b, и значение b, если это условие ложно. Часто при каком‐то условии нужно выполнить сразу несколько действий. Например, в задаче сортировки значений переменных a и b по возрастанию нужно поменять местами значения этих переменных, если a > b: Все операторы, входящие в блок, сдвинуты на одинаковое расстояние от левого края. Заметим, что в Python, в отличие от многих других языков программирования, есть множественное присваивание, которое позволяет выполнить эту операцию значительно проще: a, b = b, a Кроме знаков < и >, в условиях можно использовать другие знаки отношений: <= (меньше или равно), >= (больше или равно), == (равно, два знака «=» без пробела, чтобы отличить от операции присваивания) и != (не равно). Внутри условного оператора могут находиться любые операторы, в том числе и другие условные операторы. Например, пусть возраст Андрея записан в переменной a, а возраст Бориса – в переменной b. Нужно определить, кто из них старше. Одним условным оператором тут не обойтись, потому что есть три возможных результата: старше Андрей, старше Борис и оба одного возраста. Решение задачи можно записать так: Условный оператор, проверяющий равенство, находится внутри блока иначе (else), поэтому он называется вложенным условным оператором. Как видно из этого примера, использование вложенных условных операторов позволяет выбрать один из нескольких (а не только из двух) вариантов. Если после else сразу следует еще один оператор if, можно использовать так называемое «каскадное» ветвление с ключевыми словами elif (сокращение от else-if): если очередное условие ложно, выполняется проверка следующего условия и т.д. Обратите внимание на отступы: слова if, elif и else находятся на одном уровне. Если в цепочке if-elif-elif-… выполняется несколько условий, то срабатывает первое из них. Например, программа при cost = 1500 выдает «Скидка 2%.», хотя условие cost < 5000 тоже выполняется. Сложные условия Предположим, что ООО «Рога и Копыта» набирает сотрудников, возраст которых от 25 до 40 лет включительно. Нужно написать программу, которая запрашивает возраст претендента и выдает ответ: «подходит» он или «не подходит» по этому признаку. На качестве условия в условном операторе можно указать любое логическое выражение, в том числе сложное условие, составленное из простых отношений с помощью логических операций (связок) «И», «ИЛИ» и «НЕ». В языке Python они записываются английскими словами «and», «or» и «not». Пусть в переменной v записан возраст сотрудника. Тогда нужный фрагмент программы будет выглядеть так: При вычислении сложного логического выражения сначала выполняются отношения (<, <=, >, >=, ==, !=) а затем – логические операции в таком порядке: сначала все операции not, затем – and, и в самом конце – or (во всех случаях – слева направо). Для изменения порядка действий используют круглые скобки. Иногда условия получаются достаточно длинными и их хочется перенести на следующую строку. Сделать это в Python можно двумя способами: использовать обратный слэш (это не рекомендуется): или взять все условие в скобки (перенос внутри скобок разрешён): В языке Python разрешены двойные неравенства, например означает то же самое, что и Контрольные вопросы (для ответа на тест) 1. Чем отличаются разветвляющиеся алгоритмы от линейных? 2. Как вы думаете, почему не все задачи можно решить с помощью линейных алгоритмов? 3. Как вы думаете, хватит ли линейных алгоритмов и ветвлений для разработки любой программы? 4. Почему нельзя выполнить обмен значений двух переменных в два шага: a=b; b=a? 5. Чем отличаются условные операторы в полной и неполной формах? Как вы думаете, можно ли обойтись только неполной формой? 6. Какие отношения вы знаете? Как обозначаются отношения «равно» и «не равно»? 7. Как организовать выбор из нескольких вариантов? 8. Что такое сложное условие? 9. Как определяется порядок вычислений в сложном условии? 1.4 Циклические алгоритмы Как организовать цикл? Цикл – это многократное выполнение одинаковых действий. Доказано, что любой алгоритм может быть записан с помощью трёх алгоритмических конструкций: циклов, условных операторов и последовательного выполнения команд (линейных алгоритмов). Подумаем, как можно организовать цикл, который 10 раз выводит на экран слово «привет». Вы знаете, что программа после запуска выполняется процессором автоматически. И при этом на каждом шаге нужно знать, сколько раз уже выполнен цикл и сколько ещё осталось выполнить. Для этого необходимо использовать ячейку памяти, в которой будет запоминаться количество выполненных шагов цикла (счётчик шагов). Сначала можно записать в неё ноль (ни одного шага не сделано), а после каждого шага цикла увеличивать значение ячейки на единицу. На псевдокоде алгоритм можно записать так (здесь и далее операции, входящие в тело цикла, выделяются отступами): Возможен и другой вариант: сразу записать в счётчик нужное количество шагов, и после каждого шага цикла уменьшать счётчик на 1. Тогда цикл должен закончиться при нулевом значении счётчика: Этот вариант несколько лучше, чем предыдущий, поскольку счётчик сравнивается с нулём, а такое сравнение выполняется в процессоре автоматически. В этих примерах мы использовали цикл с условием, который выполняется до тех пор, пока некоторое условие не становится ложно. Циклы с условием Рассмотрим следующую задачу: определить количество цифр в десятичной записи целого положительного числа. Будем предполагать, что исходное число записано в переменную n целого типа. Сначала нужно разработать алгоритм решения задачи. Чтобы подсчитывать что‐то в программе, нужно использовать переменную, которую называют счётчиком. Для подсчёта количества цифр нужно как‐то отсекать эти цифры по одной, с начала или с конца, каждый раз увеличивая счётчик. Начальное значение счётчика должно быть равно нулю, так как до выполнения алгоритма ещё не найдено ни одно цифры. Для отсечения первой цифры необходимо заранее знать, сколько цифр в десятичной записи числа, то есть нужно заранее решить ту задачу, которую мы решаем. Следовательно, этот метод не подходит. Отсечь последнюю цифру проще – достаточно разделить число нацело на 10 (поскольку речь идет о десятичной системе). Операции отсечения и увеличения счётчика нужно выполнять столько раз, сколько цифр в числе. Как же «поймать» момент, когда цифры кончатся? Несложно понять, что в этом случае результат очередного деления на 10 будет равен нулю, это и говорит о том, что отброшена последняя оставшаяся цифра. Изменение переменной n и счётчика для начального значения 1234 можно записать в виде таблицы. Псевдокод выглядит так: Программа на Python выглядит так: Слово while переводится как «пока», то есть, цикл выполняется пока n > 0. Переменная ‐счётчик имеет имя count. Обратите внимание, что проверка условия выполняется в начале очередного шага цикла. Такой цикл называется циклом с предусловием (то есть с предварительной проверкой условия) или циклом «пока». Если в начальный момент значение переменной n будет нулевое или отрицательное, цикл не выполнится ни одного раза. В данном случае количество шагов цикла «пока» неизвестно, оно равно количеству цифр введенного числа, то есть зависит от исходных данных. Кроме того, этот же цикл может быть использован и в том случае, когда число шагов известно заранее или может быть вычислено: Если условие в заголовке цикла никогда не нарушится, цикл будет работать бесконечно долго. В этом случае говорят, что «программа зациклилась». Например, если забыть увеличить переменную k в предыдущем цикле, программа зациклится: Во многих языках программирования существует цикл с постусловием, в котором условие проверяется после завершения очередного шага цикла. Это полезно в том случае, когда нужно обязательно выполнить цикл хотя бы один раз. Например, пользователь должен ввести с клавиатуры положительное число и защитить программу от неверных входных данных. В языке Python нет цикла с постусловием, но его можно организовать его с помощью цикла while: Однако такой вариант не очень хорош, потому что нам пришлось написать два раза пару операторов. Но можно поступить иначе: Цикл, который начинается с заголовка while True будет выполняться бесконечно, потому что условие True всегда истинно. Выйти из такого цикла можно только с помощью специального оператора break (в переводе с англ. – «прервать», досрочный выход из цикла). В данном случае он сработает тогда, когда станет истинным условие n > 0, то есть тогда, когда пользователь введет допустимое значение. Цикл с переменной Вернёмся снова к задаче, которую мы обсуждали в начале параграфа – вывести на экран 10 раз слово «привет». Фактически нам нужно организовать цикл, в котором блок операторов выполнится заданное число раз (в некоторых языках такой цикл есть, например, в школьном алгоритмическом языке он называется «цикл N раз»). На языке Python подобный цикл записывается так: Здесь слово for означает «для», переменная i (её называют переменной цикла) изменяется в диапазоне (in range) от 0 до 10, не включая 10 (то есть от 0 до 9 включительно). Таким образом, цикл выполняется ровно 10 раз. В информатике важную роль играют степени числа 2 (2, 4, 8, 16 и т.д.) Чтобы вывести все степени двойки от 21 до 210 мы уже можем написать такую программу с циклом «пока»: Вы наверняка заметили, что переменная k используется трижды (см. выделенные блоки): в операторе присваивания начального значения, в условии цикла и в теле цикла (увеличение на 1). Цикл с переменной «собирает» все действия с ней в один оператор: Здесь диапазон (range) задается двумя числами – начальным и конечным значением, причем указанное конечное значение не входит в диапазон. Такова особенность функции range в Python. Шаг изменения переменной цикла по умолчанию равен 1. Если его нужно изменить, указывают третье (необязательное) число в скобках после слова range – нужный шаг. Например, такой цикл выведет только нечётные степени числа 2 (21, 23 и т.д.): С каждым шагом цикла переменная цикла может не только увеличиваться, но и уменьшаться. Для этого начальное значение должно быть больше конечного, а шаг – отрицательный. Следующая программа печатает квадраты натуральных чисел от 10 до 1 в порядке убывания: Вложенные циклы В более сложных задачах часто бывает так, что на каждом шаге цикла нужно выполнять обработку данных, которая также представляет собой циклический алгоритм. В этом случае получается конструкция «цикл в цикле» или «вложенный цикл». Предположим, что нужно найти все простые числа в интервале от 2 до 1000. Простейший (но не самый быстрый) алгоритм решения такой задачи на псевдокоде выглядит так: Как же определить, что число простое? Как известно, простое число делится только на 1 и само на себя. Если число n не имеет делителей в диапазоне от 2 до n-1, то оно простое, а если хотя бы один делитель в этом интервале найден, то составное. Чтобы проверить делимость числа n на некоторое число k, нужно взять остаток от деления n на k. Если этот остаток равен нулю, то n делится на k. Таким образом, программу можно записать так (здесь n, k и count – целочисленные переменные, count обозначает счётчик делителей): Попробуем немного ускорить работу программы. Делители числа обязательно идут в парах, причём в любой паре меньший из делителей не превосходит (иначе получается, что произведение двух делителей, каждый из которых больше , будет больше, чем n). Поэтому внутренний цикл можно выполнять только до значения вместо n-1. Для того, чтобы работать только с целыми числами (и таким образом избежать вычислительных ошибок), лучше заменить условие k ≤ на равносильное ему условие k2 ≤ n. При этом потребуется перейти к внутреннему циклу с условием: Чтобы еще ускорить работу цикла, заметим, что когда найден хотя бы один делитель, число уже заведомо составное, и искать другие делители в данной задаче не требуется. Поэтому можно закончить цикл. Для этого при n%k == 0 выполним досрочный выход из цикла с помощью оператора break, причём переменная count уже не нужна: Если после завершения цикла k*k>n (нарушено условие в заголовке цикла), то число n простое. В любом вложенном цикле переменная внутреннего цикла изменяется быстрее, чем переменная внешнего цикла. Рассмотрим, например, такой вложенный цикл: На первом шаге (при i=1) переменная k принимает единственное значение 1. Далее, при i=2 переменная k принимает последовательно значения 1 и 2. На следующем шаге при i=3 переменная k проходит значения 1, 2 и 3, и т.д. Контрольные вопросы (для ответа на тест) 1. Что такое цикл? 2. Сравните цикл с переменной и цикл с условием. Какие преимущества и недостатки есть у каждого из них? 3. Что означает выражение «цикл с предусловием»? 4. В каком случае цикл с предусловием не выполняется ни разу? 5. В каком случае программа, содержащая цикл с условием, может зациклиться? 6. В каком случае цикл с переменной не выполняется ни разу? 7. Верно ли, что любой цикл с переменной можно заменить циклом с условием? Верно ли обратное утверждение? 8. В каком случае можно заменить цикл с условием на цикл с переменной? 9. Как будет работать приведенная программа, которая считает количество цифр введённого числа, при вводе отрицательного числа? Если вы считаете, что она работает неправильно, укажите, как её нужно доработать.