xreducetestdlg.h

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

#pragma once
#include "atltypes.h"
#include "afxtempl.h"

//存储化简步骤
class XTabDataManager
{
public:	
	int ItemsProcessing[17][17];//{ {1，2，3，-1}，{4，2} }；

	int intCurIndex;//表示目前正在进行第几次化简
	int intCurItemNum;//目前使用的
	int ItemNumber;

	int intVarNum;
	bool auto_self;

	//两种化简方法是否完全一致
	bool operator ==( XTabDataManager t )
	{
		//判断
		if( this->intCurIndex != t.intCurIndex )
			return false;
		bool ItemsOccur[17];
		bool ItemsOccur_t[17];
		int equal_num = 0;

		for( int i = 0; i < intCurIndex ; i++ ){//扫描自己每一行
			for( int j = 0; j < 17 ; j++ )
				ItemsOccur[j] = false;
			for( int j = 0; j < 17 ; j++ ){
				if( ItemsProcessing[i][j] != -1 )
					ItemsOccur[ ItemsProcessing[i][j] ] = true;
			}
			for( int ii = 0; ii < intCurIndex ; ii++ ){//扫描对方每一行
				for( int j = 0; j < 17 ; j++ )
					ItemsOccur_t[j] = false;
				for( int j = 0; j < 17 ; j++ ){
					if( t.ItemsProcessing[ii][j] != -1 )
						ItemsOccur_t[ t.ItemsProcessing[ii][j] ] = true;
				}
				//两者比较
				for( int j = 0; j < 17 ; j++ )
					if( ItemsOccur_t[j] != ItemsOccur[j] )								
						break;
				//找到完全一致行
				if( j >= 17){
					equal_num++;
					break;
				}
			}
		}

		return equal_num == intCurIndex;
	}

	void operator = ( XTabDataManager t )
	{
		for( int i = 0; i < 17; i++ )
			for( int j = 0; j < 17; j++ )
				ItemsProcessing[i][j] = t.ItemsProcessing[i][j];
		intCurIndex = t.intCurIndex ;
		intCurItemNum = t.intCurItemNum ;
		ItemNumber = t.ItemNumber ;
		intVarNum = t.intVarNum ;
		auto_self = t.auto_self;
	}
public:
	XTabDataManager(){
		Init();
	}

	//自动化简
	void Normalize()
	{
		int temp[17];

		for( int j = 0; j < intCurIndex/2; j++ ){
			for( int i = 0; i < 17; i++ )
				temp[i] = ItemsProcessing[j][i];
			for( int i = 0; i < 17; i++ )
				ItemsProcessing[j][i] = ItemsProcessing[intCurIndex-j-1][i];
			for( int i = 0; i < 17; i++ )
				ItemsProcessing[intCurIndex-j-1][i] = temp[i];
		}
	}

	void Init(){
		for( int i = 0; i < 17; i++ )
			for( int j = 0; j < 17; j++ )
				ItemsProcessing[i][j] = -1;
		intCurIndex = 0;intCurItemNum = 0;
		ItemNumber = 0;
		auto_self = false;
	}

	void AddOneLine( int val, int mask, int num ){//直接加入一行
		int mask_numl[] = { 0,0x1,0x3,0x7 };
		int mask_numh[] = { 15,12,8,0 };

		//检查相关项是否也是最小项或无关项
		int order;
		int t1,t2,t3;
		for( int i = 0; i < num ; i++ ){
			order = i;
			for( int j = 0; j < intVarNum ; j++ ){
				if( !( (mask>>j) & 0x1) ){//如果碰到屏蔽位是 0  
					t1 = order & mask_numl[j];//低位
					t2 = val & (0x1<<j) ;//插入位
					t3 = (order<<1) & mask_numh[j];//保留高位
					order = t1 | t2 | t3;
				}
			}
			//加入
			ChangeThisLine( order );
		}
		FinishThisLine();
	}

	void ChangeThisLine( int which ){//向一行中增加或移去一项

		bool exist = false;
		//该值是否已在队列中?
		for( int i = 0;i < intCurItemNum; i++ ){
			if( ItemsProcessing[intCurIndex][i] == which ){
				exist = true;
				break;
			}
		}
		if( exist ){
			//若已经存在,则删除
			ItemsProcessing[intCurIndex][i] = ItemsProcessing[intCurIndex][intCurItemNum-1];
			ItemsProcessing[intCurIndex][intCurItemNum-1] = -1;
			intCurItemNum--;
		}
		else{
			ItemsProcessing[intCurIndex][intCurItemNum] = which;
			intCurItemNum++;
		}

	}

	int Check1Countrt( int data )
	{
		int c = 0;

		for( int i = 0; i < intVarNum; i++ ){
			if( (data&0x1) ) c++;
			data >>= 1;
		}

		return c;
	}

	bool CheckNeighbor( int * data, int count )
	{
		int d[16],c;
		int bitnum;

		if( 1 == count ) return true;
		else if( 2 == count ) bitnum = 1;
		else if( 4 == count ) bitnum = 2;
		else if( 8 == count ) bitnum = 3;
		else if( 16 == count ) bitnum = 4;
		else return false;

		for( int i = 1 ; i < count; i++ )
			d[i-1] = ( (~data[i])&(~data[0]) )| ( data[i]&data[0] );
		c = d[0]; 
		for( int i = 1 ; i < count-1; i++ )
			c &= d[i]; 

		c = Check1Countrt( c );
		if( c >= intVarNum - bitnum ) return true;

		return false;
	}

	//检查最新化简步骤.是否包含在别的化简步骤
	bool CheckIncluded()
	{
		bool exist;
		bool include;
		for( int i = 0; i < intCurIndex; i++ ){//查询每个化简步骤
			int j = 0;
			include = true;
			while( -1 != ItemsProcessing[intCurIndex][j] ){
				exist = false;
				int k = 0;
				while( -1 != ItemsProcessing[i][k] ){
					if( ItemsProcessing[i][k] == ItemsProcessing[intCurIndex][j] ){
						exist = true;//找到对应项
						break;
					}
					k++;
				}
				if( !exist ){
					include = false;//若有找不到的项，说明不包含
					break;
				}
				j++;
			}
			if( exist ) return true;
		}
		return false;
	}
	
	//检查最新化简步骤.是否包含在别的化简步骤
	bool CheckIncluding()
	{
		bool exist;
		bool include;
		bool ret = false;
		for( int i = 0; i < intCurIndex; i++ ){//查询每个化简步骤
			int j = 0;
			include = true;
			while( -1 != ItemsProcessing[i][j] ){
				exist = false;
				int k = 0;
				while( -1 != ItemsProcessing[intCurIndex][k] ){
					if( ItemsProcessing[intCurIndex][k] == ItemsProcessing[i][j] ){
						exist = true;//找到对应项
						break;
					}
					k++;
				}
				if( !exist ){
					include = false;//若有找不到的项，说明不包含
					break;
				}
				j++;
			}
			if( exist ){
				//删除以前化简步骤，保证化简顺序不变
				j = i;
				for( ; j < intCurIndex; j++ ){
					for( int ii = 0; ii < 17; ii++ )
						ItemsProcessing[j][ii] = ItemsProcessing[j+1][ii];
				}
				for( int ii = 0; ii < 17; ii++ )
					ItemsProcessing[intCurIndex][ii] = -1;
				intCurIndex--;
				ret = true;
				i--;
			}
		}
		return ret;
	}

	void FinishThisLine(){
		//判断是否能构成相临项
		if( 0 == intCurItemNum ) return;
		if( ( 1 == intCurItemNum ) || (2 == intCurItemNum) || (4 == intCurItemNum) || (8 == intCurItemNum) || (16 == intCurItemNum));
		else{
			AfxMessageBox( "只有2的n次方个相临项才能合并!" );
			return;
		}

		if( !CheckNeighbor( ItemsProcessing[intCurIndex], intCurItemNum ) ){
			AfxMessageBox( "无法合并!\n规则提示：只有相临项才能合并！" );
			return;
		}

		//检查是否包含在别的项中
		if( CheckIncluded() ){
			if( !auto_self )
				AfxMessageBox( "已经包含在以前的化简过程中!" );
			//清除本次化简数据
			for( int i = 0; i < 17; i++ )
				ItemsProcessing[intCurIndex][i] = -1;
			intCurItemNum = 0;
			return;
		}
		if( CheckIncluding() ){
			if( !auto_self )
				AfxMessageBox( "包含以前的化简过程!\n以前的化简过程将被自动删除！" );
		}

		intCurIndex++;
		intCurItemNum = 0;//新的一行
	}

	//根据用户化简步骤，分析化简的合理性
	void AnalsysThisLineRes( int lidx ,int count, int & c)
	{
		//从本行中找到一个以前化简中没有出现的一项，look around about it
		//
	}

	//得到一行化简结果:结果存放在RES中,其中的 1 表示该项必须保留
	//DATA:
	void GetThisLineRes( int lidx ,int count, int & c)
	{
		int d[16];

		if( 1 == count ){
			c = 0xff;
			return;
		}
		for( int i = 1 ; i < count; i++ )
			d[i-1] = ( (~ItemsProcessing[lidx][i])&(~ItemsProcessing[lidx][0]) )| 
					 ( ItemsProcessing[lidx][i]&ItemsProcessing[lidx][0] );
		c = d[0]; 
		for( int i = 1 ; i < count-1; i++ )
			c &= d[i]; 
	}

	bool GetThisLine( int lidx, int * data, int & count ){
		if( lidx > intCurIndex ) return false;
		//data = ItemsProcessing[lidx];
		count = 0;
		for( int i = 0;i < 17; i++ ){
			if( ItemsProcessing[lidx][i] != -1 )
				count++;
			else break;
			data[i] = ItemsProcessing[lidx][i];
		}
	}

	//检查是否已将所有的项都包含
	bool CheckAll( int * data )
	{
		bool exist[17];
		int i,j;
		int total = intVarNum == 3 ? 8 : 16;

		for( i = 0; i < 17; i++ )
			exist[i] = false;
		for( i = 0; i < intCurIndex; i++ ){
			j = 0;
			while( -1 != ItemsProcessing[i][j] ){
				exist[ ItemsProcessing[i][j] ] = true;
				j++;
			}
		}
		for( i = 0; i < 16; i++ ){
			if( 1 == data[i] ){
				if( !exist[i] ) return false;
			}
		}

		return true;
	}


};

struct treeAutoReduce
{
	treeAutoReduce * before;
	treeAutoReduce * next;
	treeAutoReduce * son;
	treeAutoReduce * par;
	int value;
	int maskbit;
	int num;
};
// XReduceTestDlg 对话框

class XReduceTestDlg : public CDialog
{
	DECLARE_DYNAMIC(XReduceTestDlg)

public:
	XReduceTestDlg(CWnd* pParent = NULL);   // 标准构造函数
	virtual ~XReduceTestDlg();

// 对话框数据
	enum { IDD = IDD_PRACTICE };

protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV 支持

	DECLARE_MESSAGE_MAP()
public:
	BOOL OnInitDialog(void);
private:
	// 变量个数
	int intValNum;
	// 是否允许输入无关项
	BOOL bHaveIgnoreItem;
public:
	afx_msg void OnBnClickedButton1();
	afx_msg void OnLButtonDown( UINT, CPoint );
	afx_msg void OnRButtonDown( UINT, CPoint );
	afx_msg void OnPaint();
	afx_msg void OnKeyDown( UINT, UINT, UINT );
	afx_msg void OnKeyUp( UINT, UINT, UINT );
	afx_msg void OnTimer( UINT ); 
protected:
	void DrawBlockTitle( CDC * );
public:
	// 绘图区域
	CRect rectDrawArea;
	// 目前处理状态：设置、添表、化简、检查、自动演示
	int intProcessState;
	int old_state;
	// 显示表格中的数值
	int intTabValue[16];
	// 显示化简过程以及化简结果
	int curProcess;
	// 定时器
	UINT_PTR m_timer;
	bool timer_on;

	// 手工化简过程：几个最小项
	XTabDataManager tabSelfReducing;

	// 自动化简：几个最小项
	XTabDataManager * tabAutoReducing;//自动化简后
	int use_num;//debug
	int autonum;//共有几种化简方法
	int cur_autonum;//共有几种化简方法
	bool intArrayValue[16];//队列中剩余1的位置
	int intArrayNum;
	treeAutoReduce root;

	//判断化简方法是否一致
	bool CheckReduceOK();
	//自动化简
	void DeleteInvalid();
	void SearchAutoRedTree( treeAutoReduce * par );
	bool CanReduce( int val, int mask ,int item_num );
	void ReduceNext( treeAutoReduce * par , int val, int mask ,int item_num );
	void AutoReduce();

	void DrawTabData( CDC * );
	// 检测鼠标的位置
	int PointInWhichTab(CPoint poi, CRect & rect);
	void ChangeTabVal( int order );
	afx_msg void OnBnClickedButton4();
	// 正在手工化简
	void DrawSelfReduingTab(CDC *dc);
	void DrawThisBlock(CDC * dc, int * data, int count);
	afx_msg void OnBnClickedButton5();
	afx_msg void OnBnClickedButton6();
	afx_msg void OnBnClickedButton7();
	// 显示化简结果
	CString csReduceResult;
	void DrawSelfReduingProcess(CDC * dc);
	afx_msg void OnBnClickedButton8();
	afx_msg void OnBnClickedButton11();
	afx_msg void OnBnClickedButton12();
	afx_msg void OnBnClickedButton9();
	afx_msg void OnBnClickedButton13();
};