Интернет магазин китайских планшетных компьютеров


Компьютеры - Признаки делимости - Общие принципы построения

23 января 2011


Оглавление:
1. Признаки делимости
2. Общие принципы построения
3. Признаки делимости в десятичной системе счисления
4. Признаки делимости в других системах счисления



Пусть требуется определить делится ли некоторое натуральное число A на другое натуральное число m. Для этого будем строить последовательность натуральных чисел:

A_0,\,A_1,\,A_2,\,A_3,\,\dots,\,A_n,

такую, что:

  1. A_0 = A;\,
  2. каждый член последовательности вполне определяется предыдущим;
  3. A_i < A_{i-1},\quad i=1,\,2,\,3,\,\dots,\,n-1;
  4. последний член последовательности меньше m, то есть 0 \leqslant A_n < m.\,
  5. все члены последовательности являются равноделимыми на m.

Тогда если последний член этой последовательности равен нулю, то A делится на m, в противном случае A на m не делится.

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

A_i = f\left,\quad i=1,\,2,\,3,\,\dots,\,n-1,

удовлетворяющей следующим условиям:

  1. при x < m\, значение f\, не определено;
  2. при x \geqslant m значение f\, есть натуральное число;
  3. если x \geqslant m, то f < x;\,
  4. если x \geqslant m, то f\, и x равноделимы на m.

Если требование равноделимости для всех членов последовательности заменить на более строгое требование равноостаточности, то последний член этой последовательности будет являться остатком от деления A на m, а способ построения такой последовательности будет признаком равноостаточности на m. В силу того, что из равенства остатка при делении на m нулю следует делимость на m, любой признак равноостаточности может применяться как признак делимости. Математически признак равноостаточности тоже может быть описан с помощью функции f,\, определяющей каждый следующий член последовательности в зависимости от предыдущего:

A_i = f\left,\quad i=1,\,2,\,3,\,\dots,\,n-1,

удовлетворяющей следующим условиям:

  1. при x < m\, значение f\, не определено;
  2. при x \geqslant m значение f\, есть натуральное число;
  3. если x \geqslant m, то f < x;\,
  4. если x \geqslant m, то f\, и x равноостаточны при делении на m.

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

f = x - m,\quad x \geqslant m,

а последовательность, построенная с её помощью будет иметь вид:

A,\,A-m,\,A-2m,\,A-3m,\,\dots

По сути применение признака равноостаточности на базе этой функции эквивалентно делению при помощи вычитания.

Другим примером может служить общеизвестный признак делимости на 10.

Если последняя цифра в десятичной записи числа равна нулю, то это число делится на 10; кроме того, последняя цифра будет являться отстатком от деления исходного числа на 10.

Математически этот признак равноостаточности может быть сформулирован следующим образом. Пусть надо выяснить остаток от деления на 10 натурального числа A, представленного в виде

A = 10\,b + a,\quad 0 \leqslant a < 10,\quad b \geqslant 0.

Тогда остатком от деления A на 10 будет a. Функция, описывающая это признак равноостаточности будет выглядеть как

f = a,\quad A \geqslant 10.

Легко доказать, что эта функция удовлетворяет всем перечисленным выше требованиям. Причём последовательность, построенная с её помощью, будет содержать всего один или два члена.

Также легко видеть, что такой признак ориентирован именно на десятичное представление числа A — так, например, если применять его на компьютере, использующем двоичную запись числа, то чтобы выяснить a, программе пришлось бы сначала поделить A на 10.



Просмотров: 7305


<<< Решето Аткина


Компьютерное аппаратное обеспечение   
Вычислительные комплексы   
Компьютерные данные   
Компьютерные журналы   
Классы компьютеров   
Компьютеры   
Программное обеспечение   
Производители компьютеров   
Профессии в ИТ   
Системное администрирование   
Компьютерный сленг   
Списки компьютерных терминов   
Человеко-компьютерное взаимодействие