Прекрасное управление потоком

Опубликовал admin 15 Декабрь 2014 в рубрике Шедевры юниоров. Комментарии: Комментарии отключены

Сегодня наткнулся в code review на следующий код:

do
{
	IStream* spStream = SHCreateMemStream(&icon[0], icon.size());
	if (!spStream)
		break;
	boost::scoped_ptr<Gdiplus::Bitmap> bitmap(new Gdiplus::Bitmap(spStream));
	if (!bitmap)
		break;
	HBITMAP hbitmap = 0;
	Gdiplus::Color bg(0, 0, 0, 0);
	if (bitmap->GetHBITMAP(bg, &hbitmap) != Gdiplus::Status::Ok)
		break;
	m_bitmaps.push_back(hbitmap);
} while (0);

Только с тртьего раза прочтения мне удалось заценить всю красоту while(0) в связке с брейками.

Игра ним и алгоритм Шпрага-Гранди

Опубликовал admin 25 Август 2014 в рубрике Алгоритмы, Логические задачи. Комментарии: Комментарии отключены

Есть несколько кучек, в каждой из которых X камней. В игре учавствуют два игрока, которые по очереди берут из кучек определенное количество камней. За один ход игрок может взять из какой-нибудь одной кучки любое ненулевое число камней. Выигрывает тот, кто сможет взять последний камень из последней кучи. Для N кучек с размерами X1, X2, …, Xn, нужно определить, кто победит: тот кто ходит первым или вторым.

На помощь приходит алгоритм Шпрага-Гранди.

Ксорим размеры всех кучек. Если получившееся значение равно 0, то значит победителем будет тот, кто ходит вторым, иначе – первым.

int main()
{
	int a, b;
	cin >> a >> b;
	if (a == 0){
		if ((3 * b) % 2 == 0) cout << 2;
		else cout << 1;
	}
	else if (b == 0){
		if (a % 2 == 0) cout << 2;
		else cout << 1;
	}
	else{
		int res = 2;
		for (int i = 1; i < a; i++){
			res ^= 2;
		}
		for (int i = 0; i < b; i++){
			res ^= 3;
		}
		cout << (res == 0 ? 2 : 1);
	}
	return 0;
}

To count the total pairs of numbers which have a difference of K

Опубликовал admin 23 Январь 2014 в рубрике Задачи для интервью. Комментарии: Комментарии отключены
Given N numbers , [N<=10^5] we need to count the total pairs of numbers which have a difference of K. [K>0 and K<10^9].
Input Format:
1st line contains N & K (integers).
2nd line contains N numbers of the set. All the N numbers are assured to be distinct.
Output Format:
One integer saying the no of pairs of numbers that have a diff K.
Sample Input:
5 2
1 5 3 4 2
Sample Output:
3
Explanation:
The possible pairs are (5,3), (4,2) and (3,1).

Задача коммивояжера

Опубликовал admin 11 Январь 2014 в рубрике Алгоритмы. Комментарии: Комментарии отключены

Как известно задача коммивояжера является np-полной. Существуют несколько эвристических методов комбинаторного поиска, которые позволяют найти хорошее решение за приемлемое время. Одним из самых эффективных и простых в реализации является метод имитации отжига (simulated anealing). Данный метод основан на принципе, который лежит в основе одноименного процесса обработки металла. Хорошее описание алгоритма имитации отжига с примером кода приводится здесь.

Heavy and Light Balls Puzzle

Опубликовал admin 9 Январь 2014 в рубрике Логические задачи. Комментарии: Комментарии отключены

Очень простая задачка, но за пять минут может и не получиться решить.

You have 2 ball of each A,B,C colors and each color have 1 light and 1 heavy ball.  All light balls  are of same weight same goes for heavy. Find out weight type of each ball in minimum chances. You can use a two sided balance system (not the electronic one).

Что появилось нового и интересного в Visual Studio 2013

Опубликовал admin 30 Декабрь 2013 в рубрике Заметки программиста. Комментарии: Комментарии отключены
Помимо мелких и незначительных фишек в Visual Studio 2013 появилось несколько очень удобных фич, которых реально не хватало:
  1. Map mode. Теперь вместо скролбара для прокрутки кода справа можно активировать в опциях новый мега скрол с возможность проматывать код и одновременно видеть в попапе его содержимое.
  2. Доступ к буферу через Ctrl+Shift+V. Вот этого реально не хватало. Бывало такое, что скопировал кусок кода и понимаешь, что вот еще одну строчку тоже надо копирнуть? Теперь без проблем можно нажимать Ctrl+C еще раз. При вставке Ctrl+V вставляет содержимое активного буфера, а при нажатии Ctrl+Shift+V вставляет то, что было скопировано перед этим.
  3. Просмотр реализации функции в попапе Alt+F12. Теперь можно посмотреть реализацию функции, не переходя в другое окно, нажимаем Alt+F12 и вуаля! Всплывающий попап со скролом показывает всю подноготную исследуемого метода.
  4. В окне Autos можно смотреть, что возвращает текущий метод. Последнее по списку, но не последнее по полезности нововведение. Все наверняка сталкивались с такой ситуацией, когда отлаживаешь метод, который возвращает какое-то значение без сохранения ее в локальную переменную, что делает несколько затруднительным посмотреть его в отладчике. Теперь же в окне Autos можно совершенно спокойно просматривать, что возвращает метод. Например, у вас есть код return 12 + 34, и когда вы доходите до закрывающей фигурной скобки метода, в окне Autos отображается заветный результат 46.

Задача на алгоритм поиска в ширину на графе

Опубликовал admin 30 Декабрь 2013 в рубрике Алгоритмы. Комментарии: Комментарии отключены

What would be the best way to arrange a given sequence of number such that sum of any two adjacent number is a prime number. For e.g : 7,6,5,2,1,4,3 is a valid one sequence for arranging 1..7

Bitwise Stuff

Опубликовал admin 27 Декабрь 2013 в рубрике Алгоритмы. Комментарии: Комментарии отключены

1. Пусть N — такое число, что 0xff = 0xc0 + N. Напишите представление числа N в десятичной системе счисления.

2. You are given a number having only one “1″ its binary representation,. You have to find position of it?

3. Find if a number is of power of 2

4. Given an array of integers, write an algorithm that will check if the sum of any two is zero

Головоломка с выключателями

Опубликовал admin 26 Декабрь 2013 в рубрике Логические задачи. Комментарии: Комментарии отключены

Еще одна логическая задачка. Так же есть две полностью изолированные комнаты. В одной комнате на столе стоят 3 лампы, во второй – 3 выключателя. Каждый выключатель может включать одну лампу. Надо определить какой выключатель за какую лампу отвечает.

Экспериментатор только один – это Вы. Толькоодна попытка: сначала вы должны войти в комнату с выключателями. Затем вы должны войти в комнату с лампочками и определить какой выключатель за какую лампу отвечает. Никакими инструментами и измерительной техникой пользоваться нельзя.

Задачи с собеседований

Опубликовал admin 24 Декабрь 2013 в рубрике Логические задачи. Комментарии: Комментарии отключены

1. Перед вами прямоугольный стол и неограниченное количество монет достоинством 25 центов. Вы и ваш противник по очереди кладёте монеты на стол(каждый по одной), полностью плашмя (нельзя ставить на другие монеты или ребром), выигрывает тот после чьего хода у противника нет возможности положить монету на стол.

Ваш ход первый, какой стратегией следует воспользоваться, чтобы победить.

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