Алгоритм определения мест — различия между версиями
Материал из ALL
Строка 32: | Строка 32: | ||
*[[метод математической индукции]]; | *[[метод математической индукции]]; | ||
*[[схема примитивной рекурсии]]; | *[[схема примитивной рекурсии]]; | ||
+ | *[[рекурсия]]; | ||
*[[машина Поста]]; | *[[машина Поста]]; | ||
*[[машина Тьюринга]]; | *[[машина Тьюринга]]; |
Версия 13:30, 14 февраля 2016
Алгоритм определения мест — это алгоритм (операция) упорядочения индексов элементов конечного множества (массива) без изменения положения самих элементов.
Содержание
Обозначения
Введём обозначения:
n – число элементов;
{A1,A2,…,An} – массив элементов;
{m1,m2,…,mn} – массив мест (индексов) элементов.
Сортировка индексов по возрастанию элементов
Входные данные: n, {A1,A2,…,An}.
Выходные данные: {m1,m2,…,mn}.
- Особенность алгоритма состоит в том, что для одинаковых элементов индексы мест различны.
Определение мест по возрастанию элементов
Входные данные: n, {A1,A2,…,An}.
Выходные данные: {m1,m2,…,mn}.
- Особенность алгоритма состоит в определении одинаковых мест для одинаковых элементов, при этом если одинаковых элементов k, то в распределении мест пропускается (k-1) место.
Другие алгоритмы:
- наибольший общий делитель;
- наименьшее общее кратное;
- проверка кратности;
- деление по модулю;
- получение простых чисел;
- разложение на множители;
- система счисления;
- метод математической индукции;
- схема примитивной рекурсии;
- рекурсия;
- машина Поста;
- машина Тьюринга;
- комбинаторные алгоритмы;
- сортировка;
- алгоритм определения мест.