A点有一个卒,需要走到目标B点.行走规则:可以向下(共4步)或者向右(共8步).要求计算从A能够到达B的路径的条数,并输出每一条路径.
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/22 00:58:13
![A点有一个卒,需要走到目标B点.行走规则:可以向下(共4步)或者向右(共8步).要求计算从A能够到达B的路径的条数,并输出每一条路径.](/uploads/image/z/6838094-38-4.jpg?t=A%E7%82%B9%E6%9C%89%E4%B8%80%E4%B8%AA%E5%8D%92%2C%E9%9C%80%E8%A6%81%E8%B5%B0%E5%88%B0%E7%9B%AE%E6%A0%87B%E7%82%B9.%E8%A1%8C%E8%B5%B0%E8%A7%84%E5%88%99%EF%BC%9A%E5%8F%AF%E4%BB%A5%E5%90%91%E4%B8%8B%EF%BC%88%E5%85%B14%E6%AD%A5%EF%BC%89%E6%88%96%E8%80%85%E5%90%91%E5%8F%B3%EF%BC%88%E5%85%B18%E6%AD%A5%EF%BC%89.%E8%A6%81%E6%B1%82%E8%AE%A1%E7%AE%97%E4%BB%8EA%E8%83%BD%E5%A4%9F%E5%88%B0%E8%BE%BEB%E7%9A%84%E8%B7%AF%E5%BE%84%E7%9A%84%E6%9D%A1%E6%95%B0%2C%E5%B9%B6%E8%BE%93%E5%87%BA%E6%AF%8F%E4%B8%80%E6%9D%A1%E8%B7%AF%E5%BE%84.)
A点有一个卒,需要走到目标B点.行走规则:可以向下(共4步)或者向右(共8步).要求计算从A能够到达B的路径的条数,并输出每一条路径.
A点有一个卒,需要走到目标B点.行走规则:可以向下(共4步)或者向右(共8步).要求计算从A能够到达B的路径的条数,并输出每一条路径.
A点有一个卒,需要走到目标B点.行走规则:可以向下(共4步)或者向右(共8步).要求计算从A能够到达B的路径的条数,并输出每一条路径.
/*
A点有一个卒,需要走到目标B点.行走规则:可以向下(共4步)或者向右(共8步).
要求计算从A能够到达B的路径的条数,并输出每一条路径.
题目描述的是一种在二维空间中情形.设 X 轴为从左到右,Y轴为从上到下.
有 A 和 B 两点,第 1 维(X轴)距离d[1]=8,第 2 维(Y轴)距离 d[2]=8,
因此沿着点A到点B的向量为(8,4) .每次沿着向量的一个方向(X轴或Y轴)运动一个单位,
也就是每次可以移到(1,0)或者(0,1).计算从A到达B的路径条数.
一般的情形是:
在 D 维空间中,有A,B两点,
这两点在第 1 维距离d[1],第 2 维距离d[2],...,第D维的距离d[D],
因此沿着点A到点B的向量为(d[1],d[2],...,d[D]).每次沿着向量的一个方向运动一个单位,
也就是每次可以移动(±1,0,...,0)或者(0,±1,...,0),...,或者(0,0,...,±1),
这里的第 i 个 ±1,实际只能取+1或者-1,具体正负性和相应的 d[i] 一样.
计算从A到达B的路径条数.
解决的方案:
我们针对题目描述的二维空间的情形进行分析.
点A到点B的向量为(8,4) 定下来后,因为每次只能沿着向量的一个方向(X轴或Y轴)运动一个单位,
而这两个方向是正交的,也就是互不影响的.
不管先走X方向,还是先走Y方向,最后都一定是向X方向走 8 步,向 Y 方向走 4 步.
假设开始沿 X 方向运动一个单位,我们假设到达了点 A' .
那么点 A' 到点 B 的向量为(7,4) ,下面问题就是计算 A' 到达 B 的路径条数.
可以发现,问题“计算 A 到达 B 的路径条数”和问题“计算 A 到达 B 的路径条数”是同一类问题.
假设开始沿 Y 方向运动一个单位,我们假设到达了点 A'' .
那么点 A'' 到点 B 的向量为(8,3) ,下面问题就是计算 A'' 到达 B 的路径条数.
可以发现,问题“计算 A 到达 B 的路径条数”和问题“计算 A'' 到达 B 的路径条数”是同一类问题.
通过上面的两个假设可以发现,不管第一步怎么走,接下来都产生了一个相似的子问题.
这就是分治的策略,也就是把一个大问题,分解成若干个相似的子问题.
上面的两个假设,最后的一个子问题必定是某点到 B 的向量为(1,0),
或者某点到 B 的向量为(0,1),这是能立即解决的子问题.
*/
#include
#include
// 当前需要的维度,可以修改这个值进行扩展(不用改动算法)
#define DIMENSION 2
// 每个维度的最大长度
#define MAX_LENGTH_PER_DIMENSION 100
// 空间最小的移动向量.一次只能在一个维度移动一个单位.
struct Step
{
// 维度索引
int index;
// 移动距离
int d;
};
/*
根据向量距离 distance ,计算每个维度上的最小移动单位.
通过 steps 和 stepsAmount 返回.
注意:如果向量距离某个维度上的的距离为 0 ,那么这个维度上不会返回最小移动单位.
*/
void getSteps(int distance[],struct Step steps[],int *stepsAmount)
{
int i;
*stepsAmount=0;
for(i=0;i0 1 :-1;
(*stepsAmount) ++;
}
}
}
// 打印最小移动单位
void printStep(const struct Step* step)
{
int i;
// 对于小于等于二维的坐标系,可以为每一步指定上下左右四个方向
if(DIMENSION index == 0)
{
if(step->d > 0)
printf("右");
else
printf("左");
}
else if(step->index == 1)
{
if(step->d > 0)
printf("下");
else
printf("上");
}
}
// 对于大于二维的坐标系,直接输出移动向量.
else
{
printf("[");
for(i=0;iindex step->d :0);
if(i != DIMENSION-1)
printf(",");
}
printf("]");
}
}
void getPath(int distance[],
struct Step path[],int pathLength,int *totalSchemeAmount)
{
int i,j,k,d;
struct Step steps[DIMENSION];
int stepsAmount;
// 计算需要移动的总距离
for(i=0,d=0;i