实验1 金刚石图案算法
实验1 金刚石图案算法
一、实验目的
在圆的基础上绘制金刚石图案。金刚石图案是一个二维图案，仅使用二维坐标（x,y）就可以绘制：利用数学函数sin（）及cos（）函数计算点坐标，利用MoveTo（）及LineTo （）函数将顶点连接起来，验证算法的正确性，并修改程序，加深对VC++绘图的理解。
二、实验任务
将半径为r的圆周n等份，然后用直线将各等分点两两相连，形成的图案称为“金刚石”图案，并编程实现。
三、实验内容
1.建立工程----“TestDiamond”。
2. 编写Diamond（）函数：
（1）指定n、及r的值；
（2）根据等分点数，计算金刚石图案的等分角“theta”，theta=2*PI/n；
（3）将等分点坐标存储在数组中；
（4）设计二重循环，将各等分点两两相连。
3.OnDraw（）中调用Diamond（）函数。
4.注意：
（1）用到sin（）等数学函数，所以在CtestDiamondView.cpp中添加“#include "math.h"”语句；
（2）为了简单起见（没有使用面向对象的方法定义“点”类，没有使用动态内存分配），初始化存储点坐标的数组x[]和y[]为固定大小，即x[i]和y[i]共同表示第i个点的x和y坐标。
5.代码
（1）Diamond（）函数
void CTestDiamondView::Diamond(CDC *pDC, int n, double r)
{
//n为等分点的个数，r为圆的半径
double Theta;//thta为圆的等分角
double PI=3.1415926;
double x[40];
double y[40];
int MaxX=700;
int MaxY=700;//圆心设定为（350 ，350）
Theta=2*PI/n;
for(int i=0;i { x[i]=r*cos(i*Theta)+MaxX/2; y[i]=r*sin(i*Theta)+MaxY/2; } for(i=0;i<=n-2;i++) //二次循环，点点连接 { for(int j=i+1;j<=n-1;j++) { pDC->MoveTo(int(x[i]),int(y[i])); pDC->LineTo(int(x[j]),int(y[j])); } } } （2）OnDraw（）函数 void CTestDiamondView::OnDraw(CDC* pDC) { CTestDiamondDoc* pDoc = GetDocument(); ASSERT_V ALID(pDoc); // TODO: add draw code for native data here CPen PenBlue(PS_SOLID,1,RGB(0,0,255));//定义蓝色笔pDC->SelectObject(&PenBlue); Diamond(pDC,31, 300 ); } 《计算方法》上机实验报告 班级：XXXXXX 小组成员：XXXXXXX XXXXXXX XXXXXXX XXXXXXX 任课教师：XXX 二〇一八年五月二十五日 前言 通过进行多次的上机实验，我们结合课本上的内容以及老师对我们的指导，能够较为熟练地掌握Newton 迭代法、Jacobi 迭代法、Gauss-Seidel 迭代法、Newton 插值法、Lagrange 插值法和Gauss 求积公式等六种算法的原理和使用方法，并参考课本例题进行了MATLAB 程序的编写。 以下为本次上机实验报告，按照实验内容共分为六部分。 实验一： 一、实验名称及题目： Newton 迭代法 例2.7(P38):应用Newton 迭代法求 在 附近的数值解 ，并使其满足 . 二、解题思路： 设'x 是0)(=x f 的根,选取0x 作为'x 初始近似值,过点())(,00x f x 做曲线)(x f y =的切线L ,L 的方程为))((')(000x x x f x f y -+=,求出L 与x 轴交点的横坐标) (') (0001x f x f x x - =,称1x 为'x 的一次近似值,过点))(,(11x f x 做曲线)(x f y =的切线,求该切线与x 轴的横坐标) (') (1112x f x f x x - =称2x 为'x 的二次近似值,重复以上过程,得'x 的近似值序列{}n x ,把 ) (') (1n n n n x f x f x x - =+称为'x 的1+n 次近似值，这种求解方法就是牛顿迭代法。 三、Matlab 程序代码： function newton_iteration(x0,tol) syms z %定义自变量 format long %定义精度 f=z*z*z-z-1; f1=diff(f);%求导 y=subs(f,z,x0); y1=subs(f1,z,x0);%向函数中代值 x1=x0-y/y1; k=1; while abs(x1-x0)>=tol x0=x1; y=subs(f,z,x0); y1=subs(f1,z,x0); x1=x0-y/y1;k=k+1; end x=double(x1) K 四、运行结果： 实验二： 实验2 古典密码 1.实验目的 （1）了解古典密码中的基本加密运算。 （2）了解几种典型的古典密码体制。 （3）掌握古典密码的统计分析方法。 2.实验内容 （1）古典密码体制 ①简单移位加密（单表代换） 该加密方法中，加密时将明文中的每个字母向前推移K位。经典恺撒密码加密变换就是这种变换，取k=3。 步骤1：打开CAP4软件，并加载实验一附带的“mw.txt”，如图2-1所示。 图2-1加载文件 步骤2：采用恺撒加密方法手工加密“mw.txt”;打开CAP4菜单栏“Cipher”菜单项选择“simple shift”选项，并选择移位值“shift value”为3，加密步骤1中加载的文件，如图2-2所示。 图2-2 参数设置 图2-3加密文件 步骤3：比较二者的加密结果是否相同。 步骤4：点击CAP4软件中的“Simple analysis”下的“shift”键，观察恺撒加密法的可能密钥值，并分析其攻击的难度，如图2-4所示。 图2-4密钥分析 ②仿射密码加密（单表代换） 在仿射密码加密(affine cipher)中，字母表中的字母被赋予一个数字，例如，a=0,b=1,c=2,…,z=25.仿射密码加密法的密钥为0~25之间的数字对（a,b）。a与26的最大公约数必须为1，这就是说能整除a和26的数只有1.现在假设m为明文字母的数字，而c为密文字母的数字，那么，这两个数字之间有如下关系： c=(am+b)(mod 26) m=a-1(c-b)(mod 26) 其中，（mod 26）的操作是：除以26，得其余数。 例如，选取密钥为（7，3）。因为7与26互素，也就是只有公约数1，所以（7，3）可以作为仿射密码的加密钥。将“hot”转换成数字7、14、19，利用仿射等式生成： c(H)=(7×7+3) mod 26=52 mod 26=0,即为字母“a“。 c(O)=(7×14+3) mod 26=101 mod 26=23,即为字母“x“. c(T)=(7×19+3) mod 26=136 mod 26=6,即为字母”g”. 这样，对于这个密钥，”hot”变成了“axg“. 算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 数值实验课试题 本次数值实验课结课作业，请按题目要求内容写一篇文章。按题目要求 人数自由组合，每组所选题目不得相同(有特别注明的题目除外)。试题如下： 1）解线性方程组的Gauss 消去法和列主元Gauss 消去法(2人)/*张思珍，巩艳华*/ 用C 语言将不选主元和列主元Gauss 消去法编写成通用的子程序，然后用你编写的程序求解下列84阶的方程组 ???? ?????? ? ??=??????????? ????????????? ? ?1415151515768 168 168 168 1681684 8382321 x x x x x x 参考书目： 1.《计算机数值方法》，施吉林、刘淑珍、陈桂芝编 2.《数值线性代数》，徐树方、高立、张平文编 3.《数值分析简明教程》，王能超编 2）解线性方程组的平方根法(4人)/*朱春成、黄锐奇、张重威、章杰*/ 用C 语言将平方根法和改进的平方根法编写成通用的子程序，然后用你编写的程序求解对称正定方程组b Ax =，其中 (1)b 随机的选取，系数矩阵为100阶矩阵 ?????? ???? ? ? ?101 1101 1101 1101 1101110 ； (2)系数矩阵为40阶的Hilbert 矩阵，即系数矩阵A 的第i 行第j 列元素为 1 1-+= j i a ij ，向量b 的第i 个分量为∑=-+ = n j i j i b 1 1 1. 参考书目： 1.《计算机数值方法》，施吉林、刘淑珍、陈桂芝编 2.《数值线性代数》，徐树方、高立、张平文编 3.《数值分析简明教程》，王能超编 3）三对角线方程组的追赶法(3人)/*黄佳礼、唐伟、韦锡倍*/ 用C 语言将三对角线方程组的追赶法法编写成通用的子程序，然后用你编写的程序求解如下84阶三对角线方程组 ???? ?????? ? ??=??????????? ????????????? ? ?1415151515768 168 168 168 16816 84 8382321 x x x x x x 参考书目： 1.《计算机数值方法》，施吉林、刘淑珍、陈桂芝编 2.《数值分析简明教程》，王能超编 4）线性方程组的Jacobi 迭代法(3人)/*周桂宇、杨飞、李文军*/ 用C 语言将Jacobi 迭代法编写成独立的子程序，并用此求解下列方程组， 精确到小数点后5位 ???? ? ??=????? ??????? ? ?-149012 2111221 3 2 1 x x x 参考书目： 1.《计算机数值方法》，施吉林、刘淑珍、陈桂芝编 2.《数值线性代数》，徐树方、高立、张平文编 3.《数值分析简明教程》，王能超编 5）线性方程组的Gauss-Seidel 迭代法(3人)/*张玉超、范守平、周红春*/ 用C 语言将Gauss-Seidel 迭代法编写成独立的子程序，并用此求解下列方程组，精确到小数点后5位 ???? ? ??=????? ??????? ? ?--39721 1111112 3 2 1 x x x 参考书目： 1.《计算机数值方法》，施吉林、刘淑珍、陈桂芝编 2.《数值线性代数》，徐树方、高立、张平文编 3.《数值分析简明教程》，王能超编 6）解线性方程组的最速下降法法(2人)/*赵育辉、阿热孜古丽*/ 用C 语言将最速下降法编写成通用的子程序，然后用你编写的程序求解对称 《数据结构与算法设计》 实验报告 ——实验一 学院： 班级： 学号： 姓名： 一、实验目的 1.通过实验实践、巩固线性表的相关操作； 2.熟悉VC环境，加强编程、调试的练习； 3.用C语言编写函数，实现循环链表的建立、插入、删除、取数据等基本操作； 4.理论知识与实际问题相结合，利用上述基本操作实现约瑟夫环。 二、实验内容 1、采用单向环表实现约瑟夫环。 请按以下要求编程实现： ①从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的 结点编号依次为1，2，……，m。 ②从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到 第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点 的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出 了这个环表的全部结点为止。 三、程序设计 1、概要设计 为实现上述程序功能，应用单向环表寄存编号，为此需要建立一个抽象数据类型：单向环表。 （1）、单向环表的抽象数据类型定义为： ADT Joseph{ 数据对象：D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0} 数据关系：R1={ 曲线拟合的数值计算方法实验 【摘要】实际工作中，变量间未必都有线性关系，如服药后血药浓度与时间的关系；疾病疗效与疗程长短的关系；毒物剂量与致死率的关系等常呈曲线关系。曲线拟合（curve fitting）是指选择适当的曲线类型来拟合观测数据，并用拟合的曲线方程分析两变量间的关系。曲线直线化是曲线拟合的重要手段之一。对于某些非线性的资料可以通过简单的变量变换使之直线化，这样就可以按最小二乘法原理求出变换后变量的直线方程，在实际工作中常利用此直线方程绘制资料的标准工作曲线，同时根据需要可将此直线方程还原为曲线方程，实现对资料的曲线拟合。常用的曲线拟合有最小二乘法拟合、幂函数拟合、对数函数拟合、线性插值、三次样条插值、端点约束。 关键词曲线拟合、最小二乘法拟合、幂函数拟合、对数函数拟合、线性插值、三次样条插值、端点约束 一、实验目的 1.掌握曲线拟合方式及其常用函数指数函数、幂函数、对数函数的拟合。 2.掌握最小二乘法、线性插值、三次样条插值、端点约束等。 3.掌握实现曲线拟合的编程技巧。 二、实验原理 1.曲线拟合 曲线拟合是平面上离散点组所表示的坐标之间的函数关系的一种数据处理方法。用解析表达式逼近离散数据的一种方法。在科学实验或社会活动中，通过 实验或观测得到量x与y的一组数据对（X i ，Y i )（i=1，2，...m），其中各X i 是彼此不同的。人们希望用一类与数据的背景材料规律相适应的解析表达式，y=f(x，c）来反映量x与y之间的依赖关系，即在一定意义下“最佳”地逼近或 拟合已知数据。f(x，c)常称作拟合模型，式中c=(c 1，c 2 ，…c n )是一些待定参 数。当c在f中线性出现时，称为线性模型，否则称为非线性模型。有许多衡量拟合优度的标准，最常用的一种做法是选择参数c使得拟合模型与实际观测值在 实验报告名称 班级：学号：姓名：成绩： 1实验目的 1）通过对二分法与牛顿迭代法作编程练习与上级运算，进一步体会二分法与牛顿迭代法的不同特点。 2）编写割线迭代法的程序，求非线性迭代法的解，并与牛顿迭代法。 2 实验内容 用牛顿法和割线法求下列方程的根 x^2-e^x=0; x*e^x-1=0; lgx+x-2=0; 3实验步骤 1)根据二分法和牛顿迭代法，割线法的算法编写相应的求根函数； 2)将题中所给参数带入二分法函数，确定大致区间； 3)用牛顿迭代法和割线法分别对方程进行求解； 3 程序设计 牛顿迭代法x0=1.0; N=100; k=0; eps=5e-6; delta=1e-6; while(1) x1=x0-fc1(x0)/fc2(x0); k=k+1; if k>N disp('Newmethod failed') break end if(abs(x1-x0) 算法设计与分析实验报告 学院：信息学院 专业：物联网1101 姓名：黄振亮 学号：20113379 2013年11月 目录 作业1 0-1背包问题的动态规划算法 (7) 1.1算法应用背景 (3) 1.2算法原理 (3) 1.3算法描述 (4) 1.4程序实现及程序截图 (4) 1.4.1程序源码 (4) 1.4.2程序截图 (5) 1.5学习或程序调试心得 (6) 作业2 0-1背包问题的回溯算法 (7) 2.1算法应用背景 (3) 2.2算法原理 (3) 2.3算法描述 (4) 2.4程序实现及程序截图 (4) 2.4.1程序源码 (4) 2.4.2程序截图 (5) 2.5学习或程序调试心得 (6) 作业3循环赛日程表的分治算法 (7) 3.1算法应用背景 (3) 3.2算法原理 (3) 3.3算法描述 (4) 3.4程序实现及程序截图 (4) 3.4.1程序源码 (4) 3.4.2程序截图 (5) 3.5学习或程序调试心得 (6) 作业4活动安排的贪心算法 (7) 4.1算法应用背景 (3) 4.2算法原理 (3) 4.3算法描述 (4) 4.4程序实现及程序截图 (4) 4.4.1程序源码 (4) 4.4.2程序截图 (5) 4.5学习或程序调试心得 (6) 作业1 0-1背包问题的动态规划算法 1.1算法应用背景 从计算复杂性来看,背包问题是一个NP难解问题。半个世纪以来,该问题一直是算法与复杂性研究的热点之一。另外,背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、网络信息安全等应用中具有重要的价值。如果能够解决这个问题那么则具有很高的经济价值和决策价值，在上述领域可以获得最大的价值。本文从动态规划角度给出一种解决背包问题的算法。 1.2算法原理 1.2.1、问题描述： 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi ∈{0,1}, ?∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。 1.2.2、最优性原理： 设(y1,y2,…,yn)是 (3.4.1)的一个最优解.则(y2,…,yn)是下面相应子问题的一个最优解: 证明:使用反证法。若不然,设(z2,z3,…,zn)是上述子问题的一个最优解,而(y2,y3,…,yn)不是它的最优解。显然有 ∑vizi > ∑viyi (i=2,…,n) 且 w1y1+ ∑wizi<= c 因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n) 说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的一个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,矛盾。 1.2.3、递推关系： 实验一误差分析 实验1.1（病态问题） 实验目的：算法有“优”与“劣”之分，问题也有“好”与“坏”之别。对数值方法的研究而言，所谓坏问题就是问题本身对扰动敏感者，反之属于好问题。通过本实验可获得一个初步体会。 数值分析的大部分研究课题中，如线性代数方程组、矩阵特征值问题、非线性方程及方程组等都存在病态的问题。病态问题要通过研究和构造特殊的算法来解决，当然一般要付出一些代价（如耗用更多的机器时间、占用更多的存储空间等）。 问题提出：考虑一个高次的代数多项式 显然该多项式的全部根为1,2,…,20共计20个，且每个根都是单重的。现考虑该多项式的一个扰动 其中ε（1.1）和（1.221,,,a a 的输出b ”和“poly ε。 （1（2 （3）写成展 关于α solve 来提高解的精确度，这需要用到将多项式转换为符号多项式的函数poly2sym,函数的具体使用方法可参考Matlab 的帮助。 实验过程： 程序： a=poly(1:20); rr=roots(a); forn=2:21 n form=1:9 ess=10^(-6-m); ve=zeros(1,21); ve(n)=ess; r=roots(a+ve); -6-m s=max(abs(r-rr)) end end 利用符号函数：（思考题一）a=poly(1:20); y=poly2sym(a); rr=solve(y) n 很容易的得出对一个多次的代数多项式的其中某一项进行很小的扰动，对其多项式的根会有一定的扰动的，所以对于这类病态问题可以借助于MATLAB来进行问题的分析。 学号：06450210 姓名：万轩 实验二插值法 数值分析上机实验报告 《数值分析》上机实验报告 1.用Newton 法求方程 X 7-X 4+14=0 在（0.1，1.9）中的近似根（初始近似值取为区间端点，迭代6次或误差小于0.00001）。 1.1 理论依据： 设函数在有限区间[a ，b]上二阶导数存在，且满足条件 {}α?上的惟一解在区间平方收敛于方程所生的迭代序列 迭代过程由则对任意初始近似值达到的一个中使是其中上不变号 在区间],[0)(3,2,1,0,) (') ()(],,[x |))(),((|,|,)(||)(|.4;0)(.3],[)(.20 )()(.110......b a x f x k x f x f x x x Newton b a b f a f mir b a c x f a b c f x f b a x f b f x f k k k k k k ==- ==∈≤-≠>+ 令 )9.1()9.1(0)8(4233642)(0)16(71127)(0)9.1(,0)1.0(,1428)(3 2 2 5 333647>?''<-=-=''<-=-='<>+-=f f x x x x x f x x x x x f f f x x x f 故以1.9为起点 ?? ?? ? ='- =+9.1)()(01x x f x f x x k k k k 如此一次一次的迭代，逼近x 的真实根。当前后两个的差<=ε时，就认为求出了近似的根。本程序用Newton 法求代数方程(最高次数不大于10)在（a,b ）区间的根。 1.2 C语言程序原代码： #include 实验一古典密码-Vigenere算法 班级：学号：姓名： 一、实验目的 1、理解简单加密算法的原理； 2、掌握Vigenere密码的原理，完成Vigenere密码加解密程序的编写； 3、通过实验，加深对古典密码体制的了解，掌握对字符进行灵活处理的方法。 二，实验要求 根据Vigenere密码的原理编写程序，对输入的符号串能够根据设置的密钥分别正确实现Vigenere加密和解密功能。 三，实验过程及内容 源程序 #include "stdio.h" #include "string.h" #define BUF_MAX 100 static int square[27][27]; //密钥统一转换为大写字母 void UpperKey(char key[]) { int key_length = strlen(key); for(int i = 0; i < key_length; i++) { if (key[i] >= 'a' && key[i] <= 'z') { key[i] -= 32; } } } //Vigenere加密 void VigenereEncrypt(char word[], char key[]) { char text[BUF_MAX]; int key_length = strlen(key); int word_length = strlen(word); int i, j, k; for(i = 0; i < word_length; i++) { j = i % key_length; if (word[i] >= 'a' && word[i] <= 'z') { k = word[i] - 'a'; k = (k + key[j] - 'A') % 26; text[i] = k + 'a'; } else if (word[i] >= 'A' && word[i] <= 'Z') { k = word[i] - 'A'; k = (k + key[j] - 'A') % 26; text[i] = k + 'A'; } else { text[i] = word[i]; } } text[i] = '\0'; printf("Encrypt string:"); puts(text); } //Vigenere解密 void VigenereDecript(char en_word[], char key[]) { char word[BUF_MAX]; int key_length = strlen(key); int word_length = strlen(en_word); int i, j, k; for(i = 0; i < word_length; i++) { j = i % key_length; if (en_word[i] >= 'a' && en_word[i] <= 'z') 银行家算法设计实验报告 银行家算法设计实验报告 一．题目分析 1.银行家算法： 我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。 当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。 2.基本要求： （1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。 （2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。 （3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况： A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回 B. 所申请的资源未大于其所需资源， 但大于系统此时的可利用资源，提 示分配不合理不予分配并返回。 C. 所申请的资源未大于其所需资源， 亦未大于系统此时的可利用资源，预 分配并进行安全性检查： a. 预分配后系统是安全的，将该进 程所申请的资源予以实际分配并 打印后返回。 b. 与分配后系统进入不安全状态，提示系统不安全并返回。 （4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入。 3.目的： 根据设计题目的要求，充分地分析和理解题 目，叙述系统的要求，明确程序要求实现的功能以及限制条件。 明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。 本科实验报告 课程名称：计算机数值方法 实验项目：方程求根、线性方程组的直接解 法、线性方程组的迭代解法、代数插值和最 小二乘拟合多项式 实验地点：行勉楼 专业班级： ******** 学号： ********* 学生姓名： ******** 指导教师：李誌，崔冬华 2016年 4 月 8 日 y = x*x*x + 4 * x*x - 10; return y; } float Calculate(float a,float b) { c = (a + b) / 2; n++; if (GetY(c) == 0 || ((b - a) / 2) < 0.000005) { cout << c <<"为方程的解"<< endl; return 0; } if (GetY(a)*GetY(c) < 0) { return Calculate(a,c); } if (GetY(c)*GetY(b)< 0) { return Calculate(c,b); } } }; int main() { cout << "方程组为：f(x)=x^3+4x^2-10=0" << endl; float a, b; Text text; text.Getab(); a = text.a; b = text.b; text.Calculate(a, b); return 0; } 2.割线法： // 方程求根（割线法）.cpp : 定义控制台应用程序的入口点。// #include "stdafx.h" #include"iostream" 心得体会 使用不同的方法，可以不同程度的求得方程的解，通过二分法计算的程序实现更加了解二分法的特点，二分法过程简单，程序容易实现，但该方法收敛比较慢一般用于求根的初始近似值，不同的方法速度不同。面对一个复杂的问题，要学会简化处理步骤，分步骤一点一点的循序处理，只有这样，才能高效的解决一个复杂问题。 计算方法实验报告 班级： 学号： 姓名： 成绩： 1 舍入误差及稳定性 一、实验目的 （1）通过上机编程，复习巩固以前所学程序设计语言及上机操作指令； （2）通过上机计算，了解舍入误差所引起的数值不稳定性 二、实验内容 1、用两种不同的顺序计算10000 21n n -=∑，分析其误差的变化 2、已知连分数() 1 01223//(.../)n n a f b b a b a a b =+ +++，利用下面的算法计算f ： 1 1 ,i n n i i i a d b d b d ++==+ (1,2,...,0 i n n =-- 0f d = 写一程序，读入011,,,...,,,...,,n n n b b b a a 计算并打印f 3、给出一个有效的算法和一个无效的算法计算积分 1 041 n n x y dx x =+? (0,1,...,1 n = 4、设2 2 11N N j S j == -∑ ，已知其精确值为1311221N N ?? -- ?+?? （1）编制按从大到小的顺序计算N S 的程序 （2）编制按从小到大的顺序计算N S 的程序 （3）按两种顺序分别计算10001000030000,,,S S S 并指出有效位数 三、实验步骤、程序设计、实验结果及分析 1、用两种不同的顺序计算10000 2 1n n -=∑，分析其误差的变化 （1）实验步骤： 分别从1~10000和从10000~1两种顺序进行计算，应包含的头文件有stdio.h 和math.h （2）程序设计： a.顺序计算 #include 实验报告 （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]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。 实验报告 学院（系）名称： 主程序部分列选主元部分 实验结果： 一．列主元消去法 输入各个数据，最终使用列选主元法，得到结果为：x1=x2=x3=1二．高斯-赛德尔迭代法 输入各个数据，输出每一步迭代数据，最终结果为：x1=0.285716，附录（源程序及运行结果） 一．列主元高斯消去法 #include 实验1: 古典密码 一、实验名称和性质 二、实验目的 掌握古典密码体制中的基本加密解密运算，如加法密码、仿射密码等，几种典型的古典密码体制，如Hill体制，以及关于这些古典密码体制的一些破译方法。 三、实验的软硬件环境要求 硬件环境要求： 单机，无需上Internet网。 使用的软件名称、版本号以及模块： 使用Matlab，版本6.0或以上。 四、知识准备 前期要求掌握的知识： Matlab编程 实验相关理论或原理： 古典密码的基本加密解密运算，几种典型古典密码的加密解密算法。 实验流程： 五、实验要求和注意事项 1．完成给出的程序中标有“-----------------------”部分的编程。 2．参照例子的做法，完成实验题目。要求给出完整的过程，包括程序，实验结果。 六、实验步骤和内容 1．基本的加密解密运算 例1. 使用加法密码（或称为移位密码）获得密文kddkmu，尝试所有的可能性来解密它。解：编写allshift程序，调用该程序 allshift('kddkmu') 运行结果为 kddkmu leelnv mffmow nggnpx ohhoqy piiprz qjjqsa rkkrtb sllsuc tmmtvd unnuwe voovxf wppwyg xqqxzh yrryai zsszbj attack 是列表上出现的唯一单词，所以它就是明文buubdl cvvcem dwwdfn exxego fyyfhp gzzgiq haahjr ibbiks jccjlt function y = allshift(x); % This function displays all of the shifts of the message x for j=0:25, ------------ ; disp(z); end function y = shift(x,b); % This function performs the shift encryption function % y = x + b mod 26 % We assume that x is a text string and b is a number % The result is kept in text representation xnum=text2int(x); -----------------------; y=int2text(ynum); function y = text2int (x) % This function takes the letter in the string x and converts % it to an integer. % The convention for this function is % a --> 0 % b --> 1 % and so on... if ( (x < 'a') | (x > 'z') ), error('Text character out of range a-z'); end; y=x - 'a'; %It helps to know Matlab tricks 算法与分析实验报告软件工程专业 安徽工业大学 指导老师：许精明 实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 一：实验目的 1：掌握动态规划算法的基本思想，学会用其解决实际问题。 2：通过几个基本的实验，提高算法分析与设计能力，提高动手操作能力和培养良好的编程习惯。 二：实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 实验一：杨辉三角 问题分析： ①每行数字左右对称，由1开始逐渐变大，然后变小，回到1。 ②第n行数之和为2^n。 ③下一行每个数字等于上一行的左右两个数字之和。 算法设计及相关源代码： public void yanghui(int n) { int[] a = new int[n]; if(n==1){ System.out.println(1); }else if(n==2) { System.out.print(1 + " " +1); }else{ a[1]=1; System.out.println(a[1]); a[2]=1; System.out.println(a[1]+" "+a[2]); for(int i=3;i<=n;i++){ a[1]=a[i]=1; for(int j=i-1;j>1;j--){ a[j]=a[j]+a[j-1]; } for(int j=1;j<=i;j++){ System.out.print(a[j]+" "); } System.out.println(); } } } 实验结果：n=10 实验二：0-1背包问题 问题分析：：令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就 j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数: (1) V(i,0)=V(0,j)=0 (2) V(i,j)=V(i-1,j) j计算方法上机实验报告
实验二 古典密码
算法设计与分析实验报告贪心算法
数值计算实验课题目
北京理工大学《数据结构与算法设计》实验报告实验一
曲线拟合的数值计算方法实验
计算方法第二章方程求根上机报告
算法设计与实验报告讲解
数值分析实验报告1
数值分析上机实验报告
实验一 古典密码-Vigernere算法
银行家算法设计实验报告
太原理工大学数值计算方法实验报告
计算方法上机实习题大作业(实验报告).
南京邮电大学算法设计实验报告——动态规划法
数值计算方法实验5
古典密码
算法与设计实验报告