@TheDailyLeo

[Машина Тьюринга] Каким образом можно разделить число (в десятичной системе счисления) на 5?

Здравствуйте! Задание звучит след. образом: "Дано число в десятичной системе счисления. Разделить его на 5". Честно, я даже не знаю с чего начать. Допустим, каретка начинает обозревать со старшего разряда. Полагаю, начать нужно так как на картинке?

5e588da1c20a5099497400.png
  • Вопрос задан
  • 387 просмотров
Пригласить эксперта
Ответы на вопрос 3
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Полагаю, что алгоритм: деление в "столбик" (как в тетрадке, без выч.средств).
Ответ написан
@SlonicK
C#, MS SQL, Visual Basic
2 действия:
1. Поделить на десять (сдвинуть десятичную запятую/точку)
2. Умножить на два (много способов)
Ответ написан
@Sumor
Надо действительно умножать на два и удалить последнюю цифру.
Умножать можно со старшего разряда, можно с младшего.
Умножение на два алгоритмически достаточно простое и требует небольшого количества состояний.
Нужно определиться с тем что будут означать состояния машины.
Вот, примерная схема, деления на 5, оно же умножения на два со старшего разряда:
Qt - Начало умножения текущей цифры
Qr - На следующем шаге просто пойдём направо
Qrr - Следующие два шага пойдём направо
Ql - Следующий шаг пойдём налево для прибавления единицы
Q1 - Добавление единицы от переполнения на предыдущих шагах
Qlast - Дошли до конца и удаляем последнюю цифру
Qend - Конец

Остальное дело техники - внимательно прописать переходы между состояниями. Вот часть переходов
1 + Qt -> 2 + Qr - на текущей позиции единица, мы вместо неё пишем двойку и готовимся на следующем шаге перейти к следующей цифре.
2 + Qr -> Right + Qt - перешли направо к следующей цифре
6 + Qt -> 2 + Ql - У нас переполнение, поэтому нужно вернуться налево и добавить единичку
2 + Ql -> Left + Q1 - перешли налево для последующего добавления единички
3 + Q1 -> 4 + Qrr - добавили единичку и планируем переместиться на две позиции направо для продолжения работы.
4 + Qrr -> Right + Qr - перемещаемся направо к текущей позиции (остался один переход направо для продолжения алгоритма)
_ + Qt -> Left + Qlast - мы дошли до конца числа - перемещаемся на последнюю цифру для затирания
0 + Qlast -> _ + Qend - затёрли последнюю цифру и заканчиваем работу.

Занимательный факт 1: 9 + Q1 - невозможное состояние
Занимательный факт 2: когда состояние машины Qlast, то она должна указывать на 0.
Ответ написан
Ваш ответ на вопрос

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

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