О том что это такое можно почитать вот ЗДЕСЬ. Мой пост о самом алгоритме. Мне было интересно написать и проверить этот алгоритм. Это алгоритм поиска, прикол в том, что если мы увеличиваем наш список вдвое, то количество поисковых запросов увеличивается на 1.
Длина списка 20 - макс. кол. запросов 4
Длина списка 40 - макс. кол. запросов 5
Длина списка 80 - макс. кол. запросов 6
И так далее...
Получается, что абсолютно не важно как много номеров в вашей телефонной книге, ваш телефончик моментально всё найдёт.
Я его написал вот так (гугл тоже помогал :) ):
Я импортировал Randint для рандомального разброса чисел и задал переменные. Так же мне было интересно поработать с форматированием текста:
from random import randint
lis = []
y = 0
txt = "Есть контакт!! Что что вы искали находится на {} месте."
txt2 = "Количество попыток поиска: {}"
Затем создаём сам список. Так же можно задать длину списка. Это я сделал для того, что бы можно было посмотреть как быстро производится поиск в зависимости от длины списка.
dlinnaSpiska = int(input("Какова длина списка? "))
for x in range(dlinnaSpiska):
lis.append(randint(1, dlinnaSpiska + 1))
lis.sort()
Затем мы задаём число которое надо найти. Первый же if проверяет если наше число не выходит за рамки списка. Если оно не в рамках то какой смысл продолжать? А если оно таки в рамках списка то тогда идёт разбор списка по минимум, максимум и середине.
if iskat < lis[0] or iskat > lis[dlinnaSpiska - 1]:
print("Нет такого слова в этой букве!")
else:
dlinna = len(lis)
mini = 0
maxi = dlinna - 1
midi = dlinna // 2
Далее идёт сам алгоритм поиска. При каждом запросе отсеивается половина списка. Какую половину отсеивать, большую или меньшую, решается в зависимости от положения нашего числа от середины списка. И если в конечном итоге наше число будет в середине - значит алгоритм его нашел. В противном случаем программа скажет что его нет в списке.
while lis[mini] <= lis[maxi] and iskat != lis[midi]:
if iskat > lis[midi]:
mini = midi + 1
else:
maxi = midi - 1
midi = (mini + maxi) // 2
y += 1
После того как алгоритм прошелся по списку, мы получаем ответ. Если ответ положительный то программа скажет на каком месте в списке находится наше число. А если отрицательный - то увы и ах. В любом случае программа скажет сколько запросов она совершила.
if mini > maxi:
print("Нет такого слова в этой букве!")
print(txt2.format(y))
else:
place = midi
print(txt.format(place))
print(txt2.format(y))
И весь код целиком:
from random import randint
lis = []
y = 0
txt = "Есть контакт!! Что что вы искали находится на {} месте."
txt2 = "Количество попыток поиска: {}"
dlinnaSpiska = int(input("Какова длина списка? "))
for x in range(dlinnaSpiska):
lis.append(randint(1, dlinnaSpiska + 1))
lis.sort()
iskat = int(input("Какое число искать? "))
if iskat < lis[0] or iskat > lis[dlinnaSpiska - 1]:
print("Нет такого слова в этой букве!")
else:
dlinna = len(lis)
mini = 0
maxi = dlinna - 1
midi = dlinna // 2
while lis[mini] <= lis[maxi] and iskat != lis[midi]:
if iskat > lis[midi]:
mini = midi + 1
else:
maxi = midi - 1
midi = (mini + maxi) // 2
y += 1
if mini > maxi:
print("Нет такого слова в этой букве!")
print(txt2.format(y))
else:
place = midi
print(txt.format(place))
print(txt2.format(y))
Комментариев нет:
Отправить комментарий