程序设计方法与艺术 小组解题报告模板.docVIP

题目A 旅行路线的数目 一个正方形的小镇被分成N2个小方格，Betsy要从左上角的方格到达左下角的方格，并且经过每个方格恰好一次。编程对于给定的N，计算出Betsy能采用的所有的旅行路线的数目 解题思路： 这道题目很明显是道有哪些信誉好的足球投注网站题，关键在于优化。而有哪些信誉好的足球投注网站题的优化主要就是剪枝。 首先很容易想到，因为Betsy是任意的走，当ｎ取到５或６时，它的方案总数就已经很大了，方案数越是大，有哪些信誉好的足球投注网站时，不要用的枝就会越多，而且这些枝占方案总数的比例相当大。如果能知道什么情况下，会出现必然无解，就能很好的提高效率了。于是由此知道，此题用剪枝的方法做是正确的。 具体解法： 首先从题目的条件入手，题目要求每一个各自都必须走到，而且每一个格子只能走一遍。这两个条件就指出了这道题目的可剪的枝条中的两个。 然后从这两条出发，仔细分析一下，到底在什么情况下会不满足题目的要求。 第二个条件要求每个格子只能走一遍，这很简单，用一个数组记录一下到底有哪些格子是已经经过了的，那些是还没有经过的，在Betsy移动时，就只移动到那些还没有经过的格子中去，这样就避免了一个格子走两遍。 第一个条件要求每个格子都要经过一次，这是个很难满足的条件，有很多无解的情况就是因为不满足它，那到底有哪些情况会导致不满足着一个条件呢。比方说下面的几个图。图中箭头表示Betsy的行走路线。 如图１，其中的黄色区是不能达到的，如果到达了黄色区，就别再想到最左下角了，因为，这个区域只有一个入口，没有出口，进得去，出不来。于是，就一般的情况来说，每一个还没有到过得格子（除开终点）都必须要有两个空格子与之相连接（Betsy当前所在的格子算是个空格子），这样才能保证Betsy既可以移进这个格子又可以移出这个格子。 　　　　　图１　　　　　　　 再如图２，其中的红色格子是不可能达到了，虽然它满足每一个格子都有两个相邻的空格子，但是，Betsy是不可能移动到这些红格子中去了，这几个格子被隔断了。一般化，Betsy行走的路径不能够圈出一个独立的块出来，否则这一块是没有办法走到的。 　　　　　 图２ 图２中的独立的一块要如何判断，难道要进行一次有哪些信誉好的足球投注网站求得？不。看一下的几种情况，仅当出现这几种情况时，会分割出一个独立的块。 图中绿色格子表示Betsy现在所在的格子，黑色格子表示Betsy已经走过的格子，空格子是没有经过的格子。仅当Betsy沿箭头方向移动时会分割出两块相对独立的块，Betsy只能到达其中的一块，而另一块是不可能到达的，于是这种情况不满足条件二，应当予以排除。 当然，还有一种情况，如果想到了，程序速度可以加快很多，就是，最左下角的格子必须是最后走，如果还没把所有的格子都走到就到了终点是不合要求的。 有了这三条剪枝，速度就可以猛增了。下面进行一下对比。 数据n 答案 没有用任何剪枝的程序耗时 用了三种剪枝的程序耗时 1 1 0 s 0 s 2 1 0 s 0 s 3 2 0 s 0 s 4 8 0 s 0 s 5 48 0 s 0 s 6 1770 3．72 s 0 s 7 88418 〉30 min 0．83 s 其实这个题目还有其它的剪枝，但是对于这些数据，不能取得很明显的效果，就不与介绍，但是如果要计算更大的数据，还是有枝可剪的。 代码实现： #include iostream #include String #include stdlib.h using namespace std; int main() { string num; long f[20][20]={},max,t; int k; while(cinnum){ cink; for(int i=0;inum.length();i++) { f[i][0]=atoi(num.substr(0,i+1).c_str()); } for(int m=1;mk;m++) for(int j=0;jnum.length();j++) { max=0; for(int x=0;xj;x++) { if((t=f[x][m-1]*atoi(num.substr(x+1,j-x).c_str()))max) { max=t; } }