Полные последовательности определяются как бесконечные последовательности натуральных чисел, с помощью которых можно представить любое другое натуральное число. Наиболее сильный результат, позволяющий судить о полноте любой последовательности, был получен Д. Брауном. В статье ставится задача представления в виде суммы элементов полной последовательности всех натуральных чисел до некоторого предела (такие начальные участки полных последовательностей названы порождающими последовательностями). Тогда возникает задача нахождения для заданного предела N порождающих последовательностей минимальной длины. В статье предложены алгоритмы генерации порождающих последовательностей минимальной длины. Предложен класс алгоритмов генерации порождающих последовательностей, содержащих в себе заданную порождающую последовательность меньшей длины, что позволяет вводить регулярные алгоритмы генерации полных последовательностей. Предложенные регулярные алгоритмы генерации полных последовательностей использованы при разработке алгоритма сортировки натуральных чисел без их сравнения, являющегося развитием алгоритма поразрядной сортировки с интерпретацией разрядов как элементов подходящей полной последовательности. В статье продемонстрированы подходы адаптации работы данного алгоритма для сортировки конкретной сортируемой последовательности.

Ссылка для цитирования:

Артамонов Ю.Н. Использование полных последовательностей для сортировки натуральных чисел // Известия Иркутского государственного университета. Серия Математика. 2017. Т. 22. С. 3-17. https://doi.org/10.26516/1997-7670.2017.22.3

MSC

68P10

DOI

https://doi.org/10.26516/1997-7670.2017.22.3

1. Артамонов Ю. Н. Групповой выбор с использованием матричных норм / Ю. Н. Артамонов // Изв. Иркут. гос. ун-та. Сер. Математика. – 2016. – Т. 18. – С. 3–20.

2. Кнут Д. Э. Искусство программирования. Т. 3. Сортировка и поиск / Д. Э. Кнут. – 2-е изд. – М. : Вильямс, 2007. – С. 274–387.

3. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. М. Штайн. – 2-е изд. – М. : Вильямс, 2005. – C. 220–238.

4. Научный форум dxdy. Модификация старой задачи про мешки с монетами [Электронный ресурс]. –– URL: http://dxdy.ru/topic111132-30.html (дата обращения: 02.11.2017).

5. Национальный открытый университет «ИНТУИТ» [Электронный ресурс]. – URL: http://www.diofant.ru/problem/383/ (дата обращения: 02.11.2017).

6. Седжвик Р. Фундаментальные алгоритмы на C++. Анализ. Структуры данных. Сортировка. Поиск / Р. Седжвик. – Киев : ДиаСофт, 2001. – С. 401–438.

7. Goodrich M. 4.5 Bucket-Sort and Radix-Sort / M. Goodrich, T. Michael, R. Tamassia // Algorithm Design: Foundations, Analysis, and Internet Examples. – John Wiley, 2002. – P. 241–243.

8. Honsberger R. Mathematical Gems III / R. Honsberger. – Washington, DC : Math. Assoc. Amer., 1985. – P. 123–128.