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

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

Под унар­ной формой за­пи­си на­ту­ра­ль­но­го чис­ла n бу­дем по­ни­мать на­бор, со­сто­ящий из n+1 сим­во­лов «I» (т.е. в унарной записи для изображения числа 0 используется один символ «I», числа 1 два символа «I» и т.д.).

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

    Пусть на ленте задано число 4 в унарной форме записи (т.е. пятью символами «I») (рис. 23). Результатом работы алгоритма должно быть число 5 (шесть символов «I» на ленте (рис. 24). Так как изображение результата на ленте отличается от исходного изображения числа только на один символ, то решением данной задачи является алгоритм, на основании которого выполняется прибавление единицы в форме наивной унарной записи. Этот алгоритм описан выше в задаче 1.

 

I

I

I

I

I

Рис. 23

 

I

I

I

I

I

I

Рис. 24

 

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

Пусть на ленте заданы числа 3 и 4 в унарной форме записи на расстоянии в одну пустую ячейку друг от друга, и начальное положение головки левее массива первого слагаемого (рис. 25). Результатом работы алгоритма должно быть число 7 (восемь символов «I» на ленте).

 

I

I

I

I

I

I

I

I

I

Рис. 25

Для реализации данной задачи, недостаточно только сдвинуть массив первого слагаемого (n) к массиву второго слагаемого (k), как было осуществлено в аналогичной задаче с числами, записанными в наивной унарной форме (задача 2). Дополнительно необходимо стереть в массиве результата один символ «I», иначе его запись будет содержать на один символ больше чем в записи верного решения (рис. 26).

 

I

I

I

I

I

I

I

I

Рис. 26

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

Q\S	I	_
	_ R	_ R
	I R	I R
	I R	_ L
	_ L

 

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

Пусть на ленте заданы числа 7 и 4 в унарной форме записи на расстоянии в одну пустую ячейку друг от друга, и начальное положение головки над крайним слева символом уменьшаемого (рис. 27). Результатом работы алгоритма должно быть число 3 (четыре символа «I» на ленте).

 

I

I

I

I

I

I

I

I

I

I

I

I

I

Рис. 27

Для реализации данной задачи, необходимо выполнить действия аналогичные действиям, описанным в задаче 3 с поправкой: к полученному результату необходимо прибавить один символ «I», иначе его запись будет содержать на один символ меньше, чем в записи верного решения (рис. 28).

                                                                                          

I

I

I

I

Рис. 28

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

Q\S	I	#	_
	I L		_ R
			# R
	I R		_ R
	I R		# L
	I L		_ N
	_ L	_ L	_ R
	_ R		_ L
	I L	# L	_ L

 

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

Пусть на ленте заданы числа 3 (четыре символа на ленте) и 2 (три символа на ленте) в форме унарной записи на расстоянии в одну пустую ячейку друг от друга. Начальное положение головки над крайним слева символом множимого (рис. 29). Результатом работы алгоритма должно быть число 6 (семь символов «I» на ленте).

 

I

I

I

I

I

I

I

Рис. 29

Для реализации данной задачи, необходимо в ходе выполнения алгоритма, перевести эти числа в наивную унарную форму, решить задачу согласно решению задачи 4 с поправкой: к получившемуся результату необходимо прибавить один символ «I», иначе его запись будет содержать на один символ меньше чем в записи верного решения (рис. 30).

 

I

I

I

I

I

I

I

Рис. 30

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

Q\S	I	*	#	_
	_ R			_ R
	I R			_ R
	I R			_ L
	_ L
	I L			* L
	I R			_ R
	_ R	_ R
	I R	* R
	# R	* R	# L	* L
	I R	* L	I R
	I R	* R	# R	I L
	I L	* L
	I R		# L
	# L	* L
	I L			_ R
		I N	_ R

 

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

Пусть на ленте заданы числа 7 (восемь символов «I» на ленте) и 2 (три символа «I» на ленте) в унарной форме записи на расстоянии в одну пустую ячейку друг от друга, и начальное положение головки над крайним слева символом делимого (рис. 31). Результатом выполнения алгоритма должно быть число 3 (четыре символа «I» на ленте) (рис. 32).

 

I

I

I

I

I

I

I

I

I

Рис. 31

 

I

I

I

I

Рис. 32

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

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

Q\S	I	*	#	_
	_ R			_ R
	I R			_ R
	I R			_ L
	_ L
	I L			_ L
	I L			_ R
	I L			_ R
				* R
	I R			_ R
	I R			* L
	I L			_N
	_ R	_ R		_ L
	# R		# R	_ R
	I L	* R
			# L	_ N
	I R			I L
	I L	* L	I L	_ N
	_ R	_ N	_ R	_ R