Ю4.31

Задача

Циклический сдвиг. Осуществить циклический сдвиг элементов массива [latex]T\left(n\right)[/latex] на  [latex]m[/latex] позиций влево, то есть получить массив: [latex]t_{m+1},\ldots t_{n}, t_{1},\ldots t_{m}[/latex].
ри этом необязательно [latex]m<n[/latex].

Тесты:

изначальный массив сдвиг (m) результат комментарий
1 2 3 4 5 6 7 2 3 4 5 6 7 1 2 пройден
1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 пройден
1 2 3 4 5 6 7 10 4 5 6 7 1 2 3 пройден

 

 

Ссылка на код.

Код на Java:

 

 

Денисова Ольга
Денисова Ольга

Latest posts by Денисова Ольга (see all)

6 thoughts on “Ю4.31

  1. Почему Вы ничего не объясняете?
    Есть несколько подходов к решению задачи в зависимости от того, сколько дополнительной памяти можно выделить. Например, если можно выделить объём дополнительной памяти для второго такого же массива, то получим самый быстрый алгоритм с пересылками:

    Можете изменить алгоритм так, чтобы использовать только одну дополнительную ячейку памяти?

    • Вы зачли работу, внесите пожалуйста в таблицу результат.

      Алгоритм, который позволяет сделать циклически сдвиг вообще без переменных и дополнительных массивов:

      void reverse(int *arr , int n){
      for (int i=0; i > n >> m;
      int dt=m % n ;
      int *T = new int[n];

      for (int i = 0; i < n; i++) T[i]=i;

      reverse(T,dt);
      reverse(T+dt,n-dt);
      reverse(T,n);

      // print
      for (int i = 0; i < n; i++) cout << T[i] << "/";
      }

      • Тут только обрывки кода.

        На будущее лучше вставлять код с тегом pre. Тогда будет красивое форматирование.

        Без дополнительной памяти сделать конечно можно. Нужно использовать операцию xor (exclude or) или какие-то свойства типа данных к которому принадлежат элементы массива. Но лучше не надо.
        Одной ячейки памяти вполне достаточно чтобы обойтись обычной пересылкой данных (присваиванием).

  2. Ну понятно зачем Вам константа ARRAY_SIZE в C++ версии. Вы не захотели передавать размер массива в функции. Но в Java для переданного массива ведь можно узнать его размер, верно? Соответственно методы shiftArray и printArray (заметили, как должны выглядеть имена?) должны узнавать размер переданного параметра array. Кстати параметр array_size тоже переименуйте в arraySize.

Добавить комментарий