Необходимо составить программу для машины Тьюринга, вычисляющую функцию $%2^{N} $%, где $%N$% задано в троичной системе счисления.

Смущает очень троичная система. Подскажите, пожалуйста, какой будет алгоритм.

задан 21 Май '17 3:08

Нужно уточнить, в каком формате машина должна давать ответ. Скажем, пусть мы задали запись 12 на ленте. В троичной системе это будет число N=5. Тогда 2^N=32. В какой системе выдаётся ответ? Тоже в троичной, или как-то иначе?

(21 Май '17 3:22) falcao

В троичной, отсюда и непонятно, как это сделать..

(21 Май '17 13:18) katkainite
10|600 символов нужно символов осталось
1

В деталях это всё описывать сложно, но общая идея следующая. Нужна "подпрограмма" умножения троичного числа на 2 (все действия -- в троичной системе). Тогда заводится счётчик N, из которого на каждом шаге цикла вычитается по единице, пока он не обнулится. Это делается на правой части ленты, а левее у нас будет число 1, которое будет каждый раз удваиваться.

Делается это по обычному алгоритму, когда мы умножаем "столбиком". Мы идём по записи числа справа налево, и что-то "пишем", а что-то находится "в уме". Последнее запоминается в виде состояния.

Например, у нас "в уме" 1, и удвоить надо цифру 2. Это даст 4, и ещё плюс один, то есть 5. В троичной системе мы пишем 2, и далее 1 получаем "в уме". Если бы первоначально "в уме" было 6, то мы бы написали цифру 0, и 2 перешло бы в следующий разряд. То есть это обычный алгоритм умножения, а специфика системы счисления тут роли не играет (троичная система даже проще десятичной).

Вычитание единицы из троичного числа основано на том же принципе, а помнить надо то, сколько единиц из следующего разряда мы "занимаем".

ссылка

отвечен 21 Май '17 14:07

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×786
×205
×91
×54
×44

задан
21 Май '17 3:08

показан
678 раз

обновлен
21 Май '17 14:07

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru