задан 13 Апр '17 18:35

10|600 символов нужно символов осталось
0

В подробностях здесь всё описывать очень долго, но вот основная идея.

У нас имеется строка из единиц. Сначала мы из 1^n создаём 1^n01^{2n}, а затем примерно таким же способом продолжаем до 1^n01^{2n}01^{3n}. Опишем первый из этапов.

Слово 1^n выполняет функцию счётчика -- сколько единиц справа надо допечатать. Чтобы было ясно, сколько шагов протекает этот процесс, мы в цикле начинаем стирать по единице, идём вправо, печатаем две единицы с правого конца (через разделяющий символ 0), а затем идём влево, находим место стёртой единицы, восстанавливаем её, и стираем следующую справа, после чего повторяем действия в цикле. Когда справа окажется 0, это означает, что первый этап завершён.

Покажем на примере случая трёх единиц, что при этом будет происходить, отмечая отдельные "узловые" моменты:

111

011011

10101111

1100111111

1110111111

Далее второй этап, в котором мы так же точно стираем единицы (с последующим восстановлением) у счётчика, а с правого края дописываем уже по три единицы вместо двух на предыдущем этапе. Принцип тут точно такой же. Остальное -- дело техники.

ссылка

отвечен 14 Апр '17 2:54

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

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

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

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

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

отмечен:

×44

задан
13 Апр '17 18:35

показан
294 раза

обновлен
14 Апр '17 2:54

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

по почте:

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

по RSS:

Ответы

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

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