Без перебора с возвратом. Часть 2

Как я уже говорил в прошлый раз, полезной особенностью «отсутствия перебора с возвратом» является то, что язык становится проще в понимании. Простые правила полезны как компилятору, так и программисту, читающему код; они оба читают код, в попытке его понять. Не всегда разумно пользоваться тем, что компилятор может просмотреть огромное пространство решений, если это усложняет понимание…


Без перебора с возвратом. Часть 1

В нескольких статьях, опубликованных в этом году, я говорил об алгоритме «перебора с возвратом» (backtracking algorithm); в последний раз я упоминал о нем в серии статей, посвященных решению головоломок Судоку с помощью перебора с возвратами (и более общей задачи раскраски графов). Идея алгоритма перебора с возвратом очень проста и эффективна: если возникает необходимость выбора, просто…


Раскраска графов с помощью простого поиска с возвратом. Часть 3

Итак, у нас готовы базовые структуры данных. Раскраска графа – это очень хорошо изученная задача. Известно, что это NP-полная задача для произвольных графов, так что (предполагая, что P != NP) мы не стремимся находить эффективный алгоритм для раскрашивания произвольного графа. Однако, для типовых графов, с которыми мы сталкиваемся в реальной жизни, следующий простой алгоритм вполне…


Раскраска графов с помощью простого поиска с возвратом. Часть 2

Прежде чем я начну, короткое замечание: поздравления с наилучшими пожеланиями Дэвиду Джонсону, текущему президенту моей alma mater, Университета Ватерлоо. Королева назначила его следующим Генерал-Губернатором Канады и он приступает к своим полномочиям в октябре. Для тех из вас, кто не знаком с политической структурой Канады, Ее Величество Елизавета II является главой государства, Генерал-Губернатор является ее прямым…


Лучше поздно, чем никогда

Слава Богу, я понял, что я совершенно забыл опубликовать ссылку на это интервью. С опозданием на год, но лучше поздно, чем никогда. Год назад Кен приехал в мой офис и у нас состоялся очень свободный, занимательный и довольно сумбурный разговор о различных аспектах проектирования языков программирования. Если вам интересна эта тема и у вас есть…


Все существующие программы. Часть 8

  Хорошо, давайте начнем с начала. Предположим, что у нас есть строка, которая содержит грамматику, уже переписанную в нашей «удобной» форме, которая содержит в точности два терма для каждого правила подстановки. Мы можем легко написать анализатор для разбора этой строки. Я создам ассоциативный массив, который будет содержать соответствие каждого правила со списком двухсимвольной подстановки. Итак,…


Рыцари, жулики, Protected и Internal

  При  переопределении виртуального метода в C# вы требуете гарантий, что указанный модификатор доступа переопределенного метода (т.е. модификаторы public, internal, protected или protected internal (*)), будет точно соблюдаться при переопределении. За исключением одного случая. Я имею в виду раздел 10.6.4 спецификации языка C#, в котором сказано: «объявление переопределенного метода не может изменять модификатор доступа виртуального…


Не давайте классам и пространствам имен одинаковые имена. Часть 4

Часть 4. Делаем проблему еще серьезнее Как я уже сказал ранее, фундаментальная задача пространств имен заключается, прежде всего, в организации типов в иерархии, а не в разделении двух сущностей с одинаковыми именами. Но предположим, что вы поместили нечто в пространство имен, поскольку у вас есть две сущности с одинаковыми именами и должны находиться раздельно. Предположим,…


Не давайте классам и пространствам имен одинаковые названия. Часть 2

Часть 2: Автоматически сгенерированный код Вы написали namespace Foo {   public sealed class Foo   {     public string Blah(int x) { … } } } Вы берете этот код и с помощью стороннего инструмента «декоратора» превращаете свой класс в более красочный: // Автоматически сгенерированный код: namespace Foo {   public sealed class ColorFoo…


Сколько проходов?

В огромном объеме кода, написанном на языках C/C++, обычно происходит разделение кода на заголовочные файлы, в которых содержится только объявления методов и типов (а также определения макросов). Сами тела методов и типов содержатся в совершенно других файлах. Меня иногда спрашивают, а почему в языке C# не требуются заголовочные файлы? Мне такая постановка вопроса кажется странной….