Форум программистов, компьютерный форум CyberForum.ru

Одномерный массив. Циклический сдвиг вправо - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 41, средняя оценка - 4.80
LeShu
0 / 0 / 0
Регистрация: 08.12.2012
Сообщений: 32
03.02.2013, 01:46     Одномерный массив. Циклический сдвиг вправо #1
Дан массив A размера N и целое число K (1 ≤ K ≤ 4, K < N). Осущест-
вить циклический сдвиг элементов массива вправо на K позиций (при этом
A перейдет в A , A — в A , …, A — в A ). Допускается использовать
1 K+1 2 K+2 N K
вспомогательный массив из 4 элементов.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.02.2013, 01:46     Одномерный массив. Циклический сдвиг вправо
Посмотрите здесь:

C++ Ввести одномерный целочисленный массив A, вывести его. Произвести циклический сдвиг вправо его элементов столько раз, сколько раз в массиве встречаютс
Циклический сдвиг вправо C++
C++ Дан массив размера N. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k- индекс максимального элемента.
Циклический сдвиг массива влево и вправо C++
C++ Дано одномерный массив Х, размером 15 элементов. Провести циклический сдвиг элементов в массиве вправо на 2 позиции
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tsin
 Аватар для Tsin
419 / 395 / 108
Регистрация: 30.12.2012
Сообщений: 1,085
Записей в блоге: 2
Завершенные тесты: 3
03.02.2013, 01:49     Одномерный массив. Циклический сдвиг вправо #2
LeShu, а какие-нибудь собственные попытки сделать это у Вас есть?
LeShu
0 / 0 / 0
Регистрация: 08.12.2012
Сообщений: 32
03.02.2013, 01:51  [ТС]     Одномерный массив. Циклический сдвиг вправо #3
Цитата Сообщение от Tsin Посмотреть сообщение
LeShu, а какие-нибудь собственные попытки сделать это у Вас есть?
Да вот сижу, мучаю эти задачки или они меня
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11823 / 6802 / 769
Регистрация: 27.09.2012
Сообщений: 16,870
Записей в блоге: 2
Завершенные тесты: 1
03.02.2013, 02:04     Одномерный массив. Циклический сдвиг вправо #4
ShiftR - вправо
ShiftL - влево
Shift - если shift меньше 0, то влево, иначе вправо
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
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <iomanip>
#include <ctime>
#include <cmath>
#include <memory.h>
 
int * ShiftR(int *arr,int size, int shift){
    if(shift<0) return arr;
    shift=shift%size;
    int *temp=new int[shift];
    memcpy(temp,arr+size-shift,shift*sizeof(*arr));
    memmove(arr+shift,arr,(size-shift)*sizeof(*arr));
    memcpy(arr,temp,shift*sizeof(*arr));
    delete [] temp;
    return arr;
}
 
int * ShiftL(int *arr,int size, int shift){
    if(shift<0) return arr;
    shift=shift%size;
    int *temp=new int[shift];
    memcpy(temp,arr,shift*sizeof(*arr));
    memmove(arr,arr+shift,(size-shift)*sizeof(*arr));
    memcpy(arr+size-shift,temp,shift*sizeof(*arr));
    delete [] temp;
    return arr;
}
 
 
int * Shift(int *arr,int size, int shift){
    if (shift<0) return ShiftL(arr,size,std::abs(shift));
    if (shift>0) return ShiftR(arr,size,shift);
    return arr;
}
 
int main(){
    const int size=10;
    int arr[size];
    std::srand(std::time(NULL));
    for(int i=0;i<size;++i){
        std::cout<<std::setw(3)<<(arr[i]=std::rand()%90+10);
    }
    std::cout<<std::endl;
 
    ShiftL(arr,size,1);
    ShiftR(arr,size,2);
 
    Shift(arr,size,-1);
    Shift(arr,size,2);
 
    for(int i=0;i<size;++i){
        std::cout<<std::setw(3)<<arr[i];
    }   
    std::cin.get();
    return 0;
}
ValeryS
Модератор
6375 / 4841 / 443
Регистрация: 14.02.2011
Сообщений: 16,045
03.02.2013, 02:16     Одномерный массив. Циклический сдвиг вправо #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
есть одно интересное решение приводить пока не буду
расскажу принцип для того чтобы циклически сдвинуть массив надо сначала
перевернуть правую часть
потом левую часть
потом весь массив
12345678
надо сдвинуть на три элемента влево
1-32145678
2-32187654
3-45678123
надо сдвинуть на три элемента вправо
1 54321678
2 54321876
3 67812345

Добавлено через 56 секунд
никакой дополнительной памяти все делается в этом же массиве
DESergik
1 / 1 / 0
Регистрация: 26.12.2012
Сообщений: 17
10.02.2013, 16:13     Одномерный массив. Циклический сдвиг вправо #6
Написал реализацию циклического сдвига в обе стороны по способу ув. ValeryS. Буду благодарен за комментарии и исправления
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <iostream>
#include <locale>
 
using namespace std;
 
const int size=8; //Задание величины массива
int const sdvig_size(); //Функция для задания величины сдвига
void sdvig_f(int a, int b, int usl, int center, int *mass2); //Функция, меняющая местами части массива
void buffer(int &mass_i, int &mass_j); //Функция, меняющая местами заданные элементы массива
void print(int *mass2); //Функция вывода всего массива на экран
 
int main()
{
    setlocale(LC_ALL,"Russian");
    cout<<"-->Программа сдвига массива вправо или влево на заданную величину<--"<<endl;
 
    //Задание исходного массива и его вывод на экран:
    int mass[size]={1, 2, 3, 4, 5, 6, 7, 8};
    int i, j;
    cout<<endl<<"Исходный массив:"<<endl;
    print(mass);
 
    //Создание управляющего меню
    int option;
    cout<<endl<<"В какую сторону будем сдвигать массив?"<<endl;
    cout<<"1. Влево"<<endl;
    cout<<"2. Вправо"<<endl;
    do
    {
        cout<<endl<<"Введите нужный вариант: ";
        cin>>option;
    }
    while (option<1 || option>2); //Пока пользователь не нажмёт цифру от 1 до 2 программа дальше работать не будет
 
    switch (option)
    {
    case 1:
        {
            //Задаем сдвиг:
            const int sdvig=sdvig_size();
            //1) Переворачиваем левую часть:
            sdvig_f(0, (sdvig-1), (sdvig/2), sdvig%2, mass);
            cout<<"Переворот левой части:"<<endl;
            print(mass);
            
            //2) Переворачиваем правую часть:
            sdvig_f(sdvig, (size-1), (sdvig+((size-sdvig)/2)), (size-sdvig)%2, mass);
            cout<<"Переворот правой части:"<<endl;
            print(mass);
 
            //3) Переворачиваем весь массив:
            sdvig_f(0, (size-1), (size/2), size%2, mass);
            cout<<"Переворот всего массива:"<<endl;
            print(mass);
        }
        break;
    case 2:
        {
            //Задаем сдвиг:
            const int sdvig=sdvig_size();
            //1) Переворачиваем левую часть:
            sdvig_f(0, ((size-sdvig)-1), ((size-sdvig)/2), (size-sdvig)%2, mass);
            cout<<"Переворот левой части:"<<endl;
            print(mass);
    
            //2) Переворачиваем правую часть:
            sdvig_f((size-sdvig), (size-1), ((size-sdvig)+(sdvig/2)), sdvig%2, mass);
            cout<<"Переворот правой части:"<<endl;
            print(mass);
 
            //3) Переворачиваем весь массив:
            sdvig_f(0, (size-1), (size/2), size%2, mass);
            cout<<"Переворот всего массива:"<<endl;
            print(mass);
        }
        break;
    }
    cout<<endl;
 
    system("pause"); 
    return 0;
}
 
//Задание сдвига:
int const sdvig_size()
{
    int a;
    cout<<"Введите сдвиг: ";
    cin>>a;
    return a;
}
 
//Меняем местами части массива:
void sdvig_f(int a, int b, int usl, int center, int *mass2)
{
    int i;
    int j;
    if (center==0)
    {
        for(i=a, j=b; i!=usl; i++, j--) buffer(mass2[i], mass2[j]);
    }
    else
    {
        for(i=a, j=b; i!=j; i++, j--) buffer(mass2[i], mass2[j]);
    }
}
 
//Меняем местами заданные элементы массива
void buffer(int &mass_i, int &mass_j)
{
    int buf=mass_i;
    mass_i=mass_j;
    mass_j=buf;
}
 
//Вывод всего массива на экран:
void print(int *mass2)
{
    int i;
    for(i=0; i<size; i++)
    {
        cout<<mass2[i]<<" ";
    }
    cout<<endl;
}
Байт
 Аватар для Байт
13964 / 8795 / 1223
Регистрация: 24.12.2010
Сообщений: 15,930
04.03.2016, 20:49     Одномерный массив. Циклический сдвиг вправо #7
Croessmah, ValeryS, Господа, прошу прощения за эксгумацию. ссылками занесло.Croessmah, как говаривала моей недоброй памяти учительница английского - "Шейман ю" Заводить массивы - это конечно же моветон. Когда вполне можно справиться и без них, воспользовавшись идеей взаимной простоты.
ValeryS, а вот твое решение меня весьма заинтриговало. Понять его смысл в данный момент мне не предоставляется возможным. Надеюсь, что утром тучки разойдутся, голова посвежеет, попробую разобраться
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11823 / 6802 / 769
Регистрация: 27.09.2012
Сообщений: 16,870
Записей в блоге: 2
Завершенные тесты: 1
04.03.2016, 20:54     Одномерный массив. Циклический сдвиг вправо #8
Цитата Сообщение от Байт Посмотреть сообщение
Когда вполне можно справиться и без них, воспользовавшись идеей взаимной простоты.
Когда я это писал, я был совсем зеленый в плюсах
Сейчас, правда, тоже не далеко ушел, но чуть получше
Байт
04.03.2016, 21:27
  #9

Не по теме:

Цитата Сообщение от Croessmah Посмотреть сообщение
тоже не далеко ушел, но чуть получше
Скромность украшает даже классного программера

ValeryS
Модератор
6375 / 4841 / 443
Регистрация: 14.02.2011
Сообщений: 16,045
04.03.2016, 21:33     Одномерный массив. Циклический сдвиг вправо #10
Цитата Сообщение от Байт Посмотреть сообщение
ValeryS, а вот твое решение меня весьма заинтриговало.
честно говоря, это не мое решение, давным давно подсмотрел в какой-то книге
там еще пример был на пальцах, причем реально на пальцах, два кулака вместе, массив из 10 пальцев, сдвиг на 5
поворачиваешь левый кулак,потом правый, потом оба вместе, так чтобы кулаки поменялись местами
посмотри вот эту тему, там несколько решений Функция сдвига массива
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2899 / 1435 / 395
Регистрация: 18.10.2014
Сообщений: 2,643
04.03.2016, 22:15     Одномерный массив. Циклический сдвиг вправо #11
Эта задача всплывала здесь не раз (Переставить первые М-элементов в конец массива) и, в частности, является одной из классических задач программирования (подробно разобрана у Бентли в "Жемчужинах программирования"). Разумеется, задача тривиальна если разрешается использовать дополнительный массив. Задача становится интереснее, если дополнительного массива использовать не разрешается.

У задачи три классических решения
1. Популярное и общеизвестное решение через три переворота (упоминается ValeryS выше в ответе #5)
2. Более хитрое решение через обмен неравных блоков (несложно видеть, что циклический сдвиг - это то же самое, что обмен местами двух блоков длины K и N-K)
3. Жонглирование - индивидуальная перестановка элементов сразу на правильные места со следованием циклов в перестановке

Отдельно стоит заметить, что в С++ задача уже решена стандартным алгоритмом 'std::rotate', т.е. с этой точки зрения делать ничего не надо. В частности, в стандартной библиотеке MSVC++ 'std::rotate' для итераторов с произвольным доступом реализуется именно через три вызова 'std::reverse'. GCC, насколько я помню, делает это по-другому.

А вот, например, возможная реализация по методу 2

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename IT> void swap_blocks(IT b, IT m, IT e)
{ // В диапазоне [b, e) обмениваем местами поддиапазоны [b, m) и [m, e)
  if (m == b)
    return;
 
  while (e != m)
  {
    size_t n_left = m - b, n_right = e - m;
    if (n_left <= n_right)
    {
      std::swap_ranges(b, m, e - n_left);
      e -= n_left;
    }
    else
    {
      std::swap_ranges(b, b + n_right, m);
      b += n_right;
    }
  }
}
Теперь требуемый сдвиг вправо запросто реализуется как 'swap_blocks(A, A + N - K, A + N)'

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
  const int N = 8;
  const int K = 3;
  int A[N] = { 1, 2, 3, 4, 5, 6, 7, 8 };
 
  std::copy(std::begin(A), std::end(A), std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
 
  swap_blocks(A, A + N - K, A + N);
 
  std::copy(std::begin(A), std::end(A), std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
}
Байт
 Аватар для Байт
13964 / 8795 / 1223
Регистрация: 24.12.2010
Сообщений: 15,930
05.03.2016, 00:17     Одномерный массив. Циклический сдвиг вправо #12
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
"Жемчужинах программирования"
Если эта задача является жемчужиной, то должен вас предупредить, жемчуг - фальшивый. Задача нетривиальна только для совершенно начинающего и ничегошеньки не соображающего.
Цитата Сообщение от ValeryS Посмотреть сообщение
посмотри вот эту тему, там несколько решений
Решение я знаю, сам придумал, ничего там особенного нет. Только надо взять НОД от N и step и устроить 2 простых вложенных цикла. Даже хотел это решение куда-то прикрепить, но с модераторами не удалось столковаться. А вот твое "кулачное" решение - я просто сейчас, по убожеству своей соображалки, не могу разобрать. Просплюсь - попробую.
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2899 / 1435 / 395
Регистрация: 18.10.2014
Сообщений: 2,643
05.03.2016, 00:30     Одномерный массив. Циклический сдвиг вправо #13
Цитата Сообщение от Байт Посмотреть сообщение
Задача нетривиальна только для совершенно начинающего и ничегошеньки не соображающего.
Отнюдь!

Во-первых, авторитет классической книги мы тут оспаривать мы не будем. Задача действительно является жемчужиной.

Во-вторых, в "Жемчужинах программирования" эта задача преподносится в большей степени для иллюстрации того, как формальная эффективность алгоритма (в данном случае - оцениваемая по количеству переносов единичных элементов массива в памяти) может существенно не согласовываться с фактической производительностью реализации этого алгоритма на современных кэшированных архитектурах.

Формально оптимальным решением данной задачи является "жонглирующий" алгоритм, который берет элемент массива i и сразу же перемещает его в его финальную позицию (i + K) % N (я не буду расписывать все детали). Однако фактически такой алгоритм ведет себя очень плохо с точки зрения локализации доступа к памяти и громко проигрывает как реверсивному, так и блочно-обменному алгоритму на современных кэшированных архитектурах (при достатчоном размере массива, разумеется).

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

Кстати, ваше упоминание НОД свидетельствует именно о том, что вы изобрели какую-то вариацию того самого "жонглирующего" алгоритма
Байт
 Аватар для Байт
13964 / 8795 / 1223
Регистрация: 24.12.2010
Сообщений: 15,930
05.03.2016, 00:38     Одномерный массив. Циклический сдвиг вправо #14
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
авторитет ... мы тут оспаривать мы не будем.
Чего это вдруг?
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
берет элемент массива i и сразу же перемещает его в его финальную позицию (i + K) % N (я не буду расписывать все детали).
Вот уж Америка!
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
я не буду расписывать все детали
И впрямь, не стоит. Там деталей-то...
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
с точки зрения локализации доступа к памяти и громко проигрывает как реверсивному, так и блочно-обменному алгоритму на современных кэшированных архитектурах
Простите, но в данном контексте это выглядит просто чушью.
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2899 / 1435 / 395
Регистрация: 18.10.2014
Сообщений: 2,643
05.03.2016, 00:43     Одномерный массив. Циклический сдвиг вправо #15
Цитата Сообщение от Байт Посмотреть сообщение
Чего это вдруг?
Я так сказал.

Цитата Сообщение от Байт Посмотреть сообщение
Простите, но в данном контексте это выглядит просто чушью.
Хм... Интересно, в каком таком "контексте" объективные факты могут вдруг "выглядеть просто чушью". Мне действительно интересно.
Байт
 Аватар для Байт
13964 / 8795 / 1223
Регистрация: 24.12.2010
Сообщений: 15,930
05.03.2016, 00:57     Одномерный массив. Циклический сдвиг вправо #16
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Я так сказал.
Убедили
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Мне действительно интересно.
Ну... Стоит только соетнести контекст решения простой задачи с вашими глубочайшими изысканиями... Понимаете, тема которую вы пытаетесь поднять, лежит совершенно в других плоскостях. Наверное, тема эта эта интересна. Но всему свое место, вы не находите?
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Однако фактически такой алгоритм ведет себя очень плохо с точки зрения локализации доступа к памяти и громко проигрывает как реверсивному, так и блочно-обменному алгоритму на современных кэшированных архитектурах (при достатчоном размере массива, разумеется).
Я неплохо знаю математику. И в программировании не совсем уж новичок. И книжечки читывал. Но в процитированной фразе понимаю 1 слово из трех. А уж связи между ними... Но тут же раздел - "для начинающих"
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2899 / 1435 / 395
Регистрация: 18.10.2014
Сообщений: 2,643
05.03.2016, 01:19     Одномерный массив. Циклический сдвиг вправо #17
Цитата Сообщение от Байт Посмотреть сообщение
Понимаете, тема которую вы пытаетесь поднять, лежит совершенно в других плоскостях.
Единственная тема, которую я тут "пытался поднять", это наличие как минимум трех несложных алгоритмов решения данной задачи in-place. А дальше, по какой-то мне не ясной причине, пошли какие-то странные посягательства на светлое имя этой задачи... Как истинный джентльмен, я должен был вступиться.

-----

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

C++
1
2
3
4
5
6
7
8
9
void shift_right(int a[], size_t n, size_t k)
{ 
  int buffer[4];
  assert(k < n && k < sizeof buffer / sizeof *buffer);
 
  std::copy(a + n - k, a + n, buffer);
  std::copy_backward(a, a + n - k, a + n);
  std::copy(buffer, buffer + k, a);
}
И все.
Байт
 Аватар для Байт
13964 / 8795 / 1223
Регистрация: 24.12.2010
Сообщений: 15,930
05.03.2016, 11:11     Одномерный массив. Циклический сдвиг вправо #18
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
если внимательно посмотреть на условие задачи,
Да чего на нее смотреть! Школьная чушь! Если на это смотреть, так и вообще говорить не о чем.
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
И все.
Ваша правда

Добавлено через 9 часов 46 минут
Цитата Сообщение от ValeryS Посмотреть сообщение
надо сдвинуть на три элемента влево
Как я понимаю, 3 - это величина сдвига, да? Но тогда это решение эквивалентно исходной задаче... Или я чего-то не допонял?
ValeryS
Модератор
6375 / 4841 / 443
Регистрация: 14.02.2011
Сообщений: 16,045
05.03.2016, 13:46     Одномерный массив. Циклический сдвиг вправо #19
Цитата Сообщение от Байт Посмотреть сообщение
Как я понимаю, 3 - это величина сдвига, да?
да
взято в качестве примера, а так любое число,в теме которую я указывал есть уже готовый код
Цитата Сообщение от Байт Посмотреть сообщение
Но тогда это решение эквивалентно исходной задаче...
в исходной задаче
Цитата Сообщение от LeShu Посмотреть сообщение
массива вправо на K позиций
а у меня 3
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.07.2016, 13:12     Одномерный массив. Циклический сдвиг вправо
Еще ссылки по теме:

C++ Одномерный массив. Циклический сдвиг влево
Одномерный массив. Осуществить сдвиг вправо на k позиций C++
Дан массив размера N. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – индекс максимального элемента C++

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

Или воспользуйтесь поиском по форуму:
Cetych
5 / 5 / 2
Регистрация: 08.01.2016
Сообщений: 36
20.07.2016, 13:12     Одномерный массив. Циклический сдвиг вправо #20
Осталось код в голове смастерить=)
Yandex
Объявления
20.07.2016, 13:12     Одномерный массив. Циклический сдвиг вправо
Ответ Создать тему
Опции темы

Текущее время: 09:30. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru