项目欧拉＃15

本文介绍了项目欧拉＃15的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

昨天晚上我试图从项目欧拉解决挑战＃15：

在 2×2网格的左上角开始，有6个路由（无回溯）到右下角。

通过 20×20格？

我想这多少路在那里不应该这么辛苦，所以我写了一个基本的递归函数：

const int的gridSize = 20; //与正在进行的呼叫（0，0）静态INT进步（INT X，int y）对 { INT I = 0; 如果（X< gridSize） I + =进度（X + 1，Y）; 如果（Y< gridSize） I + =进步（X，Y + 1）; 如果（X == gridSize&放大器;&安培; Y == gridSize）返回1; 回报我; }

我验证了它为一个较小的网格，如2×2或3 ×3，然后将其设置为一个20×20的网格上运行。想象一下，我的惊讶，当，5个小时后，该计划仍在兴高采烈地捣弄数字，只有约80％了（根据检查其当前位置在网格/路由）。

显然，我会对此错误的方式。你将如何解决这个问题？我想它应该使用一个公式，而不是像我这样的方法来解决，但是这不幸的是不是我的坚强的一面。

更新：

我现在有一个工作版本。基本上它缓存，当N×M挡仍有待运行之前获得的结果。下面是一些意见沿着代码：

//我们的电网静态INT gridSize = 20的大小; //路径可用于N×M的块的数量，例如， 2×2=> 4 静态字典<字符串，长> pathsByBlock =新词典<字符串，长>（）; //计算块终点线静态长calcsurface（长×长Y） {返回的表面（gridSize - X）* （gridSize - Y）; } //调用使用进度（0，0）静态长进度（长×长Y） { //先计算块剩余长面= calcsurface（X，Y）的表面; 长I = 0; //零表面意味着只有1路依然 //（我们或者去唯一正确的，或者只向下）如果（表面== 0）返回1; //创建剩余 //块的文本表示，为在辞典串块=（gridSize - x）的使用+×+（gridSize - Y）; //如果同一块以前没有如果（！pathsByBlock.ContainsKey（块）） { //计算它的方向是正确处理如果（X< gridSize）I + =进度（X + 1，Y）; //和在向下方向如果（γ&下; gridSize） I + =进展（X，Y + 1）; //并缓存的结果！ pathsByBlock [块] =我; } //言自明:) 返回pathsByBlock [块] }

调用它的20倍，对于大小为1格×1到20×20产生下面的输出：

有一个1大小的格 0,0110006秒 2路中有一个2大小的网格 6分配路径0,0030002秒 中有一个3大小的网格 0，秒 $ b 20分配路径$ b中有一个4大小的网格0秒 70的路径中有一个5大小的网格0秒 有252路径924路径中6大小的网格0秒 中有一个7大小的网格0秒 3432的路径中有一个12870路径8大小的网格0001秒 中有一个9大小的网格 48620路径0,0010001秒 中有一个10尺寸184756路径格0001秒 中有一个11大小的网格0秒 705432路径中有12大小的网格$ b $二百七万四千一百五十六路径b 0，秒 中有一个13大小的网格 10400600路径0001秒 中有14大小的网格0秒$四千〇十一万六千六路径b $ b本章是一个15大小的网格 0，秒 155117520路径中有16大小的网格 0,0010001秒$ b $六亿○一百○八万○三百九十○路径b 本章是一个17大小的网格 2333606220路径0001秒 中有18大小的网格0001秒 $ b $九十亿七千五百一十三万五千三路径b本章是一个19大小的网格 35345263800路径0001秒 中有20大小的网格 137846528820路径0,0010001秒 0 ，0390022秒共

我接受danben的答案，因为他帮我找到这个解决方案最。但也upvotes蒂姆·古德曼和阿戈：）

奖金更新

阅读埃里克利珀的回答后，我又外观和重写了它一些。其基本思想仍然是相同的，但缓存部分已被取出，放在一个单独的功能，如在Eric的例子。其结果是一些更优雅寻找代码。

//我们的电网常量的大小INT gridSize = 20 ; //魔法。 静态Func键&下; A1，A2，R GT; memoize的< A1，A2，R>（本功能使< A1，A2，R&F）的温度 { //返回一个函数，它为f与缓存。 变种词典=新词典<字符串，R>（）; 返回（A1 A1，A2 A2）=> { R R; 串键= A1 +X+ A2; 如果 { //不在高速缓存尚未 R = F（A1，A2）（dictionary.TryGetValue（标号，OUT R）！）; dictionary.Add（键，R）; } 回报率 - [R; }; } //计算块终点线静态长calcsurface（长×长Y） {返回的表面（ gridSize - X）*（gridSize - Y）; } //调用使用进度（0，0）静态Func键<长，很长很长>进度=（（Func键<长，很长很长>）（（长×长Y）=> { //先计算出块的表面剩余长面= calcsurface（X，Y）; 长I = 0; //零表面意味着只有1路依然 //（我们或者去唯一正确的，或者只下） 如果（表面== 0）返回1， //计算它在正确的方向如果（X< gridSize）I + =进展（X + 1，Y）; //和在向下方向如果（γ&下; gridSize）$ b $双向+ =进展（X，Y + 1）; //言自明:) 回报我; }））memoize的（）;

顺便说一句，我想不出更好的方式来使用这两个参数作为重点为字典。我用Google搜索了一下周围，似乎这是一个通用的解决方案。 。//en.wikipedia：哦

解决方案

这可多，如果你使用的动态规划（存储子问题的结果，而不是重新计算它们）。动态编程可以应用到表现出最优子问题 - 这意味着它们的最佳解决方案可以从最优解被构造为子问题（信用维基）。

我宁愿不放弃的答案，而是考虑如何的路径右下角的数量可能与路径数量。以相邻的广场

另外 - 如果你要手工工作了这一点，你会怎么办呢

Last night I was trying to solve challenge #15 from Project Euler :

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20×20 grid?

I figured this shouldn't be so hard, so I wrote a basic recursive function:

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; }

I verified that it worked for a smaller grids such as 2×2 or 3×3, and then set it to run for a 20×20 grid. Imagine my surprise when, 5 hours later, the program was still happily crunching the numbers, and only about 80% done (based on examining its current position/route in the grid).

Clearly I'm going about this the wrong way. How would you solve this problem? I'm thinking it should be solved using an equation rather than a method like mine, but that's unfortunately not a strong side of mine.

Update:

I now have a working version. Basically it caches results obtained before when a n×m block still remains to be traversed. Here is the code along with some comments:

// 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]; }

Calling it 20 times, for grids with size 1×1 through 20×20 produces the following output:

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

I'm accepting danben's answer, because his helped me find this solution the most. But upvotes also to Tim Goodman and Agos :)

Bonus update:

After reading Eric Lippert's answer, I took another look and rewrote it somewhat. The basic idea is still the same but the caching part has been taken out and put in a separate function, like in Eric's example. The result is some much more elegant looking code.

// 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();

By the way, I couldn't think of a better way to use the two arguments as a key for the dictionary. I googled around a bit, and it seems this is a common solution. Oh well.

解决方案

This can be done much faster if you use dynamic programming (storing the results of subproblems rather than recomputing them). Dynamic programming can be applied to problems that exhibit optimal substructure - this means that an optimal solution can be constructed from optimal solutions to subproblems (credit Wikipedia).

I'd rather not give away the answer, but consider how the number of paths to the lower right corner may be related to the number of paths to adjacent squares.

Also - if you were going to work this out by hand, how would you do it?