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

Материал из Вики проекта PascalABC.NET
Перейти к навигацииПерейти к поиску
Нет описания правки
 
(не показано 109 промежуточных версий 4 участников)
Строка 1: Строка 1:
=== Вывод массива ===
__NOTOC__
<source lang="Delphi">procedure Println<T>(a: array of T; delim: string := ' ');
== Стандартные задачи на циклы ==
begin
=== [[Стандартные задачи на циклы|Программы]] ===
  foreach x: T in a do
==== [[Стандартные задачи на циклы#Простейшие алгоритмы|Простейшие алгоритмы]] ====
    write(x, delim);
# [[Стандартные задачи на циклы#№1. Сумма вводимых целых чисел|Сумма вводимых целых чисел]]
  writeln;
# [[Стандартные задачи на циклы#№2. Произведение целых чисел|Произведение целых чисел]]
end;
# [[Стандартные задачи на циклы#№3. Двойной факториал n!!=n*(n-2)*(n-4)*...*2 (или 1)|Двойной факториал n!!=n*(n-2)*(n-4)*...*2 (или 1)]]
</source>
# [[Стандартные задачи на циклы#№4. Сколько нечетных среди n введенных|Сколько нечетных среди n введенных]]
# [[Стандартные задачи на циклы#№5. Защита от неверного ввода|Защита от неверного ввода]]
# [[Стандартные задачи на циклы#№6. Табулирование функции f(x) на отрезке в точках, разбивающих отрезок на N частей|Табулирование функции f(x) на отрезке в точках, разбивающих отрезок на N частей]]
# [[Стандартные задачи на циклы#№6a. Решение, использующее while. Погрешность округления и вычислительная погрешность|Решение, использующее while. Погрешность округления и вычислительная погрешность]]


=== Заполнение массива случайными числами ===
==== [[Стандартные задачи на циклы#Рекуррентные соотношения|Рекуррентные соотношения]] ====
<source lang="Delphi">procedure CreateRandomArray(var a: array of integer;
# [[Стандартные задачи на циклы#№7. Вывод 10 первых степеней двойки|Вывод 10 первых степеней двойки]]
  n: integer);
# [[Стандартные задачи на циклы#№8. Вывод всех двухзначных чисел, кратных 5|Вывод всех двухзначных чисел, кратных 5]]
begin
# [[Стандартные задачи на циклы#№9. Вывод n первых чисел Фибоначчи|Вывод n первых чисел Фибоначчи]]
  SetLength(a,n);
# [[Стандартные задачи на циклы#№10. Найти НОД(A,B), используя алгоритм Евклида:|Найти НОД(A,B), используя алгоритм Евклида]]
  for var i:=0 to n-1 do
# [[Стандартные задачи на циклы#№11. Найти сумму цифр целого положительного числа m|Найти сумму цифр целого положительного числа m]]
    a[i] := random(100);
end;</source>


=== Инвертирование массива ===
==== [[Стандартные задачи на циклы#Максимумы и минимумы|Максимумы и минимумы]] ====
<source lang="Delphi">procedure Invert<T>(a: array of T);
# [[Стандартные задачи на циклы#№12. Найти max из введенных чисел|Найти max из введенных чисел]]
begin
# [[Стандартные задачи на циклы#№12a. Найти min, удовлетворяющее условию p(x)|Найти min, удовлетворяющее условию p(x)]]
  var n := a.Length;
  for var i:=0 to n div 2 - 1 do
    Swap(a[i],a[n-i-1]);
end; </source>


=== Поиск элемента по заданному значению ===
==== [[Стандартные задачи на циклы#Суммирование рядов (конечных и бесконечных)|Суммирование рядов (конечных и бесконечных)]] ====
<source lang="Delphi">// С помощью for
# [[Стандартные задачи на циклы#№13. Вычислить Σ(i=1..n) a^i/i!|Вычислить Σ(i=1..n) a^i/i!]]
function Find<T>(a: array of T; x: T): integer;
# [[Стандартные задачи на циклы#№13a. Вычислить Σ(i=1..∞) (-1)^i * a^i/i!|Вычислить Σ(i=1..∞) (-1)^i * a^i/i!]]
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;
# [[Стандартные задачи на циклы#№14. Есть ли среди введенных число k?|Есть ли среди введенных число k?]]
begin
# [[Стандартные задачи на циклы#№14b. Есть ли среди введенных число k? (то же с использованием while)|Есть ли среди введенных число k? (то же с использованием while)]]
  var n := a.Length;
# [[Стандартные задачи на циклы#№15. Является ли число N>0 простым?|Является ли число N>0 простым?]]
  var i := 0;
  while (i<n) and (a[i]<>x) do
    i += 1;
  if i=n then
    Result := -1
  else Result := i;
end;


// Поиск с барьером
==== [[Стандартные задачи на циклы#Другие алгоритмы|Другие алгоритмы]] ====
function FindWithBarrier<T>(a: array of T; n: integer; x: T): integer;
# [[Стандартные задачи на циклы#№16. Разложение числа на простые множители|Разложение числа на простые множители]]
begin
# [[Стандартные задачи на циклы#№17. Вычисление значения многочлена в точке x по схеме Горнера|Вычисление значения многочлена в точке x по схеме Горнера]]
  Assert((0 < n) and (n < a.Length));
# [[Стандартные задачи на циклы#№18. Дана непрерывная на отрезке функция f(x), имеющая на отрезке ровно один корень. Найти его методом половинного деления|Дана непрерывная на отрезке функция f(x), имеющая на отрезке ровно один корень. Найти его методом половинного деления]]
  a[n] := x;
  var i := 0;
  while a[i]<>x do
    i += 1;
  if i=n then
    Result := -1
  else Result := i;
end;</source>


=== Минимальный элемент и его индекс ===
<source lang="Delphi">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>


=== Сдвиг влево ===
== Стандартные задачи на одномерные массивы ==
<source lang="Delphi">procedure ShiftLeft<T>(a: array of T);
=== [[Стандартные задачи на одномерные массивы|Программы]] ===
begin
==== [[Стандартные задачи на одномерные массивы#Простейшие алгоритмы|Простейшие алгоритмы]] ====
  for var i:=0 to a.Length-2 do
# [[Стандартные задачи на одномерные массивы#№1. Вывод массива|Вывод массива]]
    a[i] := a[i+1];
# [[Стандартные задачи на одномерные массивы#№2. Заполнение массива случайными числами|Заполнение массива случайными числами]]
  a[a.Length-1] := default(T);
# [[Стандартные задачи на одномерные массивы#№3. Инвертирование массива|Инвертирование массива]]
end;</source>
# [[Стандартные задачи на одномерные массивы#№4. Поиск элемента по заданному значению|Поиск элемента по заданному значению]]
# [[Стандартные задачи на одномерные массивы#№4a. Поиск с барьером|Поиск с барьером]]
# [[Стандартные задачи на одномерные массивы#№5. Минимальный элемент и его индекс|Минимальный элемент и его индекс]]


=== Сдвиг вправо ===
==== [[Стандартные задачи на одномерные массивы#Сдвиги, вставка, удаление|Сдвиги, вставка, удаление]] ====
<source lang="pascal">
# [[Стандартные задачи на одномерные массивы#№6. Сдвиг влево|Сдвиг влево]]
procedure ShiftRight<T>(a: array of T);
# [[Стандартные задачи на одномерные массивы#№7. Сдвиг вправо|Сдвиг вправо]]
begin
# [[Стандартные задачи на одномерные массивы#№8. Циклический сдвиг вправо|Циклический сдвиг вправо]]
  for var i := a.Length-1 downto 1 do
# [[Стандартные задачи на одномерные массивы#№9. Удаление k-того|Удаление k-того]]
    a[i] := a[i-1];
# [[Стандартные задачи на одномерные массивы#№10. Вставка на k-тое место|Вставка на k-тое место]]
  a[0] := default(T);
end;
</source>


[http://pascalabc.net/WDE/?shared=PacVlad/ShiftRight.pas Ссылка на алгоритм в среде WDE]
==== [[Стандартные задачи на одномерные массивы#Слияние упорядоченных и бинарный поиск в упорядоченном массиве|Слияние упорядоченных и бинарный поиск в упорядоченном массиве]] ====
# [[Стандартные задачи на одномерные массивы#№11. Слияние двух упорядоченных в один упорядоченный|Слияние двух упорядоченных в один упорядоченный]]
# [[Стандартные задачи на одномерные массивы#№12. Поиск в упорядоченном массиве|Поиск в упорядоченном массиве]]


=== Циклический сдвиг вправо ===
==== [[Стандартные задачи на одномерные массивы#Сортировка массивов|Сортировка массивов]] ====
<source lang="pascal">
# [[Стандартные задачи на одномерные массивы#№13. Сортировка выбором|Сортировка выбором]]
procedure CycleShiftRight<T>(a: array of T);
# [[Стандартные задачи на одномерные массивы#№14. Пузырьковая сортировка|Пузырьковая сортировка]]
begin
## [[Стандартные задачи на одномерные массивы#Способ №1|Способ №1]]
  var v := a[a.Length-1];
## [[Стандартные задачи на одномерные массивы#Способ №2(оптимизация)|Способ №2]]
  for var i := a.Length downto 1 do
# [[Стандартные задачи на одномерные массивы#№15. Сортировка вставками|Сортировка вставками]]
    a[i] := a[i-1];
  a[0] := v;
end;
</source>


[http://pascalabc.net/WDE/?shared=PacVlad/CycleShiftRight.pas Ссылка на алгоритм в среде WDE]
==== [[Стандартные задачи на одномерные массивы#Использование процедурных типов в задачах на массивы|Использование процедурных типов в задачах на массивы]] ====
# [[Стандартные задачи на одномерные массивы#№16. Поиск по условию|Поиск по условию]]
# [[Стандартные задачи на одномерные массивы#№17. Количество по условию|Количество по условию]]
# [[Стандартные задачи на одномерные массивы#№18. Условный минимум|Условный минимум]]
# [[Стандартные задачи на одномерные массивы#№19. Удаление по условию|Удаление по условию]]


=== Удаление k-того ===
<source lang="pascal">
procedure Delete<T>(a: array of T; var n: integer; k: integer);
begin
  Assert((0<=k) and (k<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]
----


=== Вставка на k-тое место ===
© Буцев Виктор, Белоусько Тихон, Зуев Семен, Гончаров Владислав, Батраков Михаил, Гаджиев Казанфар, Пак Владислав
<source lang="pascal">
procedure Insert<T>(a: array of T; var n: integer; var 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]
 
=== Слияние двух упорядоченных в один упорядоченный ===
<source lang="pascal">
// a,b упорядочены по возрастанию
function Merge(a,b: array of real; n,m: integer): array of real;
begin
  Assert((0 < n) and (n < a.Length));
  Assert((0 < m) and (m < b.Length));
  a[n] := real.MaxValue;
  b[m] := real.MaxValue;
  SetLength(Result,m+n);
  var ia := 0;
  var ib := 0;
  for var ir := 0 to n+m-1 do
    if a[ia]<b[ib] then
    begin
      Result[ir] := a[ia];
      ia += 1;
    end
    else
    begin
      Result[ir] := b[ib];
      ib += 1;
    end;
end;
</source>
 
=== Поиск в упорядоченном массиве ===
<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>

Текущая версия от 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