raceprojectview.cpp

这是一个算法分析的经典问题

// RaceProjectView.cpp : implementation of the CRaceProjectView class
//

#include "stdafx.h"
#include "RaceProject.h"

#include "RaceProjectDoc.h"
#include "RaceProjectView.h"

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

/////////////////////////////////////////////////////////////////////////////
// CRaceProjectView

IMPLEMENT_DYNCREATE(CRaceProjectView, CFormView)

BEGIN_MESSAGE_MAP(CRaceProjectView, CFormView)
	//{{AFX_MSG_MAP(CRaceProjectView)
	ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CRaceProjectView construction/destruction

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

}

CRaceProjectView::~CRaceProjectView()
{
}

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

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

	return CFormView::PreCreateWindow(cs);
}

void CRaceProjectView::OnInitialUpdate()
{
	CFormView::OnInitialUpdate();
	GetParentFrame()->RecalcLayout();
	ResizeParentToFit();
	memset(m_Table,0,sizeof(m_Table));
}

/////////////////////////////////////////////////////////////////////////////
// CRaceProjectView diagnostics

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CRaceProjectView message handlers

void CRaceProjectView::OnButton1() 
{
	// TODO: Add your control notification handler code here
	int n=GetDlgItemInt(IDC_EDIT1);
	int i;
	int * p;

	p=(int *)malloc((n+2)*(n+2)*sizeof(int));
	for (i=1;i<=n+1;i++)
	{
	    m_Table[i]=p;
	    p=&p[n+1];
	}
	Doit(n);
//	WXDBook(n);
	ShowIt(n);
	free(m_Table[1]);
	memset(m_Table,0,sizeof(m_Table));
}

int CRaceProjectView::WXDBook(int n)
{
    int j,k,m;

    m_Table[1][1]=1;	// 先形成 1 x 1 矩阵
    for (j=1;j<n;j+=j)   // 由 j x j 生成 2j x 2j 的比赛表
    {
         for (k=1;k<=j;k++)
         for (m=1;m<=j;m++)
	 {
	    m_Table[k+j][m]=m_Table[k][m]+j;
	    m_Table[k][m+j]=m_Table[k+j][m];
	    m_Table[k+j][m+j]=m_Table[k][m];
	 }

    }
    return 0;
}

int CRaceProjectView::ShowIt(int n)
{
    CListBox * p=(CListBox *)GetDlgItem(IDC_LIST1);
    int        i,j;
    char       ss[4096];

    if (n& 1) n++;
    p->ResetContent();
    for (i=1;i<=n;i++)
    {
	ss[0]=0;
	for (j=1;j<=n;j++)
	{
	    sprintf(ss+strlen(ss),"%3d ",m_Table[i][j]);
	}
	p->AddString(ss);
    }
    return 0;
}

int CRaceProjectView::NormalCopy(int n)
{
    int m=n/2;
    int i,j;

    for (i=1;i<=m;i++)
    for (j=1;j<=m;j++)
    {
	m_Table[i][j+m]=m_Table[i][j]+m;	// 把左上角抄到右上角
	m_Table[i+m][j]=m_Table[i][j+m];	// 把右上角抄到左下角
	m_Table[i+m][j+m]=m_Table[i][j];	// 把左上角抄到右下角
    }
    return 0;
}

int CRaceProjectView::PackCopy(int n)
{
    int m=n/2;
    int i,j,k;

    for (i=1;i<=m;i++)
    {
	for (j=1;j<=m+1;j++)			// 因为 m 是奇数，所以生成的日程表有 m+1 列
	{
	    if (m_Table[i][j]>m)		// 如果轮空
	    {
		m_Table[i][j]=m+i;		// 当日，i 与 m+i 比赛
		m_Table[m+i][j]=i;
	    }
	    else				// 如果没有轮空
	    {
		m_Table[m+i][j]=m_Table[i][j]+m;// 就抄到下方
	    }
	}
	for (j=2;j<=m;j++)			// 处理右侧的 m-1 列,因为已经填了 m+1 列
	{
	    k=i+j-1;				// 要保证不与填入轮空的选手(m+i) 重复，所以，从 m+i+1 开始取号
	    if (k>m) k-=m;
	    k+=m;				// 右侧的号码要加上 m
	    m_Table[i][m+j]=k;			// 填入比赛选手对
	    m_Table[k][m+j]=i;
	}
    }
    return 0;
}

int CRaceProjectView::Doit(int n)
{
    int m;

    if (n==1)					// 如果只有一个选手
    {
	m_Table[1][1]=1;
	return 0;
    }
    if (n & 1) n++;				// n若为奇数，就变成偶数
    Doit(m=n/2);				// 生成 n/2 人数的日程表
    if (m>1 && (m & 1)!=0)			// 若 n/2 为奇数
    {
	return PackCopy(n);
    }
    return NormalCopy(n);
}