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

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

03.02.2013, 01:46. Показов 19534. Ответов 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)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
03.02.2013, 01:46
Ответы с готовыми решениями:

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

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

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

28
 Аватар для shilko2013
257 / 234 / 185
Регистрация: 02.04.2016
Сообщений: 898
20.07.2016, 13:37
Студворк — интернет-сервис помощи студентам
ValeryS, Ай молодца!!!
0
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
20.07.2016, 22:43
Цитата Сообщение от 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);
}
Писал на коленке. Мог ошибиться. Где-то на форуме мной опубликовано проверенное решение, но найти его не смог...
0
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
21.07.2016, 23:08
Прошу прощения у почтенной публики, коленка оказалась дырявой. И нагородил я в коде чуши.
Подождите, пожалуйста, до нормального рабочего рабочего стола и нормального интернета...
0
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
26.07.2016, 00:05
Сразу оговорюсь. Я здесь рассматриваю немного не ту задачу, которая сформулирована в стартовом топике. А именно - циклический сдвиг массива размером 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");
}
2
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
26.07.2016, 01:49
При всем уважении к светлому имени этой задачи - я бы написал функцию/класс-обертку/итератор или как там это называется в выбранном языке реализации, который не будет переписывать память, а просто организует доступ к нужному элементу массива, рассматривая его как кольцевой буфер. Итого - имея один массив любой длины мы сразу получаем все его сдвиги на любое число элементов за О(1) по времени и самое забавное - все они будут лежать в памяти, занимаемой исходным массивом.
3
Модератор
Эксперт по электронике
8982 / 6749 / 921
Регистрация: 14.02.2011
Сообщений: 23,878
26.07.2016, 07:05
_Ivana, идея конечно интересная
но бывают случаи когда нужно сдвигать именно физические данные, например, видеобуфер или данные в файле
0
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
26.07.2016, 09:54
_Ivana, идея вполне светлая. И, ИМХО,код должен получиться короче.

Добавлено через 7 минут
Переформулирую. Написать функцию F(A[], n, s, i) дающую i-тый элемент массива A, состоящего из n элементов, после циклического сдвига на s. Сам массив не трогать (считать, что он находится в памяти onle-read)
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
26.07.2016, 18:52
Цитата Сообщение от ValeryS Посмотреть сообщение
но бывают случаи когда нужно сдвигать именно физические данные, например, видеобуфер или данные в файле
я думал об этом. И пришел к выводу, что 9 из 10 таких случаев совершенно не требуют лежания массива в последовательной области памяти, а просто опираются на это предположение . Например, у нас есть сишная функция, принимает указатель на начало массива и количество элементов и что-то с ним делает (читает, пишет). Внутри вовсю используется взятие значения указателя и запись значения по указателю плюс арифметика/инкремент/декремент указателя. И таких мест много. Чтож, это печально, но можно пойти двумя путями:

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

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

Цитата Сообщение от Байт Посмотреть сообщение
Переформулирую. Написать функцию F(A[], n, s, i) дающую i-тый элемент массива A, состоящего из n элементов, после циклического сдвига на s. Сам массив не трогать (считать, что он находится в памяти onle-read)
Ну и тогда любой сдвиг плюс опциональный реверс заодно, чтоб 2 раза не вставать
1
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
29.07.2016, 14:00
Цитата Сообщение от _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 раз реже другой, это еще не повод для игнорирования попыток ее решения.
2
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
29.07.2016, 14:00

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
29
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru