Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.87/245: Рейтинг темы: голосов - 245, средняя оценка - 4.87
Заблокирован

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

26.06.2013, 21:13. Показов 51249. Ответов 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];
    }
}
но требованиям задачи это не отвечало, сейчас ищу более оптимальный вариант.

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

спасибо (-:
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
26.06.2013, 21:13
Ответы с готовыми решениями:

Функция Циклического сдвига
Уже несколько дней мучаюсь никак не могу организовать функции циклического сдвига. Необходимо выполнить циклический сдвиг в квадратной...

Функция циклического сдвига строк и колонок в матрице
Нужно написать функцию циклического сдвига строк и колонок в матрице. Короче, пока ждал ответа, вроде сделал все: void...

Ошибка в коде сдвига элементов массива
не пойму,почему выводит ошибку #include&lt;stdio.h&gt; #include&lt;conio.h&gt; #define N 6 int main(void) {int arr, i, j, y, p; ...

50
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38173 / 21108 / 4307
Регистрация: 12.02.2012
Сообщений: 34,708
Записей в блоге: 14
26.06.2013, 21:28
Цитата Сообщение от obozhdi Посмотреть сообщение
под буфер в цикле нельзя выделять целый массив
- а что такое int temp[size]?

Вообще подобные задачи умиляют... Сдвинуть массив. Массив имеет фиксированные размеры. Куда девать элементы, которые "выходят за пределы"? И чем заполнять освобожающееся место?

Цитата Сообщение от obozhdi Посмотреть сообщение
сложность алгоритма не должна превышать O(N).
- да с какого перепуга она должна превышать O(N)? Чтобы превысила - надо сильно постараться...
0
Заблокирован
26.06.2013, 21:31  [ТС]
я наверное криво описал по неопытности.

в функцию передаются array[] - массив
int size - расмер массива
int shift - размер сдвига

сдвиг массива циклический ->
int size = 6
array[size] = {1,2,3,4,5,6}
int shift = 2
сдвиг на 2 вправо -> на выходе должно быть
array[size] = {5,6,1,2,3,4}
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38173 / 21108 / 4307
Регистрация: 12.02.2012
Сообщений: 34,708
Записей в блоге: 14
26.06.2013, 21:33
Цитата Сообщение от obozhdi Посмотреть сообщение
сдвиг массива циклический
- а, это меняет дело!..
0
Модератор
Эксперт по электронике
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,868
26.06.2013, 21:40
Лучший ответ Сообщение было отмечено как решение

Решение

я уже описывал как то алгоритм циклического сдвига массива
код поищи на форуме
а словами он выглядит так
1 переворачиваем одну часть массива
2 переворачиваем другую часть массива
3 переворачиваем весь массив

например массив
123456789
нужно сдвинуть на три элемента влево
0) 123456789
1) 321456789
2) 321987654
3) 456789123

на три вправо
0) 123456789
1) 123456987
2) 654321987
3) 789123456
6
Заблокирован
26.06.2013, 21:41  [ТС]
так я не думал.
спасибо, буду пробовать так.
0
 Аватар для shurikspk
409 / 228 / 43
Регистрация: 10.02.2013
Сообщений: 780
26.06.2013, 21:51
я б делал так:
1. нулевой элемент в временную переменную
2. и в циклу двигать элементы на место 0, 1,2 ну и тд.
3. в последний принудительно запишем с временной переменной число.

поместив в цикл можно сдвинуть на сколько угодно позиций

для сдвига в другую сторону делаем действия относительно последнего элемента
0
Модератор
Эксперт по электронике
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,868
26.06.2013, 22:07
вот примерный код
учти не проверял пишу на коленке

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void Reverse(int * arr, int sz)
{
for(int i=0;i<sz;i++)
   {
      int tmp=arr[i];
      arr[i]=arr[sz- i-1];
      arr[sz- i-1]=tmp;
   }
 
}
 
void MyROL( int * arr,  // адрес массива
                  int  ofset, // на сколько смещаем
                  int  sizeArray) // размер массива
{
 Reverse(arr,ofset);
  Reverse(&arr[ofset],sizeArray-ofset;
 Reverse(arr,sizeArray);
 
 
}
 
 
...................................
int myArr[]={1,2,3,4,5,6,7,8,9};
 
MyROL(myArr,3,sizeof(myArr));
преимущество в том, что на сколько не сдвигай массив все равно будет один проход по массиву
здесь нет сдвига вправо и нет проверки если смещение больше чем размер
но это не сложно добавить
Цитата Сообщение от obozhdi Посмотреть сообщение
спасибо, буду пробовать так.
для "спасибы" кнопка есть

Добавлено через 2 минуты
Цитата Сообщение от shurikspk Посмотреть сообщение
я б делал так:
сколько раз пробежишь по массиву при сдвиге допустим 5???
тогда уж так
первые пять элементов во временный массив
остатки сдвигаешь в начало
из временного записываешь
в конец

Добавлено через 4 минуты
Цитата Сообщение от ValeryS Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
void Reverse(int * arr, int sz)
{
for(int i=0;i<sz;i++)
 {
   int tmp=arr[i];
   arr[i]=arr[sz-i-1];
   arr[sz-i-1]=tmp;
   }
}
тоже без использования временной переменной
C++
1
2
3
4
5
6
7
8
9
void Reverse(int * arr, int sz)
{
  for(int i=0;i<sz;i++)
  {
    arr[i]^=arr[sz-i-1];
    arr[sz-i-1]^=arr[i];
    arr[i]^=arr[sz-i-1];
  }
}
1
 Аватар для shurikspk
409 / 228 / 43
Регистрация: 10.02.2013
Сообщений: 780
26.06.2013, 22:08
Цитата Сообщение от ValeryS Посмотреть сообщение

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

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

я знаю что в моем случае места в памяти меньше занимать будет
0
Модератор
Эксперт по электронике
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,868
26.06.2013, 22:10
Цитата Сообщение от shurikspk Посмотреть сообщение
я знаю что в моем случае места в памяти меньше занимать будет
серьезно
посмотри на мою реализацию
столько же сколько у тебя
размер массива плюс одна переменная
а во второй реализации вообще размер массива
0
 Аватар для shurikspk
409 / 228 / 43
Регистрация: 10.02.2013
Сообщений: 780
26.06.2013, 22:12
ну вторую реализацию ты позже добавил, а я не видел
0
Модератор
Эксперт по электронике
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,868
26.06.2013, 22:18
Цитата Сообщение от shurikspk Посмотреть сообщение
ну вторую реализацию ты позже добавил,
а я вообще не хотел её добавлять
думал уже все знают
как поменять две переменных не используя третью
так же можно через + -

C++
1
2
3
a+=b;
b=a-b;
a=a-b;
а насчет памяти

это всегда антогонизм или скорость или память
если и то и другое нужно иши другие пути
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
 Аватар для easybudda
12843 / 7592 / 1766
Регистрация: 25.07.2009
Сообщений: 13,973
27.06.2013, 04:44

Не по теме:

Искренне надеюсь, что преподы, запрещающие использовать стандартную библиотеку, после смерти попадают в ад, в котором целую вечность переписывают реализацию этой самой libc, раз от раза всё быстрее и экономичнее... ;)


C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
#include <string.h>
 
int * rotate_array(int * array, const size_t count, const int steps) {
    if ( steps < 0 ) {
        int tmp = *array;
        memmove(array, array + 1, sizeof(int) * (count - 1));
        array[count - 1] = tmp;
        return rotate_array(array, count, steps + 1);
    }
    else if ( steps > 0 ) {
        int tmp = array[count - 1];
        memmove(array + 1, array, sizeof(int) * (count - 1));
        *array = tmp;
        return rotate_array(array, count, steps - 1);
    }
    else
        return array;
}
 
void dump(const int * array, size_t count) {
    while ( count-- )
        printf("%d%c", *array++, ( count ) ? ' ' : '\n');
}
 
#define SIZE (10)
 
int main(void) {
    int arr[SIZE] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    
    dump(arr, SIZE);
    
    /* три шаги налево */
    dump(rotate_array(arr, SIZE, -3), SIZE);
    /* две шаги направо */
    dump(rotate_array(arr, SIZE, 2), SIZE);
    /* шаг вперёд */
    dump(rotate_array(arr, SIZE, -1), SIZE);
    /* и две назад */
    dump(rotate_array(arr, SIZE, 2), SIZE);
    /* (c) Одесский фольклёр */
    
    return 0;
}
0
Модератор
Эксперт по электронике
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,868
27.06.2013, 09:21
@easybudda,
а как поведет себя прога если steps>count???
неправомерный доступ получим
да и еще рекурсия
какая нагрузка на машину( стек то он все таки не резиновый)
и memmove внутри себя содержит тот же цикл
оптимизированный правда, но для int эта оптимизация теряется

Добавлено через 3 минуты
пардон
первое возражение снимается,
чей то я ступил
все будет в пределах массива
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38173 / 21108 / 4307
Регистрация: 12.02.2012
Сообщений: 34,708
Записей в блоге: 14
27.06.2013, 09:50
@ValeryS, Ваш подход остроумен!
0
Модератор
Эксперт по электронике
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,868
27.06.2013, 10:31
Цитата Сообщение от Catstail Посмотреть сообщение
Ваш подход остроумен!
Если честно, не совсем мой
прочитал где то, давным давно в алгоритмах,в какой то книге
там еще пример наглядный приводился на пальцах
для удобства взят массив на 10 и сдвиг на 5
разворачиваешь левый кулак потом правый кулак и потом меняешь кулаки местами
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
 Аватар для easybudda
12843 / 7592 / 1766
Регистрация: 25.07.2009
Сообщений: 13,973
27.06.2013, 11:35
Цитата Сообщение от ValeryS Посмотреть сообщение
да и еще рекурсия
какая нагрузка на машину( стек то он все таки не резиновый)
да не то, чтобы большая на самом деле, но не принципиально:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int * rotate_array(int * array, const size_t count, int steps) {
    while ( steps ) {
        if ( steps < 0 ) {
            int tmp = *array;
            memmove(array, array + 1, sizeof(int) * (count - 1));
            array[count - 1] = tmp;
            ++steps;
        }
        else {
            int tmp = array[count - 1];
            memmove(array + 1, array, sizeof(int) * (count - 1));
            *array = tmp;
            --steps;
        }
    }
    
    return array;
}
0
 Аватар для uburuntu
95 / 95 / 58
Регистрация: 04.10.2012
Сообщений: 189
27.06.2013, 17:51
@shurikspk, у вас идея заключается в том чтобы k раз применить функцию сдвига на 1.
Это плохая идея. У вас получается k*O(n) вместо O(n).

И небольшое замечание для тех, кто будет читать тему:
Такая перестановка переменных годится только для целого типа.
C
1
2
3
x = x ^ y;
y = x ^ y;
x = x ^ y;
0
6 / 6 / 0
Регистрация: 28.06.2013
Сообщений: 15
28.06.2013, 11:57
Я расцениваю это как задачу на логику, т.е. задача не максимальная производительность
, а использование одной ячейки памяти. Поэтому, думаю подойдёт следующий алгоритм(на примере 1,2,3,4,5,6 со сдвигом вправо на 2):
общее количество Count=6;
сдвиг Shift=2
массив значений data[6]
количество которое нужно сдвинуть Count-Shift
int nTemp; единственно доступная ячейка памяти
for(int i=Count-Shift-1; i>=0; i--)
{
nTemp=data[i+Shift];
data[i+Shift]=data[i];
data[i]=nTemp;
}
виртуальный массив (без выделения памяти) первые Count-Shift элементов.
Меняя с последнего элемента до первого (в виртуальном массиве) на элемент со смещением Shift из реального
получим циклическое смещение
начало 1,2,3,4,5,6
1,2,3,6,5,4
1,2,5,6,3,4
1,6,5,2,3,4
5,6,1,2,5,6
итого 4 перестановки.
Аналогично смещение в другую сторону. Думаю идея ясна.
0
Модератор
Эксперт по электронике
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,868
28.06.2013, 12:53
Цитата Сообщение от _Faeton_ Посмотреть сообщение
итого 4 перестановки.
теперь возми смешение на 3
и размер массива этак 100
сколько будет перестановок
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
28.06.2013, 12:53
Помогаю со студенческими работами здесь

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

Функция циклического сдвига побитово вправо
Форумчане, приветствую! Подскажите почему не работает сдвиг вправо? Программа компилируется, но сдвига не происходит. Сверился с...

Программа циклического сдвига элементов массива
Помогите!Срочно! Составить программу циклического сдвига элементов массива А(10) на 5 позиций влево.Заранее спасибо)))

Описать процедуру циклического сдвига массива
Полиморфизм.Описать процедуру MoveLeft(A,N,k)1|MoveRight(A,N,k)2, осуществляющую циклический сдвиг элементов вещественного массива A...

Ошиба циклического сдвига
Вот задание. Дана действительная квадратная матрица порядка n. 1) осуществить циклический сдвиг элементов прямоугольной матрицы на N...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Символьное дифференцирование
igorrr37 13.02.2026
/ * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru