На этом занятии рассмотрим несколько алгоритмов обработки элементов списков.
Разбивка целого положительного числа по цифрам
Программа на Python будет выглядеть следующим образом:
x = int(input("Введите целое положительное число: "))
digs = []
while x:
digs.append(x%10) #берем последнюю цифру числа
x = x//10 #отбрасываем последнюю цифру числа
print(digs)
Чтобы цифры шли
по порядку: слева-направо, мы их будем добавлять в начало списка:
Программа, меняющая порядок следования элементов в списке
Программа на Python будет выглядеть следующим образом:
# программа reverse
N = 11
A = list(range(N))
print(A)
for i in range(N//2):
A[i], A[N-i-1] = A[N-i-1], A[i]
print(A)
Сортировка методом выбора
Идея этого
метода сортировки довольно проста. Классический пример для объяснения подобных
алгоритмов – выстроить людей по росту, допустим по возрастанию. (Детальный разбор самого алгоритма смотрите в видео этого занятия).
Этот алгоритм на Python можно реализовать следующим образом:
# сортировка методом выбора
A = [2, 2, -1, -5, 55, 34, 0, 10]
N = len(A)
for i in range(N-1):
for j in range(i+1, N):
if A[i] > A[j]:
A[i], A[j] = A[j], A[i]
print(A)
Алгоритм Евклида (поиск наибольшего общего делителя двух чисел)
Теория. Пусть
даны два натуральных числа a и b, для которых
требуется найти НОД. Далее, такой алгоритм:
пока a не равно b
находим большее среди a и b
уменьшаем большее на величину меньшего
выводим полученное равное значение преобразованных величин a и b
Например,
пусть у нас два числа: a=18 и b=24 и далее по
алгоритму:
Реализуем этот алгоритм на Python:
a = int(input("Введите 1-е натуральное число: "))
b = int(input("Введите 2-е натуральное число: "))
sa = a; sb = b
while a != b:
if a>b: a -= b
else: b -=a
print("НОД(%d, %d) = %d"%(sa,sb,a))
Быстрый алгоритм Евклида
Но у этого
алгоритма есть один существенный недостаток: если мы введем два вот таких
числа:
100000000 и 2
то этот алгоритм
начнет довольно долго работать и понятно почему, здесь мы получим большое
количество вычитаний 2. Эти вычитания будут происходить до тех пор, пока двойка
укладывается в оставшееся число. И мы здесь без всяких вычитаний сразу можем
сказать, что на последнем шаге будет вот такая операция:
4-2 = 2
После чего оба
числа станут равными и НОД будет равен двум. Так вот, чтобы без лишних операций
сразу определить на сколько будут отличаться два числа после серии вычитаний,
достаточно взять целый остаток от деления. Например:
100000000 % 2 =
0
Это значит, что
большее число можно полностью составить из суммы двоек. Следовательно, они оба
делятся на два нацело и их НОД равен 2. Хорошо, а если вместо 2 взять 3. В этом
случае имеем:
100000000 % 3 =
1
и далее уже
можно рассматривать два числа: 3 и 1. Причем, для них также можно выполнить
такую же операцию:
3 % 1 = 1
1 % 1 = 0
Все, получили
НОД, равный 1. И смотрите, здесь на каждой итерации большее число делится на
меньшее. Поэтому быстрый алгоритм Евклида можно записать так:
пока меньшее число больше 0
большему числу присваиваем остаток от деления на меньшее число
выводим большее число
Реализуем этот алгоритм. И договоримся, что большее число будем хранить в a, меньшее – в b.
a = int(input("Введите 1-е натуральное число: "))
b = int(input("Введите 2-е натуральное число: "))
sa = a; sb = b
b = min(sa, sb)
a = max(sa, sb)
while b:
a,b = b, a%b
print("НОД(%d, %d) = %d"%(sa,sb,a))
В этом алгоритме
используется свойство:
a%b = c, c < b
то есть, остаток
всегда будет меньше числа b. Значит, из двух чисел c и b большим будет b, а меньшим – c. Именно поэтому
в программе записано такое множественное присваивание:
a,b = b, a%b
Мы здесь переменной a
присваиваем
значение b, а b
становится
равным остатку от деления. Это гарантируется, что a
>=
b.