НОД – это математический термин, обозначающий наибольший общий делитель, который может идеально разделить два числа. НОД также известен как наибольший общий фактор(HCF).
Например, HCF / GCD двух чисел 54 и 24 равен 6. Поскольку 6 – это наибольший общий делитель, который полностью делит 54 и 24.
Разберемся как найти НОД двух чисел в Python. 
НОД с использованием функции gcd()
gcd() в python – это встроенная функция, предлагаемая математическим модулем для поиска наибольшего общего делителя двух чисел.
Синтаксис:
gcd(a, b)
Где a и b – два целых числа, которые передаются в качестве аргумента функции gcd().
Давайте создадим программу для печати НОД двух чисел, используя встроенную функцию math.gcd() в python.
math_fun.py
# create a program to print the gcd of two number in python using the math.gcd() function.
import math
print(" GCD of two number 0 and 0 is ", math.gcd(0, 0)) #math.gcd(a, b), a and b are the two integer number
print(" GCD of two number 0 and 48 is ", math.gcd(0, 48))
a = 60 # assign the number to variable a
b = 48 # assign the number to variable b
print(" GCD of two number 60 and 48 is ", math.gcd(a, b)) # pass the variable a and b to math.gcd() function.
print(" GCD of two number 48 and -12 is ", math.gcd(48, -12)) # pass the integer number
print(" GCD of two number -24 and -18 is ", math.gcd(-24, -18))
print(" GCD of two number -60 and 48 is ", math.gcd(-60, 48))
Выход:
В приведенном выше примере функция math.gcd() генерирует НОД двух заданных чисел. В функции gcd() a и b передаются в качестве аргумента, который возвращает наибольший общий делитель двух целых чисел, полностью разделяя числа.
НОД с использованием рекурсии
Рекурсия – это функция, потребляющая память, определенная в Python, которая вызывает себя через самореферентное выражение. Это означает, что функция будет постоянно вызывать и повторять себя до тех пор, пока не будет выполнено определенное условие для возврата наибольшего общего делителя числа.
Псевдокод алгоритма
Шаг 1: Возьмите два входа, x и y, от пользователя.
Шаг 2: Передайте входной номер в качестве аргумента рекурсивной функции.
Шаг 3: Если второе число равно нулю(0), возвращается первое число.
Шаг 4: В противном случае он рекурсивно вызывает функцию со вторым числом в качестве аргумента, пока не получит остаток, который делит второе число на первое число.
Шаг 5: Вызовите или назначьте gcd_fun() переменной.
Шаг 6: Отобразите НОД двух чисел.
Шаг 7: Выйдите из программы.
Разберемся с программой для нахождения НОД двух чисел с помощью рекурсии.
gcdRecur.py
# write a program to understand the GCD of two number in python using the recursion.
def gcd_fun(x, y):
if(y == 0): # it divide every number
return x # return x
else:
return gcd_fun(y, x % y)
x =int(input("Enter the first number: ")) # take first no.
y =int(input("Enter the second number: ")) # take second no.
num = gcd_fun(x, y) # call the gcd_fun() to find the result
print("GCD of two number is: ")
print(num) # call num
Выход:
Нахождение НОД с помощью цикла
Давайте создадим программу для нахождения НОД двух чисел в Python с помощью циклов.
gcdFile.py
def GCD_Loop( a, b):
if a > b: # define the if condition
temp = b
else:
temp = a
for i in range(1, temp + 1):
if(( a % i == 0) and(b % i == 0 )):
gcd = i
return gcd
x = int(input(" Enter the first number: ") ) # take first no.
y =int(input(" Enter the second number: ")) # take second no.
num = GCD_Loop(x, y) # call the gcd_fun() to find the result
print("GCD of two number is: ")
print(num) # call num
Выход:
Как мы видим в приведенной выше программе, мы берем два значения в качестве входных и передаем эти числа в функцию GCD_Loop(), чтобы вернуть GCD.
Алгоритм Евклида
Алгоритм Евклида – эффективный метод нахождения наибольшего общего делителя двух чисел. Это самый старый алгоритм, который делит большее число на меньшее и берет остаток. Опять же, он делит меньшее число от остатка, и этот алгоритм непрерывно делит число, пока остаток не станет 0.
Например, предположим, что мы хотим вычислить HCF двух чисел, 60 и 48. Затем мы делим 60 на 48; он возвращает остаток 12. Теперь мы снова делим число 24 на 12, а затем он возвращает остаток 0. Таким образом, мы получаем HCF равным 12.
Псевдокод алгоритма Евклида
Шаг 1: Есть два целых числа, например a и b.
Шаг 2: Если a = 0, то НОД(a, b) равен b.
Шаг 3: Если b = 0, НОД(a, b) равен a.
Шаг 4: Найти mod b.
Шаг 5: Предположим, что a = b и b = R.
Шаг 6: Повторяйте шаги 4 и 3, пока mod b не станет равным или большим 0.
Шаг 7: GCD = b и затем распечатайте результат.
Шаг 8: Остановите программу.
Найдем HCF или GCD двух чисел, используя алгоритм Евклида в python.
Euclid.py
# Create a program to find the GCD of two number in python using the Euclid's Algorithm.
def find_hcf(a,b):
while(b):
a, a = b, a % b
return a
a = int(input(" Enter the first number: ") ) # take first no.
b = int(input(" Enter the second number: ")) # take second no.
num = find_hcf(a, b) # call the find_hcf() to get the result
print(" The HCF of two number a and b is ")
print(num) # call num
Выход:
Изучаю Python вместе с вами, читаю, собираю и записываю информацию опытных программистов.
So I’m writing a program in Python to get the GCD of any amount of numbers.
def GCD(numbers):
if numbers[-1] == 0:
return numbers[0]
# i'm stuck here, this is wrong
for i in range(len(numbers)-1):
print GCD([numbers[i+1], numbers[i] % numbers[i+1]])
print GCD(30, 40, 36)
The function takes a list of numbers.
This should print 2. However, I don’t understand how to use the the algorithm recursively so it can handle multiple numbers. Can someone explain?
updated, still not working:
def GCD(numbers):
if numbers[-1] == 0:
return numbers[0]
gcd = 0
for i in range(len(numbers)):
gcd = GCD([numbers[i+1], numbers[i] % numbers[i+1]])
gcdtemp = GCD([gcd, numbers[i+2]])
gcd = gcdtemp
return gcd
Ok, solved it
def GCD(a, b):
if b == 0:
return a
else:
return GCD(b, a % b)
and then use reduce, like
reduce(GCD, (30, 40, 36))
asked May 18, 2013 at 19:19
TetramputechtureTetramputechture
2,9112 gold badges32 silver badges47 bronze badges
3
Since GCD is associative, GCD(a,b,c,d) is the same as GCD(GCD(GCD(a,b),c),d). In this case, Python’s reduce function would be a good candidate for reducing the cases for which len(numbers) > 2 to a simple 2-number comparison. The code would look something like this:
if len(numbers) > 2:
return reduce(lambda x,y: GCD([x,y]), numbers)
Reduce applies the given function to each element in the list, so that something like
gcd = reduce(lambda x,y:GCD([x,y]),[a,b,c,d])
is the same as doing
gcd = GCD(a,b)
gcd = GCD(gcd,c)
gcd = GCD(gcd,d)
Now the only thing left is to code for when len(numbers) <= 2. Passing only two arguments to GCD in reduce ensures that your function recurses at most once (since len(numbers) > 2 only in the original call), which has the additional benefit of never overflowing the stack.
answered May 18, 2013 at 19:53
alexkonradialexkonradi
7505 silver badges5 bronze badges
You can use reduce:
>>> from fractions import gcd
>>> reduce(gcd,(30,40,60))
10
which is equivalent to;
>>> lis = (30,40,60,70)
>>> res = gcd(*lis[:2]) #get the gcd of first two numbers
>>> for x in lis[2:]: #now iterate over the list starting from the 3rd element
... res = gcd(res,x)
>>> res
10
help on reduce:
>>> reduce?
Type: builtin_function_or_method
reduce(function, sequence[, initial]) -> value
Apply a function of two arguments cumulatively to the items of a sequence,
from left to right, so as to reduce the sequence to a single value.
For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates
((((1+2)+3)+4)+5). If initial is present, it is placed before the items
of the sequence in the calculation, and serves as a default when the
sequence is empty.
answered May 18, 2013 at 19:27
Ashwini ChaudharyAshwini Chaudhary
242k58 gold badges460 silver badges503 bronze badges
2
Python 3.9 introduced multiple arguments version of math.gcd, so you can use:
import math
math.gcd(30, 40, 36)
3.5 <= Python <= 3.8.x:
import functools
import math
functools.reduce(math.gcd, (30, 40, 36))
3 <= Python < 3.5:
import fractions
import functools
functools.reduce(fractions.gcd, (30, 40, 36))
answered May 13, 2020 at 16:08
Yam MesickaYam Mesicka
6,2157 gold badges45 silver badges64 bronze badges
A solution to finding out the LCM of more than two numbers in PYTHON is as follow:
#finding LCM (Least Common Multiple) of a series of numbers
def GCD(a, b):
#Gives greatest common divisor using Euclid's Algorithm.
while b:
a, b = b, a % b
return a
def LCM(a, b):
#gives lowest common multiple of two numbers
return a * b // GCD(a, b)
def LCMM(*args):
#gives LCM of a list of numbers passed as argument
return reduce(LCM, args)
Here I’ve added +1 in the last argument of range() function because the function itself starts from zero (0) to n-1. Click the hyperlink to know more about range() function :
print ("LCM of numbers (1 to 5) : " + str(LCMM(*range(1, 5+1))))
print ("LCM of numbers (1 to 10) : " + str(LCMM(*range(1, 10+1))))
print (reduce(LCMM,(1,2,3,4,5)))
those who are new to python can read more about reduce() function by the given link.
answered May 28, 2015 at 6:22
MD SARFARAZMD SARFARAZ
1172 silver badges17 bronze badges
The GCD operator is commutative and associative. This means that
gcd(a,b,c) = gcd(gcd(a,b),c) = gcd(a,gcd(b,c))
So once you know how to do it for 2 numbers, you can do it for any number
To do it for two numbers, you simply need to implement Euclid’s formula, which is simply:
// Ensure a >= b >= 1, flip a and b if necessary
while b > 0
t = a % b
a = b
b = t
end
return a
Define that function as, say euclid(a,b). Then, you can define gcd(nums) as:
if (len(nums) == 1)
return nums[1]
else
return euclid(nums[1], gcd(nums[:2]))
This uses the associative property of gcd() to compute the answer
answered May 18, 2013 at 19:23
torquestomptorquestomp
3,30418 silver badges26 bronze badges
3
Try calling the GCD() as follows,
i = 0
temp = numbers[i]
for i in range(len(numbers)-1):
temp = GCD(numbers[i+1], temp)
answered May 18, 2013 at 19:28
DeepuDeepu
7,5844 gold badges25 silver badges47 bronze badges
My way of solving it in Python. Hope it helps.
def find_gcd(arr):
if len(arr) <= 1:
return arr
else:
for i in range(len(arr)-1):
a = arr[i]
b = arr[i+1]
while b:
a, b = b, a%b
arr[i+1] = a
return a
def main(array):
print(find_gcd(array))
main(array=[8, 18, 22, 24]) # 2
main(array=[8, 24]) # 8
main(array=[5]) # [5]
main(array=[]) # []
Some dynamics how I understand it:
ex.[8, 18] -> [18, 8] -> [8, 2] -> [2, 0]
18 = 8x + 2 = (2y)x + 2 = 2z where z = xy + 1
ex.[18, 22] -> [22, 18] -> [18, 4] -> [4, 2] -> [2, 0]
22 = 18w + 4 = (4x+2)w + 4 = ((2y)x + 2)w + 2 = 2z
answered Jul 24, 2018 at 2:06
Zoe LZoe L
1,10914 silver badges21 bronze badges
As of python 3.9 beta 4, it has got built-in support for finding gcd over a list of numbers.
Python 3.9.0b4 (v3.9.0b4:69dec9c8d2, Jul 2 2020, 18:41:53)
[Clang 6.0 (clang-600.0.57)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import math
>>> A = [30, 40, 36]
>>> print(math.gcd(*A))
2
answered Aug 5, 2020 at 2:24
bigbountybigbounty
16.2k5 gold badges36 silver badges63 bronze badges
One of the issues is that many of the calculations only work with numbers greater than 1. I modified the solution found here so that it accepts numbers smaller than 1. Basically, we can re scale the array using the minimum value and then use that to calculate the GCD of numbers smaller than 1.
# GCD of more than two (or array) numbers - alows folating point numbers
# Function implements the Euclidian algorithm to find H.C.F. of two number
def find_gcd(x, y):
while(y):
x, y = y, x % y
return x
# Driver Code
l_org = [60e-6, 20e-6, 30e-6]
min_val = min(l_org)
l = [item/min_val for item in l_org]
num1 = l[0]
num2 = l[1]
gcd = find_gcd(num1, num2)
for i in range(2, len(l)):
gcd = find_gcd(gcd, l[i])
gcd = gcd * min_val
print(gcd)
answered Aug 10, 2020 at 19:04
Nikhil GuptaNikhil Gupta
1,38612 silver badges15 bronze badges
HERE IS A SIMPLE METHOD TO FIND GCD OF 2 NUMBERS
a = int(input("Enter the value of first number:"))
b = int(input("Enter the value of second number:"))
c,d = a,b
while a!=0:
b,a=a,b%a
print("GCD of ",c,"and",d,"is",b)
answered Oct 24, 2020 at 5:35
As You said you need a program who would take any amount of numbers
and print those numbers’ HCF.
In this code you give numbers separated with space and click enter to get GCD
num =list(map(int,input().split())) #TAKES INPUT
def print_factors(x): #MAKES LIST OF LISTS OF COMMON FACTROS OF INPUT
list = [ i for i in range(1, x + 1) if x % i == 0 ]
return list
p = [print_factors(numbers) for numbers in num]
result = set(p[0])
for s in p[1:]: #MAKES THE SET OF COMMON VALUES IN LIST OF LISTS
result.intersection_update(s)
for values in result:
values = values*values #MULTIPLY ALL COMMON FACTORS TO FIND GCD
values = values//(list(result)[-1])
print('HCF',values)
Hope it helped
answered Nov 11, 2022 at 14:03
Improve Article
Save Article
Like Article
Improve Article
Save Article
Like Article
The GCD of three or more numbers equals the product of the prime factors common to all the numbers, but it can also be calculated by repeatedly taking the GCDs of pairs of numbers.
gcd(a, b, c) = gcd(a, gcd(b, c))
= gcd(gcd(a, b), c)
= gcd(gcd(a, c), b)
Python
def find_gcd(x, y):
while(y):
x, y = y, x % y
return x
l = [2, 4, 6, 8, 16]
num1=l[0]
num2=l[1]
gcd=find_gcd(num1,num2)
for i in range(2,len(l)):
gcd=find_gcd(gcd,l[i])
print(gcd)
Output:
2
Time complexity : O(n + log(min(a, b))), as the function goes through the list of numbers and finds the GCD for each pair of numbers using the Euclidean algorithm.
Auxiliary Space: O(log x), as the function only uses a few variables to store the GCD and the numbers being compared.
Please refer complete article on GCD of more than two (or array) numbers for more details!
Last Updated :
09 Feb, 2023
Like Article
Save Article
Курс по Python: https://stepik.org/course/100707
На этом занятии я
хочу показать вам пример использования функций для решения одной частной задачи
– нахождения наибольшего общего делителя (НОД) для двух натуральных чисел a и b. Причем, мы не
просто напишем алгоритм, а еще выполним его тестирование с применением
тестирующей функции. То есть, это будет полноценный пример, показывающий
принцип разработки программ с использованием функций и тестов.
Но, вначале пару
слов о самом алгоритме Евклида, о принципе его работы. Сначала рассмотрим его
медленный, но простой вариант.
Например, пусть
даны два натуральных числа: a = 18 и b = 24. Чтобы
определить для них НОД, будем действовать, следующим образом. Из большего
значения вычтем меньшее и результат сохраним в переменной с большим значением,
то есть, в b. Фактически,
это означает, что мы выполняем операцию: b = b – a. Теперь у нас
два значения a = 18, b = 6. Для них
повторяем тот же самый процесс. Здесь большее уже переменная a, поэтому,
корректируем ее значение, вычитая меньшее. Получаем новую пару a = 12, b = 6. Опять
повторяем этот процесс и видим, что a = 6, b = 6 –
переменные равны. В этом случае останавливаем алгоритм и получаем, что НОД(18,
24) = 6, что, в общем то, верно.
Весь этот
алгоритм можно представить следующим псевдокодом:
пока
a != b
находим большее среди a и b
уменьшаем большее на величину меньшего
выводим
полученное значение величины a (или b)
Давайте его
опишем с помощью, следующей функции:
def get_nod(a, b): """Вычисляется НОД для натуральных чисел a и b по алгоритму Евклида. Возвращает вычисленный НОД. """ while a != b: if a > b: a -= b else: b -= a return a
Смотрите, здесь
вначале идет многострочная строка с описанием работы функции. Так рекомендуется
делать для ключевых функций программы, чтобы другие программисты могли быстро
понимать, как их применять на практике. А, далее, после описания следует сам
алгоритм Евклида.
Выполним эту
функцию со значениями аргументов 18 и 24:
res = get_nod(18, 24) print(res)
Видим в консоли верное
значение 6. Вот пример правильного оформления ключевых функций программы. Мало
того, встроенная функция:
позволяет
выводить описание указанных функций. И мы видим в консоли наше сформированное сообщение.
Это очень удобно, особенно при групповой работе над проектом.
После того, как
функция определена, ее следует протестировать и убедиться в корректности
возвращаемых результатов. Для этого тестировщик создает свою вспомогательную
функцию. Используя наши текущие знания, мы ее опишем, следующим образом:
def test_nod(func): # -- тест №1 ------------------------------- a = 28 b = 35 res = func(a, b) if res == 7: print("#test1 - ok") else: print("#test1 - fail") # -- тест №2 ------------------------------- a = 100 b = 1 res = func(a, b) if res == 1: print("#test2 - ok") else: print("#test2 - fail") # -- тест №3 ------------------------------- a = 2 b = 10000000 st = time.time() res = func(a, b) et = time.time() dt = et - st if res == 2 and dt < 1: print("#test3 - ok") else: print("#test3 - fail")
В первых двух
тестах мы проверяем корректность вычислений, а в третьем – еще и скорость
работы. Конечно, это довольно примитивное тестирование, показывающее лишь
принцип разработки программы, но для учебных целей вполне достаточно.
Далее, выполним
импорт нужного нам модуля time для вызова
функции time():
и в конце вызовем
тестирующую функцию для тестирования get_nod:
Смотрите, у нас
первые два теста прошли, а третий – не прошел, так как функция слишком долго
вычисляла результат.
Давайте поправим
ее и ускорим алгоритм Евклида. Как это можно сделать? Смотрите, если взять два
числа a = 2 и b = 100, то по
изначальному алгоритму мы будем делать многочисленные вычитания из b a, пока значения
не сравняются. То есть, мы здесь, фактически, вычисляем остаток от вхождения
двойки в сотню, а это есть не что иное, как операция:
b = b % a = 0
И никаких
циклических вычитаний! Это, очевидно, будет работать много быстрее. При этом,
как только получаем остаток равный нулю, то НОД – это значение меньшей
переменной, то есть, в нашем примере – a = 2.
То же самое для
предыдущих значений a = 18, b = 24. Получаем серию таких
вычислений:
b = 24 % 18 = 6
a = 18 % 6 = 0
Значит, НОД(18,
24) = 6. Видите, как это быстро и просто! На уровне псевдокода быстрый алгоритм
Евклида можно описать так:
пока
меньшее число больше 0
большему числу присваиваем остаток от деления на меньшее число
выводим большее
число
Реализуем его в
виде функции:
def get_fast_nod(a, b): """Вычисляется НОД для натуральных чисел a и b по быстрому алгоритму Евклида. Возвращает вычисленный НОД. """ if a < b: a, b = b, a while b != 0: a, b = b, a % b return a
Предлагаю, в
качестве самостоятельного задания, вам самим в деталях разобраться, как она
работает. А мы ее сразу протестируем:
Как видите, она
проходит все три наших теста.
Надеюсь, из
этого занятия мне удалось донести до вас общий принцип разработки и
тестирования ключевых программных функций. А также объяснить работу алгоритма
Евклида. Если все это понятно, то смело переходите к следующему уроку.
Курс по Python: https://stepik.org/course/100707
Видео по теме
Давайте рассмотрим библиотеки math и numpy для решения математических задач.
Важное уточнение: количество функций и внутренних модулей во многих библиотеках не позволяет рассмотреть их полностью в одной главе. Поэтому при изучении библиотек мы будем рассматривать лишь некоторые их возможности, а более подробную информацию вы сможете найти в документации. Ссылка на документацию будет в конце главы.
Библиотека math
Библиотека math является стандартной в Python и содержит много полезных математических функций и констант. Официальная документация Python выделяет следующие виды функций этого модуля:
-
Функции теории чисел и функции представления. Рассмотрим некоторые из них:
-
math.comb(n, k)— возвращает количество сочетаний изnэлементов поkэлементам без повторений и без учёта порядка. Определим, сколькими способами можно выбрать 3 объекта из множества в 12 объектов (порядок не важен):import math print(math.comb(12, 3)) # 220 -
math.factorial(x)— возвращает факториал целого неотрицательного числаx:print(math.factorial(5)) # 120 -
math.gcd(*integers)— возвращает наибольший общий делитель (НОД) для чисел-аргументов. Возможность определения НОДа для более чем двух чисел появилась в Python версии 3.9:print(math.gcd(120, 210, 360)) # 30 -
math.lcm(*integers)— возвращает наименьшее общее кратное (НОК) для чисел-аргументов. Функция появилась в Python версии 3.9:print(math.lcm(10, 20, 30, 40)) # 120 -
math.perm(n, k=None)— возвращает количество размещений изnэлементов поkэлементам без повторений и с учётом порядка. Если значение аргументаkне задано, то возвращается количество перестановок множества изnэлементов:print(math.perm(4, 2)) # 12 print(math.perm(4)) # 24 -
math.prod(iterable, start=1)— возвращает произведение элементов итерируемого объектаiterable. Еслиiterableпустой, то возвращается значение именованного аргументаstart:print(math.prod(range(10, 21))) # 6704425728000
-
-
Степенные и логарифмические функции. Некоторые из функций:
-
math.exp(x)— возвращает значение экспоненциальной функции ex:print(math.exp(3.5)) # 33.11545195869231 -
math.log(x, base)— возвращает значение логарифма отxпо основаниюbase. Если значение аргументаbaseне задано, то вычисляется натуральный логарифм. Вычисление производится по формулеlog(x) / log(base):print(math.log(10)) # 2.302585092994046 print(math.log(10, 2)) # 3.3219280948873626 -
math.pow(x, y)— возвращает значениеxв степениy. В отличие от операции**, происходит преобразование обоих аргументов в вещественные числа:print(math.pow(2, 10)) # 1024.0 print(math.pow(4.5, 3.7)) # 261.1477575641718
-
-
Тригонометрические функции. Доступны функции синус (
sin(x)), косинус (cos(x)), тангенс (tan(x)), арксинус (asin(x)), арккосинус (acos(x)), арктангенс (atan(x)). Обратите внимание: угол задаётся и возвращается в радианах. Имеются особенные функции:-
math.dist(p, q)— возвращает Евклидово расстояние между точкамиpиq, заданными как итерируемые объекты одной длины:print(math.dist((0, 0, 0), (1, 1, 1))) # 1.7320508075688772 -
math.hypot(*coordinates)— возвращает длину многомерного вектора с координатами, заданными в позиционных аргументахcoordinates, и началом в центре системы координат. Для двумерной системы координат функция возвращает длину гипотенузы прямоугольного треугольника по теореме Пифагора:print(math.hypot(1, 1, 1)) # 1.7320508075688772 print(math.hypot(3, 4)) # 5.0
-
-
Функции преобразования угла. Доступны функции:
-
math.degrees(x)— преобразует угол из радианов в градусы:print(round(math.sin(math.radians(30)), 1)) # 0.5 -
math.radians(x)— преобразует угол из градусов в радианы.print(round(math.degrees(math.asin(0.5)), 1)) # 30.0
-
-
Гиперболические функции. Доступны функции
acosh(x),asinh(x),atanh(x),cosh(x),sinh(x),tanh(x). -
Специальные функции. Среди специальных функций интерес представляет Гамма-функция. Она описывает гладкую непрерывную функцию f(x) = (x – 1)!, график которой проходит через точки, соответствующие значениям функции факториала для целых чисел. Другими словами, гамма-функция интерполирует значения факториала для вещественных чисел:
print(math.gamma(3)) # 2.0 print(math.gamma(3.5)) # 3.323350970447842 print(math.gamma(4)) # 6.0
В библиотеке math можно воспользоваться значениями числа пи (math.pi) и экспоненты (math.e).
Библиотека numpy
Язык программирования Python удобен для быстрого создания программ с целью проверки какой-либо идеи. Однако зачастую его используют и в решении научных задач, а также при анализе больших данных и машинном обучении.
Возникает вопрос: каким образом может быстро обрабатывать много данных интерпретируемая, а не скомпилированная программа?
Оказывается, что в решении некоторых математических задач программы на Python могут быть такими же быстрыми, как и программы, созданные на компилируемых языках.
Существенную прибавку в скорости обеспечивает библиотека numpy (Numerical Python, читается как «нампАй»). Библиотека numpy частично написана на языках С и «Фортран», благодаря чему и работает быстро. Таким образом, numpy сочетает в себе вычислительную мощность языков С и «Фортран» и простоту синтаксиса Python.
Библиотека numpy является нестандартной библиотекой.
Нестандартные модули можно установить в Python несколькими способами. Мы рассмотрим самый простой — установку из репозитория PyPI (Python Package Index). Репозиторий — коллекция дополнительных библиотек для Python, хранящаяся на сервере. В настоящий момент количество библиотек в репозитории составляет более 400 тысяч.
Для установки библиотек из репозитория необходимо подключение к сети Интернет, а далее нужно выполнить команду в консоли (терминале):
pip install <название библиотеки>
Установим библиотеку numpy командой:
pip install numpy
После ввода команды начнётся загрузка установочного пакета и дополнительных библиотек, от которых зависит numpy. Затем начнётся процесс установки. Если установка пройдёт успешно, то вы увидите вывод в командной строке:
Successfully installed numpy
Для импорта numpy обычно используют следующий код:
import numpy as np
В программе мы сможем обращаться к numpy по новому имени — np. Это упростит чтение кода. Такой импорт широко используется сообществом программистов, поэтому стоит его придерживаться, чтобы ваш код был понятен каждому.
Библиотека numpy работает с объектами-массивами, которые способны хранить много значений и быть многомерными. При этом, в отличие от списков, массивы могут хранить только значения одного типа. За счёт этого массивы в numpy занимают меньше памяти и работают быстрее, чем списки.
Создать массив можно разными способами. Один из них — использовать функцию array() для преобразования списка в массив. Для доступа к элементам массива необходимо указать индекс элемента в квадратных скобках. Индексация начинается с нуля:
import numpy as np
a = np.array([1, 2, 3, 4])
b = np.array([[1, 2], [3, 4], [5, 6], [7, 8]])
print(f"a[0] = {a[0]}")
print(f"b[0] = {b[0]}")
Вывод программы:
a[0] = 1 b[0] = [1 2]
В нашем примере массив a имеет размерность, равную 1. Размерность массива b равна 2. В терминологии numpy массив a имеет одну ось (термин «axis» из документации) длиной четыре элемента, а массив b имеет две оси: первая имеет длину 4, а длина второй оси равна 2.
Массивы numpy являются объектами класса ndarray. Наиболее важными атрибутами класса ndarray являются:
ndarray.ndim— размерность (количество осей) массива;ndarray.shape— кортеж, значения которого содержат количество элементов по каждой из осей массива;ndarray.size— общее количество элементов массива;ndarray.dtype— объект, описывающий тип данных элементов массива;ndarray.itemsize— размер памяти в байтах, занимаемый одним элементом массива.
import numpy as np
a = np.array([[1, 2], [3, 4], [5, 6], [7, 8]])
print(f"a.ndim = {a.ndim}, a.shape = {a.shape}, a.size = {a.size}, a.dtype = {a.dtype}")
Вывод программы:
a.ndim = 2, a.shape = (4, 2), a.size = 8, a.dtype = int32
Встроенные в numpy типы данных аналогичны типам данных в языке программирования С. Например, в предыдущем примере мы создали массив со значениями типа int32, то есть целые числа со знаком (отрицательные и положительные) и размером занимаемой памяти 32 бита. Из ограничения в размере памяти для типов данных в numpy следует то, что массивы каждого типа данных могут хранить значения из определённого диапазона. Например, для int32 этот числовой диапазон составляет от -2 147 483 648 до 2 147 483 647.
Покажем на примере, что произойдёт, если попытаться записать значение не из диапазона для типа данных. Для этого создадим массив типа uint8 — целые числа без знака размером 8 бит. Диапазон значений для этого типа от 0 до 255. Тип данных можно указать через именованный аргумент dtype при создании массива:
import numpy as np
a = np.array([1, 2, 3], dtype="uint8")
a[0] = 256
print(a)
Вывод программы:
[0 2 3]
Значение элемента не вышло за пределы диапазона, а было взято с его начала.
В numpy существуют и другие встроенные типы данных. С ними можно ознакомиться в документации.
При создании массива без указания его типа в аргументе dtype библиотека numpy попытается привести его к тому типу данных, который сможет хранить все значения исходной коллекции.
Рассмотрим пример:
import numpy as np
a = np.array([1, 2.5, 3])
print(a)
print(a.dtype)
b = np.array(['text', 1, 2.5])
print(b)
print(b.dtype)
Вывод программы:
[1. 2.5 3. ] float64 ['text' '1' '2.5'] <U32
В примере для массива a был выбран тип данных float64, так как исходный список содержит вещественное число. Для массива b был выбран тип данных <U32, который может хранить строки в кодировке Unicode длиной 32 символа. Такой тип данных был выбран, поскольку в исходной коллекции есть элемент-строка.
Для создания массива из нулей используется функция np.zeros(), которая принимает кортеж с количеством чисел, соответствующим количеству осей массива, а значения в кортеже — количество элементов по каждой из осей.
import numpy as np
a = np.zeros((4, 3))
print(a)
print()
a = np.zeros((4, 3), dtype="int32")
print(a)
Вывод программы:
[[0. 0. 0.] [0. 0. 0.] [0. 0. 0.] [0. 0. 0.]] [[0 0 0] [0 0 0] [0 0 0] [0 0 0]]
Функция np.ones() создаёт массив аналогично функции np.zeros(), только из элементов-единиц.
import numpy as np
a = np.ones((4, 3))
print(a)
Вывод программы:
[[1. 1. 1.] [1. 1. 1.] [1. 1. 1.] [1. 1. 1.]]
Функция np.eye() создаёт единичную матрицу, то есть массив с единицами на главной диагонали и нулевыми остальными элементами:
import numpy as np
a = np.eye(5, 5, dtype="int8")
print(a)
Вывод программы:
[[1 0 0 0 0] [0 1 0 0 0] [0 0 1 0 0] [0 0 0 1 0] [0 0 0 0 1]]
Для создания массива, заполненного значениями из диапазона, используется функция np.arange(). Эта функция похожа на стандартную функцию range(), но возвращает массив и может создавать диапазон значений из вещественных чисел.
import numpy as np
a = np.arange(1, 10)
print(a)
print()
a = np.arange(1, 5, 0.4)
print(a)
Вывод программы:
[1 2 3 4 5 6 7 8 9] [1. 1.4 1.8 2.2 2.6 3. 3.4 3.8 4.2 4.6]
Функция np.linspace() создаёт массив из заданного количества вещественных равномерно распределённых значений из указанного диапазона.
import numpy as np
a = np.linspace(1, 5, 10) # задаётся начало, конец диапазона и количество значений
print(a)
Вывод программы:
[1. 1.44444444 1.88888889 2.33333333 2.77777778 3.22222222 3.66666667 4.11111111 4.55555556 5. ]
Для изменения размерности массива используется функция reshape(). Она принимает кортеж, значения которого задают новые размеры массива по осям. Функция reshape() возвращает новый массив. Обратите внимание: при изменении размерности количество элементов в массиве не должно измениться.
import numpy as np
a = np.zeros((4, 3), dtype="uint8")
print(a)
print()
a = a.reshape((2, 6))
print(a)
Вывод программы:
[[0 0 0] [0 0 0] [0 0 0] [0 0 0]] [[0 0 0 0 0 0] [0 0 0 0 0 0]]
Метод resize() меняет размерность исходного массива:
import numpy as np
a = np.zeros((4, 3), dtype="uint8")
print(a)
print()
a.resize((2, 2, 3))
print(a)
Вывод программы:
[[0 0 0] [0 0 0] [0 0 0] [0 0 0]] [[[0 0 0] [0 0 0]] [[0 0 0] [0 0 0]]]
Если при изменении размерности в функции reshape() указать значение -1 по одной или нескольким осям, то значения размерности рассчитаются автоматически:
import numpy as np
a = np.zeros((4, 3), dtype="uint8")
print(a)
print()
a = a.reshape((2, 3, -1))
print(a)
Вывод программы:
[[0 0 0] [0 0 0] [0 0 0] [0 0 0]] [[[0 0] [0 0] [0 0]] [[0 0] [0 0] [0 0]]]
Для работы с массивами доступны все стандартные арифметические операции, а также тригонометрические, экспоненциальная и другие функции. Выполнение математических операций над массивами происходит поэлементно. Размерность массивов должна совпадать при выполнении этих операций. Применение некоторых из операций приведено в примере:
import numpy as np
a = np.array([9, 8, 7])
b = np.array([1, 2, 3])
print(a + b)
print(a - b)
print(a * b)
print(a / b)
Вывод программы:
[10 10 10] [8 6 4] [ 9 16 21] [9. 4. 2.33333333]
Для умножения матриц используется операция @ или функция dot:
import numpy as np
a = np.array([[1, 2, 3],
[4, 5, 6],
[7, 8, 9]])
b = np.array([[0, 0, 1],
[0, 1, 0],
[1, 0, 0]])
print(a @ b)
Вывод программы:
[[3 2 1] [6 5 4] [9 8 7]]
Матрицы можно транспонировать функцией transpose() и поворачивать функцией rot90(). При повороте можно указать направление поворота вторым аргументом:
import numpy as np
a = np.arange(1, 13).reshape(4, 3)
print(a)
print("Транспонирование")
print(a.transpose())
print("Поворот вправо")
print(np.rot90(a))
print("Поворот влево")
print(np.rot90(a, -1))
Вывод программы:
[[ 1 2 3] [ 4 5 6] [ 7 8 9] [10 11 12]] Транспонирование [[ 1 4 7 10] [ 2 5 8 11] [ 3 6 9 12]] Поворот вправо [[ 3 6 9 12] [ 2 5 8 11] [ 1 4 7 10]] Поворот влево [[10 7 4 1] [11 8 5 2] [12 9 6 3]]
Функции вычисления суммы элементов массива, поиска минимального и максимального элементов и многие другие по умолчанию работают для всех элементов массива, не учитывая размерность:
import numpy as np
a = np.array([[1, 2, 3],
[4, 5, 6],
[7, 8, 9]])
print(a.sum())
print(a.min())
print(a.max())
Вывод программы:
45 1 9
Дополнительно в указанных функциях можно указать номер оси (индексация с 0), на которой будет работать функция:
import numpy as np
a = np.array([[1, 2, 3],
[4, 5, 6],
[7, 8, 9]])
print(a.sum(axis=0)) # сумма чисел в каждом столбце
print(a.sum(axis=1)) # сумма чисел в каждой строке
print(a.min(axis=0)) # минимум по столбцам
print(a.max(axis=1)) # максимум по строкам
Вывод программы:
[12 15 18] [ 6 15 24] [1 2 3] [3 6 9]
В массивах можно брать срез. Для одномерных массивов эта операция аналогична стандартному срезу в Python. Для многомерного массива можно задавать диапазон среза отдельно для каждой оси. Таким образом, можно взять срез отдельной части матрицы, указав, какие строки и столбцы должны попасть в срез:
import numpy as np
a = np.arange(1, 13).reshape(3, 4)
print(a)
print()
print(a[:2, 2:])
print()
print(a[:, ::2])
Вывод программы:
[[ 1 2 3 4] [ 5 6 7 8] [ 9 10 11 12]] [[3 4] [7 8]] [[ 1 3] [ 5 7] [ 9 11]]
В цикле for можно пройти по элементам первой оси массива:
import numpy as np
a = np.arange(1, 13).reshape(3, 4)
print(a)
for row in a:
print(row)
Вывод программы:
[[ 1 2 3 4] [ 5 6 7 8] [ 9 10 11 12]] [1 2 3 4] [5 6 7 8] [ 9 10 11 12]
Для линеаризации многомерного массива можно использовать атрибут flat, который является итератором, возвращающим последовательно значения массива:
import numpy as np
a = np.arange(1, 13).reshape(3, 4)
print(a)
print()
print("; ".join(str(el) for el in a.flat))
Вывод программы:
[[ 1 2 3 4] [ 5 6 7 8] [ 9 10 11 12]] 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12
Покажем на примере различие в скорости работы массивов и списков. Посчитаем сумму квадратных корней первых 107 чисел.
import numpy as np
from time import time
t = time()
print(f"Результат итератора: {sum(x ** 0.5 for x in range(10 ** 7))}.")
print(f"{time() - t} с.")
t = time()
print(f"Результат numpy: {np.sqrt(np.arange(10 ** 7)).sum()}.")
print(f"{time() - t} с.")
Вывод программы:
Результат итератора: 21081849486.439312. 1.7823209762573242 с. Результат numpy: 21081849486.442448. 0.05197310447692871 с.
Библиотека numpy решила задачу в 30 раз быстрее, чем итератор.
За счёт скорости работы и удобной обработки массивов библиотека numpy используется для расчётов во многих других библиотеках. С одной из них мы поработаем в следующей главе.
Ещё по теме
Для более детального изучения библиотеки numpy рекомендуем почитать документацию.
