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

Поділитись

На уроке рассматриваются алгоритмы работы с массивами: сортировка на python, поиск в массиве, поиск максимального или минимального элемента и другие алгоритмы

Поиск в массиве

  • Используем цикл while:
  • Используем цикл for:
  • Поэтому рассмотрим второй способ поиска, более простой:

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

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

  • Однако, для поиска максимального и минимального элементов массива в Python есть собственные функции max:

Задание 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=»»)

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

БЫСТРАЯ СОРТИРОВКА МАССИВА

Данную сортировку еще называют 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:
Необходимо написать программу, которая сортирует массив (быстрой сортировкой) по возрастанию первой цифры числа.

ВСТРОЕННЫЕ ФУНКЦИИ

  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

Поділитись