Условие:
На сколько может измениться число инверсий в перестановке $ \sigma=\left(
$ если в её нижней строке поменять местами два соседних элемента? А как при этом изменится её знак?
Решение:
Рассмотрим перестановку σ = (1 2 3 … n) с соответствующим набором значений σ(1), σ(2), …, σ(n). Пусть нам дано два соседних элемента σ(i) и σ(i+1), которые мы меняем местами. Обозначим их как a = σ(i) и b = σ(i+1).
Шаг 1. Анализ влияния на пару (i, i+1)
В исходной последовательности пара (a, b) может быть инверсией, если a > b. После обмена эти элементы становятся b и a. Тогда
– Если первоначально a < b (то есть (a, b) не была инверсией), то после обмена пара (b, a) образует инверсию, так как b > a;
– Если первоначально a > b (то есть (a, b)...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи