Форум программистов, компьютерный форум 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 позиции
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
shilko2013
 Аватар для shilko2013
237 / 214 / 115
Регистрация: 02.04.2016
Сообщений: 812
Завершенные тесты: 1
20.07.2016, 13:37     Одномерный массив. Циклический сдвиг вправо #21
ValeryS, Ай молодца!!!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Байт
 Аватар для Байт
13941 / 8772 / 1220
Регистрация: 24.12.2010
Сообщений: 15,872
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);
}
Писал на коленке. Мог ошибиться. Где-то на форуме мной опубликовано проверенное решение, но найти его не смог...
Байт
 Аватар для Байт
13941 / 8772 / 1220
Регистрация: 24.12.2010
Сообщений: 15,872
21.07.2016, 23:08     Одномерный массив. Циклический сдвиг вправо #23
Прошу прощения у почтенной публики, коленка оказалась дырявой. И нагородил я в коде чуши.
Подождите, пожалуйста, до нормального рабочего рабочего стола и нормального интернета...
Байт
 Аватар для Байт
13941 / 8772 / 1220
Регистрация: 24.12.2010
Сообщений: 15,872
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
2174 / 1379 / 123
Регистрация: 01.03.2013
Сообщений: 4,115
Записей в блоге: 2
26.07.2016, 01:49     Одномерный массив. Циклический сдвиг вправо #25
При всем уважении к светлому имени этой задачи - я бы написал функцию/класс-обертку/итератор или как там это называется в выбранном языке реализации, который не будет переписывать память, а просто организует доступ к нужному элементу массива, рассматривая его как кольцевой буфер. Итого - имея один массив любой длины мы сразу получаем все его сдвиги на любое число элементов за О(1) по времени и самое забавное - все они будут лежать в памяти, занимаемой исходным массивом.
ValeryS
Модератор
6373 / 4839 / 440
Регистрация: 14.02.2011
Сообщений: 16,038
26.07.2016, 07:05     Одномерный массив. Циклический сдвиг вправо #26
_Ivana, идея конечно интересная
но бывают случаи когда нужно сдвигать именно физические данные, например, видеобуфер или данные в файле
Байт
 Аватар для Байт
13941 / 8772 / 1220
Регистрация: 24.12.2010
Сообщений: 15,872
26.07.2016, 09:54     Одномерный массив. Циклический сдвиг вправо #27
_Ivana, идея вполне светлая. И, ИМХО,код должен получиться короче.

Добавлено через 7 минут
Переформулирую. Написать функцию F(A[], n, s, i) дающую i-тый элемент массива A, состоящего из n элементов, после циклического сдвига на s. Сам массив не трогать (считать, что он находится в памяти onle-read)
_Ivana
2174 / 1379 / 123
Регистрация: 01.03.2013
Сообщений: 4,115
Записей в блоге: 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++ Одномерный массив. Циклический сдвиг влево
Одномерный массив. Осуществить сдвиг вправо на k позиций C++
Дан массив размера N. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – индекс максимального элемента C++

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

Или воспользуйтесь поиском по форуму:
Байт
 Аватар для Байт
13941 / 8772 / 1220
Регистрация: 24.12.2010
Сообщений: 15,872
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     Одномерный массив. Циклический сдвиг вправо
Ответ Создать тему
Опции темы

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