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

Материал из Вики проекта PascalABC.NET
Перейти к навигацииПерейти к поиску
Нет описания правки
 
(не показано 119 промежуточных версий 4 участников)
Строка 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. Погрешность округления и вычислительная погрешность]]


=== Вывод массива ===
==== [[Стандартные задачи на циклы#Рекуррентные соотношения|Рекуррентные соотношения]] ====
<source lang="Delphi">procedure Print<T>(a: array of T; delim: string := ' ');
# [[Стандартные задачи на циклы#№7. Вывод 10 первых степеней двойки|Вывод 10 первых степеней двойки]]
begin
# [[Стандартные задачи на циклы#№8. Вывод всех двухзначных чисел, кратных 5|Вывод всех двухзначных чисел, кратных 5]]
  foreach x: T in a do
# [[Стандартные задачи на циклы#№9. Вывод n первых чисел Фибоначчи|Вывод n первых чисел Фибоначчи]]
    write(x, delim);
# [[Стандартные задачи на циклы#№10. Найти НОД(A,B), используя алгоритм Евклида:|Найти НОД(A,B), используя алгоритм Евклида]]
end;   
# [[Стандартные задачи на циклы#№11. Найти сумму цифр целого положительного числа m|Найти сумму цифр целого положительного числа m]]


// С переходом на следующую строку
==== [[Стандартные задачи на циклы#Максимумы и минимумы|Максимумы и минимумы]] ====
procedure Println<T>(a: array of T; delim: string := ' ');
# [[Стандартные задачи на циклы#№12. Найти max из введенных чисел|Найти max из введенных чисел]]
begin
# [[Стандартные задачи на циклы#№12a. Найти min, удовлетворяющее условию p(x)|Найти min, удовлетворяющее условию p(x)]]
  Print(a, delim);
  writeln;
end;</source>


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


=== Инвертирование массива ===
==== [[Стандартные задачи на циклы#Поиск значения|Поиск значения]] ====
<source lang="Delphi">procedure Invert<T>(a: array of T);
# [[Стандартные задачи на циклы#№14. Есть ли среди введенных число k?|Есть ли среди введенных число k?]]
begin
# [[Стандартные задачи на циклы#№14b. Есть ли среди введенных число k? (то же с использованием while)|Есть ли среди введенных число k? (то же с использованием while)]]
  var n := a.Length;
# [[Стандартные задачи на циклы#№15. Является ли число N>0 простым?|Является ли число N>0 простым?]]
  for var i:=0 to n div 2 - 1 do
    Swap(a[i],a[n-i-1]);
end; </source>


=== Поиск элемента по заданному значению ===
==== [[Стандартные задачи на циклы#Другие алгоритмы|Другие алгоритмы]] ====
<source lang="Delphi">// С помощью for
# [[Стандартные задачи на циклы#№16. Разложение числа на простые множители|Разложение числа на простые множители]]
function Find<T>(a: array of T; x: T): integer;
# [[Стандартные задачи на циклы#№17. Вычисление значения многочлена в точке x по схеме Горнера|Вычисление значения многочлена в точке x по схеме Горнера]]
begin
# [[Стандартные задачи на циклы#№18. Дана непрерывная на отрезке функция f(x), имеющая на отрезке ровно один корень. Найти его методом половинного деления|Дана непрерывная на отрезке функция f(x), имеющая на отрезке ровно один корень. Найти его методом половинного деления]]
  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;


// Поиск с барьером
== Стандартные задачи на одномерные массивы ==
function FindWithBarrier<T>(a: array of T; n: integer;
=== [[Стандартные задачи на одномерные массивы|Программы]] ===
  x: T): integer;
==== [[Стандартные задачи на одномерные массивы#Простейшие алгоритмы|Простейшие алгоритмы]] ====
begin
# [[Стандартные задачи на одномерные массивы#№1. Вывод массива|Вывод массива]]
  Assert((0 < n) and (n < a.Length));
# [[Стандартные задачи на одномерные массивы#№2. Заполнение массива случайными числами|Заполнение массива случайными числами]]
  a[n] := x;
# [[Стандартные задачи на одномерные массивы#№3. Инвертирование массива|Инвертирование массива]]
  var i := 0;
# [[Стандартные задачи на одномерные массивы#№4. Поиск элемента по заданному значению|Поиск элемента по заданному значению]]
  while a[i]<>x do
# [[Стандартные задачи на одномерные массивы#№4a. Поиск с барьером|Поиск с барьером]]
    i += 1;
# [[Стандартные задачи на одномерные массивы#№5. Минимальный элемент и его индекс|Минимальный элемент и его индекс]]
  if i=n then
    Result := -1
  else Result := i;
end;</source>


=== Минимальный элемент и его индекс ===
==== [[Стандартные задачи на одномерные массивы#Сдвиги, вставка, удаление|Сдвиги, вставка, удаление]] ====
<source lang="Delphi">procedure MinElem(a: array of integer;
# [[Стандартные задачи на одномерные массивы#№6. Сдвиг влево|Сдвиг влево]]
  var min: integer; var minind: integer);
# [[Стандартные задачи на одномерные массивы#№7. Сдвиг вправо|Сдвиг вправо]]
begin
# [[Стандартные задачи на одномерные массивы#№8. Циклический сдвиг вправо|Циклический сдвиг вправо]]
  min := a[0];
# [[Стандартные задачи на одномерные массивы#№9. Удаление k-того|Удаление k-того]]
  minind := 0;
# [[Стандартные задачи на одномерные массивы#№10. Вставка на k-тое место|Вставка на k-тое место]]
  for var i:=1 to a.Length-1 do
    if a[i]<min then
    begin
      min := a[i];
      minind := i;
    end;
end;</source>


==== [[Стандартные задачи на одномерные массивы#Слияние упорядоченных и бинарный поиск в упорядоченном массиве|Слияние упорядоченных и бинарный поиск в упорядоченном массиве]] ====
# [[Стандартные задачи на одномерные массивы#№11. Слияние двух упорядоченных в один упорядоченный|Слияние двух упорядоченных в один упорядоченный]]
# [[Стандартные задачи на одномерные массивы#№12. Поиск в упорядоченном массиве|Поиск в упорядоченном массиве]]


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


=== Сдвиг вправо ===
==== [[Стандартные задачи на одномерные массивы#Использование процедурных типов в задачах на массивы|Использование процедурных типов в задачах на массивы]] ====
<source lang="pascal">
# [[Стандартные задачи на одномерные массивы#№16. Поиск по условию|Поиск по условию]]
procedure ShiftRight<T>(a: array of T);
# [[Стандартные задачи на одномерные массивы#№17. Количество по условию|Количество по условию]]
begin
# [[Стандартные задачи на одномерные массивы#№18. Условный минимум|Условный минимум]]
  for var i := a.Length-1 downto 1 do
# [[Стандартные задачи на одномерные массивы#№19. Удаление по условию|Удаление по условию]]
    a[i] := a[i-1];
  a[0] := default(T);
end;
</source>


[http://pascalabc.net/WDE/?shared=PacVlad/ShiftRight.pas Ссылка на алгоритм в среде WDE]


=== Циклический сдвиг вправо ===
----
<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]
© Буцев Виктор, Белоусько Тихон, Зуев Семен, Гончаров Владислав, Батраков Михаил, Гаджиев Казанфар, Пак Владислав
 
=== Удаление 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 integer; n,m: integer): array of integer;
begin
  Assert((0 < n) and (n < a.Length));
  Assert((0 < m) and (m < b.Length));
  a[n] := integer.MaxValue;
  b[m] := integer.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