@nimbus214

Остаток от деления на машине Тьюринга?

подскажите как реализовать данную задачу, идей нет.
614d8710d01e1009966770.jpeg
  • Вопрос задан
  • 236 просмотров
Решения вопроса 1
zagayevskiy
@zagayevskiy
Android developer at Yandex
В общем порекомендую сначала прикинуть алгоритм на естественном языке, в смысле, как бы это могло быть:
Встаем на %.
Пока в делителе есть 1, заменяем её на Х, и заменяем одну 1 в делимом на Y. Если в делимом нет единиц(нечего заменить на Y), то переносим все Y в виде 1 на ячейки после "->". Это и есть ответ.
Когда в делителе все 1 заменены на Х, заменяем их обратно на 1 и проверяем, остались ли ещё 1 в делимом.
Если в делимом остались единицы, заменяем все Y на 0, встаем на % и начинаем всё это заново.
Если в делимом единиц не осталось, то переносим все оставшиеся Y в виде 1 на ячейки после "->". Это и есть ответ.
Тут была ошибка. Мы только что успешно закончили отнимать очередной делитель, и в делимом больше ничего не осталось. Это значит, что разделилось нацело.

Не скажу, что это оптимально, но работать будет. Может быть , надо продумать ещё какие-то корнер кейсы, но идея должна быть понятна. По сути ты просто отнимаешь от делимого делитель до тех пор, пока делимое не станет меньше делителя.
Теперь каждое из этих правил надо оформить в виде набора правил для МТ. Всех этих "когда/если/то" в МТ конечно нет, поэтому придется эмулировать их переходами в соответствующее состояние. Это не сложно, но правил может получиться реально много. Например, простая фраза "Пока в делителе есть 1, заменяем её на Х, и заменяем одну 1 в делимом на Y." будет развернута в 3-5 состояний.

Плюс, этот алгоритм портит исходные данные. Если портить их нельзя, то надо сначала скопировать их в другое место на ленте, а потом не забыть "прибраться", удалив оставшийся мусор.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы