Число инверсий
Задача. Найти число инверсий в строке
[4, 6, 5, 1, 3, 2]
Решение
Элементы ia=m и ib=n в строке [i1, i2,..., ik] образуют инверсию, если a < b и m > n.
Рассмотрим последовательно элементы строки.
  • Число 4 образует три инверсии с элементами 1,3,2.
  • Число 6 образует четыре инверсии с элементами 5,1,3,2.
  • Число 5 образует три инверсии с элементами 1,3,2.
  • Число 1 не образует инверсий.
  • Число 3 образует одну инверсию с 2.
Всего 3+4+3+1=12 инверсий.
Литература
Просветов Г.И. Дискретная математика. Задачи и решения М.: Альфа-Пресс. 2009


File translated from TEX by TTH, version 3.64.
On 01 Nov 2009, 08:55.