Комбинаторные алгоритмы для программистов



             

Последовательности


Бесконечная последовательность

s_1,s_2,s_3,\ldots

формально определяется как функция

f
, областью определения которой является множество положительных целых чисел:
f(i) = s_i,i \geqslant 1
. Во многих случаях индексирование последовательности более удобно начинать с нуля; тогда областью определения
f
будет множество целых неотрицательных чисел. Аналогично определим конечную последовательность или список

s_1,s_2,\ldots,s_n

как функцию, областью определения которой является множество

\{ 1,2,\ldots,n\}
. Примером бесконечной последовательности являются простые числа

i:1\;2\; 3\; 4\; 5\; 6\; 7\; 8\; 9\; 10…

(2.3)

p_i : 2\; 3\; 5\; 7\; 11\; 13\; 17\; 19\; 23\; 29…,

а перестановка

\Pi(1,2,3,4,5,6)=(6,2,5,1,3,4)

представляет собой пример конечной последовательности.

В комбинаторных алгоритмах часто приходится встречаться с представлениями конечных последовательностей (или начальных сегментов бесконечных последовательностей) и операциями над ними.




Содержание  Назад  Вперед