余新华-5分.txt

这是很不错的计算机算法

/*棋盘覆盖问题求解程序*/
/*本程序运行前提：
  在源程序目录下存在input.txt文件，并且该文件已经按一定格式存储若干值
/*本程序在tc++3.0和vc++6.0上运行通过*/
#include<fstream.h>
#include<stdlib.h>
#include<iomanip.h>

int tile;//L型骨牌的编号 

class chess//棋盘类 
{
  private:
    int **board;//表示棋盘的二维数组指针 
    int n;//棋盘的行（列） 格子数 
  public:
    chess(const int,const int,const int);//构造函数 
    void chessboard(int,int,int,int,int);//棋盘覆盖函数 
    ~chess();//析构函数 
    friend void outputtofile(chess&);//输出棋盘方案到文件 
};

/*构造函数的定义*/ 
chess::chess(const int size,const int row,const int col)
{
  n=size;
  if(!(board=new int*[n]))//为棋盘数组分配空间
  {
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出
    exit(-1);
  }
  for(int i=0;i<n;i++)
    if(!(board[i]=new int[n]))//为每个一维数组分配空间
    {
      cerr<<"insufficient memory!"<<endl;//分配不成功，退出
      delete[] board;
      exit(-1);
    }
  board[row-1][col-1]=0;//设置特殊方格元素为0 
}

/*析构函数的定义*/ 
chess::~chess()
{
  for(int i=0;i<n;i++)//释放棋盘数组所占内存 
    delete[] board[i];
  delete[] board;
}

/*棋盘覆盖函数的定义*/ 
void chess::chessboard(int trow,int tcol,int drow,int dcol,int size)
{
  if(size==1) return;//如果棋盘大小是1，则返回 
  int t=++tile;//L型骨牌编号加1 
  int s=size/2;//分割棋盘
  //覆盖左上角子棋盘 
  if(drow<trow+s && dcol<tcol+s)//特殊方格在此棋盘中 
    chessboard(trow,tcol,drow,dcol,s);//递归覆盖此棋盘
  else//此棋盘中无特殊方格 
  {
    board[trow+s-1][tcol+s-1]=t;//用t号L型骨牌覆盖右下角 
    chessboard(trow,tcol,trow+s-1,tcol+s-1,s);//递归覆盖此棋盘 
  }
  /*覆盖右上角子棋盘*/ 
  if(drow<trow+s && dcol>=tcol+s)//特殊方格在此棋盘中
    chessboard(trow,tcol+s,drow,dcol,s);//递归覆盖此棋盘
  else//此棋盘中无特殊方格
  {
    board[trow+s-1][tcol+s]=t;//用t号L型骨牌覆盖左下角
    chessboard(trow,tcol+s,trow+s-1,tcol+s,s);//递归覆盖此棋盘
  }
  /*覆盖左下角子棋盘*/
  if(drow>=trow+s && dcol<tcol+s)//特殊方格在此棋盘中
    chessboard(trow+s,tcol,drow,dcol,s);//递归覆盖此棋盘
  else//此棋盘中无特殊方格
  {
    board[trow+s][tcol+s-1]=t;//用t号L型骨牌覆盖右上角
    chessboard(trow+s,tcol,trow+s,tcol+s-1,s);//递归覆盖此棋盘
  }
  /*覆盖右下角子棋盘*/ 
  if(drow>=trow+s && dcol>=tcol+s)//特殊方格在此棋盘中
    chessboard(trow+s,tcol+s,drow,dcol,s);//递归覆盖此棋盘
  else//此棋盘中无特殊方格
  {
    board[trow+s][tcol+s]=t;//用t号L型骨牌覆盖左上角
    chessboard(trow+s,tcol+s,trow+s,tcol+s,s);//递归覆盖此棋盘
  }
}

/*普通函数声明部分*/ 
void inputfromfile(int&,int&,int&);
void outputtofile(chess&);

/*主程序部分*/ 
int main()
{
  int n,row,col;
  inputfromfile(n,row,col);//从文件获取所需值 
  chess mychess(n,row,col);//创建棋盘对象 
  mychess.chessboard(0,0,row-1,col-1,n);//开始覆盖棋盘 
  outputtofile(mychess);//输出棋盘方案到文件 
  return 0;
}

/*inputfromfile函数定义*/ 
void inputfromfile(int& n,int& row,int& col)
{
  int k;
  ifstream fin("input.txt",ios::nocreate);//打开输入文件
  if(!fin) //如果文件不存在 
  {
    cerr<<"文件不存在";
    exit(-1);
  } 
  fin>>k>>row>>col;//读出阶数k和特殊方格位置 
  n=1;
  for(int i=1;i<=k;i++)//求得棋盘行（列） 格子数 
    n*=2;
  fin.close();//关闭输入文件 
}

/*outputtofile函数定义*/ 
void outputtofile(chess& mychess)
{
  ofstream out("output.txt");//创建输出文件
  for(int i=0;i<mychess.n;i++)//输出每个格子的状态
  {
    for(int j=0;j<mychess.n;j++)
      out<<setw(3)<<mychess.board[i][j]<<" ";
    out<<endl;//一行完毕换行 
  }
  out.close();//关闭输出文件 
}