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

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

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

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<2³¹.

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

Пример

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

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

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

Пример

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

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

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

Пример

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

J: Шестнадцатеричная сумма

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

Пример

Ввод	Вывод
F1 F	100

K: Уравновешенная троичная система счисления

В уравновешенной троичной системе счисления используется основание 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

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

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

L: Фибоначчиева система счисления

Рассмотрим последовательность Фибоначчи: F₁=1, F₂=1, F_n=F_n-1+F_n-2 при n>2. В частности, F₃=3, F₄=5, F₅=8, F₆=13 и т.д.

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

Будем говорить, что число A представимо в фибоначчиевой системе счисления в виде a_ka_k-1...a₂, где a_i∈{0;1}, если A=a_kF_k+...+a₂F₂ и в записи a_ka_k-1...a₂ нет двух единиц подряд.

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

Десятичная	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

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

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

M: Уравновешенное троичное сложение

Дано два числа, записанных в уравновешенной троичной системе счисления. Выведите их сумму без лидирующих нулей. Длины входных чисел не превосходят 1000 символов.

Пример

Ввод	Вывод
1$$$ $0$	11

Пример соответствует выражению 14+(-10)=4.

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

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

Пример

Ввод	Вывод
100101	101000

O: Фибоначчиево сложение

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

Пример

Ввод	Вывод
10010 10101	1000001

P: Дополнительный код - 1

Дано целое число А и число n. Выведите запись числа A в двоичном n-разрядном дополнительном коде.

Ограничения: 2≤n≤16, -2^n-1≤A≤2^n-1-1. Программа должна вывести последовательность из n нулей и единиц.

Пример

Ввод	Вывод
5 8	00000101
-5 8	11111011

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

Q: Дополнительный код - 2

Дана запись некоторого числа в двоичном дополнительном коде. Определите это число и выведите его.

Программа получает на вход строку из нескольких нулей и единиц длиной не меньше 2 и не больше 16. Разрядность кода определяется длиной строки.

Пример

Ввод	Вывод
00000101	5
11111011	-5

R: Двоичную дробь в десятичную

Дано неотрицательное число, записанное в виде двоичной дроби: запись содержит только цифры 0 и 1 и, возможно, точку. Запись числа содержит не более 30 символов. Переведите это значение в величину типа double и выведите результат с точностью не менее 12 знаков (инструкция cout.precision(12)).

Пример

Ввод	Вывод
11.01	3.25
100	4
0.111111	0.984375

S: Десятичную дробь в двоичную

Дано действительное неотрицательное число, не превосходящее 100, записанное в десятичном виде с фиксированной точкой. Необходимо представить его в виде двоичной дроби с фиксированной точкой и вывести это представление. Ответ должен отличаться от верного не более, чем на 2^-32 степени, поэтому необходимо вывести не менее 32 двоичных цифр после точки.

Пример

Ввод	Вывод
3.25	11.01
4	100
0.1	0.00011001100110011001100110011001100110011

T: Двоичную периодическую дробь в десятичное число

Дана запись двоичной периодической дроби, которая включает в себя:

Необязательную целую часть.
Обязательный символ точки, отделяющий целую часть от дробной.
Необязательную дробную непериодическую часть.
Необязательную периодическую дробную часть, записываемую в круглых скобках.

Переведите значение этой дроби в величину типа double и выведите результат с точностью не менее 12 знаков. Общая длина входной строки не превосходит 30 символов.

Пример

Ввод	Вывод
0.(01)	0.33333333333333
11.01	3.25
10.0(101)	2.357142857143

U: Рациональную дробь в двоичную периодическую

Дано рациональное число. Запишите его в виде двоичной периодической дроби.

На вход программа получает два натуральных числа n и m, каждое из которых не превосходит 1000. Программа должна вывести значение n/m, записанное в виде двоичной периодической дроби, при этом длина непериодической дробной части и длина периода должны быть минимально возможными. Если данное число является конечной двоичной дробью, периодическую часть выводить не надо.

Формат вывода двоичной дроби соответствует предыдущей задаче.

Пример

Ввод	Вывод
1 3	0.(01)
13 4	11.01
5 14	0.0(101)

V: Двоичную периодическую дробь в рациональное число

Дана запись двоичной периодической дроби, как в задаче T. Необходимо представить ее в виде несократимой рациональной дроби n/m. Программа должна вывести значения n и m.

Пример

Ввод	Вывод
0.(01)	1 3
11.01	13 4
0.0(101)	5 14