Сучасна диджитал-освіта для дітей — безоплатне заняття в GoITeens ×
Mazda CX 5
×
👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn

Схожі статті




38 коментарів

Підписатись на коментаріВідписатись від коментарів Коментарі можуть залишати тільки користувачі з підтвердженими акаунтами.

для правильного ответа 2n перестановок— медлено.

Правильный ответ:

Определите, на каком символе от начала строки вы хотите быть после сдвига. Затем разделите строку на две части так, чтобы этот символ был первым во второй «половине» строки. Оберните каждую часть на месте, затем оберните всю результирующую строку.

Вы слишком усложняете.Сдвиг влево на М символов есть перестановка местами двух подстрок из М и N-M символов.Перестановка без дополнительной памяти делается следующим образом: АБЦД1234567 -> ДЦБА1234567 -> ДЦБА7654321 -> 1234567АБЦДКак все уже догадались, на каждом шаге мы разворачиваем некоторую подстроку задом наперед.Вот мы и свели задачу к предыдущей — как обратить строку за линейное время без доп.памяти уже бурно обсуждалась при трудоустройстве в стартапы.Так-то.

Мда... Александру накидали тут кусков кода. Поди разберись чей как работает: -)


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);

Ну, наверное ниче нового не внесу, но как еще один вариант можно рассмотреть.Идея 1) сдвиг на m равносилен сдвигу на m%n2) сдвигать можно в стиле: Идейно цикл: запомнить то, на чем сейчас, перейти на m%n символов влево/вправо, влупить туда то, что запомнил, перед этим запомнить то, что там было.Но тут появляются приколы. Решение математикой.Если m и n не взаимопростые, то цикл пройдется не по всем елементам, а по классу одинаковых остатков стартового символа.Для этого (не вычисляя никаких НСД/НСК) мы просто итерируем все классы одинаковы х остатков. Можно начинать с 0, потом 1,...и так пока не переитерируем все символы, используя каунтер уже сдвинутиых символов. Можно было б вычислить шаги сразу -, но нет смысла, т.к там надо будет НСКНСД...Ну вот такое решение на JAVA. Влом было красиво оформлять с параметрами...

кудато else прапало при посте

} else {m = n-m;for(int i=n-(m/2)-1;i>=0;i--){swap(str,i,((n-m)+(i%m)));}}

при буфере в 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; }

Ага, возвращает std: string: size_type или size_t. Исправлюсь.А по второму вопросу, анализ хидерных файлов студии показал что это тип unsigned. Как по ГОСТУ, я к сожалению не знаю

Я имел ввиду, что количество обменов зависит от длины строки, а не от велечины сдвига.А чем конструкция «const int m=str.length (); » плоха? Я специально ее и вводил, чтобы если ненароком захочу изменить m, то компилятор выдал бы мне предупреждение. Стараюсь стремиться к безопасному программированию так сказать...

Правда у Vladа алгоритм тоже вроде как линейный. По крайней мере количество перестановок при любом n одинаково.

Вот версия без вложенных циклов и рекурсий

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];}}}

2 ВладНе знаю, думаю, що просто глюки з областями видимості.

2 ВладА, вірно, треба замінити на doMove (s, last, m — ((i — start) % m)); наdoMove (s, last, m — ((last — start) % m)); Хоча в сьомій студії таке працювало, коли я тестува (змінна і зберігає значення, якого вона набула в циклі, а з областями видимості у них проблеми)

2 VladВін розбиває перестановку букв на незалежні циклічні перестановки, і переставляє кожну таку циклічну перестановку окремо (красиво, до речі, вийшло:)

Принаймні при додатніх m:)

if (m > n) m %= n; еквівалентноm %= n;

2 VladА що твій код робить? Можеш словами пояснити?

Опоздал, Vlad уже опубликовал: (

Сдвиг вправо для C#:

        public static string Shift(string s, int m)        {            char[] input = s.ToCharArray();            int n = s.Length;            int k = <a href="n, m">Наибольший общий делитель</a>;            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);        }

2 VladУсловие if (m > n) избыточно.

@4, не поможет ли

code { white-space: pre }

? Если это портит малину для кода внутри строки, то можно добавлять

pre

автоматически если внутри

code

есть переносы строки. Ану орлы, бегом задачку решите, не только ж байты переставлять. =))

>> Кстати, чтобы код был секси, надо заключать его в теги pre+codeЩось ніяк не виходить.


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));}

2 mdm>> Тогда нужно с начала строки и до shift-1 копировать символы в буфер размером kбайт, затем сдвигать всю строку влево на k байт и символы из буфера копировать в конец строки.Так, а що робити, якщо вони не влізуть в буфер розміром к байт, бо к менше, ніж shift?

Класна задача, раніше такої не бачив.Будемо вважати, що зсуваємо вліво.Яка ідея придумалась: Йдемо зліва направо, і обмінюємо символ з номером і на символ з номером і + 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 ВсеволодНаверное вы правы.Тогда уместно будет использовать XOR для перестановки соответствующих символов в строке. Время будет = O (m/k).

2 IgorО каком коде вы говорите? В первом комментарии я писал псевдокод.

А ведь-таки так! Тогда нужно с начала строки и до shift-1 копировать символы в буфер размером k байт, затем сдвигать всю строку влево на k байт и символы из буфера копировать в конец строки. Или наоборот.

2 1mdmА мне кажется что этот код не будет работать вообще

Условие «за линейное время» в моём решение соблюдено.А условие «при константной доп. памяти» решается копированием символовиз первой части строки в конец второй части с использованием фиксированногопо размеру буфера. Если буфер будет равен одному символу, то мы решаем этузадачу на O (m) времени.

В некотором смысле, эта задача есть частным случаем предыдущей.

Кстати, чтобы код был секси, надо заключать его в теги pre+code.

Задачка сама по себе не очень сложная — сделать из «колбаса» «басакол».

str = str.substr(shift) + str.substr(0, shift-1);
А вот решить ее, соблюдая ограничения — уже труднее:

при константной дополнительной памяти за линейное время

Символы «съелись». Короче, свопаем вот так: swap (start... (shift-1), shift...end), где «...» это диапазон.

Псевдокод: shift = m % n; str = str.substr (shift) + str.substr (0, shift-1); Сначала вычисляем на сколько символов нужно реально сдвинуть (если вдруг m > n), а затем меняем местами части строки: start... (shift-1) shift...end.Вроде так:)

Підписатись на коментарі