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

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

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

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

03.02.2013, 01:46. Просмотров 6544. Ответов 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 и через побитовые операции. Вот так я пишу побитовый сдвиг ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Байт
Эксперт C
16061 / 10330 / 1540
Регистрация: 24.12.2010
Сообщений: 19,449
05.03.2016, 00:57 #16
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Я так сказал.
Убедили
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Мне действительно интересно.
Ну... Стоит только соетнести контекст решения простой задачи с вашими глубочайшими изысканиями... Понимаете, тема которую вы пытаетесь поднять, лежит совершенно в других плоскостях. Наверное, тема эта эта интересна. Но всему свое место, вы не находите?
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Однако фактически такой алгоритм ведет себя очень плохо с точки зрения локализации доступа к памяти и громко проигрывает как реверсивному, так и блочно-обменному алгоритму на современных кэшированных архитектурах (при достатчоном размере массива, разумеется).
Я неплохо знаю математику. И в программировании не совсем уж новичок. И книжечки читывал. Но в процитированной фразе понимаю 1 слово из трех. А уж связи между ними... Но тут же раздел - "для начинающих"
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3826 / 2084 / 532
Регистрация: 18.10.2014
Сообщений: 3,699
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);
}
И все.
0
Байт
Эксперт C
16061 / 10330 / 1540
Регистрация: 24.12.2010
Сообщений: 19,449
05.03.2016, 11:11 #18
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
если внимательно посмотреть на условие задачи,
Да чего на нее смотреть! Школьная чушь! Если на это смотреть, так и вообще говорить не о чем.
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
И все.
Ваша правда

Добавлено через 9 часов 46 минут
Цитата Сообщение от ValeryS Посмотреть сообщение
надо сдвинуть на три элемента влево
Как я понимаю, 3 - это величина сдвига, да? Но тогда это решение эквивалентно исходной задаче... Или я чего-то не допонял?
0
ValeryS
Модератор
6631 / 5039 / 466
Регистрация: 14.02.2011
Сообщений: 16,847
05.03.2016, 13:46 #19
Цитата Сообщение от Байт Посмотреть сообщение
Как я понимаю, 3 - это величина сдвига, да?
да
взято в качестве примера, а так любое число,в теме которую я указывал есть уже готовый код
Цитата Сообщение от Байт Посмотреть сообщение
Но тогда это решение эквивалентно исходной задаче...
в исходной задаче
Цитата Сообщение от LeShu Посмотреть сообщение
массива вправо на K позиций
а у меня 3
0
Cetych
6 / 6 / 2
Регистрация: 08.01.2016
Сообщений: 36
20.07.2016, 13:12 #20
Осталось код в голове смастерить=)
0
shilko2013
240 / 217 / 117
Регистрация: 02.04.2016
Сообщений: 827
Завершенные тесты: 1
20.07.2016, 13:37 #21
ValeryS, Ай молодца!!!
0
Байт
Эксперт C
16061 / 10330 / 1540
Регистрация: 24.12.2010
Сообщений: 19,449
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);
}
Писал на коленке. Мог ошибиться. Где-то на форуме мной опубликовано проверенное решение, но найти его не смог...
0
Байт
Эксперт C
16061 / 10330 / 1540
Регистрация: 24.12.2010
Сообщений: 19,449
21.07.2016, 23:08 #23
Прошу прощения у почтенной публики, коленка оказалась дырявой. И нагородил я в коде чуши.
Подождите, пожалуйста, до нормального рабочего рабочего стола и нормального интернета...
0
Байт
Эксперт C
16061 / 10330 / 1540
Регистрация: 24.12.2010
Сообщений: 19,449
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");
}
2
_Ivana
3149 / 1776 / 152
Регистрация: 01.03.2013
Сообщений: 4,981
Записей в блоге: 2
26.07.2016, 01:49 #25
При всем уважении к светлому имени этой задачи - я бы написал функцию/класс-обертку/итератор или как там это называется в выбранном языке реализации, который не будет переписывать память, а просто организует доступ к нужному элементу массива, рассматривая его как кольцевой буфер. Итого - имея один массив любой длины мы сразу получаем все его сдвиги на любое число элементов за О(1) по времени и самое забавное - все они будут лежать в памяти, занимаемой исходным массивом.
2
ValeryS
Модератор
6631 / 5039 / 466
Регистрация: 14.02.2011
Сообщений: 16,847
26.07.2016, 07:05 #26
_Ivana, идея конечно интересная
но бывают случаи когда нужно сдвигать именно физические данные, например, видеобуфер или данные в файле
0
Байт
Эксперт C
16061 / 10330 / 1540
Регистрация: 24.12.2010
Сообщений: 19,449
26.07.2016, 09:54 #27
_Ivana, идея вполне светлая. И, ИМХО,код должен получиться короче.

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

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

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

Цитата Сообщение от Байт Посмотреть сообщение
Переформулирую. Написать функцию F(A[], n, s, i) дающую i-тый элемент массива A, состоящего из n элементов, после циклического сдвига на s. Сам массив не трогать (считать, что он находится в памяти onle-read)
Ну и тогда любой сдвиг плюс опциональный реверс заодно, чтоб 2 раза не вставать
1
Байт
Эксперт C
16061 / 10330 / 1540
Регистрация: 24.12.2010
Сообщений: 19,449
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 раз реже другой, это еще не повод для игнорирования попыток ее решения.
2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.07.2016, 14:00
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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