Черная кошка
Гений-Говорун
Offline
Сообщений: leet
СПАСИБО
-вы поблагодарили: 362
-вас поблагодарили: 215
я не ангел, но ведь и жизнь- не рай.
|
|
� : Август 05, 2013, 12:59:48 � |
|
Возможно и была. Но вот я сколько не просмотрела, развернутого ответа нигде не нашла, сама решала, получилось 99 монет, а по ответу гораздо больше . Если можно дать не просто ответ, а развернутое решение. Просто интересно.
Даны чашечные весы, имеющие особенность — они могут выдержать ровно 3 взвешивания (неважно в каком порядке) неравных грузов, после чего ломаются. Одинаковые веса можно уравновешивать на этих весах бесконечное количество раз. Среди N монет есть одна фальшивая, вес которой меньше настоящих.
Найдите максимальное N при котором можно найти фальшивую не более, чем за 7 взвешиваний на этих весах.
|
|
|
Записан
|
|
|
|
☭-Изделие 20Д
|
|
� Ответ #1 : Август 05, 2013, 14:14:03 � |
|
Возможно и была. Но вот я сколько не просмотрела, развернутого ответа нигде не нашла, сама решала, получилось 99 монет, а по ответу гораздо больше . Если можно дать не просто ответ, а развернутое решение. Просто интересно.
Даны чашечные весы, имеющие особенность — они могут выдержать ровно 3 взвешивания (неважно в каком порядке) неравных грузов, после чего ломаются. Одинаковые веса можно уравновешивать на этих весах бесконечное количество раз. Среди N монет есть одна фальшивая, вес которой меньше настоящих.
Найдите максимальное N при котором можно найти фальшивую не более, чем за 7 взвешиваний на этих весах.
Очень оригинальная трактовка вопроса Очевидно 7 и есть максимальное число если в фильтрах - "не более чем за 7 Да и имхо в таких задачач искать МАКСИМАЛЬНОЕ ЧИСЛО - чушь - однозначно - бесконечность, сиди и взвешивай 1-1, 2-2 ну и т.д. "
|
|
� Последнее редактирование: Август 05, 2013, 14:23:12 от Изделие 20Д �
|
Записан
|
|
|
|
Руслан Дехтярь
Гость
|
|
� Ответ #2 : Август 05, 2013, 14:43:56 � |
|
У меня тоже пока 99 получается. иду от обратного: в конце должно быть 3 монеты.
|
|
|
|
iPhonograph
Гений-Говорун
Offline
Сообщений: 2100
СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315
Дискоед
|
|
� Ответ #3 : Август 05, 2013, 16:45:11 � |
|
379 решение: Показать скрытый текст local function f(total, unequal) unequal = math.min(total, unequal) if unequal == 0 then return 1 else return f(total - 1, unequal - 1) * 2 + f(total - 1, unequal) end end
print(f(7, 3))
|
"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
|
|
|
Черная кошка
Гений-Говорун
Offline
Сообщений: leet
СПАСИБО
-вы поблагодарили: 362
-вас поблагодарили: 215
я не ангел, но ведь и жизнь- не рай.
|
|
� Ответ #4 : Август 06, 2013, 07:24:26 � |
|
я же просила решение, а не мнение, чушь это или не чушь, если не понимаете, зачем захламлять тему?
|
|
|
Записан
|
|
|
|
Черная кошка
Гений-Говорун
Offline
Сообщений: leet
СПАСИБО
-вы поблагодарили: 362
-вас поблагодарили: 215
я не ангел, но ведь и жизнь- не рай.
|
|
� Ответ #5 : Август 06, 2013, 07:27:58 � |
|
379
решение:
в ответе написано 527, а вот решения там нет, как они пришли к этому числу.
|
|
|
Записан
|
|
|
|
Руслан Дехтярь
Гость
|
|
� Ответ #6 : Август 06, 2013, 13:51:25 � |
|
Фиг его знает. я до 219 досчитал:) 1 взвешивание: 33 и 33. 153 остается. Если в одной из кучек по 33 есть фальшивая- находим еще за 6 взвешиваний. Если 33 = 33, берем из оставшейся кучи 153 по 27(нужно, чтоб в случае равенства весов, осталось еще 1 взвешивание неравных весов). Взвешиваем. Показывают неравенство. Находим фальшивую. Нет. Берем из большей оставшейся кучи по 21 монет (за 5 взвешиваний, включая 2 возможности взвесить неравный вес). и так далее...
|
|
|
|
Черная кошка
Гений-Говорун
Offline
Сообщений: leet
СПАСИБО
-вы поблагодарили: 362
-вас поблагодарили: 215
я не ангел, но ведь и жизнь- не рай.
|
|
� Ответ #7 : Август 06, 2013, 13:56:07 � |
|
RD Фиг его знает. я до 219 досчитал:) Уже прогресс. Попробую посчитать с конца. с 527 , только вот как это число разбить.
|
|
|
Записан
|
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #8 : Август 06, 2013, 20:33:28 � |
|
Прочтите ещё раз решение iPhonograph и вникните в него. Даю подсказки. Если нам можно К раз взвешивать, но только 1 раз из этих К допускается неравенство, то мы можем выделит лёгкую из 2К+1 монет: каждый раз взвешивается пара, неравенство даёт ответ, равенство -> берём следующую пару и т.д. Если все 2К взвешиваний дали равенство, то последняя (2К+1)-я монета фальшивая. Теперь рассмотрим в-т когда дважды допускается неравенство и можно К раз взвешивать. 1-е взвешивание: 2К-1 монета на одной чашке и столько же на другой. В случае неравенства - у нас ещё есть К-1 взвешивание для 2К-1 монеты. В случае равенства - 2-е взвешивание - по 2К-3 монеты на каждой чашке и т.д. То есть всего можно взвесить: 2К-1 + 2K-3 + 2K-5... и т.д. - сумму найти просто. По аналогичному принципу определяется общее кол-во монет, когда допустимы 3 взвешивания с неравенством и т.д. iPhonograph привёл рекурсивное решение общего вида (или рекуррентное, уж и не помню как верно).
|
|
|
|
Черная кошка
Гений-Говорун
Offline
Сообщений: leet
СПАСИБО
-вы поблагодарили: 362
-вас поблагодарили: 215
я не ангел, но ведь и жизнь- не рай.
|
|
� Ответ #9 : Август 08, 2013, 06:52:44 � |
|
buka а васне смущает вот это условие? Найдите максимальное N при котором можно найти фальшивую не более, чем за 7 взвешиваний
|
|
|
Записан
|
|
|
|
Руслан Дехтярь
Гость
|
|
� Ответ #10 : Август 08, 2013, 15:46:37 � |
|
Прочтите ещё раз решение iPhonograph и вникните в него. Даю подсказки. Если нам можно К раз взвешивать, но только 1 раз из этих К допускается неравенство, то мы можем выделит лёгкую из 2К+1 монет: каждый раз взвешивается пара, неравенство даёт ответ, равенство -> берём следующую пару и т.д. Если все 2К взвешиваний дали равенство, то последняя (2К+1)-я монета фальшивая. Теперь рассмотрим в-т когда дважды допускается неравенство и можно К раз взвешивать. 1-е взвешивание: 2К-1 монета на одной чашке и столько же на другой. В случае неравенства - у нас ещё есть К-1 взвешивание для 2К-1 монеты. В случае равенства - 2-е взвешивание - по 2К-3 монеты на каждой чашке и т.д. То есть всего можно взвесить: 2К-1 + 2K-3 + 2K-5... и т.д. - сумму найти просто. По аналогичному принципу определяется общее кол-во монет, когда допустимы 3 взвешивания с неравенством и т.д. iPhonograph привёл рекурсивное решение общего вида (или рекуррентное, уж и не помню как верно).
К сожалению то, что написал iPhonograph, для меня китайская грамота. Пусть он хоть тысячу раз прав. Ваши примеры мне более понятны. Но решение iPhonograph у меня что- то не получается:) Решаю так: Пусть сразу после 2- х взвешиваний неравных весов осталось X монет. То есть, после 2- го взвешивания Х монет. Тогда на втором взвешивании можно было бы взвесить X и X монет. X осталось бы в запасе. Тогда после первого взвешивания можно было бы взвесить 3X и 3X. X = 2*(K - 2) + 1 - где K - кол- во взвешиваний. То есть, кол- во монет при 7 попытках для взвешивания было бы: 6*(2*(K - 2) + 1) = 66 Если бы весы показали равенство при взвешивании 33 и 33, взяли бы 6 * (2(K-3)+1) = 54 на последних двух попытках для взвешивания можно оставить 9 монет для первого взвешивания (3+3+3), и (1+1+1), для последнего взвешивания оставим 3 монеты. Итого считаю и получаю: 231
|
|
� Последнее редактирование: Август 08, 2013, 15:57:35 от RD �
|
Записан
|
|
|
|
zhekas
Гений-Говорун
Offline
Сообщений: 1035
СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 486
|
|
� Ответ #11 : Август 08, 2013, 16:30:04 � |
|
Тогда на втором взвешивании можно было бы взвесить X и X монет. X осталось бы в запасе.
В запасе осталось бы не X, а больше.
|
|
|
Записан
|
|
|
|
Руслан Дехтярь
Гость
|
|
� Ответ #12 : Август 08, 2013, 16:35:02 � |
|
Тогда на втором взвешивании можно было бы взвесить X и X монет. X осталось бы в запасе.
В какой момент больше? В запасе при втором взвешивании я имел в виду. То есть : X = 2*(K-2)+1 на 2- м взвешивании можно было взвесить X и X, На первом - 3X и 3X.
|
|
|
Записан
|
|
|
|
zhekas
Гений-Говорун
Offline
Сообщений: 1035
СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 486
|
|
� Ответ #13 : Август 08, 2013, 16:41:09 � |
|
на 2- м взвешивании можно было взвесить X и X, На первом - 3X и 3X.
Почему из утверждения на 2- м взвешивании можно было взвесить X и X,
ты делаешь вывод, что На первом - 3X и 3X.
? На втором взвешивании ты взвешиваешь X и X, но в запасе у тебя остаётся не X, а какое-то Y большее X. Так что на первом взвешивании ты моешь взвесить 2X+Y и 2X+Y
|
|
� Последнее редактирование: Август 08, 2013, 16:44:05 от zhekas �
|
Записан
|
|
|
|
Руслан Дехтярь
Гость
|
|
� Ответ #14 : Август 08, 2013, 16:44:48 � |
|
Так: я на первом взвешивании взвешиваю 33 и 33 монеты (3X и 3X). В случае их неравенства проверяю кучку 3X с фальш. монетой взвешиванием X и X.
|
|
|
Записан
|
|
|
|
|