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

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

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

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

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

Таким образом три взвешивания исключают минимум один камень, то есть максимум 66 взвешиавний
41 samozvanec
 
10.01.13
10:55
(33) не, смотри: 12 взвешиваний, осталось 12 камней. потом еще 6, осталось 6. потом еще три. итого - 21. хоть нам и не подходит.
42 КонецЦикла
 
10.01.13
11:01
А вес тяжелых камней одинаков или необязательно? :)
43 Trance_1C
 
10.01.13
11:04
Брутфорс - 576 взвешиваний.
многослойный персертрон 5 скрытых нейронов на слой - 20 - 22 взвешивания.
44 Trance_1C
 
10.01.13
11:06
+(43) ошибочка вышла, "Многослойный персептрон" - нейронная сеть.
45 1Сергей
 
10.01.13
11:08
(42) одинаковых камней нет
46 КонецЦикла
 
10.01.13
11:11
Точно, "разной массы"
47 1Сергей
 
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 взвешеваний
48 ICWiner
 
10.01.13
11:33
Удачное стечение рандома? :) А если 1000 итераций прогнать, наихудший какой будет?
49 1Сергей
 
10.01.13
11:35
(48) как раз 1000 итераций и делаю. Странно, что всегда получается 35 взвешиваний. Хотя, логически в худшем случае должно получится 69 взвешиваний.

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

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

не три, а две
67 Andrew_1C
 
10.01.13
12:11
Три т.к. третий камень самый тяжелый в своей кучке был
68 1Сергей
 
10.01.13
12:13
(67) и? в них не может быть камней Топ3?
69 1Сергей
 
10.01.13
12:14
хотя, да. не может
70 Andrew_1C
 
10.01.13
12:14
Не может т.к. Они легче самого легкого из топ3
71 ICWiner
 
10.01.13
12:16
Да все правильно, 2 кучки только убираем, первые три кучи надо оставить. В каждой из них могут быть все топ 3
72 ICWiner
 
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 итерация... Так мб?
73 ICWiner
 
10.01.13
12:19
Блин, 3-я кучка самая легкая же...
74 Andrew_1C
 
10.01.13
12:20
Убираем 3 кучки. Кучка самого легкого из топ3 нас тоже не интересует. Кстати 42 взвешивания. Тк не надо все 5 камней сортировать. Надо найти только 3 самых тяжелых
75 ICWiner
 
10.01.13
12:20
(74) Да, прав :)
76 SeraFim
 
10.01.13
12:22
Спасибо большое автору!
Пока добирался домой, было чем заняться :)

Посчитать - запутался. Получилось от 37 до 40 взвешиваний.
Щас все распишу
77 Andrew_1C
 
10.01.13
12:23
Можно еще поиграться размерами кучек - они были взяты наобум))
78 1Сергей
 
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
81 1Сергей
 
10.01.13
12:35
(65) и всё-равно не понятно откуда 43 получилось.
20+9 согласен.
а дальше не расписано
82 Andrew_1C
 
10.01.13
12:38
Дальше имеем 1 самый тяжелый и 2 кучки по 5 камней. По 4 взвешивания для определения самого тяжелого + 1 на определение самого тяжелого из двух. Отбрасываем еще 4 камня  и в оставшихся 5 ищем самый тяжелый -еще 4 взвешивания 8+1+4
83 SeraFim
 
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. Но если правильно посчитал, они хуже...
84 1Сергей
 
10.01.13
12:51
(83) для того, чтобы упорядочить 3 камня, 2 взвешивания не достаточно
85 exchang
 
10.01.13
12:55
1ая очередь получаем 6 пар с 13ти взвешеваний
2очередь получаем 3 пары с 6ти взвешеваний
3я очередь остается 3 камня с 3х взвешеваний
итого 13+6+3=22
86 1Сергей
 
10.01.13
12:56
что-то никто ещё не предложил какого-нибудь варианта, где взвешивались бы кучки
87 Gesperid
 
10.01.13
13:04
(85) меньше 25?
88 SeraFim
 
10.01.13
13:06
(42) блин, точно... тогда еще +2...
+1 взвешивание, чтобы определить порядок в той кучке, где самый тяжелый.
и +1 там где найдется второй по тяжести.

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

Что не так?
98 Gesperid
 
10.01.13
15:28
(97) докажи минимальность
99 Мимо Проходил
 
10.01.13
15:38
(98) А кто-то нашел меньший вариант?
100 Gesperid
 
10.01.13
15:40
101 Gesperid
 
10.01.13
15:45
по формуле получается вроде как <= 32 взвешивания
102 DexterMorgan
 
10.01.13
16:46
(97) А почему в 3 туре так много взвешиваний? Ведь есть всего 5 камней, которые проиграли первому месту, второе определено, занчит всего 4 камня и -> 2 взвешивания определят  третье место.

<<<3 неудачника из второго тура, проигравшие второму призеру и 5 неудачников из 1-го тура, проигравшие ему же выходят в 3-й тур.

Это же одни и те же камни!
103 DexterMorgan
 
10.01.13
16:53
1 тур 12 + 6 + 3 + 2 (это с 25 камнем) + 1 = 24
2 тур всего 5 камней проиграли победителю, значит за 3 взвешивания можно найти 2 место
3 тур из 5 камней остается 4 - значит 2 взвешивания. Итого 24+3+2=29. Вроде как то.
104 DexterMorgan
 
10.01.13
16:54
Хотя не, первый тур правильно в (97), но вроде от этого результат не меняется
105 SUA
 
10.01.13
17:25
(101)по формуле <=(25-3)+3(LOG2(32))=22+15=37
106 SUA
 
10.01.13
17:36
(103)"2 тур всего 5 камней проиграли победителю, значит за 3 взвешивания.." за 4
"3 тур из 5 камней остается 4.." и до 4х, проигравших 2му месту, итого 8, 7 взвешиваний
107 DexterMorgan
 
10.01.13
18:01
(106) Из 5 камней? Почему за 4? --- 1 взвешивание имеем три камня, 2 взвешивание - 2 камня, ну и третье 1.

<<<"3 тур из 5 камней остается 4.." и до 4х, проигравших 2му месту, итого 8, 7 взвешиваний

Я не догоняю) После первого тура - 5 камней претендуют на 2,3 место. 1 камень занял 2. Значит осталось 4, ну и тд
108 SUA
 
14.01.13
13:16
(107)
"Из 5 камней? Почему за 4? --- 1 взвешивание имеем три камня," - как? одним взвешиванием выкинуть 2 камня из претендентов
на 2е - 5
на 3е - претендуют не только проигравшие 1му, но и проигравшие 2му
109 exchang
 
16.01.13
17:27
3 класс

17. Как тремя взвешиваниями определить одну фальшивую монету (более легкую) из 8? 10? 16? 17? 26? 27?

18. Из 80 одинаковых по виду монет одна – фальшивая (более легкая). Как ее определить четырьмя взвешиваниями на чашечных весах?

19. Как на чашечных весах уравновесить кусок металла массой в 47 г с помощью набора из пяти гирь: 1 г, 3 г, 9 г, 27 г, 81 г? Гири можно класть на обе чашки весов.

20. У брата и сестры вместе 10 монет. У брата 3-копеечные монеты, у сестры 2-копеечные монеты. У них денег поровну. Сколько монет у сестры?

21. Петя сказал однажды друзьям: "Позавчера мне было 9 лет, а в будущем году мне исполнится 12 лет". Какого числа родился Петя?

22. Назовите дату (число, месяц и год) первого дня двадцать первого века.

23. Который сейчас час, если оставшаяся часть суток вдвое больше прошедшей? втрое больше? вдвое меньше? впятеро меньше?

24. Имеем 3 сосуда вместимостью 8, 5 и 3 л. Наибольший сосуд полон молока. Как разделить это молоко на 2 равные части, используя остальные сосуды?

25. См. задачу № 24 для сосудов 12, 7 и 5 л.

26. На монетном заводе 100 рабочих. Каждому выдавали 1 кг золота для изготов-ления 100 монет по 10 г. Один стал делать монеты по 9 г, а сэкономленное золото при-сваивать. Как за одно взвешивание определить мошенника?

27. В  10  мешочках одинаковые на вид монеты. Но в одном  – они фальшивые – на 1 г легче настоящих. Как найти этот мешочек с помощью одного взвешивания?

28. С бароном Мюнхгаузеном за его долгую баронскую жизнь случилось 336 удивительных приключений и каждое было описано бароном в его замечательных книгах. С третьеклассником Федей за его школьные годы случилось вдвое больше приключений, и каждое послужило причиной опоздания в школу на 15 минут. На сколько суток в общей сложности опоздал на уроки за свои  школьные годы третьеклассник Федя?

29. Мотоциклист ехал 7 часов. Первый час он ехал со скоростью 20 км/ч, а каждый следующий увеличивал скорость на 10 км/ч. Его путь = ?

30. На I чашу весов положен кусок мыла, а на другую ? такого же куска и еще 50 г. Весы находятся в равновесии. Какова масса куска мыла?
110 only82
 
16.01.13
18:04
(97) Не понятно как ты определил второй по тяжести. Если взять ситуацию когда ты вначале выбрал камень который оказался самым тяжелым и он победил все 24 взвешивания. Какой тогда второй?
111 only82
 
16.01.13
18:42
(97) Я понял:
1    2        1    3        1    5        1    9        1    17
3    4        5    7        9    13        17    25            
5    6        9    11        17    21                        
7    8        13    15        25                            
9    10        17    19                                    
11    12        21    23                                    
13    14        25                                        
15    16                                                
17    18                                                
19    20                                                
21    22                                                
23    24                                                
25                                                    
                                                   
                                                   
2    3        2    5        2    17                        
5    9        17                                        
17                                                    
                                                   
                                                   
3    5        3    17                                    
17                                                    

25 + 4 + 2 = 31 взвешивание
112 Юный 1С
 
16.01.13
18:47
Нельзя сравнивать вес попарно как указано в (111). А если у тебя в паре попался самый тяжелый и второй по тяжести, то ты сразу выкидываешь второй.
113 only82
 
16.01.13
18:53
(112) Нет, не выкидываю. Наоборот он участвует в следующем туре.
114 SUA
 
17.01.13
13:32
(111)а теперь во 2м туре победил 17й, 3е место может быть у 16го
115 Мимо Проходил
 
17.01.13
13:58
(114) Все правильно. В 97 я ошибся на единицу. В первом туре максимум 5 туров, но проигравших 2-му может быть максимум -4, т.к. он сам проиграл в последнем для себя туре 1-му. Вот эти 4 и добавляются к 3-му туру
116 oleg_km
 
31.01.13
09:20
Мне кажется отсортировать пузырьковым способом (единственный который проходил в институте) или любым более оптимальным будет эффективнее всего
117 sda553
 
31.01.13
09:55
Сколькими способамт можно выбрать три камня из 24х? Безусловно это C(3,24)= 42504
Взвешивания на весах могут передавать нам информацию в трех видах, больше, равно, меньше. Таким образом в троичной системе исчисления каждое взвешивание это один разряд. Сколько требуется разрядов в троичной системе, чтобы закодировать числа от 1 до 42504?
Правильно, как минимум 10 рахрядов 3^10=59049

А значит нужно уж точно не менее 10ти взвешиваний, чтобы получить информацию о трех самых тяжелых камнях.
10 взвешиваний это слишком тяжко и поэтому решать неохота
118 Jump
 
31.01.13
10:09
Вроде сколько ни считал необходимый минимум взвешиваний 22раза.
Меньше не получается.
У кого меньше?
119 razlagator
 
31.01.13
10:58
(118) больше 22
120 Sidney
 
31.01.13
11:07
(0)Откладываем один камень. Две кучки на весы. Снимаем по одному с каждой стороны. Смотрим на отклонение. откладываем тяжелый из снятых. Итого 11 взвешиваний первая итерация. Осталась кучка из 12 камней. Делим пополам и повторяем. Это еще 5 взвешиваний. Дальше сами считайте :)
121 Мимо Проходил
 
31.01.13
11:11
(120) Допустим, один камень тяжелее всех остальных, вместе взятых, что не противоречит (0). И что даст твой алгоритм?
122 Мимо Проходил
 
31.01.13
11:39
+(121) Допустим чашечные весы сверхчуствительные, любая разница в весе на чашках приводит к "зашкаливанию", т.е. чашки оказываются в крайнем положении. Так что отклонения ты не увидишь, за исключением случая, когда сменится соотношение, т.е. тяжелая кучка станет легкой.
ЗЫ. Но это "лечится" тем, что не надо "все яйца класть в одну корзину", а достаточно взвешивать только пару из кучек, а хранить их не не на чашках, а просто рядом с ними.
123 sda553
 
31.01.13
13:24
(120) В конце этих итераций останется какой то камень, про который невозможно сказать ничего, кроме того, что он не самый легкий
124 sda553
 
31.01.13
13:37
я в 50 парных взвешиваний нашел решения
125 sda553
 
31.01.13
13:42
(116) Нет, один "пузырьковый проход" уже 25 взвешиваний, чтобы всплыл самый нжний надо где то 24*25 взвешиваний, что многовато
126 Sidney
 
31.01.13
15:28
(121)Согласен, косяк.
Другая мысль.
Берем первые три камня, первые два взвешивания что бы упорядочить их по степени тяжести. Далее кладем их слева(от весов, не на весы :) ), остальные справа и 4ый сравниваем с самым тяжелым слева. Если тяжелее выкидываем самый легкий слева, если нет, сравниваем с оставшимися двумя по очереди. И того 2 +21*3 взвешиваний.
127 sda553
 
31.01.13
15:41
(126) много
128 Мимо Проходил
 
31.01.13
15:59
(126) Тогда уж сравнивать со средним, и в зависимости от результата или с 1-м или с 3-им
129 acsent
 
31.01.13
16:01
вот они 1сники - ничего кроме пузырька и не знают. А большинство даже пузырька не знают
130 NS
 
31.01.13
16:04
количество сочетаний из трех камней - 25*24*23/6=2300
Каждое взвешивание дает один из двух возможных вариантов.
ограничение снизу на количество взвешиваний - 13.
Правильный ответ будет либо 13, либо чуть больше.
131 NS
 
31.01.13
16:05
(117) Ты неправильно сосчитал. В задании нет условия ранжировки трех самых тяжелых камней по весу. И даже если бы было, всё-равно неправильно посчитано.
132 Sidney
 
31.01.13
17:30
(128)Тогда 2+21*2 но все равно много :(
133 NS
 
31.01.13
20:06
(130) (131) нет, я вру. Все так просто только если нам известны веса камней, но неизвестно кто есть кто.
134 NS
 
31.01.13
20:49
(0) где ты взял такую задачу?
Если одновременно на каждую сторону весов можно класть только по одному камню, то есть формула оценки необходимого числа сравнений, но это уже далеко не школьный курс.
Как задача сформулирована в (0) - думаю решение на данный момент неизвестно никому.
135 sanya_nickname
 
01.02.13
02:32
(0) 29 взвешиваний
136 sanya_nickname
 
01.02.13
02:54
(135) точнее 28
137 sanya_nickname
 
01.02.13
07:09
(136) както так
Чемпионат по турам:
1 тур 12 взвешиваний (один камень отбросили)
2 тур 6 взвешиваний
3 тур 3 взвешивания
4 тур 2 взаешивания (тут прибавляем ранее отброшеный 25-й камень)
5 тур 1 взвешиввание-нашли чемпиона
итого 24 взвешивания
далее:
6 тур берем лузера из 5 тура и лузера 4 тура(против чемпиона) (1 взвешивание)
7 тур берем победителя 6 тура и лузера 1 тура(против чемпиона) (1 взвешивание)
8 тур берем победителя 7 тура и лузера 2 тура(против чемпиона) (1 взвешивание) борьба за второе место
9 тур берем победителя 6 тура и лузера 8тура (1 взвешивание) борьба за третье место
плюсуем еще 4 взвешивания
Ответ 28 взвешиваний.
138 sda553
 
01.02.13
07:16
(137) Третье место было побеждено вторым местом в первом туре. Твое решение третье место тогда не нашло
139 sanya_nickname
 
01.02.13
07:29
(138) ок тогда делаем еще 1 проверку: победителя 9 тура сравним с лузером 1 тура(со вторым местом)
140 sda553
 
01.02.13
09:41
(139) тогда след. сценарий: 25-ый камень(отброшенный) был чемпионом.
Тогда у нас нет однозначного лузера 1го и 2го тура, которые против чемпиона. Т.к. никто на 1м 2м не был чемпионом.
Ну вообщем дыр в твоей методе до фига, я не хочу по одной все находить
141 sanya_nickname
 
01.02.13
16:15
(140) Думай шире, вместо чемпиона что мешает рассмотреть ветку по которой шел второй призер? докажи что метод не работает
142 sda553
 
01.02.13
16:46
(141) В третьем туре чемпион бился со вторым местом. Второе место по твоему алгоритму вылетело и больше в соревнованиях не участвовало
143 sda553
 
01.02.13
16:55
Но логика твоя понятна.
1. За 5 туров выявляем чемпиона - 24 взвешивания
2. Кандидаты на второе место это 5 камней побитых чемпионом за 5 туров, выявляется за 3 взвешивания
3. Кандидаты на третье место, это 4 бывших кандидата на второе место и максимум 4 камня побитые вторым местом за 4 тура, итого 8 претендентов, определяются за 3 взвешивания

Итого 30 взвешиваний
144 sda553
 
01.02.13
16:57
ой, спутал взвешивания с турами
по 2. 5 камней 4 взвешивания
по 3. 8 камней 7 взвешиваний
Итого 35 взвешиваний
Оптимист верит, что мы живем в лучшем из миров. Пессимист боится, что так оно и есть.