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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 41, средняя оценка - 4.80
LeShu
0 / 0 / 0
Регистрация: 08.12.2012
Сообщений: 32
#1

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

03.02.2013, 01:46. Просмотров 6436. Ответов 28
Метки нет (Все метки)

Дан массив 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++ Дано одномерный массив Х, размером 15 элементов. Провести циклический сдвиг элементов в массиве вправо на 2 позиции
Одномерный массив. Осуществить сдвиг вправо на k позиций C++
C++ Одномерный массив. Циклический сдвиг влево
Дан массив размера N. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – индекс максимального элемента C++
C++ Дан массив размера N. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k- индекс максимального элемента.
Циклический сдвиг вправо C++
C++ Циклический сдвиг массива вправо
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tsin
709 / 454 / 129
Регистрация: 30.12.2012
Сообщений: 1,235
Записей в блоге: 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
Модератор
Эксперт CЭксперт С++
13052 / 7315 / 814
Регистрация: 27.09.2012
Сообщений: 18,052
Записей в блоге: 3
Завершенные тесты: 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
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,733
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;
}
Байт
Эксперт C
15835 / 10162 / 1522
Регистрация: 24.12.2010
Сообщений: 19,159
04.03.2016, 20:49     Одномерный массив. Циклический сдвиг вправо #7
Croessmah, ValeryS, Господа, прошу прощения за эксгумацию. ссылками занесло.Croessmah, как говаривала моей недоброй памяти учительница английского - "Шейман ю" Заводить массивы - это конечно же моветон. Когда вполне можно справиться и без них, воспользовавшись идеей взаимной простоты.
ValeryS, а вот твое решение меня весьма заинтриговало. Понять его смысл в данный момент мне не предоставляется возможным. Надеюсь, что утром тучки разойдутся, голова посвежеет, попробую разобраться
Croessmah
Модератор
Эксперт CЭксперт С++
13052 / 7315 / 814
Регистрация: 27.09.2012
Сообщений: 18,052
Записей в блоге: 3
Завершенные тесты: 1
04.03.2016, 20:54     Одномерный массив. Циклический сдвиг вправо #8
Цитата Сообщение от Байт Посмотреть сообщение
Когда вполне можно справиться и без них, воспользовавшись идеей взаимной простоты.
Когда я это писал, я был совсем зеленый в плюсах
Сейчас, правда, тоже не далеко ушел, но чуть получше
Байт
04.03.2016, 21:27
  #9

Не по теме:

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

ValeryS
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,733
04.03.2016, 21:33     Одномерный массив. Циклический сдвиг вправо #10
Цитата Сообщение от Байт Посмотреть сообщение
ValeryS, а вот твое решение меня весьма заинтриговало.
честно говоря, это не мое решение, давным давно подсмотрел в какой-то книге
там еще пример был на пальцах, причем реально на пальцах, два кулака вместе, массив из 10 пальцев, сдвиг на 5
поворачиваешь левый кулак,потом правый, потом оба вместе, так чтобы кулаки поменялись местами
посмотри вот эту тему, там несколько решений Функция сдвига массива
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3693 / 1968 / 514
Регистрация: 18.10.2014
Сообщений: 3,554
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;
}
Байт
Эксперт C
15835 / 10162 / 1522
Регистрация: 24.12.2010
Сообщений: 19,159
05.03.2016, 00:17     Одномерный массив. Циклический сдвиг вправо #12
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
"Жемчужинах программирования"
Если эта задача является жемчужиной, то должен вас предупредить, жемчуг - фальшивый. Задача нетривиальна только для совершенно начинающего и ничегошеньки не соображающего.
Цитата Сообщение от ValeryS Посмотреть сообщение
посмотри вот эту тему, там несколько решений
Решение я знаю, сам придумал, ничего там особенного нет. Только надо взять НОД от N и step и устроить 2 простых вложенных цикла. Даже хотел это решение куда-то прикрепить, но с модераторами не удалось столковаться. А вот твое "кулачное" решение - я просто сейчас, по убожеству своей соображалки, не могу разобрать. Просплюсь - попробую.
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3693 / 1968 / 514
Регистрация: 18.10.2014
Сообщений: 3,554
05.03.2016, 00:30     Одномерный массив. Циклический сдвиг вправо #13
Цитата Сообщение от Байт Посмотреть сообщение
Задача нетривиальна только для совершенно начинающего и ничегошеньки не соображающего.
Отнюдь!

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

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

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

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

Кстати, ваше упоминание НОД свидетельствует именно о том, что вы изобрели какую-то вариацию того самого "жонглирующего" алгоритма
Байт
Эксперт C
15835 / 10162 / 1522
Регистрация: 24.12.2010
Сообщений: 19,159
05.03.2016, 00:38     Одномерный массив. Циклический сдвиг вправо #14
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
авторитет ... мы тут оспаривать мы не будем.
Чего это вдруг?
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
берет элемент массива i и сразу же перемещает его в его финальную позицию (i + K) % N (я не буду расписывать все детали).
Вот уж Америка!
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
я не буду расписывать все детали
И впрямь, не стоит. Там деталей-то...
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
с точки зрения локализации доступа к памяти и громко проигрывает как реверсивному, так и блочно-обменному алгоритму на современных кэшированных архитектурах
Простите, но в данном контексте это выглядит просто чушью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.03.2016, 00:43     Одномерный массив. Циклический сдвиг вправо
Еще ссылки по теме:
Циклический сдвиг массива влево и вправо C++
Осуществить циклический сдвиг массива вправо на m позиций C++
C++ Циклический сдвиг элементов массива вправо на К позиций
Циклический сдвиг прямоугольной матрицы на n элементов вправо C++
C++ Произвести циклический сдвиг вправо элементов массива

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

Или воспользуйтесь поиском по форуму:
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3693 / 1968 / 514
Регистрация: 18.10.2014
Сообщений: 3,554
05.03.2016, 00:43     Одномерный массив. Циклический сдвиг вправо #15
Цитата Сообщение от Байт Посмотреть сообщение
Чего это вдруг?
Я так сказал.

Цитата Сообщение от Байт Посмотреть сообщение
Простите, но в данном контексте это выглядит просто чушью.
Хм... Интересно, в каком таком "контексте" объективные факты могут вдруг "выглядеть просто чушью". Мне действительно интересно.
Yandex
Объявления
05.03.2016, 00:43     Одномерный массив. Циклический сдвиг вправо
Ответ Создать тему
Опции темы

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