Задача
Циклический сдвиг. Осуществить циклический сдвиг элементов массива [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 | пройден |
|
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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <iostream> #include <vector> using namespace std; const int ARRAY_SIZE = 7; int check_shift_position(int array_size, int m); void shift_array(int array[ARRAY_SIZE], int m); void print_array (int array[ARRAY_SIZE]); int main() { int array[ARRAY_SIZE]; for(int i =0; i < ARRAY_SIZE; i++) { cin >> array[i]; } int m = 0; cin >> m; m = check_shift_position(ARRAY_SIZE,m); cout << "Initial array = "; print_array(array); shift_array(array, m); return 0; } int check_shift_position(int array_size, int m) { if (array_size < m) { return m%array_size; } return m; } void shift_array(int array[ARRAY_SIZE], int m) { // Init shifted array int shifted_array[ARRAY_SIZE]; // Shift elements for [m + 1..n] to start; for (int i = m, k = 0; i < ARRAY_SIZE ; i++,k++) { shifted_array[k] = array[i]; } // Shift elements for [0..m] to the end; for (int i = 0, k = ARRAY_SIZE - m; i < m ; i++,k++) { shifted_array[k]= array[i]; } cout << "Shifted array = "; print_array(shifted_array); } void print_array (int array[ARRAY_SIZE]) { for (int i = 0; i < ARRAY_SIZE ; i++) { cout << array[i] << " "; } cout << endl; } |
Ссылка на код.
Код на Java:
|
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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
import java.util.*; import java.lang.*; import java.io.*; class Main { static int ARRAY_SIZE; public static void main (String[] args) { Scanner in = new Scanner(System.in); ARRAY_SIZE = 7; int array[] = new int [ARRAY_SIZE]; for(int i =0; i < ARRAY_SIZE; i++) { array[i] = in.nextInt(); } int m = 0; m = in.nextInt(); m = check_shift_position(ARRAY_SIZE,m); System.out.print("Initial array = "); print_array(array); shift_array(array, m); } static int check_shift_position(int array_size, int m) { if (array_size < m) { return m%array_size; } return m; } static void shift_array(int array[], int m) { // Init shifted array int shifted_array[] = new int [ARRAY_SIZE]; // Shift elements for [m + 1..n] to start; for (int i = m, k = 0; i < ARRAY_SIZE ; i++,k++) { shifted_array[k] = array[i]; } // Shift elements for [0..m] to the end; for (int i = 0, k = ARRAY_SIZE - m; i < m ; i++,k++) { shifted_array[k]= array[i]; } System.out.print("Shifted array = "); print_array(shifted_array); } static void print_array (int array[]) { for (int i = 0; i < ARRAY_SIZE ; i++) { System.out.print(array[i]+" "); } System.out.println(); } } |
Циклический сдвиг массива? Классическая задача на аккуратность. Особенно когда величина сдвига может превышать размер массива.
А массив-то где?
Исправлено.
Почему Вы ничего не объясняете?
Есть несколько подходов к решению задачи в зависимости от того, сколько дополнительной памяти можно выделить. Например, если можно выделить объём дополнительной памяти для второго такого же массива, то получим самый быстрый алгоритм с пересылками:
Можете изменить алгоритм так, чтобы использовать только одну дополнительную ячейку памяти?
Вы зачли работу, внесите пожалуйста в таблицу результат.
Алгоритм, который позволяет сделать циклически сдвиг вообще без переменных и дополнительных массивов:
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) или какие-то свойства типа данных к которому принадлежат элементы массива. Но лучше не надо.
Одной ячейки памяти вполне достаточно чтобы обойтись обычной пересылкой данных (присваиванием).
Ну понятно зачем Вам константа ARRAY_SIZE в C++ версии. Вы не захотели передавать размер массива в функции. Но в Java для переданного массива ведь можно узнать его размер, верно? Соответственно методы shiftArray и printArray (заметили, как должны выглядеть имена?) должны узнавать размер переданного параметра array. Кстати параметр array_size тоже переименуйте в arraySize.