xreducetestdlg.cpp

一个有趣的卡诺图划简程序。学生可自己填充卡诺图

// XReduceTestDlg.cpp : 实现文件
//

#include "stdafx.h"
#include "reduce.h"
#include "XReduceTestDlg.h"
#include <math.h>



// XReduceTestDlg 对话框

IMPLEMENT_DYNAMIC(XReduceTestDlg, CDialog)
XReduceTestDlg::XReduceTestDlg(CWnd* pParent /*=NULL*/)
	: CDialog(XReduceTestDlg::IDD, pParent)
	, intValNum(0)
	, bHaveIgnoreItem(FALSE)
	, intProcessState(0)
	, csReduceResult(_T(""))
{
}

XReduceTestDlg::~XReduceTestDlg()
{
}

void XReduceTestDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	DDX_Check(pDX, IDC_IGNORE, bHaveIgnoreItem);
	DDV_MaxChars(pDX, csReduceResult, 255);
}


BEGIN_MESSAGE_MAP(XReduceTestDlg, CDialog)
	ON_BN_CLICKED(IDC_BUTTON1, OnBnClickedButton1)
	ON_WM_PAINT()
	ON_WM_LBUTTONDOWN()
	ON_WM_RBUTTONDOWN()
	ON_WM_KEYDOWN()
	ON_WM_KEYUP()
	ON_BN_CLICKED(IDC_BUTTON4, OnBnClickedButton4)
	ON_BN_CLICKED(IDC_BUTTON5, OnBnClickedButton5)
	ON_BN_CLICKED(IDC_BUTTON6, OnBnClickedButton6)
	ON_BN_CLICKED(IDC_BUTTON7, OnBnClickedButton7)
	ON_WM_TIMER()
	ON_BN_CLICKED(IDC_BUTTON8, OnBnClickedButton8)
	ON_BN_CLICKED(IDC_BUTTON11, OnBnClickedButton11)
	ON_BN_CLICKED(IDC_BUTTON12, OnBnClickedButton12)
	ON_BN_CLICKED(IDC_BUTTON9, OnBnClickedButton9)
	ON_BN_CLICKED(IDC_BUTTON13, OnBnClickedButton13)
END_MESSAGE_MAP()


// XReduceTestDlg 消息处理程序

BOOL XReduceTestDlg::OnInitDialog(void)
{
	BOOL ret = CDialog::OnInitDialog();
	if(!ret) return ret;

	//内存分配
	tabAutoReducing = new XTabDataManager[1000];
	if( tabAutoReducing == NULL ){
		AfxMessageBox( "内存不足，本能运行本程序！!" );
		this->EndDialog( 0 );
		return FALSE;
	}

	//初始化设置
	intValNum = 4;//
	bHaveIgnoreItem = false;//没有无关项
	this->CheckRadioButton( IDC_RADIO3,IDC_RADIO5,IDC_RADIO4 ); 
	UpdateData( FALSE );

	CWnd * pwnd = this->GetDlgItem( IDC_DRAWRECT );
	CPoint   pt(30, 20);
	pwnd->GetClientRect( &rectDrawArea ); 
	rectDrawArea += pt;

	intProcessState = 0;//0-正在设置
	timer_on = false;
	OnBnClickedButton1();

	root.par = &root;

	return FALSE;
}

void XReduceTestDlg::OnBnClickedButton1()
{
	if( timer_on ) return;
	int id = this->GetCheckedRadioButton(  IDC_RADIO3,IDC_RADIO5 );

	switch(id){
		case IDC_RADIO3: intValNum = 3; break;
		case IDC_RADIO5: intValNum = 5; break;
		case IDC_RADIO4: intValNum = 4; 
	}


	UpdateData( TRUE );
	intProcessState = 1;//正在填充卡诺图

	for( int i = 0; i < 16; i++ )
		intTabValue[i] = 0;

	//重新绘制卡诺图框
	this->InvalidateRect( NULL ); 
}

//根据变量个数画框
void XReduceTestDlg::DrawBlockTitle( CDC *dc )
{
	CRect rectBlock = rectDrawArea;
	CPoint pt1,pt2;
				
	rectBlock.DeflateRect( 40,40,0,0 );

	dc->DrawEdge( &rectDrawArea ,BDR_RAISEDINNER | BDR_RAISEDOUTER,BF_RECT  );
	dc->DrawEdge( &rectBlock ,BDR_SUNKENINNER | BDR_SUNKENOUTER,BF_RECT  );
	pt1 = rectBlock.TopLeft(); 
	pt2 = rectDrawArea.TopLeft(); pt2.x += 2; pt2.y += 2 ;
	dc->MoveTo( pt2 );	dc->LineTo( pt1 );

	//写字
	CString xitem[2] = { "BC","CD" };
	CString yitem[2] = { "A","AB" };
	CString xtitle[4] ={ "00","01","11","10" } ;
	CString ytitle[2][4] ={ {"0","1"},{"00","01","11","10"} };
	CRect rectTitle;


	//竖立格
	pt1 = rectBlock.TopLeft(); 
	pt2.x = rectBlock.left ; pt2.y = rectBlock.bottom ;
	int dw = rectBlock.Width() / 4;
	//CString xitem[2] = { "BC","CD" };
	//CString yitem[2] = { "A","AB" };

	dc->SetTextColor( RGB(0,0,255) );
	dc->TextOut( pt1.x, pt1.y-30, xitem[intValNum-3] );
	for( int i = 0; i < 4; i++ ){
		rectTitle.left = pt1.x;
		rectTitle.right = pt1.x + dw;
		rectTitle.top = pt1.y - 20;
		rectTitle.bottom = pt1.y;
		dc->DrawText( xtitle[i], &rectTitle, DT_CENTER|DT_VCENTER );
		dc->MoveTo( pt1 ); dc->LineTo( pt2 );
		pt1.x += dw; pt2.x += dw;
	}
	//横格 	intValNum = 4;
	int lnum = (intValNum - 2)*2;
	pt1 = rectBlock.TopLeft(); 
	pt2.x = rectBlock.right ; pt2.y = rectBlock.top ;
	int dh = rectBlock.Height() / lnum;

	dc->TextOut( pt1.x-30, pt1.y, yitem[intValNum-3] );
	for( int i = 0; i < lnum; i++ ){
		rectTitle.left = pt1.x - 20;
		rectTitle.right = pt1.x;
		rectTitle.top = pt1.y;
		rectTitle.bottom = pt1.y + dh;
		dc->DrawText( ytitle[intValNum-3][i], &rectTitle, DT_CENTER|DT_VCENTER|DT_SINGLELINE  );

		dc->MoveTo( pt1 ); dc->LineTo( pt2 );
		pt1.y += dh; pt2.y += dh;
	}
	//在表格中填固定显示值
	int tabVal[][4] = { {0,1,3,2},{4,5,7,6},{12,13,15,14},{8,9,11,10} };
	CString str;
	CPoint pt3,pt4;

	dc->SetBkMode( TRANSPARENT );
	pt1 = rectBlock.TopLeft(); pt1.x += 5; pt1.y += 5; 
	for( int i = 0; i < 4; i++ ){
        pt3.x = pt1.x + i*dw;
		for( int j = 0; j < lnum; j++ ){
			pt3.y = pt1.y + j*dh;
			pt4 = pt3; pt4.x++; pt4.y++; 
			str.Format( _T("%d"),tabVal[j][i] ); 
			dc->SetTextColor( RGB(255,255,255) );
			dc->TextOut( pt4.x,pt4.y,str );
			dc->SetTextColor( RGB(132,130,132) );
			dc->TextOut( pt3.x,pt3.y,str );
		}
	}


	//写字
	//CString xtitle[] ={ "00","01","11","10" } ;
	//CString ytitle[] ={ {"00","01","11","10"},{"0","1"} };
	//CRect rectTitle = rectBlock;
	//CBrush b( RGB(255,255,255) );

	//dc->SetBkMode( TRANSPARENT );

	//rectTitle.right -= 2;
	//rectTitle.bottom = rectBlock.top;
	//rectTitle.top = rectBlock.top - 18;
	//dc->SetTextColor( RGB(0,128,255) );
	//dc->FillRect( &rectTitle , &b ); 
	//dc->DrawText( xtitle,&rectTitle,DT_SINGLELINE|DT_BOTTOM );

	//rectTitle = rectBlock;
	//rectTitle.bottom -= 2;
	//rectTitle.right = rectBlock.left;
	//rectTitle.left = rectBlock.left - 18;
	//dc->FillRect( &rectTitle , &b ); 
	//dc->DrawText( ytitle[4-intValNum],&rectTitle,DT_WORDBREAK|DT_RIGHT );

}

void XReduceTestDlg::OnPaint(void)
{
	CPaintDC dc(this);

	DrawBlockTitle( &dc );
	DrawTabData( &dc );
	if( (intProcessState == 2) || (intProcessState == 3)  )
		DrawSelfReduingTab( &dc );
	else if( (intProcessState == 4) || (intProcessState == 5) || (intProcessState == 10) )
		DrawSelfReduingProcess( &dc );


}

// 显示表格中的数值
void XReduceTestDlg::DrawTabData( CDC *dc )
{
	//若变量还未确定,则不显示具体数值,此时显示没有意义
	if( intProcessState <= 0 ) return;

	CRect rectBlock = rectDrawArea;
	CPoint pt1,pt3;
				
	rectBlock.DeflateRect( 40,40,0,0 );

	int dw = rectBlock.Width() / 4;
	int lnum = (intValNum - 2)*2;
	int dh = rectBlock.Height() / lnum;
	CString val[3] = { "0","1","X" };
	int tabVal[][4] = { {0,1,3,2},{4,5,7,6},{12,13,15,14},{8,9,11,10} };

	dc->SetBkMode( TRANSPARENT );
	pt1 = rectBlock.TopLeft(); pt1.x += (dw/2-3); pt1.y += (dh/2-3); 
	for( int i = 0; i < 4; i++ ){
        pt3.x = pt1.x + i*dw;
		for( int j = 0; j < lnum; j++ ){
			pt3.y = pt1.y + j*dh;
			switch( intTabValue[ tabVal[j][i] ] ){
				case 0: dc->SetTextColor( RGB(132,130,132) ); break;
				case 1: dc->SetTextColor( RGB(0,0,255) ); break;
				case 2: dc->SetTextColor( RGB(0,255,255) ); break;
			}
			dc->TextOut( pt3.x,pt3.y,val[ intTabValue[ tabVal[j][i] ] ] );
		}
	}

}

//在化简时，结束本次化简
void XReduceTestDlg::OnRButtonDown( UINT ,CPoint  )
{
	if( 2 != intProcessState ) return;

	tabSelfReducing.FinishThisLine(); 
	InvalidateRect( NULL );
}

void XReduceTestDlg::OnLButtonDown( UINT nFlags,CPoint point )
{
	CRect blk;
	int order;

	if( intProcessState <= 0 ) return;
	//正在添表时
	else if( 1 == intProcessState ){
		//检测鼠标位置
		order = PointInWhichTab( point,blk );
		//落在区域内
		if( -1 == order ) return;
		//改变该值
		ChangeTabVal( order );
		//刷新显示该区域
		InvalidateRect( &blk );
		
	}
	else if( 2 == intProcessState ){
		order = PointInWhichTab( point,blk );
		//落在区域内
		if( -1 == order ) return;
		if( 0 == intTabValue[order] ){
			MessageBox( "该项不能选择!" );
			return;
		}
		//加入当前化简队列
		tabSelfReducing.ChangeThisLine( order ); 
		//刷新显示该区域
		InvalidateRect( &blk );
		//InvalidateRect( NULL );
	}

}

// 检测鼠标的位置
int XReduceTestDlg::PointInWhichTab( CPoint poi , CRect & rect )
{
	CRect rectBlock = rectDrawArea;
	rectBlock.DeflateRect( 40,40,0,0 );

	int dw = rectBlock.Width() / 4;
	int lnum = (intValNum - 2)*2;
	int dh = rectBlock.Height() / lnum;
	int tabVal[][4] = { {0,1,3,2},{4,5,7,6},{12,13,15,14},{8,9,11,10} };

	CRect tabBlock0, tabBlock;
	CPoint   pt;
	tabBlock0 = rectBlock;
	tabBlock0.right = tabBlock0.left + dw;
	tabBlock0.bottom = tabBlock0.top + dh;
	for( int i = 0; i < 4; i++ ){
		for( int j = 0; j < lnum; j++ ){
			tabBlock = tabBlock0;
			pt.x = dw*i; pt.y = dh*j;
			tabBlock += pt;
			if( tabBlock.PtInRect(poi) ){ 
				rect = tabBlock;
				return tabVal[j][i];
			}
		}
	}

	return -1;
}

void XReduceTestDlg::ChangeTabVal( int order )
{
	if( order<0 || order>=16 ) return;

	intTabValue[order]++;
	if( bHaveIgnoreItem ){
		if( intTabValue[order] > 2 )
			intTabValue[order] = 0;
	}
	else{
		if( intTabValue[order] > 1 )
			intTabValue[order] = 0;
	}
}

//表格中值确定,开始化简
void XReduceTestDlg::OnBnClickedButton4()
{
	//检查有无"1"
	if( timer_on ) return;

	bool haveOne = false;
	bool num = 0;
		for( int i = 0;( (i < 16) && (4 == intValNum) )|| ( (i < 8) && (3 == intValNum ) );i++ ){
		if( 1 == intTabValue[i] ){
			haveOne = true;
			break;
		}
	}
	if( !haveOne ){
		MessageBox( "没有最小项,请重新填写卡诺图!" );
		return;
	}
	for( int i = 0;( (i < 16) && (4 == intValNum) )|| ( (i < 8) && (3 == intValNum ) );i++ ){
		if( 0 == intTabValue[i] )
			num++;
	}
	if( num == 0 ){
		MessageBox( "Very easy,结果是1！" );
		return;
	}
	Invalidate();
	intProcessState = 2;

	tabSelfReducing.Init(); 
	tabSelfReducing.intVarNum = intValNum;
	//卡诺图确定后，立即自动产生正确答案
	AutoReduce();
}

void XReduceTestDlg::AutoReduce()
{
	//初始化
	root.son = NULL;
	//tabAutoReducing = NULL;
	autonum = 0;
	cur_autonum = 0;
	intArrayNum = 0;
	//读出所有最小项
	for( int i = 0; i < 16; i++ ){
		if( intTabValue[i] == 1 )
			intArrayValue[ i ] = true;
		else
			intArrayValue[ i ] = false;
	}
	for( int i = 0; i <= 999; i++ ){
		tabAutoReducing[i].Init();
		tabAutoReducing[i].intVarNum = intValNum;
		tabAutoReducing[i].auto_self = true;
	}
	use_num = 0;
		
	int pos = 0;
	int maskbit[4][7] = { {14,13,11,7},{12,10,9,6,5,3},{8,4,2,1},{0} };
	//可化简的项数          3                2             1        
	int mask_num[] = { 4,6,4,1 };//3项化简：共有四种屏蔽码
	int mask_itemnum[] = { 8,4,2,1 };
	int m_num = intValNum == 3 ? 1 : 0;//与变量数有关,8
	int m_idx = m_num;
	int j;
	int high_ok = false;//尽量更多项化简
	treeAutoReduce * par_node = &root;
	treeAutoReduce * cur_node = NULL , * bef_node = NULL;

	while( !intArrayValue[pos] ) pos++;
	if( pos >= 16 ) return;
	
	HCURSOR CUR = ::LoadCursor( NULL,IDC_WAIT );
	HCURSOR oldcur = SetCursor( CUR );

	//取intArrayValue第一项值
	for( m_idx = m_num; m_idx <= 3; m_idx++ ){//8项，4项，2项
		for( j = 0; j < mask_num[m_idx]; j++ ){//使用那一个MASK 
    			if( CanReduce( pos,maskbit[m_idx][j],mask_itemnum[m_idx] ) ){
				if( high_ok ){//说明同一级存在多种化简方法
					bef_node = cur_node;
					cur_node = new treeAutoReduce;
					use_num++;
					bef_node->next = cur_node;
					cur_node->before = bef_node;
					cur_node->par = par_node;
					cur_node->son = NULL;
					cur_node->next = NULL;
					cur_node->value = pos;
					cur_node->maskbit = maskbit[m_idx][j];
					cur_node->num = mask_itemnum[m_idx];
				}
				else{
					high_ok = true;
					cur_node = new treeAutoReduce;
					use_num++;
					par_node->son = cur_node;
					cur_node->par = par_node;
					cur_node->before = NULL;
					cur_node->son = NULL;
					cur_node->next = NULL;
					cur_node->value = pos;
					cur_node->maskbit = maskbit[m_idx][j];