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


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

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

Программа на 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.

icon