算法设计与分析实验4报告(优选.)

实验报告题目实验一递归与分治策略一、实验目的1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。

二、实验内容设计一个递归和分治算法，找出数组的最大元素，找出x在数组A中出现的次数。

三、实验要求（1）用分治法求解…问题；（2）再选择自己熟悉的其它方法求解本问题；（3）上机实现所设计的所有算法；四、实验过程设计（算法设计过程）1.设计一个递归算法，找出数组的最大元素。

2.设计一个分治算法，找出x在数组A中出现的次数。

3.写一个主函数，调用上述算法。

五、实验结果分析（分析时空复杂性，设计测试用例及测试结果）时间复杂性：最好情况下，O(n)最坏情况下：O(nlog(n)空间复杂性分析：O(n)六、实验体会通过写递归与分治策略实验，更加清楚的知道它的运行机理，分治法解题的一般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

做实验重在动手动脑，还是要多写写实验，才是硬道理。

七、附录：（源代码）#include"stdio.h"#define ElemType intint count(ElemType a[],int i,int j,ElemType x){int k=0,mid; //k用来计数，记录数组中x出现的次数if(i==j){if(a[i]==x) k++;return k;}else{mid=(i+j)/2;k+=count(a,i,mid,x);k+=count(a,mid+1,j,x);}return k;}ElemType Maxitem(ElemType a[],int n){ElemType max=a[n-1],j;if(n==1){max=a[n-1];return max;}else{j=Maxitem(a,n-1);if(j>max) max=j;return max;}}void main(void){ElemType a[]={1,5,2,7,3,7,4,8,9,5,4,544,2,4,123};ElemType b;ElemType x;int n;b=Maxitem(a,15);printf("数组的最大元素为%d\n",b);printf("输入想要计数的数组元素:\n");scanf("%d",&x);n=count(a,0,14,x);printf("%d在数组中出现的次数为%d次\n",x,n);}实验二动态规划——求解最优问题一、实验目的1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。

实验一排序算法设计一、实验内容冒泡排序二、实验问题分析该问题主要涉及到了指针和循环和相互比较的方法，是综合知识的应用。

三、数学模型根据题目要求，依次对每个数据进行比较，直至得出最后结果。

如果a>b则交换位置，如果a<b则不交换。

四、程序流程图五、源代码#include <stdio.h>void sort(int a[]){int temp;for(int i=0;i<9;i++){for(int j=0;j<10-i-1;j++){if(a[j]>a[j+1]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}printf("排序后的数据\n"); for(i=0;i<10;i++){if(i==5){printf("\n");}printf("%d ",a[i]);}printf("\n");}void main(){int a[10];for(int i=0;i<10;i++){scanf("%d",&a[i]);}printf("排序前的数据\n"); for(i=0;i<10;i++){if(i==5){printf("\n");}printf("%d ",a[i]);}printf("\n");sort(a);}六、测试结果实验二递归算法设计一、实验内容1.判断S字符是否为“回文”的递归函数，并编写程序测试。

二、实验问题分析递归是一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法。

递归算法设计，就是把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题，在逐步求解小问题后，再返回（回溯）得到大问题的解。

算法设计与分析实验报告算法设计与分析实验报告引言：算法设计与分析是计算机科学中的重要课程，它旨在培养学生解决实际问题的能力。

本次实验旨在通过设计和分析不同类型的算法，加深对算法的理解，并探索其在实际应用中的效果。

一、实验背景算法是解决问题的步骤和方法的描述，是计算机程序的核心。

在本次实验中，我们将重点研究几种经典的算法，包括贪心算法、动态规划算法和分治算法。

通过对这些算法的设计和分析，我们可以更好地理解它们的原理和应用场景。

二、贪心算法贪心算法是一种基于局部最优选择的算法，它每一步都选择当前状态下的最优解，最终得到全局最优解。

在实验中，我们以背包问题为例，通过贪心算法求解背包能够装下的最大价值物品。

我们首先将物品按照单位重量的价值从大到小排序，然后依次将能够装入背包的物品放入，直到背包无法再装下物品为止。

三、动态规划算法动态规划算法是一种通过将问题分解为子问题，并记录子问题的解来求解整体问题的算法。

在实验中，我们以斐波那契数列为例，通过动态规划算法计算斐波那契数列的第n项。

我们定义一个数组来保存已经计算过的斐波那契数列的值，然后通过递推公式将前两项的值相加得到后一项的值，最终得到第n项的值。

四、分治算法分治算法是一种将问题分解为更小的子问题，并通过递归求解子问题的算法。

在实验中，我们以归并排序为例，通过分治算法对一个无序数组进行排序。

我们首先将数组分成两个子数组，然后对子数组进行递归排序，最后将两个有序的子数组合并成一个有序的数组。

五、实验结果与分析通过对以上三种算法的设计和分析，我们得到了以下实验结果。

在贪心算法中，我们发现该算法能够在有限的时间内得到一个近似最优解，但并不能保证一定得到全局最优解。

在动态规划算法中，我们发现该算法能够通过记忆化搜索的方式得到准确的结果，但在问题规模较大时，其时间复杂度较高。

在分治算法中，我们发现该算法能够将问题分解为更小的子问题，并通过递归求解子问题，最终得到整体问题的解。

学号09710118《算法设计与分析》实验报告四学生姓名范振山专业、班级09计算机一班指导教师唐国峰成绩电子与信息工程系2012 年4 月6 日实验四：贪心算法运用练习一、实验目的本次实验是针对贪心算法的设计及应用练习，旨在加深学生对该部分知识点的理解，提高学生运用该部分知识解决问题的能力。

二、实验步骤与要求1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料；2．学生独自完成实验指定内容；3．实验结束后，用统一的实验报告模板编写实验报告。

4．提交说明：（1）电子版提交说明：a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验四_学号_姓名”，如“《算法设计与分析》实验四_09290101_张三”。

b 压缩包内为一个“《算法设计与分析》实验四_学号_姓名”命名的顶层文件夹，其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验报告电子版”。

其下分别放置对应实验成果物。

（2）打印版提交说明：a 不可随意更改模板样式。

b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号字。

c 行间距：单倍行距。

（3）提交截止时间：2012年4月20日16:00。

三、实验项目请从下列题目列表中任选2道或3道题目，运用贪心算法对问题的进行求解。

备选题目列表如下：1．教材第106页所记述的0-1背包问题。

2．教材课后习题4-9；3．教材课后习题4-21。

四、实验过程（一）题目一：给定n种物品和一个背包，物品i的重量是wi，其价值为vi，背包的容量为c。

问如何选择装入背包中的物品，使得装入背包中物品的总价值最大？1.题目分析给定c>0;wi>0;vo>0,1≤i≤n,要求找出一个n元0-1向量（x1,x2,……xn）,xi∈{0,1},1≤i ≤n,使得∑wixi≤c,而且∑vixi达到最大。

2.算法构造首先计算每种物品单位重量的价值vi.wi；然后，依贪心算法策略，将尽可能多的单位重量价值最高的物品装入背包。

计算机算法设计与分析实验报告专业：java 技术学号：541213440245 姓名：徐亚涛指导老师：谷培培实验一：棋盘覆盖（递归与分治策略）一、实验目的与要求1、明确棋盘覆盖的概念2、明确递归与分治策略的设计思路。

3、利用递归与分治策略解决棋盘覆盖问题。

二、实验题：问题描述：递归与分治策略算法，用4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。

输入数据由程序运行后的界面中的编辑框中输入游戏规模,特殊方格的位置。

将覆盖的结果在窗口中显示出来。

三、实验代码package cn.ChessBoard;import java.awt.BorderLayout;import java.awt.Color;import java.awt.Font;import java.awt.GridLayout;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import java.util.Random;import javax.swing.JButton;import javax.swing.JFrame;import javax.swing.JLabel;import javax.swing.JPanel;import javax.swing.JTextArea;import javax.swing.JTextField;public class ChessBoards extends JFrame {private int tr, tc, dr, dc, size;//定义各成员变量int tile = 1;float red,green,blue;JPanel centerPanel;JPanel southPanel;JButton[][] button;JTextField TrText, TcText, DrText, DcText, SizeText;JLabel TrLabel, TcLabel, DrLabel, DcLabel, SizeLabel;JButton OKButton;JButton CancelButton;JPanel panel = new JPanel();public ChessBoards() {super();setTitle("棋盘覆盖");this.setResizable(false);centerPanel = new JPanel();southPanel = new JPanel();OKButton = new JButton("确定或开始");OKButton.addActionListener(new OKButtonAction()); CancelButton = new JButton("取消或清除"); CancelButton.addActionListener(new OKButtonAction()); setBounds(300, -10, 900, 900);//设置窗口大小与位置TrText = new JTextField("0",2);//定义各组件TcText = new JTextField("0",2);DrText = new JTextField("0",2);DcText = new JTextField("0",2);SizeText = new JTextField("4",2);TrLabel = new JLabel("起始方格坐标x: ");TcLabel = new JLabel("起始方格坐标y: "); DrLabel = new JLabel("特殊方格坐标x: "); DcLabel = new JLabel("特殊方格坐标y: "); SizeLabel = new JLabel("棋盘规模size: ");TrText.setEnabled(false);TcText.setEnabled(false);int tR = Integer.parseInt(TrText.getText());int tC = Integer.parseInt(TcText.getText());int dR = Integer.parseInt(DrText.getText());int dC = Integer.parseInt(DcText.getText());int Size = 1;for (int i=0;i<Integer.parseInt(SizeText.getText());i++) Size*=2;tr = tR;tc = tC;dr = dR;dc = dC;size = Size;southPanel.add(CancelButton);//添加各组件到窗体southPanel.add(TrLabel);southPanel.add(TrText);southPanel.add(TcLabel);southPanel.add(TcText);southPanel.add(DrLabel);southPanel.add(DrText);southPanel.add(DcLabel);southPanel.add(DcText);southPanel.add(SizeLabel);southPanel.add(SizeText);southPanel.add(OKButton);getContentPane().add(southPanel, BorderLayout.NORTH);setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);}class gridLayout {public gridLayout() {centerPanel.setLayout(new GridLayout(0, size));button = new JButton[size][size];for (int i = 0; i < size; i++) {for (int j = 0; j < size; j++) {button[i][j] = new JButton();if (i == dr && j == dc) {button[i][j].setBackground(Color.BLUE);button[i][j].setText("<html><font size='2' color='white'>棋盘覆盖<br>Done By Java!</font></html>");button[i][j].setEnabled(false);}centerPanel.add(button[i][j]);}}}private void sleep(){for (int i=0;i<100;i++)for(int j=0;j<1000;j++);}public void ChessBoard(int tr, int tc, int dr, int dc, int size) {//算法实现if (size == 1) // 棋盘方格大小为1,说明递归到最里层return;int t = tile++;// 每次递增1Random rd = new Random();red=rd.nextFloat();green=rd.nextFloat();blue=rd.nextFloat();Color col = new Color(red,green,blue);sleep();int s = size / 2; // 棋盘中间的行、列号(相等的)// 检查特殊方块是否在左上角子棋盘中if (dr < tr + s && dc < tc + s) // 在ChessBoard(tr, tc, dr, dc, s);else // 不在，将该子棋盘右下角的方块视为特殊方块{button[tr + s - 1][tc + s - 1].setBackground(col);button[tr + s - 1][tc + s - 1].setEnabled(false);button[tr + s - 1][tc + s - 1].setText("<html><Font size='4',color='white'>"+t+"</Font></html>");ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);sleep();}// 检查特殊方块是否在右上角子棋盘中if (dr < tr + s && dc >= tc + s) // 在ChessBoard(tr, tc + s, dr, dc, s);else // 不在，将该子棋盘左下角的方块视为特殊方块{button[tr + s - 1][tc + s].setBackground(col);button[tr + s - 1][tc + s].setEnabled(false);button[tr + s - 1][tc + s ].setText("<html><Font size='4',color='white'>"+t+"</Font></html>");ChessBoard(tr, tc + s, tr + s - 1, tc + s, s);sleep();}// 检查特殊方块是否在左下角子棋盘中if (dr >= tr + s && dc < tc + s) // 在ChessBoard(tr + s, tc, dr, dc, s);else // 不在，将该子棋盘右上角的方块视为特殊方块{button[tr + s][tc + s - 1].setBackground(col);button[tr + s][tc + s - 1].setEnabled(false);button[tr + s ][tc + s - 1].setText("<html><Font size='4',color='white'>"+t+"</Font></html>");ChessBoard(tr + s, tc, tr + s, tc + s - 1, s);sleep();}// 检查特殊方块是否在右下角子棋盘中if (dr >= tr + s && dc >= tc + s) // 在ChessBoard(tr + s, tc + s, dr, dc, s);else // 不在，将该子棋盘左上角的方块视为特殊方块{button[tr + s][tc + s].setBackground(col);button[tr + s][tc + s].setEnabled(false);button[tr + s ][tc + s ].setText("<html><Font size='4',color='white'>"+t+"</Font></html>");ChessBoard(tr + s, tc + s, tr + s, tc + s, s);sleep();}}}public class OKButtonAction implements ActionListener {public void actionPerformed(ActionEvent e) {// TODO Auto-generated method stubJButton whichButton = (JButton) e.getSource();String whichName = whichButton.getActionCommand();if(whichName.equals("开始")) {getContentPane().add(centerPanel, BorderLayout.CENTER);int tR = Integer.parseInt(TrText.getText());int tC = Integer.parseInt(TcText.getText());int dR = Integer.parseInt(DrText.getText());int dC = Integer.parseInt(DcText.getText());int Size = 1;for (int i=0;i<Integer.parseInt(SizeText.getText());i++)Size*=2;tr = tR;tc = tC;dr = dR;dc = dC;size = Size;try {gridLayout grid = new gridLayout();grid.ChessBoard(tr, tc, dr, dc, size);centerPanel.updateUI();} catch (Exception EX) {EX.printStackTrace();}panel.removeAll();OKButton.setEnabled(false);}if (whichName.equals("取消或清除")) {//当你点下一个提示按钮时的事件响应JLabel label = new JLabel();label.setHorizontalAlignment(JLabel.CENTER);label.setText("<html><Font size='+8',color='red'><center><b><br> 您取消了操作或是<br><Font size='+8',color='blue'><center>您清除了前一个棋盘……" +"<br><Font size='+8',color='green'><center>下面是关于题目的介绍<br><br><br><br><br><br> </b></Font></html>");// JLabel l = new JLabel("题目要求");JTextArea area = new JTextArea("在一个2k x 2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，" +"称该方格为一特殊方格，且称该棋盘为一特殊棋盘。

《算法设计与分析》课程实验报告实验序号：实验项目名称：随机化算法一、实验题目1.N后问题问题描述：在n*n格的棋盘上放置彼此不受攻击的n个皇后，任何两个皇后不放在同一行同一列，同一斜线上，问有多少种放法。

2.主元素问题问题描述：设A是含有n个元素的数组，如果元素x在A中出现的次数大于n/2，则称x是A的主元素。

给出一个算法，判断A中是否存在主元素。

二、实验目的（1）通过N后问题的实现，体会拉斯维加斯随机算法的随机特点：运行次数随机但有界，找到的解一定为正确解。

但某次运行可能找不到解。

（2）通过实现主元素的不同算法，了解蒙特卡罗算法的随机特性：对于偏真的蒙特卡罗算法，找到为真的解一定是正确解；但非真的解以高概率给出解的正确率------即算法找到的非真解以小概率出现错误。

同时体会确定性算法与随机化算法的差异及各自的优缺点。

（3）通过跳跃表的实现，体会算法设计的运用的广泛性，算法设计的思想及技巧不拘泥独立问题的解决，而在任何需要计算机解决的问题中，都能通过算法设计的技巧（无论是确定性还是随机化算法）来灵巧地解决问题。

此实验表明，通过算法设计技巧与数据组织的有机结合，能够设计出高效的数据结构。

三、实验要求（1）N后问题分别以纯拉斯维加斯算法及拉斯维加斯算法+回溯法混合实现。

要求对同一组测试数据，完成如下任务a.输出纯拉斯维加斯算法找到解的运行次数及运行时间。

b.输出混合算法的stopVegas值及运行时间c.比较a、b的结果并分析N后问题的适用情况。

（2）主元素问题，要求对同一组测试数据，完成如下任务：a.若元素可以比较大小，请实现O(n )的确定性算法，并输出其运行时间。

b.(选做题）若元素不可以比较大小，只能比较相同否，请实现O（n) 确性算法，并输出其运行时间。

c.实现蒙特卡罗算法，并输出其运行次数及时间。

d.比较确定性算法与蒙特卡罗算法的性能，分析每种方法的优缺点。

（3）参照教材实现跳跃表（有序）及基本操作：插入一个结点，删除一个结点。

本科实验报告课程名称：算法设计与分析实验项目：递归与分治算法实验地点：计算机系实验楼110专业班级：物联网1601 学号：2016002105 学生：俞梦真指导教师：郝晓丽2018年05月04 日实验一递归与分治算法1.1 实验目的与要求1．进一步熟悉C/C++语言的集成开发环境；2．通过本实验加深对递归与分治策略的理解和运用。

1.2 实验课时2学时1.3 实验原理分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。

需要注意的是，分治法使用递归的思想。

划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。

最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。

1.4 实验题目1．上机题目：格雷码构造问题Gray码是一个长度为2n的序列。

序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。

试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。

对于给定的正整数n，格雷码为满足如下条件的一个编码序列。

（1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。

（2）序列中无相同的编码。

（3）序列中位置相邻的两个编码恰有一位不同。

2．设计思想：根据格雷码的性质，找到他的规律，可发现，1位是0 1。

两位是00 01 11 10。

三位是000 001 011010 110 111 101 100。

n位是前n-1位的2倍个。

N-1个位前面加0，N-2为倒转再前面再加1。

3．代码设计：}}}int main(){int n;while(cin>>n){get_grad(n);for(int i=0;i<My_grad.size();i++)cout<<My_grad[i]<<endl;My_grad.clear();}return 0;}运行结果：1.5 思考题（1）递归的关键问题在哪里？答：1.递归式，就是如何将原问题划分成子问题。

《算法分析与设计》实验报告专业：计科班级：日期：2016/04/11 成绩:学生姓名：学号：指导老师：实验单元三贪心算法一、实验题目实验二哈弗曼树二、实验目的了解前缀编码的概念，掌握最优子结构性质的证明方法；掌握贪心算法的设计思想并能熟练运用。

三、实验内容设需要编码的字符集为{d1, d2, •, dn}，它们出现的频率为{w1, w2, •, wn}，应用哈弗曼树构造最短的编码。

哈弗曼编码的基本思想是：在集合中选择两颗根节点的权值最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根节点的权值为其左、右子树上根节点的权值之和；随后删除这两颗树，同时将新得到的二叉树加入F 中。

不断重复，最后直到剩下一棵树，这棵树便是哈弗曼树。

四、实验结果（代码及运行结果）实验源代码：#include <stdio.h>#include <string.h>#include <time.h>#include <stdlib.h>typedef struct Node // 定义树结构{int data;struct Node *leftchild;struct Node *rightchild;} Tree;typedef struct Data // 定义字符及其对应的频率的结构{int data; // 字符对应的频率是随机产生的char c;};void Initiate(Tree **root); // 初始化节点函数int getDataMin(struct Data a[],int n); // 得到数组 a 中数值（频率）最小的数void toLength(char s[],int k); // 设置有 k 个空格的串 svoid set(struct Data a[],struct Data b[]); // 初始化数组 a,且将 a 备份至 bchar getCharhar(int x,struct Data a[]); // 得到 a 中频率为 x 对应的字符void print(struct Data a[]); // 输出初始化后的字符及对应的频率int n;int main() // 入口函数{Tree *root = NULL,*left = NULL,*right = NULL,*p = NULL;int min,num;int k = 30,j,m;struct Data a[100];struct Data b[100];int i;char s[100] = {'\0'},s1[100] = {'\0'};char c;set(a,b);print(a);Initiate(&root);Initiate(&left);Initiate(&right);Initiate(&p);//设置最底层的左节点min = getDataMin(a,n);left->data = min;left->leftchild = NULL;left->rightchild = NULL;//设置最底层的右节点min = getDataMin(a,n-1);right->data = min;right->leftchild = NULL;right->rightchild = NULL;root->data = left->data+right->data;Initiate(&root->leftchild);Initiate(&root->rightchild);//将设置好的左右节点插入到root中root->leftchild = left;root->rightchild = right;for(i = 0; i<n-2; i++){min = getDataMin(a,n-2-i);Initiate(&left);Initiate(&right);if(min<root->data)//权值小的作为左节点{left->data = min;left->leftchild = NULL;left->rightchild = NULL;p->data = min+root->data;Initiate(&p->leftchild);Initiate(&p->rightchild);p->leftchild = left;p->rightchild = root;root = p;}else{right->data = min;right->leftchild = NULL;right->rightchild = NULL;p->data = min+root->data;Initiate(&p->leftchild);Initiate(&p->rightchild);p->leftchild = root;p->rightchild = right;root = p;}Initiate(&p);}num = n-1;p = root;printtf("哈夫曼树:\n");while(num) // 输出建立的 Huffman 图{if(num == n-1){for(j = 0; j<k-3; j++)printtf(" ");printtf("%d\n",root->data);}for(j = 0; j<k-4; j++)printtf(" ");printtf("/ \\\n");for(j = 0; j<k-5; j++)printtf(" ");printtf("%d",root->leftchild->data);printtf(" %d\n",root->rightchild->data); if(root->leftchild->leftchild!= NULL){root = root->leftchild;k = k-2;}{root = root->rightchild;k = k+3;}num--;}num = n-1;Initiate(&root);root = p;printtf("字符编码:\n");while(num){if(root->leftchild->leftchild == NULL){strcpy(s1,s);m = root->leftchild->data;c = getChar(m,b);printtf("%c 【%d】:%s\n",c,m,strcat(s1,"0")); }if(root->rightchild->leftchild == NULL){strcpy(s1,s);m = root->rightchild->data;c = getChar(m,b);printtf("%c 【%d】:%s\n",c,m,strcat(s1,"1")); }if(root->leftchild->leftchild!= NULL){strcat(s,"0");root = root->leftchild;}if(root->rightchild->leftchild!= NULL){strcat(s,"1");root = root->rightchild;}num--;}return 0;}int getDataMin(struct Data a[],int n){int i,t;for(i = 1; i<n; i++)if(a[i].data<a[0].data){t = a[i].data;a[i].data = a[0].data;a[0].data = t;}}t = a[0].data;for(i = 0; i<n-1; i++){a[i] = a[i+1];}return t;}void toLength(char s[],int k) // 输出空格{int i = 0;for(; i<k; i++)strcat(s," "); // strcat（）字符串连接函数}void Initiate(Tree **root) // 初始化函数{*root = (Tree *)malloc(sizeof(Tree));(*root)->leftchild = NULL;(*root)->rightchild = NULL;}void set(struct Data a[],struct Data b[]){int i;srand((unsigned)time(NULL)); // 生成随机数n = rand()%10+2;for(i = 0; i<n; i++){a[i].data = rand()%100+1;a[i].c = i+97;b[i].data = a[i].data;b[i].c = a[i].c;if(i >= 0&&a[i].data == a[i-1].data)i--;}}char getChar(int x,struct Data b[]){for(i = 0; i<n; i++){if(b[i].data == x){break;}}return b[i].c;}void print(struct Data a[]) // 打印函数{int i;printtf("字符\t 出现的频率\n");for(i = 0; i<n; i++){printtf("%c\t %d\n",a[i].c,a[i].data);}}运行结果为：五、实验体会哈夫曼编码算法：每次将集合中两个权值最小的二叉树合并成一棵新二叉树，n-1次合并后，成为最终的一棵哈夫曼树。

算法设计与程序分析实验报告姓名：学号：班级：指导老师：实验1：汉诺塔问题程序代码：#include <stdio.h>//第一个塔为初始塔，中间的塔为借用塔，最后一个塔为目标塔int i=1;//记录步数void move(int n,char from,char to) //将编号为n的盘子由from移动到to{printf("第%d步:将%d号盘子%c---->%c\n",i++,n,from,to);}void hanoi(int n,char from,char denpend_on,char to)//将n个盘子由初始塔移动到目标塔(利用借用塔){if (n==1)move(1,from,to);//只有一个盘子是直接将初塔上的盘子移动到目的地else{hanoi(n-1,from,to,denpend_on);//先将初始塔的前n-1个盘子借助目的塔移动到借用塔上move(n,from,to); //将剩下的一个盘子移动到目的塔上hanoi(n-1,denpend_on,from,to);//最后将借用塔上的n-1个盘子移动到目的塔上}}void main(){printf("请输入盘子的个数:\n");int n;scanf("%d",&n);char x='A',y='B',z='C';printf("盘子移动情况如下:\n");hanoi(n,x,y,z);}实验结果：实验2：杨辉三角：程序代码：#include<stdio.h>void print(int *row,int n){int i;for(i=1;i<n;i++){if(row[i]!=0){printf("%d",row[i]);row[i]=0;//置为初始态，方便保存下一行}elseprintf(" ");}printf("\n");}void initia(int num){int up_row[20];int next_row[20];int i,j;for(i=0;i<=num*2;i++){up_row[i]=0;next_row[i]=0;}up_row[num]=next_row[num]=1;for(i=0;i<num;i++)//控制行{for(j=1;j<num+i+1;j++){up_row[j]=next_row[j];//保存当前输出行}print(next_row,num+i+1);//本行输出的有效数据个数为当前行数for(j=1;j<=num+i+1;j++)//0号位的值保留以便下行计算{next_row[j]=up_row[j-1]+up_row[j+1];//下一行相应位置的值是上一行相应位置左右值的和}}}int main(void){int num_row;printf("确定行数(小于10)：");scanf("%d",&num_row);initia(num_row);return 0;}实验结果：方法2：动态规划实现：程序代码：#include <stdio.h>#define MAXH 31int main(void){unsigned long num[MAXH]={0};int i,j,k;int n;printf("Input a number to set row:");scanf("%d",&n);num[0]=1;i=0;for(i=0;i<n;i++){for(k=n-i;k>0;k--)printf(" ");for(j=i;j>0;j--){num[j] = num[j] + num[j-1];printf("%d ",num[j]);}printf(" %d \n",1);}return 0;}实验3：背包问题：程序代码：#include<stdio.h>int c[10][100];/*对应每种情况的最大价值*/int knapsack(int m,int n){int i,j,w[10],p[10];printf("\n输入每个物品的重量及价值：\n");for(i=1;i<=n;i++)scanf("%d,%d",&w[i],&p[i]);for(i=0;i<10;i++)for(j=0;j<100;j++)c[i][j]=0;/*初始化数组*/for(i=1;i<=n;i++)for(j=1;j<=m;j++){if(w[i]<=j) /*如果当前物品的容量小于背包容量*/{if(p[i]+c[i-1][j-w[i]]>c[i-1][j])/*如果本物品的价值加上背包剩下的空间能放的物品的价值*/ /*大于上一次选择的最佳方案则更新c[i][j]*/c[i][j]=p[i]+c[i-1][j-w[i]];elsec[i][j]=c[i-1][j];}else c[i][j]=c[i-1][j];}return(c[n][m]);}int main(){int m,n;int maxvalue;printf("输入背包的承重量：");scanf("%d",&m);printf("\n输入物品的总个数：");scanf("%d",&n);maxvalue = knapsack(m,n);printf("\n背包能装的最大总价值为%d",maxvalue);printf("\n");return 0;}实验结果：实验4：斐波那契数列：程序代码：#include<stdio.h>void main(){int Fibonacci(int n);int n,i;long int c=0;printf("求斐波那契数组：\n");printf(" | 0 n=0\n");printf("F(n) = { 1 n=1\n");printf(" | F(n-1)+F(n-2) n>1\n");printf("请输入n的值:");scanf("%d",&n);for(i=1; i<=n; i++){c = Fibonacci(i);printf("%-10ld",c);if(i%5==0) //每输出5个换一行；printf("\n");}printf("\n");}int Fibonacci(int n)//函数部分；{long int fib;if(n==0){fib=0;}else if(n==1 || n==2){fib=1;}else if(n>=3){fib = Fibonacci(n-1) + Fibonacci(n-2);}return fib;}实验结果：实验5：归并排序程序代码：#include <iostream.h>int *a=new int[20];int n=0;//归并排序，排序结果放到了b[]中void Merge(int a[],int b[],int left ,int mid,int right)//此处的right指向数组中左后一个元素的位置{int i=left;int j=mid+1;int k=left;while(i<=mid&&j<=right){if(a[i]<=a[j])b[k++]=a[i++];else b[k++]=a[j++];}while(i<=mid)b[k++]=a[i++];while(j<=right)b[k++]=a[j++];}//从b[]中又搬到了a[]中void Copy(int a[],int b[],int left,int right)//right同上{for(int i=left;i<=right;i++)a[i]=b[i];}//划分并排序void MergeSort(int a[],int left,int right)//同上{int *b = new int[right+1];if(left<right){//将当前传经来的数组划分成更小的大小几乎相同的数组int i=(left+right)/2;MergeSort(a,left,i);MergeSort(a,i+1,right);//将小数组合成大数组，同时排序，结果放到b[]中Merge(a,b,left,i,right);//从b[]中挪到a[]中Copy(a,b,left,right);}}void Input(){cout<<"Please Input array's size:";cin>>n;cout<<"Array's elemants:"<<endl;for(int i=0;i<n;i++)cin>>a[i];//调用算法MergeSort(a,0,n-1);}void Output(){for(int i=0;i<n;i++)cout<<a[i]<<" ";cout<<endl;}void main(){Input();Output();}实验结果：实验6:二分查找：程序代码：#include <stdio.h>int search ( int a[],int s,int r,int key ){int low=s,high=r,mid;if ( s<=r ){mid=(high+low)/2;if ( a[mid]==key )return mid;if ( a[mid]<key )return search ( a,mid+1,high,key );if ( a[mid]>key )return search ( a,low,mid-1,key );}elsereturn -1;}int main (){int n,a[10000],key,k,i;printf("请输入数组大小：\n");while ( scanf ("%d",&n)!=EOF ){for ( i=0;i<n;i++ )scanf ("%d",&a[i]);printf("请输入要查找的数：");scanf ("%d",&key);k=search(a,0,n-1,key);if ( k==-1 )printf("NO\n未找到!\n");else{printf("YES\n");printf("该数位置在第%d位！\n",k+1);}}return 0;}实验结果：。

算法分析与设计实验报告1. 引言算法是计算机科学中的核心概念之一，它为解决问题提供了一种清晰、有效的方法。

本实验报告旨在通过分析与设计一个特定算法的实验过程，来加深对算法的理解和应用。

2. 实验背景在现代社会中，算法的应用无处不在。

无论是搜索引擎的排序算法，还是社交媒体的推荐算法，都离不开算法的支持。

因此，学习算法的分析与设计，对于计算机科学相关领域的学生来说具有重要的意义。

3. 实验目的本实验的主要目的是通过分析与设计一个特定算法，加深对算法的理解和应用。

通过实际操作，学生将能够熟悉算法的设计过程，并能够分析算法的效率和复杂性。

4. 实验步骤4.1 确定算法目标在开始实验之前，我们需要明确算法的目标。

在本实验中，我们将设计一个排序算法，用于对一组数字进行排序。

4.2 了解算法原理在设计算法之前，我们需要对目标算法的原理进行深入了解。

在本实验中，我们将选择经典的冒泡排序算法作为实现对象。

冒泡排序算法的基本思想是通过比较相邻的元素，并根据需要交换位置，使得每一轮循环都能使最大（或最小）的元素“冒泡”到数组的末尾。

通过多次迭代，最终实现整个数组的排序。

4.3 实现算法在了解算法原理后，我们将根据算法的步骤逐步实现。

具体步骤如下：1.遍历待排序数组，从第一个元素开始。

2.比较当前元素与下一个元素的大小。

3.如果当前元素大于下一个元素，则交换它们的位置。

4.继续比较下一个元素，直到遍历完整个数组。

5.重复上述步骤，直到没有需要交换的元素。

4.4 测试算法在实现算法之后，我们需要对其进行测试，以验证其正确性和效率。

我们可以准备一组随机的数字作为输入，并对算法进行测试。

通过比较输入和输出结果，我们可以判断算法是否正确。

同时，我们还可以通过计算算法的时间复杂性和空间复杂性来评估其效率。

在本实验中，我们将使用时间复杂性分析来评估算法的效率。

4.5 分析与总结通过测试和分析，我们将得出算法的执行时间和空间复杂性。

实验课程名称：算法设计与分析这里的数据包括1到100的所有数字，55在这个序列中。

2.当没找到所要寻找的数字时，输出该数据并不存在于数据库中：0并不存在于这个序列中。

一、时间复杂性分析：1.最好情况下：这里的最好情况，即为第一次查找就找到了要找的数据，故时间复杂性为O （1）。

2.最坏情况下：这里的最坏情况意味着要将所有数据都找一遍最后才能找到要查找的数据，随着数据库的增大，查找次数会随之增长，故其时间复杂度为O （n ）。

3.平均情况下：这种情况考虑了数据时等概率的分布于数据库中。

ASL=-101-121111=2=(1*2+2*2+...+*2)log (+1)-1nkj k i i i j p c j k n nn==≈∑∑折半查找的时间复杂性为O （2log n ）。

二、空间复杂度分析：这里查找的过程中并不需要额外的空间，只需要存放数据的空间，故空间复杂度为O （n ），n 为数组的大小。

三、算法功能：其功能主要是用来查找数据，若对它进行一下拓展，可以由自主确定数据库，并可对他进行操作；这里的数据也可以不只是包括整数。

实验二结果：1.当数组的容量不大于0时，显示错误：2.当输入数据错误时，显示错误：3.当输入正确时的显示结果：一、时间复杂性分析：1.最好情况下：T (n )≤2 T (n /2)＋n ≤2(2T (n /4)＋n /2)＋n ＝4T (n /4)＋2n ≤4(2T (n /8)＋n /4)＋2n ＝8T (n /8)＋3n … … …≤nT (1)＋n log 2n ＝O (n log 2n ) 因此，时间复杂度为O (n log 2n )。

2.最坏情况下：待排序记录序列正序或逆序，每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空）。

此时，必须经过n -1次递归调用才能把所有记录定位，而且第i 趟划分需要经过n -i 次关键码的比较才能找到第i 个记录的基准位置，因此，总的比较次数为： 因此，时间复杂度为O (n 2)。

算法设计与分析实验报告《算法设计与分析》实验报告实验一递归与分治策略应用基础学号：**************姓名：*************班级：*************日期：2014-2015学年第1学期第九周一、实验目的1、理解递归的概念和分治法的基本思想2、了解适用递归与分治策略的问题类型，并能设计相应的分治策略算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：以下题目要求应用递归与分治策略设计解决方案，本次实验成绩按百分制计，完成各小题的得分如下，每小题要求算法描述准确且程序运行正确。

1、求n个元素的全排。

（30分）2、解决一个2k*2k的特殊棋牌上的L型骨牌覆盖问题。

（30分）3、设有n=2k个运动员要进行网球循环赛。

设计一个满足要求的比赛日程表。

（40分）提交结果：算法设计分析思路、源代码及其分析说明和测试运行报告。

三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#include "iostream"using namespace std;#define N 100void Perm(int* list, int k, int m) {if (k == m){for (int i=0; i<m; i++)cout << list[i] << " ";cout << endl;return;}else{for (int i=m; i<k; i++){swap(list[m], list[i]);Perm(list, k, m+1);swap(list[m], list[i]);}}}void swap(int a,int b){int temp;temp=a;a=b;b=temp;}int main(){int i,n;int a[N];cout<<"请输入排列数据总个数：";cin>>n;cout<<"请输入数据：";for(i=0;i<n;i++){cin>>a[i];}cout<<"该数据的全排列："<<endl;Perm(a,n,0);return 0;}《算法设计与分析》实验报告实验二递归与分治策略应用提高学号：**************姓名：*************班级：*************日期：2014-2015学年第1学期一、实验目的1、深入理解递归的概念和分治法的基本思想2、正确使用递归与分治策略设计相应的问题的算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用递归与分治策略设计解决方案。

算法设计与分析实验报告1. 引言本实验报告旨在介绍算法设计与分析的相关内容。

首先，我们将介绍算法设计的基本原则和步骤。

然后，我们将详细讨论算法分析的方法和技巧。

最后，我们将通过一个实例来演示算法设计与分析的过程。

2. 算法设计算法设计是解决问题的关键步骤之一。

它涉及确定问题的输入和输出，以及找到解决方案的具体步骤。

以下是算法设计的一般步骤：2.1 理解问题首先，我们需要全面理解给定问题的要求和约束。

这包括确定输入和输出的格式，以及问题的具体要求。

2.2 制定算法思路在理解问题后，我们需要制定解决问题的算法思路。

这涉及确定解决问题的高层次策略和步骤。

通常，我们使用流程图、伪代码等工具来表示算法思路。

2.3 编写算法代码在制定算法思路后，我们可以根据思路编写实际的算法代码。

这可能涉及选择适当的数据结构和算法，以及编写相应的代码来实现解决方案。

2.4 调试和测试编写算法代码后，我们需要进行调试和测试，以确保算法的正确性和可靠性。

这包括检查代码中可能存在的错误，并使用不同的测试样例来验证算法的正确性。

3. 算法分析算法分析是评估算法性能的过程。

它涉及确定算法的时间复杂度和空间复杂度，以及评估算法在不同输入情况下的执行效率。

3.1 时间复杂度时间复杂度是衡量算法执行时间随输入规模增长的速度。

常见的时间复杂度包括常数时间复杂度 O(1)、线性时间复杂度 O(n)、对数时间复杂度 O(log n)、平方时间复杂度 O(n^2) 等。

通过分析算法中的循环、递归等关键部分，可以确定算法的时间复杂度。

3.2 空间复杂度空间复杂度是衡量算法所需空间随输入规模增长的速度。

它通常用于评估算法对内存的使用情况。

常见的空间复杂度包括常数空间复杂度 O(1)、线性空间复杂度 O(n)、对数空间复杂度 O(log n) 等。

通过分析算法中的变量、数组、递归栈等关键部分，可以确定算法的空间复杂度。

3.3 执行效率评估除了时间复杂度和空间复杂度外，我们还可以通过实验和测试来评估算法的执行效率。

算法设计与分析实验报告1. 引言本实验旨在设计和分析一个算法，解决特定的问题。

通过对算法的设计、实现和性能分析，可以对算法的优劣进行评估和比较。

本报告将按照以下步骤进行展开：1.问题描述2.算法设计3.算法实现4.性能分析5.结果讨论和总结2. 问题描述在本实验中，我们面临的问题是如何在一个给定的无序数组中寻找一个特定元素的位置。

具体而言，给定一个包含n个元素的数组A和一个目标元素target，我们的目标是找到target在数组A中的位置，如果target不存在于数组中，则返回-1。

3. 算法设计为了解决上述问题，我们设计了一个简单的线性搜索算法。

该算法的思想是从数组的第一个元素开始，逐个比较数组中的元素与目标元素的值，直到找到匹配的元素或搜索到最后一个元素。

算法的伪代码如下：function linear_search(A, target):for i from 0 to len(A)-1:if A[i] == target:return ireturn -14. 算法实现我们使用Python编程语言实现了上述线性搜索算法。

以下是算法的实现代码：def linear_search(A, target):for i in range(len(A)):if A[i] == target:return ireturn-15. 性能分析为了评估我们的算法的性能，我们进行了一系列实验。

我们使用不同大小的数组和不同目标元素进行测试，并记录了每次搜索的时间。

实验结果显示，线性搜索算法的时间复杂度为O(n)，其中n是数组的大小。

这是因为在最坏的情况下，我们需要遍历整个数组才能找到目标元素。

6. 结果讨论和总结通过对算法的设计、实现和性能分析，我们可以得出以下结论：1.线性搜索算法是一种简单但有效的算法，适用于小规模的数据集。

2.线性搜索算法的时间复杂度为O(n)，在处理大规模数据时可能效率较低。

3.在实际应用中，我们可以根据具体的问题和数据特征选择合适的搜索算法，以提高搜索效率。

《算法设计与分析》实验报告实验四动态规划策略应用提高学号：122208206101姓名：蔡猛班级：网络工程日期：2014-2015学年第1学期一、实验目的1、深入理解动态规划策略的基本思想。

2、能正确采用动态规划策略设计相应的算法，解决实际问题。

3、掌握动态规划算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用动态规划策略设计解决方案。

1、编辑距离问题。

2、石子合并问题。

3、租用游艇问题。

提交结果：程序设计的源代码及其分析说明和测试运行报告。

三、设计分析首先创建一个二维矩阵，6 x 9,设为C[][]代表移动距离,然后进入循环，如果S 的第一个字符串==T的第二个字符串，z=C[I][J],否则z=C[I+1][J+1]其实就是记录操作数。

z=0,或者z=1,最后记录到c[i=1][i=1],也就是说C，对应数组值的是距离，如果不相等，则z=1,x=2,y=2,最后，C[1][1]=1;也就是说，到现在已经进行了距离为1的编辑。

重新进入循环并判断。

四、算法描述及程序#include <iostream>#include <string>using namespace std;int min(int a, int b){return a < b ? a : b;}int edit(string str1, string str2){int max1 = str1.size();int max2 = str2.size();int **ptr = new int*[max1 + 1];for(int i = 0; i < max1 + 1 ;i++)ptr[i] = new int[max2 + 1];}for( i = 0 ;i < max1 + 1 ;i++){ptr[i][0] = i;}for( i = 0 ;i < max2 + 1;i++){ptr[0][i] = i;}for( i = 1 ;i < max1 + 1 ;i++){for(int j = 1 ;j< max2 + 1; j++){int d;int temp = min(ptr[i-1][j] + 1, ptr[i][j-1] + 1);if(str1[i-1] == str2[j-1]){d = 0 ;}else{d = 1 ;}ptr[i][j] = min(temp, ptr[i-1][j-1] + d);}}cout << "**************************" << endl;for( i = 0 ;i < max1 + 1 ;i++){for(int j = 0; j< max2 + 1; j++){cout << ptr[i][j] << " " ;}cout << endl;}cout << "**************************" << endl;int dis = ptr[max1][max2];for( i = 0; i < max1 + 1; i++){delete[] ptr[i];ptr[i] = NULL;delete[] ptr;ptr = NULL;return dis;}int main(void){string str1 = "sailn";string str2 = "failing";int r = edit(str1, str2);cout << "the dis is : " << r << endl;return 0;}五、测试与分析。

《算法设计与分析》课程实验报告实验序号：04实验项目名称：实验4 分治法（三）一、实验题目1.邮局选址问题问题描述：在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。

用x 坐标表示东西向，用y坐标表示南北向。

各居民点的位置可以由坐标(x,y)表示。

街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值∣x1−x2∣+∣y1−y2∣度量。

居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。

编程任务：给定n 个居民点的位置,编程计算邮局的最佳位置。

2.最大子数组问题问题描述：对给定数组A，寻找A的和最大的非空连续子数组。

3.寻找近似中值问题描述：设A是n个数的序列，如果A中的元素x满足以下条件：小于x的数的个数≥n/4,且大于x的数的个数≥n/4 ，则称x为A的近似中值。

设计算法求出A的一个近似中值。

如果A中不存在近似中值，输出false，否则输出找到的一个近似中值4.循环赛日程表问题描述：设有n=2^k个运动员要进行网球循环赛。

现要设计一个满足以下要求的比赛日程表：每个选手必须与其他n-1个选手各赛一次，每个选手一天只能赛一次，循环赛一共进行n-1天。

二、实验目的（1）进一步理解分治法解决问题的思想及步骤（2）体会分治法解决问题时递归及迭代两种不同程序实现的应用情况之差异（3）熟练掌握分治法的自底向上填表实现（4）将分治法灵活于具体实际问题的解决过程中，重点体会大问题如何分解为子问题及每一个大问题涉及哪些子问题及子问题的表示。

三、实验要求（1）写清算法的设计思想。

（2）用递归或者迭代方法实现你的算法，并分析两种实现的优缺点。

（3）根据你的数据结构设计测试数据，并记录实验结果。

（4）请给出你所设计算法的时间复杂度的分析，如果是递归算法，请写清楚算法执行时间的递推式。

四、实验过程（算法设计思想、源码）1.邮局选址问题(1)算法设计思想根据题目要求，街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值∣x1−x2∣+∣y1−y2∣度量。

《算法设计与分析》实验报告网络10-1 李俊实验一分治与递归基本题一：基本递归算法四、程序清单：#include <iostream>using namespace std;int q(int n ,int m){if((n<1) || (m<1) )return 0;if((n==1) || (m==1)) return 1;if(n<m) return q(n,n);if(n==m) return q(n,m-1)+1;return q(n,m-1)+q(n-m,m);}int main (){int a,b,c;int q(int n, int m);cout << "please input a and b" <<endl;cin >>a>>b;c=q(a,b);cout <<"整数的划分为："<<c<<endl;return 0;}测试数据及结果如下图所示：基本题二：棋盘覆盖问题程序清单：#include<iostream>#include<iomanip>using namespace std;int Board[1024][1024];//模拟棋盘int tile=0;//骨牌编号,从0开始void ChessBoard(int tr, int tc, int dr, int dc, int size);void OutputBoard(int size);int main(){int size,dr,dc;cout<<"请输入方阵的规格k(方阵为k*k,须为2的幂): ";cin>>size;cout<<"请输入特殊方格的行号(矩阵下标由零开始计算,即0~k-1): "; cin>>dr;cout<<"请输入特殊方格的列号(矩阵下标由零开始计算,即0~k-1): "; cin>>dc;ChessBoard(0,0,dr,dc,size);// 覆盖特殊棋盘OutputBoard(size);//输出覆盖后的棋盘return 0;}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{//本棋盘中没有特殊方格Board[tr+s-1][tc+s-1]=t;//把三格板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{//本棋盘中没有特殊方格Board[tr+s-1][tc+s]=t;//把三格板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 {//本棋盘中没有特殊方格Board[tr+s][tc+s-1]=t;//把三格板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;// 把三格板t放在左上角,将此棋盘转化为特殊棋盘ChessBoard(tr+s,tc+s,tr+s,tc+s,s);//覆盖其余部分}}void OutputBoard(int size){int i,j;for(i = 0; i < size; i++){for (j = 0; j < size; j++)cout << setw (5) << Board[i][j];cout << endl;}}测试数据及结果如下图所示：提高题一：二分搜索1、设a[0:n-1]是一个已排好序的数组。