Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Поиск >> Номер 12

[Назад]    [Содержание ]    [Вперед]

  


Номер 12


  Условие: Номер 12


Задача 12. На столе в двух столбиках лежат 64 золотых и 64 серебряных монеты соответственно. Как серебряные, так и золотые монеты упорядочены в порядке убывания масс. Массы всех монет разные. Какое наименьшее количество взвешиваний необходимо для определения 64-ой монеты в порядке убывания масс среди всех 128 монет? За один раз можно взвешивать две монеты и определить, которая из них тяжелее. Ответ обосновать.

  Решение задачи: Номер 12


Решение задачи 12. Очевидным решением задачи является создание общего упорядоченного массива, содержащего элементы двух массивов, и нахождение в нем 64-того по величине элемента. Однако можно существенно сократить трудоемкость, используя дихотомический способ поиска. Пусть для каждого из двух наборов определены начальный Ni и конечный Ki номера элементов в массивах, рассматриваемых на данном шаге алгоритма, i=1,2. Определим номера средних элементов Si=(Ni+ +Ki)/2. Понятно, что на первом этапе N1=1, K1=64, N2=1, K2=64, а S1=32, S2=32. Обозначим эти средние элементы массивов X и У Сравнив эти средние элементы Х и У, найдем больший из них, и пусть это Х. Понятно, что каждый из элементов, стоящих перед Х, не меньше Х по величине. С другой стороны, только элементы, стоящие перед средним элементом У другого массива, могут быть не меньше Х. Поэтому Х не меньше 64-го элемента. Следовательно все элементы первого массива от первого до элемента Х включительно (всего 32 элемента) можно выбросить, учитывая при этом, что теперь необходимо искать 32-й по величине элемент среди оставшихся. Аналогично можно показать, что по крайней мере 63 элемента (выброшенные элементы и элементы, стоящие перед У,) не меньше У. Поэтому элементы, стоящие после У, можно тоже выбросить, так как они малы. После таких действий в массивах осталось по 32 элемента, и при этом необходимо найти 32-й по величине элемент. Повторяем описанный выше процесс с измененными значениями начальных Ni и конечных Ki номеров элементов в массивах по следующему правилу: если Х находится в первом массиве то N1=S1+1; K2=S2 иначе N2=S2+1; K1=S1. Процесс заканчивается, когда осталось по одному элементу в каждом массиве. При этом меньший из них и будет искомым.

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017