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

Алгоритмы обработки массивов. Программирование на 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

Источник

Python Урок 7. Массивы (списки) в Питоне: продолжение (алгоритмы)

import random from random import randint n=10;x=5 mas = [randint(1,10) for i in range(n)] for i in range (n): if mas[i] == x: nomer = i break if nomer >= 0: print ( «mas[«, nomer, «]=», x, sep = «» ) else: print ( «Не нашли!» )

В данном случае в переменной nomer сохраняется номер элемента массива с найденным значением.

Можно также предусмотреть более короткий вариант решения:

from random import randint n=10; x=5 mas = [randint(1,10) for i in range(n)] # инициализируем массив print(mas) ifTrue = [item for item in mas if item == x]# создаем массив найденных значений print(len(ifTrue)>0)

from random import randint n=10; x=5 mas = [randint(1,10) for i in range(n)] # инициализируем массив print(mas) ifTrue = [item for item in mas if item == x]# создаем массив найденных значений print(len(ifTrue)>0)

Но на языке Python цикл for обладает уникальным свойством: у него есть блок else, который выполняется в том случае, если в цикле не применился оператор break.

1 2 3 4 5 6 7 8 9 10 11 12 13

import random from random import randint n=10;x=5 mas = [randint(1,10) for i in range(n)] nomer = -1 for i in range (n): if mas[i] == x: print ( "mas[", i, "]=", x, sep = "" ) break else: print ( "Не нашли!" )

import random from random import randint n=10;x=5 mas = [randint(1,10) for i in range(n)] nomer = -1 for i in range (n): if mas[i] == x: print ( «mas[«, i, «]=», x, sep = «» ) break else: print ( «Не нашли!» )

Задание Python 7_1:
Дан массив. Необходимо подтвердить, что в массиве есть числа, кратные трем.

Задание Python 7_2:
Заполните массив случайными числами в диапазоне 0..4 и выведите на экран номера всех элементов, равных значению X (оно вводится с клавиатуры).

Поиск минимального или максимального элемента

import random from random import randint mas = [randint(1,10) for i in range(n)] MaxEl = mas[0] for i in range(1,n): if mas[i] > MaxEl: MaxEl = mas[i] print (MaxEl)

import random from random import randint mas = [randint(1,10) for i in range(n)] MaxEl = mas[0] for i in range(1,n): if mas[i] > MaxEl: MaxEl = mas[i] print (MaxEl)

В переменной MaxEl сохранится максимальный элемент массива.

import random from random import randint mas = [randint(1,10) for i in range(n)] MaxEl = max (mas) print ( MaxEl )

import random from random import randint mas = [randint(1,10) for i in range(n)] MaxEl = max (mas) print ( MaxEl )

Задание Python 7_3:
Заполните массив случайными числами. Найдите номера первого минимального и последнего максимального элемента массива.

Сортировка массива в Python

Метод Пузырька

Сортировку массива в python будем выполнять методом Пузырька:

1 2 3 4 5 6 7 8 9 10 11 12 13

import random from random import randint mas = [randint(1,10) for i in range(n)] for i in range(n): print(mas[i],sep="") print(" ") for i in range(n-1): for j in range(n-2, i-1 ,-1): if mas[j+1]  mas[j]: mas[j], mas[j+1] = mas[j+1], mas[j] for i in range(n): print(mas[i],sep="")

import random from random import randint mas = [randint(1,10) for i in range(n)] for i in range(n): print(mas[i],sep=»») print(» «) for i in range(n-1): for j in range(n-2, i-1 ,-1): if mas[j+1] < mas[j]: mas[j], mas[j+1] = mas[j+1], mas[j] for i in range(n): print(mas[i],sep="")

Задание Python 7_4:
Необходимо написать программу, в которой сортировка выполняется «методом камня» – самый «тяжёлый» элемент опускается в конец массива.

исходный массив: [8, 2, 9, 5, 6, 7, 0, 4] результат: [0, 2, 4, 5, 6, 7, 8, 9]

Быстрая сортировка массива

Данную сортировку еще называют quick sort или сортировка Хоара (по имени разработчика — Ч.Э. Хоар).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

import random from random import randint # процедура def qSort ( A, nStart, nEnd ): if nStart >= nEnd: return L = nStart; R = nEnd X = A[(L+R)//2] while L  R: while A[L]  X: L += 1 # разделение while A[R] > X: R -= 1 if L  R: A[L], A[R] = A[R], A[L] L += 1; R -= 1 qSort ( A, nStart, R ) # рекурсивные вызовы qSort ( A, L, nEnd ) N=10 A = [randint(1,10) for i in range(N)] print(A) # вызов процедуры qSort ( A, 0, N-1 ) print('отсортированный', A)

Задание Python 7_5:
Необходимо написать программу, которая сортирует массив (быстрой сортировкой) по возрастанию первой цифры числа.

Исходный массив: [2, 99, 14, 100, 88, 21, 31, 43, 79, 71] Отсортированный массив: [2, 14, 21, 31, 43, 71, 79, 88, 99, 100]

Встроенные функции

1. mas.reverse() — стандартный метод для перестановки элементов массива в обратном порядке;
2. mas2 = sorted (mas1) — встроенная функция для сортировки массивов (списков);

Задание Python 7_6:
Напишите программу, которая, не изменяя заданный массив, выводит номера его элементов в возрастающем порядке значений этих элементов. Использовать вспомогательный массив номеров.

[1,5,2,3,7] результат: 0 2 3 1 4

Задание Python 7_7:
Напишите программу, которая сортирует массив и находит количество различных чисел в нём. Не использовать встроенные функции.
Пример:

Введите количество: 10 Массив: [15, 19, 15, 12, 10, 13, 4, 18, 38, 27] Массив отсортированный: [4, 10, 12, 13, 15, 15, 18, 19, 27, 38] Количество различных элементов: 9

Задание Python 7_8:
Дан массив. Назовем серией группу подряд идущих одинаковых элементов, а длиной серии — количество этих элементов. Сформировать два новых массива, в один из них записывать длины всех серий, а во второй — значения элементов, образующих эти серии.
Пример:

Введите количество элементов: 15 Массив: [3, 1, 1, 1, 2, 5, 2, 5, 5, 1, 1, 3, 2, 5, 5] Элементы, создающие серии: [1, 5] Длины серий: [3, 2, 2]

Задание Python 7_9:
Напишите вариант метода пузырька, который заканчивает работу, если на очередном шаге внешнего цикла не было перестановок. Не использовать встроенные функции.

Задание Python 7_10:
Напишите программу, которая сортирует массив, а затем находит максимальное из чисел, встречающихся в массиве несколько раз. Не использовать встроенные функции.

Введите количество: 15 Массив исходный: [7, 15, 8, 11, 4, 7, 9, 4, 6, 12, 12, 8, 9, 8, 3] Массив отсортированный: [3, 4, 4, 6, 7, 7, 8, 8, 8, 9, 9, 11, 12, 12, 15] Максимальное из чисел, встречающихся в массиве несколько раз: 12

Источник

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

Презентация «Алгоритмы обработки массивов» для обучающихся 9 класса.

Просмотр содержимого документа
«Алгоритмы обработки массивов в Python»

-80%

Источник