longestseqview.cpp

该程序为算法分析中的一个经典问题

// LongestSeqView.cpp : implementation of the CLongestSeqView class
//

#include "stdafx.h"
#include "LongestSeq.h"

#include "LongestSeqDoc.h"
#include "LongestSeqView.h"

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

/////////////////////////////////////////////////////////////////////////////
// CLongestSeqView

IMPLEMENT_DYNCREATE(CLongestSeqView, CFormView)

BEGIN_MESSAGE_MAP(CLongestSeqView, CFormView)
	//{{AFX_MSG_MAP(CLongestSeqView)
	ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CFormView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CFormView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CFormView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CLongestSeqView construction/destruction

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

}

CLongestSeqView::~CLongestSeqView()
{
}

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

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

	return CFormView::PreCreateWindow(cs);
}

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

}

/////////////////////////////////////////////////////////////////////////////
// CLongestSeqView printing

BOOL CLongestSeqView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CLongestSeqView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CLongestSeqView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

void CLongestSeqView::OnPrint(CDC* pDC, CPrintInfo* /*pInfo*/)
{
	// TODO: add customized printing code here
}

/////////////////////////////////////////////////////////////////////////////
// CLongestSeqView diagnostics

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CLongestSeqView message handlers
int CLongestSeqView::GetIntArray(int a[],char * s)
{
    int i,j,State;
    BYTE c;

    j=0;
    State=0;
    for (i=0;c=s[i];i++)
    if (State==0)				// 如果等待数字
    {
	if (isdigit(c))
	{
	    a[j]=c-'0';
	    State=1;				// 等待分隔符
	}
    }
    else					// 如果等待分隔符
    {
	if (isdigit(c))				// 如果仍然是数字,就归为正在收的单元里
	{
	    a[j]=a[j]*10+(c-'0');
	}
	else					// 如果是分隔符
	{
	    j++;				// 收到的个数加1
	    State=0;				// 状态回到 0,即等待数字
	}
    }
    return (State==0) ? j : j+1;		// 返回收到的数字个数
}

int CLongestSeqView::ConstructSeq(int a[],int c[],int Pos,char * z)
{
    if (Pos==0) return 0;
    ConstructSeq(a,c,c[Pos],z);
    sprintf(z+strlen(z),"[a(%d)=%d]",Pos,a[Pos]);
    return 0;
}

int CLongestSeqView::DoIt(int a[],int n)
{
    int b[256];
    int c[256];
    int i,j;
    char z[1024];

    b[1]=1;
    c[1]=0;
    for (i=2;i<=n;i++)
    {
	b[i]=1;
	c[i]=0;
	for (j=1;j<i;j++)
	if (a[j]<a[i])
	if (b[j]+1>b[i])
	{
	    b[i]=b[j]+1;
	    c[i]=j;
	}
    }
    j=1;
    for (i=2;i<=n;i++)
    if (b[i]>b[j]) j=i;

    z[0]=0;
    ConstructSeq(a,c,j,z);
    SetDlgItemText(IDC_EDIT2,z);
    return 0;
}

int CLongestSeqView::FindMin(int a[],int n)
{
    int x=a[0];
    int i;
    for (i=1;i<n;i++)
    {
	if (a[i]<x) x=a[i];
    }
    return x;
}

int CLongestSeqView::OnlyLength(int a[],int n)
{
     int Left,Right,Middle,i,MaxLen=1;
     int b[256];

     b[1]=a[0];//FindMin(a,n)-1;
     for(i=1;i<n;i++)
     {
         if(a[i]>b[MaxLen])
	 {
            MaxLen++;
            b[MaxLen]=a[i];
         }
         else
	 {
             Left=1;
	     Right=MaxLen;
             while(Left<=Right)
	     {
                Middle=(Left+Right)/2;
		if(a[i]>b[Middle]) Left=Middle+1;
		else Right=Middle-1;
             }
             b[Left]=a[i];
         }
     }
     return MaxLen;
}

void CLongestSeqView::OnButton1() 
{
	// TODO: Add your control notification handler code here
	char s[256];
	int  a[256];
	int  n,m;

	GetDlgItemText(IDC_EDIT1,s,sizeof(s));
	n=GetIntArray(&a[1],s);
	DoIt(a,n);
	m=OnlyLength(&a[1],n);

}