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

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

Популярные алгоритмы обработки списков в Python: примеры программ

Алгоритмы обработки списков являются важной темой в программировании. В этой статье мы рассмотрим самые популярные алгоритмы обработки списков на Python, а именно:

1. Разбивка целого положительного числа по цифрам
2. Программа, меняющая порядок следования элементов в списке
3. Метод пузырька
4. Сортировка методом выбора
5. Алгоритм Евклида (поиск наибольшего общего делителя двух чисел)

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

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

num = 12345 digits = [int(d) for d in str(num)] print(digits) # [1, 2, 3, 4, 5] 

Программа, меняющая порядок следования элементов в списке

Чтобы поменять порядок следования элементов в списке на обратный, можно использовать следующий алгоритм:

my_list = [1, 2, 3, 4, 5] reversed_list = my_list[::-1] print(reversed_list) # [5, 4, 3, 2, 1] 

Метод пузырька на Python

Метод пузырька является одним из самых простых алгоритмов сортировки. Он основан на сравнении пар элементов списка и перестановке их местами в случае, если они находятся в неправильном порядке. Алгоритм повторяется до тех пор, пока список не будет отсортирован.

def bubble_sort(lst):  n = len(lst)  for i in range(n):  for j in range(n - i - 1):  if lst[j] > lst[j + 1]:  lst[j], lst[j + 1] = lst[j + 1], lst[j]  my_list = [5, 2, 8, 6, 1, 9] bubble_sort(my_list) print(my_list) # [1, 2, 5, 6, 8, 9] 

Сортировка методом выбора

Сортировка методом выбора (Selection sort) — это алгоритм сортировки, который на каждом шаге выбирает наименьший элемент из неотсортированной части массива и ставит его на своё место в отсортированной части.

def selection_sort(arr):  for i in range(len(arr)):  min_idx = i for j in range(i + 1, len(arr)):  if arr[j]  arr[min_idx]:  min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i]  return arr # Пример использования arr = [64, 25, 12, 22, 11] sorted_arr = selection_sort(arr) print(sorted_arr) # Output: [11, 12, 22, 25, 64] 

Алгоритм Евклида (поиск наибольшего общего делителя двух чисел)

Алгоритм Евклида — это алгоритм для нахождения наибольшего общего делителя двух целых чисел. Он основан на наблюдении, что если a больше, чем b , то НОД(a, b) также будет НОД(b, a%b) .

def euclidean_algorithm(a, b):  while b:  a, b = b, a % b return a # Пример использования a = 60 b = 48 gcd = euclidean_algorithm(a, b) print(gcd) # Output: 12 

Заключение

Python предоставляет различные алгоритмы обработки списков для обработки больших объемов данных.

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

Добро пожаловать в Блог Разработчика Владислава Александровича.

Ведется медленная, но уверенная разработка функционала сайта.

Django Core: 0.3.4 / Next.js 1.0 / UPD: 05.06.2023

Источник

Алгоритмы обработки массивов. Программирование на Python

Поиск в массиве
Найти элемент, равный X:
i=0
while A[i] != X:
Что плохо?
i += 1
print ( «A[«, i, «]=», X, sep = «» )
?
i=0
while i < N and A[i] != X:
i += 1
Что если такого нет?
if i < N:
print ( «A[«, i, «]=», X, sep = «» )
else:
print ( «Не нашли!» )
?

3.

Поиск в массиве
Вариант с досрочным выходом:
номер найденного
элемента
nX = -1
for i in range ( N ):
if A[i] == X:
nX = i
досрочный выход
break
из цикла
if nX >= 0:
print ( «A[«, nX, «]=», X, sep = «» )
else:
print ( «Не нашли!» )

4.

Поиск в массиве
Варианты в стиле Python:
for i in range ( N ):
if A[i] == X:
print ( «A[«, i, «]=», X, sep = «» )
break
else:
print ( «Не нашли!» )
если не было досрочного выхода из цикла
if X in A:
nX = A.index(X)
print ( «A[«, nX, «]=», X, sep = «» )
else:
print ( «Не нашли!» )

5.

Задачи
«A»: Заполните массив случайными числами в интервале [0,5]. Введите число X и
найдите все значения, равные X.
Пример:
Массив:
1 2 3 1 2
Что ищем:
2
Нашли: A[2]=2, A[5]=2
Пример:
Массив:
1 2 3 1 2
Что ищем:
6
Ничего не нашли.

6.

Задачи
«B»: Заполните массив случайными числами в интервале [0,5]. Определить, есть ли
в нем элементы с одинаковыми значениями, стоящие рядом.
Пример:
Массив:
1 2 3 3 2 1
Есть: 3
Пример:
Массив:
1 2 3 4 2 1
Нет

7.

Задачи
«C»: Заполните массив случайными числами. Определить, есть ли в нем элементы с
одинаковыми значениями, не обязательно стоящие рядом.
Пример:
Массив:
3 2 1 3 2 5
Есть: 3, 2
Пример:
Массив:
3 2 1 4 0 5
Нет

8.

Максимальный элемент
M = A[0]
for i in range(1,N):
if A[i] > M:
M = A[i]
print ( M )
?
Если range(N)?
Варианты в стиле Python:
M = A[0]
for x in A:
if x > M:
M=x
M = max ( A )
?
Как найти его номер?

9.

Максимальный элемент и его номер
M = A[0]; nMax = 0
for i in range(1,N):
if A[i] > M:
Что можно улучшить?
M = A[i]
nMax = ii
print ( «A[«, nMax, «]=», M, sep = «» )
?
!
По номеру элемента можно найти значение!
nMax = 0
for i in range(1,N):
if A[i] > A[nMax]
A[nMax]:
nMax = i
print ( «A[«, nMax, «]=», A[nMax]
A[nMax], sep = «» )

10.

Максимальный элемент и его номер
Вариант в стиле Python:
M = max(A)
nMax = A.index(M)
print ( «A[«, nMax, «]=», M, sep = «» )
номер заданного элемента
(первого из…)

11.

Задачи
«A»: Заполнить массив случайными числами и найти минимальный и
максимальный элементы массива и их номера.
Пример:
Массив:
1 2 3 4 5
Минимальный элемент: A[1]=1
Максимальный элемент: A[5]=5
«B»: Заполнить массив случайными числами и найти два максимальных элемента
массива и их номера.
Пример:
Массив:
5 5 3 4 1
Максимальный элемент: A[1]=5
Второй максимум: A[2]=5

12.

Задачи
«C»: Введите массив с клавиатуры и найдите (за один проход) количество
элементов, имеющих максимальное значение.
Пример:
Массив:
3 4 5 5 3 4 5
Максимальное значение 5
Количество элементов 3

13.

Реверс массива
0
1
2
3
N-4
N-3
N-2
N-1
7
12
5
8
18
34
40
23
0
1
2
3
N-4
N-3
N-2
N-1
23
40
34
18
8
5
12
7
«Простое» решение:
остановиться на середине!
for i in range( N//2
N ):
поменять местами A[i] и A[N-1-i]
?
Что плохо?

14.

Реверс массива
for i in range(N//2):
c = A[i]
A[i] = A[N-1-i]
A[N-1-i] = c
Варианты в стиле Python:
for i in range(N//2):
A[i], A[N-i-1]= A[N-i-1], A[i]
A.reverse()

15.

16.

17.

18.

Задачи
«A»: Заполнить массив случайными числами и выполнить циклический сдвиг
элементов массива вправо на 1 элемент.
Пример:
Массив:
1 2 3 4 5 6
Результат:
6 1 2 3 4 5
«B»: Массив имеет четное число элементов. Заполнить массив случайными
числами и выполнить реверс отдельно в первой половине и второй
половине.
Пример:
Массив:
1 2 3 4 5 6
Результат:
3 2 1 6 5 4

19.

Задачи
«C»: Заполнить массив случайными числами в интервале [-100,100] и переставить
элементы так, чтобы все положительные элементы стояли в начала массива, а
все отрицательные и нули – в конце. Вычислите количество положительных
элементов.
Пример:
Массив:
20 -90 15 -34 10 0
Результат:
20 15 10 -90 -34 0
Количество положительных элементов: 3

20.

Отбор нужных элементов
Задача. Отобрать элементы массива A,
удовлетворяющие некоторому условию, в массив B.
Простое решение:
B = []
сделать для i от 0 до N-1
если условие выполняется для A[i] то
добавить A[i] к массиву B
B = []
for x in A:
if x % 2 == 0:
B.append(x)
?
Какие элементы выбираем?
добавить x в конец
массива B

21.

Отбор нужных элементов
Задача. Отобрать элементы массива A,
удовлетворяющие некоторому условию, в массив B.
Решение в стиле Python:
перебрать все
элементы A
B = [ x for x in A ]
if x % 2 == 0 ]
если x – чётное
число

22.

Особенности работы со списками
A = [1, 2, 3]
B=A
A
B
[1, 2, 3]
A[0] = 0
A = [1, 2, 3]
B = A[:]
A
B
[0, 2, 3]
A
[0, 2, 3]
B
[1, 2, 3]
копия массива A
A
[1, 2, 3]
B
[1, 2, 3]
A[0] = 0

23.

Копирование списков
«Поверхностное» копирование:
import copy
A = [1, 2, 3]
B = copy.copy(A)
A = [1, 2, 3]
B = [4, 5, 6]
C = [A, B]
D = copy.copy(C)
C[0][0] = 0
A
«Глубокое» копирование:
D = copy.deepcopy(C)
A
[1,2,3]
B
[4,5,6]
C
[A,B]
D
[A,B]
!
Влияет на C и D!
C
D
[A,B] A
B
[ , ]
0
[1,2,3]
[4,5,6]
A
B
[1,2,3]
[4,5,6]
[1,2,3]
[4,5,6]

24.

Задачи
«A»: Заполнить массив случайными числами в интервале
[-10,10] и отобрать в другой массив все чётные отрицательные числа.
Пример:
Массив А:
-5 6 7 -4 -6 8 -8
Массив B:
-4 -6 -8
«B»: Заполнить массив случайными числами в интервале [0,100] и отобрать в другой
массив все простые числа. Используйте логическую функцию, которая
определяет, является ли переданное ей число простым.
Пример:
Массив А:
12 13 85 96 47
Массив B:
13 47

25.

Задачи
«C»: Заполнить массив случайными числами и отобрать в другой массив все числа
Фибоначчи. Используйте логическую функцию, которая определяет, является ли
переданное ей число числом Фибоначчи.
Пример:
Массив А:
12 13 85 34 47
Массив B:
13 34

Источник