算法设计与分析实验报告棋盘覆盖问题1

贵州大学计算机科学与技术学院

计算机科学与技术系上机实验报告

课程名称：算法设计与分析班级：信计101班实验日期：2013-9-30

姓名：张胜学号：1007010162 指导教师：程欣宇

实验序号：一实验成绩：

一、实验名称

分治算法实验- 棋盘覆盖问题

二、实验目的及要求

1、熟悉递归算法编写；

2、理解分治算法的特点；

3、掌握分治算法的基本结构。

三、实验环境

Visual C++

四、实验内容

根据教材上分析的棋盘覆盖问题的求解思路，进行验证性实验；

要求完成棋盘覆盖问题的输入、分治求解、输出。有余力的同学尝试消去递归求解。

五、算法描述及实验步骤

分治算法原理：

分治算法将大的分解成形状结构相同的子问题，并且不断递归地分解，直到子问题规模小到可以直接求解。

棋盘覆盖问题描述：

在一个2k x 2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方格，想要求利用四种L型骨牌（每个骨牌可覆盖三个方格）不相互重叠覆盖的将除了特殊方格外的其他方格覆盖。

实验步骤：

1、定义用于输入和输出的数据结构；

2、完成分治算法的编写；

3、测试记录结构；

4、有余力的同学尝试不改变输入输出结构，将递归消除，并说明能否不用栈，直接消除递归，为什么？

六、调试过程及实验结果

实验运行结果：

七、总结

通过本次实验，我更深的理解了递归和分治策略。代码是书上的算法，加上主函数就行了，用的是C语言编写，很长时间没用了，感觉有点生疏。实验结果有点问题，就是覆盖棋盘时，并不是按照1，2，3….的字符顺序，而是按照很乱的顺序输出字符，这个我不知道怎么解决，就没解决。

八、附录

#include "stdio.h"

#include "conio.h"

int board[8][8] ={

{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0

,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0}

};

int tile=0;

void chessBoard(int tr, int tc, int dr, int dc, int size)

{

int t=tile++,

s=size/2;

if (size==1) return;

if (dr

chessBoard(tr,tc,dr,dc,s);

else {

board[tr+s-1][tc+s-1]=t;

chessBoard(tr,tc,tr+s-1,tc+s-1,s);}

if(dr = tc+s)

chessBoard(tr,tc+s,dr,dc,s);

else {

board[tr+s-1][tc+s]=t;

chessBoard(tr,tc+s,tr+s-1,tc+s,s);}

if(dr >= tr+s&&dc

chessBoard(tr+s,tc,dr, dc,s);

else {

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 {

board[tr+s][tc+s]=t;

chessBoard(tr+s,tc+s,tr+s,tc+s,s);} }

main()

{

int i ,j;

chessBoard(0,0,5,5,8);

for(i=0;i <8;i++)

{

for( j=0;j <8;j++) {

if(board[i][j]<10)

printf("0");

printf("%d",board[i][j]);

printf(" ");

}

printf( "\n");

}

getchar();

}

word完整版小学六年级奥数教案15棋盘的覆盖

小学六年级奥数教案一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个白格。

实验报告 马踏棋盘

2.4题马踏棋盘 题目：设计一个国际象棋的马踏棋盘的演示程序 班级：姓名：学号：完成日期： 一．需求分析 （1）输入的形式和输入值的范围：输入马的初始行坐标X和列坐标Y， X和Y的范围都是[1,8]。 （2）输出形式： 以数组下表的形式输入，i为行标，j为列标，用空格符号隔开。以棋盘形式输出，每一格打印马走的步数，这种方式比较直观 （3）程序所能达到的功能：让马从任意起点出发都能够遍历整个8*8的 棋盘。 （4）测试数据，包括正确输入及输出结果和含有错误的输入及其输出结 果。数据可以任定，只要1<=x,y<=8就可以了。 正确的输出结果为一个二维数组，每个元素的值表示马行走的第几步，若输入有错，则程序会显示：“输入有误！请重新输入……”并且要求用户重新输入数据，直至输入正确为止。 二．概要设计 （1）、位置的存储表示方式 （2） typedef struct { int x; int y; int from; }Point; （2）、栈的存储方式 #define STACKSIZE 70 #define STACKINCREASE 10 typedef struct Stack { Point *top; Point *base; int stacksize; }; （1）、设定栈的抽象数据类型定义： ADT Stack { 数据对象：D=｛ai | ai∈ElemSet,i=1,2,…,n,n≥0｝ 数据关系：R1={|ai-1, ai∈D,i=2,…,n} 约定an端为栈顶，ai端为栈顶。 基本操作： InitStack(&s) 操作结果：构造一个空栈s， DestroyStack(&s) 初始条件：栈s已存在。 操作结果：栈s被销毁。 ClearStack(&s) 初始条件：栈s已存在。

数字逻辑个性课实验报告

学生学号0121410870432实验成绩 学生实验报告书 实验课程名称逻辑与计算机设计基础 开课学院计算机科学与技术学院 指导教师姓名肖敏 学生姓名付天纯 学生专业班级物联网1403 2015--2016学年第一学期

译码器的设计与实现 【实验要求】： （1）理解译码器的工作原理，设计并实现n-2n译码器，要求能够正确地根据输入信号译码成输出信号。（2）要求实现2-4译码器、3-8译码器、4-16译码器、8-28译码器、16-216译码器、32-232译码器。 【实验目的】 （1）掌握译码器的工作原理； （2）掌握n-2n译码器的实现。 【实验环境】 ◆Basys3 FPGA开发板，69套。 ◆Vivado2014 集成开发环境。 ◆Verilog编程语言。 【实验步骤】 一·功能描述 输入由五个拨码开关控制，利用led灯输出32种显示 二·真值表

三·电路图和表达式

四·源代码 module decoder_5( input [4:0] a, output [15:0] d0 ); reg [15:0] d0; reg [15:0] d1; always @(a) begin case(a) 5'b00000 :{d1,d0}=32'b1000_0000_0000_0000_0000_0000_0000_0000; 5'b00001 :{d1,d0}=32'b0100_0000_0000_0000_0000_0000_0000_0000; 5'b00010 :{d1,d0}=32'b0010_0000_0000_0000_0000_0000_0000_0000; 5'b00011 :{d1,d0}=32'b0001_0000_0000_0000_0000_0000_0000_0000; 5'b00100 :{d1,d0}=32'b0000_1000_0000_0000_0000_0000_0000_0000; 5'b00101 :{d1,d0}=32'b0000_0100_0000_0000_0000_0000_0000_0000; 5'b00110 :{d1,d0}=32'b0000_0010_0000_0000_0000_0000_0000_0000; 5'b00111 :{d1,d0}=32'b0000_0001_0000_0000_0000_0000_0000_0000; 5'b01000 :{d1,d0}=32'b0000_0000_1000_0000_0000_0000_0000_0000; 5'b01001 :{d1,d0}=32'b0000_0000_0100_0000_0000_0000_0000_0000; 5'b01010 :{d1,d0}=32'b0000_0000_0010_0000_0000_0000_0000_0000; 5'b01011 :{d1,d0}=32'b0000_0000_0001_0000_0000_0000_0000_0000; 5'b01100 :{d1,d0}=32'b0000_0000_0000_1000_0000_0000_0000_0000; 5'b01101 :{d1,d0}=32'b0000_0000_0000_0100_0000_0000_0000_0000; 5'b01110 :{d1,d0}=32'b0000_0000_0000_0010_0000_0000_0000_0000; 5'b01111 :{d1,d0}=32'b0000_0000_0000_0001_0000_0000_0000_0000; 5'b10000 :{d1,d0}=32'b0000_0000_0000_0000_1000_0000_0000_0000; 5'b10001 :{d1,d0}=32'b0000_0000_0000_0000_0100_0000_0000_0000; 5'b10010 :{d1,d0}=32'b0000_0000_0000_0000_0010_0000_0000_0000; 5'b10011 :{d1,d0}=32'b0000_0000_0000_0000_0001_0000_0000_0000; 5'b10100 :{d1,d0}=32'b0000_0000_0000_0000_0000_1000_0000_0000; 5'b10101 :{d1,d0}=32'b0000_0000_0000_0000_0000_0100_0000_0000; 5'b10110 :{d1,d0}=32'b0000_0000_0000_0000_0000_0010_0000_0000; 5'b10111 :{d1,d0}=32'b0000_0000_0000_0000_0000_0001_0000_0000; 5'b11000 :{d1,d0}=32'b0000_0000_0000_0000_0000_0000_1000_0000; 5'b11001 :{d1,d0}=32'b0000_0000_0000_0000_0000_0000_0100_0000; 5'b11010 :{d1,d0}=32'b0000_0000_0000_0000_0000_0000_0010_0000;

棋盘覆盖实验报告

算法设计与分析实验报告 专业： 学号： 姓名： 指导老师：

实验一：棋盘覆盖 一、实验目的与要求 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);

马踏棋盘实验报告

西安郵電學院 数据结构 课内实验报告书 院系名称：计算机学院 实验题目：马踏棋盘 学生姓名： 专业名称：计算机科学与技术班级： 学号： 时间： 2011年10月10日指导教师：曾艳

一、实验题目：马踏棋盘 二、实验目的： 通过本次实验，熟练掌握抽象数据类型栈和队列的实现，学会使用栈和队列解决具体应用问题，从而体会栈和队列的特点。 三、实验要求： 设计一个国际象棋的马踏遍棋盘的演示程序。 要求：将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之 四、设计与实现过程 （1）栈或队列的定义及其主要操作的实现 struct Chess { int x; int y; int h;/*h记录下一次需要试探的马字格式的下标值*/ }Chess1[65]; （2）主要算法的描述 void Handlechess(int m,int n) { int flag=1,i; double j=0.0;/*增加了j用于统计while循环的执行次数，很好奇循环到底执行了多少次*/ int chessx[8]={-2,-2,-1,-1,1,1,2,2};/*马字的格式的8个位置，按下标序依次试探*/ int chessy[8]={-1,1,-2,2,-2,2,-1,1}; for(i=1;i<=64;i++) Chess1[i].h=0;/*赋初值*/ chess[m][n]=flag; Chess1[flag].x=m; Chess1[flag].y=n; while(flag<64) { j+=1.0; for(i=Chess1[flag].h;i<8;i++)/*i的初值由Chess1[flag].h确定*/ { m=Chess1[flag].x+chessx[i]; n=Chess1[flag].y+chessy[i]; if((m>=0&&m<=7&&n>=0&&n<=7)&&(chess[m][n]==0))/*去掉了函数，改为直接用关系表达式判断，提高运行速度*/ { Chess1[flag].h=i+1;/*h记录下一次需试探马字格式位置的下标*/ flag++;

华中科技大学计算机学院数字逻辑实验报告2(共四次)

数字逻辑实验报告（2） 姓名： 学号： 班级： 指导教师： 计算机科学与技术学院 20 年月日

数字逻辑实验报告（2）无符号数的乘法器设计

一、无符号数的乘法器设计 1、实验名称 无符号数的乘法器的设计。 2、实验目的 要求使用合适的逻辑电路的设计方法，通过工具软件logisim进行无符号数的乘法器的设计和验证，记录实验结果，验证设计是否达到要求。 通过无符号数的乘法器的设计、仿真、验证3个训练过程，使同学们掌握数字逻辑电路的设计、仿真、调试的方法。 3、实验所用设备 Logisim2.7.1软件一套。 4、实验内容 （1）四位乘法器设计 四位乘法器Mul4 4实现两个无符号的4位二进制数的乘法运算，其结构框图如图3-1所示。设被乘数为b(3:0)，乘数为a(3:0)，乘积需要8位二进制数表示，乘积为p(7:0)。 图3-1 四位乘法器结构框图 四位乘法器运算可以用4个相同的模块串接而成，其内部结构如图3-2所示。每个模块均包含一个加法器、一个2选1多路选择器和一个移位器shl。 图3-2中数据通路上的数据位宽都为8，确保两个4位二进制数的乘积不会发生溢出。shl是左移一位的操作，在这里可以不用逻辑器件来实现，而仅通过数据连线的改变（两个分线器错位相连接）就可实现。

a(0)a(1)a(2)a(3) 图3-2 四位乘法器内部结构 （2）32 4乘法器设计 32 4乘法器Mul32 4实现一个无符号的32位二进制数和一个无符号的4位二进制数的乘法运算，其结构框图如图3-3所示。设被乘数为b(31:0)，乘数为a(3:0)，乘积也用32位二进制数表示，乘积为p(31:0)。这里，要求乘积p能用32位二进制数表示，且不会发生溢出。 图3-3 32 4乘法器结构框图 在四位乘法器Mul4 4上进行改进，将数据通路上的数据位宽都改为32位，即可实现Mul32 4。 （3）32 32乘法器设计 32 32乘法器Mul32 32实现两个无符号的32位二进制数的乘法运算，其结构框图如图3-4所示。设被乘数为b(31:0)，乘数为a(31:0)，乘积也用32位二进制数表示，乘积为p(31:0)。这里，要求乘积p能用32位二进制数表示，且不会发生溢出。 图3-4 32 32乘法器结构框图 用32 4乘法器Mul32 4作为基本部件，实现32 32乘法器Mul32 32。 设被乘数为b(31:0)=(b31b30b29b28···b15b14b13b12···b4b3b2b1b0)2 乘数为a(31:0)=(a31a30a29a28···a15a14a13a12···a3a2a1a0)2 =(a31a30a29a28)2 228+···+ ( a15a14a13a12)2 212+···+ (a3a2a1a0)2 20

算法实验报告

贵州大学计算机科学与技术学院 计算机科学与技术系上机实验报告 课程名称：算法设计与分析班级：软件101 实验日期：2012-10-23 姓名：学号：指导教师： 实验序号：一实验成绩： 一、实验名称 分治算法实验- 棋盘覆盖问题 二、实验目的及要求 1、熟悉递归算法编写； 2、理解分治算法的特点； 3、掌握分治算法的基本结构。 三、实验环境 Visual C++ 四、实验内容 根据教材上分析的棋盘覆盖问题的求解思路，进行验证性实验； 要求完成棋盘覆盖问题的输入、分治求解、输出。有余力的同学尝试消去递归求解。 五、算法描述及实验步骤 分治算法原理： 分治算法将大的分解成形状结构相同的子问题，并且不断递归地分解，直到子问题规模小到可以直接求解。 棋盘覆盖问题描述： 在一个2k x 2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方格，想要求利用四种L型骨牌（每个骨牌可覆盖三个方格）不相互重叠覆盖的将除了特殊方格外的其他方格覆盖。

实验步骤： 1、定义用于输入和输出的数据结构； 2、完成分治算法的编写； 3、测试记录结构； 4、有余力的同学尝试不改变输入输出结构，将递归消除，并说明能否不用栈，直接消除递归，为什么？ 六、调试过程及实验结果 详细记录程序在调试过程中出现的问题及解决方法。 记录程序执行的结果。

七、总结 对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。 通过对本实验的学习，对分治算法有了进一步的认识，对棋盘覆盖问题和其他分治问题进行了对比。 八、附录 源程序（核心代码）清单或使用说明书，可另附纸 ① #include #include using namespace std; int board[100][100],tile=1; void chessboard(int tr,int tc,int dr,int dc,int size)//tr 棋盘左上角方格的行号，tc棋盘左上角方格的列号。dr特殊方格所在的行号。dc特殊方格所在的列号。size棋盘的大小2^k. { int s; if(size==1) return ; int t=tile++; s=size/2; //覆盖左上角棋盘 if(dr=tc+s) chessboard(tr,tc+s,dr,dc,s); else { board[tr+s-1][tc+s]=t; chessboard(tr,tc+s,tr+s-1,tc+s,s); } ② //覆盖左下角子棋盘 if(dr>=tr+s&&dc=tr+s&&dc>=tc+s) chessboard(tr+s,tc+s,dr,dc,s); else { board[tr+s][tc+s]=t; chessboard(tr+s,tc+s,tr+s,tc+s,s); } } int main() { int k,tr,tc,size,i,j; cin>>k>>tr>>tc; size=pow(2,k); chessboard(0,0,tr,tc,size); for(i=0;i

马踏棋盘数据结构实践报告

马踏棋盘问题 摘要： 马踏棋盘就是在国际象棋8X8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。理解栈的“后进先出”的特性以及学会使用回溯。 关键字：马踏棋盘、递归、栈、回溯 1．引言 马踏棋盘就是在国际象棋8X8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。 编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2….64依次填入一个8X8的方阵，并输出它的行走路线。输入：任意一个起始位置；输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。 2．需求分析 （1）需要输出一个8X8的棋盘，可以采用二维数组的方法实现。 （2）输入马的起始位置，必须保证输入的数字在规定范围内，即0<=X<=7,0<=Y<=7。 （3）保证马能走遍整个棋盘，并且不重复。

（4）在棋盘上输出马的行走路线,标记好数字1、2、3直到64。 3．数据结构设计 采用栈数组为存储结构。 #define maxsize 100 struct { int i; int j; int director; }stack[maxsize]; 4．算法设计 4.1 马的起始坐标 void location(int x,int y) //马的位置坐标的初始化 { top++; stack[top].i=x; //起始位置的横坐标进栈 stack[top].j=y; //起始位置的竖坐标进栈 stack[top].director=-1;

a[x][y]=top+1; //标记棋盘Try(x,y); //探寻的马的行走路线 } 4.2 路径探寻函数 void Try(int i,int j) { int count,find,min,director; int i1,j1,h,k,s; int b[8]={-2,-2,-1,1,2,2,1,-1},c[8]={1,-1,-2,-2,-1,1,2,2} ; //存储马各个出口相对当前位置行、列坐标的增量数组 int b2[8],b1[8]; for(h=0;h<=7;h++) //用数组b1[8]记录当前位置的下一个位置的可行路径的条数 { count=0; i=stack[top].i+c[h]; j=stack[top].j+b[h]; if(i>=0&&i<=7&&j>=0&&j<=7&&a[i][j]==0) //如果找到下一个位置 { for(k=0;k<=7;k++) { i1=i+c[k]; j1=j+b[k]; if(i1>=0&&i1<=7&&j1>=0&&j1<=7&&a[i1]

数字逻辑实验报告

. 武汉理工大学

2017 年月日 实验一：一位全加器 实验目的： 1. 掌握组合逻辑电路的设计方法； 2. 熟悉Vivado2014 集成开发环境和Verilog 编程语言； 3. 掌握1 位全加器电路的设计与实现。 试验工具： 1.Basys3 FPGA 开发板 2.Vivado2014 集成开发环境和Verilog 编程语言。 实验原理： Ci+A+B={Co，S} 全加器真表

全加器逻辑表达式 S=A○+B○+Ci Co=A.B+ (A○+B).Ci 全加器电路图 实验步骤： (一)新建工程： 1、打开 Vivado 2014.2 开发工具，可通过桌面快捷方式或开始菜单中 Xilinx Design Tools->Vivado 2014.2 下的 Vivado 2014.2 打开软件； 2、单击上述界面中 Create New Project 图标，弹出新建工程向导。 3、输入工程名称、选择工程存储路径，并勾选Create project subdirectory选项，为工程在指 定存储路径下建立独立的文件夹。设置完成后，点击Next。注意：工程名称和存储路径中不能出现中文和空格，建议工程名称以字母、数字、下划线来组成 4、选择RTL Project一项，并勾选Do not specify sources at this time，为了跳过在新建工 程的过程中添加设计源文件。 5、根据使用的FPGA开发平台，选择对应的FPGA目标器件。（在本手册中，以Xilinx大学计 划开发板Digilent Basys3 为例，FPGA 采用Artix-7 XC7A35T-1CPG236-C 的器件，即Family 和Subfamily 均为Artix-7，封装形式（Package）为CPG236，速度等级（Speed grade）为-1，温度等级（Temp Grade）为C）。点击Next。 6、确认相关信息与设计所用的的FPGA 器件信息是否一致，一致请点击Finish，不一致，请返 回上一步修改。 7、得到如下的空白Vivado 工程界面，完成空白工程新建。

计算机算法设计与分析

算法设计与分析 实 验 报 告 班级： 姓名： 学号： (备注：共给出5个参考实验案例，根据学号尾数做对应的实验，即如尾号为1，则模仿案例实验123；尾号2，则模仿案例实验234；尾号3，即345；尾号4，同1.)

目录 实验一分治与递归 (1) 1、基本递归算法 (1) 2、棋盘覆盖问题 (2) 3、二分搜索 (3) 4、实验小结 (5) 实验二动态规划算法 (5) 1、最长公共子序列问题 (5) 2、最大子段和问题 (7) 3、实验小结 (8) 实验三贪心算法 (8) 1、多机调度问题 (8) 2、用贪心算法求解最小生成树 (10) 3、实验小结 (12) 实验四回溯算法和分支限界法 (12) 1、符号三角形问题 (12) 2、0—1背包问题 (14) 3、实验小结 (18) 实验五多种排序算法效率比较 1、算法：起泡排序、选择排序、插入排序、shell排序，归并排序、快速排序等 (19) 2、实验小结 (18)

P art1：课程设计过程 设计选题--→题目分析---→系统设计--→系统实现--→结果分析---→撰写报告 P art2：课程设计撰写的主要规范 1.题目分析：主要阐述学生对题目的分析结果，包括题目描述、 分析得出的有关模型、相关定义及假设； 2.总体设计：系统的基本组成部分，各部分所完成的功能及相互 关系； 3.数据结构设计：主要功能模块所需的数据结构，集中在逻辑设 计上； 4.算法设计：在数据结构基础上，完成算法设计； 5.物理实现：主要有数据结构的物理存储，算法的物理实现，系 统相关的实现。具体在重要结果的截图，测试案例的结果数据，核心算法的实现结果等； 6.结果分析：对第五步的分析，包括定性分析和定量分析，正确 性分析，功能结构分析，复杂性分析等； 7.结论：学生需对自己的课程设计进行总结，给出评价，并写出 设计体会； 8.附录：带有注释的源代码，系统使用说明等； 9.参考文献：列出在撰写过程中所需要用到的参考文献。

马踏棋盘分析文档

数据结构课程设计 题目：马踏棋盘 院系： 班级： 学号： 姓名： 2014-2015年度第1学期

马踏棋盘 一．题目：马踏棋盘 (3) 二. 设计目标 (3) 三. 问题描述 (3) 四. 需求分析 (4) 五. 概要设计 (4) 第一步：定义四个常量和一个数据类型 (4) 第二步：构造函数 (4) 六. 详细设计（给出算法的伪码描述和流程图） (5) 流程图设计 (5) 代码分析 (9) 第一步：定义常量与变量 (9) 第二步：构造函数 (9) ●定义一个结构体类型 (9) ●创建一个初始化函数 (10) ●创建提示输入函数 (10) ●创建产生新节点函数 (11) ●创建计算路径函数 (12) ●创建入栈函数 (13) ●创建出栈函数 (13) ●创建输出函数 (13)

第三步：在主函数中调用其它函数 (15) 七. 测试分析 (16) 八. 使用说明 (16) 九. 测试数据 (16) 十．课程设计总结 (17) 一．题目：马踏棋盘 二. 设计目标 帮助学生熟练掌握顺序栈的基本操作，让学生深入了解栈的使 用，使得更深层次的灵活运用栈。 三. 问题描述 ○所谓的马踏棋盘是：将马随机放在国际象棋的8×8棋盘的某个方格中，马按走棋规则（马走日字）进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。由用户自行指定一个马的初始位置，求出马的行走路线，并按照求出的行走路线的顺序，将数字1、2、…、64依次填入一个8X8的方阵并输出。 从用户给出的初始位置开始判断，按照顺时针顺序，每次产生一个新的路点，并验证此路点的可用性，需要考虑的是当前路点是否超出棋盘范围和此路点是否已经走过。如果新路点可用，则入栈，并执行下一步，重复进行如上步骤，每次按照已走路点的位置生成新路点。如果一个路点的可扩展路数为0，进行回溯，直到找到一个马能踏遍棋盘的行走路线并输出。

数字逻辑实验报告。编码器

数字逻辑实验实验报告 脚分配、1）分析输入、输出，列出方程。根据方程和IP 核库判断需要使用的门电路以及个数。 2）创建新的工程，加载需要使用的IP 核。 3）创建BD 设计文件，添加你所需要的IP 核，进行端口设置和连线操作。 4）完成原理图设计后，生成顶层文件（Generate Output Products）和HDL 代码文件（Create HDL Wrapper）。 5）配置管脚约束（I/O PLANNING），为输入指定相应的拨码开关，为输出指定相应的led 灯显示。

6）综合、实现、生成bitstream。 7）仿真验证，依据真值表，在实验板验证试验结果。

实验报告说明 数字逻辑课程组 实验名称列入实验指导书相应的实验题目。 实验目的目的要明确，要抓住重点，可以从理论和实践两个方面考虑。可参考实验指导书的内容。在理论上，验证所学章节相关的真值表、逻辑表达式或逻辑图的实际应用，以使实验者获得深刻和系统的理解，在实践上，掌握使用软件平台及设计的技能技巧。一般需说明是验证型实验还是设计型实验，是创新型实验还是综合型实验。 实验环境实验用的软硬件环境（配置）。 实验内容（含电路原理图/Verilog程序、管脚分配、仿真结果等；扩展内容也列入本栏）这是实验报告极其重要的内容。这部分要写明经过哪几个步骤。可画出流程图，再配以相应的文字说明，这样既可以节省许多文字说明，又能使实验报告简明扼要，清楚明白。 实验结果分析数字逻辑的设计与实验结果的显示是否吻合，如出现异常，如何修正并得到正确的结果。 实验方案的缺陷及改进意见在实验过程中发现的问题，个人对问题的改进意见。 心得体会、问题讨论对本次实验的体会、思考和建议。

小学六年级奥数★棋盘的覆盖

棋盘的覆盖 同学们会下棋吗？下棋就要有棋盘，下面是中国象棋的棋盘（图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的正方形？

数据结构 马踏棋盘 设计报告

《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目： 姓名： 院系： 专业： 年级： 学号： 指导教师： 2011年月日

目录 1、程序设计的目的 2、设计题目 3、分析 4、设计思想 5、算法 6、测试结果 7、调试分析 8、小结 1、课程设计的目的 1、熟练使用C++语言编写程序，解决实际问题； 2、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 5、学习并熟悉栈的有关操作； 6、利用栈实现实际问题； 2、设计题目 【马踏棋盘】 *问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。 *测试数据：由读者指定,可自行指定一个马的初始位置。 *实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳

策略”，以减少回溯的次数。 3、分析 确定输入值的范围，输入马的初始行坐标X和Y，X和Y的范围都是1到8之间。程序的功能是输出马走的步骤，要使马从任一起点出发，通过程序能找到下一个地点，然后遍历整个棋盘。每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。输出时可以用二维数组。 4、设计思想 输入马初始位置的坐标。将初始位置进栈，经过一个while循环，取出符合条件的栈顶元素。利用函数，找出栈顶元素周围未被占用的新位置，如果有，新位置入栈；否则弹出栈顶元素。再进行判断，最后输出。 位置的存储方式，栈的存储方式和一些操作函数为： #include #ifndef STACK_H #define STACK_H struct Point { int x; int y; int from; }; #define STACKSIZE 70 #define STACKINCREASE 10 struct Stack { Point *top; Point *base; int length;

华中科技大学数字逻辑实验报告

华中科技大学数字逻辑实验报告 姓名: 专业班级: 学号: 指导老师： 完成时间：

实验一：组合逻辑电路的设计 一、实验目的： 1．掌握组合逻辑电路的功能测试。 2．验证半加器和全加器的逻辑功能 3．学会二进制的运算规律。 二、实验所用组件： 二输入四与门74LS08,二输入四与非门74LS00,二输入四异或门74LS86,六门反向器74LS04芯片，三输入三与非门74L10，电线若干。 三、实验内容： 内容A：全加全减器。 实验要求： 一位全加/全减法器，如图所示： 电路做加法还是做减法运算是由M决定的，当M=0做加法，M=1做减法。当作为全加法起时输入A.B和Cin分别为加数，被加数和低位来的进位，S和数，Co位向上位的进位。当作为全减法器时输入信号A,B和Cin分别为被减数，减数和低位来的借位，S为差，Co为向上的借位。 实验步骤： 1．根据功能写出输入/输出观察表：

2． 3．做出卡诺图，确定输出和激励的函数表达式：

4．根据逻辑表达式作出电路的平面图： 5．检查导线以及芯片是否完好无损坏，根据平面图和逻辑表达式连接电路。 实验结果： 电路连接好后，经检测成功实现了一位全加/全减法器的功能。 内容B：舍入与检测电路的设计： 试验要求： 用所给定的集合电路组件设计一个多输出逻辑电路，该电路的输入为8421码，F1为“四

舍五入”输出信号，F2为奇偶检测输出信号。当电路检测到输入的代码大宇或等于（5）10时，电路的输出F1=1；其他情况F1=0。当输入代码中含1的个数为奇数时，电路的输出F2=1，其他情况F2=0。该电路的框图如下所示： （1）按照所设计的电路图接线，注意将电路的输入端接试验台的开关，通过拨动开关输入8421代码，电路输入按至试验台显示灯。 （2）每输入一个代码后观察显示灯，并将结果记录在输入/输出观察表中。 实验步骤 1．按照所给定的实验要求填写出F1，F2理论上的真值表。 2．根据真值表给出F1和F2的卡诺图。

《算法分析与设计》实验指导书

《计算机算法设计与分析》实验指导书（第一版）

前言 计算机算法分析与设计是面向设计的，它是计算机科学的核心。无论是计算机系统、系统软件和解决计算机的各种应用问题都可归结为算法的设计。通过本课程的学习，使学生掌握计算机领域中许多常用的非数值的算法描述：分治法、贪心法、动态规划、回溯法、分枝限界等算法，并掌握算法分析的方法，从而把学生的分析问题和解决问题能力提高到理论的高度。 前期课程为程序设计语言、数据结构、高等数学，即学生应该具备一门高级语言程序设计编程基础，学习基本的数据结构知识，还要求学生掌握较好的数学基础。 开发环境不限，本书采用C/C++语言的集成开发环境等。 实验完成后书写实验报告，包含实验问题、基本思想、关键算法流程图、测试数据及运行结果（截图）、调试心得和源程序。 总实验学时为16学时。

目录 预备实验验证算法的方法 (4) 实验目的： (4) 实验课时： (4) 实验原理： (4) 实验题目： (6) 基本题： (6) 提高题： (6) 实验一递归与分治 (7) 实验目的： (7) 实验课时： (7) 实验原理： (7) 实验题目： (7) 基本题： (7) 提高题： (8) 思考问题： (8) 实验二动态规划算法 (9) 实验目的： (9) 实验课时： (9) 实验原理： (9) 实验题目： (9) 基本题： (9) 提高题： (10) 思考问题： (10) 实验三贪心选择算法 (11) 实验目的： (11) 实验课时： (11) 实验原理： (11) 实验题目： (11) 基本题： (11) 提高题： (12) 思考问题： (12) 实验四回溯算法 (13) 实验目的： (13) 实验课时： (13) 实验原理： (13) 实验题目： (14) 基本题： (14) 提高题： (14) 思考问题： (14)

棋盘覆盖算法

用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;

数字逻辑实验报告

数字逻辑实验报告：加法器

安徽师范大学 学院实验报告 专业名称软件工程 实验室 实验课程数字逻辑 实验名称加法器实验姓名 学号 同组人员 实验日期 2013.3.26

注：实验报告应包含（实验目的，实验原理，主要仪器设备和材料，实验过程 和步骤，实验原始数据记录和处理，实验结果和分析，成绩评定）等七项内容。具体内容可根据专业特点和实验性质略作调整，页面不够可附页。 实验目的：学会使用实验箱搭建基本组合逻辑电路。 实验原理：全加器是中规模组合逻辑器件，它实现二进制数码的加法运算，是计算机中最基本的运算单元电路。一位加法器有三个输入端Ａi 、B i 、C i -1,即被加数，有两个输出端S i 和B i 即相加及向高一位的进位输出。 (全加真值表) Si=A i B i C i -1+A i B i C i -1+A i B i C i -1+A i B i C i -1 C i =A i B i +A i C i -1+B i C i -1 全加器主要用于数值运算；另外，全加器还可以实现组合逻辑函数。 主要仪器设备和材料：数字逻辑电路实验装置、芯片 74LS32、芯片 74LS08、 芯片74LS86，导线 实验过程和步骤： ①关闭实验箱的电源开关，将三个芯片正确地安装在实验箱装置上； ②分别用三根导线将三个芯片的第14号引脚与实验箱左下角的+5V 连接起来，，再分别用三根导线将三个芯片的第7号引脚与实验箱左下角的GND 连接 Ａi B i C i -1 S i B i 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1