Голландская национальная проблема заключается в следующем: у меня есть последовательность символов x^k (k >= 3). Моя цель — преобразовать это предложение в голландский флаг, то есть:
ХХХ дает RWB
xxxx дает RWBB
ххххх дает RWWBB
xxxxxx дает RRWWBB
...
где R ‹= W ‹= B ‹= R+1
Я хочу спроектировать машину Тьюринга с одной лентой и сложностью n.log(n) . Дело в том, что стандартный алгоритм использует свопы и я не могу его использовать, что недоступно (недостаточно эффективно) в такой машине Тьюринга....
Вы знаете, как это сделать? :)
