Динка, ма-ла-дец!!!
Вид для печати
Динка, ма-ла-дец!!!
Вся в смущении и в реверансах!!! ))
Балдею и наслаждаюсь по полной программе от прочитанного...
Молодцы !!!
Кирпич весит 1 кг плюс еще пол кирпича. Сколько весит кирпич?
1 кг наверное :):):)
Нет.
Еще варианты?
И заодно задачка (решение есть, я его еще не нашла) 10 монет, 1 из них или легче, или тяжелее. Весы (2 чашечки) и 3 (три) взвешивания. Задача - найти эту монетку.
Цитата:
Сообщение от Меламори
да.Цитата:
Сообщение от Меламори
Кирпич весит пол-кирпича плюс 1 кг.
Сколько весит кирпич?
2 кг.
Решения при такой постановке нет. Для гарантированного нахождения требуется Log(10) по степени 2, т.е. более трех взвешиваний.Цитата:
Сообщение от Меламори
Решение есть.Цитата:
Сообщение от Smic
Это стандартная задача из любого учебника по программированию, за 3 взвешивания можно найти фальшивую монетку если изначально дано до 13 монет и неизвестно фальшивая тяжелее или легче настоящих.
Решение не сложное, хотя и не такое очевидное, как в случае с 9 монетами. :) Мы всей фирмой думали 2 дня, быстрее всех решил директор и даже преобразовал задачку в фокус:"Загадай какая монетка фальшивая, а я отгадаю", очень весело было. :p
2 кгЦитата:
Сообщение от Меламори
Готов рассмотреть, но очень сомневаюсь, что Вы сможете его представить, т.к.Цитата:
Сообщение от Nass
И называется она "двоичный поиск". И из теории решения этой задачи известно, что минимальное число попыток, необходимое для гарантированного нахождения с помощью двоичного поиска нужного элемента из множества N элементов требуется Log(N) по степени 2 попыток.Цитата:
Это стандартная задача из любого учебника по программированию
Могу опубликовать, если остальные не против. :)Цитата:
Сообщение от Smic
Nass, опубликуйте пожалуйста :)
Так какой же ответ правильный???Цитата:
Сообщение от Меламори
pretty, 2 кг читай мой пост 48 :):):)
2 кг. :)
Монетки - действительно до 13 решаемы. :)
Вау! Я правильно посчитала!!! :):):):) уууууу... нананана.....ууууу.....
Ну так мозги ж варят, не зря вчера диплом защитила :)
Не могли бы Вы представить это решение?Цитата:
Сообщение от Меламори
Меламори, по чему до 13? есть прикол с 16-ю. Задача № 2 http://bspu.ab.ru/Department/WMiP/Me.../logika_b.html
Это не прикол. Это просто совсем другая задача.Цитата:
Сообщение от sema
Smic, они все похожие есть даже с 40 монетками.
sema, они похожи только наличием двоичного поиска (весы) и тем, что в них используются монетки. Но ищется в каждой задаче разное.
с 12-ю решение.Цитата:
Сообщение от Smic
{1,2,3,4,5,6,7,8,9,10,11,12} - множество всех монеток
Lk - множество монеток на левой чашке весов при k-м взвешивании
Rk - тоже для правой чашки
Н - множество хороших монеток
н - хорошая монетка
ф - фальшивая монетка
I взвешивание
L1 = {1,2,3,4}, R1 = {5,6,7,8}
возможны два случая:
1) Весы в равновесии
Н = {1,2,3,4,5,6,7,8}, ф принадлежит {9,10,11,12}
Нужно найти среди четырех монеток фальшивую за два взвешивания. Этот случай можно свести к взвешиванию II' (см. ниже).
2) Весы отклонились в какую-либо сторону, тогда
H = {9,10,11,12}, ф принадлежит {1,2,3,4,5,6,7,8}
II взвешивание
L2 = {3,4,6,7}, R2 = {2,8,н,н}
возможны 3 случая:
2.1)Весы в равновесии, значит
ф принадлежит {1,5}
За одно взвешивание среди них можно найти фальшивую, сравнив любую из них с н
2.2)Весы отклонились в ту же сторону, что и при первом взвешивании, значит фальшивая монета среди тех, которые не перекладывались в соседнюю чашку, т.е.
ф принадлежит {3,4,8}
2.3)Весы отклонились в сторону противоположную первому взвешиванию, значит фальшивая монета среди тех, которые были переложены на соседнюю чашку, т.е.
ф принадлежит {2,6,7}
Случаи 2.2 и 2.3 очень похожи.
Мысленно снимем с каждой из чашек по две хороших монетки. Имеем: на одной из чашек две "подозрительных" монетки, на другой одна "подозрительная" и одна заведомо хорошая.
Пусть для определенности
L2' = {a,b}, R2' = {c, н}. Это обобщенное взвешивание II'. Мы его не проводим, но знаем результат из взвешивания II.
III Взвешивание
L3 = {a}, R3 = {b}
Возможны три случая:
а) Весы в равновесии ==> фальшивая монетка c
б) Весы отклонились в ту же сторону, что и при взвешивании II' ==> фальшивая монетка а
в) Весы отклонились в противоположную сторону по сравнению с взвешиванием II' ==> фальшивая монетка b
гы :) так их обычно программерам задают )))Цитата:
Сообщение от Smic
С одной чашки это можно сделать, т.к. сниамются две заведомо хорошие монетки, положенные вместо монеток 1 и 5. Но как Вы найдете две хорошие монеты из четырех, лежащих в чаше весов, в которую Вы не добавляли заведомо хорошие монеты? Не катит это решение....Цитата:
Случаи 2.2 и 2.3 очень похожи.
Мысленно снимем с каждой из чашек по две хороших монетки
Smic, ты что думаешь это мое решение? у меня от такого мозги заклить может :):):)
sema, теория задачи о двоичном поиске - вещь простая и обойти ее "практически невозможно".....
Smic, Вообще вариантов/попыток решения масса, но ты не одинок в своем мнении, что задача решения не имеет :)
sema, я рад за тех, кто со мной согласен в данном вопросе....
Smic, ну так нарисовал бы доказуху, что за 3 взвешивания задачка решения не имеет :)
Так вот она:Цитата:
Сообщение от sema
Цитата:
Решения при такой постановке нет. Для гарантированного нахождения требуется Log(10) по степени 2, т.е. более трех взвешиваний.
Просто каждый акт двоичного поиска (взвешивание) сужает область поиска в два раза. Исходя из этого, надо посчитать, за сколько попыток двоичного поиска (взвешиваний) множество из N элеменотов сужается до величины, меньшей 1. И число таких попыток равно Log(N) по степени 2, округленному до ближайшего целого сверху. К случае с 10-ю монетками это число равно 4.Цитата:
И называется она "двоичный поиск". И из теории решения этой задачи известно, что минимальное число попыток, необходимое для гарантированного нахождения с помощью двоичного поиска нужного элемента из множества N элементов требуется Log(N) по степени 2 попыток.
Для 10 монет. Мож раскритикуете, но я пока не вижу засады в сем решении.
Обозначения - см. пост 65
10 монет {0;1;2;3;4;5;6;7;8;9;}
L1={0;1;2} R1={3;4;5}
Варианты:
I) равновесие, Н={0;1;2;3;4;5}, ф={6;7;8;9}
L2={6;7} R2={1;2}
варианты:
1) равновесие, ф={8;9}
L3={8} R3={1}, если равны, ф={9}, нет, ф={8}
2) перевешивает одна чаша, ф={6;7}
L3={6} R3={1}, если равны, ф={7}, нет, ф={6}
II) Перевешивает 1 чаша, ф={0;1;2;3;4;5}, Н={6;7;8;9}
L2={0;3} R2={1;4}
варианты:
1) равновесие, ф={2;5}
L3={2} R3={1}, если равны, ф={5}, нет, ф={2}
2) одна чаша перевешивает, та же, что и при 1 взвешивании, ф={0;4}, L3={0} R3={9}, если равны, ф={4}, нет, ф={0}
3) одна чаша перевешивает, другая, чем при 1 взвешивании, ф={1;3}, L3={1} R3={9}, если равны, ф={3}, нет, ф={1}
Smic, Ваше слово!
Фигня в том, что в задании нет указания на то, что ф.м. тяжелее...Цитата:
Меламори
Цитата:
1 из них или легче, или тяжелее
прально мало кто учитывает, что она может быть тяжелее или легче :)
Ошибка здесь. После второго взвешивания:Если Вы при после первого взвешивания при неуравновешенных чашах убираете по одной монете с каждой чашки и производите второе взвешивание, то у Вас может быть две возможных ситуации:Цитата:
2) одна чаша перевешивает, та же, что и при 1 взвешивании, ф={0;4}
1. положение чаш не изменилось, значит у вас на чашах весов 4 монеты, одна из которых фальшивая, для того что бы определить какая, нужно еще 2 взвешивания, итого 4.
2. чаши уравновесились, значит у Вас на руках две убранные монеты, одн из которых фальшивая. Необходимо еще одно взвешивание, чтобы определить какая.
Т.е. Вам нужно все равно не менее 4-х взвешиваний.
Если положение чаш не изменилось, то значит, что мы и убрали не фальшивку (2 и 5), и переложили не фальшивку (1 и 3), остаются - 0 и 4.
Если изменилось на противоположное, значит переложили фальшивку. А перекладывали - 1 и 3.
Если стало равновесие, то убрали фальшивку (2 и 5)
Следите за номерами монет.
Это ни к чему не приведет. Математику не обманешь.Цитата:
Сообщение от Меламори
