Русский

Давно уже собирался выложить это где-нибудь на блоге, да руки не доходили...

Да-да, далеко не все празднуют этот праздник, и многие не сегодня, но я все-таки поздравлю всех, потому что universal message - идея этого праздника важна и обща для людей всех вер. Если уж на то пошло, то одно из самых лучших выражений его идеи было создано во времена советского коммунизма без малейших религиозных намеков:

Ну, ладно, предыдущий снегопад на 31 марта можно было считать первоапрельской шуткой природы. Но в конце апреля???

Недавно патентный оффис утвердил один из патентов Microsoft, в котором я являюсь одним из авторов. Как я узнал об этом? Из почты. Но не от патентного оффиса, а от фирм, специализирующихся на производстве табличек на стенку, кои должны увековечить сие достижение. Почему-то считается, что счастливый изобретатель (все права которого, между прочим, ушли фирме, на которую он работает) просто спит и видит как бы заказать на свои кровные таких табличек по цене долларов двести за штуку и развесить их в оффисе, дома и еще невесть где.

У одного из моих коллег в офисе висел плакат: очкарик склонился над компьютером и собирается нажать кнопку Download, за его спиной огромный лохматый казак с черной лохматой шевелюрой, выпучеными глазами и огромными кривыми зубами, в полушубке, опоясанный пулеметными лентами, с огромной красной звездой на папахе одобрительно похлопывает паренька по спине. Все это сопровождается подписью “When you download free music, you download communism!”

Это ответ на пост про быструю сортировку (quicksort).

Цитата: "Пока возился обратил внимание на забавный момент: как бы ни распределялись данные, количество нетривиальных вызовов Quicksort (когда i<j) всегда равно длине массива минус один. Сначала удивился, а потом дошло почему. Можете ответить?"

Исходная задачка:

На обычной плитке шоколада выдавлены канавки, чтобы удобнее ее было ломать. У вас есть шоколадка на которой есть три полоски в длину и пять в ширину. Понятное дело, это делит ее на 15 кусочков.

Задача: разломать ее на 15 кусочков сделав минимальное число разломов. Разлом делается так: берете со стола один из кусочков, ломаете его по канавке, кладете результат обратно на стол.

Вчера супруга, которая решила посмотреть вокруг место работы получше и начала каждый вечер делать программистские задачки на C#, C++ и Python, полвечера убила на быструю сортировку (quicksort). Я тем временем опять удивился насколько много граничных условий вылезает в исходном алгоритме Хоара. Да-да, знаю, уже придумали улучшенную и починенную версию, но захотелось исправить сохранив дух решения, с двумя индексами сходящимися к центру. И вот что получилось. Вроде работает. Кто-нибудь видит баг?

Вот фотография Круглого Озера с моего любимого трейла в начале зимы, точнее под Рождество 2007-го года:

А вот фотография того же озера в марте 2008-го:

В Саммамише наконец наступила весна. В субботу было 20 градусов тепла (по Цельсию, разумеется...) Цветут деревья, включая сливу в углу моего двора.