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

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

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

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

03.02.2013, 01:46. Просмотров 6443. Ответов 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++ Циклический сдвиг массива вправо
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Байт
Эксперт C
15841 / 10168 / 1522
Регистрация: 24.12.2010
Сообщений: 19,171
05.03.2016, 00:57     Одномерный массив. Циклический сдвиг вправо #16
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Я так сказал.
Убедили
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Мне действительно интересно.
Ну... Стоит только соетнести контекст решения простой задачи с вашими глубочайшими изысканиями... Понимаете, тема которую вы пытаетесь поднять, лежит совершенно в других плоскостях. Наверное, тема эта эта интересна. Но всему свое место, вы не находите?
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Однако фактически такой алгоритм ведет себя очень плохо с точки зрения локализации доступа к памяти и громко проигрывает как реверсивному, так и блочно-обменному алгоритму на современных кэшированных архитектурах (при достатчоном размере массива, разумеется).
Я неплохо знаю математику. И в программировании не совсем уж новичок. И книжечки читывал. Но в процитированной фразе понимаю 1 слово из трех. А уж связи между ними... Но тут же раздел - "для начинающих"
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3706 / 1981 / 516
Регистрация: 18.10.2014
Сообщений: 3,565
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);
}
И все.
Байт
Эксперт C
15841 / 10168 / 1522
Регистрация: 24.12.2010
Сообщений: 19,171
05.03.2016, 11:11     Одномерный массив. Циклический сдвиг вправо #18
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
если внимательно посмотреть на условие задачи,
Да чего на нее смотреть! Школьная чушь! Если на это смотреть, так и вообще говорить не о чем.
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
И все.
Ваша правда

Добавлено через 9 часов 46 минут
Цитата Сообщение от ValeryS Посмотреть сообщение
надо сдвинуть на три элемента влево
Как я понимаю, 3 - это величина сдвига, да? Но тогда это решение эквивалентно исходной задаче... Или я чего-то не допонял?
ValeryS
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,737
05.03.2016, 13:46     Одномерный массив. Циклический сдвиг вправо #19
Цитата Сообщение от Байт Посмотреть сообщение
Как я понимаю, 3 - это величина сдвига, да?
да
взято в качестве примера, а так любое число,в теме которую я указывал есть уже готовый код
Цитата Сообщение от Байт Посмотреть сообщение
Но тогда это решение эквивалентно исходной задаче...
в исходной задаче
Цитата Сообщение от LeShu Посмотреть сообщение
массива вправо на K позиций
а у меня 3
Cetych
6 / 6 / 2
Регистрация: 08.01.2016
Сообщений: 36
20.07.2016, 13:12     Одномерный массив. Циклический сдвиг вправо #20
Осталось код в голове смастерить=)
shilko2013
240 / 217 / 117
Регистрация: 02.04.2016
Сообщений: 827
Завершенные тесты: 1
20.07.2016, 13:37     Одномерный массив. Циклический сдвиг вправо #21
ValeryS, Ай молодца!!!
Байт
Эксперт C
15841 / 10168 / 1522
Регистрация: 24.12.2010
Сообщений: 19,171
20.07.2016, 22:43     Одномерный массив. Циклический сдвиг вправо #22
Цитата Сообщение от Cetych Посмотреть сообщение
Осталось код в голове смастерить=)
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Nod(int a, int b)
{
  ....
}
void swap(int *a, int *)
{
  ...
}
Shift(int A[], int n, int s)
{
  nd = Nod(n, k);
  for(i=0; i<nd; i++)
     for(j=0; j < n/nd; j++)
        swap(A+nd*i + j, (A+nd*i + j + s)%n);
}
Писал на коленке. Мог ошибиться. Где-то на форуме мной опубликовано проверенное решение, но найти его не смог...
Байт
Эксперт C
15841 / 10168 / 1522
Регистрация: 24.12.2010
Сообщений: 19,171
21.07.2016, 23:08     Одномерный массив. Циклический сдвиг вправо #23
Прошу прощения у почтенной публики, коленка оказалась дырявой. И нагородил я в коде чуши.
Подождите, пожалуйста, до нормального рабочего рабочего стола и нормального интернета...
Байт
Эксперт C
15841 / 10168 / 1522
Регистрация: 24.12.2010
Сообщений: 19,171
26.07.2016, 00:05     Одномерный массив. Циклический сдвиг вправо #24
Сразу оговорюсь. Я здесь рассматриваю немного не ту задачу, которая сформулирована в стартовом топике. А именно - циклический сдвиг массива размером n на произвольное число позиций s без использования дополнительных массивов.
Все оказалось не так тривиально в смысле реализации (кода), но идея не сложна, хоть и симпатична.
Если размер массива (n) и сдвиг (s) взаимно просты, то задачу решает следующий код.
Кликните здесь для просмотра всего текста
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
void swap(int *a, int *b)
{  int t;
  t = *a;
  *a = *b;
  *b = t;
}
int main(int ac, char *av[])
{ int n=10, s=1, A[100], i, ii;
   if (ac > 1) n = atoi(av[1]);
   if (ac > 2) s = atoi(av[2]);
   printf("n=%d s=%d\n", n, s);
   for(i=0; i<n; i++) A[i] = i+1;
   ii = 0;
   for(i=0; i<n-1; i++) {
     swap(A+ii, A+(n+ii-s)%n);
     ii = (n+ii-s)%n;
   }
   for(i=0; i<n; i++) printf("%d ", A[i]);
   printf("\n");
}

Программа запускается из командной строки с параметрами Размер Сдвиг
sdvig 36 10
Если же Nd = Nod(n,s) не равен 1, то поступаем следующим образом.
Разбиваем исходный массив на Nd подмассивов размером n/Nd. Элементы каждого подмассива отстоят друг от друга на Nd (поэтому и требуется функция Ind).
Сдвиг тоже делим на Nd. Теперь каждый из массивов удовлетворяет условию взаимной простоты размера и сдвига, и к ним применяется описанный алгоритм.
Кликните здесь для просмотра всего текста
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
#include <stdio.h>
void swap(int *a, int *b)
{  int t = *a;
  *a = *b;
  *b = t;
}
int Nod(int a, int b)
{
  while(a!=0) {
    if (a < b) swap(&a, &b);
    a = a%b;
  }
  return b;
}
int Ind(int I, int m, int Nd)  // Перевод индекса подмассива в положение в исходном массиве
{
  return m + I*Nd;
}
int main(int ac, char *av[])
{ int n=10, s=1, A[100], i, ii, Nd, j, k;
   if (ac > 1) n = atoi(av[1]);
   if (ac > 2) s = atoi(av[2]);
   if (s < 0) s = n - s;
   s %= n;
   Nd = Nod(n, s);
   printf("n=%d s=%d Nd=%d\n", n, s, Nd);
   s /= Nd;
   for(i=0; i<n; i++) A[i] = i+1;
   k = n / Nd;  // Размер каждого массива
   for(j=0; j<Nd; j++) {  // Цикл по массивам
     ii = 0;
     for(i=0; i<k-1; i++) {
       swap(A+Ind(ii,j,Nd)%n, A+Ind(k+ii-s,j,Nd)%n);
       ii = (k+ii-s)%n;
     }
   }
   for(i=0; i<n; i++) printf("%d ", A[i]);
   printf("\n");
}
_Ivana
3042 / 1729 / 150
Регистрация: 01.03.2013
Сообщений: 4,908
Записей в блоге: 2
26.07.2016, 01:49     Одномерный массив. Циклический сдвиг вправо #25
При всем уважении к светлому имени этой задачи - я бы написал функцию/класс-обертку/итератор или как там это называется в выбранном языке реализации, который не будет переписывать память, а просто организует доступ к нужному элементу массива, рассматривая его как кольцевой буфер. Итого - имея один массив любой длины мы сразу получаем все его сдвиги на любое число элементов за О(1) по времени и самое забавное - все они будут лежать в памяти, занимаемой исходным массивом.
ValeryS
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,737
26.07.2016, 07:05     Одномерный массив. Циклический сдвиг вправо #26
_Ivana, идея конечно интересная
но бывают случаи когда нужно сдвигать именно физические данные, например, видеобуфер или данные в файле
Байт
Эксперт C
15841 / 10168 / 1522
Регистрация: 24.12.2010
Сообщений: 19,171
26.07.2016, 09:54     Одномерный массив. Циклический сдвиг вправо #27
_Ivana, идея вполне светлая. И, ИМХО,код должен получиться короче.

Добавлено через 7 минут
Переформулирую. Написать функцию F(A[], n, s, i) дающую i-тый элемент массива A, состоящего из n элементов, после циклического сдвига на s. Сам массив не трогать (считать, что он находится в памяти onle-read)
_Ivana
3042 / 1729 / 150
Регистрация: 01.03.2013
Сообщений: 4,908
Записей в блоге: 2
26.07.2016, 18:52     Одномерный массив. Циклический сдвиг вправо #28
Цитата Сообщение от ValeryS Посмотреть сообщение
но бывают случаи когда нужно сдвигать именно физические данные, например, видеобуфер или данные в файле
я думал об этом. И пришел к выводу, что 9 из 10 таких случаев совершенно не требуют лежания массива в последовательной области памяти, а просто опираются на это предположение . Например, у нас есть сишная функция, принимает указатель на начало массива и количество элементов и что-то с ним делает (читает, пишет). Внутри вовсю используется взятие значения указателя и запись значения по указателю плюс арифметика/инкремент/декремент указателя. И таких мест много. Чтож, это печально, но можно пойти двумя путями:

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

Во втором случае функция будет более универсальна.

Цитата Сообщение от Байт Посмотреть сообщение
Переформулирую. Написать функцию F(A[], n, s, i) дающую i-тый элемент массива A, состоящего из n элементов, после циклического сдвига на s. Сам массив не трогать (считать, что он находится в памяти onle-read)
Ну и тогда любой сдвиг плюс опциональный реверс заодно, чтоб 2 раза не вставать
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.07.2016, 14:00     Одномерный массив. Циклический сдвиг вправо
Еще ссылки по теме:
Циклический сдвиг массива влево и вправо C++
Осуществить циклический сдвиг массива вправо на m позиций C++
C++ Циклический сдвиг элементов массива вправо на К позиций
Циклический сдвиг прямоугольной матрицы на n элементов вправо C++
C++ Произвести циклический сдвиг вправо элементов массива

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

Или воспользуйтесь поиском по форуму:
Байт
Эксперт C
15841 / 10168 / 1522
Регистрация: 24.12.2010
Сообщений: 19,171
29.07.2016, 14:00     Одномерный массив. Циклический сдвиг вправо #29
Цитата Сообщение от _Ivana Посмотреть сообщение
пришел к выводу, что 9 из 10 таких случаев
Предложенная функция чрезвычайно проста. Вот ее код
C
1
int F(int A[], int n, int s, int i) { return A[(n+i-s)%n]; :
Но остается еще один случай из 10, когда всетки требуется сдвинуть массив физически
Как вы предлагаете это сделать?
Даже если в вашем распоряжении есть эта замечательная функция F

Добавлено через 24 минуты
ЗЫ. Если одна задача встречается в 9 раз реже другой, это еще не повод для игнорирования попыток ее решения.
Yandex
Объявления
29.07.2016, 14:00     Одномерный массив. Циклический сдвиг вправо
Ответ Создать тему
Опции темы

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