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

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

25 камней

25 камней
Я
   Undefined vs NULL
 
10.01.13 - 10:03
Есть 25 камней разной массы и чашечные весы без гирь. Какое минимальное число взвешиваний нужно, чтобы найти три камня наибольшей массы?
 
 
   Gesperid
 
101 - 10.01.13 - 15:45
по формуле получается вроде как <= 32 взвешивания
   DexterMorgan
 
102 - 10.01.13 - 16:46
(97) А почему в 3 туре так много взвешиваний? Ведь есть всего 5 камней, которые проиграли первому месту, второе определено, занчит всего 4 камня и -> 2 взвешивания определят  третье место.

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

Это же одни и те же камни!
   DexterMorgan
 
103 - 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. Вроде как то.
   DexterMorgan
 
104 - 10.01.13 - 16:54
Хотя не, первый тур правильно в (97), но вроде от этого результат не меняется
   SUA
 
105 - 10.01.13 - 17:25
(101)по формуле <=(25-3)+3(LOG2(32))=22+15=37
   SUA
 
106 - 10.01.13 - 17:36
(103)"2 тур всего 5 камней проиграли победителю, значит за 3 взвешивания.." за 4
"3 тур из 5 камней остается 4.." и до 4х, проигравших 2му месту, итого 8, 7 взвешиваний
   DexterMorgan
 
107 - 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, ну и тд
   SUA
 
108 - 14.01.13 - 13:16
(107)
"Из 5 камней? Почему за 4? --- 1 взвешивание имеем три камня," - как? одним взвешиванием выкинуть 2 камня из претендентов
на 2е - 5
на 3е - претендуют не только проигравшие 1му, но и проигравшие 2му
   exchang
 
109 - 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 г. Весы находятся в равновесии. Какова масса куска мыла?
   only82
 
110 - 16.01.13 - 18:04
(97) Не понятно как ты определил второй по тяжести. Если взять ситуацию когда ты вначале выбрал камень который оказался самым тяжелым и он победил все 24 взвешивания. Какой тогда второй?
 
 Рекламное место пустует
   only82
 
111 - 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 взвешивание
   Юный 1С
 
112 - 16.01.13 - 18:47
Нельзя сравнивать вес попарно как указано в (111). А если у тебя в паре попался самый тяжелый и второй по тяжести, то ты сразу выкидываешь второй.
   only82
 
113 - 16.01.13 - 18:53
(112) Нет, не выкидываю. Наоборот он участвует в следующем туре.
   SUA
 
114 - 17.01.13 - 13:32
(111)а теперь во 2м туре победил 17й, 3е место может быть у 16го
   Мимо Проходил
 
115 - 17.01.13 - 13:58
(114) Все правильно. В 97 я ошибся на единицу. В первом туре максимум 5 туров, но проигравших 2-му может быть максимум -4, т.к. он сам проиграл в последнем для себя туре 1-му. Вот эти 4 и добавляются к 3-му туру
   oleg_km
 
116 - 31.01.13 - 09:20
Мне кажется отсортировать пузырьковым способом (единственный который проходил в институте) или любым более оптимальным будет эффективнее всего
   sda553
 
117 - 31.01.13 - 09:55
Сколькими способамт можно выбрать три камня из 24х? Безусловно это C(3,24)= 42504
Взвешивания на весах могут передавать нам информацию в трех видах, больше, равно, меньше. Таким образом в троичной системе исчисления каждое взвешивание это один разряд. Сколько требуется разрядов в троичной системе, чтобы закодировать числа от 1 до 42504?
Правильно, как минимум 10 рахрядов 3^10=59049

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

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

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