О юном Гауссе.
В продолжение предыдущей темы - не могу не похвастаться и положительным моментом.
Вы, быть может, слышали историю/легенду о том, как юному Гауссу предложили сосчитать сумму чисел от 1 до 100, и он придумал красивое решение с разбиением чисел на пары:
1 + 2 + 3 + ... + 100 = S
100 + 99 + 98 + ... + 1 = S
--------------------------------
101 + 101 + 101 + ... + 101 = 2S
Так вот, вернёмся к задаче про перестановки и сортировку пузырьком. В девятом классе нашёлся юный Гаусс - Гоша kolozab Матюшин, который придумал такую же идею:
Разобьём все перестановки на пары перевёрнутых, например (2, 3, 1, 4) и (4, 1, 3, 2). При сортировке таких двух перестановок делается ровно шесть обменов, это несложно доказать.
Все 24 перестановки разбиваются на 12 пар. По шесть обменов в каждой. Ответ: 72. Пятёрка и оптимизм.
Вы, быть может, слышали историю/легенду о том, как юному Гауссу предложили сосчитать сумму чисел от 1 до 100, и он придумал красивое решение с разбиением чисел на пары:
1 + 2 + 3 + ... + 100 = S
100 + 99 + 98 + ... + 1 = S
--------------------------------
101 + 101 + 101 + ... + 101 = 2S
Так вот, вернёмся к задаче про перестановки и сортировку пузырьком. В девятом классе нашёлся юный Гаусс - Гоша kolozab Матюшин, который придумал такую же идею:
Разобьём все перестановки на пары перевёрнутых, например (2, 3, 1, 4) и (4, 1, 3, 2). При сортировке таких двух перестановок делается ровно шесть обменов, это несложно доказать.
Все 24 перестановки разбиваются на 12 пар. По шесть обменов в каждой. Ответ: 72. Пятёрка и оптимизм.