Задача 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.
