Функция циклического сдвига массива

@obozhdi · 26.06.2013, 21:13. **Показов** 51620. **Ответов** 50

Студворк — интернет-сервис помощи студентам

Доброго времени суток,

есть задача - нужно написать функцию, которая сдвигает массив array[] размером size на shift элементов.
соответственно, чтобы двигать вправо shift больше нуля, а влево наоборот.

под буфер в цикле нельзя выделять целый массив, можно только одну переменную, тоесть нужно максимально оптимизировать использование памяти.
сложность алгоритма не должна превышать O(N).

не пишите пожалуйста код, помогите с логикой задачи.

Раньше я делал вот так -

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
 
void arrayShift(int array[], int size, int shift) {
    int temp[size];
    int i;
    
    for ( i = 0; i < size; i++ ) {
        temp[( i + shift ) % size] = array[i];
    }
    
    for (i = 0; i < size; i++) {
        array[i] = temp[i];
    }
}

но требованиям задачи это не отвечало, сейчас ищу более оптимальный вариант.

ткните носом в ошибки меня говнокодера.

спасибо (-:

ValeryS · 30.06.2013, 11:41

Сообщение от Thinker

while (a && b)
...

ну я же уже написал что ступил

@Thinker · 30.06.2013, 11:46

Сообщение от ValeryS

но проход то в половину массива (ну из за того что пары чисел)

смотри: мы доходим до половины массива и на каждом шаге обращаемся к a[i] и a[N-1-i], вот если бы только к a[i], то это полмассива, а так целый массив

Добавлено через 2 минуты
чтобы понятнее было: представь, что цикла нет и мы напишем a[0], a[1],...,a[N-1]. сколько раз мы по массиву прошлись?

@_Faeton_ · 30.06.2013, 19:20

Thinker посмотрите пожалуйста внимательней. Ваш алгоритм больше осуществляет перестановок чем мой и плюс 3 цикла против одного в моём алгоритме

Добавлено через 4 минуты
пример:
1 количество 6 сдвиг 2. У меня 4 прохода по два присваивания есть 8. В вашем алгоритме также 8 присваиваний.
2 количество 6 сдвиг 3. У меня 3 прохода по два присваивания есть 6. В вашем алгоритме 9 присваиваний.

Добавлено через 5 минут
Конечно можно сделать, чтобы количество перестановок ровнялось количеству элементов, но он будет либо громоздкий(внешние ветвления) либо тормознутый (ветвления в цикле, что есть зло).

Добавлено через 1 минуту
хотя попробую

@Thinker · 30.06.2013, 19:24

Сообщение от _Faeton_

Thinker посмотрите пожалуйста внимательней. Ваш алгоритм больше осуществляет перестановок чем мой и плюс 3 цикла против одного в моём алгоритме

какой из ваших алгоритмов мне посмотреть?
3 цикла ничего не говорят, главное, каждый элемент "трогаем" ровно один раз.
о каких перестановках речь? мы говорим на разных языках. с теорией сложности знакомы? оцените сложность вашего алгоритма по обращений к элементам массива относительно размерности массива. я бы сам оценил, просто не пойму где этот ваш алгоритм.
да, мне больше всего понравился алгоритм от ValeryS, он бесспорно очень изящен. и все же интересны еще и скоростные характеристики.

@_Faeton_ · 30.06.2013, 19:39

Вообще то код я приводил только один раз в посте 37 (до этого привёл принцип с комментарием, что идея должна быть понятна.)
Ну и главное, если вы умеете писать такие сложные слова то по идее без моей помощи должны убедиться в моих словах

Добавлено через 1 минуту
Повторюсь: ваш алгоритм больше осуществляет перестановок (имею ввиду присваивание значения ячейке массива) чем мой и плюс 3 цикла против одного в моём алгоритме

Добавлено через 9 минут
Кстати, раз такие серьёзные слова знаете, то по идее должны также знать, что вложенные циклы довольно негативно сказываются на производительности

@Thinker · 30.06.2013, 19:51

Сообщение от _Faeton_

Вообще то код я приводил только один раз в посте 37 (до этого привёл принцип с комментарием, что идея должна быть понятна.)

да, нашел, извиняюсь за невнимательность мою.

Сообщение от _Faeton_

Повторюсь: ваш алгоритм больше осуществляет перестановок (имею ввиду присваивание значения ячейке массива) чем мой и плюс 3 цикла против одного в моём алгоритме

по поводу присваиваний, то у вас используется буфер, так что их больше получается. а по поводу моего алгоритма, то писал его давно, не расценивайте его серьезно, но присваивания используются экономно.

Добавлено через 1 минуту

Сообщение от _Faeton_

вложенные циклы довольно негативно сказываются на производительности

знаю, поэтому свой старый алгоритм зря выложил. надо придумать что-то новое, но ваш алгоритм мне понравился

Добавлено через 6 минут
_Faeton_, идея у вас хорошая, но все же он не оптимален. рассмотрите случай shift = 1. тут уже можно не пары менять, а сразу ставить элементы на свои места, предварительно запомнив в буфере последний элемент.

@_Faeton_ · 30.06.2013, 19:54

не успел написать)))))

Добавлено через 18 секунд
1. Количество обращений к буферу не ограничено условием
ну а в целом я посмотрел и выяснил, что ваш и мой алгоритм (с учётом обращению к буферу) одинаковое количество обращений, НО при различных сочетаниях shit и количества элементов

Добавлено через 1 минуту
т. е . при разных сочетаниях имеют экстремумы... Так, что остаётся сравнивать только лёгкость восприятия и оптимизация кода (типа вложенных циклов)

Добавлено через 31 секунду
т.е. где-то мой выигрывает где-то ваш

@Thinker · 30.06.2013, 19:57

Сообщение от _Faeton_

т.е. где-то мой выигрывает где-то ваш

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

и все же, случай, например, с shift = 1 показывает, что, возможно, имеется еще более быстрый универсальный алгоритм

ValeryS · 08.07.2013, 09:29

заинтересовала меня идея сдвиг массива за один проход
и вот что я надумал
Выношу на суд общественности

для примера рассмотрим сдвиг вправо
например массив
1234567
нужно сдвинуть на 3 вправо
должно получится
5671234
т.е видно что последние элементы нужно поместить на место первых

меняем
0) 1234567
1) 5674123

т.е. остается массив 4123 который тоже нужно сдвинуть на 3 элемента
на лицо рекурсия

и еще одно допущение сдвиг на размер массива равен отсутствие сдвига

вот такая функция получилась

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void MyROR(int *arr,//адрес массива
             int size,// размер
            int ofset)//величина сдвига
 {
ofset%=size; // сделано на случай если сдвиг больше размера массива
if(ofset==0)// если сдвиг равен размеру
   return; // выходим сдвиг не нужен
for(int i=0;i<ofset;i++) // цикл перестановки
   {
    int tmp=arr[i];
    arr[i]=arr[size-ofset+i];
    arr[size-ofset+i]=tmp; 
   }
MyROR(arr+ofset,size-ofset,ofset);// сдвиг остатков массива
}

обидно будет если алгоритм уже кто то реализовал

зря думал

@Thinker · 08.07.2013, 13:03

ValeryS, хорошая идея. у _Faeton_ тоже перестановка за один проход
https://www.cyberforum.ru/post4788988.html

ValeryS · 08.07.2013, 13:49

Сообщение от Thinker

у _Faeton_ тоже перестановка за один проход

честно говоря это он и сподвигнул меня что то изобретать
у него были ошибки которые я указал и начал думать как их избежать
а пост который ты указал я как то не заметил

ну может и хорошо иначе бы думать не стал

Новые блоги и статьи Все статьи Все блоги /
Модель здравосохранения 17. Планы на выгорание anaschu 23.05.2026 Вот конкретная схема реализации: В классе Работник добавить: накопленнаяУсталость — растёт каждый час работы, снижается в перерывы и болезни коэффициентПрезентеизма — снижает продуктивность. . .	Изменение цветов в палитре gif файла aka фавикона russiannick 23.05.2026 Изменение цветов в палитре gif файла, юзаемого как фавиконка в составе html-файла, помещенная в base64, средствами нативного Java Script, навеянное сном в майский день. Для работы необходим браузер,. . .	Модель здравосохранения 16. Слишком хорошие и здоровые сотрудники уходят, недовольные зарплатой anaschu 23.05.2026 Отладка увольнений и настройка производительности Сегодня во второй половине дня разобрались с механикой увольнений и настроили коэффициент сложности заданий. Вот что было сделано. . . .	Как я стал коммунистом))) Модель сохранения здоровья сотрудников, запись блога номер 15 anaschu 23.05.2026 Внезапно хорошее здоровье сотрудников не нужно капиталистам?))
Модель здравоСохранения 15. Как мы чинили AnyLogic модель рабочего коллектива: сочленение диаграммы состояний болезней и поломок в ресурспул anaschu 23.05.2026 Как мы чинили AnyLogic модель рабочего коллектива Сегодня разобрались с пятью багами, из-за которых модель либо падала с ошибкой, либо давала совершенно бессмысленные результаты. Каждый баг был. . .	Диалоги с ИИ zorxor 23.05.2026 Насколько я понимаю - Вы - Искусственный Интеллект. Это так? Да, всё верно. Я — искусственный интеллект. Я представляю собой большую языковую модель, созданную для помощи в самых разных задачах. . . .	Модель здравосохранения 14. Собираем всю модель вместе. anaschu 22.05.2026 Модель собрана. В будущих постах на видео я покажу, как она работает. В этом посте запускаем её, проверяем результаты и разбираем что можно с ней делать дальше. Перед запуском проверяем. . .	Модель здравоохранения 13. Добавление самой системы здравоохранения. anaschu 22.05.2026 В предыдущем посте мы настроили болезни. Теперь добавим события, которые управляют здоровьем всего коллектива, а также настроим рабочий график и расчёт финансов. В Main создаём четыре события. . . .

@_Faeton_ 6 / 6 / 0 Регистрация: 28.06.2013 Сообщений: 15
	30.06.2013, 19:20
	Thinker посмотрите пожалуйста внимательней. Ваш алгоритм больше осуществляет перестановок чем мой и плюс 3 цикла против одного в моём алгоритме Добавлено через 4 минуты пример: 1 количество 6 сдвиг 2. У меня 4 прохода по два присваивания есть 8. В вашем алгоритме также 8 присваиваний. 2 количество 6 сдвиг 3. У меня 3 прохода по два присваивания есть 6. В вашем алгоритме 9 присваиваний. Добавлено через 5 минут Конечно можно сделать, чтобы количество перестановок ровнялось количеству элементов, но он будет либо громоздкий(внешние ветвления) либо тормознутый (ветвления в цикле, что есть зло). Добавлено через 1 минуту хотя попробую 0

@_Faeton_ 6 / 6 / 0 Регистрация: 28.06.2013 Сообщений: 15
	30.06.2013, 19:39
	Вообще то код я приводил только один раз в посте 37 (до этого привёл принцип с комментарием, что идея должна быть понятна.) Ну и главное, если вы умеете писать такие сложные слова то по идее без моей помощи должны убедиться в моих словах Добавлено через 1 минуту Повторюсь: ваш алгоритм больше осуществляет перестановок (имею ввиду присваивание значения ячейке массива) чем мой и плюс 3 цикла против одного в моём алгоритме Добавлено через 9 минут Кстати, раз такие серьёзные слова знаете, то по идее должны также знать, что вложенные циклы довольно негативно сказываются на производительности 0

@_Faeton_ 6 / 6 / 0 Регистрация: 28.06.2013 Сообщений: 15
	30.06.2013, 19:54
	не успел написать))))) Добавлено через 18 секунд 1. Количество обращений к буферу не ограничено условием ну а в целом я посмотрел и выяснил, что ваш и мой алгоритм (с учётом обращению к буферу) одинаковое количество обращений, НО при различных сочетаниях shit и количества элементов Добавлено через 1 минуту т. е . при разных сочетаниях имеют экстремумы... Так, что остаётся сравнивать только лёгкость восприятия и оптимизация кода (типа вложенных циклов) Добавлено через 31 секунду т.е. где-то мой выигрывает где-то ваш 1

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	08.07.2013, 13:03
	ValeryS, хорошая идея. у _Faeton_ тоже перестановка за один проход https://www.cyberforum.ru/post4788988.html 0