Главная
Основы Python
Строки и коллекции данных

Алгоритмы обработки списков

На этом занятии рассмотрим несколько алгоритмов обработки элементов списков.

Разбивка целого положительного числа по цифрам

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

x = int(input("Введите целое положительное число: "))
digs = []
while x:
    digs.append(x%10)   #берем последнюю цифру числа
    x = x//10           #отбрасываем последнюю цифру числа
print(digs)

Чтобы цифры шли по порядку: слева-направо, мы их будем добавлять в начало списка:

digs = [x%10] + 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.