За два взвешивания определить которая из пяти монет имеет вес, отличный от остальных

Понимаю, что оффтоп, но задача для острого программерского ума.
Олимпиадная задача для 7 класса, условие:

Есть 5 монет. 4 из них по 5 грамм, пятая - неизвестно (либо больше, либо меньше пяти - это неизвестно).
Есть грузик на 5 грамм. За 2 взвешивания определить, где монета, которая НЕ 5 грамм.

1

Сообщение от alexu_007 Я читал тему.

Вы прочли стартовый пост. Посмотрите посты #14, #20, #21

Вообще какое-то "упоение" от решения что указано 12 лет назад. Как насчет общности? Как вообще решаются такие задачки (метод)? Стоит немного изменить условие, один вариант уже предлагал выше, ну ладно, еще хотя бы

Все как в стартовом посте, только число фальшивых - любое

Или просто

Все как в стартовом посте, только др число монет (напр 6, 7, 8..)

Конечно искать надо мин число взвешиваний

И что, опять начинать с нуля? Или мы уже знаем как решать?

0

при чем тут вообще программирование? почему админы не перенесут тему куда подальше?

0

Сообщение от vlisp при чем тут вообще программирование?

Ни при чем. Это задача на логическое мышление, которое программисту необходимо, особенно на стадии выбора алгоритмов решения проблемы.

0

Сообщение от VAF34 Это задача на логическое мышление, которое программисту необходимо, особенно на стадии выбора алгоритмов решения проблемы.

"Необходимость" весьма спорна. Лично я не припомню ни одного случая когда по работе требовалось хоть что-то подобное. Конечно иметь/показать силу своего логического мЫшления каждому приятно - это нормально

0

Сообщение от vlisp при чем тут вообще программирование?

если решать только конкретное задание ТС, то программирование здесь ни при чем

но, видишь ли, Igor3D предлагает написать код, который будет находить решение для произвольного количества монет, типа пользователь вводит количество монет по 5 г, и количество монет не по 5 г, а программа показывает пошагово, как оптимально решать. Можно даже усложнить, сделав так, что нужно ввести вес каждой монеты.

0

Сообщение от Royal_X который будет находить решение

Это задача на распознавание, решается цепочкой условных операторов или построением нейронной сети и ее обучения. Первый способ предпочтительнее, так как ответ не будет иметь случайной составляющей. Но в первом случае сразу не очевидно как построить алгоритм для получения минимального количества взвешиваний.

0

Мне кажется, что обобщённое решение для одной дефектной монеты и грузика будет строится не по принципу деления на 2 части, а по принципу деления на 3 части.

Имеем некоторое количество монет N.
Разделим их на 3 примерно равные группы по M, M и K монет в каждой (M+M+K=N).
За 2 взвешивания определяем группу с дефектной монетой:
1. Взвешиваем первые две группы M и M - при равенстве весов принимаем, что дефектная монета в третьей группе
2. Если M и M не равны по весу, то в третьей группе все монеты хорошие и можем сравнить вес третьей группы с первой группой, уравняв количество монет переносом 1-2 монет из первой группы во вторую. Взвешивание позволит оставить первую или вторую (увеличенную) группу на дальнейшее рассмотрение.

И так повторять, пока не останется 2-3 монеты. Одна отсеется взвешиванием и останется 2 монеты.

В конце останется 2 монеты - сравнить любую из них с грузиком или с одной из признанной эталонной.

В программе помимо массива весов будет и массив признаков качества монеты.

Это обобщённая идея. Возможно, немного потребующая доработки при реализации.

0

Что-то мы заговорились! Общая постановка: любое количество монет двух типов является классической задачей кластеризации. Решать ее при помощи программы можно многими способами, а вот найти простейший способ - это высший пилотаж.

0

Сообщение от Royal_X предлагает написать код

Для начала определитесь с компилятором/иде, потом напишете окно, из которого алгоритм будет получать входные данные

0

VAF34, если будет всего одна фальшивая монета, то любая программа без проблем справится даже с большим количеством монет.
Но вот если поменять задачу и допустить, что фальшивых монет может быть и больше 1, то при большом количестве монет обычные алгоритмы не справятся, поскольку вычислительная скорость очень быстро возрастет.
Тут только остаётся два варианта: нейросеть, которая попытается создать эффективную эвристическую стратегию, или квантовый компьютер.

0

Сообщение от Royal_X при большом количестве монет обычные алгоритмы не справятся

Алгоритмы, это такие звери, которые просто описывают, что и в каком порядке надо делать. Если на этапе написания алгоритма непреодалимые трудности, то надо менять того, кто его пишет. Пришлите задачу с монетами для решения которой, по вашему, непреодалимые проблемы.

0

Сообщение от VAF34 Пришлите задачу с монетами для решения которой, по вашему, непреодалимые проблемы.

ты посты из этой темы не читаешь и тебе нужно отправить отдельное приглашение по почте? Ну хорошо, могу повторить еще раз:
"если поменять задачу и допустить, что фальшивых монет может быть и больше 1, то при большом количестве монет обычные алгоритмы не справятся, поскольку вычислительная скорость очень быстро возрастет".
Напоминаю, что задача состоит в том, чтобы найти самое оптимальное решение. Написать говнокод (особенно в эпоху ИИ), который найдет не самый оптимальный порядок взвешиваний может любой школоло. Но нужно, чтобы программа нашла решение задачи с минимальным количеством взвешиваний. И проблема даже не в написании кода, а в том, что программа будет очень долго думать при большом количестве монет, поскольку вычислительная скорость будет быстро расти.

Сообщение от VAF34 Если на этапе написания алгоритма непреодалимые трудности, то надо менять того, кто его пишет.

быть самоуверенным это хорошо, но не помешало бы тебе немного прочесть об алгоритмах, об алгоритмически неразрешимых задачах или о разрешимых, но NP-трудных задачах. Я к тому, что не всегда программист виноват. Есть задачи, которые просто сложно поддаются обычным алгоритмам.

0

При любом количестве монет различных весов любой из нас легко справляется. Алгоритм таков: на весы две первых монеты, если равны, то первый вес найден. Откладываем одну из них в первую коробку и сравниваем все оставшиеся с одной из первых, пополняя коробку. Идея понятна. Если первое взвешивание дает неуравновешенное состояние, то перебираем все оставшиеся с первой, отбирая совпадения. Описанное есть черновик алгоритма и никакого отношения к количеству монет ни к быстродействию алгоритм не имеет. Он сам по себе, конечный продукт творчества.

0

Сообщение от VAF34 Алгоритм таков: на весы две первых монеты, если равны, то первый вес найден. Откладываем одну из них в первую коробку и сравниваем все оставшиеся с одной из первых, пополняя коробку.

твой алгоритм не является самым оптимальным

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

грубо говоря, ты описываешь решение совсем другой задачи - задачи, в которой просто нужно отсортировать монеты посредством взвешиваний и никаких условий к количеству взвешиваний не ставится. Для этой задачи, действительно, можно написать код, который легко справится даже с большим количеством монет.

Но я тут писал про совсем другую задачу, в разы сложную, которую нужно решить за минимальное количество взвешиваний.

0

Сообщение от ФедосеевПавел Мне кажется, что обобщённое решение для одной дефектной монеты и грузика будет строится не по принципу деления на 2 части, а по принципу деления на 3 части.

А я думаю на 4 части (кто больше ). Хотя можно и больше частей, производительность если и упадет, то не сильно

Разбиваем на 4 равные части M1, M2, M3, M4 (число монет в частях должно отличаться макс на 1)
Взвешиваем любые 2, напр M1, M2 (если надо юзаем грузик)
Если равны - отбрасываем взвешенные части, иначе оставшиеся
В итоге на каждой итерации число монет вдвое меньше (желанный O(log(N))

Последние итерации (5 и меньше монет) лучше захардкодить.
Если же известно что фальшивая точно легче (или точно тяжелее), то все проще, банальное разбиение пополам.

И все это, увы, "для одной дефектной монеты" (и только одной). Впрочем, и так можно тупо каждую взвесить с грузом, это O(n), бороться за оптимизацию здесь не актуально

0

Igor3D, представь такую задачу: на вход программе задается одно число - размер куба, а дальше задаются разрешимые радиусы сфер и количество доступных сфер для каждого радиуса. Подразумевается, что куб находится в точке (0, 0, 0). Нужно куб максимально заполнить сферами (т.е. важно не максимально возможное количество заполненных сфер, а максимально возможный суммарный объем сфер).
Программа должна вывести для каждой сферы радиус и координату центра. Или чтобы не повторять радиусы, то для каждого использованного радиуса вывести список координат центров сфер.

Вот эта задача интересна и имеет прикладное значение. Но вот если поменять условие на "заполняйте куб сферами как хотите", то согласись, что задача превратится в ахинею. То же самое с этой задачей про монеты. Если убрать условие про поиск оптимального решения, то задача решается тривиально и, собственного говоря, тут многие даже описали решение.

0

Сообщение от VAF34 найти простейший способ - это высший пилотаж. _

Именно так я писал много раньше.

0