划分凸多边形

10343 划分凸多边形
时间限制:1000MS 内存限制:65535K 提交次数:0 通过次数:0
题型: 编程题语言: 无限制
描述
问题描述：一个正凸N边形，可以用N-3条互不相交的对角线将正N边形分成N-2个三角形。
现在要求读入N边形的N（N≤20），输出不同划分方法的总数（要求解的是划分方法数，而不需要输出各种划分法）。
这里，注意：
1）顶点可编号，认为顶点皆不相同，因此不允许认为将凸N边形转置视为相同划分。
2）若输出是“No answer”，请注意大小写和无标点。
输入输出举例：
输入: N＝3， 输出：1
输入：N＝5， 输出：5
输入：N＝2， 输出：No answer
输入：N＝6， 输出：14
输入：N＝8， 输出：132
例如：
当N＝5时，共有5种分法。
当N＝6时，对六边形的三角形所有划分，请看下图:
输入格式
7
N，代表正凸N边形。
输出格式
不同划分方法的总数。
输入样例
5
输出样例
5

8

------------------------------------------

10343划分凸多边形（递归、分治）

（非递归)

#include<stdio.h>

#include<malloc.h>

intmain()

{

intn,i,j;

int*p;

{

scanf("%d",&n);}while(n>20);

if(n<3)

{

printf("Noanswer");return0;}

else

{

p=(int*)malloc((n+1)*sizeof(int));

p[1]=1;

for(i=2;i<=n;i++)

{p[i]=0;

for(j=1;j<i;j++)

p[i]+=p[j]*p[i-j];

}

printf("%d\n",p[n-1]);

return0;}

}

（递归)

#include<stdio.h>

intP(intn)

{

intsum=0,temp=0,k;

if(n==1)return1;

elseif(n>1)

{

for(k=1;k<n;k++)

{

temp=P(k)*P(n-k);

sum+=temp;

}

returnsum;

}

elsereturn0;

}

intmain()

{

intn;

{scanf("%d",&n);}while(n>20);

if(n<3)

{

printf("Noanswer");return0;}

else{printf("%d",P(n-1));

return0;}

}