Marcus Darnley (darnley) wrote,
Marcus Darnley
darnley

Category:

О юном Гауссе.

В продолжение предыдущей темы — не могу не похвастаться и положительным моментом.

Вы, быть может, слышали историю/легенду о том, как юному Гауссу предложили сосчитать сумму чисел от 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: math, school
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 17 comments