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

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

r

Требуется найти в массиве элемент, равный значению переменной X, или сообщить, что еготам нет. Алгоритм решения сводится к просмотру всех элементов массива с первого до последнего. Как только найден элемент, равный X, нужно выйти из цикла и вывести результат. Напрашивается такой алгоритм:i = 0while A[i] != X:i += 1print ( "A[", i, "]=", X, sep = "" )Он хорошо работает, если нужный элемент в массиве есть, однако приведет к ошибке, если такогоэлемента нет – получится зацикливание и выход за границы массива. Поэтому в условие нужнодобавить еще одно ограничение: i< N. Если после окончания цикла это условие нарушено, значитпоиск был неудачным – элемента нет:i = 0while i < N and A[i] != X:i += 1if i < N:print ( "A[", i, "]=", X, sep = "" )else:print ( "Не нашли!" )Отметим одну тонкость. В сложном условии i < N и A[i]!= X первой должно проверятьсяименно отношение i < N. Если первая часть условия, соединенного с помощью операции «И»,ложно, то вторая часть, как правило15, не вычисляется – уже понятно, что всё условие ложно. Делов том, что если i >= N, проверка условия A[i] != X приводит к выходу за границы массива, ипрограмма завершается аварийно.Возможен ещё один поход к решению этой задачи: используя цикл с переменной, перебрать все элементы массива и досрочно завершить цикл, если найдено требуемое значение.nX = -1for i in range ( len(A) ):if A[i] == X:nX = ibreakif nX >= 0:print ( "A[", nX, "]=", X, sep = "" )else:print ( "Не нашли!" )Для выхода из цикла используется оператор break, номер найденного элемента сохраняется впеременной nX. Если её значение осталось равным –1 (не изменилось в ходе выполнения цикла),то в массиве нет элемента, равного X.Последний пример можно упростить, используя особые возможности цикла for в языке Python:for i in range ( len(A) ):if A[i] == X:print ( "A[", i, "]=", X, sep = "" )breakelse:print ( "Не нашли!" )Итак, здесь мы выводим результат сразу, как только нашли нужный элемент, а не после цикла.Слово else после цикла for начинает блок, который выполняется при нормальном завершениицикла (без применения break). Таким образом, сообщение «Не нашли!» будет выведено толькотогда, когда условный оператор в теле цикла ни разу не сработал.Возможен другой способ решения этой задачи, использующий метод (функцию) index длятипа данных list, которая возвращает номер первого найденного элемента, равного X:nX = A.index(X)Тут проблема только в том, что эта строчка вызовет ошибку при выполнении программы, еслинужного элемента в массиве нет. Поэтому нужно сначала проверить, есть ли он там (с помощьюоператора in), а потом использовать метод index:if X in A:nX = A.index(X)print ( "A[", nX, "]=", X, sep = "" )else:print ( "Не нашли!" )Запись «if X in A» означает «если значение X найдено в списке A».

Максимальный элемент

Реверс массива

Сдвиг элементов массива

Отбор нужных элементов

Особенности копирования списков в Python

i = 0
while i < N and A[i] != X:
i += 1
if i < N:
print ( "A[", i, "]=", X, sep = "" )
else:
print ( "Не нашли!" )

for i in range ( len(A) ):
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 ( "Не нашли!" )

M = A[0]
for i in range(1,N):
if A[i] > M:
M = A[i]
print ( M )

nMax = 0
for i in range(1,N):
if A[i] > A[nMax]:
nMax = i
print ( "A[", nMax, "]=", A[nMax], sep = "" )

for i in range(N//2):
c = A[i]
A[i] = A[N-1-i]
A[N-1-i] = c

A.reverse()

c = A[0]
for i in range(N-1):
A[i] = A[i+1]
A[N-1] = c

A = A[1:N] + [A[0]]

B = []
for x in A:
if x % 2 == 0:
B.append(x)

B = [x for x in A if x % 2 == 0 ]

A =[1, 2, 3]
B = A[:]

import copy
A =[1,2,3]
B = copy.deepcopy(A)