В полевых условиях нужно получить свинцовую пластинку определенного объема. Из инструментов и материалов есть только охотничья дробь и политровая стеклянная банка с делениями, как мензурка. Есть так же все необходимое для плавления свинца, но это не поможет для решения задачи. А задача такая: как определить достаточный объем дроби? Дополнительное условие - при расчетах можно использовать только одно действие - вычитание.
суббота, 22 ноября 2008 г.
среда, 19 ноября 2008 г.
Удивительное рядом - shared_ptr и виртуальный деструктор
Интересную штуку про boost::shared_ptr прочитал здесь Storing dynamicly created objects in a container. Для shared_ptr не обязательно наличие виртуального деструктора у базового класса. Это не значит, что виртуальные деструкторы теперь не нужны, но может быть полезно, когда есть legacy-код без них и менять его нельзя.
воскресенье, 16 ноября 2008 г.
Объединение двух отсортированных массивов
Как объединить два отсортированных массива (n1 и n2 элементов) в один отсортированный массив? Такой вопрос мне неоднократно попадался на собеседованиях и даже пару раз сталкивался с ним на практике. Вся сложность этого вопроса не в том как это сделать, а как это сделать максимально быстро.
Быстрее всего это делается за n1+n2 итераций (линейное время). Пусть есть два отсортированных по возрастанию массива A1 и A2. Можно легко определить первый элемент результирующего массива - им будет либо первый элемент первого массива, либо первый элемент второго массива, в зависимости от того, что меньше. Допустим, наименьший - это A1[0]. На следующей итерации при помощи одного сравнения определяется второй элемент результирующего массива - опять сравниваются первые элементы исходных массивов, при условии, что для A1 первый элемент - это A1[1], так как A1[0] - уже выбыл из игры. И так продолжается пока не будет заполнен результирующий массив. На картинке это выглядит так:
Как видно, ничего сложного в этом алгоритме нет. Самое интересное в нем - это возможность использования для сортировки. Любой массив размера n можно представить в виде n массивов, состоящих из одного элемента. Пары соседних элементов, представленных ввиде массивов можно объединять по описанному выше алгоритму. Получится примерно в 2 раза (примерно, потому что n может быть как четным так и нечетным числом) меньше отсортированных массива по 2 элемента, которые в свою очередь тоже можно объединить. И так пока не получится один отсортированный массив.
А все это называется сортировка слиянием.
суббота, 15 ноября 2008 г.
Concepts в C++0x
Наконец то удалось посмотреть видео о новых расширениях С++ Concepts: Extending C++ Templates For Generic Programming. Решил поделиться своими впечатлениями.
Concepts - это расширение существующих шаблонов С++, позволяющие устанавливать требования к параметрам шаблона. Концепция позволяет ответить на несколько вопросов:
В ролике это называлось Concept definitions, Where clauses и Concept maps соответственно. Насколько я понимаю, то, что было озвучено и то, что будет в стандарте немного отличается, по крайне мере вместо where будет использоваться requires, поэтому пример будет выглядеть не как в видео:// Вычисление суммы элементов последовательности
// Параметр шаблона должен быть Forward Iterator -
// позволяет двигаться только в перед
template< ForwardIterator Iter >
// два значения, на которые указывают итераторы,
// могут быть сложены при помощи оператора +
requires Addable< Iter::value_type >,
// объект, на который указывает итератор,
// должен иметь оператор присваивания
&& Assignable< Iter::value_type >
Iter::value_type sum(Iter first, Iter last,
Iter::value_type result)
{
for (; first != last; ++first)
result = result + *first;
return result;
}
// у типа double* нет оператора сложения, присваивания,
// получения следующего элемента последовательности,
// но реализация алгоритма sum будет корректно работать
// с этим типом, поэтому устанавливается соответствие
// между ForwardIterator и double*
concept_map ForwardIterator
typedef double value_type;
};
Надеюсь, теперь понятно, зачем вводятся concepts, если нет, то подробней можно почитать здесь: ConceptC++ Tutorial.
На видео, дядька приводит другой пример, знакомый всем, кто использовал STL: простой алгоритм поиска, реализованный в соответствие с требованиями STL, отлично работает с вектором, но не хочет работать со списком. Хотя внешне все вписывается в общую структуру библиотеки: контейнеры - итераторы - алгоритмы. Для того, что бы понять, что не так с алгоритмом нужно копаться в его коде либо использовать concepts. Начиная с этого места у меня появилось чувство, что concepts - это костыль, который подсовывают С++. Проблема как была, так и осталась, но теперь можно уверенно хромать в перед. Лечится только следствие проблемы - теперь компилятор будет сам говорить, что хотя все вписывается в рамки, но работать все равно не будет. При этом, возможность писать неработающий код так и остается - для совместимости с предыдущими версиями.
Кроме того, и без того, часто трудночитаемый код с шаблонами, станет во много раз менее читабельным. А разработчику придется больше потеть, определяя жесткие требования к написанным функциям.
Это первое впечатление, основанное на двухчасовом знакомстве с этим нововведением. Надо будет еще обдумать прочитанное и просмотренное, а то прям бесполезная какая-то штука получается :) Поэтому интересно было бы услышать критику моего обзора и мысли по поводу concepts.
четверг, 13 ноября 2008 г.
Задачка про прилив
Нашел в шкафу старую книгу "Математическая смекалка". Замечательная книга! Теперь по вечерам сижу с удовольствием решаю задачки - неплохая гимнастика для мозгов и хорошая альтернатива вечернему созерцанию интернета. Вот одна из задач, которая мне понравилась (кстати, ничем не хуже майкрософтовских :)
Недалеко от берега стоит корабль со спущенной на воду веревочной лестницей вдоль борта. У лестницы 10 ступенек; расстояние между ступеньками 30 см. Самая нижняя ступенька касается поверхности воды. Океан сегодня очень покоен, но начинается прилив, который поднимает воду за каждый час на 15 см. Через сколько времени покроется водой третья ступенька веревочной лесенки?
вторник, 11 ноября 2008 г.
Python 3 Patterns & Idioms
Стала доступна open source книга Python 3 Patterns & Idioms, написанная Bruce Eckel при содействии Python community. Она распространяется под лицензией Creative Commons Attribution-Share Alike 3.0 (первый раз о такой слышу :).
Книга еще сыровата, по крайне мере в содержании все перемешано в кучу и некоторые главы отсутствуют. Большая часть посвящена паттернам, например, есть много про singleton, есть много про Jython, немного про юнит тестирование и TDD, рефакторинг, а так же упражнения к каждой главе. Самое интересное, что здесь кода больше, чем букафф :)
среда, 29 октября 2008 г.
Задача о шляпах от Microsoft
На лестнице стоят 4 человека. Самый верхний стоит на ступеньке, спрятанной за непроницаемой стеной и не видит никого. Все остальные видят только вышестоящих: A видит B и С, B видит C, С видит стену.
На каждом из человечков одета шляпа. На двоих красные шляпы, на других двоих черные. Кто из них первый поймет какого цвета у него шляпа, если никто не может ее снять и посмотреть?
Дополнительные условия: человечки не могут поворачиваться, не могут переговариваться и перемещаться по лестнице, так же они не могут блефовать и ломать стену.
ЗЫ: Выглядит это примерно так:
Подписаться на:
Сообщения (Atom)
