Найти число инверсий в перестановке:
Цитата:
(1, 5, . . . , 4n−3, 3, 7, . . . , 4n−1, 2, 6, . . . , 4n−2, 4, 8, . . . , 4n).
Тут разбито на 4 блока.
В каждом боке перестановок нет. Следовательно ищем между ними.
Берем первый блок:
1 - > 0 перест. - >(3*0)
5 - > 3 - > (3*1)
9 - > 6 - >(3*2)
13 - > 9 - >(3*3)
...
4n-3 - > 3*(n-1) - > n-1 потому что начинаем с 0.
А как также провернуть со вторым???
3 - > 1
7 - > 3
11 - > 5
...
4n-1 - >? у меня по разному получалось, то 2n-1, то 4n-2 то еще как... Я не понимаю как тут считать!
(Оффтоп)
В классе у нас все было просто и все блоки стояли по порядку. итого вышло 6(0+1+2+3+..+(n-1))=3n(n-1)
Здесь ответ проде должен быть 3n(n-2)
Объясните пожалуйста!
08.12.2012, 11:04 
