棋盘覆盖问题
方法1
#include
using namespace std;
int tile=0;
const int M = 100;
int Board[M][M];
void ChessBoard(int tr,int tc,int dr,int dc,int size) {
if (size==1) return;
int t=tile++,//L型骨牌
s=size/2;//分割棋盘
//覆盖左上角子棋盘
if(dr < tr + s && dc < tc + s)
//特殊方格在此棋盘中
ChessBoard( tr, tc, dr, dc, s);
else
{
//此棋盘中无特殊方格
//用t号L型骨牌覆盖右下角
Board[tr + s - 1 ][tc + s - 1]=t;
//覆盖其余方格
ChessBoard( tr, tc, tr + s -1, tc + s - 1, s);
}
//覆盖右上角子棋盘
if( dr < tr + s && dc >= tc + s)
//特殊方格在此棋盘中
ChessBoard( tr, tc + s, dr, dc, s);
else
{
//此棋盘中无特殊方格
//用t号L型骨牌覆盖左下角
Board[ tr + s - 1][ tc + s] = t;
//覆盖其余方格
ChessBoard( tr, tc + s, tr + s -1, tc + s, s);
}
//覆盖左下角子棋盘
if( dr >= tr + s && dc < tc + s)
//特殊方格在此棋盘中
ChessBoard( tr + s, tc, dr, dc, s);
else
{
//用t号L型骨牌覆盖右上角
Board[ tr + s][ tc + s - 1] = t;
//覆盖其余方格
ChessBoard( tr + s, tc, tr + s, tc + s - 1, s);
}
//覆盖右下角子方格
if( dr >= tr + s && dc >= tc + s)
//特殊方格在此棋盘中
ChessBoard( tr + s, tc + s, dr, dc, s);
else
{
//用t号L型骨牌覆盖左上角
Board[ tr + s][ tc + s ] = t;
//覆盖其余方格
ChessBoard( tr + s, tc + s, tr + s, tc + s, s);
}
}
int main()
{
int size,x,y;
cout<<"输入棋盘的大小（2的n次幂）：";
cin>>size;
cout<<"输入特殊方格位置的坐标：";
cin>>x>>y;
ChessBoard(1, 1, x, y, size);
for( int i = 1; i <= size; i++)
{
for(int j = 1;j <= size; j++)
{
cout< } cout< } return 0; } 方法2 #include using namespace std; int tile=0; const int M = 100; int Board[M][M]; void CB2(int size) { int t=1; if (size<4) { return ; } int sizesub=size/2; //子块的大小 int sumTmp=0;//判断子块是否有特殊方格while (sizesub>=2) { // i,j为子块的左上角 for (int i=0;i { //的坐标 for (int j=0;j { //左上角子棋盘有特殊方格吗？ t++; sumTmp=0; for (int dr1=0;dr1 { for (int dc1=0;dc1 { sumTmp+=Board[dr1+i][dc1+j]; } } if (sumTmp==0) { Board[i+sizesub-1][j+sizesub-1]=t; } //右上角子棋盘有特殊方格吗？ sumTmp=0; for (dr1=0;dr1 { for (int dc1=0;dc1 { sumTmp+=Board[dr1+i][dc1+sizesub+j]; } } if (sumTmp==0) { Board[i+sizesub-1][j+sizesub]=t; } //左下角子棋盘有特殊方格吗？ sumTmp=0; for (dr1=0;dr1 { for (int dc1=0;dc1 { sumTmp+=Board[dr1+sizesub+i][dc1+j]; } } if (sumTmp==0) { Board[i+sizesub][j+sizesub-1]=t; } //右下角有特殊方格吗？ sumTmp=0; for (dr1=0;dr1 { for (int dc1=0;dc1 { sumTmp+=Board[dr1+sizesub+i][dc1+sizesub+j]; } } if (sumTmp==0) { Board[i+sizesub][j+sizesub]=t; } } } sizesub=sizesub/2;//可用>>1 } for (int i=0;i { for (int j=0;j { //处理一个小四块 for (int dr1=0;dr1<2;dr1++) { for (int dc1=0;dc1<2;dc1++) { if (Board[dr1+i][dc1+j]==0) {Board[dr1+i][dc1+j]=t; } } } t++; } } } void main() { int size,x,y; cout<<"输入棋盘的大小（2的n次幂）："; cin>>size; cout<<"输入特殊方格位置的坐标："; cin>>x>>y; CB2(size); for( int i = 0; i <= size; i++) { for(int j = 0;j <= size; j++) { cout< } cout< } } 小学六年级奥数教案一15棋盘的覆盖 本教程共30讲 棋盘的覆盖 同学们会下棋吗？下棋就要有棋盘，下面是中国象棋的棋盘（图1）, 围棋棋盘（图2）和国际象棋棋盘（图3）。 用某种形状的卡片，按一定要求将棋盘覆盖住，就是棋盘的覆盖问题。 实际上，这里并不要求一定是某种棋盘，只要是有关覆盖若干行、若干列 的方格网的问题，就是棋盘的覆盖问题。 棋盘的覆盖问题可以分为两类：一是能不能覆盖的问题，二是有多少 种不同的覆盖方法问题。 例1要不重叠地刚好覆盖住一个正方形，最少要用多少个右图所示 的图形？ 分析与解：因为图形由3个小方格构成，所以要拼成的正方形内所含 的小方格数应是3的倍数，从而正方形的边长应是3的倍数。经试验，不 可能拼成边长为3的正方形。所以拼成的正方形的边长最少是 6（见右图）， 需要用题目所示的图形 36 - 3= 12 （个）。 F r I r 图2 例2能否用峠个形如匚□的卡片将左下图覆盖？ 分析与解：在五年级学习“奇偶性”时已经讲过类似问题。左上图共有34个小方格，17个1X 2的卡片也有34个小方格，好象能覆盖住。我们将左上图黑白相间染色，得到右上图。细心观察会发现，右上图中黑格有16个，白格有18个，而1X 2的卡片每次只能盖住一个黑格与一个白格，所以17个1X 2的卡片应当盖住黑、白格各17个，不可能盖住左上图。 例3下图的七种图形都是由4个相同的小方格组成的。现在要用这些图形拼成一个4X 7的长方形（可以重复使用某些图形），那么，最多可以用上几种不同的图形？ 分析与解：先从简单的情形开始考虑。显然，只用1种图形是可以的, 例如用7个（7）;用2种图形也没问题，例如用1个（7），6个（1）经试验，用6种图形也可以拼成4X 7的长方形（见下图）。 能否将7种图形都用上呢？7个图形共有4X 7=28 （个）小方格，从 小方格的数量看，如果每种图形用1个，那么有可能拼成4X 7的长方形。但事实上却拼不成。为了说明，我们将4X 7的长方形黑、白相间染色（见右图），图中黑、白格各有14个。在7种图形中，除第（2）种外，每种图形都覆盖黑、白格各2个，共覆盖黑、白格各12个，还剩下黑、白格各2 个。第（2）种图形只能覆盖3个黑格1个白格或3个白格1个黑格, 因此不可能覆盖住另6种图形覆盖后剩下的2个黑格2个白格。 伪代码 伪码（Pseudocode）是一种算法描述语言。使用伪码的目的是使被描述的算法可以容易地以任何一种编程语言（Pascal，C，Java等）实现。因此，伪代码必须结构清晰、代码简单、可读性好，并且类似自然语言。介于自然语言与编程语言之间。以编程语言的书写形式指明算法职能。使用伪代码，不用拘泥于具体实现。相比程序语言（例如Java, C++,C, Dephi 等等）它更类似自然语言。它是半角式化、不标准的语言。可以将整个算法运行过程的结构用接近自然语言的形式（可以使用任何一种你熟悉的文字，关键是把程序的意思表达出来）描述出来。 1.简介 定义 人们在用不同的编程语言实现同一个算法时意识到，他们的实现（注意：这里是实现，不是功能）很不同。尤其是对于那些熟练于不同编程语言的程序员要理解一个（用其他编程语言编写的程序的）功能时可能很难，因为程序语言的形式限制了程序员对程序关键部分的理解。这样伪代码就应运而生了。伪代码提供了更多的设计信息，每一个模块的描述都必须与设计结构图一起出现。伪代码是一种非正式的，类似于英语结构的，用于描述模块结构图的语言。 应用领域 当考虑算法功能（而不是其语言实现）时，伪码常常得到应用。伪码中常被用于技术文档和科学出版物中来表示算法，也被用于在软件开发的实际编码过程之前表达程序的逻辑。伪代码不是用户和分析师的工具，而是设计师和程序员的工具。计算机科学在教学中通常使用虚拟码，以使得所有的程序员都能理解。综上，简单地说，让人便于理解的代码。不依赖于语言的，用来表示程序执行过程，而不一定能编译运行的代码。在数据结构讲算法的时候用的很多。伪代码用来表达程序员开始编码前的想法。 2.语法规则 例如，类Pascal语言的伪码的语法规则是：在伪码中，每一条指令占一行（else if，例外）。指令后不跟任何符号（Pascal和C中语句要以分号结尾）。书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序 一、实验目的：用ABCD四个字母代替四种L型骨牌，覆盖于2^kX2^k大小的棋盘中 二、实验内容： 在一个2^k×2^k （k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有4^k种，因而有4k种不同的棋盘，图4.10(a)所示是k=2时16种棋盘中的一个。棋盘覆盖问题（chess cover problem）要求用图4.10(b)所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 三、程序设计说明：(算法设计思路) 主要思路是利用递归处理棋盘，先确定每个棋盘的特殊骨牌，然后由骨牌位置确定所摆放L型骨牌的型号，依次递归所有棋盘即得其解 四、程序代码（经调试正确的源程序） using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication4 { class Program { static void Main(string[] args) { char[,] chessboard = new char[1000,1000]; int startU = 1; int endU = 4;//在这里输入棋盘的大小 int startV = 1; int endV = endU; int specialU =2; int specialV = 3; setblock(startU, endU, startV, endV, chessboard, specialU, specialV); printchessboard(startU, endU, startV, endV,specialU,specialV, chessboard); Console.ReadLine(); //************1、算法没问题，程序实现有问题，增加了L型方 算法设计与分析实验报告 专业： 学号： 姓名： 指导老师： 实验一：棋盘覆盖 一、实验目的与要求 1、理解算法的概念 2、实现棋盘化以及棋盘覆盖 二、实验题： 1、编程任务：设计棋盘覆盖的一个简单算法 2、输入数据：输入特殊方格的行号和特殊方格的列号以及棋盘的大小 3、结果输出：将计算结果输出显示棋盘 解： 1,实现解释。 本程序采用java实现的，要输入期盘覆盖的行数，然后随机出现一个黑色的特殊方格，然后用其他的颜色覆盖。 出现初始画面：如图：然后点击操作： 出现对话框：然后输入棋盘覆盖的行数： 输入行数，如：8，然后点击确定：运行如下 实验源码如下： package two; import java.awt.*; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import javax.swing.*; import java.util.*; /** * * @author 郑金光 */ public class FenZi { public static void main(String args[]) { new MyChessBoard(); } } class MyChessBoard extends JFrame implements ActionListener { int dimen; //棋盘规模 int x_pos; //特殊点横坐标 int y_pos; //特殊点竖坐标 Container p; public MyChessBoard() { super(); x_pos = 0; y_pos = 0; dimen = 0; setTitle("棋盘覆盖"); setBackground(Color.YELLOW); setBounds(300,150,510,480); centreOnScreen(); //setResizable(false); p = getContentPane(); JMenuBar jmb = new JMenuBar(); JMenu jm = new JMenu("操作"); JMenuItem jitem1 = new JMenuItem("开始"); JMenuItem jitem2 = new JMenuItem("退出"); jm.add(jitem1); 实用文案 修订记录 目录 第一章概述 (5) 1.1.应用模块的目的 (5) 1.2.应用模块总体描述 (5) 1.3.应用模块接口描述 (5) 1.4.假设条件 (5) 第二章设计模式（Design pattern） (6) 第三章类设计 (7) 3.1.分块类图 (8) 3.1.1.<类图1> 8 3.1.2.<类图n> 8 3.2.整体继承关系 (8) 3.3.类描述 (9) 3.3.1.<类名1> Class Description 9 3.3.2.<类名n> Class Description 10 第四章交互图 (12) 4.1.<情景编号1: 情景名称> (12) 4.1.1.交互图 12 4.1.2.例外情况及条件 13 4.2.<情景编号n: 情景名称> (13) 第五章状态图 (14) 5.1.<状态图编号1:状态图名称> (14) 5.2.<状态图编号n:状态图名称> (15) 第六章时序流程图 (16) 第七章用户界面设计说明 (18) 7.1.用户界面关系 (18) 7.2.用户界面具体描述 (18) 7.2.1.<界面编号1:界面名称〉 18 7.2.2.<界面编号N:界面名称〉 19 第八章测试考虑 (20) 第九章附录 (21) 9.1.附录A 代码举例 (21) 9.2.附录B 设计问题 (21) 9.2.1.<设计问题1> 21 9.2.2.<设计问题n> 21 第一章概述 1.1.应用模块的目的 请明确客户建立应用模块的目的。 1.2.应用模块总体描述 描述应用模块的总体功能。 1.3.应用模块接口描述 简要描述本应用模块的公共接口，具体接口会在相应的类中进行具体描述。建议采用列表的方式。 1.4.假设条件 列出在问题领域，项目方案及其它影响系统设计的可能方面内，应当成立的假设条件。包括系统的约束条件和应遵循的标准。 实验二动态规划算法棋盘覆盖 最长公共子序列问题 一、实验目的 : 1、熟悉最长公共子序列问题的算法； 2、初步掌握动态规划算法。 二、实验内容 若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。 三、实验步骤 1、代码 // ZXL_1.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "iostream.h" #include //为每一行分配空间 for( int i= 0 ; i 棋盘的覆盖 同学们会下棋吗？下棋就要有棋盘，下面是中国象棋的棋盘（图1），围棋棋盘（图2）和国际象棋棋盘（图3）。 用某种形状的卡片，按一定要求将棋盘覆盖住，就是棋盘的覆盖问题。 例1要不重叠地刚好覆盖住一个正方形，最少要用多少个下图所示的图形？ 例2 能否用17个形如的卡片将下图刚好覆盖？ 例3 下图的七种图形都是由4个相同的小方格组成的。现在要用这些图形拼成一个4×7的长方形（可以重复使用某些图形），那么，最多可以用上几种不同的图形？ 例4 用1×1，2×2，3×3的小正方形拼成一个11×11的大正方形，最少要用1×1的正方形多少个？ 例5用七个1×2的小长方形覆盖下图，共有多少种不同的覆盖方法？ 例6有许多边长为1厘米、2厘米、3厘米的正方形硬纸片。用这些硬纸片拼成一个长5厘米、宽3厘米的长方形的纸板，共有多少种不同的拼法？（通过旋转及翻转能相互得到的拼法认为是相同的拼法） 课后练习 1.在4×4的正方形中，至少要放多少个形如所示的卡片，才能使得在不重 叠的情形下，不能再在正方形中多放一个这样的卡片？（要求卡片的边缘与格线重合） 2.下列各图中哪几个能用若干个或拼成？ 3.能否用9个形如的卡片覆盖住6×6的棋盘？ 4.小明有8张连在一起的电影票（如右图），他自己要留下4张连在一起的票，其余的送给别人。他留下的四张票可以有多少种不同情况？ 5.有若干个边长为1、边长为2、边长为3的小正方形，从中选出一些拼成一个边长为4的大正方形，共有多少种不同拼法？（只要选择的各种小正方形的数目相同就算相同的拼法） 6.用6个形如的卡片覆盖下图，共有多少种不同的覆盖方法？ 7.能不能用9个1×4的长方形卡片拼成一个6×6的正方形？ 项目编码规范 （一）命名规范 Java包、类的命名应尽量采用完整的英文描述符，一般采用小写英文字母，但类名、接口名以及任何非初始单词的第一个字母要大写，不能用完整英文描述的，应以该英文单词的前四个字母或能代表单词意思的缩写代替。具体如下： （1）尽量使用完整的英文描述符； （2）采用合适于相关领域的术语 （3）采用大小写混合使名字可读 （4）尽量少用缩写，确有需要的，要能表达其意义； （5）避免使用长的名字（小于15个字母） （6）避免使用类似的名字，或者是大小写不同的名字； （7）避免使用下划线（除静态常量等）； 举例如下： 包(packge) 采用完整的英文描述符，应该都是由小写字母组成。对于全局包，将你的internet域名反转并接上包名。如：com.boyi.eim,com.boyi.oa.web 类(Class) 采用完整的英文描述符，所有单词的第一个字母大写。如：User,StuManager 接口(interface) 采用完整的英文描述符说明接口封装,所有单词第一个字母大写。名字后面加上后缀Dao，实体类实现接口加上后缀Impl 类变量：采用完整的英文描述符，第一个字母小写，后所有单词的第一个字母大写。如：userName 参数：同上 获取成员函数:封装字段，被访问时调用get set方法 普通成员函数：采用完整的英文描述符，第一个字母小写，后所有单词的第一个字母大写。 静态常量字段：全部采用大写字母，单词之间用下划线分隔。 循环计数器：通常采用字母I,j,k…………….. 数组：采用完整的英文描述符，第一个字母小写，后所有单词的第一个字母大写 （二）代码注释 良好的注释习惯对于一支程序来说，是其易于解读的关键。也就是说，如果另一个编程人员从未见过这段代码，要在合理的时间内理解代码，需要知道哪些信息。并以此作为注释的依据。因此对于注释来说，需要注意以下几点： （1）注释应该增加代码的清晰度； （2）保持注释的简洁； （3）在写代码之前写注释 （4）注释出为什么做了一些事，而不仅仅是做了什么 使用代码注释的目的: （1）文字说明代码的作用(即为什么要用编写该代码,而不是如何编写); （2）确指出该代码的编写思路和逻辑方法; （3）人们注意到代码中的重要转折点; （4）使代码的阅读者不必在他们的头脑中仿真运行代码的执行方法. 代码注释原则： 1. 用文字说明代码的作用:简单的重复代码做写什么,这样的注释几乎不能给注释增加什么信息.如果你使用好的命名方法来创建直观明 了的代码那么这些类型的注释绝对增加不了什么信息. 2. 如果你想违背好的编程原则,请说明为什么：有的时候你可能需要违背好的编程原则，或者使用了某些不正规的方法，.遇到这种情况 时,请用内部注释来说明你在做什么和为什么要这样做。技巧性特别高的代码段，一定要加详细的注释，不要让其他开发人员花很长时间来研究一个高技巧但不易理解的程序段。 3. 用注释来说明何时可能出错和为什么出错 4. 在编写代码前进行注释：给代码加注释的方法之一是在编写一个方法前首先写上注释.如果你愿意,可以编写完整句子的注释或伪代码. 用Visual C++实现棋盘覆盖分治算法 一、问题描述 在一个k k 22?个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘唯一特殊棋盘。在棋盘覆盖问题中，要用4种不同形态的L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L 型骨牌不得重叠覆盖。 当0k >时，将k k 22?棋盘分割为4个1-k 1-k 22?子棋盘，特殊方格必位于4个较小子棋盘之一中，将其余3个子棋盘中无特殊方格。为了将这3个无特殊方格子棋盘转化为特殊棋盘，可以用一个L 型骨牌覆盖着3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归的使用这种分割，直至棋盘转化为棋盘11?。 二、程序 （1）新建一个基于对话框的工程Ex0420Chess 。 （2）打开类视图，为CEx0420ChessDlg 类添加以下成员变量和函数： int tile; //当前方块 int **board; //指向棋盘的指针 int m_dw; //棋盘每一格的宽度 void chessBoard(int tr, int tc, int dr, int dc, int size); //棋盘覆盖算法 void DrawSubBoard(int x, int y, int w, int c); //画棋盘的x行，y列的方块，w表示宽度，c表示颜色值 （3）在对话框上增加三个编辑框，ID分别IDC_K、IDC_DR和IDC_DC，并为他们分别关联一个int型的变量m_k、m_dr和m_dc。 然后添加三个按钮，ID分别为IDC_DRAW、IDC_DRAWBOAR和DIDC_CLEAR，标题分别为画棋盘、覆盖和清空。 256 ，k值越大，方格越（4）本实验棋盘的大小固定为256 多，这时每个方格的尺寸越小。为给每个L型骨牌填充不同的颜色，程序中将title的值转换成颜色值，画一个方格的函数DrawSubBoard（）的定义如下： void CEx0420ChessDlg::DrawSubBoard(int x ,int y ,int w, int c) { CClientDC dc(this); COLORREF clr; clr= RGB(c*c/256,c*c*c/256,c*c*c*c/256); //将c值转换成颜色值 CBrush br(clr); CRect r; =10+x*m_dw; =+m_dw; =10+y*m_dw; =+m_dw; 1.1需求规格说明书 需求规格相当于软件开发的图纸，一般说，软件需求规格说明书的格式可以根 据项目的具体情况采用不同的格式，没有统一的标准。下面是一个可以参照的 软件需求规格说明书的模板。 1．导言 1.1目的 [说明编写这份项目需求规格的目的，指出预期的读者] 1.2背景 说明： a）待开发的产品名称； b）本项目的任务提出者、开发者、用户及实现该产品的单位； c）该系统同其他系统的相互来往关系。 1.3缩写说明 [缩写] [缩写说明] 列出本文件中用到的外文首字母组词的原词组。 1.4术语定义 [术语] [术语定义] 列出本文件中用到的专门术语的定义。 1.5参考资料 [编号]《参考资料》[版本号] 列出相关的参考资料。 1.6版本更新信息 具体版本更新记录如表所列。 表版本更新记录 2．任务概述 2.1 系统定义 本节描述内容包括： ●项目来源及背景； ●项目要达到的目标，如市场目标、技术目标等； ●系统整体结构，如系统框架、系统提供的主要功能，涉及的接口等； ●各组成部分结构，如果所定义的产品是一个更大的系统的一个组成部分， 则应说明本产品与该系统中其他各组成部分之间的关系，为此可使用一张 方框图来说明该系统的组成和本产品同其他各部分的联系和接口。 2.2 应用环境 本节应根据用户的要求对系统的运行环境进行定义，描述内容包括： ●设备环境； ●系统运行硬件环境； ●系统运行软件环境； ●系统运行网络环境； ●用户操作模式； ●当前应用环境。 2.3 假定和约束 列出进行本产品开发工作的假定和约束，例如经费限制、开发期限等。列出本产品的最终用户的特点，充分说明操作人员、维护人员的教育水平和技术专长以及本产品的预期使用频度等重要约束。 3．需求规定 1.1对功能的规定 本节依据合同中定义的系统组成部分分别描述其功能，描述应包括： ●功能编号； ●所属产品编号； ●优先级； ●功能定义； ●功能描述。 1.2对性能的规定 本节描述用户对系统的性能需求，可能的系统性能需求有： ●系统响应时间需求； ●系统开放性需求； ●系统可靠性需求； ●系统可移植性和可扩展性需求； ●系统安全性需求； ●现有资源利用性需求。 1.2.1精度 说明对该产品的输入、输出数据精度的要求，可能包括传输过程中的精度。 1.2.2时间特性要求 说明对于该产品的时间特性要求，如对： a）响应时间； b）更新处理时间； c）数据的转换和传送时间； d）计算时间等的要求。 1.2.3灵活性 说明对该产品的灵活性的要求，即当需求发生某些变化时，该产品对这些变化的适应能力，如： a）操作方式上的变化； b）运行环境的变化； c）同其他系统的接口的变化； d）精度和有效时限的变化； e）计划的变化或改进。 对于为了提供这些灵活性而进行的专门设计的部分应该加以标明。 1.3输入输出的要求 解释各输入输出的数据类型，并逐项说明其媒体、格式、数值范围、精度等。 对软件的数据输出及必须标明的控制输出量进行解释并举例，包括对硬拷贝报 棋盘覆盖问题 代码：分治法 需要说明： tr:棋盘左上角方格的行号 tc:棋盘左上角方格的列号 dr:特殊方格所在的行号 dc:特殊方格所在的列号 size:方形棋盘的边长 #include ChessBoard(tr, tc, dr, dc, s); else//此棋盘无特殊方格 { //用t号L型骨型牌覆盖右下角Board[tr+s-1][tc+s-1] = t; //覆盖其余方格 ChessBoard(tr, tc, tr+s-1, tc+s-1, s); } //覆盖右上角子棋盘 if(dr 《嵌入式系统原理及应用》作业题目 作业1 一、调试下面的程序，并回答问题。 .global _start .text _start: LDR SP, =src LDMFD SP!,{R0-R6} STMFD SP!,{R0-R6} LDMFD SP!,{R3} LDMFD SP!,{R4} LDMFD SP!,{R5} LDMFD SP!,{R6} LDMFD SP!,{R0} LDMFD SP!,{R1} LDMFD SP!,{R2} stop: b stop .ltorg src: .long 1,2,3,4,5,6,7 .end 问：该程序完成了什么功能？ 答： 该程序完成的功能：先把数据区堆栈中的1~7这七个数据送给R0~R0寄存器，然后又把寄存器列表中的R0~R7存入堆栈，然后又依次把堆栈中的1~7这七个数送给R3~R6,R0~R2,然后程序就结束了，在取数和存数的过程中。堆栈指针sp由0x0000变到0x8030再到0x804c，然后到0x8030，然后依次加4，最后到0x804c；程序计数器R15（PC）由0x8000地址依次加4 。 二、LDMFD,STMFD伪代码实现的原理。 答： 指令STMFD和LDMFD分析： 根据ATPCS规则，我们一般使用FD（Full Descending）类型的数据栈！所以经常使用的指令就有STMFD和LDMFD， 通过ARM对于栈操作和批量Load/Store指令寻址方式，可以知道指令STMFD和LDMFD 的地址计算方法： STMFD指令的寻址方式为事后递减方式(DB) 而DB寻址方式实际存地址为： start_address = Rn - (Number_Of_Set_Bits_In(register_list)*4) end_address = Rn - 4 STM指令操作的伪代码： if ConditionPassed(cond) then address = start_address for i = 0 to 15 if register_list[i] == 1 Memory[address] = Ri address = address + 4 有上面两个伪代码可以得出STMFD SP！，{R0-R7，LR} 的伪代码如下：SP ＝SP －9×4； address =SP; for i = 0 to 7 Memory[address] = Ri; address= address + 4; Memory[address] = LR; LDMFD指令的寻址方式为事后递增方式(IA) IA存的实际地址的伪代码 start_address = Rn end_address = Rn + (Number_of_set_bits_in(register_list)*4) - 4 LDM指令操作的伪代码(未考虑PC寄存器)： if ConditionPassed(cond) then address = start_address for i = 0 to 15 if register_list[i] == 1 Ri ＝Memory[address,4] address = address + 4 所以LDMFD SP！，{R0-R7，PC}^ （；恢复现场，异常处理返回）伪代码是: address = SP; for i = 0 to 7 Ri = Memory[address ,4] address = address + 4; SP = address; 作业2 一、用移位操作完成（R0）*10运算。 参考程序： .text .global _start 用分治法求解棋盘覆盖问题 棋盘覆盖问题 问题描述： 在一个2k ×2k （k ≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中出现的位置有4k 中情形，因而有4k 中不同的棋盘，图（a ）所示是k=2时 16种棋盘中的一 个。棋盘覆盖问题 要求用图（b ）所示的4中不同形状的L 型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且热河亮哥L 型骨牌不得重复覆盖。 问题分析： K>0时，可将2k ×2k 的棋盘划分为4个2k-1×2k-1的子棋盘。这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有1个子 图（b ） 图 （a ） 棋盘中有特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化成为特殊棋盘，以便采用递归方法求解，可以用一个L型骨牌覆盖这3个较小的棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为1×1的子棋盘。 问题求解： 下面介绍棋盘覆盖问题中数据结构的设计。 （1）棋盘：可以用一个二维数组board[size][size]表示一个棋盘，其中 size=2k。为了在递归处理的过程中使用同 一个棋盘，将数组board设为全局变量。 （2）子棋盘：整个棋盘用二维数组board[size][size]表示，其中的子棋盘 由棋盘左上角的下标tr、tc和棋盘大小s 表示。 （3）特殊方格：用board[dr][dc]表示特殊方格，dr和dc是该特殊方格在二维数组 board中的下标。 （4）L型骨牌：一个2k×2k的棋盘中有一个特殊方格，所以，用到L型骨牌的个数为 TCP/IP通信程序之伪代码 UDP发送程序如下： 1.用WSAStartup函数初始化Socket环境； 2.用socket函数创建一个套接字； 3.用setsockopt函数设置套接字的属性，例如设置为广播类型；很多时候该步骤可以省略； 4.创建一个sockaddr_in，并指定其IP地址和端口号； 5.用sendto函数向指定地址发送数据，这里的目标地址就是广播地址；注意这里不需要绑定，即使绑定了，其地址也会被sendto中的参数覆盖；若使用send函数则会出错，因为send是面向连接的，而UDP 是非连接的，只能使用sendto发送数据； 6.用closesocket函数关闭套接字； 7.用WSACleanup函数关闭Socket环境。 UDP接收程序如下，注意接收方一定要bind套接字： 1.用WSAStartup函数初始化Socket环境； 2.用socket函数创建一个套接字； 3.用setsockopt函数设置套接字的属性，例如设置为广播类型； 4.创建一个sockaddr_in，并指定其IP地址和端口号； 5.用bind函数将套接字与接收的地址绑定起来，然后调用recvfrom 函数或者recv接收数据；注意这里一定要绑定，因为接收报文的套接字必须在网络上有一个绑定的名称才能保证正确接收数据； 6.用closesocket函数关闭套接字； 7.用WSACleanup函数关闭Socket环境。 TCP服务器程序： 1.用socket函数创建一个套接字sock； 2.用bind将sock绑定到本地地址； 3.用listen侦听sock套接字； 4.用accept函数接收客户方的连接，返回客户方套接字clientSocket； 5.在客户方套接字clientSocket上使用send发送数据； 6.用closesocket函数关闭套接字sock和clientSocket； 客服端程序如下： 1.用socket函数创建一个套接字sock； 2.创建一个指向服务方的远程地址； 3.用connect将sock连接到服务方，使用远程地址； 4.在套接字上使用recv接收数据； 5.用closesocket函数关闭套接字sock； 棋盘覆盖问题 问题描述： 在一个2k ×2k （k ≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中出现的位置有4k 中情形，因而有4k 中不同的棋盘，图（a ）所示是k=2时16种棋盘中的一个。棋盘覆盖问题要求用图（b ）所示的4中不同形状的L 型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且热河亮哥L 型骨牌不得重复覆盖。 问题分析： K>0时，可将2k ×2k 的棋盘划分为4个2k-1×2k-1的子棋盘。这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有1个子棋盘中有特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化成为特殊棋盘，以便采用递归方法求解，可以用一个L 型骨牌覆盖这3个较小的棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为1×1的子棋盘。 问题求解： 下面介绍棋盘覆盖问题中数据结构的设计。 （1） 棋盘：可以用一个二维数组board[size][size]表示一个棋盘，其中size=2k 。为了 在递归处理的过程中使用同一个棋盘，将数组board 设为全局变量。 （2） 子棋盘：整个棋盘用二维数组board[size][size]表示，其中的子棋盘由棋盘左上 角的下标tr 、tc 和棋盘大小s 表示。 （3） 特殊方格：用board[dr][dc]表示特殊方格，dr 和dc 是该特殊方格在二维数组 board 中的下标。 （4） L 型骨牌：一个2k ×2k 的棋盘中有一个特殊方格，所以，用到L 型骨牌的个数 为（4k -1）/3，将所有L 型骨牌从1开始连续编号，用一个全局变量tile 表示。 图（b ） 图 （a ） 学术论文书写模板与规范1 学术论文书写模板与规范1 王志海 (北京交通大学计算机与信息技术学院，北京，100044) 摘要：本文主要叙述了书写学术论文的基本规范，包括翻译学术论文的要求，以及 使用Microsoft Office Word 2003在Microsoft Windows XP之下制定的Word模版文 件．主要目的时指导研究生书写规范的学术论文． 关键字：学术论文，研究生；模板；翻译 为了使研究生在科学研究过程中书写统一规范的学术论文或翻译论文，本文规定了在Microsoft Windows XP之下采用Microsoft Office Word 2003进行书写的文档格式．这些规定充分考虑了各种中英论文在书写方面的各种规范或标准(包括中国国家标准，例如GB7714 -87等)．然而，由于不同的规范或标准在同一个问题上的规定可能不尽相同，我们不得不在各种规范或标准之间进行取舍．取舍标准主要有两个原则：一是尽可能方便地转化为大多出版机构所要求的格式，例如学校所要求的研究生学位论文格式；二是尽可能方便老师的修改或评述．要求大家务必遵守本文所规定的标准． 1 引言 我们现在使用的Word模版的名字是A4Paper1A.dot或A4Paper1B.dot，两者并没有根本的区别，建议你使用A4Paper1A.dot．当你认为必须改变或增加任何Word样式时，请你自己建立一个新Word模版文件（其后缀为.dot）并命名为A4Paper1B.dot．所有Microsoft Office 的模版文件（当然包括PowerPoint，Access等）一般都是存放在C:\Documents and Settings\＜用户名＞\Application Data\Microsoft\Templates文件夹之中的，例如我的计算机上存放Microsoft Office的模版文件的文件夹为：C:\Documents and Settings\Zhihai Wang\Application Data\Microsoft\Templates．在该模版命名中，“A4”表示“页面设置”中“纸张”采用标准的A4纸（210mm×297mm）；“Paper”表示主要适用于“学术论文”；“1”表示“学术论文”这类模版的顺序编号，其他编号的模版大多是某一出版机构制定的特定形式；最后的“A”或“B”就是这一模版的版本号． 模版A4Paper1A.dot在Microsoft Office Word 2003中的“文件”下拉菜单的“页面设置”选项之下包括如下4方面的设置： z页边距：页边距上下各25.4mm，左右各31.7mm，都没有修改； 1本文仅供研究生学习使用． 河南理工大学计算机学院算法分析解题报告 棋盘覆盖问题 专业：软件工程.net11-03班 学号：311109070314 姓名：李少伟 1.问题描述： 在一个2^k×2^k （k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有4^k种，因而有4k种不同的棋盘，下图所示是k=2时16种棋盘中的一个。棋盘覆盖问题（chess cover problem）要求用下图所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 2.解题思路 关键技术: 分治与递归 分治的技巧在于如何划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格(这句话很重要)，从而将原问题分解为规模较小的棋盘覆盖问题。先把原始棋盘划分成4个相等的棋盘，由于棋盘只有一个特殊棋盘，所以这4个子棋盘中只有一个子棋盘包含该特殊棋盘，以便采用递归的方法求解，可以用1一个L型骨牌覆盖这3个较小棋盘的汇合处。从而将原问题转换为4个较小规模的棋盘覆盖问题。递归使用这种划分策略，直至将棋盘分割为1*1的子棋盘。 3.解决方案 数据结构设计： （1）棋盘：可以一个二维数组board[size][size]表示一个棋盘，其中，size = 2^k。为了在递归处理的过程中使用同一个棋盘，将数组board设置为全局变量 （2）子棋盘：子棋盘由原始棋盘数组board的行下标tr，列下标tc 表示。 （3）特殊方格：用board[dr][dc]表示特殊方格，dr和dc表示该特殊方格的在二维数组board中的下标 （4）L型骨牌：一个（2^k）*（2^k）的棋盘中有一个特殊方格，所以用到L型骨牌的个数为（4^k - 1）/3，将所有L型骨牌从1开始连续编号，同一个骨牌有3个方格组成，这3个方格用同一个编号。 4.源代码 //问题描述：在一个2^k×2^k （k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有4^k种，因而有4k种不同的棋盘，图4.10(a)所示是k=2时16种棋盘中的一个。棋盘覆盖问题（chess cover problem）要求用下图所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠 伪代码的使用Usage of Pseudocode 伪代码(Pseudocode)是一种算法描述语言。使用为代码的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal, C, Java, etc)实现。因此，伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。 下面介绍一种类Pascal语言的伪代码的语法规则。 伪代码的语法规则 在伪代码中，每一条指令占一行(else if 例外，)，指令后不跟任何符号（Pascal和C中语句要以分号结尾）； 书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性；同一模块的语句有相同的缩进量，次一级模块的语句相对与其父级模块的语句缩进； 例如： line 1 line 2 sub line 1 sub line 2 sub sub line 1 sub sub line 2 sub line 3 line 3 而在Pascal中这种关系用begin和end的嵌套来表示， line 1 line 2 begin sub line 1 sub line 2 begin sub sub line 1 sub sub line 2 end; sub line 3 end; line 3 在C中这种关系用{ 和} 的嵌套来表示， line 1 line 2 { sub line 2 { sub sub line 1 sub sub line 2 } sub line 3 } line 3 在伪代码中，通常用连续的数字或字母来标示同一即模块中的连续语句，有时也可省略标号。 例如： 1. line 1 2. line 2 a. sub line 1 b. sub line 2 1. sub sub line 1 2. sub sub line 2 c. sub line 3 3. line 3 符号△后的内容表示注释； 在伪代码中，变量名和保留字不区分大小写，这一点和Pascal相同，与C或C++不同； 在伪代码中，变量不需声明，但变量局部于特定过程，不能不加显示的说明就使用全局变量；赋值语句用符号←表示，x←exp表示将exp的值赋给x，其中x是一个变量，exp是一个与x同类型的变量或表达式（该表达式的结果与x同类型）；多重赋值i←j←e是将表达式e的值赋给变量i和j，这种表示与j←e和i←e等价。 例如： x←y x←20*(y+1) x←y←30 以上语句用Pascal分别表示为： x := y; x := 20*(y+1); x := 30; y := 30; 以上语句用C分别表示为： x = y; x = 20*(y+1);word完整版小学六年级奥数教案15棋盘的覆盖
伪代码
棋盘覆盖算法C#
棋盘覆盖实验报告
项目开发详细设计说明书(超好用实用模板),完整版
实验二 动态规划算法棋盘覆盖
小学六年级奥数★棋盘的覆盖
项目编码规范
棋盘覆盖算法
软件开发过程文档规范
棋盘覆盖问题 分治法c(带截图)
嵌入式系统原理及应用题目要求+程序代码
用分治法求解棋盘覆盖问题
TCP伪代码
用分治法求解棋盘覆盖问题
学术论文书写模板与规范
算法分析解题报告--棋盘问题
伪代码的使用规范 Usage of Pseudocode
相关主题
文本预览