Есть чашечные весы без дроблений. Для взвешивания багажа также можно использовать
Есть чашечные весы без разделений. Для взвешивания багажа также можно использовать гирьки, массы которых целое число граммов. Вам необходимо предложить набор гирек, при подмоги которого можно отмерить на весах любую массу, одинаковую целому числу граммов от 1 до 40. Гири можно класть на каждую чашку весов, чашечки весов должны находиться в равновесии, при этом на одной из чашек весов обязан находиться обдумываемый груз. Массы гирек в комплекте могут повторяться. К примеру, при подмоги трёх гирек массами 1, 1 и 5 граммов можно отмерить всякую целочисленную массу от 1 до 7 граммов по последующей схеме (x обдумываемая масса): 1 гр: x = 1, 2 грамма: x = 1 + 1, 3 грамма: x + 1 + 1 = 5, 4 грамма: x + 1 = 5, 5 граммов: x = 5, 6 граммов: x = 5 + 1, 7 граммов: x = 5 + 1 + 1. Ответом на эту задачку являются несколько целых чисел, записанных через пробел, массы гирек, при поддержки которых можно отмерить всякую целочисленную массу от 1 до 40. В комплекте обязано быть не более 8 чисел. Числа в комплекте могут повторяться. Чем меньше гирек будет в предложенном комплекте, тем больше баллов вы получите, при условии, что, используя гири из данного набора, можно отмерить каждую целочисленную массу от 1 до 40.
Задать свой вопрос
Тогда имеет место равенство X = a1 * M1 + a2 * M2 + ... + an * Mn,
где ai = 0, если i-ая гирьке не участвовала в взвешиваниях, -1, если лежала на той же чаше весов, что и масса, которкю нужно отмерить, и +1, если на иной чаше весов.
Каждый из коэффициентов принимает одно из трёх значений, тогда при поддержки n гирек можно отмерить не более, чем 3^n разных масс. 3^3 lt; 40 + 1 lt; 3^4, означает, гирек нужно не наименее четырёх.
Докажем, что взяв гири с массами 1, 3, 9 и 27, можно отмерить всякую массу от 1 до 40. Будем это делать по индукции, доказав, что при подмоги гирек 1, 3, 9, ..., 3^k можно отмерить любую массу от 1 до (3^k - 1)/2.
База индукции. При поддержки одной гири массой 1 вправду можно отмерить массу 1.
Переход. Пусть для k = k' всё подтверждено. Докажем и для k = k' + 1.
- Если необходимо отмерить массу X lt;= (3^k' - 1)/2, то это можно сделать при подмоги k' гирек.
- Пусть надобно отмерить массу (3^k' - 1)/2 lt; X lt;= (3^(k' + 1) - 1)/2. Кладём на иную чашу весов гирьку массой 3^k'. Тогда остаётся нескомпенсированная масса X - 3^k' lt;= (3^k' - 1)/2, которую, по предположению, можно получить. Ура!
Ответ. 1, 3, 9, 27.
-
Вопросы ответы
Статьи
Информатика
Статьи
Химия.
Русский язык.
Геометрия.
Физика.
Русский язык.
Химия.
Математика.
География.
Литература.
Разные вопросы.