算法设计与分析
实验报告
—八皇后问题
-
姓名：崔明鑫
学号：08208012
班级：软件83
【问题描述】
在国际象棋盘上放八个皇后，要求任一皇后吃不到别人，也不受其他皇后的攻击，求出问题的所有解。
【问题分析&算法设计】
用8元组x[1: n]表示8后问题。其中x[ i]表示皇后i放在棋盘的第i行的第x[ i]列。由于不允许将2个皇后放在一列，所以解向量中的x[ i]互不相同。2个皇后不能放在同一斜线上是问题的隐约束。故若2个皇后放置的位置分别是（i，j）和（k，l），且i – j = k – l或i + j = k + l，则说明这2个皇后处于同一斜线上。这两个方程分别等价于i – k = j – l和i – k = l – j。由此可知，只要|i - k| = |j - l|成立，就表明2个皇后位于同一条斜线上。问题的隐约束化成了显约束。用回溯法解决8皇后问题时，用完全8叉树表示解空间。
【算法实现】
#include "stdio.h"
#include "math.h"
#include "iostream.h"
#define N 8 /* 定义棋盘大小*/
static int sum; /* 当前已找到解的个数*/
static int x[N]; /* 记录皇后的位置,x[i]表示皇后i放在棋盘的第i行的第x[i]列*/
/* 每找到一个解,打印当前棋盘状态*/
void Show()
{
sum++;
cout << "第" << sum << "种情况：" << endl;
cout << "坐标为:\t";
for(int k = 0; k < N; k++)
cout << '(' << k+1 << ',' << x[k] << ") ";
cout << endl;
cout << "---------------------------------\n";
for (int i = 0; i < N; i ++)
{
for (int j = 0; j < N; j ++)
if (j == x[i]) //printf("@ ");
cout << "* | ";
else //printf("* ");
cout << " | ";
cout << "\n---------------------------------\n";
}
}
/* 确定某一位置皇后放置与否，放置则返回1，反之返回0 */
int Judge(int k)
{
// 测试皇后k在第k行第x[k]列时是否与前面已放置好的皇后相攻击。x[j] == // x[k] 时，两皇后在同一列上；abs(k - j) == abs(x[j] - x[k]) 时，两皇
// 后在同一斜线上。两种情况两皇后都可相互攻击，故返回0表示不符合条件。
for (int j = 0; j < k; j ++)
if (abs(k - j) == abs(x[j] - x[k]) || (x[j] == x[k]))
return 0;
return 1;
}
/* 主递归函数，搜索解空间中第i层子树*/
void Backtrack(int t)
{
/* t == N 时，算法搜索至叶结点，得到一个新的N皇后互不攻击的放置方案*/ if (t == N) Show();
else
for (int i = 0; i < N; i ++)
{
x[t] = i;
if (Judge(t))
Backtrack(t + 1);
}
}
int main()
{
Backtrack(0);
cout << endl;
return 0;
}
【运行结果】
可知在考虑对称的情况下，8皇后问题共有92种解。
实验三分治算法（2） 一、实验目的与要求 1、熟悉合并排序算法（掌握分治算法） 二、实验题 1、问题陈述: 对所给元素存储于数组中和存储于链表中两中情况，写出自然合并排序算法. 2、解题思路: 将待排序元素分成大小大相同的两个集合,分别对两个集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合.自然排序是通过一次扫描待排元素中自然排好序的子数组,再进行子数组的合并排序. 三、实验步骤 程序代码: #include
int target[N],head[N],tail[N]; int i=0,n,m; for(; i
数学建模实验报告
一、实验目的 1、通过具体的题目实例，使学生理解数学建模的基本思想和方法，掌握 数学建模分析和解决的基本过程。 2、培养学生主动探索、努力进取的的学风，增强学生的应用意识和创新 能力，为今后从事科研工作打下初步的基础。 二、实验题目 （一）题目一 1、题目：电梯问题有r个人在一楼进入电梯，楼上有n层。设每个 乘客在任何一层楼出电梯的概率相同，试建立一个概率模型，求直 到电梯中的乘客下完时，电梯需停次数的数学期望。 2、问题分析 （1）由于每位乘客在任何一层楼出电梯的概率相同，且各种可能的情况众多且复杂，难于推导。所以选择采用计算机模拟的 方法，求得近似结果。 （2）通过增加试验次数，使近似解越来越接近真实情况。 3、模型建立 建立一个n*r的二维随机矩阵，该矩阵每列元素中只有一个为1，其余都为0，这代表每个乘客在对应的楼层下电梯（因为每 个乘客只会在某一层下，故没列只有一个1）。而每行中1的个数 代表在该楼层下的乘客的人数。 再建立一个有n个元素的一位数组，数组中只有0和1,其中1代表该层有人下，0代表该层没人下。 例如： 给定n=8;r=6（楼8层，乘了6个人）,则建立的二维随机矩阵及与之相关的应建立的一维数组为： m = 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 c = 1 1 0 1 0 1 1 1 4、解决方法（MATLAB程序代码）：
n=10;r=10;d=1000; a=0; for l=1:d m=full(sparse(randint(1,r,[1,n]),1:r,1,n,r)); c=zeros(n,1); for i=1:n for j=1:r if m(i,j)==1 c(j)=1; break; end continue; end end s=0; for x=1:n if c(x)==1 s=s+1; end continue; end a=a+s; end a/d 5、实验结果 ans = 6.5150 那么，当楼高11层，乘坐10人时，电梯需停次数的数学期望为6.5150。 （二）题目二 1、问题：某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6 千克,工人10名,可获利10万元;每百箱乙饮料需用原料5千 克,工人20名,可获利9万元.今工厂共有原料60千克,工人 150名,又由于其他条件所限甲饮料产量不超过8百箱.问如何 安排生产计划,即两种饮料各生产多少使获利最大.进一步讨 论: 1)若投资0.8万元可增加原料1千克,问应否作这项投资. 2)若每百箱甲饮料获利可增加1万元,问应否改变生产计划. 2、问题分析 （1）题目中共有3个约束条件，分别来自原料量、工人数与甲饮料产量的限制。 （2）目标函数是求获利最大时的生产分配，应用MATLAB时要转换
本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号： 05 学生姓名：俞梦真 指导教师：郝晓丽 2018年 05月 04 日 实验一递归与分治算法 实验目的与要求
1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 实验课时 2学时 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想： 根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计： 归式，就是如何将原问题划分成子问题。 2.递归出口，递归终止的条件，即最小子问题的求解，可以允许多个出口。 3.界函数，问题规模变化的函数，它保证递归的规模向出口条件靠拢（2）递归与非递归之间如何实现程序的转换？ （3）分析二分查找和快速排序中使用的分治思想。 答： 1．一般根据是否需要回朔可以把递归分成简单递归和复杂递归，简单递归一般就是根据递归式来找出递推公式（这也就引申出分治思想和动态规划）。 2．复杂递归一般就是模拟系统处理递归的机制，使用栈或队列等数据结构保存回朔点来求解。 （4）分析二次取中法和锦标赛算法中的分治思想。 二次取中法：使用快速排序法中所采用的分划方法，以主元为基准，将一个表划分为左右两个子表，左子表中的元素均小于主元，右子表中的元素均大于主元。主元的选择是将表划分为r
深圳大学实验报告 课程名称：算法分析与复杂性理论 实验项目名称：八皇后问题 学院：计算机与软件学院 专业：软件工程 指导教师：杨烜 报告人：学号：班级：15级软工学术型实验时间：2015-12-08 实验报告提交时间：2015-12-09 教务部制
一．实验目的 1.掌握选回溯法设计思想。 2.掌握八皇后问题的回溯法解法。 二．实验步骤与结果 实验总体思路： 根据实验要求，通过switch选择八皇后求解模块以及测试数据模块操作，其中八皇后模块调用摆放皇后函数模块，摆放皇后模块中调用判断模块。测试数据模块主要调用判断模块进行判断，完成测试。用一维数组保存每行摆放皇后的位置，根据回溯法的思想递归讨论该行的列位置上能否放置皇后，由判断函数Judge()判断，若不能放置则检查该行下一个位置。相应结果和过程如下所示（代码和结果如下图所示）。 回溯法的实现及实验结果： 1、判断函数 代码1： procedure BTrack_Queen(n) //如果一个皇后能放在第K行和X(k)列，则返回true，否则返回false。 global X(1:k);integer i,k i←1 while i
数学建模实验报告 实验一计算课本251页A矩阵的最大特征根和最大特征向量 1 实验目的 通过Wolfram Mathematica软件计算下列A矩阵的最大特征根和最大特征向量。 2 实验过程 本实验运用了Wolfram Mathematica软件计算，计算的代码如下：
3 实验结果分析 从代码的运行结果，可以得到最大特征根为5.07293，最大特征向量为 {{0.262281},{0.474395},{0.0544921},{0.0985336},{0.110298}},实验结果 与标准答案符合。
实验二求解食饵-捕食者模型方程的数值解 1实验目的 通过Wolfram Mathematica或MATLAB软件求解下列习题。 一个生物系统中有食饵和捕食者两种种群，设食饵的数量为x（t），捕食者为y（t），它们满足的方程组为x’(t)=(r-ay)x,y’(t)=-(d-bx)y,称该系统为食饵-捕食者模型。当r=1，d=0.5，a=0.1，b=0.02时，求满足初始条件x（0）=25，y（0）=2的方程的数值解。 2 实验过程 实验的代码如下 Wolfram Mathematica源代码： Clear[x,y] sol=NDSolve[{x'[t] (1-0.1y[t])x[t],y'[t] 0.02x[t]y[t]-0.5y[t],x[0 ] 25,y[0] 2},{x[t],y[t]},{t,0,100}] x[t_]=x[t]/.sol y[t_]=y[t]/.sol g1=Plot[x[t],{t,0,20},PlotStyle->RGBColor[1,0,0],PlotRange->{0,11 0}] g2=Plot[y[t],{t,0,20},PlotStyle->RGBColor[0,1,0],PlotRange->{0,40 }] g3=Plot[{x[t],y[t]},{t,0,20},PlotStyle→{RGBColor[1,0,0],RGBColor[ 0,1,0]},PlotRange->{0,110}] matlab源代码 function [ t,x ]=f ts=0:0.1:15; x0=[25,2]; [t,x]=ode45('shier',ts,x0); End function xdot=shier(t,x)
数学建模与数学实验报告 指导教师__郑克龙___ 成绩____________ 组员1：班级______________ 姓名______________ 学号_____________ 组员2：班级______________ 姓名______________ 学号______________ 实验1.(1)绘制函数cos(tan())y x π=的图像，将其程序及图形粘贴在此。 >> x=-pi:0.01:pi; >> y=cos(tan(pi*x)); >> plot(x,y) -4 -3 -2 -1 1 2 3 4 -1-0.8-0.6-0.4-0.200.20.40.60.8 1 （2）用surf,mesh 命令绘制曲面2 2 2z x y =+，将其程序及图形粘贴在此。（注：图形注意拖放，不要太大）（20分） >> [x,y]=meshgrid([-2:0.1:2]); >> z=2*x.^2+y.^2; >> surf(x,y,z)
-2 2 >> mesh(x,y,z) -2 2 实验2. 1、某校60名学生的一次考试成绩如下:
93 75 83 93 91 85 84 82 77 76 77 95 94 89 91 88 86 83 96 81 79 97 78 75 67 69 68 84 83 81 75 66 85 70 94 84 83 82 80 78 74 73 76 70 86 76 90 89 71 66 86 73 80 94 79 78 77 63 53 55 1)计算均值、标准差、极差、偏度、峰度，画出直方图；2)检验分布的正态性；3)若检验符合正态分布，估计正态分布的参数并检验参数. （20分） 1） >> a=[93 75 83 93 91 85 84 82 77 76 77 95 94 89 91 88 86 83 96 81 79 97 78 75 67 69 68 84 83 81 75 66 85 70 94 84 83 82 80 78 74 73 76 70 86 76 90 89 71 66 86 73 80 94 79 78 77 63 53 55]; >> pjz=mean(a) pjz = 80.1000 >> bzhc=std(a) bzhc = 9.7106 >> jc=max(a)-min(a) jc = 44 >> bar(a)
学号1607070212 《算法设计与分析》 实验报告一 学生姓名张曾然 专业、班级16软件二班 指导教师唐国峰 成绩 计算机与信息工程学院软件工程系 2018 年9 月19 日
实验一：递归策略运用练习 一、实验目的 本次实验是针对递归算法的算法设计及应用练习，旨在加深学生对该算法原理的理解，提高学生运用该算法解决问题的能力。 二、实验步骤与要求 1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料； 2．学生独自完成实验指定内容； 3．实验结束后，用统一的实验报告模板编写实验报告。 4．提交说明： （1）电子版提交说明： a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验一_学号_姓名”， 如“《算法设计与分析》实验一_09290101_张三”。 b 压缩包内为一个“《算法设计与分析》实验一_学号_姓名”命名的顶层文件夹， 其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。 （2）打印版提交说明： a 不可随意更改模板样式。 b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号 字。 c 行间距：单倍行距。 （3）提交截止时间：2018年10月10日16:00。 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： 【必做题】 （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？
数据结构实验报告 实验名称：实验二——利用栈结构实现八皇后问题 学生姓名： 班级： 班内序号： 学号： 日期：2013年11月21日 1．实验要求 （1）实验目的 通过选择下面五个题目之一进行实现，掌握如下内容： 进一步掌握指针、模板类、异常处理的使用 掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力 （2）实验内容 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。 ①可以使用递归或非递归两种方法实现 ②实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线。 （3）代码要求 ①必须要有异常处理，比如删除空链表时需要抛出异常； ②保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 ③递归程序注意调用的过程，防止栈溢出 2. 程序分析 2.1 存储结构 栈（递归）：
2.2 关键算法分析 (1)递归 void SeqStack 算法递归典型例题 实验一：递归策略运用练习 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序： （3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ （4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ （5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ （6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？ （7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 四、实验过程 （一）题目一：…… 1.题目分析 由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数，且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i; matlab 试验报告 姓名 学号 班级 问题：.（插值） 在某海域测得一些点(x,y)处的水深z 由下表给出，船的吃水深度为5英尺，在矩形区域（75，200）*（-50，150）里的哪些地方船要避免进入。 问题的分析和假设： 分析:本题利用插值法求出水深小于5英尺的区域，利用题中所给的数据，可以求出通过空间各点的三维曲面。随后，求出水深小于5英尺的范围。 基本假设：1表中的统计数据均真实可靠。 2矩形区域外的海域不对矩形海域造成影响。 符号规定：x ―――表示海域的横向位置 y ―――表示海域的纵向位置 z ―――表示海域的深度 建模： 1.输入插值基点数据。 2．在矩形区域（75,200）×（－50,150）作二维插值，运用三次插值法。 3．作海底曲面图。 4．作出水深小于5的海域范围，即z=5的等高线。 x y z 129 140 103.5 88 185.5 195 105 7.5 141.5 23 147 22.5 137.5 85.5 4 8 6 8 6 8 8 x y z 157.5 107.5 77 81 162 162 117.5 -6.5 -81 3 56.5 -66.5 84 -33.5 9 9 8 8 9 4 9 求解的Matlab程序代码： x=[129 140 103.5 88 185.5 195 105.5 157.5 107.5 77 81 162 162 117.5]; y=[7.5 141.5 23 147 22.5 137.5 85.5 -6.5 -81 3 56.5 -66.5 84 -33.5]; z=[-4 -8 -6 -8 -6 -8 -8 -9 -9 -8 -8 -9 -4 -9]; cx=75:0.5:200; cy=-50:0.5:150; cz=griddata(x,y,z,cx,cy','cubic'); meshz(cx,cy,cz),rotate3d xlabel('X'),ylabel('Y'),zlabel('Z') %pause figure(2),contour(cx,cy,cz,[-5 -5]);grid hold on plot(x,y,'+') xlabel('X'),ylabel('Y') 计算结果与问题分析讨论： 运行结果： Figure1:海底曲面图： 1．实验要求 【实验目的】 1、进一步掌握指针、模板类、异常处理的使用 2、掌握栈的操作的实现方法 3、掌握队列的操作的实现方法 4、学习使用栈解决实际问题的能力 5、学习使用队列解决实际问题的能力 【实验内容】 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。 提示： 1、可以使用递归或非递归两种方法实现 2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析 2.1 存储结构 存储结构：栈（递归） 2.2 关键算法分析 【设计思想】 由于八皇后问题，可以分解成算法相同的子问题，所以使用递归的方法 【伪代码】 1、输入皇后个数n 2、k=1 3、判断k是否大于n 3.1 是：打印一组可能 3.2 否：循环行位置1~n 判断该位置是否符合要求，若符合记录q[k]的坐标y值 k+1 重复3 【关键算法】 1、递归 void Queen::Queens(int k,int n) { int i; if(k>n) { Print(n); count(); } else { for(i=1;i<=n;i++) if(Isavailable(i,k)) //判断该行中该位置放置‘皇后’是否符合要求 { q[k]=i; //记录改行中该点的位置 Queens(k+1,n); //放置下一行的‘皇后’ } } } 2、判断皇后放置位置是否符合要求 bool Queen::Isavailable(int i,int k) { int j; j=1; while(j 算法设计与分析课程实验项目目录 学生：学号： *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。 本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号实验项目类型设计实验地点机房 学生学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间2012年3月1 日～6月30日温度24℃ 1.实验目的和要求： 熟悉蛮力法的设计思想。 2.实验原理和主要容： 实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验容：以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人 H.E.Dudeney(1857-1930)给出的： S END +MORE MONEY . 这里有两个前提假设： 第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。3.实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 该算法程序代码如下： #include "stdafx.h" #include "time.h" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数：\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l N后问题算法 一、实验目的及要求 所要涉及或掌握的知识： 1. 了解皇后相互攻击的条件：如果任意两个皇后在同一行，同一列或同一对角线，则她们相互攻击。 2. 运用迭代的方法实现6皇后问题，求解得到皇后不相互攻击的一个解 3. 在运用迭代的方法实现编程时，要注意回溯点 二、问题描述及实验内容 对6皇后问题求解，用数组c[1…6]来存皇后的位置。c[i]=j表示第i个皇后放在第j列。 最后程序运行的结果是c[1…6]={1,5,8,6,3,7 } 三、问题分析和算法描述 6-QUEENS的算法表示： 输入：空。 输出：对应于6皇后问题的解的向量c[1…6]={1,5,8,6,3,7} 1. for k=1 to 6 2. c[k]=0 //没有放皇后 3. end for 4. flag=false 5. k=1 6. while k>=1 7.while c[k]<=5 8.c[k]=c[k]+1 9.if c为合法着色 then set flag=ture 且从两个while循环退出 10.else if c是部分解 then k=k+1 11.end while 12. c[k]=0 //回溯并c[k]=0 13. k=k-1 14. end while 15. if flag then output c 16. else output “no solution” 四、具体实现 # include 算法设计与分析实验报告 实验名称统计数字问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1、掌握算法的计算复杂性概念。 2、掌握算法渐近复杂性的数学表述。 3、掌握用C++语言描述算法的方法。 4．实现具体的编程与上机实验，验证算法的时间复杂性函数。 二.实验内容 统计数字问题 1、问题描述 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2， (9) 2、编程任务 给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0，1，2， (9) 三.程序算法 将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数，此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。 四.程序代码 #include int zero=1; for(int i=0;i<=l;i++) //去除前缀0 { s[0]-=zero; zero*=10; } } if(n<10) { for(int i=0;i<=n;i++) { s[i]+=1; } return; }//位数为1位时,出现次数加1 //位数大于1时的出现次数 for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1) { m=1;int i; for(i=1;i 实验报告 （2009/2010学年第一学期） 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程 实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。 要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件：计算机 软件：Visual C++ 三、实验原理及内容（包括操作过程、结果分析等） 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 2、分析LCS问题特征可知，如果Z={z1,z2,……，z k}为它们的最长公共子序列，则它们一定具有以下性质： （1）若x m=y n，则z k=x m=y n，且Z k-1是X m-1和Y n-1的最长公共子序列； （2）若x m≠y n且x m≠z k，则Z是X m-1和Y的最长公共子序列； （3）若x m≠y n且z k≠y n，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若x m=y m，则进一步分解为求解两个（前缀）子字符序列X m-1和Y n-1的最长公共子序列问题； 如果x m≠y n，则原问题转化为求解两个子问题，即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。 实验项目： 八皇后问题 1.实验目的： 通过求解皇后问题，熟悉深度优先搜索法DFS（回溯法（Backtracking Algorithms）技术。 2.实验内容： 由n2 个方块排成n行n列的正方形称为n元棋盘。如果两个皇后位于n元棋盘上的同一行、同一列或同一对角线上，则称它们在互相攻击。现要找出使棋盘上n个皇后互不攻击的布局。编制程序解决上述问题，以n=6运行程序，输出结果。 3.程序简介： 将n个皇后放到一个n*n的方阵中，要求每个皇后不在同一行同一列及同一对角线，我的程序是先把每个皇后放在了第零列，然后再按行检查，不符合要求继续下一列，若已经到这一行的最后一列，还没找到符合要求的位置，则回到上一行。 4.算法设计介绍： 定义一个一维数组，数组的下标是皇后所在位置的行数，数组存的值是皇后所在位置的列数，现将A[0]-A[n-1]都赋成零，然后随着检查的进行，皇后的位置也在不断地变化，最后找到一个符合要求的方阵时，本质上就是一个存放整数的一维数组，数组的下标是行数，存放的值是列数。 5.困难及解答 我很久以前就听说过八皇后问题，没想到现在轮到自己编了，一开始还真是特别糊涂呢，后来老师上课把算法大概讲了一遍，就清楚很多了，要说问题，就是一开始纠结怎么存放皇后，我开始想用二维数组着，后来老师说用一 维数组比较好做，我看了一下老师的算法，就明白了大概，经过一段时间就编出来了 5.心得 我编程变得还是很少，天天下决心说以后多编，也没践行，心想着吧，不挂在嘴上了，努力！ 6.程序清单 /* //我真诚地保证： //我独立完成了整个程序从分析、设计到编码的所有工作。 //如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中 //详细地列举我所遇到的问题，以及别人给我的提示。 //我的程序里中凡是引用到其他程序或文档之处， //例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段, //我都已经在程序的注释里很清楚地注明了引用的出处。 //我从未没抄袭过别人的程序，也没有盗用别人的程序，//不管是修改式的抄袭还是原封不动的抄袭。//我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转 文件名称： 创建者： 创建时间： 2011.4.14 算法设计与分析实验报告 教师： 学号： 姓名： 实验一：串匹配问题 实验目的：(1) 深刻理解并掌握蛮力法的设计思想; (2) 提高应用蛮力法设计算法的技能; (3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。 三、实验要求：( 1) 实现BF 算法; (2 ) 实现BF 算法的改进算法: KMP 算法和BM 算法; (3 ) 对上述 3 个算法进行时间复杂性分析, 并设计实验程序验证 分析结果。 #include "stdio.h" #include "conio.h" #include 《算法设计与分析》递归算法典型例题
数学建模实验报告
数据结构实验报告——栈(八皇后问题)
《算法设计与分析》实验报告
n皇后问题实验报告
算法设计与分析实验报告 统计数字问题
南京邮电大学算法设计实验报告——动态规划法
八皇后实验报告
算法设计与分析实验报告
相关主题
文本预览