Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Динамическое программирование в образцах

Anna | 24.06.2014 | нет комментариев

Есть такой Дивный сайт выходного дня, как codeeval.com. На котором недурная коллекция маленьких алгоритмических задачек и комфортная система проверки, дозволяющая увлекательно провести вечер скучающим программистам. Как правило в качестве входных данных применяется файл с тестовыми данными. Впрочем мне попалась одна задача, в которой тестовые данные вестимы предварительно. Загружать программу, которая будет легко выводить верный результат не спортивно, а вот вычислять его на этапе компиляции — самое то.

Что из этого получилось дозволено посмотреть внутри. 

Задача сама по себе не трудная и рекурсивно решается дюже легко. Скажем с поддержкой вот такой вот функции:

int GetRouteCount(int map, int x, int y) {
	if ((x == -1) || (y == -1) || (x == 4) || (y == 4)) return 0;

	if ((x == 3) && ( y == 3))  return 1;

	if ( ( map & (1 << ( ( x << 2)  y) )) != 0 ) return 0;

	map |= (1 << ( (x << 2)  y));

	return	GetRouteCount(map, x-1, y)  
			GetRouteCount(map, x 1, y)  
			GetRouteCount(map, x, y-1)  
			GetRouteCount(map, x, y 1);
}

И собственно приобретение итога:

int result = GetRouteCount(1, 0, 1) << 1;

Сейчас испробуем провернуть эти же вычисления в образцах. Как параметры образца нам нужно передавать «карту» перемещений и координаты нынешней точки. Так как взамен if будет применяться специализация, то для проверки на посещение точки нужно сделать обособленный образец, у которого будет специализация на такой случай. Если попытаться добавить еще один параметр в стержневой образец, то возникнут неразрешимые обстановки на этапе компиляции. Выглядеть проверка на посещение будет вот так:

template< template<int, int, int> class _MR, int map, int x, int y, bool visited>
struct GetCount {
	enum Result
	{
		value =	_MR<(map | (1 << ( ( x << 2)  y ))), (x-1), y>::value  
				_MR<(map | (1 << ( ( x << 2)  y ))), (x 1), y>::value  
				_MR<(map | (1 << ( ( x << 2)  y ))), x, (y-1)>::value  
				_MR<(map | (1 << ( ( x << 2)  y ))), x, (y 1)>::value
	};
};

template< template<int, int, int> class _MR, int map, int x, int y>
struct GetCount<_MR, map, x, y, true> {
	enum Result { value = 0 };
};

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

template <int map, int x, int y>
struct MapRoute {
	enum Result { value = GetCount<MapRoute, map, x, y, ( (map & ( 1 << ( (x << 2)  y))) != 0 )>::value };
};

template<int map, int y>
struct MapRoute<map, -1, y> {
	enum Result { value = 0 };
};

template<int map, int y>
struct MapRoute<map, 4, y> {
	enum Result { value = 0 };
};

template<int map, int x>
struct MapRoute<map, x, -1> {
	enum Result { value = 0 };
};

template<int map, int x>
struct MapRoute<map, x, 4> {
	enum Result { value = 0 };
};

template<int map>
struct MapRoute<map, 3, 3> {
	enum Result { value = 1 };
};

Вот и готово, приобретение итога выглядит примерно так же немногословно, как и в варианте вычисления в рантайме:

int result = MapRoute<0, 0, 0>::value;

Посмотреть каждый код и итог его выполнения дозволено пройдя по ссылке.

 

Источник: programmingmaster.ru

 

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB