interpatitionview.cpp

这是一个算法当中的一个关于整数划分的程序

// INTERPATITIONView.cpp : implementation of the CINTERPATITIONView class
//

#include "stdafx.h"
#include "INTERPATITION.h"

#include "INTERPATITIONDoc.h"
#include "INTERPATITIONView.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CINTERPATITIONView

IMPLEMENT_DYNCREATE(CINTERPATITIONView, CFormView)

BEGIN_MESSAGE_MAP(CINTERPATITIONView, CFormView)
	//{{AFX_MSG_MAP(CINTERPATITIONView)
	ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
	ON_BN_CLICKED(IDC_BUTTON2, OnButton2)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CINTERPATITIONView construction/destruction

CINTERPATITIONView::CINTERPATITIONView()
	: CFormView(CINTERPATITIONView::IDD)
{
	//{{AFX_DATA_INIT(CINTERPATITIONView)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
	// TODO: add construction code here

}

CINTERPATITIONView::~CINTERPATITIONView()
{
}

void CINTERPATITIONView::DoDataExchange(CDataExchange* pDX)
{
	CFormView::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CINTERPATITIONView)
		// NOTE: the ClassWizard will add DDX and DDV calls here
	//}}AFX_DATA_MAP
}

BOOL CINTERPATITIONView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CFormView::PreCreateWindow(cs);
}

void CINTERPATITIONView::OnInitialUpdate()
{
	CFormView::OnInitialUpdate();
	GetParentFrame()->RecalcLayout();
	ResizeParentToFit();

}

/////////////////////////////////////////////////////////////////////////////
// CINTERPATITIONView diagnostics

#ifdef _DEBUG
void CINTERPATITIONView::AssertValid() const
{
	CFormView::AssertValid();
}

void CINTERPATITIONView::Dump(CDumpContext& dc) const
{
	CFormView::Dump(dc);
}

CINTERPATITIONDoc* CINTERPATITIONView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CINTERPATITIONDoc)));
	return (CINTERPATITIONDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CINTERPATITIONView message handlers

void CINTERPATITIONView::OnButton1() 
{
	// TODO: Add your control notification handler code here
	DoIt(1);
}

int CINTERPATITIONView::DoIt(int WkMode)
{
    int n=GetDlgItemInt(IDC_EDIT1);
    class IntPartSet * p;
    CListBox *         z=(CListBox *)GetDlgItem(IDC_LIST1);
    Element *          x;
    int                i;
    char               ss[4096];

    p=(WkMode==1) ? WXDIntegerPatition(n,n) : ShaoIntegerPatition(n,1);
    z->ResetContent();
    for (x=p->m_HeadElements;x!=0;x=x->m_Next)
    {
	sprintf(ss,"%d",x->m_Body[0]);
	for (i=1;i<x->m_Length;i++)
	{
	    sprintf(ss+strlen(ss),"+%d",x->m_Body[i]);
	}
	z->AddString(ss);
    }

    delete p;
    return 0;
}

Element::Element(int Length)
{
    m_Length=Length;
    m_Body=(int *)malloc(sizeof(m_Body[0])*Length);
    m_Next=0;
}

Element::~Element()
{
    free(m_Body);
}

IntPartSet::IntPartSet()
{
    m_Count=0;
    m_HeadElements=0;
}

IntPartSet::~IntPartSet()
{
    class Element * p;

    while (m_HeadElements)
    {
	p=m_HeadElements;
	m_HeadElements=m_HeadElements->m_Next;
	delete p;
    }
}

int IntPartSet::AddElement(class Element * p)
{
    p->m_Next=m_HeadElements;
    m_HeadElements=p;
    m_Count++;
    return 0;
}


//-----------------------------------------------------------------------------------
//	对 n 进行划分,其最小项不得小于 k
//	返回划分的集合
//-----------------------------------------------------------------------------------
class IntPartSet * CINTERPATITIONView::ShaoIntegerPatition(int n,int k)
{
    class IntPartSet * s;
    class IntPartSet * s1;
    class IntPartSet * s2;
    class Element    * q;
    class Element    * p;
    class Element    * z;
    int                m;

    s=new IntPartSet;
    if (n==1)					// 如果对 1 进行划分
    {
	q=new Element(1);			// 只有 1 个元素
	q->m_Body[0]=1;				// 它就是 1
	s->AddElement(q);			// 加入到集合中
	return s;				// 返回这个集合
    }

    q=new Element(1);				// 只有 1 个元素
    q->m_Body[0]=n;				// 它就是 1
    s->AddElement(q);				// 加入到集合中

    for (m=k;n-m>=m;m++)
    {
	s1=ShaoIntegerPatition(n-m,m);
	s2=ShaoIntegerPatition(m,k);
	for (p=s1->m_HeadElements;p!=0;p=p->m_Next)
	for (q=s2->m_HeadElements;q!=0;q=q->m_Next)
	{
	    z=new Element(p->m_Length+q->m_Length);
	    memcpy(z->m_Body,p->m_Body,p->m_Length*sizeof(int));
	    memcpy(z->m_Body+p->m_Length,q->m_Body,q->m_Length*sizeof(int));
	    s->AddElement(z);
	}
	delete s1;
	delete s2;
    }
    return s;
}

//-----------------------------------------------------------------------------------
//	对 n 进行划分,其首项不超过 m
//-----------------------------------------------------------------------------------
class IntPartSet * CINTERPATITIONView::WXDIntegerPatition(int n,int m)
{
    class IntPartSet * s=0;
    class IntPartSet * s1;
    class Element    * q;
    class Element    * z;
    int                i;

    if (m>n) m=n;
    if (m==1)					// 项首项不能超过 1,则只能由 1+1+1.....+1 组成
    {
	s=new IntPartSet;
	q=new Element(n);			// 有 n 个分量
	for (i=0;i<n;i++)
	{
	    q->m_Body[i]=1;			// 它就是 1
	}
	s->AddElement(q);			// 加入到集合中
	return s;				// 返回这个集合
    }
    if (n==m)					// 如果对 n 整体分解
    {
	s=WXDIntegerPatition(n,n-1);		// 先把 n 按首项不超过 n-1 分解
	q=new Element(1);			// 有 1 个分量
	q->m_Body[0]=n;				// 它就是 n
	s->AddElement(q);			// 加入到集合中
	return s;
    }

    s=WXDIntegerPatition(n,m-1);		// 先把 n 按首项不超过 m-1 分解
    s1=WXDIntegerPatition(n-m,m);		// 再把 n-m 按首项不超过 m 分解,这个集合每一个元素前要加上 <m>,因为 m 是所有这些元素的首项
    for (q=s1->m_HeadElements;q!=0;q=q->m_Next)
    {
	z=new Element(q->m_Length+1);
	z->m_Body[0]=m;
	memcpy(&z->m_Body[1],q->m_Body,q->m_Length*sizeof(int));
	s->AddElement(z);
    }
    delete s1;
    return s;
}

void CINTERPATITIONView::OnButton2() 
{
	// TODO: Add your control notification handler code here
	DoIt(2);
}