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

Материал из Вики проекта PascalABC.NET
Перейти к навигацииПерейти к поиску
Нет описания правки
 
(не показаны 24 промежуточные версии 3 участников)
Строка 1: Строка 1:
[[Стандартные задачи на циклы]]
__NOTOC__
== Стандартные задачи на циклы ==
=== [[Стандартные задачи на циклы|Программы]] ===
==== [[Стандартные задачи на циклы#Простейшие алгоритмы|Простейшие алгоритмы]] ====
# [[Стандартные задачи на циклы#№1. Сумма вводимых целых чисел|Сумма вводимых целых чисел]]
# [[Стандартные задачи на циклы#№2. Произведение целых чисел|Произведение целых чисел]]
# [[Стандартные задачи на циклы#№3. Двойной факториал n!!=n*(n-2)*(n-4)*...*2 (или 1)|Двойной факториал n!!=n*(n-2)*(n-4)*...*2 (или 1)]]
# [[Стандартные задачи на циклы#№4. Сколько нечетных среди n введенных|Сколько нечетных среди n введенных]]
# [[Стандартные задачи на циклы#№5. Защита от неверного ввода|Защита от неверного ввода]]
# [[Стандартные задачи на циклы#№6. Табулирование функции f(x) на отрезке в точках, разбивающих отрезок на N частей|Табулирование функции f(x) на отрезке в точках, разбивающих отрезок на N частей]]
# [[Стандартные задачи на циклы#№6a. Решение, использующее while. Погрешность округления и вычислительная погрешность|Решение, использующее while. Погрешность округления и вычислительная погрешность]]


[[Стандартные задачи на одномерные массивы]]
==== [[Стандартные задачи на циклы#Рекуррентные соотношения|Рекуррентные соотношения]] ====
# [[Стандартные задачи на циклы#№7. Вывод 10 первых степеней двойки|Вывод 10 первых степеней двойки]]
# [[Стандартные задачи на циклы#№8. Вывод всех двухзначных чисел, кратных 5|Вывод всех двухзначных чисел, кратных 5]]
# [[Стандартные задачи на циклы#№9. Вывод n первых чисел Фибоначчи|Вывод n первых чисел Фибоначчи]]
# [[Стандартные задачи на циклы#№10. Найти НОД(A,B), используя алгоритм Евклида:|Найти НОД(A,B), используя алгоритм Евклида]]
# [[Стандартные задачи на циклы#№11. Найти сумму цифр целого положительного числа m|Найти сумму цифр целого положительного числа m]]


==== [[Стандартные задачи на циклы#Максимумы и минимумы|Максимумы и минимумы]] ====
# [[Стандартные задачи на циклы#№12. Найти max из введенных чисел|Найти max из введенных чисел]]
# [[Стандартные задачи на циклы#№12a. Найти min, удовлетворяющее условию p(x)|Найти min, удовлетворяющее условию p(x)]]


==== [[Стандартные задачи на циклы#Суммирование рядов (конечных и бесконечных)|Суммирование рядов (конечных и бесконечных)]] ====
# [[Стандартные задачи на циклы#№13. Вычислить Σ(i=1..n) a^i/i!|Вычислить Σ(i=1..n) a^i/i!]]
# [[Стандартные задачи на циклы#№13a. Вычислить Σ(i=1..∞) (-1)^i * a^i/i!|Вычислить Σ(i=1..∞) (-1)^i * a^i/i!]]


==== [[Стандартные задачи на циклы#Поиск значения|Поиск значения]] ====
# [[Стандартные задачи на циклы#№14. Есть ли среди введенных число k?|Есть ли среди введенных число k?]]
# [[Стандартные задачи на циклы#№14b. Есть ли среди введенных число k? (то же с использованием while)|Есть ли среди введенных число k? (то же с использованием while)]]
# [[Стандартные задачи на циклы#№15. Является ли число N>0 простым?|Является ли число N>0 простым?]]


= Стандартные задачи на одномерные массивы =
==== [[Стандартные задачи на циклы#Другие алгоритмы|Другие алгоритмы]] ====
# [[Стандартные задачи на циклы#№16. Разложение числа на простые множители|Разложение числа на простые множители]]
# [[Стандартные задачи на циклы#№17. Вычисление значения многочлена в точке x по схеме Горнера|Вычисление значения многочлена в точке x по схеме Горнера]]
# [[Стандартные задачи на циклы#№18. Дана непрерывная на отрезке функция f(x), имеющая на отрезке ровно один корень. Найти его методом половинного деления|Дана непрерывная на отрезке функция f(x), имеющая на отрезке ровно один корень. Найти его методом половинного деления]]


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


=== №1. Вывод массива ===
== Стандартные задачи на одномерные массивы ==
<source lang="pascal">procedure Println<T>(a: array of T; delim: string := ' ');
=== [[Стандартные задачи на одномерные массивы|Программы]] ===
begin
==== [[Стандартные задачи на одномерные массивы#Простейшие алгоритмы|Простейшие алгоритмы]] ====
  foreach x: T in a do
# [[Стандартные задачи на одномерные массивы#№1. Вывод массива|Вывод массива]]
    write(x, delim);
# [[Стандартные задачи на одномерные массивы#№2. Заполнение массива случайными числами|Заполнение массива случайными числами]]
  writeln;
# [[Стандартные задачи на одномерные массивы#№3. Инвертирование массива|Инвертирование массива]]
end;
# [[Стандартные задачи на одномерные массивы#№4. Поиск элемента по заданному значению|Поиск элемента по заданному значению]]
</source>
# [[Стандартные задачи на одномерные массивы#№4a. Поиск с барьером|Поиск с барьером]]
# [[Стандартные задачи на одномерные массивы#№5. Минимальный элемент и его индекс|Минимальный элемент и его индекс]]


[http://pascalabc.net/WDE/?shared=DaZzz/Arrays/1.pas Ссылка на алгоритм в среде WDE]
==== [[Стандартные задачи на одномерные массивы#Сдвиги, вставка, удаление|Сдвиги, вставка, удаление]] ====
# [[Стандартные задачи на одномерные массивы#№6. Сдвиг влево|Сдвиг влево]]
# [[Стандартные задачи на одномерные массивы#№7. Сдвиг вправо|Сдвиг вправо]]
# [[Стандартные задачи на одномерные массивы#№8. Циклический сдвиг вправо|Циклический сдвиг вправо]]
# [[Стандартные задачи на одномерные массивы#№9. Удаление k-того|Удаление k-того]]
# [[Стандартные задачи на одномерные массивы#№10. Вставка на k-тое место|Вставка на k-тое место]]


=== №2. Заполнение массива случайными числами ===
==== [[Стандартные задачи на одномерные массивы#Слияние упорядоченных и бинарный поиск в упорядоченном массиве|Слияние упорядоченных и бинарный поиск в упорядоченном массиве]] ====
<source lang="pascal">procedure CreateRandomArray(var a: array of integer; n: integer);
# [[Стандартные задачи на одномерные массивы#№11. Слияние двух упорядоченных в один упорядоченный|Слияние двух упорядоченных в один упорядоченный]]
begin
# [[Стандартные задачи на одномерные массивы#№12. Поиск в упорядоченном массиве|Поиск в упорядоченном массиве]]
  SetLength(a,n);
  for var i:=0 to n-1 do
    a[i] := random(100);
end;</source>


[http://pascalabc.net/WDE/?shared=DaZzz/Arrays/2.pas Ссылка на алгоритм в среде WDE]
==== [[Стандартные задачи на одномерные массивы#Сортировка массивов|Сортировка массивов]] ====
# [[Стандартные задачи на одномерные массивы#№13. Сортировка выбором|Сортировка выбором]]
# [[Стандартные задачи на одномерные массивы#№14. Пузырьковая сортировка|Пузырьковая сортировка]]
## [[Стандартные задачи на одномерные массивы#Способ №1|Способ №1]]
## [[Стандартные задачи на одномерные массивы#Способ №2(оптимизация)|Способ №2]]
# [[Стандартные задачи на одномерные массивы#№15. Сортировка вставками|Сортировка вставками]]


=== №3. Инвертирование массива ===
==== [[Стандартные задачи на одномерные массивы#Использование процедурных типов в задачах на массивы|Использование процедурных типов в задачах на массивы]] ====
<source lang="pascal">procedure Invert<T>(a: array of T);
# [[Стандартные задачи на одномерные массивы#№16. Поиск по условию|Поиск по условию]]
begin
# [[Стандартные задачи на одномерные массивы#№17. Количество по условию|Количество по условию]]
  var n := a.Length;
# [[Стандартные задачи на одномерные массивы#№18. Условный минимум|Условный минимум]]
  for var i:=0 to n div 2 - 1 do
# [[Стандартные задачи на одномерные массивы#№19. Удаление по условию|Удаление по условию]]
    Swap(a[i],a[n-i-1]);
end; </source>
 
[http://pascalabc.net/WDE/?shared=DaZzz/Arrays/3.pas Ссылка на алгоритм в среде WDE]
 
=== №4. Поиск элемента по заданному значению ===
<source lang="pascal">// С помощью 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;</source>
 
[http://pascalabc.net/WDE/?shared=DaZzz/Arrays/4.pas Ссылка на алгоритм в среде WDE]
 
=== №5. Минимальный элемент и его индекс ===
<source lang="pascal">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;</source>
 
[http://pascalabc.net/WDE/?shared=DaZzz/Arrays/5.pas Ссылка на алгоритм в среде WDE]
 
==Сдвиги, вставка, удаление==
=== №6. Сдвиг влево ===
<source lang="pascal">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;</source>
 
[http://pascalabc.net/WDE/?shared=DaZzz/Arrays/6.pas Ссылка на алгоритм в среде WDE]
 
=== №7. Сдвиг вправо ===
<source lang="pascal">
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;
</source>
 
[http://pascalabc.net/WDE/?shared=PacVlad/ShiftRight.pas Ссылка на алгоритм в среде WDE]
 
=== №8. Циклический сдвиг вправо ===
<source lang="pascal">
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;
</source>
 
[http://pascalabc.net/WDE/?shared=PacVlad/CycleShiftRight.pas Ссылка на алгоритм в среде WDE]
 
=== №9. Удаление k-того ===
<source lang="pascal">
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;
</source>
 
[http://pascalabc.net/WDE/?shared=PacVlad/Delete.pas Ссылка на алгоритм в среде WDE]
 
=== №10. Вставка на k-тое место ===
<source lang="pascal">
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;
</source>
 
[http://pascalabc.net/WDE/?shared=PacVlad/Insert.pas Ссылка на алгоритм в среде WDE]
 
== Слияние упорядоченных и бинарный поиск в упорядоченном массиве==
=== №11. Слияние двух упорядоченных в один упорядоченный ===
<source lang="pascal">
// 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 integer[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;
</source>
 
=== №12. Поиск в упорядоченном массиве ===
<source lang="pascal">
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;
</source>
 
== Сортировка массивов ==
 
=== №13. Сортировка выбором ===
<source lang="pascal">
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;
</source>
 
=== №14. Пузырьковая сортировка ===
<source lang="pascal">
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;
 
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;
</source>
 
=== №15. Сортировка вставками ===
<source lang="pascal">
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;
</source>
 
== Использование процедурных типов в задачах на массивы ==
Пусть сделаны следующие описания:
<source lang="pascal">
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;
</source>
 
=== №16. Поиск по условию ===
<source lang="pascal">
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;
</source>
 
=== №17. Количество по условию ===
<source lang="pascal">
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;
</source>
 
=== №18. Условный минимум ===
<source lang="pascal">
procedure MinElemPred(a: array of integer; pred: IPredicate; var min, imin: integer);
begin
  min := Integer.MaxValue;
  imin := -1;
  for var i := 1 to a.length - 1 do
    if pred(a[i]) and (a[i] < min) then
    begin
      min := a[i];
      imin := i;
    end;
end;
</source>
 
=== №19. Удаление по условию ===
<source lang="pascal">
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;
</source>




Текущая версия от 23:46, 4 декабря 2010

Стандартные задачи на циклы

Программы

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

  1. Сумма вводимых целых чисел
  2. Произведение целых чисел
  3. Двойной факториал n!!=n*(n-2)*(n-4)*...*2 (или 1)
  4. Сколько нечетных среди n введенных
  5. Защита от неверного ввода
  6. Табулирование функции f(x) на отрезке в точках, разбивающих отрезок на N частей
  7. Решение, использующее while. Погрешность округления и вычислительная погрешность

Рекуррентные соотношения

  1. Вывод 10 первых степеней двойки
  2. Вывод всех двухзначных чисел, кратных 5
  3. Вывод n первых чисел Фибоначчи
  4. Найти НОД(A,B), используя алгоритм Евклида
  5. Найти сумму цифр целого положительного числа m

Максимумы и минимумы

  1. Найти max из введенных чисел
  2. Найти min, удовлетворяющее условию p(x)

Суммирование рядов (конечных и бесконечных)

  1. Вычислить Σ(i=1..n) a^i/i!
  2. Вычислить Σ(i=1..∞) (-1)^i * a^i/i!

Поиск значения

  1. Есть ли среди введенных число k?
  2. Есть ли среди введенных число k? (то же с использованием while)
  3. Является ли число N>0 простым?

Другие алгоритмы

  1. Разложение числа на простые множители
  2. Вычисление значения многочлена в точке x по схеме Горнера
  3. Дана непрерывная на отрезке функция f(x), имеющая на отрезке ровно один корень. Найти его методом половинного деления


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

Программы

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

  1. Вывод массива
  2. Заполнение массива случайными числами
  3. Инвертирование массива
  4. Поиск элемента по заданному значению
  5. Поиск с барьером
  6. Минимальный элемент и его индекс

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

  1. Сдвиг влево
  2. Сдвиг вправо
  3. Циклический сдвиг вправо
  4. Удаление k-того
  5. Вставка на k-тое место

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

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

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

  1. Сортировка выбором
  2. Пузырьковая сортировка
    1. Способ №1
    2. Способ №2
  3. Сортировка вставками

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

  1. Поиск по условию
  2. Количество по условию
  3. Условный минимум
  4. Удаление по условию


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

Источник — https://pascalabc.net/wiki/index.php?title=Алгоритмы_для_студентов&oldid=1978