Эвристический алгоритм решения задачи о минимальном количестве линий для размещения отрезков

Всем привет.  Мягко говоря, давно ничего не писал. Попробуем нарушить эту традицию )
Сегодня рассмотрим следующую интересную задачу.
Имеется некий список отрезков в одномерном пространстве. Каждый отрезок задан парой координат его левой и правой точек. Задача - найти минимальное количество линий, на которых можно разместить все эти отрезки таким образом, чтобы они не пересекались друг с другом.
В общем случае задача сводится к умному перебору.  Для разнообразия рассмотрим такую
категорию алгоритмов, как эвристические. Эти алгоритмы не гарантируют нахождение самого лучшего решения (хотя это и не исключено), но почти всегда дают вполне приемлемые результаты при сравнительно небольших временных затратах (этот показатель можно регулировать).

Давайте рассмотрим такой алгоритм. Будем действовать максимально просто.

C наступающим 2014 новым годом )

Вот и заканчивается очередной, теперь уже 2013 год. Было в нем и хорошее, и, наверное, не очень. Как, впрочем, и всегда бывает ) На смену приходит 2014-ый год - год Лошади. Будем надеяться, что в новом году это животное поможет нам легче преодолеть все трудности.
Но, конечно, нельзя рассчитывать только на помощь лошадки. Человек сам должен также прикладывать усилия, чтобы его жизнь и жизнь окружающих его людей стала лучше. Нужно самосовершенствоваться, повышать свой уровень знаний и умений. Развиваться, одним словом. Желаю всем вам, друзья, в наступающем году выполнения всех ваших планов.  Чтобы все хорошее, что вы задумали, сбылось. С новым 2014 годом. Ура )

Тест Amplitube

Решил проверить, как моя балалайка звучит через Amplitube. С учетом того, что на чистом звуке она меня не особо радует, получается вполне себе сносное звучание. То есть, я безо всякого специального оборудования и подготовки (просто тупо воткнул гитару в линейный вход встроенной звуковой и запустил Amplitube) смог получить вот такое, например (просто некий абстрактный музыкальный фрагмент, на косяки внимания не обращайте - слушайте саунд =))).

Так что все в автодор  Amplitube ! )))

Один у него минус пока на данный момент - для его (нормальной) работы нужен ASIO, а ASIO4All под Win7 монопольно блокирует аудиодевайс, то есть, или играть, или слушать ) Возможно, это как-то и решается (переходом на Linux или XP =), но пока не нашел решения.

Очередной веселый казус )

Хочу рассказать еще об одной занятной ситуации, которая произошла буквально на днях.

В общем, имеется группа статических html-файлов, из которых нужно повыносить все общее в отдельные файлики и уже их подключить в каждый первоначальный файл. Переименовал все в *.html.php, настроил редирект в .htaccess через mod_rewrite. Работа, вроде бы. движется. И тут в какой-то момент замечаю, что верстка рушится немного. То есть, положение div-блоков, которое получается у меня, слегка отличается от того, что было раньше. Появляются какие-то необъяснимые отступы и все такое. Давай сличать итоговый html. Вроде бы, все один к одному. То есть, внешне отличий не нахожу. Вошел в ступор от непонимания ситуации )

Итог всего: верстка была в utf-8. Когда я выносил блоки в отдельные файлы, то тоже создавал их в кодировке utf-8. Но не обратил внимание, что AkelPad в этом случае по дефолту выставляет utf-8 with BOM (Byte Order Mark), то есть, в самом начале файла прописывается специальная последовательность символов. Причем в самом редакторе она никак не отображается. Перекодировал все свои файлы в utf-8 без BOM, и все стало как и должно быть ) Теперь самое главное не наступить на эти же грабли в следующий раз )

"Починка" флешки Transcend JetFlash V35

Есть у меня одна флешка, которую я очень люблю ) Transcend JetFlash V35 на 8 Gb.
Куплена она была еще в 2008 году, если мне не изменяет память. Выполнена в аккуратном таком полупрозрачном корпусе. В общем, весьма симпатичная и радует глаз.
И тут неожиданно в какой-то момент случилось страшное - при удалении или записи на неё файлов получаю сообщение "Снимите защиту от записи!".  А ведь никакой аппаратной защиты от записи на ней и нет. Ну, сначала попробовал посмотреть параметры безопасности (сижу под Windows 7) для флешки и каталогов на ней. Ничего необычного, все, вроде бы, в порядке...

Настройки Apache, или как я потерял полчаса своей личной жизни )

Буквально недавно столкнулся с такой ситуацией. Нужно прикрутить mod_rewrite к Апачу на локальной машине. Ну, лезу в его httpd.conf, подключаю нужный .so-шник, в настройках виртуального хоста указываю "AllowOverride All" для того, чтобы подхватывался .htaccess. В сам .htaccess, лежащий в корне локального сайта, пишу для теста нечто такое:

===
RewriteEngine On
RewriteBase  ⁄
RewriteRule ^(.*)% index.php
===

То есть, указываю, что нужно тупо редиректить все запросы на index.php. В index.php
пишу:

==
 <?php
     phpinfo();
 ==

 Стартую Апач, пишу в адресной строке браузера нечто типа http://local.loc/dsfgkjhert и... получаю 500-ую ошибку "Internal server error".
"Что за  (тут нехорошее слово)..", - подумал я )) Сначала проверил еще раз http.conf, затем
httpd-vhosts.conf, затем просмотрел .htaccess. Вроде бы, все в порядке. Нигде никаких ошибок нет. Но почему-то выдает 500-ую ошибку при заходе на локальный домен.
Когда уже собственные мысли на предмет возможной причины ошибки иссякли, полез, разумеется, в google. Ковырялся минут 30, наверное, если не больше. Ничего нового. Все пишут одно и то же. В общем, должно работать, но не работает, почему-то.

А теперь развязка истории. До недавнего времени у меня был установлен Apache 2.2,
и стоял он у меня в Program Files. Устанавливался инсталлятором и им же был впоследствии снесен. Потом я установил Apache 2.4.из zip-архива и поставил его в корень системного раздела. Так вот, после деинсталляции версии 2.2 у него сохранились в Program Files все настроечные каталоги со всеми конфигурационными файлами внутри. Возможно, Apache таким образом беспокоится о том, чтобы пользователь не потерял свои конфигурационные файлы ? Сложно сказать.

Ну, вы уже догадались, наверное, где собака порылась ? ) В общем, не там я настройки Апача правил. Мда. Исправил уже в нужном месте - и все заработало. Возможно, нужно было сразу же в логи лезть, но что-то я не сообразил об этом на тот момент )

Вот такая веселая (и самое главное, что хорошо закончившаяся =) история.

Нахождение всех перестановок на PHP в функциональном стиле

Во время недавнего гугления по какому-то поводу попалась мне на глаза заметка, в которой автор приводил реализацию алгоритма получения всех перестановок (permutations) на PHP. Видимо, по той причине, что обработка входного массива выполнялась "по месту", что существенно экономило память,  реализация алгоритма получилась весьма витиеватой. То есть, чтобы разобраться, как он работает, пришлось натурально браться за ручку и бумагу ))

И вот задумался я, а можно ли как-то все это реализовать в более понятном ключе ?....