Прошлой ночью я пытался решить задачу № 15 от Project Euler:
Начиная с верхнего левого угла сетки 2 × 2, есть 6 маршрутов (без возврата) в нижний правый угол.
![alt text]()
(источник: projecteuler.net)Сколько маршрутов проходит через сетку 20 × 20?
Я подумал, что это не должно быть так сложно, поэтому я написал базовую рекурсивную функцию:
const int gridSize = 20;
// call with progress(0, 0)
static int progress(int x, int y)
{
int i = 0;
if (x < gridSize)
i += progress(x + 1, y);
if (y < gridSize)
i += progress(x, y + 1);
if (x == gridSize && y == gridSize)
return 1;
return i;
}
Я проверил, что он работает для меньших сеток, таких как 2 × 2 или 3 × 3, и затем установил его для сетки 20 × 20. Представьте себе мое удивление, когда через 5 часов программа все еще успешно разбирала цифры, и только около 80% сделали это (основываясь на изучении ее текущей позиции/маршрута в сетке).
Очевидно, я иду по этому пути неправильно. Как бы вы решили эту проблему? Я думаю, что это должно быть решено с использованием уравнения, а не метода, подобного моему, но это, к сожалению, не сильная сторона моего.
Обновление:
У меня сейчас есть рабочая версия. В основном он кэширует результаты, полученные до того, как блок × m еще предстоит пройти. Вот код вместе с некоторыми комментариями:
// the size of our grid
static int gridSize = 20;
// the amount of paths available for a "NxM" block, e.g. "2x2" => 4
static Dictionary<string, long> pathsByBlock = new Dictionary<string, long>();
// calculate the surface of the block to the finish line
static long calcsurface(long x, long y)
{
return (gridSize - x) * (gridSize - y);
}
// call using progress (0, 0)
static long progress(long x, long y)
{
// first calculate the surface of the block remaining
long surface = calcsurface(x, y);
long i = 0;
// zero surface means only 1 path remains
// (we either go only right, or only down)
if (surface == 0)
return 1;
// create a textual representation of the remaining
// block, for use in the dictionary
string block = (gridSize - x) + "x" + (gridSize - y);
// if a same block has not been processed before
if (!pathsByBlock.ContainsKey(block))
{
// calculate it in the right direction
if (x < gridSize)
i += progress(x + 1, y);
// and in the down direction
if (y < gridSize)
i += progress(x, y + 1);
// and cache the result!
pathsByBlock[block] = i;
}
// self-explanatory :)
return pathsByBlock[block];
}
Вызов его 20 раз для сеток с размерами от 1 × 1 до 20 × 20 дает следующий результат:
There are 2 paths in a 1 sized grid
0,0110006 seconds
There are 6 paths in a 2 sized grid
0,0030002 seconds
There are 20 paths in a 3 sized grid
0 seconds
There are 70 paths in a 4 sized grid
0 seconds
There are 252 paths in a 5 sized grid
0 seconds
There are 924 paths in a 6 sized grid
0 seconds
There are 3432 paths in a 7 sized grid
0 seconds
There are 12870 paths in a 8 sized grid
0,001 seconds
There are 48620 paths in a 9 sized grid
0,0010001 seconds
There are 184756 paths in a 10 sized grid
0,001 seconds
There are 705432 paths in a 11 sized grid
0 seconds
There are 2704156 paths in a 12 sized grid
0 seconds
There are 10400600 paths in a 13 sized grid
0,001 seconds
There are 40116600 paths in a 14 sized grid
0 seconds
There are 155117520 paths in a 15 sized grid
0 seconds
There are 601080390 paths in a 16 sized grid
0,0010001 seconds
There are 2333606220 paths in a 17 sized grid
0,001 seconds
There are 9075135300 paths in a 18 sized grid
0,001 seconds
There are 35345263800 paths in a 19 sized grid
0,001 seconds
There are 137846528820 paths in a 20 sized grid
0,0010001 seconds
0,0390022 seconds in total
Я принимаю ответ Данбена, потому что он помог мне найти это решение наиболее. Но возражает также Тим Гудман и Агос :)
Бонусное обновление:
Прочитав ответ Эрика Липперта, я еще раз посмотрел и несколько переписал его. Основная идея все та же, но часть кэширования была удалена и помещена в отдельную функцию, как в примере с Эриком. В результате получается более элегантный код.
// the size of our grid
const int gridSize = 20;
// magic.
static Func<A1, A2, R> Memoize<A1, A2, R>(this Func<A1, A2, R> f)
{
// Return a function which is f with caching.
var dictionary = new Dictionary<string, R>();
return (A1 a1, A2 a2) =>
{
R r;
string key = a1 + "x" + a2;
if (!dictionary.TryGetValue(key, out r))
{
// not in cache yet
r = f(a1, a2);
dictionary.Add(key, r);
}
return r;
};
}
// calculate the surface of the block to the finish line
static long calcsurface(long x, long y)
{
return (gridSize - x) * (gridSize - y);
}
// call using progress (0, 0)
static Func<long, long, long> progress = ((Func<long, long, long>)((long x, long y) =>
{
// first calculate the surface of the block remaining
long surface = calcsurface(x, y);
long i = 0;
// zero surface means only 1 path remains
// (we either go only right, or only down)
if (surface == 0)
return 1;
// calculate it in the right direction
if (x < gridSize)
i += progress(x + 1, y);
// and in the down direction
if (y < gridSize)
i += progress(x, y + 1);
// self-explanatory :)
return i;
})).Memoize();
Кстати, я не мог придумать лучшего способа использовать два аргумента в качестве ключа для словаря. Я немного погуглил, и, похоже, это общее решение. Ну что ж.
