2011-2012(1)《算法分析与设计》上机指导书
《算法分析与设计》实验指导书（适用于计算机科学与技术、软件工程专业）
计算机科学与技术学院
软件教研室
2011-8
目录
实验一算法分析 (3)
实验二分治策略 (4)
实验三堆排序 (5)
实验四动态规划 (6)
实验五贪心算法 (8)
实验六图算法1-基本图算法 (10)
实验七图算法2-最小生成树和单源顶点最短路径 (12)
实验八图算法3-所有点对最短路径.14 附录一实验规范. 15
实验一算法分析
一、实验目的及任务
1、使学生通过插入排序和合并排序的算法实现，理解算法的概念并且通过运行时间比较其时间复杂度。
2、体会合并排序的分治方法的三个步骤：分解、递归求解和合并。
3、了解渐近记号的意义和初步分析算法复杂性。
二、实验环境
c++或java或Turbo c
三、问题描述
Input: A sequence of n numbers
Output: A permutation (reordering)
四、编程任务
给定长度为n的一个序列，对其进行插入排序和合并排序
五、数据输入
随机产生10000以上的数据，放入输入文件input.txt，用来进行排序
六、结果输出
排序后的结果和两种排序算法的运行时间输出到文件output.txt
七、实验报告内容
见《算法分析与设计》实验规范。
实验二分治策略
一、实验目的及任务
1、掌握递归和分治策略的概念和基本思想，分析并掌握“快速排序”问题的分治算法；
2、分治算法思想解决median问题。
二、实验环境
c++或java或Turbo c
三、问题描述
(1) Input: A sequence of n numbers
Output: A permutation (reordering)
(2) Input: A set A of n (distinct) numbers and a number i, with 1 ≤i ≤n.
Output: The element x∈A that is larger than exactly i - 1 other elements of A.
四、编程任务
给定长度为n的一个序列，对其进行快速排序和求第i小数
五、数据输入
A=<13,19,9,5,12,8,7,4,11,2,6,21>
六、结果输出
将排序结果输出到文件output.txt。如果不存在所要求的第i小数，则输出-1。
七、实验报告内容
见《算法分析与设计》实验规范。
实验三堆排序
一、实验目的及任务
1、了解堆的性质； 2利用堆构成一个优先队列，并实现相关的函数功能； 3为图算法做好准备。
二、实验环境
c++或java或Turbo c
三、问题描述
A priority queue is a data structure for maintaining a set S of elements, each with an associated value called a key. A max-priority queue supports the following operations.
. INSERT(S, x) inserts the element x into the set S. This operation could be written as S←S ∪ {x}.
. MAXIMUM(S) returns the element of S with the largest key.
. EXTRACT-MAX(S) removes and returns the element of S with the largest key.
. INCREASE-KEY(S, x, k) increases the value of element x's key to the new value k,
which is assumed to be at least as large as x's current key value. 四、编程任务
编程建立最大堆，构造优先队列并实现以上的相关操作。
五、数据输入
A=<15，13，9，5，12，8，7，4，0，6，2，1>
六、结果输出
执行INSERT(A, 10)，EXTRACT-MAX(A)，将结果输出到文件output.txt。
七、实验报告内容
见《算法分析与设计》实验规范。
实验四动态规划
一、实验目的及任务
1、掌握动态规划算法的基本步骤：找出最优解的性质，并刻画其结构特征；递
归地定义最优值；以自底向上的方式计算出最优值；根据计算最优值时得到的信息，构造最优解。
2、熟悉最长公共子序列问题的算法，设计一个算法解决编辑距离问题。
二、实验环境
c++或java或Turbo c
三、问题描述
1 若给定序列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的最长公共子序列。
2 设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括：山出一个字符、插入一个字符、将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作称为字符串A到字符串B的编辑距离，记为d(A,B)。试设计一个有效算法，对任意给定的两个字符串，计算出它们的编辑距离d(A,B)。
四、编程任务
1 求X和Y的最长公共子序列长度以及最长公共子序列
2 对于给定的字符串A和字符串B，编程计算其编辑距离d(A,B)。
五、数据输入
1由文件input.txt提供输入数据，X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A}。2由文件input.txt提供输入数据。文件的第1行是字符串A，文件的第2行是字符串B。A:fxpimu B:xwrs
六、结果输出
1程序运行结束时，将编程计算出的最长公共子序列长度以及最长公共子序列输出到文件output.txt中。
2 程序运行结束时，将编辑距离d(A,B)输出到文件output.txt的第1行中。
七、实验报告内容
见《算法分析与设计》实验规范。
实验五贪心算法
一、实验目的及任务
1、掌握贪心算法的基本性质。2 贪心算法与动态规划的区别。3 贪心算法解决活动安排问题和背包问题。
二、实验环境
c++或java或Turbo c
三、问题描述
1 有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si 2 0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。 四、编程任务 1 在所给的活动集合中选出最大的相容活动子集合。 2 计算背包问题/0-1背包问题背包的价值 五、数据输入 1 i 1 2 3 4 5 6 7 8 9 10 11 si 1 3 0 5 3 5 6 8 8 2 12 fi 4 5 6 7 8 9 10 11 12 13 14 2 W={10,100,120} V={10,20,30} C=50 六、结果输出 1、将编程计算出的最长最大活动安排结果输出到文件output1.txt。 2、将编程计算出的背包价值输出到文件output2.txt。 七、实验报告内容 见《算法分析与设计》实验规范。 实验六图算法1-基本图算法 一、实验目的及任务 1、掌握图邻接表的存储方法； 2、掌握深度优先遍历算法(DFS)； 3、利用深度优先遍历的timestamps进行拓扑排序或计算有向图的强连通分支； 二、实验环境 c++或java或Turbo c 三、问题描述 Given G=(V,E) In DFS, edges are explored out the most recently discovered vertex v that still has unexplored edges leaving it. When v's edges have been explored, the search "backtracks" to explore edges leaving the vertex from which v was discovered. Besides creating a depth-first forest, DFS also timestamps each vertex. Each vertex v has two timestamps: the first timestamp d[v] records when v is first discovered, and the second one f[v] records when the search finishes examining v's adjacency list. A topological sort of a directed acyclic graph (DAG) G = (V;E) is a linear ordering of all its vertices such that if G contains an edge (u; v), then u appears before v in the ordering (if the graph is cyclic, then no linear ordering is possible). A strongly connected component (SCC) of a directed graph G = (V;E) is a maximal subset of vertices C ? V such that ?u, v ∈C, we have u→v and v→ u. 四、编程任务 1 、深度优先遍历； 2、利用深度优先遍历的timestamps进行拓扑排序；3、利用深度优先遍历的timestamps进行有向图的强连通分支； 五、数据输入 六、结果输出 1、将编程计算出深度优先遍历结果输出到文件output1.txt； 2、将编程进行拓扑排序结果输出到文件output2.txt； 3、将编程进行有向图的强连通分支的结果输出到文件output3.txt。 七、实验报告内容 见《算法分析与设计》实验规范。 实验七图算法2-最小生成树和单源顶点最短路径 一、实验目的及任务 1、应用优先队列求最小生成树的Prim 算法，了解其中的贪心算法的设计思想； 2、应用优先队列求单源顶点的最短路径Dijkstra算法，了解贪心算法的设计思想，并掌握松弛技巧。 二、实验环境 c++或java或Turbo c 三、问题描述 1、 Given a connected, undirected graph G = (V,E), where ?(u, v) ∈ E has a weight w(u, v). We intend to find an acyclic subset T ? E that connects all the vertices and whose total weight w(T) =∑ ∈T v u v u w ) , ( ) , ( is minimized. Since T is acyclic and connects all vertices, it must be a tree, called spanning tree. The problem to find such T is called minimum spanning tree (MST) problem. 2、 Dijkstra's algorithm solves the single-source shortest-paths problem on a weighted, directed graph G = (V, E) for the case in which all edge weights are nonnegative. Dijkstra's algorithm maintains a set S of vertices whose final shortest-path weights from the source s have already been determined. The algorithm repeatedly selects the vertex u ∈V –S with the minimum shortest-path estimate, adds u to S, and relaxes all edges leaving u. 四、编程任务 1、对于给定的赋权图G，编程计算图的最大边权最小生成树。 2、对于给定的赋权图G，编程计算图的单源顶点最短路径。 五、数据输入 1 由文件input.txt 给出输入数据。第1 行有 2 个正整数n 和m，表示给定的图G 有n 个 顶点和m条边，顶点编号为1，2，…，n。接下来的m行中，每行有3 个正整数u,v,w，表 示图G 的一条边(u,v)及其边权w。 2 六、结果输出 1 将编程计算出的最大边权最小生成树的最大边权输出到文件output1.txt。如果不存在所 要求的最大边权最小生成树，则输出-1。 输入文件示例 input.txt 7 9 1 2 28 1 6 10 2 7 14 2 3 16 6 5 25 7 5 24 7 4 18 3 4 12 5 4 22 输出文件示例 output.txt 25 2 将编程计算出单源顶点最短路径结果输出到output2.txt。 七、实验报告内容 见《算法分析与设计》实验规范 实验八图算法3-所有点对最短路径 一、实验目的及任务 1、掌握Matrix multiplication 和Floyd-Warshall algorithm的实现； 2、了解这两种算法的不同； 3、进一步了解所有点对最短路径问题中的动态规划设计思想。 二、实验环境 c++或java或Turbo c 三、问题描述 Given a weighted, directed graph G = (V,E), for any u, v ∈ V , find a shortest path from u to v. 四、编程任务 对于给定的赋权有向图G，编程计算图的所有点对的最短路径。 五、数据输入 六、结果输出 将编程计算出的所有点对的最短路径输出到文件output.txt。 七、实验报告内容 见《算法分析与设计》实验规范 《算法分析与设计》实验规范 一、实验课的意义 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变"活"，起到深化理解和灵活掌握教学内容的目的。平时的练习较偏重于如何编写功能单一的"小"算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。 二、实验步骤 常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然算法分析与设计课程中的实验题目的远不如从实际问题中的复杂程度高，但为了培养一个软件工作者所应具备的科学工作的方法和作风，也应遵循以下五个步骤来完成实验题目： 1．问题分析和任务定义 在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么?是否接受非法的输入?对非法输入的回答方式是什么等。还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据。 2．逻辑设计和详细设计 在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构 清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。 3．编码实现和静态检查 编码是把详细设计的结果进一步求精为程序设计语言程序。如果基于详细设计的伪码算法就能直接在键盘上输入程序的话，则可以不必用笔在纸上写出编码，而将这一步的工作放在上机准备之后进行，即在上机调试之前直接用键盘输入。 然而，不管你是否写出编码的程序，在上机之前，认真的静态检查是必不可少的。静态检查主要有两种方法，一是用一组测试数据手工执行程序(通常应先分模块检查)；二是通过对程序深入全面地理解程序逻辑，在这个过程中再加入一些注解和断言。如果程序中逻辑概念清楚，后者将比前者有效。 4．上机准备和上机调试 上机准备包括以下几个方面： (1) 注意同一高级语言文本之间的差别。 (2)熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。 (3)掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。应该能够熟练运用高级语言的程序调试器DBBUG调试程序。 (4)上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行，自底向上，即先调试低层函数。在调试过程中可以不断借助DEBUG的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，此时应动手确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。 5．总结和整理实验报告 要求采用以下模板完成实验报告 算法分析与设计程序设计上机实验报告 课程名称：班级：实验日期：姓名：学号：指导教师：实验名称：实验序号：实验成绩：1．算法问题描述 明确描述所要解决的问题，强调的该问题要做什么?主要包括： (1)输入的形式和输入值的范围； (2)输出的形式； (3)程序所能达到的功能； (4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 2．概要设计 说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。 3．详细设计 实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度应能够按照伪码算法在计算机键盘上直接输入高级程序设计语言程序)；画出函数的调用关系图。 4．调试分析 内容包括： (1)调试过程中遇到的问题是如何解决的以及对设计与实现的讨论和分析； (2)算法的时间复杂性(包括基本操作和其他算法的时间复杂性的分析)和改进 设想； (3)设计过程的经验和体会。 5．用户使用说明 说明如何使用你编写的程序，详细列出每一步的操作步骤。 6．测试结果 列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。 7．附录 带注释的源程序。程序文件名的清单。 值得注意的是，实验报告的各种文档资料，要在程序开发的过程中逐渐充实形成，而不是最后补写。 编写人：宋玲 审核人：李晓峰 批准人：李盛恩 编写日期：2006年12月30日 数值分析上机题 第一章 17.（上机题）舍入误差与有效数 设∑=-= N j N j S 2 2 11 ，其精确值为）111-23（21+-N N 。 （1）编制按从大到小的顺序1 -1 ···1-311-21222N S N +++=，计算N S 的通用 程序； （2）编制按从小到大的顺序1 21 ···1)1(111 222-++--+ -=N N S N ，计算N S 的通用程序； （3）按两种顺序分别计算210S ,410S ,610S ,并指出有效位数（编制程序时用单精度）； （4）通过本上机题，你明白了什么？ 解： 程序： （1）从大到小的顺序计算1 -1 ···1-311-21222N S N +++= ： function sn1=fromlarge(n) %从大到小计算sn1 format long ; sn1=single(0); for m=2:1:n sn1=sn1+1/(m^2-1); end end （2）从小到大计算1 21 ···1)1(111 2 22 -++--+-= N N S N function sn2=fromsmall(n) %从小到大计算sn2 format long ; sn2=single(0); for m=n:-1:2 sn2=sn2+1/(m^2-1); end end （3） 总的编程程序为： function p203() clear all format long; n=input('please enter a number as the n:') sn=1/2*(3/2-1/n-1/(n+1));%精确值为sn fprintf('精确值为%f\n',sn); sn1=fromlarge(n); fprintf('从大到小计算的值为%f\n',sn1); sn2=fromsmall(n); fprintf('从小到大计算的值为%f\n',sn2); function sn1=fromlarge(n) %从大到小计算sn1 format long; sn1=single(0); for m=2:1:n sn1=sn1+1/(m^2-1); end end function sn2=fromsmall(n) %从小到大计算sn2 format long; sn2=single(0); for m=n:-1:2 sn2=sn2+1/(m^2-1); end end end 运行结果： 网络教育课程考试复习题及参考答案算法分析与设计一、名词解释：1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题7.最小生成树二、简答题： 1.备忘录方法和动态规划算法相 比有何异同？简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。10.简述分析贪心算法与动态规划 算法的异同。三、算法编写及算法应用分析题： 1.已知有3个物品： (w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。③给出上述算法的递归算法。④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。已知，=1，2，3，4，5，6，=5，=10，=3，=12，=5，=50，=6，kijr*r1234567ii1求矩阵链积A×A×A×A×A×A的最佳求积顺序（要求给出计算步骤）。1234564.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。6.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：①删除一个字符。②插入一个字符。③将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。be2g212ad323182cf2h 8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[s，f ]，活动i,j相容的条件是：sj≥f ii，问题的解表示为(x| x =1，2…，n,)，x表示顺序为i的活动编号活动，求一个相容的活动子集，iiii且安排的活动数目最多。xxx10.设、、是一个三角形的三条边，而且x+x+x=14。请问有多少种不同的三角形？给出解答过程。12312311. 第一章算法概述 1.算法：解决问题的一种方法或过程；由若干条指令组成的有穷指令。 2.算法的性质： 1)输入：有零个或多个输入 2)输出：有至少一个输出 3)确定性：每条指令是清晰的、无歧义的 4)有限性：每条指令的执行次数和时间都是有限的 3.算法与程序的区别 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有限性 4.算法复杂性分析 1)算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复 杂性，需要空间资源的量称为空间复杂性 2)三种时间复杂性：最坏情况、最好情况、平均情况 3)可操作性最好且最有实际价值的是最坏情况下的时间复杂性 第二章递归与分支策略 1.递归概念：直接或间接调用自身的算法 2.递归函数：用函数自身给出定义的函数 3.递归要素：边界条件、递归方程 4.递归的应用 ?汉诺塔问题 void Hanuo(int n,int a,int b,int c) { if(n==1) return; Hanuo(n-1,a,c,b); move(a,b) Hanuo(n-1,c,b,a); } ?全排列问题 void Perm(Type list[],int k,int m) { //产生list[k,m]的所有排列 if(k == m) { for(int i = 0;I <= m;i++) cout< 数据分析 实验指导书 理学院实验中心数学专业实验室编写 实验一SAS系统的使用 【实验类型】（验证性） 【实验学时】2学时 【实验目的】使学生了解SAS系统，熟练掌握SAS数据集的建立及一些必要的SAS语句。 【实验内容】 1. 启动SAS系统，熟悉各个菜单的内容；在编辑窗口、日志窗口、输出窗口之间切换。 2. 建立数据集 表1 Name Sex Math Chinese English Alice f908591 Tom m958784 Jenny f939083 Mike m808580 Fred m848589 Kate f978382 Alex m929091 Cook m757876 Bennie f827984 Hellen f857484 Wincelet f908287 Butt m778179 Geoge m868582 Tod m898484 Chris f898487 Janet f866587 1）通过编辑程序将表1读入数据集sasuser.score; 2）将下面记事本中的数据读入SAS数据集，变量名为code name scale share price: 000096 广聚能源8500 0.059 1000 13.27 000099 中信海直6000 0.028 2000 14.2 000150 ST麦科特12600 -0.003 1500 7.12 000151 中成股份10500 0.026 1300 10.08 000153 新力药业2500 0.056 2000 22.75 3)将下面Excel表格中的数据导入SAS数据集work.gnp； name x1 x2 x3 x4 x5 x6 北京190.33 43.77 7.93 60.54 49.01 90.4 天津135.2 36.4 10.47 44.16 36.49 3.94 河北95.21 22.83 9.3 22.44 22.81 2.8 山西104.78 25.11 6.46 9.89 18.17 3.25 内蒙古128.41 27.63 8.94 12.58 23.99 3.27 辽宁145.68 32.83 17.79 27.29 39.09 3.47 吉林159.37 33.38 18.37 11.81 25.29 5.22 黑龙江116.22 29.57 13.24 13.76 21.75 6.04 上海221.11 38.64 12.53 115.65 50.82 5.89 江苏144.98 29.12 11.67 42.6 27.3 5.74 浙江169.92 32.75 21.72 47.12 34.35 5 安徽153.11 23.09 15.62 23.54 18.18 6.39 福建144.92 21.26 16.96 19.52 21.75 6.73 江西140.54 21.59 17.64 19.19 15.97 4.94 山东115.84 30.76 12.2 33.1 33.77 3.85 河南101.18 23.26 8.46 20.2 20.5 4.3 湖北140.64 28.26 12.35 18.53 20.95 6.23 湖南164.02 24.74 13.63 22.2 18.06 6.04 广东182.55 20.52 18.32 42.4 36.97 11.68 广西139.08 18.47 14.68 13.41 20.66 3.85 四川137.8 20.74 11.07 17.74 16.49 4.39 贵州121.67 21.53 12.58 14.49 12.18 4.57 云南124.27 19.81 8.89 14.22 15.53 3.03 陕西106.02 20.56 10.94 10.11 18 3.29 甘肃95.65 16.82 5.7 6.03 12.36 4.49 青海107.12 16.45 8.98 5.4 8.78 5.93 宁夏113.74 24.11 6.46 9.61 22.92 2.53 新疆123.24 38 13.72 4.64 17.77 5.75 4)使用VIEWTABLE格式新建数据集earn,输入如表所示数据Year earn 1981 125000 1982 136000 1983 122350 1984 65200 1985 844600 1986 255000 1987 265000 1988 280000 1989 136000 数值分析上机题目 1、 分别用不动点迭代与Newton 法求解方程250x x e -+=的正根与负根。 2、 Use each of the following methods to find a solution in [0.1,1] accurate to within 10^-4 for 4326005502002010x x x x -+--= a. Bisection method b. Newton’s method c. Secant method d. Method of False Position e. Muller’s method 3、 应用Newton 法求f （x ）的零点，e=10^-6,这里f （x ）=x-sin （x ）。 再用求重根的两种方法求f （x ）的零点。 4、 应用Newton 法求f （x ）的零点，e=10^-6,f(x)=x-sin(x) 再用Steffensen’s method 加速其收敛。 5、 用Neville’s 迭代差值算法，对于函数2 1 (),11125f x x x = -≤≤+进行lagrange 插值。取不同的等分数n=5,10，将区间[-1,1]n 等分，取等距节点。把f(x)和插值多项式的曲线画在同一张图上进行比较。 6、 画狗的轮廓图 7、 Use Romberg integration to compute the following approximations to ? a 、 Determine R1,1,R2,1,R3,1,R4,1and R5,1,and use these approximations to predict the value of the integral. b 、 Determine R2,2 ,R3,3 ,R4,4 ,and R5,5,and modify your prediction. c 、 Determine R6,1 ,R6,2 ,R6,3 ,R6,4 ,R6,5 and R6,6,and modify your prediction. 一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ） 数值分析实验指导 潘志斌 2014年3月 实验七 数值积分 数值实验综述：通过数值积分实验掌握数值积分的实现，理解各种数值积分公式的特性，并能用数值积分求解积分方程和微分方程。 基础实验 7.1 Newton-cotes 型求积公式 实验目的：学会Newton-cotes 型求积公式,并应用该算法于实际问题. 实验内容：求定积分 ? π cos xdx e x 实验要求：选择等分份数n ,用复化Simpson 求积公式求上述定积分的误差不超过810-的近似值,用MATLAB 中的内部函数int 求此定积分的准确值,与利用复化Simpson 求积公式计算的近似值进行比较。 7.2 Romberg 算法 实验目的：学会数值求积的Romberg 算法,并应用该算法于实际问题. 实验内容：求定积分 ? 1 5 .0dx x 实验要求： （1）要求程序不断加密对积分区间的等分,自动地控制Romberg 算法中的加速收敛过程,直到定积分近似值的误差不超过610-为止,输出求得的定积分近似值。 （2）可用MATLAB 中的内部函数int 求得此定积分的准确值与Romberg 算法计算的近似值进行比较。 7.3 Gauss 型求积公式 实验目的：学会Gauss 型求积公式,并应用该算法于实际问题. 实验内容：求定积分 ? -+4 42 1x dx 实验要求： （1）把Gauss 点的表格存入计算机,以Gauss-Legendre 求积公式作为本实验的例子,要求程序可以根据不同的阶数n ,自动地用n 阶Gauss-Legendre 求积 公式计算上述定积分的近似值.体会Gauss型求积公式是具有尽可能高的代数精度的数值求积公式。 （2）可用MATLAB中的内部函数int求得此定积分的准确值与Gauss型求积公式求得的值进行比较。 第一章 一、题目 设∑ =-= N N j S 2 j 2 1 1，其精确值为)11 123(21+--N N 。 1) 编制按从大到小的顺序1 1 13112122 2-+??+-+-=N S N ，计算S N 的通用程序。 2) 编制按从小到大的顺序1 21 1)1(111222-+ ??+--+-= N N S N ，计算S N 的通用程序。 3) 按两种顺序分别计算64210,10,10S S S ,并指出有效位数。（编制程序时用单精度） 4) 通过本次上机题，你明白了什么？ 二、通用程序 N=input('Please Input an N (N>1):'); AccurateValue=single((0-1/(N+1)-1/N+3/2)/2); Sn1=single(0); for a=2:N; Sn1=Sn1+1/(a^2-1); end Sn2=single(0); for a=2:N; Sn2=Sn2+1/((N-a+2)^2-1); end fprintf('The value of Sn (N=%d)\n',N); fprintf('Accurate Calculation %f\n',AccurateValue); fprintf('Caculate from large to small %f\n',Sn1); fprintf('Caculate from small to large %f\n',Sn2); disp('____________________________________________________') 三、结果 从结果可以看出有效位数是6位。 感想：可以得出，算法对误差的传播有一定的影响，在计算时选一种好的算法可以使结果更为精确。从以上的结果可以看到从大到小的顺序导致大数吃小数的现象，容易产生较大的误差，求和运算从小数到大数所得到的结果才比较准确。 专业： 班级： 学号： 姓名： 日期： 2014年 11月 10日 48476Λn n 111+++=。 2、q(n ，m)=q(n ，n)，m>=n 。 最大加数n1实际上不能大于n ，因此，q(1，m)=1。 3、q(n ，n)=1+q(n ，n-1)。 正整数n 的划分由n1=n 的划分和n1<=n-1的划分组成。 4、q(n ，m)= q(n ，m-1)+q(n-m ，m)，n>m>1。 正整数n 的最大加数n1不大于m 的划分由n1=m 的划分和n1<=m-1的划分组成。 （2）、算法描述 public class 张萌 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out .println(q (2,2)); } public static int q(int n,int m) { if ((n<1)||(m<1)) return 0; if ((n==1)||(m==1)) return 1; if (n MATLAB应用基础实验指导书 第一章 MATLAB及其工作环境介绍 (1) 1.1 MATLAB简介 (1) 1.2 MATLAB的工作环境介绍 (1) 1.3 MATLAB的基本管理命令 (4) 第二章 MATLAB的数值计算功能 (5) 2.1 变量与赋值语句 (5) 2.2 MATLAB矩阵 (5) 2.3 MATLAB表达式 (10) 2.4 MATLAB常用数学函数 (11) 2.5 矩阵的基本运算 (12) 2.6 数组运算 (16) 2.7 多项式及其运算 (17) 第三章 MATLAB程序设计入门 (19) 3.1 M文件 (19) 3.2 数据的输入输出 (21) 3.3 全局变量和局部变量 (23) 3.4 程序流程控制 (23) 第四章 MATLAB的符号运算功能 (28) 4.1 建立符号对象 (28) 4.2 符号算术运算 (29) 4.3 符号微积分运算 (32) 4.4 符号函数的可视化 (34) 第五章 MATLAB的可视化功能 (37) 5.1 二维图形 (37) 5.2绘制三维图形 (42) 5.3 特殊坐标图形 (44) 5.4 图形句柄 (45) 第一章 MATLAB及其工作环境介绍 1.1 MATLAB简介 MATLAB是matrix和laboratory前三个字母的缩写，意思是实验室矩阵。MATLAB 语言是一种广泛应用于工程计算及数值分析领域的新型高级语言，自1984年由美国MathWorks公司推向市场以来，经过十多年的发展与完善，MATLAB已发展成为由MATLAB语言、MATLAB工作环境、MATLAB图象处理系统、MATLAB数学函数库和MATLAB 应用程序接口五大部分组成的集数值计算、图形处理、程序开发为一体的功能强大的体系。MATLAB由“主包”和三十多个扩展功能和应用学科性的工具箱组成。 MATLAB具有以下基本功能： ●数值计算功能 ●符号计算功能 ●图形处理及可视化功能 ●可视化建模及动态仿真功能 MATLAB语言是以矩阵计算为基础的程序设计语言，语法规则简单易学。其指令格式与数学表达式非常相近，用MATLAB编写程序犹如在便笺上列写公式和求解，因而被称为“便笺式”的编程语言。另外，MATLAB还具有功能丰富和完备的数学函数库及工具箱，大量繁杂的数学运算和分析可通过调用MATLAB函数直接求解，大大提高效率，其程序编译和执行速度远远超过了传统的C和FORTRAN语言，因而用MATLAB 编写程序，往往可以达到事半功倍的效果。在图形处理方面，MATLAB可以给数据以二维、三维乃至四维的直观表现，并在图形色彩、视角、品性等方面具有较强的渲染和控制能力，使技术人员对大量原始数据的分析变得轻松和得心应手。 MATLAB的上述特点，使它深受工程技术人员及科技专家的欢迎，并成为应用学科计算机辅助分析、设计、仿真、教学等领域不可缺少的基础软件。目前MATLAB已成为国际上公认的最优秀的科技应用软件。 1.2 MATLAB的工作环境介绍 一、MATLAB的工作环境 ￥ 数值分析思考题1 1、讨论绝对误差（限）、相对误差（限）与有效数字之间的关系。 2、相对误差在什么情况下可以用下式代替 3、查阅何谓问题的“病态性”，并区分与“数值稳定性”的不同点。 4、取 ，计算 ，下列方法中哪种最好为什么（1）(3 3-，（2）(2 7-，（3） ()3 1 3+ ，（4） ()6 1 1 ，（5）99- , 数值实验 数值实验综述：线性代数方程组的解法是一切科学计算的基础与核心问题。求解方法大致可分为直接法和迭代法两大类。直接法——指在没有舍入误差的情况下经过有限次运算可求得方程组的精确解的方法，因此也称为精确法。当系数矩阵是方的、稠密的、无任何特殊结构的中小规模线性方程组时，Gauss消去法是目前最基本和常用的方法。如若系数矩阵具有某种特殊形式，则为了尽可能地减少计算量与存储量，需采用其他专门的方法来求解。 Gauss消去等同于矩阵的三角分解，但它存在潜在的不稳定性，故需要选主元素。对正定对称矩阵，采用平方根方法无需选主元。方程组的性态与方程组的条件数有关，对于病态的方程组必须采用特殊的方法进行求解。 数值计算方法上机题目1 1、实验1. 病态问题 实验目的： 算法有“优”与“劣”之分，问题也有“好”和“坏”之别。所谓坏问题就是问题本身的解对数据变化的比较敏感，反之属于好问题。希望读者通过本实验对此有一个初步的体会。 数值分析的大部分研究课题中，如线性代数方程组、矩阵特征值问题、非线性方程及方程组等都存在病态的问题。病态问题要通过研究和构造特殊的算法来解决，当然一般要付出一些代价（如耗用更多的机器时间、占用更多的存储空间等）。 $ r e x x e x x ** * ** - == 141 . ≈)61 第一章 什么是算法 算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题（有确定的输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解（正确的输出数据）。 算法的三个要素 1).数据: 运算序列中作为运算对象和结果的数据. 2).运算: 运算序列中的各种运算:赋值,算术和逻辑运算 3).控制和转移: 运算序列中的控制和转移. 算法分类 从解法上：数值型算法:算法中的基本运算为算术运算；非数值型算法:算法中的基本运算为逻辑运算. 从处理方式上：串行算法:串行计算机上执行的算法；并行算法:并行计算机上执行的算法 算法的五个重要的特性 （1） 有穷性：在有穷步之后结束。 （2） 确定性：无二义性。 （3） 可行性：可通过基本运算有限次执行来实现。 （4） 有输入 表示存在数据处理 （5） 有输出 伪代码 程序设计语言（PDL ），也称为结构化英语或者伪代码，它是一种混合语言，它采用一种语言（例如英语）的词汇同时采用类似另外一种语言（例如，结构化程序语言）的语法。 特点：1)使用一些固定关键词的语法结构表达了结构化构造、数据描述、模块的特征； 2)以自然语言的自由语法描述了处理过程；3)数据声明应该既包括简单的也包括复杂的数据结构；4)使用支持各种模式的接口描述的子程序定义或者调用技术。 求两个n 阶方阵的相加C=A+B 的算法如下，分析其时间复杂度。 #define MAX 20 ∑∑∑∑-=-=-=-=====102101010*11n i n i n i n j n n n n n n n n )O()1O(1O(11i i j i j ==∑∑==）)O(N )21O()O()O(21N 1=+=∑=∑==)(N N i i N i i 赋值，比较，算术运算，逻辑运算，读写单个变量（常量）只需1单位时间 2). 执行条件语句 if c then S1 else S2 的时间为TC +max(TS1,TS2). 3). 选择语句 case A of a1: s1；a2: s2；...； am: sm 需要的时间为 max （TS1,TS2 ,..., TSm ）. 4). 访问数组的单个分量或纪录的单个域需要一个单位时间. 5). 执行for 循环语句的时间=执行循环体时间*循环次数. 6). while c do s (repeat s until c)语句时间=(Tc+Ts)*循环次数. 7). 用goto 从循环体内跳到循环体末或循环后面的语句时,不需额外时间 8). 过程或函数调用语句：对非递归调用，根据调用层次由里向外用规则1-7进行分析； 对递归调用，可建立关于T(n)的递归方程,求解该方程得到T(n). 作者：李庆扬，王能超，易大义编 出版社：清华大学出版社 出版时间：2008年12月 本书是为理工科大学各专业普遍开设 的“数值分析”课程编写的教材。其内容包 括插值与逼近，数值微分与数值积分，非 线性方程与线性方程组的数值解法，矩阵 的特征值与特征向量计算，常微分方程数 值解法。每章附有习题并在书末给出了部 分答案，每章还附有复习与思考题和计算 实习题。全书阐述严谨，脉络分明，深入 浅出，便于教学。 本书也可作为理工科大学各专业研究 生学位课程的教材，并可供从事科学计算 的科技工作者参考。 作者：徐萃薇，孙绳武编著 出版社：高等教育出版社 本书为普通高等教育“十一五”国家 级规划教材。本书从服务于多层次、多 专业、多学科的教学需要出发，在选材 上考虑普适性，涉及现代数字电子计算 机上适用的各类数学问题的数值解法以 及必要的基础理论，在材料组织安排上 给讲授者根据教学要求和学生情况适当 剪裁的自由，一些内容还可作为阅读材 料。 新版全书经过整理、润色，多处内容有 所修改，乃至重写。考虑到代数计算在 应用中所占份额较大，是比较活跃的领 域，六至十章改动较大；新增共轭斜量 法、预善共轭斜量法、拟Newton法等；改进了例题设置，增加数量，加强例题间联系；新 增习题参考答案；参考文献收集了国内外内容结构与本书相近的、有影响的、包括新近面世 的一些书籍，并按大学生教材和研究生教材或专著分列，可供读者加深理解和进一步提高使 用。有些对研究工作亦不无裨益。 本书算法描述不拘一格，或用自然语言，或用某种形式语言(以描述某些细节)，便于理解， 也便于编程。本书可作为工科非计算数学专业本科生学习“计算方法”课程的教材。 实验报告一 题目：非线性方程求解 摘要：非线性方程的解析解通常很难给出，因此线性方程的数值解法就尤为重要。本实验采用两种常见的求解方法二分法和Newton法及改进的Newton法。 前言：（目的和意义） 掌握二分法与Newton法的基本原理和应用。 数学原理： 对于一个非线性方程的数值解法很多。在此介绍两种最常见的方法：二分法和Newton法。 对于二分法，其数学实质就是说对于给定的待求解的方程f(x)，其在[a,b]上连续，f(a)f(b)<0，且f(x)在[a,b]内仅有一个实根x*，取区间中点c，若，则c恰为其根，否则根据f(a)f(c)<0是否成立判断根在区间[a,c]和[c,b]中的哪一个，从而得出新区间，仍称为[a,b]。重复运行计算，直至满足精度为止。这就是二分法的计算思想。 Newton法通常预先要给出一个猜测初值x0，然后根据其迭代公式 产生逼近解x*的迭代数列{x k}，这就是Newton法的思想。当x0接近x*时收敛很快，但是当x0选择不好时，可能会发散，因此初值的选取很重要。另外，若将该迭代公式改进为 其中r为要求的方程的根的重数，这就是改进的Newton法，当求解已知重数的方程的根时，在同种条件下其收敛速度要比Newton法快的多。 程序设计： 本实验采用Matlab的M文件编写。其中待求解的方程写成function的方式，如下 function y=f(x); y=-x*x-sin(x); 写成如上形式即可，下面给出主程序。 二分法源程序： clear %%%给定求解区间 b=1.5; a=0; %%%误差 R=1; k=0;%迭代次数初值 while (R>5e-6) ; c=(a+b)/2; if f12(a)*f12(c)>0; a=c; else b=c; end R=b-a;%求出误差 k=k+1; end x=c%给出解 Newton法及改进的Newton法源程序：clear %%%% 输入函数 f=input('请输入需要求解函数>>','s') %%%求解f(x)的导数 df=diff(f); 算法分析与设计习题集整理 第一章算法引论 一、填空题： 1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为： O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求：正确性 和 可读性。 8、计算下面算法的时间复杂度记为： O(n 2) 。 for （i ＝1；i 数值分析上机题1 设2 21 1N N j S j ==-∑ ，其精确值为1311221N N ??-- ?+?? 。 （1）编制按从大到小的顺序222 111 21311 N S N = +++---，计算N S 的通用程序。 （2）编制按从小到大的顺序22 21111(1)121 N S N N =+++----，计算N S 的通用程序。 （3）按两种顺序分别计算210S ，410S ，610S ，并指出有效位数。（编制程序时用单精度） （4）通过本上机题，你明白了什么？ 程序代码（matlab 编程）： clc clear a=single(1./([2:10^7].^2-1)); S1(1)=single(0); S1(2)=1/(2^2-1); for N=3:10^2 S1(N)=a(1); for i=2:N-1 S1(N)=S1(N)+a(i); end end S2(1)=single(0); S2(2)=1/(2^2-1); for N=3:10^2 S2(N)=a(N-1); for i=linspace(N-2,1,N-2) S2(N)=S2(N)+a(i); end end S1表示按从大到小的顺序的S N S2表示按从小到大的顺序的S N 计算结果 通过本上机题，看出按两种不同的顺序计算的结果是不相同的，按从大到小的顺序计算的值与精确值有较大的误差，而按从小到大的顺序计算的值与精确值吻合。从大到小的顺序计算得到的结果的有效位数少。计算机在进行数值计算时会出现“大数吃小数”的现象，导致计算结果的精度有所降低，我们在计算机中进行同号数的加法时，采用绝对值较小者先加的算法，其结果的相对误差较小。 Program算法设计与分析基础中文版答案 习题 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m 设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c) 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答： a.将十进制整数转换为二进制整数的算法 输入：一个正整数n 输出：正整数n相应的二进制数 第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步 第三步：将Ki按照i从高到低的顺序输出 b.伪代码 算法 DectoBin(n) .n]中 i=1 while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; } 9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进. 算法 MinDistance(A[0..n-1]) XXXX大学 算法设计与分析课程设计报告 院（系）： 年级： 姓名： 专业：计算机科学与技术 研究方向：互联网与网络技术 指导教师： XXXX 大学 目录 题目1 电梯调度 (1) 1.1 题目描述 (1) 1.2 算法文字描述 (1) 1.3 算法程序流程 (4) 1.4 算法的程序实现代码 (10) 题目2 切割木材 (12) 2.1题目描述 (12) 2.2算法文字描述 (12) 2.3算法程序流程 (13) 2.4算法的程序实现代码 (18) 题目3 设计题 (20) 3.1题目描述 (20) 3.2 输入要求 (20) 3.3输出要求 (20) 3.4样例输入 (20) 3.5样例输出 (20) 3.6测试样例输入 (21) 3.7测试样例输出 (21) 3.8算法实现的文字描述 (21) 3.9算法程序流程 (22) 3.10算法的程序实现代码 (23) 算法分析与设计课程总结 (26) 参考文献 (27) 题目1电梯调度 1.1 题目描述 一栋高达31层的写字楼只有一部电梯，其中电梯每走一层需花费4秒，并且在每一层楼停靠的时间为10秒，乘客上下一楼需要20秒，在此求解最后一位乘客到达目的楼层的最短时间以及具体的停靠计划。例如：此刻电梯停靠需求为4 5 10（有三位乘客，他们分别想去4楼、5楼和10楼），如果在每一层楼都停靠则三位乘客到达办公室所需要的时间为3*4=12秒、4*4+10=26秒、4*9+2*10=56秒，则最后一位乘客到达办公室的时间为56秒，相应的停靠计划为4 5 10均停靠。对于此测试用例电梯停靠计划方案：4 10，这样到第4楼的乘客所需时间为3*4=12秒，到第5楼的乘客所需时间为3*4+20=32秒，到第10楼的乘客所需时间为9*4+10=46秒，即最后到达目的楼层的顾客所需时间为46秒。 输入要求： 输入的第1行为整数n f1 f2 … fn，其中n表示有n层楼需要停靠，n=0表示没有更多的测试用例，程序终止运行。f1 f2 … fn表示需要停靠的楼层（n<=30，2<=f1 《数值分析》 课程实验指导书 实验一 函数插值方法 一、问题提出 对于给定的一元函数)(x f y =的n+1个节点值(),0,1,,j j y f x j n == 。试用Lagrange 公式求其插值多项式或分段二次Lagrange 插值多项式。 数据如下： （1） j x 0.4 0.55 0.65 0.80 0.95 1.05 j y 0.41075 0.57815 0.69675 0.90 1.00 1.25382 求五次Lagrange 多项式5L ()x ，和分段三次插值多项式，计算(0.596)f ,(0.99)f 的值。（提示：结果为(0.596)0.625732f ≈, (0.99) 1.05423f ≈ ） （2） j x 1 2 3 4 5 6 7 j y 0.368 0.135 0.050 0.018 0.007 0.002 0.001 试构造Lagrange 多项式6L ()x ，计算的(1.8)f ,(6.15)f 值。（提示：结果为(1.8)0.164762f ≈, (6.15)0.001266f ≈ ） 二、要求 1、 利用Lagrange 插值公式 00,()n n i n k k i i k k i x x L x y x x ==≠??-= ?-??∑∏编写出插值多项式程序； 2、 给出插值多项式或分段三次插值多项式的表达式； 3、 根据节点选取原则，对问题（2）用三点插值或二点插值，其结果如何； 4、 对此插值问题用Newton 插值多项式其结果如何。 四、实验分析： Lagrange 插值多项式的表达式： 1,,2,1,)()()(, )()(1111+=--==∏∑+≠=+=n i x x x x x l x l y x L n i j j j i j i n i i i 。 其中)(x l i 被称为插值基函数，实际上是一个n 次多项式。)(x l i 的这种表示具有较好的对称性。公式具有两大优点：（1）求插值多项式，不需要求解线性方程组，当已知数据点较多时，此公式更能显示出优越性。（2）函数值可以用符号形式表示，数据点未确定的纵坐标可用多项式表示。 Newton 插值多项式如下： 10010,()()[,,]()k n n j k k j j k N x f x f x x x x -==≠=+?-∑∏ 其中： 00,0()()[,,]k i k i i j j j i k f x x x f x x ==≠-=∑∏ Newton 插值多项式的优点是：当每增加一个节点时，只增加一项多项式。 三、实验程序及注释 1、m 程序： function [c,l]=lagran(x,y) % x 为n 个节点的横坐标组成的向量，y 为纵坐标所组成的向量 % c 为所得插值函数的系数所组成的向量 w=length(x); n=w-1; l=zeros(w,w); for k=1:n+1 v=1; for j=1:n+1 if k~=j v=conv(v,poly(x(j)))/(x(k)-x(j)); end end l(k,:)=v; end c=y*l; function fi=Lagran_(x,f,xi) fi=zeros(size(xi)); n=length(f); for i=1:n东南大学数值分析上机题答案
算法分析与设计复习题及参考答案
算法分析与设计总结
SAS软件运用实验指导书
数值分析上机题目
算法设计与分析复习题目及答案
数值分析实验指导 - 7 积分
数值分析上机题目详解
算法分析与设计
matlab上机实验指导书
数值分析作业思考题汇总
算法分析与设计
数值分析丛书
(完整版)哈工大-数值分析上机实验报告
算法分析与设计习题集整理
东南大学《数值分析》-上机题
算法设计与分析基础课后习题答案
算法分析与设计-课程设计报告
数值分析(计算方法)实验一