Линейные алгоритмы. Операции над целочисленными данными

Вопросы:

·     Линейные алгоритмы.

·     Правила записи арифметических выражений в языке Python.

·     Инструменты, применяемые для обработки целых чисел.

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

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

Мы уже знаем, что приоритет выполнения арифметических операций в языке Python аналогичен математическому. Таким образом, при записи математических выражений стоит учитывать, что сначала вычисляются выражения в скобках, после чего выполняются действия возведения в степень. Далее выполняются операции умножения и деления, и в последнюю очередь – операции сложения и вычитания. Таким образом, если записать в интерактивном режиме среды разработки выражение: 2 + 2 * 2, то его результатом будет 6. Но при этом результатом  выражения (2 + 2) * 2 будет 8.

В языке Python возможно использование множественного присваивания. Если записать инструкцию: b = a = 3, то сначала будет создана ячейка оперативной памяти с целочисленным значением 3, после чего эта ячейка сначала будет связана с именем a, а потом и с именем b. То есть эту инструкцию можно заменить двумя инструкциями: присваиванием переменной a значения 3 и присваиванием переменной b значения переменной a.

Также при помощи одной инструкции присваивания можно задать сразу несколько значений нескольким переменным. Для этого в инструкции, слева от знака равенства, через запятую перечисляются имена переменных, а справа от знака равенства – выражения, значения которых необходимо присвоить указанным переменным. Количество и порядок следования имён переменных и присваиваемых значений должны совпадать. Эта инструкция присваивания работает таким образом, что сначала вычисляются значения выражений, расположенных справа от знака равенства, и после этого вычисленные значения связываются с именами переменных. Таким образом, если мы хотим поменять местами значения переменных a и b, нам достаточно написать инструкцию: a, b = b, a.

Рассмотрим целочисленный тип данных в языке Python. В языке Python могут использоваться сколь угодно большие целые числа. В зависимости от значения числа изменяется размер оперативной памяти, выделяемой для его хранения. Рассмотрим операции и функции для преобразования числовых данных. Начнём с основных арифметических операций, которых, как мы помним, четыре: сложение, вычитание, умножение и деление. При этом, операции сложения, вычитания и умножения возвращают результат в зависимости от типов своих операнд. Если оба их операнда целочисленного типа, то и результат будет целочисленного типа, если же один или оба операнда вещественного типа, то и результат также будет вещественного типа. Результат операции деления – это всегда вещественное число. Результат операции возведения в степень, как и в случае со сложением, вычитанием и умножением зависит от типа операндов.

Также есть одна функция, общая для данных всех числовых типов. Это функция модуля числа, в языке Python она записывается abs. После служебного слова abs, в скобках, следует числовой аргумент функции. Модулем числа называется расстояние на числовой оси от точки начала отсчёта до точки, соответствующей этому числу. То есть в случае, если аргументом функции будет не отрицательное число, то значение функции будет равно аргументу, а если аргумент будет отрицательным, то результат функции будет противоположен аргументу по знаку. Тип результата функции всегда будет совпадать с типом аргумента.

Убедимся в том, что описанные операции и функции работают именно так, решив задачу. Даны целочисленные ненулевые координаты точки T на плоскости. Из начала отсчёта в точку T провели отрезок, который является диагональю прямоугольника. Вычислить площадь и периметр этого прямоугольника.

Обозначим координаты точки T – x и y соответственно. При неотрицательных значениях Икс и Игрек, длины сторон прямоугольника, обозначим их a и b, равны, соответственно x и y. При отрицательных координатах точки, длины сторон прямоугольника, наоборот, противоположны координатам по знаку. Проще говоря, длины сторон прямоугольника a и b будут равны, соответственно, модулям координат x и y. Зная длины сторон прямоугольника, мы можем легко вычислить его площадь и периметр.

Напишем модуль для решения задачи. В начале, с помощью инструкции print выведем на экран запрос на ввод координат точки Т. Напишем инструкции для считывания значений x и y. Так как по условию задачи, координаты целочисленные, то мы будем преобразовывать их в целочисленный тип int. Дальше напишем инструкцию присваивания для вычисления длин сторон прямоугольника. Слева от знака равенства, через запятую, укажем имена переменных – a и b. Справа от знака равенства, через запятую, перечислим их значения – модуль x и модуль y. Дальше напишем инструкцию для вычисления площади прямоугольника. Обозначим её s. Дальше напишем инструкцию для вычисления периметра прямоугольника, обозначим его p. Теперь напишем инструкцию print, которая выводит на экран сообщение о том, что площадь заданного прямоугольника равна значению переменной s, а его периметр – значению переменной p.

print ('Введите координаты точки Т.')

x = int (input ())

y = int (input ())

a, b = abs (x), abs (y)

s = a * b

p = (a + b) * 2

print ('Площадь заданного прямоугольника равна', s, ', а периметр -', p)

Сохраним написанный модуль и запустим его на выполнение. Зададим координаты точки равными 5 и -3. Площадь заданного прямоугольника действительно равна 15, а его периметр – 16. Модуль работает правильно. Задача решена.

Есть несколько операций, используемых для обработки данных только целочисленного типа. Это операции целочисленного деления и вычисления остатка от деления. Первая операция записывается при помощи знака «//», а вторая – при помощи знака «%». Результатом выполнения обеих операций являются целые числа. Приоритет выполнения этих операций такой же, как у умножения и деления.

Рассмотрим, как работают описанные операции, записав несколько выражений в интерактивном режиме среды разработки. Запишем выражение: 10 // 3. Как видим, результат выражения – число 3. Это целая часть от частного 10 и 3. Запишем ещё одно выражение: 10 % 3. Как видим, его результат – это единица. То есть разность числа десять и произведения двух троек. Интересен результат этих операций для отрицательных чисел. Запишем два выражения: -7 // 2 и -7 % 2. Как видим, результаты этих выражений – -4 и 1. Так происходит, потому что, согласно теории чисел, остаток от деления имеет тот же знак, что и делитель, при этом сумма произведения минус четырёх и двух, а также единицы, равна минус семи.

Часто при написании программы необходимо получить случайное число, но таблицы для хранения таких чисел малы, и их будет недостаточно для генерации большого количества чисел. Поэтому в информатике используются алгоритмы генерации псевдослучайных чисел. На первый взгляд, эти числа абсолютно случайны, но на самом деле они вычисляются в соответствии с некоторыми формулами. Инструменты для генерации случайных чисел находятся в модуле random. Для того, чтобы использовать операции, описанные в модуле, его необходимо подключить. Для этого используется инструкция import. После служебного слова «импорт» указывается имя модуля, в нашем случае это random.

Для генерации целого случайного числа используется функция randint. Для того, чтобы вызвать эту функцию, после подключения модуля random  нужно написать сначала имя модуля – random, после которого поставить точку и написать имя функции – randint. После этого, через пробел, в скобках, через запятую, указываются аргументы функции. Для функции randint – это два целых числа – начальное и конечное значения промежутка, на котором нужно сгенерировать число. То есть для того, чтобы получить в переменной T случайное число на промежутке от a до b, включая концы, – мы должны, после подключения модуля random, записать следующую инструкцию:  Описанный способ вызова функции из модуля называется точечным. Есть и другие способы вызова, но их мы рассмотрим позже.

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

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

Напишем модуль для решения задачи. Он будет начинаться с инструкции print для вывода на экран поясняющего сообщения о том, что это программа, генерирующая случайное целое трёхзначное число и вычисляющая сумму его цифр. После этого напишем инструкцию для подключения модуля random – import random. Дальше, в переменной a, сгенерируем случайное число. Для этого запишем инструкцию присваивания переменной a значения функции randint из модуля random. Так как все трёхзначные числа находятся на промежутке от 100 до 999, то аргументами функции будут числа 100 и 999. Дальше напишем инструкцию print для вывода на экран поясняющего сообщения о том, что случайное число равно значению переменной a. Теперь начнём вычислять сумму цифр числа в переменной s. Для этого запишем инструкцию присваивания переменной s остатка от деления a на 10. После того, как мы учли правую цифру числа при подсчёте суммы, удалим её. Запишем инструкцию присваивания переменной a результата её безостаточного деления на 10. Для учёта следующей цифры числа и её удаления запишем инструкцию присваивания переменным s и a, соответственно, суммы текущего значения s и остатка от деления a на 10, а также результата безостаточного деления a на 10. Для того, чтобы учесть последнюю цифру числа, запишем инструкцию присваивания переменной s суммы её текущего значения и остатка от деления a на 10. После учёта последнюю цифру удалять необязательно. Запишем инструкцию print для вывода на экран сообщения о том, что сумма цифр полученного случайного числа равна значению переменной s.

print ('Программа, генерирующая случайное целое трёхзначное число и вычисляющая сумму его цифр.')

import random

a = random.randint (100, 999)

print ('Случайное число:', a)

s = a % 10

a = a // 10

s, a = s + a % 10, a // 10

s = s + a % 10

print ('Сумма цифр числа:', s)

Сохраним модуль и запустим его на выполнение. Мы получили случайное число – 427, и сумму его цифр – 13. Модуль работает правильно. Задача решена.

Мы узнали:

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

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

·     Для генерации целых случайных чисел на некотором промежутке используется функция randint из модуля random.