-----------------------------------------------------
¦ @ ¦ @ ¦ @ ¦ ^ ¦ @ ¦ @ ¦ @ ¦ ^ ¦ @ ¦ @ ¦ @ ¦ ^ ¦ ^ ¦
-----------------------------------------------------
_1.5
_22. Алгоритмы работы с числами, записанными "обычным" образом
_1.2
1. Составить функциональную схему машины, реализующей переход от десятичной записи числа n к десятичной записи числа n-1
(n>=1).
2. Составить функциональную схему машины, реализующей переход от восьмеричной записи числа n к восьмеричной записи числа n+1
(n>1).
3. Составить функциональную схему машины, реализующей переход от восьмеричной записи числа n к восьмеричной записи числа n-1
(n>=1).
4. Составить функциональную схему машины, реализующей переход от шестнадцатеричной записи числа n к шестнадцатеричной записи числа n+1 (n>1).
5. Составить функциональную схему машины, реализующей переход от шестнадцатеричной записи числа n к шестнадцатеричной записи числа n-1 (n>=1).
6. Составить функциональную схему машины, реализующей переход от двоичной записи числа n к двоичной записи n+1.
7. Составить функциональную схему машины, реализующей переход от двоичной записи числа n к двоичной записи n-1.
8. Составить функциональную схему машины, реализующей алго- ритм, который по паре натуральных чисел x и y составляет пару на- туральных чисел u и v, где u - частное, v - остаток при делении x на y.
9. Напишите программу для машины Тьюринга, работая по которой, она сложит три любых натуральных десятичных числа, разделенных звездочкой. В состоянии q0 машина обозревает крайнюю правую циф- ру.
10. Напишите программу для машины Тьюринга, работая по кото- рой, она возведет число три в любую натуральную степень, не пре- вышающую пяти. Число три и степень выписаны рядом. В состоянии q0 машина обозревает число три (основание).
11. Напишите программу для машины Тьюринга, работая по кото- рой, машина сможет извлечь квадратный корень из данного числа с точностью до целых. Программу требуется составить для конкретного числа, но алгоритм должен быть применимым к любому положительному числу.
12. На ленте машины записано число в системе счисления с осно- ванием 2,3,...,p. Записать функциональную схему машины, которая сможет выписать на ленту число, непосредственно следующее за дан- ным. Каретка находится под цифрой младшего разряда данного числа.
13. На ленте записано число в системе счисления с основанием
2,3,...,p. Написать функциональную схему машины, которая сможет выписать на ленту число, предшествующее данному. Каретка находит- ся под цифрой младшего разряда данного числа.
14. На ленте машины Тьюринга записано число, представленное в десятичной системе счисления, а следом за ним записано некоторое количество звездочек. Составить функциональную схему, работая по которой машина Тьюринга увеличивала бы данное число на количество звездочек.
15. На ленте машины Тьюринга записано число, представленное в десятичной системе счисления, а следом за ним записано некоторое количество звездочек. Составить функциональную схему, работая по которой машина Тьюринга уменьшит данное число на количество звез- дочек.
_1.5
_23. Алгоритмы работы с числами, записанными в унарной форме
(число X изображается X+1 палочкой)
_1.2
1. Составить функциональную схему машины, реализующей алгоритм сложения двух чисел в унарной записи, расположенных на расстоянии две ячейки одно от другого.
2. Составить функциональную схему машины, реализующей алгоритм вычитания из числа единицы.
3. Составить функциональную схему машины, реализующей алгоритм сложения произвольного количества чисел, записанных на расстоянии одна ячейка друг от друга.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.