кроссворды, задачки, головоломки

Сборник задач разного уровня сложности по математике, информатике, физике, химии, программированию, экономике etc. Логические задачи, SQL задачи, решение задач. Задачи с ответами, а также нерешённые задачи.

Petruchek.Info

Камень из большинства

Добавлено: 06.02.09 в 12:30
Метки: информатика взвешивания

Имеется n камней, больше половины из них имеют одинаковый вес.

Для любых двух камней можно определить, равны они по весу или нет.

Указать номер камня, принадлежащего большинству, используя не более n взвешиваний.

У этой задачи пока что нет ответа/решения. Вы можете прислать свой вариант в комментарии.


Комментарии
Google says:
Аноним (16.02.10):
-- взвешиваем камни по тройкам: для каждой тройки потребуется 3 взвешивания;
-- дожидаемся, когда в очередной тройке хотя бы пара окажется из равных по весу камней;
-- в худшем случае такая тройка появится после выборки трети камней.

i=0;
while(!(проверка_тройки_камней(i, i+1, i+2)))i+=3;
вывести(i, i+1, i+2);

int проверка_тройки_камней(int i, int j, int k){
return
камень(i)==камень(j) ||
камень(i)==камень(k) ||
камень(j)==камень(k)
}
Аст (31.03.10):
Не хватит n взвешиваний. В меньшинстве тоже могут быть камни с одинаковым весом.
kolun (15.06.11):
1. Разбиваем камни по парам. Если камней нечетное количество, запоминаем номер непарного камня (он нам понадобится в случае, если одинаковых камней n/2 + 1).
2. Взвешиваем каждую пару. Если в паре вес разный - выбрасываем пару. Получилось n/2 взвешиваний.
3. Если не осталось ни одной пары, то непарный камень принадлежит большинству.
4. Если осталось больше 1 пары, перекладываем первый камень из каждой пары в следующую пару. (из первой во вторую, 2 => 3, ..., k-1 => k, k => 1). Это нам поможет избавиться от пар, с одинаковым весом из меньшинства, т.к. пар, принадлежащих большинству будет как минимум столько же, сколько пар не принадлежащих большенству.
5. Снова взвешиваем. Теперь потребуется n/4 взвешивания.
6. Повторяем пункты 3, 4, 5 пока не останется 1 пара. Каждый раз количество взвешиваний будет геометрически уменьшаться, а сумма взвешиваний стремиться к n.

Итог: Второй камень из оставшейся пары (его номер мы знаем, его мы не перекладывали) принадлежит большенству.
Комментарий от новенького:
Новенький является
Новенький не робот
Знаки на картинке: латинские буквы, арабские цифры


Есть на сайте: Онлайн кроссворды Задачи Онлайн игры Блог
Все работы, опубликованные на сайте — авторские, если не указано иное. Перепечатка возможна только с письменного разрешения владельцев ресурса, с обязательной ссылкой на сайт petruchek.info. Пишите нам: . Сайт должен работать в IE, FF, Opera, Safari.

Реклама:

Разработано в студии "Webous"о проектесайта карта

Реклама: https://msk-ekspertiza.ru/