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

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

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

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

03.02.2013, 01:46. Просмотров 6546. Ответов 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 элементов.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.02.2013, 01:46
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Одномерный массив. Циклический сдвиг вправо (C++):

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

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Tsin
710 / 455 / 130
Регистрация: 30.12.2012
Сообщений: 1,238
Записей в блоге: 2
Завершенные тесты: 3
03.02.2013, 01:49 #2
LeShu, а какие-нибудь собственные попытки сделать это у Вас есть?
0
LeShu
0 / 0 / 0
Регистрация: 08.12.2012
Сообщений: 32
03.02.2013, 01:51  [ТС] #3
Цитата Сообщение от Tsin Посмотреть сообщение
LeShu, а какие-нибудь собственные попытки сделать это у Вас есть?
Да вот сижу, мучаю эти задачки или они меня
0
Croessmah
Эксперт CЭксперт С++
13221 / 7493 / 845
Регистрация: 27.09.2012
Сообщений: 18,412
Записей в блоге: 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;
}
1
ValeryS
Модератор
6631 / 5038 / 466
Регистрация: 14.02.2011
Сообщений: 16,849
03.02.2013, 02:16 #5
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
есть одно интересное решение приводить пока не буду
расскажу принцип для того чтобы циклически сдвинуть массив надо сначала
перевернуть правую часть
потом левую часть
потом весь массив
12345678
надо сдвинуть на три элемента влево
1-32145678
2-32187654
3-45678123
надо сдвинуть на три элемента вправо
1 54321678
2 54321876
3 67812345

Добавлено через 56 секунд
никакой дополнительной памяти все делается в этом же массиве
8
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;
}
1
Байт
Эксперт C
16061 / 10330 / 1540
Регистрация: 24.12.2010
Сообщений: 19,458
04.03.2016, 20:49 #7
Croessmah, ValeryS, Господа, прошу прощения за эксгумацию. ссылками занесло.Croessmah, как говаривала моей недоброй памяти учительница английского - "Шейман ю" Заводить массивы - это конечно же моветон. Когда вполне можно справиться и без них, воспользовавшись идеей взаимной простоты.
ValeryS, а вот твое решение меня весьма заинтриговало. Понять его смысл в данный момент мне не предоставляется возможным. Надеюсь, что утром тучки разойдутся, голова посвежеет, попробую разобраться
0
Croessmah
Эксперт CЭксперт С++
13221 / 7493 / 845
Регистрация: 27.09.2012
Сообщений: 18,412
Записей в блоге: 3
Завершенные тесты: 1
04.03.2016, 20:54 #8
Цитата Сообщение от Байт Посмотреть сообщение
Когда вполне можно справиться и без них, воспользовавшись идеей взаимной простоты.
Когда я это писал, я был совсем зеленый в плюсах
Сейчас, правда, тоже не далеко ушел, но чуть получше
0
Байт
04.03.2016, 21:27
  #9

Не по теме:

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

0
ValeryS
Модератор
6631 / 5038 / 466
Регистрация: 14.02.2011
Сообщений: 16,849
04.03.2016, 21:33 #10
Цитата Сообщение от Байт Посмотреть сообщение
ValeryS, а вот твое решение меня весьма заинтриговало.
честно говоря, это не мое решение, давным давно подсмотрел в какой-то книге
там еще пример был на пальцах, причем реально на пальцах, два кулака вместе, массив из 10 пальцев, сдвиг на 5
поворачиваешь левый кулак,потом правый, потом оба вместе, так чтобы кулаки поменялись местами
посмотри вот эту тему, там несколько решений Функция сдвига массива
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3826 / 2084 / 532
Регистрация: 18.10.2014
Сообщений: 3,699
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;
}
1
Байт
Эксперт C
16061 / 10330 / 1540
Регистрация: 24.12.2010
Сообщений: 19,458
05.03.2016, 00:17 #12
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
"Жемчужинах программирования"
Если эта задача является жемчужиной, то должен вас предупредить, жемчуг - фальшивый. Задача нетривиальна только для совершенно начинающего и ничегошеньки не соображающего.
Цитата Сообщение от ValeryS Посмотреть сообщение
посмотри вот эту тему, там несколько решений
Решение я знаю, сам придумал, ничего там особенного нет. Только надо взять НОД от N и step и устроить 2 простых вложенных цикла. Даже хотел это решение куда-то прикрепить, но с модераторами не удалось столковаться. А вот твое "кулачное" решение - я просто сейчас, по убожеству своей соображалки, не могу разобрать. Просплюсь - попробую.
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3826 / 2084 / 532
Регистрация: 18.10.2014
Сообщений: 3,699
05.03.2016, 00:30 #13
Цитата Сообщение от Байт Посмотреть сообщение
Задача нетривиальна только для совершенно начинающего и ничегошеньки не соображающего.
Отнюдь!

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

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

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

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

Кстати, ваше упоминание НОД свидетельствует именно о том, что вы изобрели какую-то вариацию того самого "жонглирующего" алгоритма
0
Байт
Эксперт C
16061 / 10330 / 1540
Регистрация: 24.12.2010
Сообщений: 19,458
05.03.2016, 00:38 #14
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
авторитет ... мы тут оспаривать мы не будем.
Чего это вдруг?
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
берет элемент массива i и сразу же перемещает его в его финальную позицию (i + K) % N (я не буду расписывать все детали).
Вот уж Америка!
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
я не буду расписывать все детали
И впрямь, не стоит. Там деталей-то...
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
с точки зрения локализации доступа к памяти и громко проигрывает как реверсивному, так и блочно-обменному алгоритму на современных кэшированных архитектурах
Простите, но в данном контексте это выглядит просто чушью.
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3826 / 2084 / 532
Регистрация: 18.10.2014
Сообщений: 3,699
05.03.2016, 00:43 #15
Цитата Сообщение от Байт Посмотреть сообщение
Чего это вдруг?
Я так сказал.

Цитата Сообщение от Байт Посмотреть сообщение
Простите, но в данном контексте это выглядит просто чушью.
Хм... Интересно, в каком таком "контексте" объективные факты могут вдруг "выглядеть просто чушью". Мне действительно интересно.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.03.2016, 00:43
Привет! Вот еще темы с ответами:

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

Циклический сдвиг массива влево и вправо - C++
Нужно реализовать циклический сдвиг массива влево и вправо! Например есть массив int- {121605}? mass_len=6, нужно чтобы после сдвига...

Произвести циклический сдвиг вправо элементов массива - C++
Люди в Си++ дуб дубом. Помагите очень надо. Вот текст задачи. Ввести одномерный целочисленный массив A, вывести его. Произвести...

Осуществить циклический сдвиг массива вправо на m позиций - C++
Разработать алгоритм и программу. Дан одномерный массив С размерностью 1хn (1&lt;=n&lt;=20). Элементы массива принимают значения от 0 до 255 и...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
05.03.2016, 00:43
Ответ Создать тему
Опции темы

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