Модуль 1. Введение в Python. Целочисленная арифметика. Модуль Введение в Python. Целочисленная арифметика
 Скачать 0.92 Mb.
|
|
Модуль 1. Введение в Python. Целочисленная арифметика Основным инструментом при освоении курса является язык программирования Python. Python – простой в освоении и, в то же время, мощный современный язык программирования, работающий на большинстве платформ, пример свободного и открытого программного обеспечения Язык разрабатывается чуть более 20 лет, первая версия Python увидела свет в феврале 1991 года. Создатель языка нидерландский программист Гвидо ван Россум (Guido van Rossum). В настоящее время существуют две версии языка более старая 2 и современная 3. Старая версия больше не развивается, но до сих пор ещё используется, поскольку существует много программного обеспечения разработанного в этой версии. Между версиями есть существенные несовместимости. Мы будем использовать 3 версию как более современную и совершенную ([1], [2]). Python – современный универсальный интерпретируемый язык программирования, его достоинства: кроссплатформенность и бесплатность; простой синтаксис и богатые возможности, которые позволяют записывать программы очень кратко и понятно; При всей своей кажущейся простоте используется в разработке реальных приложений в различных областях. Скачать дистрибутив последней версии Python нужно на cайтe http://python.org. Программный код на языке можно записывать с помощью любого простого текстового редактора. По умолчанию предполагается, что файлы с программным кодом на языке Python сохраняются в кодировке utf-8, и, как правило, имеют расширение py. Для удобства разработки кода программисты используют среды разработки (IDE). Вместе с установкой интерпретатора устанавливается среда разработки IDLE, которая обеспечивает интерактивный и файловый режим. Для демонстрации примеров в курсе будет использоваться Jupyter Notebook — это командная оболочка для интерактивных вычислений. Этот инструмент может использоваться не только с Python, но и сдругими языками. Он часто используется для работы с данными, статистическим моделированием и машинным обучением. Устанавливается Jupyter как любой модуль Python, с помощью команды pip. Еще одна среда разработки, с которой мы будем работать – Pycharm, компании JetBrains. Переменные. Базовые типы данных Описание любого языка программирования состоит из задания синтаксиса и семантики. Для языка определяется алфавит: набор символов языка и лексемы: т.е. все наборы символов из заданного алфавита, которые являются синтаксически правильными конструкциями данного языка, имеющими смысл для транслятора. Семантика – смысл синтаксически правильных конструкций. Рис. 1 Одна из фундаментальных особенностей любого языка программирования заключается в способности представлять и обрабатывать данные различных типов. В языке Python выделяется несколько базовых типов, для начала, рассмотри числа, целые и действительные, и строки. Python – язык с динамической типизацией, переменная в каждый момент времени имеет определенный тип, но этот тип может меняться по ходу выполнения программы, достаточно просто присвоить ей новое значение другого типа. На самом деле переменная в Python является лишь ссылкой на объект в памяти [3] (Рис. 1). Описывать переменные заранее не нужно, переменная появляется, когда появляется объект, на который нужно ссылаться. Когда мы встречаем операцию присваивания, то переменная ( имя), например, x создается автоматически, все остальные присваивания меняют значение, ассоциированное с этим именем. Переменные не имеют никакой информации о типе, тип присущ объектам, а переменные лишь ссылки на конкретные объекты в конкретные моменты времени. При этом объекты имеют более сложную организацию, чем просто пространство памяти, каждый объект еще имеет описатель типа и счетчик ссылок. Когда переменная встречается в выражение, ее имя заменяется объектом, на который она в данный момент ссылается. Оператор присваивания = связывает переменную, ссылку на объект, с объектом. В Python есть особый универсальный и удобный способ обмена значениями двух переменных (Рис. 2). Рис. 2 Имена, используемые для идентификации различных объектов в программе, в частности переменных, называются идентификаторами. Идентификаторы не могут совпадать с ключевыми словами, должны начинаться с алфавитного символа или с символа подчеркивания, за которым следует ноль или более алфавитных символов, символов подчеркивания или цифр. Идентификаторы не ограничены по длине и чувствительны к регистру (Рис. 3). Определить какой тип у объекта можно с помощью функции type(). Тип данных определяет, каким образом данные хранятся в памяти и какие операции можно к ним применять. Рис. 3 Целые числа в Python – тип int [4]. Литералы целых (литералы – запись в программе, представляющая собой фиксированное значение некоторого типа) записываются как последовательность цифр, перед которой также может стоять знак минус. По умолчанию записываются в 10-ой системе счисления, но могут быть представлены и в 2-ой, 8-ой или 16-ой, запись, соответственно, начинается с 0b, 0o, 0x. Размеры чисел ограничиваются только объемом памяти компьютера, как и строки. Основные операции для целых типов изображены в таблице Таблица 1. Таблица 1 Операции Описание A + B сумма A - B разность A * B произведение A % B взятие остатка от деления A на B A // B взятие целой части от деления A на B A ** B возведение в степень Действительные числа – тип float. Литералы записываются как последовательность цифр, перед которой также может стоять знак минус. В качестве разделителя целой и дробной части используется точка. Основные операции сдействительными числами изображены в таблице Таблица 2. Таблица 2 Операции Описание A + B сумма A - B разность A * B произведение A / B частное, результатом этого действия является вещественное число, даже если A нацело делится на B Приоритет операций: действия в скобках; возведение в степень справа налево; унарные операции; операции умножения и деления слева направо; операции сложения и вычитания слева направо. Для изменения порядка используйте скобки. Примеры изображены на Рис. 4. Рис. 4 Строки в Python имеют тип str. Строка – последовательность символов алфавита: буквы, цифры, знаки препинания и т.д. Литералы строк, набор символов в двойных или одинарных кавычках. Основные операции для строк – конкатенация и повторение (Таблица 3). Таблица 3 Операции Описание A + B конкатенация (строка B приписывается к строке A) A * n повторение n раз, значение n должно быть натуральным Рис. 5 Для преобразования типов используются функции с именами, совпадающими с названием типов, то есть int(), float(), str() и т.д. Примеры преобразований на Рис. 5. Ввод и вывод Для считывания со стандартного ввода используется функция input(), считанное значение сразу же можно присвоить переменной. Функция input() возвращает текстовую строку, для преобразования в другой тип нужно использовать функции перевода, удобно это сделать одной командой. У input() есть специальный параметр, который выводится на экран при вызове input(). Используйте аккуратно для заданий с автоматической проверкой (Рис. 6). Рис. 6 При считывании нескольких значений из одной строки используется метод split(), который разделяет строку на части по разделителям, по умолчанию по пробелам, в результате получаем кортеж элементов, набор строк. В параметрах split() можно указать другой разделитель (Рис. 7). Рис. 7 Можно также сразу же преобразовать считанные значения в другой тип, например числовой, если воспользоваться функцией map(), которая применяет к каждому элементу набора заданную функцию (Рис. 7). Для вывода используется функция print() (Рис. 8), функция может выводить не только значения переменных, но и значения любых выражений. У функции есть два специальных именованных параметра sep и end. Рис. 8 Параметр sep задает строку, используемую в качестве разделителя (sep – аббревиатура от слова separator, т.е. разделитель). По умолчанию параметр sep равен строке из одного пробела и между значениями выводится пробел, но можно поменять на любой другой разделитель например ‘*’, выводить без разделителя или с новой строки (Рис. 9). Рис. 9 Символ обратного слэша в текстовых строках является указанием на обозначение специального символа, в зависимости от того, какой символ записан после него. Наиболее часто употребляется символ перевода на новую строки '\n'. Параметр end указывает на то, что выводится после вывода всех значений, перечисленных в функции print(). По умолчанию параметр end равен переводу на новую строку '\n'. Можно одновременно использовать оба параметра (Рис. 9). Целочисленная арифметика При реализации многих теоретико-числовых алгоритмов таких, как проверка на простоту, алгоритм Евклида, и многих других используются целые типы данных и, соответственно, целочисленные операции, которые имеют свои особенности. Рассмотрим на простых примерах особенности округления при целочисленном делении. В Python, так же как в Си, можно использовать сокращенную форму записи операций (Рис. 10). Рис. 10 Теперь остановимся на особенностях операций целочисленного деления. Напомним правила целочисленной арифметики. Если есть два целых числа 𝐴 и 𝐵 (𝐵 ≠ 0), то деление 𝐴 на 𝐵 с остатком – это нахождение таких целых чисел Q (частное) и R (остаток), что 𝐴 = 𝐵 ∗ 𝑄 + 𝑅, при этом, если B > 0, то 0 <= R < B, а если B < 0, то B < R <= 0. Остаток имеет такой же знак, что и делитель. Именно согласно этой теореме реализовано целочисленное деление в Python для положительных и отрицательных чисел, с округлением в меньшую сторону, в отличие от таких языков как Си и Паскаль, в которых используется так называемое округление к нулю или просто отбрасывание дробной части (Рис. 11). Разница возникает при делении чисел с разными знаками. При делении чисел с одинаковыми знаками значения получаются одинаковые. Рис. 11 Сведем полученные результаты а примере на рисунке в одну таблицу ( Рис. 12). Рис. 12 Рассмотрим простейшую задачу, в которой используется целочисленное деление с округлением вниз. Есть кольцевая дорога длиной 109 км, на каждом километре стоит столбик с отметкой, какой это километр, есть байкер, который едет по этой дороге со скоростью v. Эта скорость может быть как положительной, если Вася едет в одном направлении, так и отрицательной, если в противоположном. Время в пути t, определить на какой отметке остановится байкер. Решением данной задачи на Python является нахождение остатка от деления пройденного расстояния на109. При умножении скорости на время мы получаем, отрицательные или положительные значения, но при делении на положительное 109 остаток всегда положительный, так как округление вниз, этот остаток и будет решением (Рис. 13). Рис. 13 Другой тип задач требует округления в большую сторону. Еще одна задача про дорогу. За день машина проезжает n километров, сколько дней нужно, чтобы проехать маршрут длиной m километров. Конечно, можно реализовать условным оператором, но можно и составить одно выражение. Возможно два случая. Первый, когда m делится на n. В этом случае машина проходит m километров за m // n дней (Рис. 14). Рис. 14 Второй случай – m не делится на n, в этом случае машина проходит за m // n + 1 день (Рис. 15). Рис. 15 Нам нужно добавить к m такое значение, чтобы в первом случае остаться в этом же интервале, а во втором перейти в следующий. Рис. 16 В первом случае n-1 максимально возможное значение, для того, чтобы остаться в этом же интервале, во втором случае, минимум, где может находиться машина – значение x+1, и если прибавить n-1, то машина окажется в точке x+n, т.е. в начале следующего интервала, минимально возможное значение. Решение на Python представлено на рисунке Рис. 16. |