Урок №1. Позиционные системы счисления.

Для записи целых чисел можно использовать разные способы. Такие способы принято называть системами счисления. Например, целое число можно записывать последовательностью «палочек». Число 5 выглядит при таком способе как |||||. Понятно, что такой способ хорош только для записи небольших чисел. Для записи целых чисел, особенно дат, иногда применяют римскую систему счисления. В этой системе 2013 год записывается следующим образом MMXIII.

Основным способом записи чисел является их запись в различных позиционных системах счисления. Для записи числа в позиционной системе счисления используется некоторое множество символов, называемых цифрами системы счисления. Общепринято использовать 10 цифр — 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, значения которых задают первые 10 чисел натурального ряда. Число используемых цифр задает основание системы счисления. В привычной со школьной скамьи десятичной системе счисления используются 10 цифр. В двоичной системе счисления с основанием 2 используются две цифры – 0 и 1. В позиционных системах счисления с основанием p, где p <=10 обычно используются первые p из приведенных 10 цифр. В системах счисления с основанием p > 10 десяти приведенных цифр не хватает, поэтому необходимы другие символы для записи цифр. В широко используемой при работе с компьютерами 16-иричной системе счисления, где необходимо 16 цифр, наряду с цифрами 0 – 9 в качестве цифр используют начальные буквы латинского алфавита – A, B, C, D, E, F, задающие соответственно числа от 10 до 15.

В любой системе счисления основание системы счисления – число p – всегда записывается как число 10. Поясним причину этого на примере десятичной системы. Число 9 можно записать, используя цифру 9, но, если прибавить к 9 единицу, то на следующее число цифры уже не будет. Поэтому в позиционных системах в таких случаях число записывается с помощью двух цифр как число 10 – в младшем разряде пишется 0, а в старшем 1. В двоичной системе счисления числа 0 и 1 можно записать с помощью цифр, но, если прибавить к 1 единицу, то для двойки уже цифры нет, поэтому в двоичной системе число 2 записывается с помощью двух цифр, как число 10.

Вопрос: Чему равно число, записанное в системе счисления с основанием p как 10p?

Ответ: Эта запись означает число p в привычной для нас десятичной системе счисления.

Вопрос: В каких системах счисления справедливы утверждения? 2 * 2 = 10 2 * 2 = 11 2 * 2 = 100 2 * 2 = 4

Ответы: ( В системах с основаниями соответственно: 4, 3, 2, в любых системах с основанием p > 4)

Рассмотрим привычную для нас запись числа N = 754 в десятичной системе счисления. Не задумываясь, мы ответим, что число N состоит из 7-и сотен, 5-и десятков и 4-х единиц.

N = 7* 10 2 + 5 * 10 1 + 4*10 0

В общем случае запись N = ck-1 ck-2…c0, где ci – цифры системы счисления означает: N = ck-1 * p k-1 + ck-2 * p k-2 + … + c0 * p 0 , (*)

где p – основание системы счисления. Учитывая, что в любой системе счисления p = 10, то справедлива и такая запись:

Вот точное определение:

Запись числа в позиционной системе счисления означает разложение числа по степеням основания. В роли коэффициентов выступают цифры системы счисления.

Понимание этого факта и соответствующего ему представления числа N соотношением (*) достаточно для решения многих задач экзамена ЕГЭ.

Задача 1: Сколько единиц в двоичной записи числа 130?

Решение. Число 130 = 128 + 2 = 1* 2 7 + 1* 2 1 . Остальные коэффициенты равны 0. Полное решение задачи. Поскольку максимальная степень двойки равна 7, то число 130 в двоичной системе будет содержать 8 цифр – 2 единицы и 6 нулей 13010 = 100000102 Задача 1 решается мгновенно, если помнить степени числа 2

Задача 2: Сколько нулей в троичной записи числа 130?

Решение: Используя разложение по степеням основания 3, число 130 можно представить: 13010 = 3 4 + 3 3 + 2*3 2 + 3 + 1 = 81 + 27 + 18 + 3 + 1 = 112113

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

Задача 3: Чему равно число, записанное как 2435 в пятеричной системе счисления?

Решение: Это обратная задача по отношению к задаче 1. Здесь, зная цифры и основание системы счисления, нужно восстановить число, используя соотношение (*).

N = 2435 = 2*5 2 + 4 * 5 1 + 3 = 50 + 20 + 3 = 7310

Задача 4: Число 2435 записать в двоичной системе счисления?

Решение: Задача записи числа N в системе счисления с основанием p, если задана его запись в системе с основанием q, решается в два этапа. На первом этапе число переводится в десятичную систему, на втором этапе – в систему с основанием p.

Формальный алгоритм перевода десятичного числа в систему с основанием p

Алгоритм достаточно прост. На пальцах он выглядит так. Необходимо последовательно делить число на p — основание системы счисления. Остатки от деления дают цифры для записи числа в системе с основанием p.

Приведу обоснование алгоритма:

Воспользуемся представлением (*) для записи числа N.

Положим M = N = ck-1 * p k -1 + ck-2 * p k -2 + … + c0 * p 0 ;
Представим число M в виде: M = (ck-1 * p k -2 + ck-2 * p k -3 + … + c1) * p + c0
Нетрудно видеть: с0 = M % p, где операция % означает остаток от деления;
Вычислим новое значение M = M / p, где операция / означает деление нацело. Результатом этой операции является число, от которого отрезана последняя цифра; Полученное число сохраняет представление (*).
Операции 3 и 4 будем повторять k раз, получая каждый раз очередную цифру в разложении N по степеням основания p.

Вот как выглядит точная запись этого алгоритма в виде функции на языке С#:

/// Перевод десятичного числа N

/// в систему счисления с основанием p

/// <param name=»p»>основание системы счисления</param>

/// строка, задающая запись числа

/// в системе с основанием p

static string Perevod10ToP(int N, int p)

result = (M % p).ToString() + result;

К этому алгоритму мы еще вернемся, а сейчас рассмотрим несколько менее тривиальных задач, на тему представления чисел в системах счисления.

Задача 5: Число 77 в системе счисления с основанием p заканчивается на 0, а число 29 в этой системе заканчивается на 1. Чему равно p – основание системы счисления?

Решение: При обосновании алгоритма перевода было показано, что с учетом представления (*) любое число может быть записано в виде:

Отсюда следует возможность представить наши числа 77 и 29 следующим образом:

Следовательно, справедливо соотношение:

Произведение двух целых, отличных от 1, равно 49 в том и только в том случае, когда:

Задача 6: Двузначное число N в системах счисления с основаниями 3 и 7 заканчивается одной и той же цифрой. Укажите минимально возможное значение N .

Решение: N представимо в виде:

Следовательно, справедливо соотношение:

Минимальное значение для N получается при:

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

При выполнении фрагмента программы на печать выводятся два числа - 3 и 18.

Каким может быть минимальное (максимальное) значение числа N в этом случае?

a = a + 1; //число цифр в числе

b = b + N % 10; //сумма цифр

Console.WriteLine(“ a = “ + a.ToString());

Console.WriteLine(“ b = “ + b.ToString());

Ответ: минимальное N – 189; максимальное N = 990

Решение: Если в качестве основания системы использовать число 10, то алгоритм позволяет разобрать десятичное число на цифры. Переменная a играет роль счетчика цикла, задавая тем самым число цифр в числе. Переменная b в данном фрагменте вычисляет сумму цифр. Задача сводится к определению к-значного числа по заданной сумме его цифр. Если сумма трех цифр числа равна 18, то первой цифрой у числа с минимальным значением может быть цифра 1. Две оставшиеся цифры в сумме дают 17, откуда и следует ответ. Для максимального числа, последней цифрой может быть 0, а две старшие цифры могут быть равны 9.

Задача 8: При выполнении фрагмента программы на печать выводятся два числа — 3 и 18. Перечислите все возможные значения числа N в этом случае?

a = a + 1; //число цифр в числе

b = b * N % 10; //произведение цифр

Console.WriteLine(“ a = “ + a.ToString());

Console.WriteLine(“ b = “ + b.ToString());

Ответ: (129, 136, 163, 192, 219, 233, 291, 316, 323, 332, 361, 613, 631, 912, 921)

Решение: Эта задача является вариацией предыдущей задачи. Здесь необходимо определить возможное значение трехзначного числа, зная произведение его цифр. В ответе перечислены все возможные решения

📎📎📎📎📎📎📎📎📎📎