Как сделать сдвиг массива влево в паскале
Добавил пользователь Дмитрий К. Обновлено: 06.08.2024
Рассматриваются три алгоритма циклического сдвига, в том числе алгоритм Дуга Макилроя (Doug Mcllroy) зеркального отражения.
| Вложение | Размер |
|---|---|
| massivy_ciklicheskie_sdvigi_i_szhatie.ppt | 507 КБ |
Предварительный просмотр:
Подписи к слайдам:
Одномерные массивы Циклические сдвиги, сжатие
Алгоритм циклического сдвига на k позиций I способ определить сколько раз необходимо произвести одноэлементный сдвиг k := k mod n; k раз применить одноэлементный сдвиг Алгоритм одноэлементного сдвига . Запомнить в дополнительной ячейке первый (или последний) элемент массива Сдвинуть все элементы влево (вправо) На последнее (первое) место записать тот, который запоминали.
Сдвиг вправо и влево Program test; Uses crt; С onst n =10 ; Var a:array[1..n] of integer; i,j,t,k:integer; Begin clrscr; < ввод массива >K:=k mod n; For j:=1 to k do Begin t:=a[n]; for i:=n downto 2 do a[i]:=a[i-1]; A[1]:=t; End; < Вывод массива >End. Program test; Uses crt; С onst n=10; Var a:array[1..n] of integer; i,j,t,k:integer; Begin clrscr; < ввод массива >K:=k mod n; For j:=1 to k do Begin t:=a[1]; for i:=1 to n-1 do a[i]:=a[i+1]; A[n]:=t; End; < Вывод массива >End.
III способ отобразить элементы массива( 1 , k ) отобразить элементы массива ( k +1 , n ) отобразить элементы массива ( 1 , n )
1. Элемента с индексом -1 просто нет. Туда писать нельзя. Крайний левый array[0] . 2. Его надо запомнить, а в конце (после цикла) записать вместо последнего ( array[size-1] ).
2 ответа 2
Циклический сдвиг вправо
Циклический сдвиг влево
Рекомендует компилятору локализовать эту переменную в регистре процессора для ускорения работы с ней. Можно, есно, без него.
У меня при тестировании массив за пределы вылазит (( Program returned 139 during test. void arrayShiftLeft(int array[], int size) < int temp = array[0]; for ( int i = 0; i
"Эта манишка, эти завязочки от кальсон. Проще надо одеваться, Паниковский!" Что-то вы, братцы, декрементами себя измучили. Действительно, вначале запоминаем a[0].
Все, и никаких декрементов :)
Понимаете, очень часто в программировании одна и та же проблема может быть решена несколькими способами, часто по эффективности не различающимися. Что выбрать - дело вкуса. И не нужно свои вкусы навязывать другим.
Конкретно - о каких. Я протестировал свой код, все работает. То, что Вы написали, - то же самое, только немного другими словами.
Всё ещё ищете ответ? Посмотрите другие вопросы с метками массивы c или задайте свой вопрос.
Связанные
Похожие
Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.
дизайн сайта / логотип © 2022 Stack Exchange Inc; материалы пользователей предоставляются на условиях лицензии cc by-sa. rev 2022.1.27.41279
Сайт о том, как стать программистом и как с этим жить потом
Написать метод, которому на вход подается одномерный массив и число n (может быть положительным, или отрицательным), при этом метод должен сместить все элементы массива на n позиций. Для усложнения задачи нельзя пользоваться вспомогательными массивами.
Разумеется, после первых подходов многие студенты находят следующее довольно логичное и вполне корректное решение. Оно весьма популярно на различных сайтах, описывающих циклический сдвиг. Суть его в том, что любой сдвиг можно представить в качестве n сдвигов на 1 ячейку. Сдвиг на 1 ячейку довольно просто реализуется циклом. В итоге, если изобразить это Java-методом, получается примерно такой метод:
public static int [ ] shiftArray ( int [ ] incomingArray, int shift ) <
if ( shift != 0 ) <
// Любой сдвиг больше длины массива можно оптимизировать до меньшего сдвига
// через деление по модулю
int finalShift ;
if ( shift > incomingArray. length ) <
shift = Math . abs ( shift % incomingArray. length ) ;
>
else <
finalShift = shift ;
>
// в зависимости от знака сдвига движение будет происходить
// слева направо при положительном сдвиге
// справа налево при отрицательном
if ( shift > 0 ) <
for ( int n = 0 ; n shift ; n ++ ) <
// убираем первый элемент в буфер, а на его место ставим хвостовой элемент
int buffer = incomingArray [ 0 ] ;
myArray [ 0 ] = incomingArray [ incomingArray. length - 1 ] ;
// циклично сдвигаем весь массив
for ( int j = 1 ; j incomingArray. length - 1 ; j ++ ) <
incomingArray [ incomingArray. length - j ] = incomingArray [ incomingArray. length - j - 1 ] ;
>
// ставим буферный элемент в 1 ячейку
incomingArray [ 1 ] = buffer ;
>
>
else if ( shift 0 ) <
for ( int i = 0 ; i > shift ; n -- ) <
int buffer = incomingArray [ incomingArray. length - 1 ] ;
incomingArray [ incomingArray. length - 1 ] = incomingArray [ 0 ] ;
for ( int j = 1 ; j incomingArray. length - 1 ; j ++ ) <
incomingArray [ j - 1 ] = incomingArray [ j ] ;
>
incomingArray [ incomingArray. length - 2 ] = buffer ;
>
>
>
Хочу отметить, что такое решение имеет место, и оно применимо. Но мы же решаем алгоритмическую задачу, поэтому неплохо бы поговорить о том, какую сложность будет иметь приведенный алгоритм. Если опустить процесс вычислений буферных элементов и обмена ими между ячейками, то сложность алгоритма сводится к O(N * M), где N — размер входного массива, а M — величина сдвига. Очевидно, что для |M| = 1 (т.е. M = -1 или M = 1) сложность снизится до O(N). Это частный случай.
Теперь давайте подумаем, что же тут не так. На самом деле, если мы знаем величину сдвига (а мы её знаем), то вполне можно вычислить, какой элемент будет следующим. Это говорит о том, что можно создать жонглирующий алгоритм следующего вида:
- Получаем нулевой элемент и кладем его в буфер
- Начинаем цикл от 0 до длины массива включительно (это обусловлено тем, что в момент, когда мы дойдём до последнего элемента, он будет помещен в буфер, из которого его надо восстановить на месте нулевого элемента, чем полностью закольцевать сдвиг)
- Дальше мы меняем местами элементы, исходя из размера шага. Например, для шага 3 и массива длиной 7 мы сначала поменяем элементы 0, 3, 6. Затем — 1, 4, 2. И так далее.
Если рассмотреть наборы изменяемых элементов, то мы увидим, что количество таких наборов, внутри которых мы будем итеративно менять местами элементы, будет равно наименьшему общему делителю для размера массива и размера сдвига. К примеру, для массива из 12 элементов при сдвиге 3 мы будем иметь три набора смещаемых элементов.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
- 1, 4, 7, 10
- 2, 5, 8, 11
- 3, 6, 9, 12
4 5 6 7 8 9 10 11 12 1 2 3
Поскольку эти наборы независимы, то при перестановке в них элементов местами мы не нарушим общий порядок следования элементов.
В реализации нужно учитывать и то, что сдвиг может идти как влево, так и вправо.
Теперь мы можем написать реализацию нашего алгоритма
public class moves
public static void main ( String [ ] args ) <
int [ ] in1 = < 5 , 3 , 7 , 2 , 9 , 13 , 42 >;
int [ ] out1 = moves ( in1, - 2 ) ;
printOut ( out1 ) ;
int [ ] in2 = < 5 , 3 , 7 , 2 , 9 , 13 , 42 , 43 , 45 , 46 >;
int [ ] out2 = moves ( in2, 2 ) ;
printOut ( out2 ) ;
int [ ] in3 = < 5 , 3 , 7 , 2 , 9 , 13 , 42 , 143 >;
int [ ] out3 = moves ( in3, 5 ) ;
printOut ( out3 ) ;
int [ ] in4 = < 5 , 3 , 7 , 2 , 9 , 42 , 43 , 45 , 46 >;
int [ ] out4 = moves ( in4, 0 ) ;
printOut ( out4 ) ;
>
/**
* Main method, shifts array
* @param incoming - user array
* @param delta - shift value
* @return int[] result array
*/
static int [ ] moves ( int [ ] incoming, int delta ) <
int currentIndex, movedIndex, buffer ;
for ( int i = 0 ; i greatestCommonDivisor ( delta, incoming. length ) ; i ++ ) <
buffer = incoming [ i ] ;
if ( delta > 0 ) <
while ( true ) <
movedIndex = currentIndex + delta ;
if ( movedIndex >= incoming. length )
movedIndex = movedIndex - incoming. length ;
if ( movedIndex == i )
break ;
incoming [ currentIndex ] = incoming [ movedIndex ] ;
currentIndex = movedIndex ;
>
>
else if ( delta 0 ) <
while ( true ) <
movedIndex = currentIndex + delta ;
if ( movedIndex 0 )
movedIndex = incoming. length + movedIndex ;
if ( movedIndex == i )
break ;
incoming [ currentIndex ] = incoming [ movedIndex ] ;
currentIndex = movedIndex ;
>
>
incoming [ currentIndex ] = buffer ;
>
/**
* Simple printout
* @param incomingArray user array
*/
public static void printOut ( int [ ] incomingArray ) <
for ( int item : incomingArray ) <
System . out . print ( item + " " ) ;
>
/**
* Finding the GCD in recoursive function
* @param a - first element
* @param b - second element
* @return int GCD
*/
static int greatestCommonDivisor ( int a, int b )
<
if ( b == 0 )
return a ;
else
return greatestCommonDivisor ( b, a % b ) ;
>
>
Как и в прошлый раз, мы можем пренебречь расчетами индексов. И в конечном итоге мы получаем сложность алгоритма, которая зависит исключительно от длины массива, т.е. O(N). И эта сложность не будет меняться в зависимости от исключительных ситуаций, что как минимум не хуже предыдущего алгоритма, а для сдвигов, больших, чем единица, лучше.
Надеюсь, приведенные измышления будут для Вас полезны. Буду рад критике и комментариям!
Дочитавшим до конца, картинка де мотиватор 🙂
var
a: array [1..6] of integer;
i,n,k:integer;
\u00a0 begin
\u00a0\u00a0\u00a0\u00a0 writeln('\u041c\u0430\u0441\u0441\u0438\u0432:');
\u00a0\u00a0\u00a0\u00a0 for i:=1 to 6 do
\u00a0\u00a0\u00a0\u00a0 begin
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 a[i]:= random(15)+2;
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 write(a[i],' ');
\u00a0\u00a0\u00a0\u00a0 end;
\u00a0\u00a0\u00a0\u00a0 writeln;
\u00a0\u00a0\u00a0\u00a0 n:=6;
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 k:=a[1];
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 for i:=1 to n-1 do
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 begin
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 a[i]:=a[i+1];
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 end;
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 a[n]:=k;
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 writeln('\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:');
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 for i:=1 to n do
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 write(a[i],' '); \u00a0 end. ">]" data-testid="answer_box_list">
var
a: array [1..6] of integer;
i,n,k:integer;
begin
writeln('Массив:');
for i:=1 to 6 do
begin
a[i]:= random(15)+2;
write(a[i],' ');
end;
writeln;
n:=6;
k:=a[1];
for i:=1 to n-1 do
begin
a[i]:=a[i+1];
end;
a[n]:=k;
writeln('Результат:');
for i:=1 to n do
write(a[i],' '); end.
Новые вопросы в Информатика
Каким свойством не обладает формальный исполнитель? 1. имеет собственную систему команд 2. понимает смысл команд 3. может работать в разных режимах 4. … решает круг определенных задач
Даны ящики, которые вмещают 5 кг, 10 кг и 15 кг яблок. Необходимо выяснить, сколько ящиков разного размера понадобится для того, чтобы распределить 10 … 0 кг яблок. язык пайтон
Вставка элементов в одномерный массив
Вставка одного элемента
Вставлять элемент можно до или после данного элемента, номер этого элемента можно вводить с клавиатуры или искать при определённых условиях. Рассмотрим вставку элемента после элемента с данным номером, номер этого элемента будем вводить с клавиатуры.
Вставка элемента после элемента с заданным номером.
Пример
Вставить число 100 после пятого элемента массива.
Пусть k - это номер элемента, после которого мы должны вставить элемент х (k и х будем вводить с клавиатуры). Тогда вставка осуществляется следующим образом:
| первые k элементов массива остаются без изменений; |
| все элементы, начиная с (k+1)-го, необходимо сдвинуть на один назад; |
| на место (k+1)-го элемента записываем значение х, то есть после k-го элемента массива. |
Рассмотрим на конкретном примере. Пусть дан следующий одномерный массив из N (N = 10) элементов: 3, -12, 5, 14, 27, -6, 1, -34, 10, -15.
Надо вставить 100 после пятого элемента массива. Тогда получим следующий массив:
3, -12, 5, 14, 27, 100, -6, 1, -34, 10, -15.
Таким образом, в массиве стало 11 элементов, то есть массив надо определять на N+1 элемент:
Type myarray = Array[1..n+1] Of Integer.
Кроме того, в программе необходимо выводить массив два раза, сначала первые N элементов массива, а затем все N+1 элементы. Поэтому будем использовать уже известную процедуру Print1.
Составим теперь основную программу с использованием новой процедуры Insert1 (k1, x1, m), которой передаются: k1 - номер элемента, после которого надо вставить, х1 - число, которое вставляем, m - массив, в котором делаем преобразования. Кроме того, сдвиг элементов будем начинать с последнего элемента.
Program Example_42;
Const n = 10; dd = 51;
Type myarray = Array[1.. n+1] Of Integer;
Var A : myarray;
x, k : Integer;
Procedure Init2 (Var m: myarray);
Procedure Print1 (n1: Integer; m: myarray);
Procedure Insert1 (k1,x1: Integer; Var m: myarray);
Var i; Integer;
Begin
For i:=n Downto k1+1 Do
m[i+1]:= m[i]
m[k1+1]:= x1;
End;
Рассмотрим выполнение программы по шагам выполнения. Пусть начальное заполнение массива сделано и имеется массив из десяти целых чисел:
3, -12, 5, 14, 27, -6, 1, 34, 10, -15.
Кроме того, пусть первый вывод массива тоже уже сделан и на экране появились 10 целых чисел. Введём номер элемента, после которого будем вставлять новый элемент и сам этот новый элемент:
k = 5 - будем вставлять после пятого элемента;
x = 100 - вставлять будем число 100.
Итак, получили новый массив, который уже имеет N+1 элемент, его и будем выводить на экран. На экране всё это будет выглядеть следующим образом:
3 -12 5 14 27 -6 1 34 10 -15
Номер элемента, после которого вставлять, и вставляемое число
3 -12 5 14 27 100 -6 1 34 10 -15
Вставка элемента перед данным
Пример
Вставить число 100 перед пятым элементом массива.
Эта вставка немногим отличается от предыдущей: в первой сдвигали назад все элементы, стоящие после k-го, то есть с (k+1)-го, а на его место записывали новый элемент, в этой - сдвигаем все элементы с k-го, а затем на его место записываем новый,
Пусть дан следующий одномерный массив из N (N=10) элементов:
3, -12, 5, 14, 27, -6, 1, 34, 10, -15.
Надо вставить 100 перед пятым элементом массива. Тогда получим следующий массив:
3, -12, 5, 14, 100, 27, -6, 1, 34, 10, -15.
Изменим программу для этой вставки:
Program Example_43;
Const n = 10; dd = 51;
Type myarray = Array[1..n+1] Of Integer;
Var A : myarray;
x, k : Integer;
Procedure Init2(Var m: myarray);
Procedure Print1(n1: Integer; m: myarray );
Procedure Insert2(k1, x1: Integer; Var m: myarray );
Var i : Integer;
Begin
For i:=n Downto k1 Do
m[i+1]:=m[i];
m[k1]:=x1;
End;
Begin
Init2(A);
Print1 (n,A);
Writeln ('Номер элемента, перед которым вставлять,');
Writeln (' u вставляемое число ');
Readln (k,x);
Insert2(k,x,A);
Print1(n+1,A);
Readln;
End.
Рассмотрим на том же примере пошаговое выполнение программы. Пусть начальное заполнение массива сделано и имеется массив из десяти целых чисел:
3, -12, 5, 14, 27, -6, 1, -34, 10, -15.
Кроме того, пусть первый вывод мвссива тоже уже сделан и на экране появились 10 целых чисел. Введём номер элемента, перед которым будем вставлять новый элемент и сам этот новый элемент:
| k = 5 - будем вставлять перед пятым элементом; |
| x = 100 - вставляемое число 100. |
Итак, получили новый массив, который уже имеет N+1 элемент, его и будем выводить на экран. На экране всё это будем выглядеть следующим образом:
3 -12 5 14 27 -6 1 -34 10 -15
Номер элемента, перед которым вставлять, и вставляемое число
3 -12 5 14 100 27 -6 1 -34 10 -15
Вставка нескольких элементов
Предположим, что необходимо вставлять не один элемент в массив, а по одному элементу после всех элементов с заданным свойством. Рассмотрим эту вставку на примере вставки после всех элементов с заданным свойством.
Пример
Вставить число после всех элементов массива, кратных 3.
Первое, на что необходимо обратить внимание - это описание массива: на сколько элементов может увеличиться массив? Максимальное количество элементов, после которых будет вставлен новый элемент, совпадает с количеством элементов массива, так как может случиться, что все элементы массива отвечают заданному свойству. Поэтому массив может увеличиться в два раза (это его самая большая размерность), а значит, соответствующее ему описание будет следующим:
Type myarray = Array[1..2*n] Of Integer;
Второе. Если мы будем просматривать элементы массива с начала и вставлять новый после элемента заданным свойством, то номер последнего элемента каждый раз может меняться, кроме того, будем просматриваться и новый (вставленный) элемент и его необходимо будет пропускать ("перепрыгивать"), поэтому решение будет не очень эффективным.
Лучше всего просматривать массив, начиная с конца, тогда вставляемый элемент мешать не будет. Кроме того, номер последнего элемента можно будет знать (если знать, сколько элементов вставлено на данный момент), при этом просмотр будет последовательным от N-го до 1-го.
Program Example-44;
Const n = 10; dd = 51;
Type myarray = Array[1.. 2*n] Of Integer;
Var A : myarray;
x, k, i :Integer;
Procedure Init2(Var m: myarray);
Procedure Print1(n1: Integer; m: myarray);
Begin
Init2 (A) Print1(n,A);
Writeln(' Введите вставляемое число');
Readln(x);
k: = 0;
For i:= n Downto 1 Do
If A[i] Mod 3=0 Then Insert3 (i,x,A);
Print1 (n+k,A);
Readln;
End.
Рассмотрим выполнение программы в пошаговом режиме. Будем вставлять после всех элементов, кратных 3, число 100, то есть х = 100. Пусть дан массив из 10-ти элементов:
3, -12, 5, 14, 27, -6, 1, 34, 10, -15.
Пусть так же первый вывод массива сделан. Трассировка примера приведена в таблице 5.
Читайте также: