Взвешивание любого груза на весах

[canadamoscow]

Используя равноплечные рычажные весы, нужно взвесить любой груз с точностью до 1гр., при этом используя набор с минимально возможным количеством гирь. Гири можно класть на любую чашу весов.
Например, для взвешивания груза до 4гр. понадобится набор всего из 2 гирь номиналом 1гр. и 3гр.:
(груз 1гр) = (1гр), уравновесили две чаши весов
(груз 2гр) + (1гр) = (3гр), т.е. двумя гирями номиралом 1гр. и 3гр. взвесили груз весом в 2гр.
(груз 3гр) = (3гр)
(груз 4гр) = (3гр) + (1гр)
Можно записать всё проще: слева вес груза, справа используемые гири, при этом плюс перед числом означает, что гирю с данным номиналом кладем на правую чашу весов, минус - на левую чашу)
1 = + 1
2 = + 3 - 1
3 = + 3
4 = + 3 + 1
Утверждается, что для взвешивания груза весом до 40гр. достаточно иметь набор из 4 гирь,
номиналом 1гр., 3гр., 9гр. и 27гр.
40 = + 27 + 9 + 3 + 1
35 = + 27 + 9 - 1
26 = + 27 - 1
14 = + 27 - 9 - 3 - 1
Следуя той же логике минимального набора имеющихся гирь (как вы уже поняли, это набор гирь, где каждоая следующая гиря в три раза тяжелее предыдущей), показать взвешивание груза весом 9200гр.

[ViktorR]

при этом используя набор с минимально возможным количеством гирь

Осталось понять, что это за набор?
Иначе возникает вопрос: "Нафига использовать две гири в 1 и 3 грамма для взвешивания груза весом в 4 грамма, если можно использовать одну гирю весом в 4 грамма?"

[BDA]

Сообщение от ViktorR

Осталось понять, что это за набор?

Да, вроде, наоборот, достаточно четко описано, как получается набор гирь:

Сообщение от canadamoscow

это набор гирь, где каждая следующая гиря в три раза тяжелее предыдущей

Т.е. каждая гиря имеет вес 3^k, а k от 0 до N, где N выбрано так, что из гирь можно составить заданный вес.

[evg_m]

1. любое число можно записать троичной системе счисления
2. начиная с младших разрядов (действия с гирей весом соотв. разряда)

• 0 -- пропускаем вес
• 1 -- кладем на весы
• 2 -- кладем на весы к грузу прибавляем 1 в соотв. разряде к нашему числу.

40 =1111 + 0000
35 =1022 + 0000 =1100 + 0001
26 =0222 + 0000 =1000 + 0001
14 =0112 + 0000 =0120 + 0001 =0200 +0011 =1000 +0111
4 =0011 + 0000
2 =0002 + 0000 =0010 + 0001

[canadamoscow]

Код по алгоритму evg_m на PascalABC

function ToBase3(b: Integer): string;
begin
  while b > 0 do begin
     Result :=''+ b mod 3 + Result;
     b := b div 3
  end;
  Result :='0'+ Result;
end;

begin
  var x := 14;
  var right := ToBase3(x);  // 14 → '0112' 
{}Print(x,'=',right,'=');  
  var n := Length(right); // 4
  var left :='0' * n; // '0000'
  var j := n; // 4
  while j > 0 do 
    if right[j] <>'2' then 
      j -= 1
    else begin 
        left[j] :='1'; // left = 0000 → 0001 → 0011 → 0111 
        while right[j] ='2' do begin right[j] :='0'; j -= 1 end;
        right[j] :=  if right[j] ='0' then '1' else '2'; // right = 0112 → 0120 → 0200 → 1000; 
    end;
{}Println(right,'-',left); // '1000 - 0111'
  Print(x,'= ');
  for var i := 1 to n do
    if right[i] ='1' then Print('+', 3**(n-i)) // + 27
    else if left[i] ='1' then Print('-', 3**(n-i)) // - 9 - 3 - 1
end.

[canadamoscow]

Номиналы гирь в наборе кратны трем: ВесГири = [1,3,9,27,81,...], накопительная сумма этого ряда
СуммарныйВесГирь = [0,1,4,13,40,121,364,1093,3280,9841, ...], в котором индекс равен кол-ву гирь, т.е.
СуммарныйВес[i] := СуммарныйВес[i-1] + ВесГири[i-1],
например при i=3 (СуммарныйВес[3]=13) используется 3 гири, суммарным весом 1+3+9=13гр.
соответственно 9 гирями можно взвесить любой вес до 9841гр.
Решение на PascalABC.net

##
var x := ReadlnInteger('Вес груза:'); //вес на левой чаше весов (взвешиваемый груз)
var СуммарныйВесГирь := SeqWhile(0, t-> (3*t)+1, t-> t < x).ToArray; //0,1,4,13,40... индекс=кол-во гирь
var n := СуммарныйВесГирь.Count; //количество гирь в наборе
var ВесГири := ArrGen(n, 1, t-> t*3);//1 3 9 27... - номиналы гирь в наборе 
'Набор гирь:'.Print; ВесГири.Println(', ');
Print(x,'=');
var sum := 0; //вес на правой чаше весов 
for var i := n-1 downto 0 do //пробегаем по набору гирь от большей и прибалвяем/убавляем/пропускаем
   if sum + СуммарныйВесГирь[i] < x then begin Print('+',ВесГири[i]); sum += ВесГири[i] end else
   if sum - СуммарныйВесГирь[i] > x then begin Print('-',ВесГири[i]); sum -= ВесГири[i] end