分治法解决残缺棋盘问题的C++程序资源-CSDN下载

共6个文件

ncb：1个

cpp：1个

dsp：1个

需积分: 50 40 浏览量 2010-06-17 08:51:01 上传评论 1 收藏 6KB RAR 举报

**分治法** 分治法是一种重要的算法设计策略，它将一个大问题分解为若干个规模较小、相互独立且与原问题形式相同的子问题来解决。分治法的基本步骤包括分解、解决和合并。在本题中，面对的是一个残缺的棋盘问题，我们可以通过分治法将其拆分为四个小棋盘，每个小棋盘的规模是原棋盘的四分之一。 1. **分解**：将8x8的大棋盘划分为4个4x4的小棋盘。由于棋盘中只有一个缺失方块，因此这个缺失方块必定位于这四个小棋盘中的一个。 2. **解决**：对每个4x4的小棋盘进行独立检查，看是否有缺失方块。如果一个小棋盘完整，那么我们可以忽略它；如果一个小棋盘有缺失，我们就继续对这个小棋盘进行相同的操作，直到我们找到具体缺失方块的位置。 3. **合并**：由于我们的目标是找出缺失方块的具体位置，一旦在某个小棋盘中找到，就不再需要继续分割，所以在这个问题中，合并步骤可以简化为报告找到的缺失方块的位置。 **残缺棋盘问题** 残缺棋盘问题是一个经典的计算机科学问题，通常与汉诺塔或八皇后问题等一起被用来教授分治法。在这种问题中，我们需要确定在一个8x8的棋盘上，如果只有一个方块缺失，如何快速地定位到这个缺失的方块。通过递归地应用分治策略，这个问题可以有效地解决，时间复杂度为O(n)，其中n是棋盘的边长（在这个例子中，n=8）。 **C++编程** 本题的解决方案使用C++语言实现，这是一种静态类型、编译式的通用编程语言。C++支持面向对象编程，同时也包含过程化编程和泛型编程的特点。在解决这个问题时，我们可能会定义一个函数，该函数接受棋盘的一个部分（可能是整个棋盘或一个子棋盘），然后递归地处理每个子区域，直到找到缺失的方块。 **文件列表** - `P1.CPP`：这是主程序文件，包含了用C++编写的问题解决方案代码。 - `P1.dsp`：这是Visual Studio项目文件，用于构建和管理项目。 - `P1.dsw`：这是Visual Studio工作区文件，包含了项目集和相关设置。 - `P1.ncb`：这是Visual Studio的非编译项数据库文件，用于提供IntelliSense功能。 - `P1.opt`：可能包含了项目的编译和链接选项。 - `P1.plg`：这是Visual Studio的插件状态文件，记录了上一次编译的错误和警告。利用分治法解决残缺棋盘问题，我们能够有效地在C++环境中实现一个程序，通过递归地检查棋盘的各个子区域，最终确定缺失方块的位置。这些文件则构成了该程序的开发环境和源代码。

资源推荐

资源详情

资源评论

收起资源包目录

残缺棋盘问题.rar （6个子文件）

P1.dsw 527B

P1.dsp 4KB

P1.CPP 4KB

P1.plg 1KB

P1.opt 48KB

P1.ncb 41KB

#include <iostream.h> #include <math.h> #include <time.h> #include <stdlib.h> #include <windows.h> #define BOARD_SIZE 32 int board[BOARD_SIZE][BOARD_SIZE]={0}; int val_sign; int sign(bool change=false) { if(change) { val_sign++; if (val_sign==32) val_sign++; } if(val_sign<14 || val_sign>127) val_sign=14; return val_sign; }; void fix(int left, int top, int right, int bottom, int empty_i, int empty_j) { int ret_val=0; int size=right-left+1; if (size==2) { sign(true); for (int i=left; i<=right; i++) for(int j=top; j<=bottom; j++) if (board[i][j]==1) board[i][j]=sign(); } else if (size>2) { int dir_i=(empty_i-left)/(size/2); int dir_j=(empty_j-top)/(size/2); if(dir_i==0 && dir_j==0) { board[left+size/2][top+size/2-1]=sign(true); board[left+size/2-1][top+size/2]=sign(); board[left+size/2][top+size/2]=sign(); fix(left, top, left+size/2 - 1, top+size/2 -1, empty_i, empty_j ); fix(left+size/2, top, right, top+size/2 - 1, left+size/2, top+size/2-1); fix(left, top+size/2, left+size/2 - 1, bottom, left+size/2 - 1, top+size/2 ); fix(left+size/2, top+size/2, right, bottom, left+size/2, top+size/2); } else if (dir_i==1 && dir_j==0) { board[left+size/2-1][top+size/2-1]=sign(true); board[left+size/2-1][top+size/2]=sign(); board[left+size/2][top+size/2]=sign(); fix(left, top, left+size/2 - 1, top+size/2 -1, left+size/2 - 1, top+size/2 - 1); fix(left+size/2, top, right, top+size/2 - 1, empty_i, empty_j); fix(left, top+size/2, left+size/2 - 1, bottom, left+size/2 - 1, top+size/2 ); fix(left+size/2, top+size/2, right, bottom, left+size/2, top+size/2); } else if (dir_i==0 && dir_j==1) { board[left+size/2-1][top+size/2-1]=sign(true); board[left+size/2][top+size/2-1]=sign(); board[left+size/2][top+size/2]=sign(); fix(left, top, left+size/2 - 1, top+size/2 -1, left+size/2 - 1, top+size/2 - 1); fix(left+size/2, top, right, top+size/2 - 1, left+size/2, top+size/2 - 1); fix(left, top+size/2, left+size/2 - 1, bottom, empty_i, empty_j); fix(left+size/2, top+size/2, right, bottom, left+size/2, top+size/2); } else if (dir_i==1 && dir_j==1) { board[left+size/2-1][top+size/2-1]=sign(true); board[left+size/2][top+size/2-1]=sign(); board[left+size/2-1][top+size/2]=sign(); fix(left, top, left+size/2 - 1, top+size/2 -1, left+size/2 - 1, top+size/2 - 1); fix(left+size/2, top, right, top+size/2 - 1, left+size/2, top+size/2 - 1); fix(left, top+size/2, left+size/2 - 1, bottom, left+size/2 - 1, top+size/2); fix(left+size/2, top+size/2, right, bottom, empty_i, empty_j); } } }; void main() { srand((unsigned) time(NULL)); for (int i=0; i<BOARD_SIZE; i++) for(int j=0; j<BOARD_SIZE; j++) board[i][j]=1; int random_i=rand()%BOARD_SIZE; int random_j=rand()%BOARD_SIZE; board[random_i][random_j]=0; cout<<"/////////////////////////////////////////////////////////////////////\n"; for (i=0; i<BOARD_SIZE; i++) { for(int j=0; j<BOARD_SIZE; j++) { cout<<board[i][j]<<' '; } cout<<'\n'; } cout<<"*********************************************************************\n"; fix(0,0,BOARD_SIZE-1,BOARD_SIZE-1,random_i, random_j); for (i=0; i<BOARD_SIZE; i++) { for(int j=0; j<BOARD_SIZE; j++) { cout<<(char)board[i][j]<<' '; } cout<<'\n'; } cout<<"/////////////////////////////////////////////////////////////////////\n"; cerr<<"Program will exit in 50 secs...\n"; Sleep(50000); }

评论收藏

内容反馈