C语⾔中的⼀个关于求正⽅形个数的算法题⽬
这是⼀个经典的C语⾔算法题⽬，题⽬是给出⼀个给定的图形，根据这幅图形⾥的作标可以求出这幅图形⼀共可有构成多少个正⽅形。
例如下⾯这个图形：
下⾯是解题思路：⾸先采⽤组合算法，得出这些顶点⼀共能构成多少个有四个顶点构成的四边形，并列出每⼀个四边形，然后⽤⼀个⼦函数对这四边形进⾏判断，若是正⽅形就加⼀，这样就可以得出⼀共含有多少个正⽅形。
具体代码：
#include<stdio.h>
#include<math.h>
/*输⼊的图形的顶点数量,⼀定要输⼊正确的顶点数量，修改这个值可以得到不同的点情况下的
正⽅形数量*/
#define N  13
#define B  ((N*(N-1)*(N-2)*(N-3))/(4*3*2))
c语言算法书籍typedef struct{
int x;
int y;
}Point;
typedef struct{
Point a[4];
}Squre;
Point dian[N];
Point queue[4];  /*存放矩形坐标*/
Squre tmp;
int k=0;
int  top=0;
void  comb(int s,int n,int m);
int  function(Squre s);
int main(void){
int i=0;
int num=(int)B;
printf("%d",num);
for(i=0;i<N;i++){
printf("\nplease input the %d zuo biao :",i+1);
scanf("%d %d",&dian[i].x,&dian[i].y);
}
comb(0,N,4);
printf("the sum of sibianxing are %d\n",k);
getch();
return 0;
}
}
/*判断是不是正⽅形，若是返回1，否则返回0*/
int function(Squre s){
int e,b,c,d,k;
e=pow((s.a[0].x-s.a[1].x),2)+pow((s.a[0].y-s.a[1].y),2);
b=pow((s.a[0].x-s.a[2].x),2)+pow((s.a[0].y-s.a[2].y),2);
if(e>b){ /*e作为对⾓线存在*/
c=pow((s.a[2].x-s.a[1].x),2)+pow((s.a[1].y-s.a[2].y),2);        d=pow((s.a[3].x-s.a[1].x),2)+pow((s.a[3].y-s.a[1].y),2);        k=pow((s.a[0].x-s.a[3].x),2)+pow((s.a[0].y-s.a[3].y),2);        if((b==c)&&(c==d)&&(d==k)&&(k==b)&&(e==(b+c)))            return 1;
}else if(e==b){
c=pow((s.a[1].x-s.a[3].x),2)+pow((s.a[1].y-s.a[3].y),2);        d=pow((s.a[2].x-s.a[3].x),2)+pow((s.a[2].y-s.a[3].y),2);        k=pow((s.a[1].x-s.a[2].x),2)+pow((s.a[1].y-s.a[2].y),2);        if((e==c)&&(c==d)&&((e+b)==k))
return 1;
}else {    /*b作为对⾓线存在*/
c=pow((s.a[2].x-s.a[1].x),2)+pow((s.a[1].y-s.a[2].y),2);        d=pow((s.a[3].x-s.a[2].x),2)+pow((s.a[3].y-s.a[2].y),2);        k=pow((s.a[0].x-s.a[3].x),2)+pow((s.a[0].y-s.a[3].y),2);        if((e==c)&&(c==d)&&(d==k)&&(k==e)&&(b==(e+c)))            return 1;
}
return 0;
}
/*组合算法：⽤于得到可能构成正⽅形的矩形集合
m代表选取的个数就是组合数C(m,n)，从n中选取m个点
并返回正⽅形数量*/
void  comb(int s,int n,int m)
{
int i,j=0;
if(s>n) return  ;
if(top==m) {
for(i=0;i<m;i++){
tmp.a[i]=queue[i];
}
j=function(tmp);
if(j==1){
k++;
}
return  ;
}
queue[top++]=dian[s];
comb(s+1,n,m);
top--;
comb(s+1,n,m);
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。