Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Обычно мы имеем дело с десятичной системой счисления, в которой используется ровно 10 цифр: 0..9, и мы все к этому сильно привыкли. Но для обозначения чисел возможно использование других систем, отличных от десятичной. Особенностью таких систем является, отличное от 10 количество используемых цифр. Например, в двоичной системе используется только две цифры - 0 и 1; и любое число может быть представлено в такой системе. Если система имеет порядок, больший чем 10, то в качестве следующих цифр используются латинские буквы; например, в шестнадцатеричной системе присутствуют следующие цифры: 0..9,A,B,C,D,E и F.

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

Перевод из произвольной системы счисления в десятичную

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

Перевод из десятичной системы счисления в заданную

При решении олимпиадных задач обычно рассматривают системы счисления с основаниями от 2 до 36. Это связано с тем, что в латинском алфавите 26 букв (10 цифр + 26 букв = 36 символов). Для хранения цифр числа можно использовать как целочисленный массив, так и строку. Пусть S - число, записанное в K-ой системе счисления, а X - число в десятичной системе. Тогда алгоритм перевода из любой системы в десятичную можно записать следующим образом:

read(S);
X=0;
for i = 1..len(S){
  X = X*K+S[i];
}
write(X);

Алгоритм перевода из десятичной системы числа X в систему с основанием К и записи его в S может быть представлен так:

read(X);
l=0;
do{
  l=l+1;
  S[l] = X mod K;
  X = X div K;
}while(X>0);
write(reverse(S));

Для того, чтобы перевести из k-ой системы счисления в систему с основанием m, можно воспользоваться "принципом чайника" и перевести сначала из k-ой системы в 10-ую, а затем из 10-ой в m-ую. Однако, иногда этой двойной операции можно избежать. Речь идет о случае, когда мы имеем дело с кратными системами счисления. Например, несложно переводить из 2-ой в 4-ую, 8-ую, 16-ную и обратно; аналогично можно сказать о 3-ой и 27-ой системах или о 5-ой и 25-ой. В подобных случаях каждая цифра числа в системе с большим основанием представляется в виде нескольких цифр системы с меньшим основанием. Так, в 4-ой системе каждая цифра представляется 2-мя цифрами 2-ой системы, в 8-ой - 3мя цифрами 2-ой, а в 16-ой каждая цифра есть ничто иное как 4 цифры 2-ой системы. Например, для перевода двоичного числа 101100101010011011 в 16-ую систему достаточно разбить число на 4ки: 0010 1100 1010 1001 1011 и записать каждую из них в 16-ом формате: 2CA9B, т.к. 0010 = 2, 1100 = B, 1010 = A, 1001 = 9 и 1011 = B. Несложно догадаться, что обратное преобразование из 16-ой в 2-ую систему происходит аналогичным образом.

Список задач

Задача 1: Единицы
Задача 2: Несложное вычисление
Задача 3: Наименьшая система счисления
Задача 4: Бит-реверс
Задача 5: Делимость на 7
Задача 6: Забавная игра
Задача 7: Число - палиндром
Задача 8: Система счисления

Вернуться

 
     
Югорский НИИ ИТ, Югорский ФМЛ


петли для функционального тренинга, диски.