Факториальная форма записи чисел (нетрадиционная позиционная система счисления).
Чтобы перевести число из 10-й традиционной ПСС в факториальную (от слова ФАКТОРИАЛ), надо целую часть числа разделить сначала на 2, записывая целую часть частного и остаток (тоже целое число, которое меньше делителя!). Затем эту полученную целую часть частного делим дальше на 3, потом на 4 и т.д., пока целая часть не окажется равной 0. Записываем все целочисленные остатки, начиная с последнего.
Перевод из 10-й СС в факториальную:
53/2 = 26 (ост.1)
26/3 = 8 (ост.2)
8/4 = 2 (ост.0)
2/5 = 0 (ост.2)
ответ: 53₁₀ = 2021(ф)
196/2 = 98 (ост.0)
98/3 = 32 (ост.2)
32/4 = 8 (ост.0)
8/5 = 1 (ост.3)
1/6 = 0 (ост.1)
ответ: 196₁₀ = 13020(ф)
7394/2 = 3697 (ост.0)
3697/3 = 1232 (ост.1)
1232/4 = 308 (ост.0)
308/5 = 61 (ост.3)
61/6 = 10 (ост.1)
10/7 = 1 (ост.3)
1/8 = 0 (ост.1)
ответ: 7394₁₀ = 1313010(ф)
Перевод из факториальной ПСС в десятичную.
Записываем сумму факториалов n первых натуральных чисел, умноженных на цифры факториальной записи числа.
21(ф) = 2*2!+1*1! = 5₁₀
13021 (ф) = 1*5! + 3*4! + 2*2! + 1*1! = 120 + 72 + 4 + 1 = 197₁₀
4502120 (ф) = 4*7! + 5*6! + 2*4! + 1*3! + 2*2! = 20160 + 3600 + 48 + 6 + 4 = 23818₁₀
Нули в сумму я не вписываю, потому что умножай его, не умножай – всё равно 0!
Напоминаю про факториал (n!): 6! = 6*5*4*3*2*1; 4! = 4*3*2*1 и т.д.
1. На ленте машины Тьюринга содержится последовательностью символов “+”. Напишите программу для машины Тьюринга, которая каждый второй символ “+” заменит на “–”. Замена начинается с правого конца последовательности. Автомат в состоянии q1 обозревает один из символов указанной последовательности. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
2. Дано число n в восьмеричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1. Автомат в состоянии q1 обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
3. Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
4. Дано натуральное число n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было “100”, то выходным словом должно быть “99”, а не “099”. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
5. Дан массив из открывающих и закрывающих скобок. Построить машину Тьюринга, которая удаляла бы пары взаимных скобок, т.е. расположенных подряд “( )”.
Например, дано “) ( ( ) ( ( )”, надо получить “) . . . ( ( ”.
Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
6. Дана строка из букв “a” и “b”. Разработать машину Тьюринга, которая переместит все буквы “a” в левую, а буквы “b” — в правую части строки. Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
