Pythonista. привет, python

1.2. Как прервать цикл while на Python.

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

prompt = «Введите любое слово, и оно будет выведено наоборот»
prompt += «Если надоело введите команду ‘стоп’.»
message = »while message != «стоп»:
    message = input(prompt)    
     message != «стоп»:
        print(message)
    :
        print(«Программа завершена»)

В начале создаем сообщение prompt (посказку) которое объясняет пользователю что за программа и как ее можно завершить. Затем создается переменная message и ей присваивается пустое значение

Важно переменную message определить до запуска цикла, присвоить ей можно любое значение или пустую строку.  При запуске цикла while идет проверка совпадает ли значение message с условием продолжения цикла. При каждом выполнение цикла на экран выводятся правила цикла и условия его завершения

Дальше можно запустить команду для проверки условия, если пользователь не ввел строку «стоп», то выводим строку пользователя на экран в обратном порядке с помощью сегментации строки . 

Введите любое слово, и оно будет выведено наоборот
Если надоело введите команду ‘стоп’.python лучший язык программированияяинавориммаргорп кызя йишчул nohtyp

Введите любое слово, и оно будет выведено наоборот
Если надоело введите команду ‘стоп’.123456789987654321

Введите любое слово, и оно будет выведено наоборот
Если надоело введите команду ‘стоп’.стопПрограмма завершена

Пока пользователь не введет слово «стоп», цикл будет начинаться заново.

Классический алгоритм Евклида

Этот вид алгоритма Евклида является самым простым, он был придуман более 1300 лет назад. С появлением электронно-вычислительных машин расширились возможности по применению алгоритма Евклида, возникли новые более эффективные его реализации.

Алгоритм состоит из определенного количества шагов, количество которых зависит от размера входных данных.

Сложность алгоритма выражается функцией O(h2), где h – это количество десятичных цифр в наименьшем числе, наибольший делитель которых ищется алгоритмом.

Реализация на Python

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

Реализация с помощью остатка от деления

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

Код алгоритма Евклида на Python:

def gcd_rem_division(num1, num2):
    while num1 != 0 and num2 != 0:
        if num1 >= num2:
            num1 %= num2
        else:
            num2 %= num1
    return num1 or num2

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

В каждой новой итерации большее число становится меньшим и наоборот. Возьмём числа 168 и 105 и распишем работу программы вручную:

• 1 итерация:
  168 % 105 = 63
  105
• 2 итерация:
  63
  105 % 63 = 42
• 3 итерация:
  63 % 42 = 21
  42
• 4 итерация:
  42 % 21 = 0
  21

После 4 итерации алгоритм завершает свою работу, так как одно из чисел равно нулю, второе же число равно наибольшему общему делителю, в нашем случае это 21. Проверим работу программы:

a = gcd_rem_division(168, 105)
print(a) # Выведет 21

Реализация с помощью вычитания

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

Код вычисления НОД на Python:

def gcd_subtraction(num1, num2):
    while num1 != 0 and num2 != 0:
        if num1 >= num2:
            num1 -= num2
        else:
            num2 -= num1
    return num1 or num2

Также распишем работу программы с числами 168 и 105:

• 1 итерация:
  168 — 105 = 63
  105
• 2 итерация:
  63
  105 — 63 = 42
• 3 итерация:
  63 — 42 = 21
  42
• 4 итерация:
  21
  42 — 21 = 21
• 5 итерация:
  21 — 21 = 0
  21

Видно, что до 4 итерации результаты работы обоих версий алгоритма полностью совпадают. Отличия начинаются, когда в 4 итерации вместо 0 и 21, получается числа 21 и 21, из-за чего в алгоритме с вычитанием добавляется дополнительная итерация, но это не значит, что он работает менее эффективнее.

Проверка работы программы:

a = gcd_subtraction(168, 105)
print(a) # Выведет 21

Реализация с помощью рекурсии

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

Код программы на Python нахождения НОД с помощью рекурсии:

def gcd_recursion(num1, num2):
    if num1 == 0:
        return num2
    return gcd_recursion(num2 % num1, num1)

Первое, что стоит заметить, на ноль проверяется только

Важно понять, что числа постоянно меняются местами. В качестве первого числа в рекурсивный вызов функции передаётся , вспомним 4 итерацию в алгоритме через остаток от деления:

4 итерация:
42 % 21 = 0 — num1
21 — num2

То есть рекурсивный алгоритм проверит число на ноль, получит True и вернёт значение , которое и будет являться наибольшим общим делителем.

Особенности алгоритма: простые числа

Если два переданных числа не имеют общих делителей, то алгоритм возвращает единицу. Действительно, ведь каждое число делится на единицу. Например, числа 35 и 18 не имеют общих делителей:

• 35 = 5 * 7 * 1
• 18 = 2 * 9 * 1 = 3 * 6 * 1

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

Если алгоритм получает на вход одно простое число, это не значит, что он обязательно вернет единицу:

• 5 и 15: число 5 является простым, а 15 — нет, алгоритм вернет наибольший общий делитель 5.
• 5 и 21: число 5 — простое, а 21 — нет, будет возвращена единица, потому что 21 не делится на 5.
• 3 и 21: число 3 — простое, 21 — нет, будет возвращено число 3, потому что 21 делится на 3.

Исходя из этого, можно сказать, что алгоритм Евклида со 100%-ой вероятностью возвращает единицу в том случае, если на вход переданы два простых числа не равных друг другу.

Нахождение всех простых множителей числа

Если пользователь вводит число как 12, то на выходе должно быть 2, 2, 3, а если на входе 315 – выход должен быть «3 3 5 7». Программа должна вернуть все простые множители данного числа. Простые множители 330 – это 2, 3, 5 и 11. Следовательно, 11 является наиболее значимым простым множителем 330.

Например: 330 = 2 × 3 × 5 × 11.

Прежде чем писать программу на Python, давайте разберемся со следующими догадками.

1-я гипотеза – может быть хотя бы один простой множитель, который будет меньше √n в случае, если n не является простым числом.

Доказательство. Существуют два больших числа sqrt(n), их произведение также должно делить n, но оно будет превышать n, что противоречит нашему предположению. Таким образом, не может быть более одного простого множителя n, большего, чем sqrt(n).

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

 
p <= sqrt(n} or q <= sqrt(n) 

2-я гипотеза – может быть более 1 простого множителя n больше, чем sqrt(n).

Доказательство. Предположим, что есть два больших числа sqrt(n), тогда их произведение также должно делить n, но оно будет больше n, что противоречит нашему предположению. Таким образом, не может быть более одного простого множителя n, большего, чем sqrt(n).

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

Пример – программа Python для печати простых множителей.

 
import math 
# Below function will print the 
# all prime factor of given number 
def prime_factors(num): 
    # Using the while loop, we will print the number of two's that divide n 
    while num % 2 == 0: 
        print(2,) 
        num = num / 2 
 
    for i in range(3, int(math.sqrt(num)) + 1, 2): 
 
        # while i divides n , print i ad divide n 
        while num % i == 0: 
            print(i,) 
            num = num / i 
    if num > 2: 
        print(num) 
# calling function  
 
num = 200 
prime_factors(num) 

Выход:

2 
2 
2 
5 
5 

Объяснение –

В приведенном выше коде мы импортировали математический модуль. Функция prime_factor() отвечает за печать составного числа. Сначала мы получаем четные числа; после этого все оставшиеся простые множители должны быть нечетными. В цикле for число должно быть нечетным, поэтому мы увеличили i на два. Цикл for будет вычислять квадратный корень n раз.

Давайте разберемся в следующем свойстве составных чисел.

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

Программа будет работать следующим образом:

• На первом шаге найдем наименьший простой множитель i.
• Вхождение i будет удалено из n путем многократного деления n на i.
• Повторим оба вышеуказанных шага для деления n и i = i + 2. Оба шага будут повторяться до тех пор, пока n не станет либо 1, либо простым числом.

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

Пример – 2: Программа Python для определения наибольшего простого множителя заданного числа.

 
def largest_prime_factor(n): 
    i = 2 
    while i * i <= n: 
        if n % i: 
            i += 1 
        else: 
            n //= i 
    return n 
 
print(largest_prime_factor(345)) 

Выход:

23 

Изучаю Python вместе с вами, читаю, собираю и записываю информацию опытных программистов.

Приоритеты операторов

Consider this expression:

>>> 20 + 4 * 10
60

There is ambiguity here. Should Python perform the addition first and then multiply the sum by ? Or should the multiplication be performed first, and the addition of second?

Clearly, since the result is , Python has chosen the latter; if it had chosen the former, the result would be . This is standard algebraic procedure, found universally in virtually all programming languages.

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

Вот порядок приоритета операторов Python, которые вы видели до сих пор, от низшего к высшему:

 
Оператор
Описание

низший приоритет

Логическое ИЛИ

Логическое И

Логическое НЕ

, , , , , , ,

сравнения, идентификация

побитовое ИЛИ

побитовое ИСКЛЮЧАЮЩЕЕ ИЛИ

побитовое И

,

битовый сдвиг

,

сложение, вычитание

, , ,

умножение, деление, окруляющее деление, остаток от деления

, ,

плюс, минус, побитовый минус

наивысший приоритет

возведение в степень

 
Операторы в верхней части таблицы имеют самый низкий приоритет, а операторы в нижней части таблицы имеют самый высокий. Любые операторы в одной строке таблицы имеют одинаковый приоритет.

Понятно, почему умножение выполняется первым в приведенном выше примере: умножение имеет более высокий приоритет, чем сложение.

Аналогично, в приведенном ниже примере сначала возводится в степень , что равно , а затем выполняется умножение в порядок слева направо():

>>> 2 * 3 ** 4 * 5
810

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

>>> 20 + 4 * 10
60
>>>(20 + 4) * 10
240

>>> 2 * 3 ** 4 * 5
810
>>> 2 * 3 **(4 * 5)
6973568802

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

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

(a < 10) and(b > 30)

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

a < 10 and b > 30

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

Понятие оператора

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

Подразделяются на следующие типы операторов:

• операторы присваивания;
• арифметика;
• логические;
• сравнения;
• членство;
• личность.
• мало по малу;

Проще говоря, в примере «15-5» оператором является знак «-», операнды — 15 и 5. Это арифметическая операция с целыми числами

Если мы примем во внимание выражение «Истина и Истина», то здесь будет оператор «И», а операнды — «Истина» и «Истина». Этот пример можно отнести к логическому типу

Переменные

Любые данные хранятся в ячейках памяти компьютера. Когда мы вводим число, оно помещается в какую-либо ячейку памяти. Возникают вопросы: Куда именно? Как впоследствии обращаться к этим данными? 

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

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

Например, выражение, представленное ниже, означает, что на объект, представляющий собой число 4, находящееся в определенной области памяти, теперь ссылается переменная a.

Имена переменных могут быть любыми. Однако есть несколько общих правил их написания:

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

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

Математические функции и числовые методы

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

• , для округления чисел до определённого количества десятичных знаков
• , для получения абсолютного значения числа
• , для возведения числа в степень

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

Круглые числа с round()

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

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

Число 3,14159 округляется до трех десятичных знаков, чтобы получить 3,142, а число 2,71828 округляется до двух десятичных знаков, чтобы получить 2,72.

Второй аргумент должен быть целым числом. Если это не так, Python вызывает :

Иногда не дает правильного ответа:

2.675 – это ничья, потому что она находится ровно посередине между числами 2.67 и 2.68. Поскольку Python округляет до ближайшего четного числа, вы ожидаете, что round (2,675, 2) вернет 2,68, но вместо этого он вернет 2,67. Эта ошибка является результатом ошибки представления с плавающей запятой, а не ошибки в .

Работа с числами с плавающей запятой может вызывать разочарование, но это разочарование не характерно для Python. Все языки, реализующие стандарт IEEE с плавающей запятой, имеют одинаковые проблемы, включая C / C ++, Java и JavaScript.

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

Найдите абсолютное значение с помощью abs()

Абсолютное значение числа равно , если положительно, и , если отрицательно. Например, абсолютное значение 3 равно 3, а абсолютное значение -5 равно 5.

Чтобы получить абсолютное значение числа в Python, вы используйте :

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

Возвести в степень с помощью pow()

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

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

Например, в следующем примере функция возводит 2 в степень 3:

Как и в случае , показатель степени в может быть отрицательным:

Итак, в чем разница между и ?

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

Вот пример, в котором x = 2, y = 3 и z = 2:

Сначала 2 возводится в степень 3, чтобы получить 8. Затем вычисляется 8 % 2, что равно 0, потому что 2 делит 8 без остатка.

Проверка, является ли float целым числом

Возможно, вы знакомы со строковыми методами, такими как , и Целые числа и числа с плавающей запятой также имеют методы.

Числовые методы используются не очень часто, но есть один, который может быть полезен. У чисел с плавающей запятой есть метод , который возвращает True, если число является целым, то есть не имеет дробной части, а в противном случае возвращает False:

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

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

Целые числа и числа с плавающей запятой

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

Целые числа

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

Вы можете создать целое число, набрав желаемое число. Например, следующее присваивает переменной целое число 25:

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

Возможно, вы уже знакомы с тем, как преобразовать строку, содержащую целое число, в число с помощью . Например, следующее преобразует строку «25» в целое число 25:

не является целочисленным литералом, потому что целое значение создается из строки.

Когда вы пишете большие числа от руки, вы обычно группируете цифры в группы по три, разделенные запятой или десятичной точкой. Число 1000000 читать намного легче, чем число 1000000.

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

Нет предела тому, насколько большим может быть целое число, что может быть удивительно, учитывая, что компьютеры имеют конечный объем памяти. Попробуйте ввести наибольшее число, которое вы можете придумать, в интерактивном окне IDLE. Python справится с этим без проблем!

Числа с плавающей запятой

Число с плавающей запятой(floating-point number) или сокращенно с плавающей запятой(float) – это число с десятичной запятой. 1.0 – это число с плавающей запятой, как и -2.75. Имя типа данных с плавающей запятой – float:

Как и целые числа, числа с плавающей запятой можно создавать из литералов с плавающей запятой(floating-point literals) или путем преобразования строки в число с плавающей запятой с помощью функции :

Есть три способа представить литерал с плавающей запятой. Каждое из следующих действий создает литерал с плавающей запятой со значением один миллион:

Первые два способа аналогичны двум методам создания целочисленных литералов. Третий подход использует нотацию E для создания литерала с плавающей запятой.

Чтобы написать литерал с плавающей запятой в нотации E, введите число, за которым следует буква e, а затем другое число. Python берет число слева от e и умножает его на 10, возведенное в степень числа после e. Итак, эквивалентно 1 × 10⁶.

Python также использует нотацию E для отображения больших чисел с плавающей запятой:

Число с плавающей запятой 200000000000000000.0 отображается как . Знак указывает, что показатель степени является положительным числом. Вы также можете использовать отрицательные числа в качестве показателя степени:

Литерал интерпретируется как в степени , что составляет 1/10000 или 0,0001.

В отличие от целых чисел, числа с плавающей запятой имеют максимальный размер. Максимальное число с плавающей запятой зависит от вашей системы, но что-то вроде должно выходить за рамки возможностей большинства машин. составляет 2 × 10⁴⁰⁰, что намного больше, чем общее количество атомов во Вселенной!

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

означает бесконечность, и это просто означает, что число, которое вы пытались создать, превышает максимальное значение с плавающей запятой, разрешенное на вашем компьютере. Тип по-прежнему :

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

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

Интерактивное программирование[править]

Особенно удобная возможность, предоставляемая Python — это возможность быстро проверить как работают инструкции или выражения в интерактивном режиме. Такие интерактивные оболочки называются shell. Мы уже пользовались ей как частью IDLE. Остановимся сейчас на ней поподробнее.

Interactive Shellправить

Программа, с которой мы работали в первом уроке, может быть напечатана строчка за строчкой с тем же конечным результатом:

>>> v0 = 5
>>> g = 9.81
>>> t = 0.6
>>> y = v0 * t - 0.5 * g * t ** 2
>>> print (y)
1.2342

Мы можем легко задать новое значение переменной, например для v0, и всегда способны проконтролировать, что новое значение присвоено, введя имя переменной напрямую или через инструкцию print::

>>> v0 = 6
>>> v0
6
>>> print (v0)
6

Следующий шаг — обновить выражения, в которых еще содержится старое значение, то есть нашу формулу для y. В таком редакторе как IPython можно найти предыдущее выражение, с помощью кнопок со стрелками. О возможностях этого редактора мы еще поговорим. А пока:

>>> y = v0 * t - 0.5 * g * t ** 2
>>> y
1.8341999999999996
>>> print (y)
1.8342

Причина, по которой мы получили сейчас два разных результата, в том, что, если вы просто пишите y, то вы увидите все знаки после точки, находящиеся в памяти компьютера (16), в то время как инструкция print ограничивает число знаков и, таким образом, дает ответ с достаточной точностью. Впрочем, в некоторых версиях Python автоматически округляет значение переменной.

Преобразование типаправить

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

>>> C = 21
>>> type(C)
<type 'int'>

Теперь мы преобразуем наш объект С типа int к соответствующему объекту типа float:

>>> C = float(C)     #  type  conversion
>>> type(C)
<type 'float'>
>>> C
21.0

В инструкции C = float(C) мы создали новый объект из оригинального объекта с тем же именем. Теперь имя С ссылается на новый объект. Изначальный объект типа int со значением 21 теперь недоступен, поскольку у него больше нет имени и автоматически удаляется из памяти.

Мы также можем сделать и обратное, то есть конвертировать объект типа float к объекту типа int:

>>> C = 20.9
>>> type(C)
<type 'float'>
>>> D = int(C) #  type  conversion
>>> type(D)
<type 'int'>
>>> D
20  # decimals  are  truncated  :-/

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

>>> round(20.9)
21.0
>>> int(round(20.9))
21

Цикл while в Python

Цикл while в Python используется во многих программах. Он позволяет выполнять программу пока остается истинным условие. Приведем пример перебора числовой последовательности в заданном диапазоне. 

>>> number = 1           # присваиваем начальное значение переменной
>>> while number <= 7:   # запускаем цикл при условии значение number <=7
…     print(number)    # выводим значение number при каждом цикле
…     number += 1      # после каждого цикла увеличиваем значение на 1
…1
2
3
4
5
6
7

Вначале присваиваем значение переменной number. Затем запускаем цикл while до тех пор, пока значение переменной number не будет больше 7. При каждом проходе цикла выводим значение number и затем увеличиваем его на 1. Как только значение number станет больше 7 цикл прекращается. 

Бинарный алгоритм Евклида

Суть бинарного алгоритма точно такая же — найти наибольший делитель. От классического он отличается только способом реализации.

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

Сложность алгоритма по прежнему определяется функций O(h2), однако реальные тесты показывают, что бинарный алгоритм эффективнее классического на 60%, это обусловлено различиями в реализациях обычных арифметических операций и сдвигов.

Однако ускорение бинарного по сравнению с классическим алгоритмом справедливо не для кода написанного на Python. Ниже, после описания его реализации проведём тест скорости выполнения для Python.

Реализация на Python

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

Код на Python:

def binary_gcd(num1, num2):
    shift = 0
    # Если одно из чисел равно нулю, делитель - другое число
    if num1 == 0:
        return num2
    if num2 == 0:
        return num1
    # Если num1 = 1010, а num2 = 0100, то num1 | num2 = 1110
    # 1110 & 0001 == 0, тогда происходит сдвиг, который фиксируется в shift
    while (num1 | num2) & 1 == 0:
        shift += 1
        num1 >>= 1
        num2 >>= 1
    #Если True, значит num1 - четное, иначе - нечетное
    while num1 & 1 == 0:
        # если нечетное, сдвигаем на один бит
        num1 >>= 1
    while num2 != 0:
        # пока число нечётное, сдвигаем на один бит
        while num2 & 1 == 0:
            num2 >>= 1
        # если первое число больше второго
        if num1 > num2:
            # меняем их местами
            num1, num2 = num2, num1
        #теперь первое число меньше второго, вычитаем
        num2 -= num1
    # возвращаем число, перед этим сдвинув его биты на shift
    return num1 << shift

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

Тест скорости выполнения

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

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

Код проверки следующий:

start = time.monotonic()
for i in range(10000):
    binary_gcd(168024, 105023)
result = time.monotonic() - start
print("binary time : {:>.3f}".format(result) + " seconds")
start = time.monotonic()
for i in range(10000):
    gcd_rem_division(168024, 105023)
result = time.monotonic() - start
print("standard time: {:>.3f}".format(result) + " seconds")

Результат теста выглядит следующим образом:

binary time : 0.219 seconds
standard time: 0.094 seconds

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

Сложные задачи

1. Дано целое число N (> 1). Найти наименьшее целое число K, при котором выполняется неравенство 3^K > N, где 3^K — это 3 в степени K или число 3, умноженное само на себя K раз. Например, 3^5 = 3*3*3*3*3. Ответом в задаче будет первая степень числа 3, которая больше, чем заданное число N. Например, если N=41, распишем степени числа три: 3^1 = 3; 3^2 = 3*3 = 9; 3^3 = 3*3*3 = 27; 3^4 = 3*3*3*3 = 27 * 3 = 81;. Таким образом, первая степень, в которую возвести число 3, превышающая число N — это 4. В этой задаче нужно выполнять цикл while, пока остаток от деления на число три равен

2. Дано целое число N (> 0). Используя операции деления нацело и взятия остатка от деления, вывести все его цифры, начиная с самой правой (разряда единиц). Перед решением этой задачи вспомните, как найти сумму цифр трехначного числа.

3. Даны целые положительные числа A и B. Найти их наибольший общий делитель (НОД), используя алгоритм Евклида: НОД(A, B) = НОД(B, A mod B), если B = 0; НОД(A, 0) = A.

4. Спортсмен-лыжник начал тренировки, пробежав в первый день 10 км. Каждый следующий день он увеличивал длину пробега на P процентов от пробега предыдущего дня (P — вещественное, 0

5. Дано целое число N (> 1). Последовательность чисел Фибоначчи FK определяется следующим образом: F(1) = 1, F(2) = 1, F(K) = F(K-2) + F(K-1), K = 3, 4, …. Проверить, является ли число N числом Фибоначчи. Если является, то вывести TRUE, если нет — вывести FALSE.

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

7. Дано целое число N (> 1), являющееся числом Фибоначчи: N = F(K). Найти целое число K — порядковый номер числа Фибоначчи N.