Вход | Регистрация

  1  2   
Информационные технологии :: Математика и алгоритмы

25 камней

25 камней
Я
   Undefined vs NULL
 
10.01.13 - 10:03
Есть 25 камней разной массы и чашечные весы без гирь. Какое минимальное число взвешиваний нужно, чтобы найти три камня наибольшей массы?
 
 
   Aleksey
 
1 - 10.01.13 - 10:04
Проверяешь как народ гуглить умеет?
   Undefined vs NULL
 
2 - 10.01.13 - 10:05
(1) лень было префразировать, думал найдутся честные
   MaxS
 
3 - 10.01.13 - 10:08
(0) 3 ?
   samozvanec
 
4 - 10.01.13 - 10:09
чего, уже все загуглили, или можно порассуждать?
   ICWiner
 
5 - 10.01.13 - 10:10
Я не гуглил, давайте порассуждаем. Интересно же
   samozvanec
 
6 - 10.01.13 - 10:12
на первый мой взгляд, 24 взвешивания будет достаточно)
   ICWiner
 
7 - 10.01.13 - 10:15
Странное мнение. Допустим 3 камня - там 0, 4 камня - первое взвешивание камень 1 и камень 2, второе - камень 3 и камень 4, третье - два самых легких из пар, так найдем самый легкий. Уже 3 взвешивания.
   samozvanec
 
8 - 10.01.13 - 10:16
ну да, на одно меньше, чем камней
   Aleksey
 
9 - 10.01.13 - 10:18
(6) Ты не забыл что нужно найти 3 камня?
   samozvanec
 
10 - 10.01.13 - 10:18
несколько камней взвешивать безсмысленно, они ж все разные. вот и получается, что по одному.
 
 Рекламное место пустует
   alek_aab
 
11 - 10.01.13 - 10:18
имхо, 5
   samozvanec
 
12 - 10.01.13 - 10:18
(9) я их по порядку в линию буду с весов снимать. последние 3 будут самыми тяжелыми
   ICWiner
 
13 - 10.01.13 - 10:18
Для пяти камней как оптимально? Что-то у меня много получается...
   Aleksey
 
14 - 10.01.13 - 10:19
(12) Т.е.
   Gesperid
 
15 - 10.01.13 - 10:20
кажется без логарифмов здесь не обошлось
   Aleksey
 
16 - 10.01.13 - 10:21
(15) Ага, а еще без знания плотности камня и объема
   samozvanec
 
17 - 10.01.13 - 10:21
(14) в общем начинает доходить, что, если мне первый же попадется самый тяжелый, не выйдет так...
   Мимо Проходил
 
18 - 10.01.13 - 10:22
Что-то типа швейцарской системы для шахматных турниров. Попарно сравниваем камни, получивший три поражения выбывает из турнира.
   ICWiner
 
19 - 10.01.13 - 10:23
Чтобы найти 1 самый тяжелый такое ощущение что 24, значит самый тупой способ - 24 + 23 + 22 = 69. Но как-то не оптимально :)
   samozvanec
 
20 - 10.01.13 - 10:25
(16) чего уж там, сразу массы тогда
   alek_aab
 
21 - 10.01.13 - 10:26
из 25 один откладываем в сторону, оставшиеся делим на две кучки, взвешиваем между собой кучки. тяжелую кучку делим пополам. алгоритм повторяем, пока не останется 3 камня. добавляем отложенный в сторону, взвешиваем две кучки по два камня, взвешиваем камни между собой из легкой кучки, вуаля. Тяжелый камень из последнего замера плюс тяжелые два камня из предпоследнего замера дают решение.
   Stepa86
 
22 - 10.01.13 - 10:27
можно тупо по олимпийской системе без финала, но с игрой за третье место... итого 24
   Gesperid
 
23 - 10.01.13 - 10:27
(16) не гони, я погуглил нормально
нашёл ссылку на теорему Шрейнера-Кислицына
   Stepa86
 
24 - 10.01.13 - 10:28
(21) а если в твоей отложенной после первого взвешивания все три чемпиона сидят, а все остальные очень легкие?
   SeraFim
 
25 - 10.01.13 - 10:29
(22) в первом туре встретятся самый тяжелый и второй по тяжести.
ВторойПоТяжести, ДавайДоСвиданья
   alek_aab
 
26 - 10.01.13 - 10:29
(24) блин, так нельзя. такую идею опроверг... :)
   Stepa86
 
27 - 10.01.13 - 10:29
(26) меня вон (25) тоже вышиб =)
   samozvanec
 
28 - 10.01.13 - 10:30
(22) по олимпийской системе 21 получается взвешивание
   Stepa86
 
29 - 10.01.13 - 10:30
предлагаю квиксорт и взять топ3
   SeraFim
 
30 - 10.01.13 - 10:31
(29) тоже думал про это... запутался при подсчете наихудшего случая)
   samozvanec
 
31 - 10.01.13 - 10:31
(29) собственно квиксорт нам и предлагают сделать, интересует количество итераций
   Gesperid
 
32 - 10.01.13 - 10:32
(29) квиксорт неоптимален, тогда уж TriSort или Пирамидальную
   Stepa86
 
33 - 10.01.13 - 10:32
(28) в классической олимпийской системе количество дуэлей = количество участников -1, а т.к. мы финал заменили матчем за 3ье, то 24 так и остается
 
 
   Gesperid
 
34 - 10.01.13 - 10:32
+(32) не оптимален по числу сравнений в худшем случае
   1Сергей
 
35 - 10.01.13 - 10:33
1. Взвешиваем К1 и К2. Один тяжелее, другой легче.
2. Взвешиваем тяжелый с К3, если К3 тяжелее то перейти к 4.
3. Взвешиваем легкий с К3.
4. Взвешиваем К4 и самый тяжелый, если К4 тяжелее, то перейти к 7.
5. Взвешиваем К4 и средний. если если К4 тяжелее, то перейти к 7.
6. Взвешиваем К4 и легкий.
7. Взвешиваем К5 и самый тяжелый. Если К5 тяжелее, то готово
8. Взвешиваем К5 и второй по тяжести. Если К5 тяжелее, то готово
9. Взвешиваем К5 и третий по тяжести.
   Aleksey
 
36 - 10.01.13 - 10:41
(21) допустим, камни с весами 22, 33, 47 (это тяжёлые), 1, 2, 3, 4, 5, 6, 7, 8, и 9 грамм, а в правой - 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 и 21. Что покажут весы?
   1Сергей
 
37 - 10.01.13 - 10:42
ох, пля. там же 25 камней... показалось 5
   Stepa86
 
38 - 10.01.13 - 10:48
3 кучки: ТекТоп3, Треш и Неразобранное

1. помещаем первый камень в текТоп3 - 0 взвешиваний
2. второй сравниваем с первым из топа, сортируем - 1
3. третий сравниваем с 2мя из топа, сортируем - 2 в худшем, 1 в лучшем
4-25 текущий камень сравниваем с топом, сортируем, камень после 3го по весу в треш - 3 взвешивания в худшем случае, 1 в лучшем

итого 69 в худшем и 24 в лучшем случае
   MaxS
 
39 - 10.01.13 - 10:49
+(3)Такой алгоритм.  Один камень исключаем из взвешивания ;)
Взвешиваем половину камней 12-12, отбрасываем легкую половину,
6-6, 3-3.
Имеем 3 каки-то камня. По теории вероятностей есть вероятность, что эти камни и будут самые тяжелые.
Т.е. задачу (0) выполнили, минимум нужно 3 взвешивания. ;)

Можно просто не взвешивать, а случайно отобрать 3 камня. С небольшой вероятностью они и будут самыми тяжёлыми.
   Соло
 
40 - 10.01.13 - 10:51
Я бы делал неполными итерациями...

берётся любой камень и поочередно взвешивается по одному, пока не найдется три более тяжелых или не закончится цепочка(тогда этот и более тяжелые и есть из числа искомых). Как только нашлись три более тяжелых, то все камни с которыми взвешивался текущий и были легче его вместе с ним исключаются из дальнейшего поиска. Берем любой из трех более тяжелых и повторяем сначала.

Таким образом три взвешивания исключают минимум один камень, то есть максимум 66 взвешиавний
   samozvanec
 
41 - 10.01.13 - 10:55
(33) не, смотри: 12 взвешиваний, осталось 12 камней. потом еще 6, осталось 6. потом еще три. итого - 21. хоть нам и не подходит.
   КонецЦикла
 
42 - 10.01.13 - 11:01
А вес тяжелых камней одинаков или необязательно? :)
   Trance_1C
 
43 - 10.01.13 - 11:04
Брутфорс - 576 взвешиваний.
многослойный персертрон 5 скрытых нейронов на слой - 20 - 22 взвешивания.
   Trance_1C
 
44 - 10.01.13 - 11:06
+(43) ошибочка вышла, "Многослойный персептрон" - нейронная сеть.
   1Сергей
 
45 - 10.01.13 - 11:08
(42) одинаковых камней нет
   КонецЦикла
 
46 - 10.01.13 - 11:11
Точно, "разной массы"
   1Сергей
 
47 - 10.01.13 - 11:29
Функция ВзвеситьКамни()
   
   ГенераторСЧ = Новый ГенераторСлучайныхЧисел(666);
   Камни = Новый Массив(25);
   Для НомерКамня = 0 по 24 Цикл
       ВсёХорошо = Ложь;
       Пока Не ВсёХорошо Цикл
           ВесКамня = ГенераторСЧ.СлучайноеЧисло(1,100);
           ВсёХорошо = Камни.Найти(ВесКамня) = Неопределено;
       КонецЦикла;
       Камни[НомерКамня] = ВесКамня;
   КонецЦикла;
   
   КоличествоВзвешиваний = 0;
   
   КамниТоп3 = Новый Массив(3);
   КамниТоп3.Вставить(0,Камни[0]);
   
   Если Камни[0]>Камни[1] Тогда
       КамниТоп3.Вставить(1,Камни[1]);
   Иначе
       КамниТоп3.Вставить(0,Камни[1]);
   КонецЕсли;
   КоличествоВзвешиваний = КоличествоВзвешиваний + 1;
   
   Если Камни[1]>Камни[2] Тогда
       КамниТоп3.Вставить(2,Камни[2]);
   Иначе
       Если Камни[0]>Камни[2] Тогда
           КамниТоп3.Вставить(1,Камни[2]);
       Иначе
           КамниТоп3.Вставить(0,Камни[2]);
       КонецЕсли;
       КоличествоВзвешиваний = КоличествоВзвешиваний + 1;
   КонецЕсли;
   КоличествоВзвешиваний = КоличествоВзвешиваний + 1;
   
   Для НомерКамня = 3 по 24 Цикл
       
       Если Камни[НомерКамня]>КамниТоп3[2] Тогда
           Если Камни[НомерКамня]>КамниТоп3[1] Тогда
               Если Камни[НомерКамня]>КамниТоп3[0] Тогда
                   КамниТоп3.Вставить(0,Камни[НомерКамня]);
               Иначе
                   КамниТоп3.Вставить(1,Камни[НомерКамня]);
               КонецЕсли;
               КоличествоВзвешиваний = КоличествоВзвешиваний + 1;
           Иначе
               КамниТоп3.Вставить(2,Камни[НомерКамня]);
           КонецЕсли;
           КоличествоВзвешиваний = КоличествоВзвешиваний + 1;
       КонецЕсли;
       КоличествоВзвешиваний = КоличествоВзвешиваний + 1;
       
   КонецЦикла;
   
   Возврат КоличествоВзвешиваний;

КонецФункции


Процедура КнопкаВыполнитьНажатие(Кнопка)
   
   Для Идн=1 по 1000 Цикл
       Сообщить(ВзвеситьКамни());
   КонецЦикла;
   
КонецПроцедуры







35 взвешеваний
   ICWiner
 
48 - 10.01.13 - 11:33
Удачное стечение рандома? :) А если 1000 итераций прогнать, наихудший какой будет?
   1Сергей
 
49 - 10.01.13 - 11:35
(48) как раз 1000 итераций и делаю. Странно, что всегда получается 35 взвешиваний. Хотя, логически в худшем случае должно получится 69 взвешиваний.

Худший, это когда камни идут по порядку, от меньшего к большему
 
 Рекламное место пустует
   1Сергей
 
50 - 10.01.13 - 11:37
Во, смодулировал такую ситуацию - 69 взвешеваний
   ICWiner
 
51 - 10.01.13 - 11:38
(49) велик рандом, раз 35 взвешиваний постоянно :)
   Megas
 
52 - 10.01.13 - 11:38
Опять =(
Давай уж не 25 камней сразу 1000 ...

PS Эти задачи тут часто проскакивают только раньше было 9.
   1Сергей
 
53 - 10.01.13 - 11:39
(50) + в лучшем случае 24 взвешеваний
   Gesperid
 
54 - 10.01.13 - 11:39
(47) вроде как <= 32 должно быть
   1Сергей
 
55 - 10.01.13 - 11:39
(52) дык, ответ-то какой?
   Stepa86
 
56 - 10.01.13 - 11:40
(50) почему 69? минимум 66 же должен быть
   Stepa86
 
57 - 10.01.13 - 11:41
(51) в 1Ске какой то тупой рандом, если в цикле сделать получение случайного числа, то иногда бывает, что все случайные числа одинаковые.
   1Сергей
 
58 - 10.01.13 - 11:41
(56) у меня первые три камня выкладываются по весу. А это +3 взвешивания
   Stepa86
 
59 - 10.01.13 - 11:42
(58) это лишнее так то
   1Сергей
 
60 - 10.01.13 - 11:43
(59) прав. мне нужно только знать самый легкий из Топ3
   Stepa86
 
61 - 10.01.13 - 11:46
(60) если знать самый легкий из топ3, то достаточно только с ним взвешивать в каждой итерации, а не со всем топом. Вот только в случае внесение в топ нового камня нужно пересортировку делать, что в худшем случае дела не меняет
   ICWiner
 
62 - 10.01.13 - 11:46
Мне кажется, что по решению из (18) в самом плохом случае 66 будет итераций...
   1Сергей
 
63 - 10.01.13 - 11:59
(61) не нужно пересортировывать. просто, при попадании нового камня в топ 3 (Если он тяжелее самого лёгкого из Топ3), то предыдущий самый лёгкий из Топ3 вылетает
   1Сергей
 
64 - 10.01.13 - 11:59
хотя, нет. ты прав. нужно опять узнавать самый легкий
   Andrew_1C
 
65 - 10.01.13 - 12:05
У меня получился алгоритм в 43 взвешивания.
Если изначально разделить 25 камней на 5 кучек по 5 камней и в каждой из них найти максимальный - 20 взвешиваний.
Потом отсортировать камни ( но при этом надо помнить какой камень был взят из какой кучки!) получаем последовательность из 5 камней отсортированных по весу. ( это еще 10 взвешиваний)
Самый тяжелый уже найден. Его можно отложить. Два самых легких из выдранных камей можно убрать, т.к. Они точно не самые тяжелые.
Также можно убрать 3 кучки по 4 камня из которых были взяты самые легкие из пяти- они тоже не подходят.
В итоге получаем 1 самый тяжелый камень и еще 10 камней из которых надо найти 2 самых тяжелых.
Это делается аналогично - разбиваем на две кучки по 5 камней и тд
В итоге получается 43 взвешивания
   1Сергей
 
66 - 10.01.13 - 12:07
>>Также можно убрать 3 кучки по 4 камня из которых были взяты самые легкие из пяти- они тоже не подходят.

не три, а две
   Andrew_1C
 
67 - 10.01.13 - 12:11
Три т.к. третий камень самый тяжелый в своей кучке был
   1Сергей
 
68 - 10.01.13 - 12:13
(67) и? в них не может быть камней Топ3?
   1Сергей
 
69 - 10.01.13 - 12:14
хотя, да. не может
   Andrew_1C
 
70 - 10.01.13 - 12:14
Не может т.к. Они легче самого легкого из топ3
   ICWiner
 
71 - 10.01.13 - 12:16
Да все правильно, 2 кучки только убираем, первые три кучи надо оставить. В каждой из них могут быть все топ 3
   ICWiner
 
72 - 10.01.13 - 12:18
такс, попробуем чуть подредактировать:

Если изначально разделить 25 камней на 5 кучек по 5 камней и в каждой из них найти максимальный - 20 взвешиваний.
Потом отсортировать камни ( но при этом надо помнить какой камень был взят из какой кучки!) получаем последовательность из 5 камней отсортированных по весу. ( это еще 10 взвешиваний)

нам не нужно сортировать все 5, нужно найти 3 самых тяжелых из 5, а это 4+3+2 = 9;

Самый тяжелый уже найден. Его можно отложить. Два самых легких из выдранных камей можно убрать, т.к. Они точно не самые тяжелые.
Также можно убрать 3 кучки по 4 камня из которых были взяты самые легкие из пяти- они тоже не подходят.
В итоге получаем 1 самый тяжелый камень и еще 10 камней из которых надо найти 2 самых тяжелых.

Тут да, убираем 2 кучки по 4 камня из которых были взяты самые легкие. Итого осталось
25 -10 -1 = 14 камней из которых надо выбрать 2 самых тяжелых и у нас потрачено 29 итераций.
3 кучки 5 5 4 - 11 итераций и есть 3 самых тяжелых в кучке. 3 взвешивания и знаем самый тяжелый. Убираем самую легкую кучку. Итого:


43 взвешивания, 9 камней осталось и два самых тяжелых найдено.


4 и 5 камней = 7 итераций для самого тяжелого в куче и 1 для самого тяжелого из этих топов. Итого 51 итерация... Так мб?
   ICWiner
 
73 - 10.01.13 - 12:19
Блин, 3-я кучка самая легкая же...
   Andrew_1C
 
74 - 10.01.13 - 12:20
Убираем 3 кучки. Кучка самого легкого из топ3 нас тоже не интересует. Кстати 42 взвешивания. Тк не надо все 5 камней сортировать. Надо найти только 3 самых тяжелых
   ICWiner
 
75 - 10.01.13 - 12:20
(74) Да, прав :)
   SeraFim
 
76 - 10.01.13 - 12:22
Спасибо большое автору!
Пока добирался домой, было чем заняться :)

Посчитать - запутался. Получилось от 37 до 40 взвешиваний.
Щас все распишу
   Andrew_1C
 
77 - 10.01.13 - 12:23
Можно еще поиграться размерами кучек - они были взяты наобум))
   1Сергей
 
78 - 10.01.13 - 12:24
(65) >>Потом отсортировать камни ( но при этом надо помнить какой камень был взят из какой кучки!) получаем последовательность из 5 камней отсортированных по весу. ( это еще 10 взвешиваний)

не надо полностью отсортировывать. нужно получить три самых тяжелых, выстроенных по порядку, а это 9 взвешиваний
   Мимо Проходил
 
79 - 10.01.13 - 12:25
Строим олимпийскую сетку. Проводим 24 схватки.
Имеем чемпиона, который проведет 5 или 4 боя. Имеем в худшем случае 5 претендентов на второе место.
еще 4 схватки по олимпийке и известен 2-й призер. Ему пришлось 3-х максимум сделать.
Этим троим в 2-х схватках придется выявить "потенциально третьего"
Второй в первом раунде сделал максимум 4-х. Вот этим 5 и надо в 4-х выявить бронзу.
24+4+2+4
   Мимо Проходил
 
80 - 10.01.13 - 12:26
+(79) Еще 3 забыл - итого 37
   1Сергей
 
81 - 10.01.13 - 12:35
(65) и всё-равно не понятно откуда 43 получилось.
20+9 согласен.
а дальше не расписано
   Andrew_1C
 
82 - 10.01.13 - 12:38
Дальше имеем 1 самый тяжелый и 2 кучки по 5 камней. По 4 взвешивания для определения самого тяжелого + 1 на определение самого тяжелого из двух. Отбрасываем еще 4 камня  и в оставшихся 5 ищем самый тяжелый -еще 4 взвешивания 8+1+4
   SeraFim
 
83 - 10.01.13 - 12:39
Идея такая. 1 камень выкидываем.
Найдем 3 самых тяжелых из 24. Оставшийся сможем в любом случае за 2 взвешивания проверить :)

1 вариант:
Разбиваем всё на 8 кучек по 3 камня в каждой.
Упорядочим камушки по тяжести в каждой кучке. Для этого понадобится 2*8 = 16 взвешиваний.
Выбираем из 8 самых тяжелых камней - самый тяжелый. На это уйдет 7 взвешиваний. Итого 16 + 7 = 23 взвешивания.
Самый тяжелый найден! Теперь будем искать второй по тяжести.
Кучку, в которой был СамыйТяжелыйКамень назовем МогучейКучкой.
Далеее сравниваем самые тяжелые камни и второй по тяжести из МогучейКучки. еще 7 сравнений = 30.
Если ВторойПоТяжести оказался из другой - поменяем его со вторым из МогучейКучки. При этом нужно проверить - вдруг перемещаемый камешек станет самым тяжелым в новой кучке +1 сравнение = 31 взвешивание.
Далее сравниваем самые тежелые и третий по тяжести из МогучейКучки. еще +7 сравнений = 38

ИТОГО: 38 взвешиваний + 2 на 25-ый камень = 40 взвешиваний

Еще варианты:
разбить на 4 кучки по 6, 6 кучек по 4, и 3 кучки по 8. Но если правильно посчитал, они хуже...
   1Сергей
 
84 - 10.01.13 - 12:51
(83) для того, чтобы упорядочить 3 камня, 2 взвешивания не достаточно
   exchang
 
85 - 10.01.13 - 12:55
1ая очередь получаем 6 пар с 13ти взвешеваний
2очередь получаем 3 пары с 6ти взвешеваний
3я очередь остается 3 камня с 3х взвешеваний
итого 13+6+3=22
   1Сергей
 
86 - 10.01.13 - 12:56
что-то никто ещё не предложил какого-нибудь варианта, где взвешивались бы кучки
   Gesperid
 
87 - 10.01.13 - 13:04
(85) меньше 25?
   SeraFim
 
88 - 10.01.13 - 13:06
(42) блин, точно... тогда еще +2...
+1 взвешивание, чтобы определить порядок в той кучке, где самый тяжелый.
и +1 там где найдется второй по тяжести.

Получается 42
   1Сергей
 
89 - 10.01.13 - 13:10
(88) вместо "2*8 = 16" надо "3*8 = 24"
   SeraFim
 
90 - 10.01.13 - 13:14
(89) неа, в для всех кучек это не обязательно делать. Там достаточно определить самый тяжелый
   dk
 
91 - 10.01.13 - 13:40
24?
   dk
 
92 - 10.01.13 - 13:42
ну или 25 )
   dk
 
93 - 10.01.13 - 13:48
(87) по твоей методе 24 взвешивания получается
   dk
 
94 - 10.01.13 - 13:58
(93) к (85)
щас посовещались - решение неверное, т.к. если сравниваешь два  самых тяжелых в 1-м цикле взвешиваний, то 2-й по тяжести можешь выкинуть.
   exchang
 
95 - 10.01.13 - 14:39
(94) угу, тогда никак
   dk
 
96 - 10.01.13 - 15:25
отбой - 25 не верный ответ
   Мимо Проходил
 
97 - 10.01.13 - 15:26
Возвращаясь к 79.
1тур олимпийки. 5 раундов
25 -> 16 -> 8 -> 4 -> 2 -> 1
24 взвешивания определяют победителя. Из 5(4) взвешиваний, в которых принимал участие победитель, есть второй по тяжести, т.к. только самый тяжелый мог пройти дальше в паре с ним.

2 тур олимпийки. 3 раунда
Участвуют проигравшие чемпиону. 5 максимум
5 -> 4 -> 2 -> 1
4 взвешивания дают 2-й по тяжести камень.

3-й тур. 3 раунда
3 неудачника из второго тура, проигравшие второму призеру и 5 неудачников из 1-го тура, проигравшие ему же выходят в 3-й тур. Ибо только проигравшие очно второму/первому могут быть третьими.
8 - 4 - 2 - 1
7 взвешиваний.

Итого 24 + 4 +7 = 35

Что не так?
   Gesperid
 
98 - 10.01.13 - 15:28
(97) докажи минимальность
   Мимо Проходил
 
99 - 10.01.13 - 15:38
(98) А кто-то нашел меньший вариант?
   Gesperid
 
100 - 10.01.13 - 15:40
  1  2   

Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Тема не обновлялась длительное время, и была помечена как архивная. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
Рекламное место пустует