eignumdlg.cpp

8数码

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

#include "stdafx.h"
#include "EigNum.h"
#include "EigNumDlg.h"
#include <queue> 
#include <stack>
#include<math.h>

#define NOT ! 
#define INF 1000000 
#define HashTableSize 362880 
using namespace std;
#ifdef _DEBUG
#define new DEBUG_NEW
#endif
//////////////////////////////////////////////////////////////


/*** 重载 == 运算符*****/ 

	    bool operator < (const maps& a, const maps& b)  
{ 
  return a.fx > b.fx ;  
} 
Map   org;                    //  初始状态 
Map   result; 
stack<Map> Stack; 
int   end[9][2] ;            // 目的状态 
int   BestAnswer;           // 目前最好结果的代价 
int   N=0;                      //产生的节点数
double  B;                 //平均分枝因子
     
PMap  HashTable[HashTableSize]={NULL};        //hash表 
bool  FlageNew;                                //标志是否是新状态 

short const derection[4][2] ={ { 0 , -1 } , { -1 , 0 } , { 0, 1 } , {1, 0 } } ;  // 可移动的四个方向 
/////////////////////////////////////////////////////////

// 用于应用程序“关于”菜单项的 CAboutDlg 对话框

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

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

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

// 实现
protected:
	DECLARE_MESSAGE_MAP()
public:
	afx_msg void OnBnClickedAbout();
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	ON_BN_CLICKED(IDC_ABOUT, &CAboutDlg::OnBnClickedAbout)
END_MESSAGE_MAP()


// CEigNumDlg 对话框




CEigNumDlg::CEigNumDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CEigNumDlg::IDD, pParent)
	, algo(0)
	, m_num0(0)
	, m_num1(0)
	, m_num2(0)
	, m_num3(0)
	, m_num4(0)
	, m_num5(0)
	, m_num6(0)
	, m_num7(0)
	, m_num8(0)
{
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);

	m_flag=TRUE;
}

void CEigNumDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	DDX_Radio(pDX, IDC_RADIO1, algo);
	DDX_Text(pDX, IDC_EDIT1, m_num0);
	DDX_Text(pDX, IDC_EDIT2, m_num1);
	DDX_Text(pDX, IDC_EDIT3, m_num2);
	DDX_Text(pDX, IDC_EDIT4, m_num3);
	DDX_Text(pDX, IDC_EDIT7, m_num4);
	DDX_Text(pDX, IDC_EDIT8, m_num5);
	DDX_Text(pDX, IDC_EDIT5, m_num6);
	DDX_Text(pDX, IDC_EDIT6, m_num7);
	DDX_Text(pDX, IDC_EDIT9, m_num8);
}

BEGIN_MESSAGE_MAP(CEigNumDlg, CDialog)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	//}}AFX_MSG_MAP
	ON_BN_CLICKED(IDC_START, &CEigNumDlg::OnBnClickedStart)
	ON_WM_TIMER()
	ON_BN_CLICKED(IDC_SHOW, &CEigNumDlg::OnBnClickedShow)
	ON_BN_CLICKED(IDC_STEP, &CEigNumDlg::OnBnClickedStep)
	ON_BN_CLICKED(IDC_RESET, &CEigNumDlg::OnBnClickedReset)
END_MESSAGE_MAP()


// CEigNumDlg 消息处理程序

BOOL CEigNumDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// 将“关于...”菜单项添加到系统菜单中。

	// IDM_ABOUTBOX 必须在系统命令范围内。
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// 设置此对话框的图标。当应用程序主窗口不是对话框时，框架将自动
	//  执行此操作
	SetIcon(m_hIcon, TRUE);			// 设置大图标
	SetIcon(m_hIcon, FALSE);		// 设置小图标

	// TODO: 在此添加额外的初始化代码

		SetDlgItemInt(IDC_EDIT10,0);
		SetDlgItemInt(IDC_EDIT11,0);
		SetDlgItemInt(IDC_EDIT12,0);
		SetDlgItemInt(IDC_EDIT13,0);
		SetDlgItemInt(IDC_EDIT14,0);
		SetDlgItemInt(IDC_EDIT15,0);
		SetDlgItemInt(IDC_EDIT16,0);
		SetDlgItemInt(IDC_EDIT17,0);
		SetDlgItemInt(IDC_EDIT18,0);

	return TRUE;  // 除非将焦点设置到控件，否则返回 TRUE
}

void CEigNumDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// 如果向对话框添加最小化按钮，则需要下面的代码
//  来绘制该图标。对于使用文档/视图模型的 MFC 应用程序，
//  这将由框架自动完成。

void CEigNumDlg::OnPaint()
{
	if (IsIconic())
	{
		CPaintDC dc(this); // 用于绘制的设备上下文

		SendMessage(WM_ICONERASEBKGND, reinterpret_cast<WPARAM>(dc.GetSafeHdc()), 0);

		// 使图标在工作区矩形中居中
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// 绘制图标
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

//当用户拖动最小化窗口时系统调用此函数取得光标
//显示。
HCURSOR CEigNumDlg::OnQueryDragIcon()
{
	return static_cast<HCURSOR>(m_hIcon);
}


void CEigNumDlg::OnBnClickedStart()
{
	// TODO: 在此添加控件通知处理程序代码
	m_num0=GetDlgItemInt(IDC_EDIT1);
	m_num1=GetDlgItemInt(IDC_EDIT2);
	m_num2=GetDlgItemInt(IDC_EDIT3);
	m_num3=GetDlgItemInt(IDC_EDIT4);
	m_num4=GetDlgItemInt(IDC_EDIT7);
	m_num5=GetDlgItemInt(IDC_EDIT8);
	m_num6=GetDlgItemInt(IDC_EDIT5);
	m_num7=GetDlgItemInt(IDC_EDIT6);
	m_num8=GetDlgItemInt(IDC_EDIT9);

	m_set[0]=m_num0;
	m_set[1]=m_num1;
	m_set[2]=m_num2;
	m_set[3]=m_num3;
	m_set[4]=m_num4;
	m_set[5]=m_num5;
	m_set[6]=m_num6;
	m_set[7]=m_num7;
	m_set[8]=m_num8;

	if (IsDlgButtonChecked(IDC_RADIO1))
		algo=0;
	else algo=1;
	input();
	long time =GetTickCount(); 
    Axin(); 
	m_time=GetTickCount()-time;
	SetDlgItemInt(IDC_SHIJIAN,m_time);

	FindPath(); 

}

double CEigNumDlg::fenzi(int n,int d)
 {
   double a=1.0001;
   double e;
  // double c;
   double b;
   double p,q;
   if(a==1)b=d;
    b= (1-pow(a,d))/(1-a);
   
   while(b<n)
   {
     a++;
	 b = (1-pow(a,d))/(1-a);          ///解区间为[e,a];
   }
   e=a-1;
  // c = (1-pow(e,d))/(1-e);
   p=(e+a)/2;
    q = (1-pow(p,d))/(1-p);
	while( ((int)q!=n))
   {
	   if((q<n)){
		   e=p;
		   p=(e+a)/2;
		  // cout<<"  "<<p<<endl;
	   }
	   else {
		   a=p;
		   p=(e+a)/2;
		   //cout<<"  "<<p<<endl;
	   }
	 q = (1-pow(p,d))/(1-p);
	 //if ((int)q==n) break;
	   //cout<<"**"<<endl;
	  // cout<<q<<endl;
	}
    return p;
 }

/** 
 * 
 * 评估函数 h(x) ： 计算每个位置到离它目标位置的和。 
 * 
 **/ 


int CEigNumDlg::evaluate_hx(int a[3][3])   
{ 
    int hx =0 ; 
    int temp ;  

	if (algo==0)
	{
    for(int i =0 ; i < 3; i ++ ) 
        for(int j =0 ; j< 3 ;j ++ ) 
         { 
            if(a[i][j] ==0) continue ;  
            temp = i - end[ a[i][j] ][0] ;  
            if(temp < 0 ) temp = -temp ;  
            hx += temp ;  
            temp = j  - end[ a[i][j] ][1] ;  
            if(temp < 0 ) temp = - temp ;  
            hx += temp ;  
        } 
	}
	else
	{
	for(int i =0 ; i < 3; i ++ ) 
       for(int j =0 ; j< 3 ;j ++ ) 
         { 
           if(i==end[ a[i][j] ][0]&&j==end[ a[i][j] ][1]) continue ;  
           hx++;
		 } 
	}
    return hx ;  
} 

/** 
 * 
 *    八数码的输入（在这里不做任何输入检查，均认为输入数据是正确的） 
 * 
 **/ 
void CEigNumDlg::input() 
{ 
    int i,j; 
    int sum=0; 
    for(i = 0 ; i < 9 ; i ++ ) 
    { 
         *(*org.detail + i)=m_set[i];  
        if(0 == *(*org.detail + i) )