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

Упражнения

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

В системе счисления с основанием 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<2³¹.

Необходимо вывести значение 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 будем обозначать знаком $. Достоинство уравновешенной троичной системы счисления: простота хранения отрицательных чисел и удобство нахождения числа, противоположному данному.

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

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

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

$01

-8

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

Рассмотрим последовательность Фибоначчи: F₁=1, F₂=2, 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 и должна вывести одно целое число. Гарантируется, что результат может принимать значения от 0 до 2·10⁹.

10101

12

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

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

-8

$01

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

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

12

10101

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

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

Доказательство оформляется в LaTeX, на проверку нужно сдать PDF-файл с текстом доказательства.

O: Инкремент

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

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

19A
11

1A0

P: Декремент

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

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

1A0
11

19A

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

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

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

$01

$1$

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

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

$1$

$01

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

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

100101

101000

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

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

101000

100101