Programming stuff
Есть ряд способов сдвинуть массив влево на N элементов. Можно взять и сделать N сдвигов по одному элементу, получив квадратичную сложность. Можно создать целевой массив по размеру исходного и вычислить положение каждого элемента после сдвига. Хорошо, но скорость линейна, затраты по памяти — тоже.
Если чутка подумать, то можно придумать реализацию, которая мутирует массив и дает линейную скорость и константные затраты по памяти. Но есть один очень элегантный способ – из 3-х строк на основе чудо Span of T из System.Memory:
public static void RotateLeft(int[] input, int direction) < input.AsSpan(0, direction).Reverse(); input.AsSpan(direction).Reverse(); input.AsSpan().Reverse(); >
Идея такая: чтобы сдвинуть массив из K элементов на N элементов влево, нужно перевернуть первые N элементов в массиве, затем последние K — N -1 элементов, а затем перевернуть весь массив:
// direction == 2, input.Length == 7 input.AsSpan(0, direction).Reverse(); // [2][1][3][4][5][6][7] input.AsSpan(direction).Reverse(); // [2][1][7][6][5][4][3] input.AsSpan().Reverse();// [3][4][5][6][7][1][2]
Получается два прохода по массиву, но зато с читабельностью решения все очень ОК.
26 комментариев:
Справедливости ради, хочу отметить, что это циклический сдвиг влево. Ответить Удалить
Не совсем понял мысль. Да, это одна из реализаций циклического сдвига влево. Просто, ИМХО, одна из самых кратких и выразительных. Удалить
nit: Мне показалось, что Vasya всего лишь хотел справедливо заметить, что слово «сдвиг» в заголовке и теле поста лучше бы заменить на «циклический сдвиг». Удалить
В своё время этот фокус произвёл на меня большое впечатление. минут 20 рисовал на листике пытаясь понять как этот трюк работает 🙂
Он же, но чуть с большим wow-эффектом (IMHO) используется в задачке Reverse Words: когда необходимое переставить слова в предложении в обратном порядке. Например: «Michael Jordan» => «Jordan Michael». Необходимо сделать «реверс» каждого слова и потом реверс всей строки целиком, что в конечном итоге даёт практически линейную сложность. Ответить Удалить
О! Отличный трюк.
З.Ы. Сложность-то линейная, просто коэффициент равен 2. Удалить
Фокус интересный. Но по поводу читабельности — не соглашусь. Оно же крайне не очевидно. Но элегантный, да Ответить Удалить
Ну такое. по этой теории каждый второй алгоритм можно зафукать :))) Удалить
Так гораздо понятнее, чем циклический сдвиг врукопашную.
Мне кажется, что без комментария с небольшим примером решение неочевидно. Но оно читаемо, поскольку состоит из 3 строк. После же того, как прогнан в голове/дебагере один пример, то решение садится в голове прочно. Удалить
Почему «затем последние K — N -1 элементов», если необходимо перевернуть K — N последних элементов? Ответить Удалить
Off-by-one error:) Удалить
В «Жемчужинах программирования» читал что-то подобное. я уже не помню, но там с помощью реверса решалась задача. Интуитивно восстановил алгоритм: Сложность 4N, дополнительной памяти не требуется.
Пример:
исходный массив: 1234567 сдвиг вправо на 3
Сдвиг массива
Сдвинуть элементы массива в указанном направлении (влево или вправо) и на указанное число шагов. Освободившиеся ячейки заполнить нулями. Выводить массив после каждого шага.
Если массив сдвигается на один шаг влево, то на место элемента с индексом i записывается тот элемент, который находится на месте i+1. То есть на место текущего элемента записывается следующий за ним. В последнюю ячейку массива записывать нечего. По условию задачи туда следует записать число 0.
Таким образом, сдвиг массива на один шаг влево — это цикл от первого элемента до предпоследнего включительно, в теле которого происходит запись значения из следующей ячейки в текущую ячейку ( arr[i] := arr[i+1] ). В предпоследнюю ячейку записывается последний элемент. После цикла присваивается 0 в последнюю ячейку массива.
Если массив сдвигается на один шаг вправо, то его следует «перебирать» с конца. На место элемента i присваивается стоящий перед ним (i-1). В освободившуюся первую ячейку записывается ноль.
Сдвиг массива на один шаг вправо — это цикл от последнего элемента до второго включительно, в теле которого происходит запись значения из предыдущей ячейки в текущую ( arr[i] := arr[i-1] ). После цикла в первую ячейку массива записывается ноль.
Количество шагов сдвига определяется внешним циклом.
Алгоритм решения данной задачи можно описать так:
- Запросить у пользователя количество шагов сдвига и направление. Условиться, что если вводится отрицательное целое, то сдвиг выполняется влево на указанное абсолютное значение, если вводится положительное число, то сдвиг вправо.
- Заполнить исходный массив и вывести его на экран.
- Выполнять внешний цикл столько раз, сколько шагов было указано.
- Если было введено отрицательное число, то выполнить цикл от первого элемента до предпоследнего, перезаписав в нем значение каждой очередной ячейки на значение последующей. Записать в последнюю ячейку 0.
- Иначе, выполнить цикл от последнего элемента до второго, записывая в каждую текущую ячейку значение предыдущей. В первую ячейку записать 0.
- Вывести на экран текущий массив.
Посмотреть вариант кольцевого сдвига (когда вышедший за границу элемент массива записывается с другой его стороны) можно здесь.
Pascal
сдвиг массива паскаль
const N = 9;
var
arr: array[1..N] of integer;
qty: integer;
i,j: byte;
begin
readln(qty);
for i:=1 to N do begin
arr[i] := i*100 + i*10 + i;
write(arr[i]:4);
end; writeln;
for j:=1 to abs(qty) do begin
if qty > 0 then begin
for i:=N downto 2 do
arr[i] := arr[i-1];
arr[1] := 0;
end
else begin
for i:=1 to N-1 do
arr[i] := arr[i+1];
arr[N] := 0;
end;
for i:=1 to N do
write(arr[i]:4);
writeln;
end;
end.
Пример(ы) выполнения программы:
Сдвиг влево:
-4
111 222 333 444 555 666 777 888 999
222 333 444 555 666 777 888 999 0
333 444 555 666 777 888 999 0 0
444 555 666 777 888 999 0 0 0
555 666 777 888 999 0 0 0 0
Сдвиг вправо:
5
111 222 333 444 555 666 777 888 999
0 111 222 333 444 555 666 777 888
0 0 111 222 333 444 555 666 777
0 0 0 111 222 333 444 555 666
0 0 0 0 111 222 333 444 555
0 0 0 0 0 111 222 333 444Язык Си
#include < stdio.h>
#define N 9
main() int arr[N], qty, i, j;
scanf("%d",&qty);
for (i=0; i < N; i++) arr[i] = (i+1)*100 + (i+1)*10 + (i+1);
printf("%4d",arr[i]);
>
printf("\n");
for (j=0; j < abs(qty); j++) if (qty < 0) for (i=0; i < N-1; i++)
arr[i] = arr[i+1];
arr[N-1] = 0;
> else for (i=N-1; i>0; i--)
arr[i] = arr[i-1];
arr[0] = 0;
>
for (i=0; i < N; i++)
printf("%4d",arr[i]);
printf("\n");
>
>Python
сдвиг массива python (питон)
qty = int(input())
N = 9
a = []
for i in range(1,N+1):
b = 100*i + 10*i + i
a.append(b)
print("%4d" % b, end='')
print()
for j in range(abs(qty)):
if qty < 0:
for i in range(N-1):
a[i] = a[i+1]
a[N-1] = 0
elif qty > 0:
for i in range(N-1,0,-1):
a[i] = a[i-1]
a[0] = 0
for i in a:
print("%4d" % i, end='')
print()КуМир
алг
нач
цел N=9
цел таб массив[1:N]
цел шаги, i, j
ввод шаги
нц для i от 1 до N
массив[i] := i*100+i*10+i
вывод массив[i]:4
кц
вывод нс
нц для j от 1 до iabs(шаги)
если шаги > 0 то
нц для i от N до 2 шаг -1
массив[i] := массив[i-1]
кц
массив[1] := 0
иначе
нц для i от 1 до N-1
массив[i] := массив[i+1]
кц
массив[N] := 0
все
нц для i от 1 до N
вывод массив[i]:4
кц
вывод нс
кц
конВ программе используется форматированный вывод, который доступен только в версии 2.x.
Basic-256
input qty
N = 9
dim arr(N)
for i=0 to N-1
arr[i] = (i+1)*100 + (i+1)*10 + (i+1)
print arr[i] + " ";
next i
print
for j=1 to abs(qty)
if qty < 0 then
for i=0 to N-2
arr[i] = arr[i+1]
next i
arr[N-1] = 0
else
for i=N-1 to 1 step -1
arr[i] = arr[i-1]
next i
arr[0] = 0
endif
for i=0 to N-1
print arr[i] + " ";
next i
print
next jСдвинуть элементы массива на 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: здесь есть очень интересные объяснения, как делать сдвиг.
Циклически сдвинуть элементы массива влево
Элементы массива циклически сдвинуть на k позиций влево
Помогите пожалуйста написать программу. понимаю что все должно быть оч легко, но. В С++: 1. Дан.Сдвинуть циклически элементы одномерного массива на k позиций влево
Тема и есть условие задачи. Сам же я застопорился на написании алгоритма сдвига :- #include.
Все элементы массива X(30) циклически сдвинуть на n позиций влево
Все элементы массива X(30) циклически сдвинуть на n позиций влево при помощи указателейЭлементы линейного массива сдвинуть циклически на две позиции влево
Дорогие форумчане помогите с переводом с pascal в C++ < of integer; i,j:integer; .
13663 / 10580 / 6322
Регистрация: 18.12.2011
Сообщений: 28,248
См. ссылки внизу страницы
Например Элементы массива циклически сдвинуть на k позиций влево
Неэпический
17849 / 10617 / 2049
Регистрация: 27.09.2012
Сообщений: 26,686
Записей в блоге: 1
Регистрация: 18.04.2020
Сообщений: 90
а код никак не может быть короче?
6578 / 4563 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
Сообщение от Ste 
а код никак не может быть короче?
1 2 3 4 5 6 7
const size_t N = 4; int arr[N] = {1, 2, 3, 4}; int x = arr[0]; for (size_t i = 1; i N; ++i) arr[i - 1] = arr[i]; arr[N - 1] = x;
7428 / 5021 / 2891
Регистрация: 18.12.2017
Сообщений: 15,692
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесьСдвинуть элементы массива циклически на M влево, перевернуть нечетные строки и посчитать простые числа
Доброго времени суток. Помогите составить программу. Заранее благодарен. Тут несколько условий, не.Сформировать массив десятичных цифр числа А. Элементы массива цифр сдвинуть циклически влево на 1 позицию
дано целое десятичное число А. Сформировать массив десятичных цифр числа А. Элементы массива цифр.Указатели: сдвинуть элементы циклически на 1 позицию влево
Условие задачи: Заполните случайным образом одномерный массив из n элементов и здвиньте элементы.Одномерный массив. Сдвинуть элементы циклически на n позиций влево
Ввести одномерный статический массив из k чисел. Сдвинуть элементы массива циклически на n позиций.Сдвинуть все элементы последовательности циклически на k позиций влево
1. Дано целое число. Если число отрицательное, то необходимо вывести все четные числа, начиная со.Циклически сдвинуть все элементы матрицы влево в строках, которые начинаются с положительного элемента
(((Там какая та задача из темы Массивов))) Для решения этой задачи: В матрице Z(4,5) сдвинуть все.