Стандартные задачи на одномерные массивы: различия между версиями

Материал из Вики проекта PascalABC.NET
Перейти к навигацииПерейти к поиску
Нет описания правки
Строка 11: Строка 11:
end;
end;
</source>
</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/01_Print.pas Ссылка на алгоритм в среде WDE]


=== №2. Заполнение массива случайными числами ===
=== №2. Заполнение массива случайными числами ===
Строка 21: Строка 19:
     Result[i] := random(100);
     Result[i] := random(100);
end;</source>
end;</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/02_CreateRandomArray.pas Ссылка на алгоритм в среде WDE]


=== №3. Инвертирование массива ===
=== №3. Инвертирование массива ===
Строка 31: Строка 27:
     Swap(a[i],a[n-i-1]);
     Swap(a[i],a[n-i-1]);
end; </source>
end; </source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/03_Invert.pas Ссылка на алгоритм в среде WDE]


=== №4. Поиск элемента по заданному значению ===
=== №4. Поиск элемента по заданному значению ===
Строка 58: Строка 52:
   else Result := i;
   else Result := i;
end;</source>
end;</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/04_Find.pas Ссылка на алгоритм в среде WDE]


=== №4a. Поиск с барьером ===
=== №4a. Поиск с барьером ===
Строка 73: Строка 65:
   else Result := i;
   else Result := i;
end;</source>
end;</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/04_FindWithBarrier.pas Ссылка на алгоритм в среде WDE]


=== №5. Минимальный элемент и его индекс ===
=== №5. Минимальный элемент и его индекс ===
Строка 88: Строка 78:
     end;
     end;
end;</source>
end;</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/05_MinElem.pas Ссылка на алгоритм в среде WDE]


==Сдвиги, вставка, удаление==
==Сдвиги, вставка, удаление==
Строка 99: Строка 87:
   a[a.Length-1] := default(T);
   a[a.Length-1] := default(T);
end;</source>
end;</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/06_ShiftLeft.pas Ссылка на алгоритм в среде WDE]


=== №7. Сдвиг вправо ===
=== №7. Сдвиг вправо ===
Строка 111: Строка 97:
end;
end;
</source>
</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/07_ShiftRight.pas Ссылка на алгоритм в среде WDE]


=== №8. Циклический сдвиг вправо ===
=== №8. Циклический сдвиг вправо ===
Строка 124: Строка 108:
end;
end;
</source>
</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/08_CycleShiftRight.pas Ссылка на алгоритм в среде WDE]


=== №9. Удаление k-того ===
=== №9. Удаление k-того ===
Строка 139: Строка 121:
end;
end;
</source>
</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/09_Delete.pas Ссылка на алгоритм в среде WDE]


=== №10. Вставка на k-тое место ===
=== №10. Вставка на k-тое место ===
Строка 153: Строка 133:
end;
end;
</source>
</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/10_Insert.pas Ссылка на алгоритм в среде WDE]


== Слияние упорядоченных и бинарный поиск в упорядоченном массиве==
== Слияние упорядоченных и бинарный поиск в упорядоченном массиве==
Строка 183: Строка 161:
end;
end;
</source>
</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/11_Merge.pas Ссылка на алгоритм в среде WDE]


=== №12. Поиск в упорядоченном массиве ===
=== №12. Поиск в упорядоченном массиве ===
Строка 203: Строка 180:
end;
end;
</source>
</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/12_BinarySearch.pas Ссылка на алгоритм в среде WDE]


== Сортировка массивов ==
== Сортировка массивов ==
Строка 226: Строка 202:
end;
end;
</source>
</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/13_SortByChoice.pas Ссылка на алгоритм в среде WDE]


=== №14. Пузырьковая сортировка ===
=== №14. Пузырьковая сортировка ===
Строка 240: Строка 215:
end;
end;
</source>
</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/14_BubbleSort.pas Ссылка на алгоритм в среде WDE]


====Способ №2(оптимизация)====
====Способ №2(оптимизация)====
Строка 260: Строка 234:
end;
end;
</source>
</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/14(2)_BubbleSort2.pas Ссылка на алгоритм в среде WDE]


=== №15. Сортировка вставками ===
=== №15. Сортировка вставками ===
Строка 279: Строка 252:
end;
end;
</source>
</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/15_SortByInsert.pas Ссылка на алгоритм в среде WDE]


== Использование процедурных типов в задачах на массивы ==
== Использование процедурных типов в задачах на массивы ==
Строка 311: Строка 283:
end;
end;
</source>
</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/16_FindPred.pas Ссылка на алгоритм в среде WDE]


=== №17. Количество по условию ===
=== №17. Количество по условию ===
Строка 323: Строка 294:
end;
end;
</source>
</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/17_CountPred.pas Ссылка на алгоритм в среде WDE]


=== №18. Условный минимум ===
=== №18. Условный минимум ===
Строка 339: Строка 309:
end;  
end;  
</source>
</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/18_MinElemPred.pas Ссылка на алгоритм в среде WDE]


=== №19. Удаление по условию ===
=== №19. Удаление по условию ===
Строка 356: Строка 325:
end;
end;
</source>
</source>
[http://pascalabc.net/WDE/?file=AlgStudents/Arrays/19_DeleteAll.pas Ссылка на алгоритм в среде WDE]
----
----


© Буцев Виктор, Белоусько Тихон, Зуев Семен, Гончаров Владислав, Батраков Михаил, Гаджиев Казанфар, Пак Владислав
© Буцев Виктор, Белоусько Тихон, Зуев Семен, Гончаров Владислав, Батраков Михаил, Гаджиев Казанфар, Пак Владислав

Версия от 22:04, 29 октября 2017

Стандартные задачи на одномерные массивы

Простейшие алгоритмы

№1. Вывод массива

procedure Println<T>(a: array of T);
begin
  foreach x: T in a do
    write(x, ' ');
  writeln;
end;

№2. Заполнение массива случайными числами

function CreateRandomArray(n: integer): array of integer;
begin
  SetLength(Result, n);
  for var i := 0 to n - 1 do
    Result[i] := random(100);
end;

№3. Инвертирование массива

procedure Invert<T>(a: array of T);
begin
  var n := a.Length;
  for var i:=0 to n div 2 - 1 do
    Swap(a[i],a[n-i-1]);
end;

№4. Поиск элемента по заданному значению

// С помощью for
function Find<T>(a: array of T; x: T): integer;
begin
  Result := -1;
  for var i := 0 to a.Length - 1 do
    if a[i] = x then
    begin
      Result := i;
      break;
    end;
end;

// С помощью while
function FindWhile<T>(a: array of T; x: T): integer;
begin
  var n := a.Length;
  var i := 0;
  while (i<n) and (a[i]<>x) do
    i += 1;
  if i=n then
    Result := -1
  else Result := i;
end;

№4a. Поиск с барьером

function FindWithBarrier<T>(a: array of T; n: integer; x: T): integer;
begin
  Assert((0 < n) and (n < a.Length));
  a[n] := x; // барьерный элемент равен разыскиваему
  var i := 0;
  while a[i]<>x do
    i += 1;
  if i=n then
    Result := -1
  else Result := i;
end;

№5. Минимальный элемент и его индекс

procedure MinElem(a: array of integer; var min: integer; var minind: integer);
begin
  min := a[0]; 
  minind := 0;
  for var i:=1 to a.Length-1 do
    if a[i]<min then
    begin
      min := a[i];
      minind := i;
    end;
end;

Сдвиги, вставка, удаление

№6. Сдвиг влево

procedure ShiftLeft<T>(a: array of T);
begin
  for var i:=0 to a.Length-2 do
    a[i] := a[i+1];
  a[a.Length-1] := default(T);
end;

№7. Сдвиг вправо

procedure ShiftRight<T>(a: array of T);
begin
  for var i := a.Length-1 downto 1 do
    a[i] := a[i-1];
  a[0] := default(T);
end;

№8. Циклический сдвиг вправо

procedure CycleShiftRight<T>(a: array of T);
begin
  var v := a[a.Length-1];
  for var i := a.Length downto 1 do
    a[i] := a[i-1];
  a[0] := v;
end;

№9. Удаление k-того

procedure Delete<T>(a: array of T; var n: integer; k: integer);
begin
  Assert((0<=k) and (k<n))
  Assert((0<=n) and (n<=a.Length));
  for var i := k to n-2 do
    a[i] := a[i+1];
  a[n-1] := default(T);
  n -= 1;
end;

№10. Вставка на k-тое место

procedure Insert<T>(a: array of T; var n: integer; k: integer; value: T);
begin
  Assert((0<=k) and (k<=n) and (n<a.Length));
  for var i := n-1 downto k do
    a[i+1] := a[i];
  a[k] := value;
  n += 1;
end;

Слияние упорядоченных и бинарный поиск в упорядоченном массиве

№11. Слияние двух упорядоченных в один упорядоченный

// a,b упорядочены по возрастанию
function Merge(a,b: array of real; na,nb: integer): array of real;
begin
  Assert((0 < na) and (na < a.Length));
  Assert((0 < nb) and (nb < b.Length));
  a[na] := real.MaxValue;
  b[nb] := real.MaxValue;
  var c := new real[na + nb];
  var ia := 0;
  var ib := 0;
  for var ic := 0 to na + nb - 1 do
    if a[ia]<b[ib] then
    begin
      c[ic] := a[ia];
      ia += 1;
    end
    else
    begin
      c[ic] := b[ib];
      ib += 1;
    end;
  Result := c;
end;

№12. Поиск в упорядоченном массиве

function BinarySearch(a: array of integer; x: integer): integer;
begin
  var k: integer;
  var i := 0;
  var j := a.Length-1;
  repeat
    k := (i+j) div 2;
    if x>a[k] then
      i := k + 1
    else j := k - 1;
  until (a[k]=x) or (i>j);
  if a[k]=x then
    Result := k
  else Result := -1;
end;

Сортировка массивов

№13. Сортировка выбором

procedure SortByChoice(a: array of integer);
begin
  for var i := 0 to a.Length - 2 do
  begin
    var min := a[i];
    var imin := i;
    for var j := i + 1 to a.Length - 1 do
      if a[j] < min then
      begin
        min := a[i];
        imin := j;
      end;
    a[imin] := a[i];
    a[i] := min;
  end;  
end;

№14. Пузырьковая сортировка

Способ №1

procedure BubbleSort(a: array of integer);
begin
  var n := a.Length;
  for var i := 0 to n - 2 do
    for var j := n - 1 downto i + 1 do
      if a[j] < a[j - 1] then
        Swap(a[j], a[j - 1]);
end;

Способ №2(оптимизация)

procedure BubbleSort2(a: array of integer);
begin
  var i := a.Length - 1;
  var q: boolean;
  repeat
    q := true;
    for var j := 0 to i - 1 do
      if a[j + 1] < a[j] then
      begin
        Swap(a[j + 1], a[j]);
        q := false;
      end;
    i -= 1;
  until q;  
end;

№15. Сортировка вставками

procedure SortByInsert(a: array of integer);
begin
  for var i := 1 to a.Length - 1 do 
  begin
    var x := a[i];
    var j := i - 1;
    while (j >= 0) and (x < a[j]) do
    begin
      a[j + 1] := a[j];
      j -= 1;
    end;
    a[j + 1] := x;
  end;
end;

Использование процедурных типов в задачах на массивы

Пусть сделаны следующие описания:

type IPredicate = function(x: integer): boolean;

// Примеры предикатов
function Even(x: integer): boolean;
begin
  result := not odd(x);
end;

function IsPositive(x: integer): boolean;
begin
  Result := x > 0;
end;

№16. Поиск по условию

function FindPred(a: array of integer; pred: IPredicate): integer;
begin
  var n := a.Length;
  var i := 0;
  while (i < n) and not pred(a[i]) do 
    i += 1;
  if i = n then
    Result := -1
  else Result := i;
end;

№17. Количество по условию

function CountPred(a: array of integer; pred: IPredicate): integer;
begin
  Result := 0;
  for var i := 0 to a.Length - 1 do
    if pred(a[i]) then
      Result += 1;
end;

№18. Условный минимум

procedure MinElemPred(a: array of integer; pred: IPredicate; var min, imin: integer);
begin
  min := Integer.MaxValue;
  imin := -1;
  for var i := 0 to a.length - 1 do 
    if pred(a[i]) and (a[i] < min) then
    begin
      min := a[i];
      imin := i;
    end;
end;

№19. Удаление по условию

procedure DeleteAll(a: array of integer; var n: integer; pred: IPredicate);
begin
  Assert((0 < n) and (n <= a.Length));
  var j := 0;
  for var i := 0 to n - 1 do
    if not pred(a[i]) then
    begin
      a[j] := a[i];
      j += 1;
    end;
  n := j;
end;

© Буцев Виктор, Белоусько Тихон, Зуев Семен, Гончаров Владислав, Батраков Михаил, Гаджиев Казанфар, Пак Владислав