107
правок
Изменения
→Определение
== Определение ==
{{Определение
|definition=Пусть даны две последовательности <tex> ~A = a_1 a_2 ... a_n </tex> и <tex> ~B = b_1 b_2 ... b_m </tex> <br>Тогда последовательность <tex> ~A </tex> '''лексикографически меньше''' последовательности <tex> ~B </tex>, есливыполняется одно из двух условий: <br>1. *<tex> n<m </tex> и при этом <tex> a_i=b_i </tex> для всех <tex>i \in [1;n] </tex> <br>'''или'''2. * <tex> \mathcal {9} k\leqslant \min(n, m): a_k<b_k </tex> и при этом <tex> \mathcal {8} j < k ~a_j = b_j </tex>
}}
Приведем псевдокод сравнения последовательностей из элементов множества '''Т''':
'''function''' Сompare(A, B : '''list <T>''') <font color=green>// Возвращает "LESS", если A < B, "MORE", если A > B, или "EQUAL", если последовательности равны</font> '''for''' i = 1 .. '''to''' min(len(A), len(B)) '''if''' (A[i] < B[i]) <font color=green> // i-й элемент А меньше i-го элемента B, но префиксы длины i - 1 равны</font>
'''return''' LESS
'''if''' (A[i] > B[i]) <font color=green> // i-й элемент А больше i-го элемента B, но префиксы длины i - 1 равны</font>
'''return''' MORE
'''if''' (len(A) < len(B)) <font color=green>// А - префикс В, но не равна ей.</font>
'''return''' LESS
'''if''' (len(A) > len(B)) <font color=green>// В - префикс А, но не равна ей.</font>
'''return''' MORE
'''return''' EQUAL <font color=green>// Длины последовательностей и все элементы равны</font>
{{Определение
|definition=Последовательности записаны в '''лексикографическом порядке''' ''(in lexicographical order)'', если для любых <tex> i<j </tex> выполняется неравенство <tex> S_i<S_j </tex>, где <tex> S_i </tex> и <tex> S_j </tex> последовательности с номерами <tex> i </tex> и <tex> j </tex>.
}}
Например, слово "сон" лексикографически меньше слова "сонный", так как оно является его префиксом. Слово "низ" лексикографически меньше слова "нос", поскольку первые символы совпадают, а второй символ первого слова меньше, чем второй символ второго.
== Примеры ==
# Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (000, 001, 002, 003, 004, 005, …, 999).
