function cp12(S:longint) : longint;
begin
S := S-1;
S := S OR (S shr 1);
S := S OR (S shr 2);
S := S OR (S shr 4);
S := S OR (S shr 8);
S := S OR (S shr 16);
cp12 := S+1;
end;
var
n,t : longint;
begin
ReadLn(n);
while n <> 0 do
begin
t := cp12(abs(n));
if abs(abs(n)-t) > abs(abs(n)-t div 2) then
t := t div 2;
if n > 0 then
begin
WriteLn(n,'-',t,'=',n-t);
n:=n-t;
end
else
begin
WriteLn(n,'+',t,'=',n+t);
n:=n+t;
end;
end;
ReadLn(n);
end.
Задача
Добрый день всем
У меня возник вопрос во время решения задачи. Суть задачи такая : Есть число n. Нужно свести его до 0, используя (добавляя или отнимая) только числа степеней двойки (1,2,4,8,16 .....) за наименьшее количество шагов, исходными данными должно быть одно чило - найменьше количество добавления или отниманий чисел. Например, для 14, за 2 шага можно добиться 0 (14 +2 -16).
Как я понял, решать задачу можна через рекурсию. Я сделал функцию, которая определяет, есть ли данное число степенем двойки. вот код :
function stepen(h: integer) : boolean;
var i,b : integer;
begin
stepen := false;
b := 1;
for i := 1 to 10 do begin
if (h = a) and (b=1) then
begin
stepen := true;
b := 0;
end
end;
end;
тут масив А єто - все степени двойки от 1 до 1024.
Потом, как я понял, надо проверить, что меньше к числу n, n+какое-то число =степени 2 или n - какое-то число=степень 2
Тоисть например, (для n = 14) 14 + x1 = 16 или 14 - x2 = 8
поетому |х1| = 2, а |х2| = 6, поетому мы выбрали 16, тоисть уже одни крок есть, тепер stepen(16) = true тому ещё один крок, поетому и 2 кроки.
Вот мне надо как-то всё это слить в код.
Помогите решить задачу, пожалуйста, готоюся к областной олимпиаде, очень благодарю.
У меня возник вопрос во время решения задачи. Суть задачи такая : Есть число n. Нужно свести его до 0, используя (добавляя или отнимая) только числа степеней двойки (1,2,4,8,16 .....) за наименьшее количество шагов, исходными данными должно быть одно чило - найменьше количество добавления или отниманий чисел. Например, для 14, за 2 шага можно добиться 0 (14 +2 -16).
Как я понял, решать задачу можна через рекурсию. Я сделал функцию, которая определяет, есть ли данное число степенем двойки. вот код :
function stepen(h: integer) : boolean;
var i,b : integer;
begin
stepen := false;
b := 1;
for i := 1 to 10 do begin
if (h = a) and (b=1) then
begin
stepen := true;
b := 0;
end
end;
end;
тут масив А єто - все степени двойки от 1 до 1024.
Потом, как я понял, надо проверить, что меньше к числу n, n+какое-то число =степени 2 или n - какое-то число=степень 2
Тоисть например, (для n = 14) 14 + x1 = 16 или 14 - x2 = 8
поетому |х1| = 2, а |х2| = 6, поетому мы выбрали 16, тоисть уже одни крок есть, тепер stepen(16) = true тому ещё один крок, поетому и 2 кроки.
Вот мне надо как-то всё это слить в код.
Помогите решить задачу, пожалуйста, готоюся к областной олимпиаде, очень благодарю.