Задачи районной олимпиады по программированию. Разбор задачи 1.

Задача 1.

Дано целое число, записанное в десятичной системе счисления. Посчитать количество единиц в его двоичной записи.

Как перевести число из системы в систему?

Вот число 7 (в десятичной записи). В двоичной системе это 111. Почему?

Десятичная	Двоичная
0	0
1	01
2	10
3	11
4	100
5	101
6	110
7	111

 

Ну не вручную же писать все эти цифры, правильно? Заводим массив mas [k], и считаем, что начальное число у нас – это переменная a. Заводим техническую переменную b.

И используем новый для нас вид цикла – repeat. Это цикл с постусловием. Мы не знаем, сколько раз будет повторяться действие.

k:=0;        - счетчик элементов массива.

repeat       - повторять (массив выполнится минимум 1 раз)

b:=a mod 2;  - технической переменной присваиваем остаток от деления нашего числа на 2. Это может быть только 0 или 1.

k:=k+1;      - меняем счетчик на 1

mas[k]:=b;   - записываем в очередной элемент массива остаток от деления

c:=a div 2;  - переменной с присваиваем значение целой части деления нашего числа на 2.

if c>=2 then a:=c; - пока c>=2 меняем начальное число на с

until c<2; - если с оказалось меньше 2- число полностью переведено в двоичную систему, но последний из остатков – последнее значение с – мы пока не записали.

mas[k+1]:=c; - и мы записываем последнее число в последний элемент массива. k+1 – потому, что k мы меняли внутри цикла, а из цикла мы уже вышли.

Рассмотрим на примере конкретного числа 7.

a=7, b= остатку от деления 7 на 2, т.е. 1, k=0+1=1, mas[1]=b=1, c=целой части от деления 7 на 2, т.е. 3, c=3>=2 , a:=3, условие конца цикла не достигнуто, начинаем цикл сначала.

a=3, b= 3 mod 2 = 1, k=1+1=2, mas [2]= b=1, c=a div 2=3 div 2=1, 1<2 – мы вылетаем из цикла.

mas [2+1]=mas [3] = c = 1

Мы получили три элемента массива, каждый из которых равен 1.

Теперь их надо просто сложить и вывести в файл сумму. Причем заметьте, что кроме 1 у нас могут быть в массиве только 0, т.е. сумма всех элементов и будет нам давать искомое количество 1.

А вот если бы нам надо было вывести число в двоичной записи – мы бы столкнулись с такой проблемой: в наш массив мы записываем цифры двоичной записи не от начала, а с конца числа. Потому, что берем ОСТАТОК от деления. Это значит, что для того, чтоб вывести правильное число, мы должны запустить такой простой цикл:

For i:= k+1 downto 1 do

Write(mas[i]);

При такой записи выводится будут элементы массива от последнего по счету к первому.

Самостоятельно:

• Написать работающую программу к олимпиадной задаче.
• Изменить ее так, чтоб она выводила не только количество 1, но и само число.
• Решить задачи:

a.       Вводится число в двоичной записи. Вывести его в десятичной записи.

b.      Выведите все десятичные числа не превышающие 25 в порядке возрастания, двоичная запись которых оканчивается на 11.