Как циклически сдвинуть массив в C#?
Здравствуйте! Не могли бы помочь, как циклически сдвинуть массив в C# на k элементов?
существуют два принципиально разный подхода (сейчаc лень, но можете порыться, на форуме я как-то приводил примеры кода, правда, на Delphi):
— однопроходный. Каждый элемент сразу сдвигаем на столько элементов, на сколько надо. Это очень эффективно. Но тут возникают сложности, т.к. достатночно муторно вычислить, какой элемент с каким надо менять местами.
— циклический. Любой сдвиг на K элементов это К сдвигов на один элемент. А сдвиг на один элемент — это алгоритмически крайне просто.
Вот пример решения на основании второго подхода:
const int n = 5 ;
int [ ] a = new int [ n ] { 1 , 2 , 3 , 4 , 5 } ;
Console. WriteLine ( «Исходный массив:» ) ;
for ( int i = 0 ; i < n; ++i )
Console. Write ( » \t » + a [ i ] ) ;
Console. WriteLine ( ) ;
Console. WriteLine ( «Введите k» ) ;
int k = Convert. ToInt16 ( Console. ReadLine ( ) ) ;
for ( int i = 0 ; i < k; ++i )
{
int aLast = a [ n -1 ] ;
for ( int j = n -1 ; j> 0 ; j— )
a [ j ] = a [ j -1 ] ;
a [ 0 ] = aLast;
}
Console. WriteLine ( «Новый массив: » ) ;
for ( int i = 0 ; i < n; ++i )
Console. Write ( » \t » + a [ i ] ) ;
Console. WriteLine ( ) ;
Console. ReadKey ( ) ;
Похожие статьи
- Работа с двумерными массивами (матрицами) средствами Delphi
- Динамические массивы Turbo Pascal
- Использование нетипизированного указателя для передачи массива
- Запись данных в файла из массив с помощью FileStream
- Как перемешать массив, заполненный английским алфавитом?
- Как создать двумерный динамический массив?
- Класс, который ищет совпадение в массиве
- Умножение матриц
- Получить из текста строки, и занести их в массив
- Как использовать цвета в массиве
Как сдвинуть массив влево c
Циклический сдвиг массива влево — довольно понятная задача когда внутри массива из n элементов нужно взять кусок начиная с i-ой позиции (и до конца) и сдвинуть его в начало массива.
Например, если n=8, a i=3, то массив символов «abcdefgh» должен будет превратиться в «defghabc». Дело в том, что алгоритм решения такой казалось бы ничем не выдающейся задачки играет большую роль, например, во всяческих различного рода текстовых редакторах, в каждом из которых сейчас уже обязательно присутствует такая возможность, как выделение мышкой текста и последующего его перемещения как есть в любое другое место редактируемого файла.
И вот если использовать очевидное решение в лоб: использовать n-элементный вспомогательный массив и сделав n шагов завершить всю перестановку — мы натыкаемся на дополнительный расход памяти, пропорционально растущий от объема этого выделенного, перемещаемого текста. Представьте себе, если выделяется текст большого объема, например, в миллион символов и перемещается. В этом случае весь этот миллион символов(байт) — а это уже мегабайт, будет занимать ценное место в оперативной памяти.
Поэтому было бы неплохо найти решение, которое осуществляло бы эту перестановку без дополнительного расхода памяти, по-крайней мере, чтобы этот расход не рос пропорционально объему сдвигаемого фрагмента.
И такое решение существует, а точнее даже целых 3 интересных и проверенных опытом алгоритма, которые позволяют обойтись лишь несколькими дополнительными переменными и завершить весь сдвиг не за n шагов, а всего лишь за время, пропорциональное n.
По книге Джона Бентли:
«Жемчужины программирования»
«. В некоторых языках программирования операция циклического сдвига является элементарной (то есть выполняется одним оператором). Для нас важно, что циклический сдвиг соответствует обмену соседних блоков памяти разного размера: при перемещении фрагмента текста с помощью мыши из одного места файла в другое осуществляется именно эта операция. Ограничения по времени и объему памяти существенны для многих подобных приложений.
Можно попытаться решить задачу, копируя первые i элементов массива х во временный массив, сдвигая оставшиеся n-i элементов влево на i позиций, а затем копируя данные из временного массива обратно в основной массив на последние i позиций. Однако данная схема использует i дополнительных переменных, что требует дополнительной памяти. Другой подход заключается в том, чтобы определить функцию, сдвигающую массив влево на один элемент (за время, пропорциональное n), а потом вызывать ее i раз, но такой алгоритм будет отнимать слишком много времени.
Алгоритм #1: последовательный обмен
Решение проблемы с указанными ограничениями на использование ресурсов потребует написать более сложный алгоритм циклического сдвига массива.
Одним из вариантов решения будет введение дополнительной переменной. Элемент х[0] помещается во временную переменную t, затем x[i] помещается в x[0],x[2*i] — в х[1] и так далее (перебираются все элементы массива х с индексом по модулю n), пока мы не возвращаемся к элементу х [0], вместо которого записывается содержимое переменной t, после чего процесс завершается. Если i = 3, а n = 12, этот этап проходит следующим образом (рис. 2.2):
Если при этом не были переставлены все имеющиеся элементы, процедура повторяется, начиная с х[1] и так далее, до достижения конечного результата:
псевдокод: массив циклический сдвиг ссылка
Алгоритм #2: перестановка блоков
Можно предложить и другой алгоритм, который возникает из рассмотрения задачи с другой точки зрения. Циклический сдвиг массива х сводится фактически к замене ab на bа, где а — первые i элементов х, a b — оставшиеся элементы. Предположим, что а короче b. Разобьем b на bleft и bright, где bright содержит i элементов (столько же, сколько и а). Поменяем местами а и bright, получим brightbleftа. При этом а окажется в конце массива — там, где и полагается. Поэтому можно сосредоточиться на перестановке bright и bleft. Эта задача сводится к начальной, поэтому алгоритм можно вызывать рекурсивно. Программа, реализующая этот алгоритм, будет достаточно красивой , но она требует аккуратного написания кода, а оценить ее эффективность непросто:
псевдокод: массив, циклический сдвиг через перестановку блоков ссылка
Алгоритм #3: переворотами
Задача кажется сложной, пока вас не осенит озарение («ага!»): итак, нужно преобразовать массив ab в bа. Предположим, что у нас есть функция reverse, переставляющая элементы некоторой части массива в противоположном порядке. В исходном состоянии массив имеет вид ab. Вызвав эту функцию для первой части, получим а r b (прим. редактора:а r — это модифицированная часть a, к которой применили фукнцию перестановки reverse). Затем вызовем ее для второй части: получим а r b r . Затем вызовем функцию для всего массива, что даст (а r b r ) r , а это в точности соответствует bа. Посмотрим, как будет такая функция действовать на массив abcdefgh, который нужно сдвинуть влево на три элемента:
псевдокод: Сдвиг через функцию перестановки reverse ссылка
Дуг Макилрой (Doug Mcllroy) предложил наглядную иллюстрацию циклического сдвига массива из десяти элементов вверх на пять позиций (рис. 2.3); начальное положение: обе руки ладонями к себе, левая над правой:
Код, использующий функцию переворота, оказывается эффективным и малотребовательным к памяти, и настолько короток и прост, что при его реализации сложно ошибиться.
Б. Керниган и П. Дж. Плоджер пользовались именно этим методом для перемещения строк в текстовом редакторе в своей книге (В. Kernighan, P. J. Plauger, Software Tools in Pascal, 1981). Керниган пишет, что эта функция заработала правильно с первого же запуска, тогда как их предыдущая версия, использовавшая связный список, содержала несколько ошибок. Этот же код используется в некоторых текстовых редакторах, включая тот, в котором я впервые набрал настоящую главу. Кен Томпсон (Ken Thompson) написал этот редактор с функцией reverse в 1971 году, и он утверждает, что она уже тогда была легендарной.
Циклический сдвиг массива влево и вправо
Напишите программу, которая в массиве целых чисел длины m+n, рассматриваемом как соединение двух его частей – начала длины m и конца длины n, обменивает начало и конец, не используя дополнительных массивов.
- элемент 4 (начало второго массива) надо поставить на место элемента 1 (начало первого массива). Значит после перемещения – мы потеряем число 1.
- хотелось бы сразу записать число 1 на место во втором массиве, но его правильное место занимает число 6 и при попытке записать – мы сотрем его…
Идеи как это делать:
1) можно попробовать сразу поставить на место первый массив, переместив на его место элементы второго. В результате получится что-то такое:
6 7 8 4 5 1 2 3
теперь остается переставить m и m-n элементов внутри второго массива, но при рассмотрении на этом примере становится ясно, что эта задача не проще чем изначальная – возникают ровно те же проблемы.
2) перестановка частей массива – это циклический сдвиг массива на m элементов влево. Опишем функцию, выполняющую сдвиг на 1 элемент влево и вызовем ее m раз.
Для сдвига массива на одни элемент влево:
- запомним значение первого элемента;
- сдвинем все остальные влево, по очереди;
- запишем в конец массива значение первого элемента (ведь сдвиг циклический);
#include #include #include #include void read_array(int n, int** values) < for (int i = 0; i < n; ++i) < printf("values[%d] = ", i); scanf("%d", &((*values)[i])); >> void print_array(int n, int* values) < for (int i = 0; i < n; ++i) < printf("values[%d] = %d\n", i, values[i]); >> void shift_left(int *a, int n) < if (0 == n) return; int first = a[0]; for (int i = 1; i < n; ++i) a[i-1] = a[i]; a[n-1] = first; >void shift_left_on(int *a, int n, int shift_size) < for (int i = 0; i < shift_size; ++i) < shift_left(a, n); >> int main()
Задача (сдвиг вправо):
Напишите программу, которая вводит с клавиатуры массив целых чисел и циклически сдвигает элементы массива вправо на k позиций. Число k вводится с клавиатуры.
Если есть массив из 5 элементов 1 2 3 4 5 , то сдвиг вправо на 2 позиции это 4 5 1 2 3 .
Не сложно заметить, что такой же результат получился бы при сдвиге влево на 3 позиции.
Итого, сдвиг в массиве из N элементов вправо на K позиций даст тот же результат, что сдвиг влево на N-K позиций.
Кроме того, можно учесть циклический сдвиг, то есть если в этом же массиве выполнить сдвиг на 6 , 11 или 101 позиций – то результат будет аналогичен сдвигу на 1 позицию.
void shift_right_on(int *a, int n, int shift_size) < shift_size = shift_size % n; shift_size = n - shift_size; for (int i = 0; i < shift_size; ++i) < shift_left(a, n); >>
Результаты работы программы:
Сдвинуть элементы массива на k позиций
пусть а — это массив для сдвига, а size_array — его размер и пусть массив будет целочисленный.
int tmp1, tmp2; tmp1 = a[0]; tmp2 = a[1]; for (int i = 0; i < size_array-2; i++) a[i] = a[i+2]; a[size_array-2] = tmp1; a[size_array-1] = tmp2; если нужно сдвинуть на какое то другое кол-во позиций, то обычно применяют последовательный сдвиг. Ещё можно завести массив, равный сдвигу, скопировать туда начальные элементы (memcpy) остальные элементы сдвинуть (memmove) и скопировать с дополнительно массива назад элементы в конец исходного массива.,
UPD: здесь есть очень интересные объяснения, как делать сдвиг.