Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.57/84: Рейтинг темы: голосов - 84, средняя оценка - 4.57
0 / 0 / 1
Регистрация: 08.12.2012
Сообщений: 32
1

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

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

Author24 — интернет-сервис помощи студентам
Дан массив A размера N и целое число K (1 ≤ K ≤ 4, K < N). Осущест-
вить циклический сдвиг элементов массива вправо на K позиций (при этом
A перейдет в A , A — в A , …, A — в A ). Допускается использовать
1 K+1 2 K+2 N K
вспомогательный массив из 4 элементов.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.02.2013, 01:46
Ответы с готовыми решениями:

Дано одномерный массив Х, размером 15 элементов. Провести циклический сдвиг элементов в массиве вправо на 2 позиции
Дано одномерный массив Х, размером 15 элементов. Провести циклический сдвиг элементов в массиве...

Одномерный массив. Циклический сдвиг влево
Дан массив A размера N и целое число K (1 ≤ K ≤ 4, K &lt; N). Осущест- вить циклический сдвиг...

Одномерный массив. Осуществить сдвиг вправо на k позиций
Здравствуйте, помогите, пожалуйста с лабораторкой) Все никак не получается.. Вот задача Дан массив...

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

28
746 / 487 / 187
Регистрация: 30.12.2012
Сообщений: 1,278
Записей в блоге: 2
03.02.2013, 01:49 2
LeShu, а какие-нибудь собственные попытки сделать это у Вас есть?
0
0 / 0 / 1
Регистрация: 08.12.2012
Сообщений: 32
03.02.2013, 01:51  [ТС] 3
Цитата Сообщение от Tsin Посмотреть сообщение
LeShu, а какие-нибудь собственные попытки сделать это у Вас есть?
Да вот сижу, мучаю эти задачки или они меня
0
Неэпический
17870 / 10635 / 2054
Регистрация: 27.09.2012
Сообщений: 26,737
Записей в блоге: 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;
}
2
Модератор
Эксперт по электронике
8909 / 6678 / 918
Регистрация: 14.02.2011
Сообщений: 23,524
03.02.2013, 02:16 5
Лучший ответ Сообщение было отмечено как решение

Решение

есть одно интересное решение приводить пока не буду
расскажу принцип для того чтобы циклически сдвинуть массив надо сначала
перевернуть правую часть
потом левую часть
потом весь массив
12345678
надо сдвинуть на три элемента влево
1-32145678
2-32187654
3-45678123
надо сдвинуть на три элемента вправо
1 54321678
2 54321876
3 67812345

Добавлено через 56 секунд
никакой дополнительной памяти все делается в этом же массиве
8
2 / 2 / 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;
}
1
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
04.03.2016, 20:49 7
Croessmah, ValeryS, Господа, прошу прощения за эксгумацию. ссылками занесло.Croessmah, как говаривала моей недоброй памяти учительница английского - "Шейман ю" Заводить массивы - это конечно же моветон. Когда вполне можно справиться и без них, воспользовавшись идеей взаимной простоты.
ValeryS, а вот твое решение меня весьма заинтриговало. Понять его смысл в данный момент мне не предоставляется возможным. Надеюсь, что утром тучки разойдутся, голова посвежеет, попробую разобраться
0
Неэпический
17870 / 10635 / 2054
Регистрация: 27.09.2012
Сообщений: 26,737
Записей в блоге: 1
04.03.2016, 20:54 8
Цитата Сообщение от Байт Посмотреть сообщение
Когда вполне можно справиться и без них, воспользовавшись идеей взаимной простоты.
Когда я это писал, я был совсем зеленый в плюсах
Сейчас, правда, тоже не далеко ушел, но чуть получше
0
Байт
04.03.2016, 21:27
  #9

Не по теме:

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

0
Модератор
Эксперт по электронике
8909 / 6678 / 918
Регистрация: 14.02.2011
Сообщений: 23,524
04.03.2016, 21:33 10
Цитата Сообщение от Байт Посмотреть сообщение
ValeryS, а вот твое решение меня весьма заинтриговало.
честно говоря, это не мое решение, давным давно подсмотрел в какой-то книге
там еще пример был на пальцах, причем реально на пальцах, два кулака вместе, массив из 10 пальцев, сдвиг на 5
поворачиваешь левый кулак,потом правый, потом оба вместе, так чтобы кулаки поменялись местами
посмотри вот эту тему, там несколько решений Функция циклического сдвига массива
0
Вездепух
Эксперт CЭксперт С++
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,078
04.03.2016, 22:15 11
Эта задача всплывала здесь не раз (https://www.cyberforum.ru/post6813125.html) и, в частности, является одной из классических задач программирования (подробно разобрана у Бентли в "Жемчужинах программирования"). Разумеется, задача тривиальна если разрешается использовать дополнительный массив. Задача становится интереснее, если дополнительного массива использовать не разрешается.

У задачи три классических решения
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;
}
2
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
05.03.2016, 00:17 12
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
"Жемчужинах программирования"
Если эта задача является жемчужиной, то должен вас предупредить, жемчуг - фальшивый. Задача нетривиальна только для совершенно начинающего и ничегошеньки не соображающего.
Цитата Сообщение от ValeryS Посмотреть сообщение
посмотри вот эту тему, там несколько решений
Решение я знаю, сам придумал, ничего там особенного нет. Только надо взять НОД от N и step и устроить 2 простых вложенных цикла. Даже хотел это решение куда-то прикрепить, но с модераторами не удалось столковаться. А вот твое "кулачное" решение - я просто сейчас, по убожеству своей соображалки, не могу разобрать. Просплюсь - попробую.
0
Вездепух
Эксперт CЭксперт С++
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,078
05.03.2016, 00:30 13
Цитата Сообщение от Байт Посмотреть сообщение
Задача нетривиальна только для совершенно начинающего и ничегошеньки не соображающего.
Отнюдь!

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

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

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

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

Кстати, ваше упоминание НОД свидетельствует именно о том, что вы изобрели какую-то вариацию того самого "жонглирующего" алгоритма
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
05.03.2016, 00:38 14
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
авторитет ... мы тут оспаривать мы не будем.
Чего это вдруг?
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
берет элемент массива i и сразу же перемещает его в его финальную позицию (i + K) % N (я не буду расписывать все детали).
Вот уж Америка!
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
я не буду расписывать все детали
И впрямь, не стоит. Там деталей-то...
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
с точки зрения локализации доступа к памяти и громко проигрывает как реверсивному, так и блочно-обменному алгоритму на современных кэшированных архитектурах
Простите, но в данном контексте это выглядит просто чушью.
0
Вездепух
Эксперт CЭксперт С++
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,078
05.03.2016, 00:43 15
Цитата Сообщение от Байт Посмотреть сообщение
Чего это вдруг?
Я так сказал.

Цитата Сообщение от Байт Посмотреть сообщение
Простите, но в данном контексте это выглядит просто чушью.
Хм... Интересно, в каком таком "контексте" объективные факты могут вдруг "выглядеть просто чушью". Мне действительно интересно.
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
05.03.2016, 00:57 16
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Я так сказал.
Убедили
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Мне действительно интересно.
Ну... Стоит только соетнести контекст решения простой задачи с вашими глубочайшими изысканиями... Понимаете, тема которую вы пытаетесь поднять, лежит совершенно в других плоскостях. Наверное, тема эта эта интересна. Но всему свое место, вы не находите?
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Однако фактически такой алгоритм ведет себя очень плохо с точки зрения локализации доступа к памяти и громко проигрывает как реверсивному, так и блочно-обменному алгоритму на современных кэшированных архитектурах (при достатчоном размере массива, разумеется).
Я неплохо знаю математику. И в программировании не совсем уж новичок. И книжечки читывал. Но в процитированной фразе понимаю 1 слово из трех. А уж связи между ними... Но тут же раздел - "для начинающих"
0
Вездепух
Эксперт CЭксперт С++
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,078
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);
}
И все.
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
05.03.2016, 11:11 18
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
если внимательно посмотреть на условие задачи,
Да чего на нее смотреть! Школьная чушь! Если на это смотреть, так и вообще говорить не о чем.
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
И все.
Ваша правда

Добавлено через 9 часов 46 минут
Цитата Сообщение от ValeryS Посмотреть сообщение
надо сдвинуть на три элемента влево
Как я понимаю, 3 - это величина сдвига, да? Но тогда это решение эквивалентно исходной задаче... Или я чего-то не допонял?
0
Модератор
Эксперт по электронике
8909 / 6678 / 918
Регистрация: 14.02.2011
Сообщений: 23,524
05.03.2016, 13:46 19
Цитата Сообщение от Байт Посмотреть сообщение
Как я понимаю, 3 - это величина сдвига, да?
да
взято в качестве примера, а так любое число,в теме которую я указывал есть уже готовый код
Цитата Сообщение от Байт Посмотреть сообщение
Но тогда это решение эквивалентно исходной задаче...
в исходной задаче
Цитата Сообщение от LeShu Посмотреть сообщение
массива вправо на K позиций
а у меня 3
0
7 / 7 / 4
Регистрация: 08.01.2016
Сообщений: 50
20.07.2016, 13:12 20
Осталось код в голове смастерить=)
0
20.07.2016, 13:12
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.07.2016, 13:12
Помогаю со студенческими работами здесь

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

Циклический сдвиг вправо
Нужно сделать цеклический сдвиг машинного слова на 1 байт влево, через union и через побитовые...

Циклический сдвиг массива вправо
дан двумерный массив MxN нужно осуществить поэлементный сдвиг вправо на 1 элемент

Реализовать циклический сдвиг вправо
Вот собственно мой код: #include &quot;pch.h&quot; #include &lt;iostream&gt; #include &quot;conio.h&quot; #include...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru