|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Использование полных последовательностей для сортировки натуральных чисел
Ю. Н. Артамонов ФГБНУ «Госметодцентр»
Аннотация:
Полные последовательности определяются как бесконечные последовательности натуральных чисел, с помощью которых можно представить любое другое натуральное число. Наиболее сильный результат, позволяющий судить о полноте любой последовательности, был получен Д. Брауном. В статье ставится задача представления в виде суммы элементов полной последовательности всех натуральных чисел до некоторого предела (такие начальные участки полных последовательностей названы порождающими последовательностями). Тогда возникает задача нахождения для заданного предела $N$ порождающих последовательностей минимальной длины. В статье предложены алгоритмы генерации порождающих последовательностей минимальной длины. Предложен класс алгоритмов генерации порождающих последовательностей, содержащих в себе заданную порождающую последовательность меньшей длины, что позволяет вводить регулярные алгоритмы генерации полных последовательностей. Предложенные регулярные алгоритмы генерации полных последовательностей использованы при разработке алгоритма сортировки натуральных чисел без их сравнения, являющегося развитием алгоритма поразрядной сортировки с интерпретацией разрядов как элементов подходящей полной последовательности. В статье продемонстрированы подходы адаптации работы данного алгоритма для сортировки конкретной сортируемой последовательности.
Ключевые слова:
полные последовательности, алгоритмы сортировки за линейное время, поразрядная сортировка, нетрадиционные системы счисления, алгоритмы поиска и хранения числовых данных.
Образец цитирования:
Ю. Н. Артамонов, “Использование полных последовательностей для сортировки натуральных чисел”, Известия Иркутского государственного университета. Серия Математика, 22 (2017), 3–17
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/iigum319 https://www.mathnet.ru/rus/iigum/v22/p3
|
Статистика просмотров: |
Страница аннотации: | 189 | PDF полного текста: | 95 | Список литературы: | 31 |
|