e-olymp

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

Вещи бывают великими и малыми не токмо по воле судьбы и обстоятельств, но также по понятиям каждого.

Козьма Прутков

Существует 10 видов людей: те, кто понимает двоичную систему счисления, и те, кто ее не понимает...


   Наверное все понимают, что использование десятичной системы счисления имеет исторические корни и тесно связано с биологическим строением организма вида homo sapiens.

   Существовали и другие системы, связанные именно с анатомическим строеним организма человека. Об этом, в частности, упоминал и Теодор Заркуа на своих лекциях зимней школы по программированию в Харькове в 2010 г. [1]. Более детально с  исторической информацией о системах счисления можно онакомится в [2].

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

   В компьютерных технологиях широко используются двоичная, восьмеричная и шестнадцатиричные системы счисления. В 16-ричной системе счисления для обозначения цифр больших 9-ти используют прописные буквы латинского алфавита. Использование двоичной системы счисления в компьютерных технологиях объясняется тремя параметрами: простотой, надежностью и дешевизной.

Основная теорема арифметики

   Теорема 1:Каждое натуральное число может быть представлено в виде произведения простых одним и только одним способом.

   Упражнение: Попробуйте доказать эту теорему воспользовавшись методом математической индукции.

   Основная теорема арифметики вскрывает структуру натуральных чисел по отношению к операции умножения. Эта теорема показывает, что все натуральные числа получаются из простых с помощью всевозможных умножений, причем в результате различных умножений получаются различные числа. Именно поэтому число 1 не относится к простым числам.

Следствия из основной теоремы

   Пусть задано натуральное n:

n = paqb...                                          (1)

   Тогда полное число делителей числа n (включая 1 и n), обзначаемое через d(n), равно:

d(n) = (a+1)(b+1)...                           (2)

   Сумма делителей, обозначаемая σ(n), равна:

σ(n) = {1+p+...+pa}{1+q+...+qb}...    (3)

   Указанные арифметические функции и их значения давно известны, см., например,: http://en.wikipedia.org/wiki/Divisor_function [3].

Алгоритм Евклида

   "Пока числа не равны, от большего отнимай меньшее и заноси в большее", - как утверждает одна из легенд, именно эти слова, описывающие алгоритм Евклида, выбиты на надгробном камне великого грека.

   С алгоритмом Евклида для нахождения НОД и НОК рекомендуем ознакомиться в статье М.Медведева "Наибольший общий делитель и наименьшее общее кратное", здесь же отметим, что существует более хитрый алгоритм для нахождения НОК, не требующий выполнения операции умножения, описанный в [4]. Приведем его реализацию на языке Паскаль, (перевод на С++ сложности не составляет):

var nsd, nsk, x, y, u, v : longint;
begin
  readln(x,y); u := y; v := x;
  while x <> y do
  begin
    if x > y then begin x := x-y; v := v+u end
    else if y > x then begin y := y-x; u := u+v end;
  end;
  nsd := (x+y) div 2;
  nsk := (u+v) div 2;
  writeln(nsd,' ',nsk);
end.

   Интересующимся рекомендуем ознакомится с описанием алгоритма в указанной книге и разобраться с деталями. 

   Используя алгоритм Евклида можно найти целочисленные решения диофантового уравнения ax + by = c, если они существуют.

   Теорема 2:Уравнение ax + by = c, где a, b и c - целые числа, имеет целочисленное решение тогда и только тогда, когда c делится на НОД(a, b).

    Если c делится на НОД(a, b), то решением уравнения ax + by = c является пара чисел:

x0 = (u·c)/НОД(a, b), y0 = (v·c)/НОД(a, b),  (4)

где u и v - любое решение уравнения НОД(a, b) = a·u + b·v.           (5)

   Эта теорема дает возможность определять, существует ли решение, и находить частичное решение для уравнения ax + by = c, если оно существует. Следующая теорема дает возможность находить все решения уравнения.

   Теорема 3:Если a иb- ненулевые целые числа и (x0, y0) - решение уравнения ax + by = c, тогда любое другое решение (x, y) имеет вид:

x = x0 + (b/d)t;

y = y0 - (a/d)t,

где t - произвольное целое число, а d = НОД(a, b).

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

   Выберем некоторое число p - основание системы счисления. Каждое число N тогда можно представить в виде комбинации его степеней с коэффициентами, принимающими значение от 0 до p-1, в виде:

ak·pk+ak-1·pk-1+...+a1·p+a0                    (6)

   Обычно это число сокращенно записывается в виде:

(akak-1...a1a0)p.

   Перевод из десятичной системы счисления в p-ичную систему счисления описывается следующим алгоритмом: делить заданное десятичное число N на основание p целиком нацело до тех пор, пока в частном не получим 0. Полученные в процессе деления остатки, записанные в обратном порядке, и дают p-ичное представление заданного десятичного числа.

   Перевод из p-ичной системы счисления в десятичную осуществляется также в обратном порядке, путем умножения цифр p-ичного передставления числа на последовательные степени числа p, начиная с нулевой (6).

Игра "НИМ"

   Еще в древнем Китае была известна следующая игра, называвшаяся игрой "НИМ": Имеется три кучки камней. Двое играющих поочередно берут камни из этих кучек. За один ход разрешается взять любое отличное от нуля число камней, но только с одной кучки. Выигрывает взявший последний камень.

   Для решения этой задачи удобно воспользоватся двоичной системой. Пусть в трех кучках лежат, соответственно a, b, и c камней. Запишем эти числа в двоичной системе:

a=am·2m+am-1·2m-1+...+a1·2+a0 ,

b=bm·2m+bm-1·2m-1+...+b1·2+b0 ,

c=cm·2m+cm-1·2m-1+...+c1·2+c0 .

   Если в каком-то двоичном представлении числа не хватает разрядов, дополним его впереди ведущими нулями. Таким образом, каждая из цифр a0, b0, c0, ..., am, bm, cm может быть равна 0 или 1, причем из цифр am, bm и   cm хотя бы одна (но не обязательно все!) отлична от нуля. Игрок, делающий первый ход, может заменить одно из чисел a, b или c любым меньшим числом.

   Рассмотрим суммы

  am+bm+ cm, am-1+bm-1+ cm-1, ..., a0+b0+ c0.   (7)

   Каждая из этих сумм может быть равна 0, 1, 2 или 3. Если хотя бы одна из этих сумм нечетна, то игрок, делающий первый ход, может обеспечить себе выигрыш, взяв такое количество камней, чтобы все из сумм (7) стали четными.

Литература

1. Зимняя школа по программированию., Харьков, ХНУРЭ - 2010, 290 с.

2. Фомин С.В. Системы счисления. - 5-е изд. - М.: Наука, 1987. - 48 с.

3. http://en.wikipedia.org/wiki/Divisor_function

4. Дейкстра Э. "Дисциплина программирования", М.: Мир, 1978. - 265 с.

5. Гашков С.Б. "Системы счисления и их применение", М.: МЦНМО, 2004. - 52 с.: ил.