Взвешивание на равноплечих весах

[basshead]

Помогите плз. Кто знает какой алгоритм или как реализовать?:

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

[Tonny_Bennet]

Необходимо определить наименьший набор гирь »

А вы думали как бы вы решали такую задачу если бы у вас просто весы стояли перед вами?

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

Пусть вес измеряемого предмета задаётся случайным числом, генерируемым программой. И пусть для упрощения изложения он будет целым. И также пусть мы не знаем даже примерно чему примерно равен измеряемый вес.

Тогда это будет похоже на задачу стрельбы из пушки (ну или как то так она называлась). Где нужно было подбором силы выстрела и угла наклона попасть в цель.

Вы кладёте на чашу весов самую большую гирю и проверяете три отношения: равен ли вес гири и измеряемого предмета, больше ли он или меньше. Исходя из полученных результатов вы начинаете добавлять или убирать гири. Если обнаружите некоторую вилку в пределах которой будет находится вес измеряемого тела, то оставляйте больший из 2-х набор гирь и начинайте класть гири на чашу с измеряемым телом.

[XPEHOMETP]

Что-то задача мутная. Скажем, дано: есть изделие весом в 19 грамм. Я отвечаю: наименьшим набором гирь для ее взвешивания является одна-единственная гиря весом в 19 грамм. А Вы бы как ответили?

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

[Beyound]

насколько мне известно гири бывают только весом ряда 1,2,5,10. по этому скажем 19г можно взвесить 2-мя гирями: 19+1г и 20г на чашах соответственно. а с алгоритмом все просто, самое простое - тупо перебор, если хватает мозгов - оптимизируй его выкидывая лишнее. можно попробовать поискать условия, когда ставить гирьки на 2 чаши весов заведомо лучше чем только на одну чашу

[Tonny_Bennet]

насколько мне известно гири бывают только весом ряда 1,2,5,10 »
Но тут снова не указывается количество гирь. Может там три гири по 5 г. и дву гири по 1 г. Интереснее конечно поставить задачу с ограниченным, но достаточным для взвешивания, набором гирь. Думаю что нужно более точно формулировать условие.

[XPEHOMETP]

насколько мне известно гири бывают только весом ряда 1,2,5,10. »
Безусловно. Есть некий устоявшийся набор не только гирь, но и монеток, жестко привязанный к десятичной системе. А вот в Англии система монеток совсем другая была, не десятичная. В идеале, задача имеет все шансы плавно перейти в вопрос о выборе некой наиболее удобной системы построения такой шкалы взвешивания, и я не сомневаюсь, что наиболее удобная шкала десятичной не будет. Троичная хорошо пойдет, наверняка, особенно при раскладе разновесов на обе чашки. Из условия единственным критерием "удобства" является наименьшее число гирь. Что-то мне говорит, что если прошерстить, скажем, двоичные, троичные, четверичные и прочие системы разновесов, и найти наиболее экономный по числу гирь, то задача будет решена. Лично я (без детальной проверки, по ощущениям) за троичную систему.