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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Правило хорошо тона при Рендеринге !? http://www.cyberforum.ru/cpp-beginners/thread777792.html
Появился такой вопрос, правильно ли запихивать указатель на устройство рендеринга в объект. Class Object { //.. D3DXDEVICE * pVideoCard; //.. } или схожий пример для обертки над DirectX Class Object {
C++ Build Error 1. откуда взялся? в универе простые задачки решали письменно, решила попробовать прогу создать по одной из простеньких что было. вроде все правильно,но выбило ошибку Build Error 1 . в чем причина?? #include<stdio.h> #include<stdlib.h> int main() {int i; int R; for (i=0;i>=255;i++) R=rand; for (i=0;i>=255;i++) printf("yniversal'noe mno*estvo: %d", R); http://www.cyberforum.ru/cpp-beginners/thread777785.html
C++ Чётные числа на нечётных местах
Доброго времени суток, уважаемые форумчане! Уже больше 10 часов бьюсь на задачей, но почти безрезультатно. Перерыла весь интернет, и здесь искала, но того что мне нужно не нашла. Задание такое: Дано n, a. Определить количество чётных чисел, стоящих на нечётных местах. Помогите, пожалуйста, две задачи из трёх сделала, если эту не сделаю - отчисление из колледжа :( Я смогла вывести массив на...
C++ Что за входным параметром DynamicArray(long s = 10): size(s), count(0)?
: size(s), count(0) объясните что это ? //конструкторы DynamicArray(long s = 10): size(s), count(0) { //<=======================что это? p = new T; if(!p) cout << "Ошибка при создании массива" << endl; }
C++ сумма ряда 1,3,5,7 http://www.cyberforum.ru/cpp-beginners/thread777752.html
# include <stdio.h> # include <conio.h> #include <iomanip> int main () { setlocale(LC_ALL,"Russian"); int i,n,s=0; printf ("\n Введите количество первых нечетных чисел которые необходимо просумировать n=\n"); scanf ("%d",&n);
C++ функция для нахождения длины связного списка Помогите написать функцию для нахождения длины связного списка. реализуйте функцию итеративно и рекурсивно. getLength (NULL) должен возвращать 0. class List { public: int value; List* next; }; int getLength(List* list) подробнее

Показать сообщение отдельно
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2779 / 1425 / 393
Регистрация: 18.10.2014
Сообщений: 2,620
04.03.2016, 22:15     Одномерный массив. Циклический сдвиг вправо
Эта задача всплывала здесь не раз (Переставить первые М-элементов в конец массива) и, в частности, является одной из классических задач программирования (подробно разобрана у Бентли в "Жемчужинах программирования"). Разумеется, задача тривиальна если разрешается использовать дополнительный массив. Задача становится интереснее, если дополнительного массива использовать не разрешается.

У задачи три классических решения
1. Популярное и общеизвестное решение через три переворота (упоминается ValeryS выше в ответе #5)
2. Более хитрое решение через обмен неравных блоков (несложно видеть, что циклический сдвиг - это то же самое, что обмен местами двух блоков длины K и N-K)
3. Жонглирование - индивидуальная перестановка элементов сразу на правильные места со следованием циклов в перестановке

Отдельно стоит заметить, что в С++ задача уже решена стандартным алгоритмом 'std::rotate', т.е. с этой точки зрения делать ничего не надо. В частности, в стандартной библиотеке MSVC++ 'std::rotate' для итераторов с произвольным доступом реализуется именно через три вызова 'std::reverse'. GCC, насколько я помню, делает это по-другому.

А вот, например, возможная реализация по методу 2

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename IT> void swap_blocks(IT b, IT m, IT e)
{ // В диапазоне [b, e) обмениваем местами поддиапазоны [b, m) и [m, e)
  if (m == b)
    return;
 
  while (e != m)
  {
    size_t n_left = m - b, n_right = e - m;
    if (n_left <= n_right)
    {
      std::swap_ranges(b, m, e - n_left);
      e -= n_left;
    }
    else
    {
      std::swap_ranges(b, b + n_right, m);
      b += n_right;
    }
  }
}
Теперь требуемый сдвиг вправо запросто реализуется как 'swap_blocks(A, A + N - K, A + N)'

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
  const int N = 8;
  const int K = 3;
  int A[N] = { 1, 2, 3, 4, 5, 6, 7, 8 };
 
  std::copy(std::begin(A), std::end(A), std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
 
  swap_blocks(A, A + N - K, A + N);
 
  std::copy(std::begin(A), std::end(A), std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
}
 
Текущее время: 10:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru