组合数学-输出所有路径-路径数问题
德玛西亚之力出装顺序-忐忑不安的反义词
组合数学-输出所有路径
一．程序
#include
#include
int
num1=1;全局变量主要是为了在遍历二叉树的时候，只对无禁止线段的路径数计数。
typedefstruct Point
{
intx,y;
};
typedefstruct node二叉树
{
}
Point data;二叉树的点坐标
intnum;主要是为了求经过此结点的次数C(x+y,y);
struct node
*lchl,*rchl;
*NODE;
struct Line禁止线段的结构体
{
Point start;
Point end;
};
boolbelongTo(Line l,Line line[],int n)
判断l是否属于禁止经过的线段，是则返回true;
{
int i;
for(i=0;i
if(.x==line[i].start.x
&&.y==line[i].start.y
&&.x==line[i].end.x
&&.y==line[i].end.y)
return true;
}
return false;
}
int C(intm,int
n) 返回组合数C(m,n)
{
double a=1.0,b=1.0;
int c;
int i;
for(i=0;i
for(i=n;i>0;i--)
b=b*(double)i;
c=ab;
return c;
}
void create(NODE &t,Point a) 创建二叉树，父结
点坐标为(x,y),左子树结点坐标为(x,y-1),右子
树结点坐标为(x-1,y)。直到所有
叶子结点为(0,0)为止。
{
Point r,l;左结点，右结点数据
r.x=a.x;r.y=a.y-1;
l.x=a.x-1;l.y=a.y;
t=(node*)malloc(sizeof(node));
t->data=a
t->num=C(a.x+a.y,a.y);
if(r.x<0||r.y<0)当x,y都小于0时停止创建结点
t->rchl=NULL;
else
create(t->rchl,r);递归创建右结点
if(l.x<0||l.y<0)
t->lchl=NULL;
else
create(t->lchl,l);
}
void prints(NODE
T)打印结点坐标(x,y)
{
if(T)
{
printf(
printf(
}
}
void
Ergodic(NODE T,intn,Line
line[])一次遍历，从根结点到叶子结点，找出其中一条路径
{
intb,i;b为此二叉树的层数
Line
l,p;父结点与子结点的一条线段，为了判断此线段是否属于禁止线段。
b=T->data.x+T->data.y;
if(T)结时点不为
{
num1++;上面的全局变量，如果此路径不含禁止线段，那么就直接加1,
for(i=0;i
if(T->num>=1)此结点的遍历次数>=1才继续遍历
{
T->num--;此结点的遍历次数-1
prints(T);打印此结点信息
=T->data;
=T->data;
if(T->rchl&&T->rchl->num>=1)如果左子
树存在，而且可以继续遍历此接结
{
=T->rchl->data;
点
if(!belongTo(l,line,n))父
子结点构成的线段与禁止线段进行比较，不同，
则继续
{
T=T->rchl;
}
else含有禁止线段，中断
{
printf(含有禁止路径
num1--;
break;
}
}
else
if(T->lchl&&T->lchl->num>=1)
{
=T->lchl->data;
if(!belongTo(p,line,n))
{
T=T->lchl;
}
else
{
printf(含有禁止路径
num1--;
break;
}
}
}
}
}
}
void main()
{
int x=5,y=3,i,h,j;x,y终点坐标
Point
data;终点坐标结点
data.x=x;data.y=y;
NODE
root;数的根结点
create(root,data)
以根结点(x,y)创建二叉树
h=root->num;总的路径数
int
n=3;禁止线段条数
Line *line=new Line[n];
line[0].start.x=2;
line[0].start.y=2;
line[0].end.x=3;
line[0].end.y=2;
line[1].start.x=4;
line[1].start.y=2;
line[1].end.x=5;
line[1].end.y=2;
line[2].start.x=6;
line[2].start.y=2;
line[2].end.x=6;
line[2].end.y=3;
line[3].start.x=7;
line[3].start.y=2;
line[3].end.x=7;
line[3].end.y=3;
for(i=0;i
printf(这是第%d条路径:n全局变量，
如果找到一条可以通过的路径，就+1，其他
数量不变。
Ergodic(root,4,line);
}
printf(
}
二.运行结果。
若所输出路径包含禁止线段，则如图所示：
三．整体思路：
根据二差树遍历，假设终点坐标为（x，y），那么二叉树的根节点就是（x
，y），他的两个子
节点就是（x-1，y），（x，y-1），以此类推，那么所有的叶子节点最终都
会为（0,0）.如图所
示：