maxal писал(а):
незваный гость писал(а):
:evil:
"""Меня терзают смутные сомнения.""" Предполагая, что подпрограмма перестановки сделана, где гарантия, что пузырек остановится? (Может быть, мой вопрос сводится к тому, как сделать маркер начала. А это, в свою очередь, к вопросу, как сделать 00.)
Сделать 00 не проблема. Сначала пишем прогу для случая, когда два 00 есть, а потом еще ее модификацию для случая, когда есть только один 0: у самого первого слова заменяем первую единицу на 0 (получая таким образом два нуля) и помним этот факт, когда дело доходит до сравнения/обмена первого слова со вторым по счету. Аналогичным образом можно получить два нуля для обозначения конца сортированного участка.
Бесконечная в два конца лента тоже проблем не доставляет, в этом случае ведем поиск новых слов по одной позиции вправо и влево: вправо пробегаем отсортированный участок (до двух нулей), и смотрим есть ли сразу за ним новое слово, если есть обрабатываем, если нет ставим 1; бежим влево до двух нулей и смотрим есть ли там новое слово, есть - обрабатываем, нет - ставим единичку; затем снова бежим вправо по отсортированному участку до двух нулей, затем ищем нашу единичку, стираем ее, смотрим есть ли слово в следующей позиции, если есть - обрабатываем, нет - ставим единичку в эту позицию; затем бежим вправо до 1 после отсортированного участка и сдвигаем ее правее, если слово не найдено и т.д.
С искусственным созданием двух нулей (при необходимости) ситуация та же, что в однонаправленной бесконечной лентой.
Спасибо большое за идею решения! Только возникают небольшие вопросы:
1. Обрабатывая параллельно два отсортированных участка, мы также должны сравнивать их между собой. Возникает идея решать эту проблему следующим способом: обработав слово на правом участке, его надо прогнать по левому участку либо до тех пор, пока не натолкнёмся на слово большей или равной длины (тогда прогоним его обратно в правый участок и поставим на место либо остановимся соответственно), либо натолкнёмся на 00, ограничивающие левый участок и также прогоним это слово в правый участок и поставим его на место. Аналогично со словами из левого участка. Не возникнет ли здесь какая-нибудь спорная ситуация?
2. Я придумал метод, который меняет местами два массива из единиц, но думаю, что есть метод попроще. Не могли бы Вы более подробно описать, как это делать?
P.S.
Уточнения к условию: лента бесконечная в обе стороны, а код, на неё нанесённый, есть не что иное, как последовательности из единичек, разделённые ровно одним нулём. Возможно, что такой код бесконечен в обе стороны, если в одну сторону он конечен, то далее следует бесконечная последовательность из одних нулей. Задачка представляет сложность только в том случае, если код в обе стороны бесконечный.
08.12.2006, 01:18 
