Каким образом можно циклично сдвинуть строку длиной n на m символов при константной дополнительной памяти за линейное время?
UPDATE: ответ.
Понравилась статья? Подпишись на обновления по RSS/E-mail
Станьте автором нашего сайта!
Какие материалы подходят для публикации? — Такие.
Присылайте статьи на editors@developers.org.ua.
| интернет магазин | бытовая техника | магазин Laptoper |
|---|
© 2005–2010 developers.org.ua
Использование материалов сайта в коммерческих целях возможно только с письменного разрешения редакции.
тел.: (044) 222-87-72
support@developers.org.ua
Загрузка ...
Псевдокод:
shift = m % n;
str = str.substr(shift) + str.substr(0, shift-1);
Сначала вычисляем на сколько символов нужно реально сдвинуть (если вдруг m > n),
а затем меняем местами части строки: start..(shift-1) shift..end.
Вроде так : )
Символы «съелись». Короче, свопаем вот так: swap(start..(shift-1), shift..end), где «..» это диапазон.
Задачка сама по себе не очень сложная – сделать из “колбаса” “басакол”.
А вот решить ее, соблюдая ограничения – уже труднее:
Кстати, чтобы код был секси, надо заключать его в теги pre+code.
В некотором смысле, эта задача есть частным случаем предыдущей.
Условие «за линейное время» в моём решение соблюдено.
А условие «при константной доп. памяти» решается копированием символов
из первой части строки в конец второй части с использованием фиксированного
по размеру буфера. Если буфер будет равен одному символу, то мы решаем эту
задачу на O(m) времени.
2 1mdm:
мне кажется, вы не совсем правильно поняли, что значит “при константной доп. памяти”.
Константной должна быть вся память, которая понадобится для решения задачи, не считая исходной строки, т.е. у нас есть n байт + k байт, где k не зависит от m и n. Если “копировать символы
из первой части строки в конец второй части”, то будет дополнительно использованно m байт, так ведь?
2 1mdm
А мне кажется что этот код не будет работать вообще
А ведь-таки так! Тогда нужно с начала строки и до shift-1 копировать символы в буфер размером k байт, затем сдвигать всю строку влево на k байт и символы из буфера копировать в конец строки. Или наоборот.
2 Igor
О каком коде вы говорите? В первом комментарии я писал псевдокод.
2 1mdm:
тогда не получится линейного времени, поскольку на каждое копирование у нас уйдет k операций, на сдвиг еще (n-k) и на обратное копирование — снова k. Итого: n+k. А сделать это нужно будет m/k раз. Т.е. выходит, если я не ошибаюсь, квадратичное время выполнения: (n+k)*m/k…
2 Всеволод
Наверное вы правы.
Тогда уместно будет использовать XOR для перестановки соответствующих символов в строке. Время будет = O(m/k).
Класна задача, раніше такої не бачив.
Будемо вважати, що зсуваємо вліво.
Яка ідея придумалась:
Йдемо зліва направо, і обмінюємо символ з номером і на символ з номером і + m, допоки не дійдемо до моменту, коли цього зробити не можна, бо і + m вилазить за межі.
Наприклад, зсуваємо рядок “abcdefg” на 3 символи вліво:
abcdefg -> dbcaefg -> decabfg -> defabcg -> defgbca
Тепер запускаємо рекурсивно ту саму операцію на хвості, але з іншим m (в даному випадку – зсуваємо bca на два символи вліво). Якщо тепер акуратно реалізувати, то виходить:
void doMove(string& s, int start, int m) {
m %= (s.length() – start);
if (m == 0)
return;
int last = s.length() – m;
for (int i = start; i < last; i++)
swap(s[i], s[i + m]);
doMove(s, last, m – ((i – start) % m));
}
На д/з лишаємо доведення того, що час виконання буде лінійним.
ПС
через те, що траплятиметься забагато вкладених викликів методу, але цей самий метод можна легко переписати ітеративно, а не рекурсивно.
Дана реалізація, насправді, теоретично може жерти лінійну пам’ять, якщо підібрати правильні Н та М (питання – які?
2 mdm
>> Тогда нужно с начала строки и до shift-1 копировать символы в буфер размером kбайт, затем сдвигать всю строку влево на k байт и символы из буфера копировать в конец строки.
Так а що робити, якщо вони не влізуть в буфер розміром к байт, бо к менше, ніж shift?
void doMove(string& s, int start, int m) {
m %= (s.length() - start);
if (m == 0)
return;
int last = s.length() - m;
for (int i = start; i < last; i++)
swap(s[i], s[i + m]);
doMove(s, last, m - ((i - start) % m));
}
void doMove(string& s, int start, int m) {
m %= (s.length() - start);
if (m == 0)
return;
int last = s.length() - m;
for (int i = start; i < last; i++)
swap(s[i], s[i + m]);
doMove(s, last, m - ((i - start) % m));
}
>> Кстати, чтобы код был секси, надо заключать его в теги pre+code
Щось ніяк не виходить.
Пока m < n(i)/2, меняем местами первые и последние m символов подстроки s(i). Это требует у нас m операций swap.
s(0) = s
s(i) = substr(s, m)
Таких замен нам понадобится выполнить n/m-1. Т.е., в общем, n-m замен.
Послдений сдвиг будет, когда m = n(i).
Короче, в целом, нам нужно < n-m+m+1 = n+1 замен и 1 байт дополнительной памяти.
Забыл дописать, что когда m становится больше n(i), делаем сдвиг только уже в обратную сторону на n(i)-m.
@4, не поможет ли
code { white-space: pre }? Если это портит малину для кода внутри строки, то можно добавлятьpreавтоматически если внутриcodeесть переносы строки. Ану орлы, бегом задачку решите, не только ж байты переставлять. =))char *shiftStr(char *str, size_t m, size_t n)
{
size_t i, j;
size_t guard = 0;
if (m > n)
m %= n;
for (i = 0; i < m && guard < n; ++i) {
char tmp = str[i];
for (j = i+m; j != i && guard < n;) {
char tmp_inner = str[j];
str[j] = tmp;
tmp = tmp_inner;
j = (j + m < n ? j + m : m - (n - j));
++guard;
}
str[j] = tmp;
++guard;
}
return str;
}
Автар, либо показывай красивое решение, либо получаешь одну звезду. И вопрос как для собеседование плоховат, если не знать сразу со всеми подводными камнями не напишеш…
2 Vlad
Условие if (m > n) избыточно.
Сдвиг вправо для C#:
public static string Shift(string s, int m)
{
char[] input = s.ToCharArray();
int n = s.Length;
int k = [Наибольший общий делитель](n, m);
int count = n / k;
for (int shift = 0; shift < k; shift++)
{
char old = input[shift];
for (int index = 1; index < count; index++)
{
int currentIndex = (shift + index * m) % n;
char tmp = input[currentIndex];
input[currentIndex] = old;
old = tmp;
}
input[shift] = old;
}
return new string(input);
}
Опоздал, Vlad уже опубликовал
2 Vlad
А що твій код робить? Можеш словами пояснити?
2 1mdm
if (m < n) это защита от дурака. Много сэкономим если кто-то решит сдвинуть 100-символьную строку на 876345 символов
if (m > n) m %= n;
еквівалентно
m %= n;
Принаймні при додатніх m
2 Pro100Oleh
> int k = [Наибольший общий делитель](n, m);
Может я что-то забыл, но нахождение GCD вроде как в лучшем случае O(log n), тоесть Ваш алгоритм вобщем – O(n log n). Правда ума не приложу зачем Вам GCD…
O(n + log n) конечно же. Можно отбросить логарифм, как некоторое число, значительно меньшее чем собственно сдвиг линейной сложности, но все же ума не приложу зачем ждесь GCD
2 Vlad
Він розбиває перестановку букв на незалежні циклічні перестановки, і переставляє кожну таку циклічну перестановку окремо (красиво, до речі, вийшло
void doMove(string& s, int start, int m) {
m %= (s.length() - start);
if (m == 0)
return;
int last = s.length() - m;
for (int i = start; i < last; i++)
swap(s[i], s[i + m]);
doMove(s, last, m - ((i - start) % m));
}
Вас не смущает, что переменная i используется за пределами ее области видимости?
2 Влад
А, вірно, треба замінити на
doMove(s, last, m – ((i – start) % m));
на
doMove(s, last, m – ((last – start) % m));
Хоча в сьомій студії таке працювало, коли я тестува (змінна і зберігає значення, якого вона набула в циклі, а з областями видимості у них проблеми)
Для кожного елемента(на позиції i) копіюємо його в j =((i+m) mod n), а елемент який був на цьому місці запам’ятовуємо і вставляємо його в позицію яку обраховуємо за тою ж формулою де i:=j(присвоюємо), якщо ж попадаємо на клітинку де вже забрали елемент і ще нічого не поставили, то i:=(i+1)mod n.
Позиції з яких забрали елемент і ще не поставили можна просто очищати.
>Хоча в сьомій студії таке працювало, коли я тестува (змінна і зберігає значення, якого вона набула в циклі, а з областями видимості у них проблеми)
А если между циклом и рекурсивным вызовом добавить еще какой-нибудь вызов процедуры, что-бы перезаписать эту область стека все равно работать будет? Не имею возможности в Линуксе проверить это в какой либо из студий…
Маленька поправка, якщо m і n взаємно прості, то получиться лінійний час, в іншому випадку мабіть трохи більше.
2 Влад
Не знаю, думаю, що просто глюки з областями видимості.
Вот версия без вложенных циклов и рекурсий
void move(std::string& str, int n)
{
const int m=str.length();
int pos=0, start=0;
char ch=str[0];
for(int i=0;i<m;i++)
{
pos=(pos+n)%m;
std::swap(str[pos], ch);
if(pos==start)
{
pos=start+=1;
ch=str[start];
}
}
}
Правда у Vladа алгоритм тоже вроде как линейный. По крайней мере количество перестановок при любом n одинаково.
Евгений, Ваш компилятор не ругается на всякие “const int m=str.length();”?
Если количество перестановок было одинаково при любом n, то алгоритм был бы с константной сложностью а не линейной
Я имел ввиду, что количество обменов зависит от длины строки, а не от велечины сдвига.
А чем конструкция “const int m=str.length();” плоха? Я специально ее и вводил, чтобы если ненароком захочу изменить m, то компилятор выдал бы мне предупреждение. Стараюсь стремиться к безопасному программированию так сказать…
Vlad, а Ваш варнинг выдал?
Евгений, для Вас есть ЛегкийВопросНаСобеседовании
Даже 2. Результат какого типа возращиет std::string::length() и на каких системах int не совпадает по размерам с этим типом?
Ага, возвращает std::string::size_type или size_t. Исправлюсь.
А по второму вопросу, анализ хидерных файлов студии показал что это тип unsigned. Как по ГОСТУ, я к сожалению не знаю
Остання спроба _http://img57.imageshack.us/img57/8567/codewh0.png
при буфере в 1 char, время выполнения = O(n-(m/2)):
public static void main(String[] args) {
char[] str = {'0','1','2','3','4','5','6','7','8','9'};
int n = str.length;
int m=4;
if (n/2>=m) {
for(int i=0;i=0;i--){
swap(str,i,((n-m)+(i%m)));
}
}
System.err.println(Arrays.toString(str));
}
static void swap(char[] str, int i1, int i2 ){
char t = str[i1];
str[i1] = str[i2];
str[i2] = t;
}
кудато else прапало при посте
} else {
m = n-m;
for(int i=n-(m/2)-1;i>=0;i--){
swap(str,i,((n-m)+(i%m)));
}
}
Ну, наверное ниче нового не внесу, но как еще один вариант можно рассмотреть.
Идея
1) сдвиг на m равносилен сдвигу на m%n
2) сдвигать можно в стиле:
Идейно цикл:
запомнить то, на чем сейчас, перейти на m%n символов влево/вправо, влупить туда то, что запомнил, перед этим запомнить то, что там было.
Но тут появляются приколы. Решение математикой.
Если m и n не взаимопростые, то цикл пройдется не по всем елементам, а по классу одинаковых остатков стартового символа.
Для этого (не вычисляя никаких НСД/НСК) мы просто итерируем все классы одинаковы х остатков. Можно начинать с 0,потом 1,…и так пока не переитерируем все символы, используя каунтер уже сдвинутиых символов. Можно было б вычислить шаги сразу – но нет смысла,т.к там надо будет НСК\НСД…
Ну вот такое решение на JAVA. Влом было красиво оформлять с параметрами…
char s[] = "asdasfmnsbd sdf".toCharArray();
int n = s.length;
int m = 3;
int count = 0;
int j = 0,i;
char dop,tmp;
// пока не обработали все
while (count<n)
{
i=j;
dop = s[i];
do
{
tmp = s[(n+i-m%n)%n];
s[(n+i-m%n)%n] = dop;
i=(n+i-m%n)%n;
dop = tmp;
count++;
}
while (i!=j); // пока не пришли на начало цикла
j++; // увеличиваем остаток рассматриваемого класса
}
System.out.println(s);
Мда… Александру накидали тут кусков кода. Поди разберись чей как работает
Вы слишком усложняете.
Сдвиг влево на М символов есть перестановка местами двух подстрок из М и N-M символов.
Перестановка без дополнительной памяти делается следующим образом:
АБЦД1234567 -> ДЦБА1234567 -> ДЦБА7654321 -> 1234567АБЦД
Как все уже догадались, на каждом шаге мы разворачиваем некоторую подстроку задом наперед.
Вот мы и свели задачу к предыдущей – как обратить строку за линейное время без доп.памяти уже бурно обсуждалась при трудоустройстве в стартапы.
Так-то.
Правильный ответ:
для правильного ответа 2n перестановок– медлено.