stirling (表).cpp

计算机组合数学中 stirling 数的实现。STL 实现

//**************************************************************************/
/*                           stirling (表)                                 */
//**************************************************************************/

#include <iostream>
#include <set>
#include <algorithm>
#include <utility>
#include <vector>
#include <iomanip>
using namespace std;

typedef pair<int ,int >num;

class stirling
{
public:
	stirling():x1(x1),m(m),n(n),pa(pa),pa1(pa1),pa2(pa2),ms(0){}
	void Print();
	void S(int x, int y);
	~stirling(){delete ms;}
private:
	int x1,m,n;
	num pa,pa1,pa2;
	multiset<num> * ms;	
};

void main()
{
	stirling q;
	q.Print();
}

void stirling::Print()
{
	vector<int > * svec= new vector<int>;
	vector<int>::iterator iter;
    ostream_iterator<int> screen(cout,"      ");

	cout<<"Ener a num:";
	cin>>m;

	for (int i=1;i<=m;i++)
	{
		svec->push_back(i);
	}
	cout<<"       ";
    copy(svec->begin(),svec->end(),screen);
	cout<<endl;

	iter=svec->begin();
	while (iter!=svec->end())
	{
		cout<<*iter<<"      ";
		for (i=1;i<=*iter;i++)
		{
			x1=*iter;
			S(x1,i);
		}
		cout<<endl;
		iter++;
	}
}

void stirling::S(int x, int y)
{	
	ms = new multiset<num>;
	multiset<num>::iterator iter;
	bool yes_no = true;
	
	pa.first=x;
	pa.second=y;
	
	ms->insert(pa);

   while(yes_no)
   {
	   iter=ms->begin();
	   while (iter!=ms->end())
	   {
		   if ((*iter).first!=(*iter).second||(*iter).second!=1)
		   {	
			if ((*iter).first-1>0&&(*iter).second-1>0)
			{
			   if ((*iter).first>(*iter).second)
			   {
			
			      pa1.first=(*iter).first-1;
			      pa1.second=(*iter).second-1;
			      ms->insert(pa1);	
				  
				  pa2.first=(*iter).first-1;
				  pa2.second=(*iter).second;
				  for (int i=0;i<(*iter).second;i++)
				  {
					  ms->insert(pa2);
				  }
				  ms->erase(iter); 
				  break;			
			   }
			
			}

		}

		if ((*iter).first==(*iter).second||(*iter).second==1)
		{
			iter++;
		}
	}
/*
	iter=ms.begin();

	while (iter!=ms.end())
	{
		cout<<"S"<<"("<<(*iter).first<<","<<(*iter).second<<") ";
		iter++;
	}
	cout<<endl;
	
*/
        iter=ms->begin();
		while (iter!=ms->end())
		{
			if ((*iter).first==(*iter).second||(*iter).second==1)
			{
				yes_no=false;
			}
			else
			{
				yes_no=true;
				break;
			}
			iter++;
		}			    
}

        n=ms->size();
		cout<<left;
        cout<<setw(7)<<n;
}