Подскажите, как среди 2n+1 различных по массе монет найти среднюю(т. е. такую, которая тяжелее n монет и легче других n монет), за 100n взвешиваний на чашечных весах без гирь.
Пронумеруем все монеты. Очевидно что искомая монета может иметь любой номер. А среди оставшихся 2N монет N весят менее искомой. Всего (2n+1)*(2n)!/n! вариантов. При каждом взвешивание в худшем случае из них мы сможем отбрасывать не более половины вариантов. То есть должно выполняться неравенство: (2n+1)*(2n)!/n! < 2^(100n) Заменим 2n! и n! по формуле Стирлинга: (2n+1)*(2n/e)^2n*sqrt(2*pi*2n)/((n/e)^n*sqrt(2*pi*n)) < 2^(100n) Вычислим натуральный логарифм от обеих частей: ln(2n+1)+2n*ln(2n/e)+ln(sqrt(2*pi*2n))-n*ln(n/e)-ln(sqrt(2*pi*n)) < 100n*ln(2) ln(2n+1)+2n*ln(2n)-2n+ln(sqrt(2*pi*2n))-n*ln(n)+n-ln(sqrt(2*pi*n)) < 100n*ln(2) Всё что со знаком минус перенесём в правую часть: ln(2n+1)+2n*ln(2n)+ln(sqrt(2*pi*2n)) < 100n*ln(2)+n+n*ln(n)+ln(sqrt(2*pi*n)) n*2*ln(2n)+ln(2n+1)+ln(sqrt(2*pi*2n)) < n*(100*ln(2)+1+ln(n))+ln(sqrt(2*pi*n)) ln(2n+1) и ln(sqrt) можно выбросить как не особо существенные слагаемые, и поделить всё на n: 2*ln(2n)< (100*ln(2)+1+ln(n)) 2*ln(n)+2*ln(2) < (100*ln(2)+1+ln(n)) 2*ln(n) < 98*ln(2) ln(n) < 49*ln(2) То есть для n больше чем 2^49(приблизительно), за 100n взвешиваний эту задачу нельзя решить даже теоретически.
Если я правильно понимаю вопрос, то речь идет о нахождении медианы, то есть в принципе стандартная задача. Существует алгоритм, позволяющий сделать это менее чем за 3х сравнений (где х - количество элементов), в данном случае соответственно за 6n+3. Описание можно посмотреть например здесь В университетском курсе скорее всего будут давать более старый алгоритм SPP, которого здесь тоже за глаза хватит там немного больше 3х сравнений. Поэтому вопрос: какой смысл имеет число 100 в вопросе? Такое ощущение, что это снова какое-то плохо сформулированное или второпях списанное упражнение из задачника.
Первое что вспомнилось - сначала quick sort, чтобы упорядочить веса по возрастанию, потом взять из получившегося ряду монету с индексом n+1 (т.е. среднюю). Должно подойти по условиям вроде.
Stiver quicksort необязательно выполнять полностью, так как нужно найти только медиану. Стандартный quicksort сначала разбивает массив на две части, все элементы в левой части меньше всех элементов в правой части. А теперь главный хинт: нам нужно найти элемент, находящийся на k-й (в общем случае) позиции в массиве. Зная размеры частей, можно определить, в какой из них (и на какой позиции) он будет после сортировки, и сортировать только эту часть. Таким образом можно избавиться от одного рекурсивного вызова, и время работы сократится до O(n). В ссылке, которую ты привел, должно быть описание этого алгоритма.
