wuheji.cpp

无和集问题求解算法

#include<iostream.h>
#include"windows.h"
  int a[100][100];//第一行用作计数，其余每行作为一个集合
  int n,k=1,j=0,l=0;
  int test(int k,int i)//检测函数
  {
	  int p,q,s=1;
      for(p=0;p<a[0][i]-1;p++)
	  {
	  for(q=1;q<a[0][i];q++)
	  {
	    if(a[i][p]+a[i][q]==k) 
		{
		 s=0; 
		   break;
		}
   
	  }
  }
 return(s); 
}
void insert(int n,int k)//插入函数
{
  int i,m;
  for(i=1;i<=n;i++)
  {    
	  m=a[0][i];
	 
	   if(test(k,i)==1)
	   {
	      a[i][m]=k;
	      k++;
	      a[0][i]++;
	      insert(n,k);
		  a[0][i]--;
		  k--;
	   } 
  }
if(k-1>l)l=k-1;
}
void main()//主函数
{   int p,q;
	cout<<"输入n值"<<endl;
	cin>>n;
	for(p=0;p<n;p++)
	{
		for(q=0;q<100;q++)
			a[p][q]=0;
	}
	if(n==1)cout<<"k值为1";
	else{
	a[1][0]=1;
    a[0][1]=1;
	k=2;	
   insert(n,k);
	}
   cout<<"所求K值为"<<l<<endl;//所求得最大k值
   cin>>q;
}