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

Posted by obzor under Pascal

Используя равноплечные рычажные весы, нужно взвесить любой груз с точностью до 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гр.

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 ='1' then Print('+', 3**(n-i)) // + 27
    else if left ='1' then Print('-', 3**(n-i)) // - 9 - 3 - 1
end.

Номиналы гирь в наборе кратны трем: ВесГири = [1,3,9,27,81,…], накопительная сумма этого ряда
СуммарныйВесГирь = [0,1,4,13,40,121,364,1093,3280,9841, …], в котором индекс равен кол-ву гирь, т.е.
СуммарныйВес := СуммарныйВес[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 + СуммарныйВесГирь < x then begin Print('+',ВесГири); sum += ВесГири end else
   if sum - СуммарныйВесГирь > x then begin Print('-',ВесГири); sum -= ВесГири end

тема на форуме

Похожие статьи

• PascalABC.net — Заполнить массив случайными числами и найти сумму элементов