Задача о шляпах от Microsoft

На лестнице стоят 4 человека. Самый верхний стоит на ступеньке, спрятанной за непроницаемой стеной и не видит никого. Все остальные видят только вышестоящих: A видит B и С, B видит C, С видит стену.

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

Дополнительные условия: человечки не могут поворачиваться, не могут переговариваться и перемещаться по лестнице, так же они не могут блефовать и ломать стену.

ЗЫ: Выглядит это примерно так:

Read More...

Summary only...

Поиск последовательности в массиве

Задача

Есть массив положительных и отрицательных чисел. Нужно найти последовательность значений, сумма которой будет наибольшая. Например, для массива [-2, 5, -5, 8, -1, 3, 2, 6] наибольшая сумма будет для последовательности [8, -1, 3, 2, 6].

Решение

Пусть нам дан массив:

src_aray = [x1, x2, x3, x4]

Тогда для решения поставленной задачи нужно вычислить и найти наибольшее для следующих последовательностей:

x1+x2+x3
x2+x3
x1
x2+x3+x4
x2+x3
x2
x3+x4
x3
x4

Так как известно, что массив может содержать отрицательные значения, то можно попытаться уменьшить количество вычислений, суммируя только те последовательности, которые начинаются с положительного числа. Только нужно учесть, что массив может полностью состоять из отрицательных чисел.

Тогда алгоритм будет такой:
1. Массив проверяется на наличие положительных чисел.
2. Пошагово проверяем каждый элемент массива xi.
3. Если в массиве нет положительных чисел (худший вариант), вычисляем сумму всех последовательностей, начинающихся с xi.
4. Если в массиве есть положительные числа, вычисляем сумму всех последовательностей, начинающихся с xi, только в случае xi > 0.
5. Среди вычисленных сумм, выбираем наибольшую.

Реализовать этот алгоритм можно так:

// допускаем, что данные всегда передаются валидные
// src_array - исходный массив
// len - его длина
// sindex, eindex - результат поиска - начальный и 
// конечный индексы последовательности
void sub_array(int *src_array, int len, 
                int &sindex, int &eindex)
{
   int sum = src_array[0];
   sindex = 0;
   eindex = 0;
   
   // проверяем наличие положительных значений
   bool has_positive = false;
   for(int i=0;i < len;i++)
      if(src_array[i]>0)
      {
         has_positive = true;
         break;
      }

   for(int i=0;i < len;i++)
   {
      int ssum = src_array[i];
      if(has_positive && ssum < 0) continue;

      for(int j=i;j < len;j++)
      {
         ssum += j>i?src_array[j]:0;
         if(ssum>=sum)
         {
            sum = ssum;
            sindex = i;
            eindex = j;
         }
      }
   }
}

Read More...

Summary only...

Поиск дубликатов в массиве

Задача

Есть массив целых от 1 до N. Нужно определить, есть ли в этом массиве повторяющиеся значения.

Решение

Задачу можно решить несколькими способами. Первое, что приходит в голову - отсортировать исходный массив и сравнивать соседние элементы. Затраты по времени и по расходуемой памяти будут зависеть от алгоритма сортировки, например, при быстрой сортировке временная сложность будет O(nlogn +n-1) и емкостная сложность (память) будет O(logn).

<br />bool has_duplicates(int *array, int len)<br />{<br /> quicksort(array, 0, len-1);<br /><br /> for(int i=1;i < len;i++)<br /> if(array[i-1]==array[i]) return true;<br /><br /> return false;<br />};
Другое решение - пошагово обходить массив и в каждой итерации проверять значение элемента, сравнивая с информацией о предыдущих итерациях, сохраняемой в дополнительном контейнере. Таким контейнером может быть массив размера N и полностью заполненный нулями. Индекс элемента в массиве - значение от 1 до N (точнее от 0 до N-1), значение элемента - количество "индекса" в исходном массиве. Это проще выглядит на примере:

// исходный массив, со значениями от 1 до 9
src_array = [1,3,8,4,2,9,3,9]

// дополнительный массив на 9 элементов (что бы уместились от 1 до 9)
add_array = [0,0,0,0,0,0,0,0,0]

// после обработки исходного массива результирующий будет выглядеть так:
// одна единица, одна двойка, две тройки, одна четверка, одна восьмерка и две девятки
add_array = [1,1,2,1,0,0,0,1,2]

<br />bool has_duplicates(int *src_array, int len, int minN, int maxN)<br />{<br /> // допускаем, что входящие данные валидны<br /> int add_len = maxN-minN+1;<br /> int *add_array = new int [add_len];<br /><br /> // что-то не помню, можно ли по другому забить массив нулями :(<br /> for(int i=0;i < add_len;i++) add_array[i] = 0;<br /><br /> for(int i=0;i < len;i++)<br /> if(++add_array[src_array[i]-1]>1)<br /> // здесь можно добавить return true;<br /> // но для наглядности просто выведем результат<br /> std::cout<< src_array[i]<< add_array[src_array[i]-1]<< std::endl;<br /><br /> delete [] add_array;<br /><br /> return false;<br />}
Сложность такого алгоритма будет O(n), затраты памяти будут зависеть от диапазона данных - O(maxN-minN). Кроме этого, требуется, что бы было известно максимальное значение элементов из исходного массива, в противном случае либо будет затрачиваться дополнительное время на его поиск, либо понадобиться значительно больше памяти (например, что бы поместить все целые числа).

Вывод

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

Read More...

Summary only...

Абстрактный класс VS интерфейс

Недавно меня озадачили вопросом: чем отличается абстрактный класс от интерфейса в С++? Я вроде бы не настолько забыл С++, что бы помнить об абстрактных классах, но не помнить об интерфейсах.

В С++ есть понятие абстрактного класса - класс, у которого есть хотя бы одна чисто виртуальная функция и, соответственно, нельзя создать объект этого класса. Иногда еще говорят о чисто абстрактных классах, у которых все функции чисто виртуальные, но это скорее искусственное понятие, в большинстве случаев ничем не отличающееся от просто абстрактных классов.

Ни о каких интерфейсах в стандарте С++ не говориться, кроме того, что абстрактный класс может предоставлять интерфейс, который реализуется наследниками (10.4.1):

An abstract class can also be used to define an interface for which derived classes provide a variety of implementations.

Все остальное - это проблемы семантики. Например, в пределах команды (компании), можно принять, что чисто абстрактные классы - это классы, у которых все функции чисто абстрактные, а чисто абстрактные классы, у которых нет не-константных членов данных и все функции public - это интерфейсы. Или под интерфейсами могут подразумеваться просто абстрактные классы и даже COM-интерфейсы.

Лично я придерживаюсь мнения, что интерфейс - это любой класс, у которого есть хотя бы одна виртуальная функция. Клиенту, который ориентируется на этот интерфейс используя указатель на базовый класс, по барабану, есть ли у базового класса члены данных и если у него не чисто виртуальные функции. Кроме того, с позиции клиента, все доступные методы объекта - это интерфейс, даже если объект описывается классом без виртуальных функций.

Так что ответить о разнице между абстрактными классами и интерфейсом в С++ не так просто, так как может быть несколько правильных точек зрения. Кроме того, возможно путаются понятия ОО концепции и реализации этой концепции в конкретном языке программирования. А может, спрашивающий джавист...

Рекомендую к прочтению: Доступность действия в любой момент - оправдание не делать его вообще, Эффект осознания, Парадоксальные заповеди

Read More...

Summary only...

Windows исключения

Интересное описание устройства исключений в Windows (не тех, которые C++-исключения): А что, собственно, происходит, когда бросается исключение?

Read More...

Summary only...

PyQt in-depth: типы signal-slot соединений

В Qt слоты и сигналы являются платформенно-независимым средством обмена сообщениями между объектами. Подробнее писать о них я не собираюсь, так это хорошо сделали до меня прямо в документации Qt или, например, вот здесь. Я хочу выделить некоторые особенности их использования, с которыми мне удалось столкнуться.

Signal-slot механизм - это не просто вызов колбеков в чистом виде. Между сигналом и слотом устанавливается соединение, которое может быть 4-х типов:

• DirectConnection - прямое соединение, когда сигнал моментально обрабатывается слотом;
  
  
• QueuedConnection - сигнал добавляется в очередь и ожидает своего "выхода" в очереди сообщений, при этом поток, в котором возник сигнал не блокируется;
  
  
• BlockingQueuedConnection - то же, что и QueuedConnection, но вызывающий поток блокируется, пока сигнал не будет обработан;
  
  
• AutoConnection - автоматически выбирается DirectConnection, если сигнал вызывается из того же потока, в котором живет приемник, и QueuedConnection, если используются разные потоки.

Как видно, два соединения являются синхронными, одно асинхронным и одно автоматически выбирает себе соответствующий тип в зависимости от внешнего окружения.

Тип соединения указывается как параметр QObject.connect:

QObject.connect(doer, SIGNAL('event'), self.handle, Qt.DirectConnection)

Теперь, как это все работает на примере. Пусть есть задача, которую надо выполнить в отдельном потоке (класс Doer) и обработчик, который должен узнать о результате выполнения (класс Handler).
<br />from PyQt4 import QtGui, QtCore<br />import sys<br /># пользуется стандартная питоновкая либа для работы с потоками, а не <br /># Qt-шная, так как у первой красивше информации о текущем потоке<br />import threading<br /><br />class Doer(QtCore.QObject):<br /><br /> def __init__(self):<br /> QtCore.QObject.__init__(self)<br /> self.thread = threading.Thread(target=self.run) <br /><br /> def start(self):<br /> self.thread.start()<br /><br /> def run(self):<br /> print 'task in thread', threading.currentThread() <br /> self.emit(QtCore.SIGNAL('event'))<br /> print 'after notify'<br /><br />class Handler(QtCore.QObject):<br /><br /> def __init__(self, doer, ctype):<br /> QtCore.QObject.__init__(self)<br /> QtCore.QObject.connect(doer, QtCore.SIGNAL('event'), self.handleNotify, ctype)<br /><br /> def handleNotify(self):<br /> print 'handle in thread', threading.currentThread()<br /> import time<br /> time.sleep(2) <br /> print 'handle finish'<br /><br />app = QtGui.QApplication(sys.argv)<br /><br />d = Doer()<br />handler = Handler(d, QtCore.Qt.DirectConnection)<br />d.start() <br /><br />sys.exit(app.exec_()) <br />
На это примере можно проследить где и когда будет отрабатываться слот в зависимости типа соединения.

В случае DirectConnection, сигнал обрабатывается синхронно, в потоке, где выполнялась задача:

task in thread < Thread(Thread-1, started) >
handle in thread < Thread(Thread-1, started) >
handle finish
after notify

При QueuedConnection, сигнал обрабатывается асинхронно в главном потоке приложения:

task in thread < Thread(Thread-1, started) >
after notify
handle in thread < _MainThread(MainThread, started) >
handle finish

BlockingQueuedConnection заставляет поток, вызывающий сигнал, ждать обработки, которая происходит в главном потоке приложения:

task in thread < Thread(Thread-1, started) >
handle in thread < _MainThread(MainThread, started) >
handle finish
after notify

При AutoConnection ситуация такая же как и при QueuedConnection, так как сигнал и приемник в разных потоках:

task in thread < Thread(Thread-1, started) >
after notify
handle in thread <_MainThread(MainThread, started)>
handle finish

Но если изменить одну строчку кода результат будет таким же как при DirectConnection:
<br />#d.start()<br /># теперь Doer.run будет выполняться в основном потоке<br />d.run()<br />
task in thread <_MainThread(MainThread, started)>
handle in thread <_MainThread(MainThread, started)>
handle finish
after notify

Тип соединения BlockingQueuedConnection стоит использовать только в многопоточных приложениях, так как в одном потоке может привести к dead lock'у, о чем Qt должно предупредить ворнингом:

Qt: Dead lock detected while activating a BlockingQueuedConnection

Таким образом, Qt позволяет гибко настраивать обработку сигналов в синхронном и асинхронном режиме, в одном или нескольких потоках.

Read More...

Summary only...

Неосторожность с lambda

Все утро боролся с кодом, в котором вроде как все правильно, но работал не так как надо. Выглядел он примерно так:
<br />class Menu(object):<br /><br /> def __init__(self):<br /> # элементы меню<br /> self.actions = {}<br /><br /> def addAction(self, name, fn):<br /> '''Добавляет элемент меню с названием name и обработчиком fn'''<br /> self.actions[name] = fn<br /><br /> def callAll(self):<br /> '''Запускает обработчики всех меню'''<br /> for name, fn in self.actions.items():<br /> print 'item', name, 'result', fn()<br /><br />m = Menu()<br /><br />lst = ['a', 'b', 'c']<br />for item in lst:<br /> m.addAction(item, lambda : item)<br /><br /># здесь ожидался вызов для каждого элемента меню<br /># обработчика с именем этого элемента<br />m.callAll()
Но результат выполнения этого кода получился неожиданный:

item a result c
item c result c
item b result c

Проблема оказалась в строке:
m.addAction(item, lambda : item)

lambda использует переменную item из контекста вызывающей функции. Переменная изменяется в цикле и к моменту вызова lambda в item сохраняется значение последней итерации.

Отсюда вывод - смешивание функционального подхода и "обычного" может привести к самым неожиданным результатам. Для того, что бы избежать такого смешивания, достаточно заменить цикл на map:
map(lambda item: m.addAction(item, lambda : item), lst)

Read More...

Summary only...