追赶法
9.用追赶法解三对角方程组A x=b，其中
A=
(
2?10
?1 2?1
0?12
?1
0 0?1 2?1
0 0 0 ?1 2)
，b=
(
1
0)
.
解：对于对角占优的三对角线性矩阵可用追赶法求解采用Fortran编程计算如下：
program main
implicit none
integer::i,j,in,nb
real::x
real::a(1:100),b(1:100),c(1:100),f(1:100)
real::d(1:100),y(1:100),v(1:100)
open(unit=100,file='a.dat')
open(unit=101,file='b.dat')
open(unit=102,file='c.dat')
open(unit=103,file='f.dat')
open(unit=104,file='v.dat')
do while(.not.eof(100))
read(unit=100,fmt=*)in,x
a(in)=x
end do
nb=0
do while(.not.eof(101))
read(unit=101,fmt=*)in,x
b(in)=x
nb=nb+1
end do
do while(.not.eof(102))
read(unit=102,fmt=*)in,x
c(in)=x
end do
do while(.not.eof(103))
read(unit=103,fmt=*)in,x
f(in)=x
end do
d(1)=c(1)/b(1)
do i=2,nb-1
d(i)=c(i)/(b(i)-a(i)*d(i-1))
end do
y(1)=f(1)/b(1)
do i=2,nb
y(i)=(f(i)-a(i)*y(i-1))/(b(i)-a(i)*d(i-1))
end do
v(nb)=y(nb)
do i=nb-1,1,-1
v(i)=y(i)-d(i)*v(i+1)
end do
write(unit=104,fmt=201)'y(i)',',','x(i)'
do i=1,nb
write(unit=104,fmt=200)y(i),',',v(i)
end do
200 format(f7.4,a1,f7.4)
201 format(a7,a1,a7)
end program
其中a.dat、b.dat、c.dat和f.dat的内容分别如图1、图2、图3和图4所示；计算结果保存在v.dat中，如图5所示：
图1 图2 图3 图4 图5
算法实验 递归回溯解八皇后问题
深圳大学实验报告 课程名称：算法分析与复杂性理论 实验项目名称：八皇后问题 学院：计算机与软件学院 专业：软件工程 指导教师：杨烜 报告人：学号：班级：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
追赶法求解方程组
实验课程名称计算机数值方法 实验项目名称追赶法求解方程组 年级 10级 专业统计101班 学生姓名黄新银 学号 1007010253 理学院 实验时间：2011年10 月9 日
学生实验室守则 一、按教学安排准时到实验室上实验课，不得迟到、早退和旷课。 二、进入实验室必须遵守实验室的各项规章制度，保持室内安静、整洁，不准在室内打闹、喧哗、吸烟、吃食物、随地吐痰、乱扔杂物，不准做与实验内容无关的事，非实验用品一律不准带进实验室。 三、实验前必须做好预习（或按要求写好预习报告），未做预习者不准参加实验。 四、实验必须服从教师的安排和指导，认真按规程操作，未经教师允许不得擅自动用仪器设备，特别是与本实验无关的仪器设备和设施，如擅自动用或违反操作规程造成损坏，应按规定赔偿，严重者给予纪律处分。 五、实验中要节约水、电、气及其它消耗材料。 六、细心观察、如实记录实验现象和结果，不得抄袭或随意更改原始记录和数据，不得擅离操作岗位和干扰他人实验。 七、使用易燃、易爆、腐蚀性、有毒有害物品或接触带电设备进行实验，应特别注意规范操作，注意防护；若发生意外，要保持冷静，并及时向指导教师和管理人员报告，不得自行处理。仪器设备发生故障和损坏，应立即停止实验，并主动向指导教师报告，不得自行拆卸查看和拼装。 八、实验完毕，应清理好实验仪器设备并放回原位，清扫好实验现场，经指导教师检查认可并将实验记录交指导教师检查签字后方可离去。 九、无故不参加实验者，应写出检查，提出申请并缴纳相应的实验费及材料消耗费，经批准后，方可补做。 十、自选实验，应事先预约，拟订出实验方案，经实验室主任同意后，在指导教师或实验技术人员的指导下进行。 十一、实验室内一切物品未经允许严禁带出室外，确需带出，必须经过批准并办理手续。
求解线性方程组的直接解法
求解线性方程组的直接解法 5.2LU分解 ① Gauss消去法实现了LU分解 顺序消元结束时的上三角矩阵U和所用的乘数,严格下三角矩阵。 将下三角矩阵的对角元改成1,记为L,则有A=LU, 这事实是一般的,我们不难从消去的第k个元素时的矩阵k行及k列元素的 历史得到这一点.因为从消元的历史有 u kj=a kj-m k1u1j- m k2u2j -…- m k,k-1u k-1,j, j=k,k+1,…,n m ik=(a ik-m i1u1k- m i2u2k -…-m i,k-1u k-1,k>/u kk i=k+1,k+2,…,n 于是a kj=m k1u1j+m k2u2j+…+m k,k-1u k-1,j+u kj, j=k,k+1,…,n a ik=m i1u1k+m i2u2k+…+m i,k-1u k-1,k+m ik u kk i=k+1,k+2,…,n 从前面两个式子我们可以直接计算L和U(见下段>.将矩阵分解为单位下 三角矩阵和上三角矩阵之积称为矩阵的LU分解.顺序消元实现了LU分 解,同时还求出了g, Lg=b的解. ②直接LU分解 上段我们得到(l ij=m ij> u kj=a kj-l k1u1j-l k2u2j -…- l k,k-1u k-1,j, j=k,k+1,…,n l ik=(a ik-l i1u1k-l i2u2k -…-l i,k-1u k-1,k>/u kk i=k+1,k+2,…,n 2 诸元素对应乘积,只不过算L的元素时还要除以同列对角元.这一规律很 容易记住.可写成算法(L和U可存放于A>: for k=1:n-1 for j=k:n u kj=a kj-l k1u1j-l k2u2j -…- l k,k-1u k-1,j end for i=k+1:n l ik=(a ik-l i1u1k-l i2u2k -…-l i,k-1u k-1,k>/u kk end end 这一算法也叫Gauss消去法的紧凑格式,可一次算得L,U的元素,不需逐步 计算存储.
平方根法追赶法
§5 平方根法 一、教学设计 1．教学内容：对称正定矩阵的Cholesky 分解法、三对角线矩阵分解的追赶法。 2．重点难点：Cholesky 分解法、追赶法。 3．教学目标：掌握对称正定矩阵的Cholesky 分解的计算过程，掌握三对角线矩阵分解的追赶法。 4．教学方法：讲授与讨论。 二、教学过程 §5 平方根法 在工程计算中，常遇到求解解对称再正定线性方程组问题，如应用有限元法解结构力学问题，应用差分方法解椭圆型偏微分方程等，最后都归结为求解系数矩阵为对称正定阵的线性方程组。根据系数矩阵的特殊性，是否有更好的解决方案（在存贮空间上的好处是显而易见的），算法上是否有所简化？ 5－0对称正定矩阵及性质复习 定义：设n n R A ?∈，如果A 满足条件 （1）A A T =；（2）对任意非零向量n R ∈x ，有0>x x A T ，则称A 为对称正定矩阵。 定理1 （对称正定矩阵的性质）如果n n R A ?∈为对称正定矩阵，则 （1）A 为非奇异阵，且1-A 亦是对称正定阵； （2）记k A 为A 的顺序主子阵，则k A 亦是对称正定阵),,2,1(n k =； （3）A 的特征值),,2,1(0)(n i A i =>λ； （4）A 的顺序主子式都大于零，即),,2,1(0)det(n k A k =>。 定理2 设n n R A ?∈为对称矩阵（判据）
（1）若A 的特征值),,2,1(0)(n i A i =>λ，则A 为对称正定矩阵； （2）若A 的顺序主子式都大于零，即),,2,1(0)det(n k A k =>，则A 为对称正定阵。 5－1 对称正定矩阵的三角分解 由前述定理 3.1知，若n 阶方阵A 的顺序主子式)1,,2,1 ()d e t (-=n k A k 均不为零，则A 有唯一的三角分解LU A =，其中L 为单位下三角阵，U 为上三角阵。n 阶对称正定阵A 的顺序主子式都大于零，当然有LU 分解，进一步地，此时U L ,之间有什么关系？这对解方程组有用处。由LU A L U A T T T ===及分解的唯一性，想到若U 的主对角元素皆为1，就有可能获得一些结果。为此，再将U 分解 DR u u u u u u u u u u u u u u u U n n nn nn n n ≡??? ?????? ???????? ?????? ??? ? ? ? ?=????????? ?? ?=111222********* 11222 11211 易知),,2,1(0n i u ii => （用k k k U L A ,,分别记矩阵U L A ,,的k 阶 顺序主子阵，容易验证k k k U L A =于是 ii k i i ii k i k k k k k k u a U U L U L A ∏∏ =======1 )(1det det det )det(det ） 于是LDR LU A ==，所以 A DR L LU DL R LDR A T T T T =====)()()(， 即 )()(DR L DL R A T T == 由分解的唯一性知：T R L =，R L T =，于是T LDL A = 自然地，若记
算法分析与程序设计动态规划及回溯法解背包问题
动态规划法、回溯法解0-1背包问题 2012级计科庞佳奇 一、问题描述与分析 1.动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会 有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。 不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。 多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。1.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。3.子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。 01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。 2.回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目 标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
综合结转分步法与分项结转分步法例题【可编辑】
综合结转分步法与分项结转分步法 1、综合逐步结转分步法举例 例：某企业200×年6月份生产甲产品，该产品顺序经过第一、二、三加工步骤，第一步骤投入原材料后生产A半成品，交第二步骤生产B半成品，再交第三步骤加工成甲产成品，原材料在第一步骤开始生产时一次投入，各步骤的加工程度逐步发生，各步骤月末在产品的完工程度均为50%，该企业采用综合逐步结转分步法计算产品成本，自制半成品通过半成品库收发，发出自制半成品的计价采用加权平均法。 （1）产量资料 （2）期初在产品成本 (3)期初库存：A半成品月初库存60件，实际成本8700元，B半成品月初无库存。 (4)本月生产费用：
第一步骤基本生产成本明细账 车间名称：第一步骤完工产量：240件 产品名称：A半成品 200×年 6月金额单位：元 （5）第一步骤成本计算 直接材料=31500÷（240+110）=90 直接人工=6490÷（240+110×50%）=22 制造费用=11210÷（240+110×50%）=38 根据完工入库半成品成本作如下会计分录： 借：自制半成品——A半成品 36000 贷：生产成本——基本生产成本——A半成品 36000 半成品明细分类账 名称：A半成品单位：元
第二步骤基本生产成本明细账 车间名称：第二步骤完工产量：200件产品名称：B半成品 200×年6月金额单位：元 （6）第二步骤成本计算 直接材料=41440÷（200+80）=148 直接人工=11280÷（200+80×50%）=47 制造费用=12000÷（200+80×50%）=50 根据完工入库半成品成本作如下会计分录： 借：自制半成品——B半成品 49000 贷：生产成本——基本生产本——B半成品 49000 半成品明细分类账
0028算法笔记——【回溯法】批作业调度问题和符号三角形问题
1、批作业调度问题 (1)问题描述 给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。 批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。 例：设n=3，考虑以下实例： 这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3； 2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。 (2)算法设计
批处理作业调度问题要从n个作业的所有排列中找出具有最小完成时间和的作业调度，所以如图，批处理作业调度问题的解空间是一颗排列树。按照回溯法搜索排列树的算法框架，设开始时x=[1,2,……n]是所给的n个作业，则相应的排列树由x[1:n]的所有排列构成。 算法具体代码如下： [cpp]view plain copy 1.#include "stdafx.h" 2.#include
12. *x, // 当前作业调度 13. *bestx, // 当前最优作业调度 14. 15. *f2, // 机器2完成处理时间 16. f1, // 机器1完成处理时间 17. f, // 完成时间和 18. 19. bestf, // 当前最优值 20. n; // 作业数 21. }; 22. 23.int Flow(int **M,int n,int bestx[]); 24. 25.template function x= thomas(A,b) %本函数用于解三对角方程，采用托马斯算法（追赶法） %对于Ax=b的矩阵，有三种输入方式 %1.输入参数A,b,其中A为完全矩阵；2.输入参数A,b,其中A为N*3的矩阵,分别存储三条对角线；3.只输入增广矩阵A; [m,n]=size(A); %% 检查输入参数 if nargin==1 if n~=m+1 error('请检查输入的增广矩阵维数'); end b=A(:,end); A(:,end)=[]; else l=length(b); if n~=3&&(m~=n||m~=l) error('请检查A,b的维数'); end end [m,n]=size(A); %% 追赶法解方程 if m==n for i=2:m A(i,i)=A(i,i)-A(i-1,i)*A(i,i-1)/A(i-1,i-1); b(i)=b(i)-b(i-1)*A(i,i-1)/A(i-1,i-1); end x(m)=b(m)/A(m,m); for i=m-1:-1:1 x(i)=(b(i)-x(i+1)*A(i,i+1))/A(i,i); end return else if A(1,1)~=0 error('第一行输入应为[0,d1,a1]'); end for i=2:m A(i,2)=A(i,2)-A(i-1,3)*A(i,1)/A(i-1,2); b(i)=b(i)-b(i-1)*A(i,1)/A(i-1,2); end x(m)=b(m)/A(m,2); for i=m-1:-1:1 x(i)=(b(i)-x(i+1)*A(i,3))/A(i,2); end return end end 应用数学学院信息安全专业班学号姓名 实验题目回溯算法 实验评分表 实验报告 一、实验目的与要求 1、理解回溯算法的基本思想； 2、掌握回溯算法求解问题的基本步骤； 3、了解回溯算法效率的分析方法。 二、实验内容 【实验内容】 最小重量机器设计问题：设某一个机器有n个部件组成，每个部件都可以m个不同供应商处购买，假设已知表示从j个供应商购买第i个部件的重量，表示从j个供应商购买第i个部件的价格，试用回溯法求出一个或多个总价格不超过c且重量最小的机器部件购买方案。 【回溯法解题步骤】 1、确定该问题的解向量及解空间树； 2、对解空间树进行深度优先搜索； 3、再根据约束条件（总价格不能超过c）和目标函数（机器重量最小）在搜索过程中剪去多余的分支。 4、达到叶结点时记录下当前最优解。 5、实验数据n,m, ] ][ [j i w,] ][ [j i c的值由自己假设。 三、算法思想和实现【实现代码】 【实验数据】 假设机器有3个部件，每个部件可由3个供应商提供（n=3，m=3）。总价不超过7（c<=7）。 部件重量表： 部件价格表： 【运行结果】 实验结果：选择供应商1的部件1、供应商1的部件2、供应商3的部件3，有最小重量机器的重量为4，总价钱为6。 四、问题与讨论 影响回溯法效率的因素有哪些？ 答：影响回溯法效率的因素主要有以下这五点： 1、产生x[k]的时间； 2、满足显约束得x[k]值的个数； 3、计算约束函数constraint的时间； 4、计算上界函数bound的时间； 5、满足约束函数和上界函数约束的所有x[k]的个数。 五、总结 这次实验的内容都很有代表性，通过上机操作实践与对问题的思考，让我更深层地领悟到了回溯算法的思想。 回溯算法的基本思路并不难理解，简单来说就是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法的基本做法是深度优先搜索，是一种组织得井井 〔例题〕某企业生产甲产品，分第一车间和第二车间进行生产，采用平行结转分步法计算产品成本。直接材料于生产开始时一次投入，各步骤月末在产品完工程度均为40%，生产费用在完工产品与在产品之间的分配采用约当产量法。相关资料见下表： 表1 各车间产量记录 表2 第一车间成本计算单 金额单位：元 表3 第二车间成本计算单金额单位：元 表4 产品成本汇总计算表 金额单位：元 要求： （1）计算第一车间的约当总产量（按直接材料、直接人工、制造费用分别计算），并把表2填写完整； （2）计算第二车间的约当总产量，并把表3填写完整； （3）把表4填写完整，并计算单位产品成本。 【答案】 （1）第一车间的在产品约当产量计算如下： 直接材料：在产品约当产量＝40×100％＋60＝100（件） 直接人工：在产品约当产量＝40×40％＋60＝76（件） 制造费用：在产品约当产量＝40×40％＋60＝76（件） 由于企业最后完工的产品（400件）耗用第一车间的完工产品400件，因此，计算第一车间的约当总产量时，还应该加上企业最后完工的产品数量400件，即： 直接材料：约当总产量＝400＋100＝500（件） 直接人工：约当总产量＝400＋76＝476（件） 制造费用：约当总产量＝400＋76＝476（件） 直接材料： 计入产成品成本份额＝（2800＋8000）/500×400＝8640（元）月末在产品成本＝2800＋8000－8640＝2160（元） 或：月末在产品成本＝（2800＋8000）/500×100＝2160（元）直接人工： 计入产成品成本份额＝（580＋1800）/476×400＝2000（元） 月末在产品成本＝580＋1800－2000＝380（元） 或：月末在产品成本＝（580＋1800）/476×76＝380（元） 制造费用： 计入产成品成本份额＝（1008＋2800）/476×400＝3200（元）月末在产品成本＝1008＋2800－3200＝608（元） 或：月末在产品成本＝（1008＋2800）/476×76＝608（元） 表2 第一车间成本计算单 金额 单位：元 第8章怎样研究算法:排序算法示例 1、排序算法是最基本的算法，很多复杂算法都是以排序为基础进行构造的。关于排序算法，下列说法不正确的是_____。 (A)大规模数据集合中查找有无某些元素的问题，有序数据集合比无序数据集合的查找要快得多； (B)大规模数据集合中按元素分组进行计算的问题，有序数据集合比无序数据集合的计算要快得多； (C)对无序数据集合，两个算法X和Y：X采用无序数据处理，Y采用先将无序数据排序成有序数据，然后进行处理；则对前述(A)、(B)两类问题，Y算法一定比X算法慢； (D)上述说法有不正确的； 答案：C 解释： 本题考核排序算法的研究 在大规模数据集合中查找，有序数据集合有利算法进行和判断，要比无序数据集合查找的快，对于（C）选项，Y算法尽管需要排序后再处理，但排序处理后的数据查找更加快捷，因此可能Y算法比X算法更快。 具体内容请参考排序算法以及第八章课件。 2、下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法：针对一个“学生”数据表，如下示意，找出“成绩”为某一分数的所有学生。 【算法A1】 Start of algorithm A1 Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2。Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果是，则输出；如果不是，则不输出。 End of algorithm A1 【算法A2】 Start of algorithm A2 Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2和Step 3。 Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果等于，则输出；如果不等于，则不输出。 Step 3. 判断该条记录的成绩是否小于给定的分数：如果不是，则继续；否则，退出循环，算法结束。 End of algorithm A2 【算法A3】 Start of algorithm A3 Step 1. 假设数据表的最大记录数是n，待查询区间的起始记录位置Start为1，终止记录位置Finish为n； Step 2. 计算中间记录位置I = (Start+Finish)/2，读取第I条记录。 Step 3. 判断第I条记录的成绩与给定查找分数： (3.1)如果是小于关系，则调整Finish = I-1；如果Start >Finish则结束，否则继续做Step 2； (3.2)如果是大于关系，则调整Start = I+1；如果Start>Finish则结束，否则继续做Step 2； (3.3)如果是等于关系，则输出，继续读取I周围所有的成绩与给定查找条件相等的记录并输出，直到所有相等记录查询输出完毕则算法结束。 End of algorithm A3 针对上述三个算法，回答下列问题： (1)关于算法A1, A2, A3的快慢问题，下列说法正确的是_____。 (A)算法A1快于算法A2，算法A2快于算法A3； (B)算法A2快于算法A1，算法A2快于算法A3； (C)算法A3快于算法A2，算法A2快于算法A1； (D)算法A1快于算法A3，算法A3快于算法A2； (E)上述都不正确。 答案：C 解释： 本题考核排序算法的研究 首先，数据是有序排列的，从大到小。 算法A1依次搜索，穷举。 算法A2与A1一样，穷举，不同的是它利用数据是从大到小排序的特点，因此，如果当前数据比如果小于目标数，那么说明只有的也一定小于，则目标不在序列中。因此，A2比A1快。 算法A3利用数据有序特点，采用二分查找，每次将目标数与中间值比较，缩小搜索范围，因此A3比A2快。 综上，答案选（C）。 具体内容请参考排序算法以及第八章课件。 做三次样条曲线时，需要解三对角矩阵（Tridiagonal Matrices）。常用解法为Thomas Algorithm，又叫The tridiagonal matrix algorithm (TDMA)。它是一种基于高斯消元法的算法，分为两个阶段：向前消元forward elimination和回代backward substitution。本文以一个6乘6矩阵为例，介绍一下使用TDMA的求解过程。 1.范例求解 步骤1：将矩阵变为上三角矩阵 首先要把上面公式中的系数矩阵变为一个上三角矩阵。 第一行： 将上式除以b1： 可写作： 所以矩阵方程可写为： 第二行： 将变换后的第一行乘以a2，再与第二行相减，即可消去x1，得： 所以新的矩阵方程为： 同理可推， 第三行： 第四行： 第五行： 第六行： 最后得到新的上三角矩阵公式为： 步骤2：求解 x逆序可以求出，如下： 2. 一般性公式： 注意： 使用TDMA求解，系数矩阵需时diagonally dominant，即： 3. 实现代码（C语言） void tdma(float x[], const size_t N, constfloat a[], constfloat b[], float c[]) { size_t n; c[0] = c[0] / b[0]; x[0] = x[0] / b[0]; for (n = 1; n < N; n++) { float m = 1.0f / (b[n] - a[n] * c[n - 1]); c[n] = c[n] * m; x[n] = (x[n] - a[n] * x[n - 1]) * m; } for (n = N - 1; n-- >0; ) x[n] = x[n] - c[n] * x[n + 1]; } 《算法分析与设计》期末复习题 一、选择题 1.算法必须具备输入、输出和（ D ）等4个特性。 A．可行性和安全性 B．确定性和易读性 C．有穷性和安全性 D．有穷性和确定性 2.算法分析中，记号O表示（ B ），记号Ω表示（ A ） A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 3.假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。在某台计算机上实现并 完成概算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？（ B ）解题方法：3*2^n*64=3*2^x A．n+8 B．n+6 C．n+7 D．n+5 4.设问题规模为N时，某递归算法的时间复杂度记为T(N)，已知T(1)=1， T(N)=2T(N/2)+N/2，用O表示的时间复杂度为（ C ）。 A．O(logN) B．O(N) C．O(NlogN) D．O(N2logN) 5.直接或间接调用自身的算法称为（ B ）。 A．贪心算法 B．递归算法 C．迭代算法 D．回溯法 6.Fibonacci数列中，第4个和第11个数分别是（ D ）。 A．5，89 B．3，89 C．5，144 D．3，144 7.在有8个顶点的凸多边形的三角剖分中，恰有（ B ）。 A．6条弦和7个三角形 B．5条弦和6个三角形 C．6条弦和6个三角形 D．5条弦和5个三角形 8.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A．重叠子问题 B．最优子结构性质 C．贪心选择性质 D．定义最优解 9.下列哪个问题不用贪心法求解（ C ）。 A．哈夫曼编码问题 B．单源最短路径问题 C．最大团问题 D．最小生成树问题 10.下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A．备忘录法 B．动态规划法 C．贪心法 D．回溯法 11.下列算法中不能解决0/1背包问题的是（ A ）。 A．贪心法 B．动态规划 C．回溯法 D．分支限界法 12.下列哪个问题可以用贪心算法求解（ D ）。 追赶法求解三对角线性方程组 一 实验目的 利用编程方法实现追赶法求解三对角线性方程组。 二 实验内容 1、 学习和理解追赶法求解三对角线性方程组的原理及方法； 2、 利用MATLAB 编程实现追赶法； 3、 举例进行求解，并对结果进行分。 三 实验原理 设n 元线性方程组Ax=d 的系数矩阵A 为非奇异的三对角矩阵 11222=(1)(n 1)()()a c b a c A a n c b n a n ??????????--?????? ………… 这种方程组称为三对角线性方程组。显然，A 是上下半宽带都是1的带状矩阵。设A 的前n-1个顺序主子式都不为零，根据定理2.5的推论，A 有唯一的Crout 分解，并且是保留带宽的。 其中L 是下三角矩阵，U 是单位上三角矩阵。利用矩阵相乘法，可以1112212(1)1u(n 1)()()1l u m l u A LU l n m n l n ????????????????==?????--????????????…………… 得到： 由上列各式可以得到L 和U 。 引入中间量y ，令 y Ux =，则有： 已知 L 和d ，可求得y 。 则可得到y 的求解表达式： 11/1 2,3,,()(1)*y()=()[()(1)]/y d l i n m i y i li i di y i di m i y i li ==-+=--… 1111111/1(2)(1)(1)u (1)(11)/(1)(1)(1)l a l u c u c l mi bi i n a i m i i l i i n ci li ui ui ci li l i a i b i ui =*===≤≤+=+++≤≤-=?=+=+-+Ax LUx Ly d Ly d ====1112222(1)(n 1)(n 1)()()(n)(n)l y d m l y d l n y d m n l n y d ?????????????????????????=??????---?????????????????? …………… 一、算法理论 在一些实际问题中，例如解常微分方程边值问题，解热传导方程以及船体数学放样中建立三次样条函数等，都会要求解系数矩阵为对角占优的三对角线方程组 ??????? ? ??=???????? ?????????? ? ?-----n n n n n n n n n f f f f x x x x b a c b a c b a c b 121121111 22211 ， 简记为f Ax =. 求解f Ax =等价于解两个三角形方程组： y f Ly 求,=；x y Ux 求,=.从而得到解三对角线方程组的追赶法公式： (1)计算{}i β的递推公式 ();1,,3,2,/,/111-=-==n i a b c b c i i i i i βββ (2)… (3) 解f Ly = ()();,,3,2,/,/11111n i a b y a f y b f y i i i i i i i =--==--β (4)解y Ux = .1,2,2,1,,1 --=-==+n n i x y x y x i i i i n n β 我们将计算系数 的过程称为追的过程，及n n y y y →→→→→→- 21121βββ 将计算方程组的解 的过程称为赶的过程。11x x x n n →→→- — 二、算法框图 ; \ 三、 算法程序 #include <> #include <> #include<> #define N 20 double a[N], b[N], c[N-1], f[N], r[N]; int n; （1） void LUDecompose(); ???????? ??2100012100012100012100012A －－－－－－－－＝??? ?? ?? ? ??=00001b 回车。 （2） 显示出 请输入下三角元素 输入4个a 值：-1 -1 -1 -1，回车。 （3） 显示出 请输入主对角线元素 输入5个b 值：2 2 2 2 2 ，回车。 （4） ！ （5） 显示出 请输入上三角元素 输入4个c 值：-1 -1 -1 -1，回车。 （6） 显示出 请输入5个方程组右端顶：1 0 0 0 0，回车。 其解为????? ????166667 .0333333.0500000.0666667.0833333 .0 例2．用该程序计算三对角线方程组 《数值分析》课程设计追赶法解三对角方程组 院（系）名称信息工程学院 专业班级10普本信计 学号100111014 学生姓名刘银朋 指导教师张荣艳 2013 年05 月31日 数值分析课程设计评阅书 题目追赶法解三对角方程组 学生姓名刘银朋学号100111014 指导教师评语及成绩 指导教师签名： 年月日答辩评语及成绩 答辩教师签名： 年月日 教研室意见 总成绩： 教研室主任签名： 年月日 课程设计任务书 2012—2013学年第二学期 专业班级：10普本信息与计算科学学号：100111014 姓名：刘银朋 课程设计名称：数值分析Ⅰ、Ⅱ 设计题目：追赶法解三对角方程组 完成期限：自2013 年05月21 日至2013年05 月31日共10天 设计依据、要求及主要内容： 一、设计目的 理解追赶法,掌握追赶法的算法设计以及关于追赶法的分析和综合应用,能 够较熟练的应用Matlab软件编写求解追赶法的程序和应用Matlab软件数据库软 件. 二、设计内容 （1）认真挑选有代表性的三对角方程组. （2）认真梳理解三对角方程组的解题思路. （3）比较追赶法和高斯消去法的计算精度. 三、设计要求 1．先用Matlab数据库中的相应的函数对选定的方程,求出具有一定精度的解. 2．然后使用所用的方法编写Matlab程序求解. 3.对于使用多个方程解同意问题的,在界面上要设计成菜单的形式. 计划答辩时间：2013年06 月 5 日 工作任务鱼工作量要求： 查阅文献资料不少于3篇,课程设计报告1篇不少于3000字. 指导教师（签字）：教研室主任（签字）： 批准日期：2013 年05 月20 日 内部资料，转载请注明出处，谢谢合作。 一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ A ）。 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 ） A、分治法 B、动态规划法 C、贪心法 D、回溯法14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 回溯算法 搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。 递归回溯法算法框架[一] procedure Try(k:integer); begin for i:=1 to 算符种数 Do if 满足条件 then begin 保存结果 if 到目的地 then 输出解 else Try(k+1); 恢复：保存结果之前的状态{回溯一步} end; end; 递归回溯法算法框架[二] procedure Try(k:integer); begin if 到目的地 then 输出解 else for i:=1 to 算符种数 Do if 满足条件 then begin 保存结果 Try(k+1); end; end; 例 1：素数环：把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。【算法分析】非常明显，这是一道回溯的题目。从1 开始，每个空位有 20（19）种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第 20个数还要判断和第1个数的和是否素数。 〖算法流程〗1、数据初始化； 2、递归填数： 判断第J种可能是否合法； A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个； B、如果不合法：选择下一种可能； 【参考程序】 program z74;框架[一] var a:array[0..20]of byte; b:array[0..20]of boolean; total:integer; function pd(x,y:byte):boolean; var k,i:byte; begin k:=2; i:=x+y; pd:=false; while (k<=trunc(sqrt(i)))and(i mod k<>0) do inc(k); if k>trunc(sqrt(i)) then pd:=true; end; procedure print; var j:byte; begin inc(total);write('<',total,'>:'); for j:=1 to 20 do write(a[j],' '); writeln; end; procedure try(t:byte); var i:byte; begin for i:=1 to 20 do if pd(a[t-1],i)and b[i] then begin a[t]:=i; b[i]:=false; if t=20 then begin if pd(a[20],a[1]) then print;end 分步法例题1 [例7-1] 假定某工业企业的甲种产品生产分两个步骤，分别由两个车间进行。第一车间生产A半成品，交半成品库验收；第二车间按照所需加工数量向半成品库领用。该企业以甲产品及其所经过的生产步骤的A半成品为成本核算对象，按成本核算对象设置的产品成本明细账有甲产成品(第二车间)、甲产品的A半成品(第一车间)。产品成本明细账按照直接材料(或半成品)、直接人工和制造费用三个成本项目设置专栏组织核算。 该企业经过半成品仓库收发的A半成品，设置“自制半成品——A半成品”明细账组织收入、发出和结存的核算。送交半成品仓库的半成品，按实际成本综合结转；半成品仓库发出的A半成品采用全月一次加权平均法计算其实际成本。 该企业某年6月份有关资料如下： 1.第一和第二车间发生的费用已经在各成本核算对象之间进行了分配。两个车间月末在产品均按定额成本计价。 2.月初、月末在产品定额成本以及本月生产费用发生额如表7-1所示。 表7-1 成本资料单位:元 该企业某年6月份有关资料如下： 3.本月初半成品库结存A半成品800件，其实际成本总额为206 000元。本月第一车间完工入库A半成品1 000件，第二车间从半成品库领用A半成品1 400件。本月完工入库甲产成品1 600件。 成本计算程序如下： (1)计算第一车间本月生产A半成品的实际成本。 第一车间为生产甲产品的第一生产步骤，没有上步骤转入费用，将A半成品月初在产品定额成本和本月发生的生产费用记入第一车间产品成本明细账后，即可用生产费用合计数扣减月末在产品定额成本，从而计算出完工A半成品的成本。其计算过程见表7-2所示。 表7-2 产品成本计算表 车间名称：第一车间产品名称：半成品A 单位: 元MATLAB托马斯算法(追赶法)实现
算法设计与分析：回溯法-实验报告
平行结转分步法例题
第8章怎样研究算法排序算法示例练习题答案解析
TDMA追赶法
最新《算法分析与设计》期末考试复习题纲(完整版)
追赶法求解三对角线性方程组
追赶法(经典计算)
追赶法解三对角方程组
算法分析复习题目及答案
回溯算法的一些例题
最新分步法例题1
- 第二章 解线性方程组的直接法 第五节 追赶法课件ppt课件
- 追赶法解三对角方程组
- 实验2追赶法算法设计及MATLAB实现
- 追赶法算法流程图
- 三次样条算法
- 追赶法求解方程组
- 追赶法(Thomas算法)
- 追赶法解三对角矩阵
- 计算方法作业第六章
- 各种迭代法的算法实现
- 解三对角方程组的追赶法
- TDMA追赶法
- 【良心出品】MATLAB 追赶法求解三对角方程组的算法原理例题与程序
- 追赶法算法流程图(优.选)
- 实验2追赶法算法设计及MATLAB实现
- 追赶法(经典计算)
- 追赶法解三对角方程组
- 实验2追赶法算法设计和MATLAB实现
- MATLAB-追赶法求解三对角方程组的算法原理例题与程序
- 计算方法追赶法解三对角矩阵方程