|
Помогите пожалуйста сделать схему машины Тьюринга для такой задачи:
Дана унарная система счисления (алфавит {1}). Нужно число записать как произведение простых множителей. Допустим 111111111111111111111111 записать как 11*11*11*111
Решать планировал так: записывать слева единицами 2,3... - т.е. текущий делитель. Справа постепенно основное число уменьшать и записывать после него через знак-разграничитель все его делители. После каждого удачного деления пробовать еще раз разделить число на тот же делитель до тех пор, пока в остатке будет 0. В случае неудачного деления вернуть все что было и перейти в следующее состоящие, которое увеличит делитель на 1. В конце от начального числа останется 1, которая будет стоять между двумя разграничителями - это и будет признаком конца. Ну а дальше все лишнее можно будет удалить с ленты. Основная проблема, которую не знаю как решить: как разделить число, да еще так, чтобы в случае неудачного деления можно было вернуть все как было и перейти в новое состояние?
Или может есть какой-то более эффективный или простой алгоритм?
|
05.12.2010, 21:04 