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

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

26.06.2013, 21:13. Просмотров 19850. Ответов 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)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.06.2013, 21:13
Ответы с готовыми решениями:

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

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

Ошибка в коде сдвига элементов массива
не пойму,почему выводит ошибку #include&lt;stdio.h&gt; #include&lt;conio.h&gt; #define N 6 int...

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

50
Модератор
Эксперт Python
26641 / 13893 / 2641
Регистрация: 12.02.2012
Сообщений: 22,776
Записей в блоге: 1
26.06.2013, 21:28 2
Цитата Сообщение от obozhdi Посмотреть сообщение
под буфер в цикле нельзя выделять целый массив
- а что такое int temp[size]?

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

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

в функцию передаются 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
26641 / 13893 / 2641
Регистрация: 12.02.2012
Сообщений: 22,776
Записей в блоге: 1
26.06.2013, 21:33 4
Цитата Сообщение от obozhdi Посмотреть сообщение
сдвиг массива циклический
- а, это меняет дело!..
0
Модератор
Эксперт по электронике
8228 / 6095 / 814
Регистрация: 14.02.2011
Сообщений: 21,158
26.06.2013, 21:40 5
Лучший ответ Сообщение было отмечено как решение

Решение

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

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

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

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

для сдвига в другую сторону делаем действия относительно последнего элемента
0
Модератор
Эксперт по электронике
8228 / 6095 / 814
Регистрация: 14.02.2011
Сообщений: 21,158
26.06.2013, 22:07 8
вот примерный код
учти не проверял пишу на коленке

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
404 / 223 / 43
Регистрация: 10.02.2013
Сообщений: 780
26.06.2013, 22:08 9
Цитата Сообщение от ValeryS Посмотреть сообщение

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

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

я знаю что в моем случае места в памяти меньше занимать будет
0
Модератор
Эксперт по электронике
8228 / 6095 / 814
Регистрация: 14.02.2011
Сообщений: 21,158
26.06.2013, 22:10 10
Цитата Сообщение от shurikspk Посмотреть сообщение
я знаю что в моем случае места в памяти меньше занимать будет
серьезно
посмотри на мою реализацию
столько же сколько у тебя
размер массива плюс одна переменная
а во второй реализации вообще размер массива
0
404 / 223 / 43
Регистрация: 10.02.2013
Сообщений: 780
26.06.2013, 22:12 11
ну вторую реализацию ты позже добавил, а я не видел
0
Модератор
Эксперт по электронике
8228 / 6095 / 814
Регистрация: 14.02.2011
Сообщений: 21,158
26.06.2013, 22:18 12
Цитата Сообщение от shurikspk Посмотреть сообщение
ну вторую реализацию ты позже добавил,
а я вообще не хотел её добавлять
думал уже все знают
как поменять две переменных не используя третью
так же можно через + -

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

это всегда антогонизм или скорость или память
если и то и другое нужно иши другие пути
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
10837 / 6647 / 1614
Регистрация: 25.07.2009
Сообщений: 12,424
27.06.2013, 04:44 13

Не по теме:

Искренне надеюсь, что преподы, запрещающие использовать стандартную библиотеку, после смерти попадают в ад, в котором целую вечность переписывают реализацию этой самой 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
Модератор
Эксперт по электронике
8228 / 6095 / 814
Регистрация: 14.02.2011
Сообщений: 21,158
27.06.2013, 09:21 14
@easybudda,
а как поведет себя прога если steps>count???
неправомерный доступ получим
да и еще рекурсия
какая нагрузка на машину( стек то он все таки не резиновый)
и memmove внутри себя содержит тот же цикл
оптимизированный правда, но для int эта оптимизация теряется

Добавлено через 3 минуты
пардон
первое возражение снимается,
чей то я ступил
все будет в пределах массива
0
Модератор
Эксперт Python
26641 / 13893 / 2641
Регистрация: 12.02.2012
Сообщений: 22,776
Записей в блоге: 1
27.06.2013, 09:50 15
@ValeryS, Ваш подход остроумен!
0
Модератор
Эксперт по электронике
8228 / 6095 / 814
Регистрация: 14.02.2011
Сообщений: 21,158
27.06.2013, 10:31 16
Цитата Сообщение от Catstail Посмотреть сообщение
Ваш подход остроумен!
Если честно, не совсем мой
прочитал где то, давным давно в алгоритмах,в какой то книге
там еще пример наглядный приводился на пальцах
для удобства взят массив на 10 и сдвиг на 5
разворачиваешь левый кулак потом правый кулак и потом меняешь кулаки местами
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
10837 / 6647 / 1614
Регистрация: 25.07.2009
Сообщений: 12,424
27.06.2013, 11:35 17
Цитата Сообщение от 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
95 / 95 / 58
Регистрация: 04.10.2012
Сообщений: 189
27.06.2013, 17:51 18
@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 19
Я расцениваю это как задачу на логику, т.е. задача не максимальная производительность
, а использование одной ячейки памяти. Поэтому, думаю подойдёт следующий алгоритм(на примере 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
Модератор
Эксперт по электронике
8228 / 6095 / 814
Регистрация: 14.02.2011
Сообщений: 21,158
28.06.2013, 12:53 20
Цитата Сообщение от _Faeton_ Посмотреть сообщение
итого 4 перестановки.
теперь возми смешение на 3
и размер массива этак 100
сколько будет перестановок
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.06.2013, 12:53

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.