Задача 12.
На столе в двух столбиках лежат 64 золотых и 64 серебряных монеты соответственно. Как серебряные, так и золотые монеты упорядочены в порядке убывания масс. Массы всех монет разные. Какое наименьшее количество взвешиваний необходимо для определения 64-ой монеты в порядке убывания масс среди всех 128 монет? За один раз можно взвешивать две монеты и определить, которая из них тяжелее. Ответ обосновать.
|
Решение задачи 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.
Процесс заканчивается, когда осталось по одному элементу в каждом массиве. При этом меньший из них и будет искомым.
|
