算法分析——>跳格子
学校的趣味运动会，其中的一个项目是：跳格子。
地上画着一些格子，每个格子里写一个字，如下所示：
比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。 一直要跳到“华”字结束。
要求跳过的路线刚好构成“从我做起振兴中华”这句话。
请你算一算共有多少种可能的跳跃路线呢？
问题分析：
根据题目我们可以知道此题要求我们算出从左上角到右下角单元格的所有可能性，而且根据文字的排列规律你可以发现行走路线只能是向右或者向左移动，那么我们只需遍历图表中的所有可能情况就可，首当想到递归的方法来解决此题，将图中“从我做起振兴中华”八个字分别对应1、2、3、4、5、6、7、8 则得到新的表格如下：
使用递归方法求解：
public class RevitalizeChina01 {
static int count=0; //累加器
public static void main(String args[])
{
int map[][]={{1,2,3,4,5},{2,3,4,5,6},{3,4,5,6,7},{4,5,6,7,8}}; //初始化地图
find(0,0,map); //由起点“从”字开始遍历地图
System.out.println(count); //输出最后统计结果
}
public static void find(int i,int j,int map[][]) //此方法用于递归遍历地图中所有元素
{
if(map[j]==8){ //设置退出条件，诺最后值为8（即“华”字）退回上一层
count++; //满足条件累加
return;
}
if(i < 4 && j + 1 < 5) { //向右继续遍历地图
if(map[j] + 1 == map[j + 1]) { //判断下一个单元格是否满足 (i的下一个单元格 = i+1)
find(i, j + 1, map);
}
}
if(i + 1 < 4 && j < 5) { //向下继续遍历地图
if(map[j] + 1 == map[i + 1][j]) {
find(i + 1, j, map);
}
}
}
}
运行结果： 35
以上的确输出了正确结果，可是有没有更好的方法呢？
上面的程序多次递归，肯定会影响到程序效率，由于本题只是个4行5列的表格，如果百行百列、千行前列呢？肯定会使程序竟如长期循环状态，效率大大折扣，能不能找到一种更简洁、快速的方法来解决此问题呢？
深入分析：
其实通过原图中的文字排列顺序，以及只能向下或向右行走的限制，我们会发现无论多大的表格，它的首行首列只能走一边，那么我们就可初始化出以下这张图：
（图中单元格中存放的是此单元格被行走的总次数,0为默认值，还未进行计算）
那么，这些单元格之间有些什么规律呢？
其实，我们可以试想一下：map[1][1]这个单元格会被走几次？
很明显只能是两次，由于只能向下或向右行走，它也就只能被 map[0][1] 和 map[1][0] 各走一边，细心的小伙伴们可能已经发现：
当前单元格被行走的次数 = 上面的单元格行走次数 + 左面的单元格行走次数
（即：map[j] = map[i-1][j] + map[j-1] )
那么利用此公式我们便可计算出任意单元格的行走次数：
public class RevitalizeChina02 {
public static void main(String args[]){
int map[][]=new int[4][5]; //初始化地图，默认值0
for(int i=0;i<4;i++)
for(int j=0;j<5;j++)
{
if(j==0||i==0) //将第一行，第一列值设置为1
{
map[j]=1;
}
}
for(int i=1;i<4;i++) //遍历还未设值的其他所有单元格
{ for(int j=1;j<5;j++)
{
map[j]=map[i-1][j]+map[j-1]; //通过公式计算当前单元格中的总次数
}
}
for(int i=0;i<4;i++)
{ for(int j=0;j<5;j++)
{
System.out.print("\t"+map[j]);
}
System.out.println();
}
}
}
运行结果：
通过我们的简单分析，将设计出了更为合理的简单算法，使得程序更简洁，在实际开发中可能通过分析后写出的代码往往不易于程序员阅读，但能大大提高程序的运行速度，而要设计出更为合理的代码对程序员的算法要求相当高，此题只是举例说明，并无多大技术含量，为了成为心中的黑马，一起努力吧！！
:handshake :handshake :handshake :handshake :handshake :handshake 诺有更好的设计算法或其他题型，欢迎分享！！！:handshake :handshake :handshake :handshake :handshake :handshake :handshake
收藏
淘帖
踩
