Вывести количество единиц в двоичном представлении результата выражения 2n – 2k - Pascal ABC
Формулировка задачи:
Задача 2. "Двоичная арифметика" (25 баллов)
Имя входного файла: b.in
Имя выходного файла: b.out
Ограничение времени 2 секунды на тест
Ограничение по памяти 256 Мб
На уроках информатики Изольда Леопольдовна рассказала детям о системах счисления. Например, мальчики и девочки из ее класса теперь прекрасно понимают, что 100112 - это всего лишь сумма 1*20+1*21+1*24. Изольда Леопольдовна рассказала также детям, как можно складывать и вычитать числа столбиком, если они записаны в двоичной системе счисления.
В классе Изольды Леопольдовны учится любознательный Гоша. Так ему понравилась тема про системы счисления, что он решил написать программу для компьютера про вычитание двоичных чисел. Причем речь идет о вычитании чисел, являющихся целыми степенями двойки…
Формат входных данных:
Входной текстовый файл b.in содержит в единственной строке выражение вида 2^n-2^k без пробелов. Известно, что k ≤ n. Известно, что n≤250. n и k – натуральные числа
Формат выходных данных:
В выходной файл b.out вывести единственное целое число — количество единиц в двоичном представлении результата выражения 2n – 2k.
Пример файла с входными данными и файла с результатом:
b.in b.out
2^5-2^3 2
Комментарий к примеру:
25 – 23 = 3210 – 810 = 2410=110002.
Решение задачи: «Вывести количество единиц в двоичном представлении результата выражения 2n – 2k»
textual
Листинг программы
var f:text; s,s1,s2,s3:string; n,k,i,j,ln,k1:integer; begin assign(f,'b.in'); reset(f); readln(f,s); close(f); //находим n delete(s,1,2); n:=strtoint(copy(s,1,pos('-',s)-1)); //находим k delete(s,1,pos('^',s)); k:=strtoint(s); //получаем число 2^n в СС 2, это 1 и n нолей s1:='1'; for i:=1 to n do s1:=s1+'0'; ln:=length(s1);//длина числа //получаем число 2^k в СС 2, это 1 и k нолей s2:='1'; for i:=1 to k do s2:=s2+'0'; while length(s2)<ln do //выравниваем s2:='0'+s2; s3:=''; //вычитаем и получаем результат s3 for i:=ln downto 1 do begin if s1[i]='1' then begin if s2[i]='0' then s3:='1'+s3 else s3:='0'+s3; end else begin if s2[i]='0' then s3:='0'+s3 else begin s3:='1'+s3; if (s1[i-1]='1') then s1[i-1]:='0' else begin j:=1; while (i-j>0) and (s1[i-j]='0') do begin s1[i-j]:='1'; inc(j); end; s1[i-j]:='0'; end; end; end; end; //посчитаем 1 k1:=0; for i:=1 to ln do if s3[i]='1' then inc(k1); assign(f,'b.out'); rewrite(f); writeln(f,k1); close(f); end.
Объяснение кода листинга программы
- Создаются переменные f, s, s1, s2, s3, n, k, i, j, ln, k1, которые будут использоваться в программе.
- Задается код для вывода количества единиц в двоичном представлении результата выражения 2n – 2k.
- Выполняется чтение строки s из файла 'b.in'.
- Строка s преобразуется в целое число n.
- Строка s преобразуется в целое число k.
- Создается строка s1, которая будет содержать число 2^n в СС 2, это 1 и n нолей.
- Длина строки s1 запоминается в переменной ln.
- Создается строка s2, которая будет содержать число 2^k в СС 2, это 1 и k нолей.
- Строка s2 преобразуется в целое число k.
- Строка s2 преобразуется в целое число i.
- Строка s2 преобразуется в целое число j.
- Строка s2 преобразуется в целое число ln.
- Строка s2 преобразуется в целое число k1.
- Строка s3 создается для хранения результата выражения 2n – 2k.
- Строка s3 инициализируется нулями.
- Строка s3 изменяется путем добавления единиц в те позиции, где в исходной строке s1 были единицы.
- Строка s3 сравнивается с исходной строкой s1.
- Если строка s3 содержит больше единиц, чем s1, то переменная k1 увеличивается на единицу.
- Код записывается в файл 'b.out'.
- Код считывается из файла 'b.in'.