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

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

03.02.2013, 01:46. Показов 19220. Ответов 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,875
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
Ответ Создать тему
Новые блоги и статьи
сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным?
anaschu 12.07.2026
Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров В текущей версии модели успешно реализован ключевой механизм. . .
сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию.
anaschu 12.07.2026
Анализ соответствия модели требованиям Реализованные компоненты: Механизм закисления почвы через протонную помпу Конкуренция между типами микориз pH как триггер сукцессии C/ P соотношение. . .
Сукцессия 26. Мат модель создана.
anaschu 12.07.2026
Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .
Решил проблему с ошибкой пагинации сообщений с сервера на алгоритме обхода дерева "Эстафета хвоста".
Hrethgir 12.07.2026
Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .
сукцессия 25. Хронология ошибок
anaschu 12.07.2026
# От 50-тонного гриба до устойчивого леса: хроника ошибок при построении модели вековой сукцессии микоризы ## О чём эта статья В процессе построения ОДУ-модели (система дифференциальных. . .
сукцессия 24. Промежуточное общее описание модели
anaschu 12.07.2026
Хендофф: модель АМ→ЭКМ сукцессии микоризы (ризосфера, 50 лет) Содержание проекта Симуляция вековой (50 лет) экологической сукцессии в почве леса Основные участники: АМ-гриб, ЭКМ-гриб,. . .
сукцессия 23. Более физиологичная физиология, более экологичная экология, более диффурные диффуры.
anaschu 12.07.2026
Что реально нашли и починили за эти 5 часов Правило Линдемана (КПД конверсии сахара в тело, kEff) — раньше 100% полученного углерода шло прямо в биомассу гриба; теперь только kEff=0. 5 (после. . .
сукцессия 22. От артефактов к физиологии: калибровка агентной модели грибной сукцессии для воспроизведения сезонной динамики и pH-плато
anaschu 11.07.2026
Аннотация В данной работе представлена калибровка агентной модели динамики грибных сообществ (fungal-succession), направленная на устранение нефизичных артефактов (коллапс биомассы, мгновенное. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru