Blog posts

Ответ: Почему Quicksort нетривиально вызывается n-1 раз (n - длина сортируемого массива)

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

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

Ответ: Как разломать плитку шоколада минимальным числом разломов

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

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

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

Работающая быстрая сортировка (quicksort) на C#...

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

И _ЭТО_ стоит 42 миллиарда долларов???

Попытался заказать билет на самолет дочке для поездки на восточное побережье... Ну, выбор невелик, бывшая майкрософтовская Expedia или Yahoo Travel. Yahoo Travel на первой же странице отказался показывать календарь для выбора дат:

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer