Появление подобных задач, например задачи определения фальшивой монеты, в контексте рассмотрения алгоритмов поиска не случайно. Во-первых, поиск и в этом случае осуществляется путем операций сравнения, правда, уже не только одиночных элементов, но и групп элементов между собой. Во-вторых, как будет показано ниже, задачи на взвешивания вполне можно решать конструктивно.
В качестве примера рассмотрим задачу, предлагавшуюся на теоретическом туре одной из региональных олимпиад по информатике. Пусть у нас имеется 12 монет, одна из которых фальшивая, по весу отличающаяся от остальных монет, причем неизвестно, легче она или тяжелее. Требуется за три взвешивания определить номер фальшивой монеты (попробуйте решить эту задачу самостоятельно и вы убедитесь, что это совсем не просто, а порой вообще кажется невозможным). Введем следующие обозначения. Знаком “+” будем обозначать монеты, которые во время текущего взвешивания следует положить на весы, причем, если монета на весах уже была, то на ту же самую чашу, на которой эта монета находилась во время своего предыдущего взвешивания. Знаком “-“ будем обозначать монеты, которые следует переложить на противоположную чашу весов, по отношению к той, на которой они находились (каждая в отдельности), заметим, что если монета на весах еще не была, то знак “-“ к ней применен быть не может. Наконец, знаком “0” — монеты, которые в очередном взвешивании не участвуют. Тогда, существует 14 различных способов пометки монет для трех взвешиваний:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
+ + + + + + + + + 0 0 0 0 0 — первое взвешивание
+ + + — — — 0 0 0 + + + 0 0 — второе взвешивание
+ — 0 + — 0 + — 0 + — 0 + 0 — третье взвешивание
Из полученной таблицы вычеркнем 2 столбца так, чтобы в каждой из трех строк количество ненулевых элементов оказалось четным (ведь мы не можем во время одного взвешивания положить на две чаши весов нечетное число монет). Это могут быть, например, столбцы 4 и 14. Теперь будем взвешивать 12 монет так, как это записано в оставшихся 12 столбцах. То есть, в первом взвешивании будут участвовать 8 произвольных монет, во втором — три монеты следует с весов убрать, две — переложить на противоположные по отношению к первому взвешиванию чаши весов и три монеты положить на весы впервые (на свободные места так, чтобы на каждой из чаш вновь оказалось по 4 монеты). Согласно схеме проведем и третье взвешивание, опять располагая на каждой чаше весов по 4 монеты. Результат каждого взвешивания в отдельности никак не анализируется, а просто записывается. При этом равновесие на весах всегда кодируется нулем, впервые возникшее неравновесное состояние — знаком плюс, если при следующем взвешивании весы отклонятся от равновесия в ту же самую сторону, то результат такого взвешивания также кодируется плюсом, а если в другую сторону — то минусом. Например, записи “=<>” кодируются как “0++”, а записи “” и “>= как “+0-“. Так как мы не знаем, легче или тяжелее остальных монет окажется фальшивая, то нам важно как изменялось состояние весов от взвешивания к взвешиванию, а не то какая именно чаша оказывалась тяжелее, а какая легче. Поэтому два, на первый взгляд, различных результата трех взвешиваний в этом случае кодируются одинаково. После подобной записи результатов взвешиваний фальшивая монета уже фактически определена. Ею оказывается та, которой соответствует такой же столбец в таблице, как и закодированный нами результат трех взвешиваний. Для первого из примеров это монета, которая участвовала во взвешиваниях по схеме, указанной в 10-м столбце таблицы, а для второго — в 8-м. В самом деле, состояние весов в нашей задаче меняется в зависимости от того, где оказывается фальшивая монета во время каждого из взвешиваний. Поэтому монета, “поведение” которой согласуется с записанным результатом взвешиваний, такой результат и определяет.
Анализ таблицы показывает, что эту задачу можно решить не только для 12, но и для 13 монет. Для этого следует исключить из рассмотрения любой не содержащий нулей столбец, например, все тот же четвертый. В остальном все действия остаются неизменными. Для произвольного числа монет N>2 количество взвешиваний при определяется по формуле [log3(2*N + 1)] (за одно взвешивание задача не разрешима ни для какого количества монет!!!), но подход к решению задачи при этом не изменится.
Попробуйте теперь решить задачу, которая предлагалась в 1998 году на уже упоминавшемся выше полуфинале чемпионата мира по программированию среди студенческих команд вузов. В ней также требовалось определить номер фальшивой монеты, вес которой отличался от остальных. Но все взвешивания уже были проведены, а их результаты записаны. Число взвешиваний являлось входным параметром в задаче (оно могло быть и избыточным по сравнению с описанным выше оптимальным алгоритмом определения номера фальшивой монеты). При этом в каждом из взвешиваний могло участвовать любое четное количество имеющихся монет (сколько и какие именно — известно). Результаты записывались с помощью символов “” и “=”.
Еще одна задача на взвешивания рассмотрена в [8]. В общем случае в ней требуется найти набор из минимального количества гирь такой, что с его помощью можно взвесить любой груз, весящий целое число килограмм, в диапазоне от 1 кг до N кг. При необходимости гири можно располагать на обеих чашах весов. Так, для N=40 это гири 1, 3, 9 и 27 кг.
Алгоритмы поиска в неупорядоченных одномерных массива
Поиск в упорядоченных массивах
Поиск подстроки в строке
