Системы счисления

Упражнения

Во всех задачах этого листка ввод-вывод стандартный.

В системе счисления с основанием b цифры записываются так: 0, 1, 2, ..., 9, A, B, C, ...

В тексте программ на языке C++ можно использовать целочисленные константы, записанные в восьмеричной системе счисления. В этом случае их запись начинается с символа 0. Можно использовать константы в шестнадцатеричной системе счисления, в этом случае их запись начинается с 0x. Например:

    unsigned char MaxChar = 0xFF; // То же, что и 255
    unsigned short int MaxShort = 0xFFFF; // То же, что и 65535
    unsigned short int MaxShortAgain = 0177777; // То же самое значение

A: Шестнадцатеричная цифра - 1

Дана шестнадцатеричная цифра, записанная как char. Выведите ее десятичное значение.

Программа должна содержать функцию перевода int hex2int(char c).

Ввод Вывод
9
9
F
15

B: Шестнадцатеричная цифра - 2

Решите задачу, обратную предыдущей.

Ввод Вывод
9
9
15
F

C: Из двоичной в десятичную

Дано число, записанное в двоичной системе счисления. Переведите его в тип int и выведите на экран в десятичном виде. Исходное число необходимо считать в переменную типа string, для перевода реализовать функцию int bin2int (string).

Гарантируется, что ответ всегда вмещается в переменную типа int.

Ввод Вывод
10110011
179

D: Из шестнадцатеричной в десятичную

Решите предыдущую задачу в случае, когда входное число задано в шестнадцатеричном виде. Соответствующая функция должна называться int hex2int(string).

Ввод Вывод
B3
179

E: Из десятичной в двоичную

Переведите число из десятичной системы в двоичную. Соответствующая функция должна называться string int2bin(int).

Ввод Вывод
179
10110011

F: Из десятичной в шестнадцатеричную

Переведите число из десятичной системы в шестнадцатеричную. Соответствующая функция должна называться string int2hex(int).

Ввод Вывод
179
B3

G: Из любой в любую

Напишите программу, переводящую запись числа между двумя произвольными системами счисления.

На вход программа получает три величины: n, A, k, где n и k – натуральные числа от 2 до 36: основания системы счисления, A – число, записанное в в системе счисления с основанием n, A<231.

Необходимо вывести значение A в системе счисления с основанием k без лидирующих нулей.

Ввод Вывод
2
101111
16
2F
10
35
36
Z

Указание. Напишите две функции перевода — из числа в произвольной системе счисления, записанного в переменной типа int в переменную типа int и обратно.

H: Из шестнадцатеричной в двоичную

Переведите число из шестнадцатеричной системы счисления в двоичную. Исходное число может быть очень большим (до 1000 символов). Необходимо вывести результат без лидирующих нулей.

Ввод Вывод
2F
101111

I: Из двоичной в шестнадцатеричную

Переведите число из двоичной системы счисления в шестнадцатеричную. Исходное число может быть очень большим (до 4000 символов).

Ввод Вывод
101111
2F

J: Из уравновешенной троичной в десятичную

В уравновешенной троичной системе счисления используется основание 3 и три цифры: 0, 1 и -1. Цифру -1 будем обозначать знаком $. Достоинство уравновешенной троичной системы счисления: простота хранения отрицательных чисел и удобство нахождения числа, противоположному данному.

Вот как записываются небольшие числа в уравновешенной троичной системе счисления:

Десятичная -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9
Уравнов. троичная $00 $01 $1$ $10 $11 $$ $0 $1 $ 0 1 1$ 10 11 1$$ 1$0 1$1 10$ 100

Подробней о уравновешенной троичной системе счисления можно прочитать в Википедии (статья Троичная система счисления, там используется термин "троичная симметричная система счисления") а также в этой статье.

Дана запись числа в уравновешенной троичной системе счисления. Запишите это число в десятичной системе счисления. Гарантируется, что ответ вмещается в переменную типа int.

Ввод Вывод
$01
-8

K: Из фибоначчиевой в десятичную

Рассмотрим последовательность Фибоначчи: F1=1, F2=2, Fn=Fn-1+Fn-2 при n>2. В частности, F3=3, F4=5, F5=8, F6=13 и т.д.

Любое натуральное число можно представить в виде суммы нескольких членов последовательности Фибоначчи. Такое представление будет неоднозначным, но если наложить дополнительное условие, что в представлении нет двух соседних членов последовательности Фибоначчи, то представление становится единственным.

Будем говорить, что число A представимо в фибоначчиевой системе счисления в виде akak-1...a2, где ai∈{0;1}, если A=akFk+...+a2F2 и в записи akak-1...a2 нет двух единиц подряд.

Вот как записываются небольшие числа в фибоначчиевой системе счисления:

Десятичная 0 1 2 3 4 5 6 7 8 9 10 11 12 13
Фибоначчиева 0 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000

Подробней о фибоначчиевой системе счисления можно прочитать в Википедии (статья Фибоначчиева система счисления).

Дана запись числа в фибоначчиевой системе счисления. Запишите его в десятичной системе счисления.

Программа получает на вход строку из символов 0 и 1 и должна вывести одно целое число. Гарантируется, что результат может принимать значения от 0 до 2·109.

Ввод Вывод
10101
12

L: Из десятичной в уравновешенную троичную

Дано целое число oт -2·109 до 2·109. Выведите его представление в уравновешенной троичной системе счисления без лидирующих нулей.

Ввод Вывод
-8
$01

M: Из десятичной в фибоначчиеву

Дано целое число oт 0 до 2·109. Выведите его представление в фибоначчиевой системе счисления без лидирующих нулей.

Ввод Вывод
12
10101

N: Инкремент

Первая строка входных данных содержит последовательность символов '0', ..., '9', 'A', ..., 'Z', являющейся записью некоторого неотрицательного числа в системе счисления с основанием base. Длина числа не превосходит 1000 символов. Вторая строка входных данных содержит основание системы счисления base, не превосходящее 36.

Увеличьте это число на 1 и выведите результат в той же системе счисления.

Ввод Вывод
19A
11
1A0

O: Декремент

Первая строка входных данных содержит последовательность символов '0', ..., '9', 'A', ..., 'Z', являющейся записью некоторого положительного числа в системе счисления с основанием base. Длина числа не превосходит 1000 символов. Вторая строка входных данных содержит основание системы счисления base, не превосходящее 36.

Уменьшите это число на 1 и выведите результат в той же системе счисления.

Ввод Вывод
1A0
11
19A

P: Инкремент в уравновешенной троичной системе счисления

Дана запись некоторого числа в уравновешенной троичной системе счисления, длина записи не превосходит 1000 символов.

Увеличьте это число на 1 и выведите его значение в той же системе.

Ввод Вывод
$01
$1$

Q: Декремент в уравновешенной троичной системе счисления

Уменьшите на 1 длинное число, записанное в уравновешенной троичной системе счисления.

Ввод Вывод
$1$
$01

R: Фибоначчиев инкремент

Дано целое неотрицательное число n, записанное в фибоначчиевой системе счисления, длина числа не превосходят 1000 символов. Выведите значение числа n+1 в фибоначчиевой системе счисления.

Ввод Вывод
100101
101000

S: Фибоначчиев декремент

Дано целое положительное число n, записанное в фибоначчиевой системе счисления, длина числа не превосходят 1000 символов. Выведите значение числа n-1 в фибоначчиевой системе счисления.

Ввод Вывод
101000
100101

Бонусные задачки

ZA: Марсианские факториалы

В 3141 году очередная экспедиция на Марс обнаружила в одной из пещер таинственные знаки. Они однозначно доказывали существование на Марсе разумных существ. Однако смысл этих таинственных знаков долгое время оставался неизвестным. Недавно один из ученых, профессор Очень-Умный, заметил один интересный факт: всего в надписях, составленных из этих знаков, встречается ровно \(K\) различных символов. Более того, все надписи заканчиваются на длинную последовательность одних и тех же символов.

Вывод, который сделал из своих наблюдений профессор, потряс всех ученых Земли. Он предположил, что эти надписи являются записями факториалов различных натуральных чисел в системе счисления с основанием \(K\). А символы в конце — это конечно же нули — ведь, как известно, факториалы больших чисел заканчиваются большим количеством нулей. Например, в нашей десятичной системе счисления факториалы заканчиваются на нули, начиная с \(5!=1\times2\times3\times4\times5\). А у числа \(100!\) в конце следует \(24\) нуля в десятичной системе счисления и \(48\) нулей в системе счисления с основанием 6 — так что у предположения профессора есть разумные основания!

Теперь ученым срочно нужна программа, которая по заданным числам \(N\) и \(K\) найдет количество нулей в конце записи в системе счисления с основанием \(K\) числа \(N!\), чтобы они могли проверить свою гипотезу. Вам придется написать им такую программу!

В первой строке входных данных содержатся числа \(N\) и \(K\), разделенные пробелом, (\(1\le N \le 10^9\), \(2 \le K \le 1000\)). Выведите число \(X\) — количество нулей в конце записи числа \(N!\) в системе счисления с основанием \(K\).

Ввод Вывод
5 10
1
100 10
24
100 6
48
3 10
0

ZB: Счастливые цифры

Школьнику Васе нравятся числа, которые заканчиваются счастливыми для него цифрами \(k\). Поэтому каждый раз, когда он видит какое-нибудь натуральное число n, он сразу пытается подобрать такое \(d\) (\(d \ge 2\)), что число \(n\) в системе счисления с основанием \(d\) заканчивается как можно большим количеством цифр \(k\).

Требуется написать программу, которая по заданным числам \(n\) и \(k\) найдет такое \(d\), чтобы число \(n\) в системе счисления с основанием \(d\) заканчивалось как можно большим количеством цифр \(k\).

Вводятся два целых десятичных числа \(n\) и \(k\) (\(1 \le n \le 10^{11}\), \( 0 \le k \le 9\)).

Выведите два числа: \(d\) — искомое основание системы счисления и \(l\) — количество цифр \(k\), которым заканчивается запись числа \(n\) в этой системе счисления. Если искомых \(d\) несколько, выведите любое из них, не превосходящее \(10^{12}\) (такое всегда существует).

Ввод Вывод
49 1
3 2
7 5
3 0

ZC: Интересные числа

Роман коллекционирует числа, кажущиеся ему интересными. Например, сейчас он считает интересным положительные числа, запись которых в системе счисления с основанием \(k\) заканчивается нечетным числом нулей. Например, при \(k = 2\) такими числами являются \(2_{10} = 10_{2}\), \(24_{10} = 11000_{2}\).

Для того, чтобы пополнить свою коллекцию, Роман хочет найти \(n\)-е в порядке возрастания такое число. Поскольку \(n\) он взял достаточно большим, то вручную у него это сделать не получается. Помогите Роману — напишите программу, которая найдет число, которое нужно ему для пополнения коллекции.

Первая строка входного файла содержит два целых числа \(n\) и \(k\) (\(1 \le n \le 10^{15}\), \(2 \le k le 10\)).

В выходной файл выведите \(n\)-е в порядке возрастания число, запись которого в системе счисления с основанием \(k\) заканчивается на нечетное число нулей. Это число необходимо вывести в десятичной системе счисления.

Ввод Вывод
1 2
2
10 10
110