Реализация алгоритмов. 
Технология разработки программного обеспечения

Предположим, необходимо найти позицию наименьшего элемента в следующем наборе данных: 809, 834, 477, 478, 307, 122, 96, 102, 324, 476.

Первым делом выбираем подходящий для хранения тип данных. Очевидно, что это будет список:

«> counts = [809, 834, 477, 478, 307, 122, 96, 102, 324, 476].

>" counts. index (min (counts)).

# решение задачи в одну строку!

>>>

Усложним задачу и попытаемся найти позицию двух наименьших элементов в неотсортированном списке. Возможные алгоритмы решения:

• 1) поиск, удаление, поиск. Поиск индекса минимального элемента в списке, удаление его, снова поиск минимального, возвращаем удаленный элемент в список;
• 2) сортировка, поиск минимальных, определение индексов;
• 3) перебор всего списка. Сравниваем каждый элемент, но порядку, получаем два наименьших значения, обновляем значения, если найдены наименьшие.

Рассмотрим каждый из перечисленных алгоритмов.

1. Поиск, удаление, поиск: поиск индекса минимального элемента в списке, удаление его, снова поиск минимального, возвращение удаленного элемента обратно в список.

Начнем:

[809, 834, 477, 478, 307, 122, 96, 102, 324, 476] индекс: 0 1 23 4 567 8 9.

Первый минимальный: 96.

Индекс элемента 96: 6.

Удаляем из списка найденный минимальный элемент (96), при этом индексы в обновленном списке смещаются:

[809, 834, 477, 478, 307, 122, 102, 324, 476].

индекс :12 345 6 7 8

Второй минимальный: 102.

Индекс элемента 102: 6.

Возвращаем удаленный (первый минимальный) элемент обратно в список:

[809, 834, 477, 478, 307, 122, 96, 102, 324, 476] индекс: 0 1 23 4567 8 9

Не забываем о смещении индексов после удаления первого минимального элемента: индекс второго минимального элемента ра вен индексу первого минимального элемента, поэтому увеличиваем индекс второго минимального на 1. Функция, реализующая данный алгоритм:

def find_two_smallest (L): smallest = min (L) mini = L. index (smallest).

L.remove (smallest).

# удаляем первый минимальный элемент next_smallest = min (L).

min2 = L. index (next_smallest).

L.insert (mini, smallest).

# возвращаем первый минимальный.

# проверяем индекс второго минимального из-за смещения: if mini <= min2:

min2 += 1 # min2 = min2 + 1.

return (mini, min2) # возвращаем кортеж.

2. Сортировка, поиск минимальных, определение индексов:

реализация второго алгоритма интуитивно понятна, поэтому приведем только исходный текст функции:

def find_two_smallest (L): temp_list = sorted (L) smallest = temp_list[0] next_smallest = temp_list[l] mini = L. index (smallest) min2 = L. index (next_smallest) return (mini, min2).

3. Перебор всего списка: сравниваем каждый элемент по порядку, получаем два наименьших значения, обновляем значения, если найдены наименьшие.

Третий алгоритм наиболее сложный из перечисленных выше, поэтому остановимся на нем подробнее.

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

На первом шаге рассматриваются первые два элемента списка.

[809, 834, …].

индекс: 0 1.

Сравниваем 809 и 834 и определяем наименьший из них, чтобы задать начальные значения mini и min2, где будут храниться индексы первого минимального и второго минимального элементов соответственно. Затем перебираем элементы, начиная с индекса 2 до окончания списка.

Определили, что 809 — первый минимальный, а 834 — второй минимальный элемент из двух первых встретившихся значений списка. Рассматриваем следующий элемент списка (477).

Элемент 477 оказался наименьшим (назовем это «первым случаем»). Поэтому обновляем содержимое переменных mini и min2. так как нашли новый наименьший элемент.

Рассматриваем следующий элемент списка (478). Он оказался между двумя минимальными элементами (назовем это «вторым случаем»).

Снова обновляем минимальные элементы (теперь обновился только min2), и т. д. пока не дойдем до конца списка.

Далее представлен исходный текст функции, реализующий предложенный алгоритм:

def find_two_smallest (L): if L[0] < L[1]:

mini, min2 = 0, 1.

# устанавливаем начальные значения else:

mini, min2 = 1, 0.

for i in range (2, len (L)):

if L[i] < L[minl]: # «первый случай» min2 = mini mini = i.

elif L[i] < L[min2]: # «второй случай» min2 = i.

return (mini, min2).