?

Log in

No account? Create an account

Marcus Darnley

Archive

March 24th, 2010

05:54 pm: О юном Гауссе.
В продолжение предыдущей темы — не могу не похвастаться и положительным моментом.

Вы, быть может, слышали историю/легенду о том, как юному Гауссу предложили сосчитать сумму чисел от 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. Пятёрка и оптимизм.

Tags: ,
Powered by LiveJournal.com