?

Log in

No account? Create an account

Marcus Darnley

Previous Entry Share Next Entry
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: ,

Comments

[User Picture]
From:griffon
Date:March 24th, 2010 07:14 pm (UTC)
(Link)
Хорошо, что Гоша поправился, ещё бы он до кружка дошёл...
[User Picture]
From:dmitrits
Date:March 24th, 2010 07:44 pm (UTC)
(Link)
Он и к тебе не ходит?
[User Picture]
From:griffon
Date:March 24th, 2010 07:49 pm (UTC)
(Link)
К сожалению, в последнее время мы Гошу на кружке не видели, да.
[User Picture]
From:dmitrits
Date:March 24th, 2010 07:51 pm (UTC)
(Link)
Тогда зря его так хвалит Миша. Не такая уж великая заслуга применить стандартную идею.
[User Picture]
From:griffon
Date:March 24th, 2010 07:53 pm (UTC)
(Link)
Это нормально, потому что кружок мы ведём вместе. Там Миша играет роль мягкого преподавателя, а я роль строгого =)
[User Picture]
From:monka
Date:March 24th, 2010 08:56 pm (UTC)

О умудренных опытом педагогах

(Link)
Ты бы хоть под замок все это запихал :) А то юный Гаусс юным Гауссом, но как-то непедагогично.
[User Picture]
From:griffon
Date:March 24th, 2010 09:21 pm (UTC)

Re: О умудренных опытом педагогах

(Link)
Расскажи, пожалуйста, что такое непедагогичное ты видишь в публичной похвале.
[User Picture]
From:monka
Date:March 25th, 2010 07:57 am (UTC)

Re: О умудренных опытом педагогах

(Link)
я щетаю, что хвалить можно и нужно, но сравнивать с гауссом это уже немного чересчур; кроме того, совершенно никому не нужно видеть, как его обсуждают в жж преподаватели, что тут неизбежно происходит
[User Picture]
From:darnley
Date:March 25th, 2010 06:13 pm (UTC)

Re: О умудренных опытом педагогах

(Link)
Гоша достаточно умён, чтобы понять, что его сравнение с Гауссом — дикий сарказм и зловредная ирония, муа-ха-ха!
[User Picture]
From:allocco
Date:March 25th, 2010 11:47 pm (UTC)

Re: О умудренных опытом педагогах

(Link)
А его одноклассники?
[User Picture]
From:darnley
Date:March 26th, 2010 11:00 am (UTC)

Re: О умудренных опытом педагогах

(Link)
Будут его подкалывать. В идеале — сделают демотиватор: фотография Гоши и подпись «Юный Гаусс».
[User Picture]
From:allocco
Date:March 26th, 2010 11:19 am (UTC)

Re: О умудренных опытом педагогах

(Link)
Да ты и впрямь умудрён опытом :)
From:ex_mrybak
Date:March 25th, 2010 05:01 am (UTC)
(Link)
по-моему удобнее рассмотреть не перестановку, а пару. любая пара (a, b) ровно в половине случаев потребует обмена. пар всего 6, перестановок всего 24, 6 * (0.5 * 24) = 72. и ничего не надо доказывать.
[User Picture]
From:darnley
Date:March 25th, 2010 06:14 pm (UTC)
(Link)
Я тоже считаю естественным именно такое решение, да! И его ожидал от ребят.
Но есть вот нестандартные...
[User Picture]
From:griffon
Date:March 25th, 2010 06:29 pm (UTC)
(Link)
Мда, а я когда решал фиксировал первый элемент, считал количество обменов с ним отдельно и сводил задачу к случаю для N на единицу меньше. Сколько людей столько и решений =)
From:ex_mrybak
Date:March 26th, 2010 06:01 am (UTC)
(Link)
:)
[User Picture]
From:dkorduban
Date:March 27th, 2010 12:44 pm (UTC)
(Link)
я, кстати, когда решал, тоже придумал "гауссовское" а не "вероятностное".
Powered by LiveJournal.com