Арифметические действия над натуральными числами в форме десятичной позиционной              системы счисления

Рассмотрим примеры выполнения арифметических действий над натуральными числами в десятичной позиционной системе счисления.

В десятичной позиционной системе счисления для записи чисел используются десять различных знаков-цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Задача 11. (Сложение двух натуральных чисел, записанных в форме десятичной позиционной системы счисления) Требуется написать алгоритм, обладающий следующим свойством: каковы бы ни были два натуральных числа n и k, если на ленте имеется запись этих чисел в форме десятичной позиционной системы счисления на расстоянии в одну ячейку друг от друга (а в остальном лента пуста), а головка размещена над крайним правым символом второго слагаемого (над разрядом единиц), то выполнение алгоритма должно привести к результативной остановке машины через некоторое число шагов, после чего на ленте должен быть записан результат сложения чисел n+k (а в остальном лента должна быть пуста), головка может быть остановлена сразу после выполнения задачи.

Пусть на ленте заданы числа 8 и 7 в форме десятичной позиционной системы счисления на расстоянии в одну ячейку друг от друга, заполненную символом «+». Начальное положение головки над разрядом единиц второго слагаемого (рис. 33). Результатом работы алгоритма должно быть число 15 (два символа на ленте: «1» и «5»).

 

8

+

7

Рис. 33

    Выполняя алгоритм, головка записывает в разряд единиц второго слагаемого символ со значением меньшим на единицу (например: «6» вместо «7»). Затем, двигаясь влево, головка устанавливается над разрядом единиц первого слагаемого и записывает в данный разряд символ со значением большим на единицу (например: «9» вместо «8») (рис. 34). Далее, головка, двигаясь вправо, возвращается в положение над разрядом единиц второго слагаемого. Данный цикл повторяется до тех пор, пока второе слагаемое не обнулится (рис. 35). После чего головка сотрет символ «+» и символ «0» на месте второго слагаемого, оставив на ленте только результат «15» на месте первого слагаемого (рис. 36).

 

9

+

6

Рис. 34

 

1

5

+

0

Рис. 35

 

1

5

Рис. 36

 

Этот алгоритм записывается в следующем виде:

Q\S

0

1

2

3

4

5

6

7

8

9

+

_

9L

0L

1L

2L

3L

4L

5L

6L

7L

8L

_R

0L

1L

2L

3L

4L

5L

6L

7L

8L

9L

+L

1R

2R

3R

4R

5R

6R

7R

8R

9R

0L

1R

0R

1R

2R

3R

4R

5R

6R

7R

8R

9R

+R

_L

_R

_N

 

Задача 12. (Вычитание двух натуральных чисел, записанных в форме десятичной позиционной системы счисления) Требуется написать алгоритм, обладающий следующим свойством: каковы бы ни были два натуральных числа n и k, где n≥k, если на ленте имеется запись этих чисел в форме десятичной позиционной системы счисления на расстоянии в одну ячейку друг от друга (а в остальном лента пуста), а головка размещена над крайним правым символом вычитаемого (над разрядом единиц), то выполнение алгоритма должно привести к результативной остановке машины через некоторое число шагов, после чего на ленте должен быть записан результат вычитания чисел n-k (а в остальном лента должна быть пуста), головка может быть остановлена сразу после выполнения задачи.

Пусть на ленте заданы числа 15 и 8 в форме десятичной позиционной системы счисления на расстоянии в одну ячейку друг от друга, заполненную символом «-». Начальное положение головки над разрядом единиц вычитаемого (рис. 37). Результатом выполнения алгоритма должно быть число 7.

 

1

5

-

8

Рис. 37

    Выполняя алгоритм, головка записывает в разряд единиц вычитаемого символ со значением меньшим на единицу (например: «7» вместо «8»). Затем, двигаясь влево, головка устанавливается над разрядом единиц уменьшаемого и записывает в данный разряд символ со значением меньшим на единицу (например: «14» вместо «15») (рис. 38). Затем, головка, двигаясь вправо, возвращается в положение над разрядом единиц вычитаемого. Данный цикл повторяется до тех пор, пока вычитаемое не обнулится (рис. 39). После чего головка сотрет символ «-» и символ «0» на месте вычитаемого, оставив на ленте только результат «7» на месте уменьшаемого (рис. 40).

 

 

1

4

-

7

Рис. 38

 

7

-

0

Рис. 39

 

7

Рис. 40

 

Этот алгоритм записывается в следующем виде:

Q\S

0

1

2

3

4

5

6

7

8

9

-

_

9L

0L

1L

2L

3L

4L

5L

6L

7L

8L

_R

0L

1L

2L

3L

4L

5L

6L

7L

8L

9L

-L

9R

0R

1R

2R

3R

4R

5R

6R

7R

8L

0L

0R

1R

2R

3R

4R

5R

6R

7R

8R

9R

-R

_L

_R

_N