实验报告4.回溯算法

算法设计与分析

实验报告

实验名称_____回溯算法_____

学院________数学与计算机学院____ 班级_______信科00000___________ 学号_______6666666666__________ 姓名_____000000________________ 2016年月日

{

if(((a+b)==24)||((a-b)==24)||((a*b)==24)||(b!=0&&a%b==0&&a/b==24)){//如果经过上面的计算得到解

while(!route.empty()){

node now=route.front();

printf("%d%c%d=%d\n",now.a,now.oper,now.b,now.sum);//依次输出前面的计算过程

route.pop();

}

if((a+b)==24){

if(b>a) swap(a,b);

printf("%d+%d=%d\n",a,b,a+b);

}

if((a-b)==24) printf("%d-%d=%d\n",a,b,a-b);

if((a*b)==24) {

if(b>a) swap(a,b);

printf("%d*%d=%d\n",a,b,a*b);

}

if(a%b==0&&b!=0&&(a/b)==24) printf("%d/%d=%d\n",a,b,a/b);//a/b比较特殊，要求结果必须是整数

flag=true;//表示找到解，一旦找到任何一个解就退出

}

return ;

}

queue temp=route;

node x;

x.a=a,x.b=b,x.sum=a+b,x.oper='+';

if(b>a) swap(x.a,x.b);

temp.push(x);

dfs(cur+1,a+b,num[cur+1],temp);//(((a*b)*c)*d) 模型

temp=route;

x.a=a,x.b=b,x.sum=a*b,x.oper='*';

if(b>a) swap(x.a,x.b);

temp.push(x);

dfs(cur+1,a*b,num[cur+1],temp);

temp=route;

x.a=a,x.b=b,x.sum=a-b,x.oper='-';

temp.push(x);

dfs(cur+1,a-b,num[cur+1],temp);

if(b!=0&&a%b==0){//a/b需要验证合法性

temp=route;

x.a=a,x.b=b,x.sum=a/b,x.oper='/';

temp.push(x);

dfs(cur+1,a/b,num[cur+1],temp);

}

temp=route;

x.a=b,x.b=num[cur+1],x.sum=b+num[cur+1],x.oper='+';

if(x.b>x.a) swap(x.a,x.b);

temp.push(x);

dfs(cur+1,a,b+num[cur+1],temp);//a*((b*c)*d) 模型

temp=route;

x.a=b,x.b=num[cur+1],x.sum=b*num[cur+1],x.oper='*';

if(x.b>x.a) swap(x.a,x.b);

temp.push(x);

dfs(cur+1,a,b*num[cur+1],temp);

temp=route;

x.a=b,x.b=num[cur+1],x.sum=b-num[cur+1],x.oper='-';

temp.push(x);

dfs(cur+1,a,b-num[cur+1],temp);

if(num[cur+1]!=0&&b%num[cur+1]==0) {

temp=route;

x.a=b,x.b=num[cur+1],x.sum=b/num[cur+1],x.oper='/';

temp.push(x);

dfs(cur+1,a,b/num[cur+1],temp);

}

}

int main()

{

//freopen("point24.in","r",stdin);//输入输出重定向

//freopen("point24.out","w",stdout);

queue t;

scanf("%d %d %d %d",&num[0],&num[1],&num[2],&num[3]);

while(!flag){

dfs(1,num[0],num[1],t);

printf("%d %d %d %d\n",num[0],num[1],num[2],num[3]);

if(!next_permutation(num,num+4)) break;

}

if(!flag) printf("No answer!\n");

system("pause");

return 0;

}

数值稳定性验证实验报告

实验课程：数值计算方法专业：数学与应用数学班级：08070141 学号：37 姓名：汪鹏飞 中北大学理学院

实验1 赛德尔迭代法 【实验目的】 熟悉用塞德尔迭代法解线性方程组 【实验内容】 1.了解MATLAB 语言的用法 2.用塞德尔迭代法解下列线性方程组 1234123412341234 54 1012581034 x x x x x x x x x x x x x x x x ---=-??-+--=?? --+-=??---+=? 【实验所使用的仪器设备与软件平台】 计算机，MATLAB7.0 【实验方法与步骤】 1.先找出系数矩阵A ，将前面没有算过的x j 分别和矩阵的(,)A i j 相乘,然后将累加的和赋值给sum ，即(),j s u m s u m A i j x =+?.算 出()/(,) i i x b sum A i i =-,依次循环,算出所有的i x 。 2.若i x 前后两次之差的绝对值小于所给的误差限ε，则输出i x .否则重复以上过程，直到满足误差条件为止. 【实验结果】 (A 是系数矩阵，b 是右边向量，x 是迭代初值，ep 是误差限) function y=seidel(A,b,x,ep) n=length(b); er=1; k=0; while er>=ep

k=k+1; for i=[1:1:n] q=x(i); sum=0; for j=[1:1:n] if j~=i sum=sum+A(i,j)*x(j); end end x(i)=(b(i)-sum)/A(i,i); er=abs(q-x(i)); end end fprintf('迭代次数k=%d\n',k) disp(x') 【结果分析与讨论】 >> A=[5 -1 -1 -1;-1 10 -1 -1;-1 -1 5 -1;-1 -1 -1 10]; b=[-4 12 8 34]; seidel(A,b,[0 0 0 0],1e-3) 迭代次数k=6 0.99897849430002 1.99958456867649 2.99953139743435 3.99980944604109

回溯法实验(0-1背包问题)

算法分析与设计实验报告第五次附加实验

附录： 完整代码（回溯法） //0-1背包问题回溯法求解 #include using namespace std; template class Knap //Knap类记录解空间树的结点信息 { template friend Typep Knapsack(Typep [],Typew [],Typew,int); private: Typep Bound(int i); //计算上界的函数 void Backtrack(int i); //回溯求最优解函数

Typew c; //背包容量 int n; //物品数 Typew *w; //物品重量数组| Typep *p; //物品价值数组 Typew cw; //当前重量 Typep cp; //当前价值 Typep bestp; //当前最后价值 }; template Typep Knapsack(Typep p[],Typew w[],Typew c,int n); //声明背包问题求解函数template inline void Swap(Type &a,Type &b); //声明交换函数 template void BubbleSort(Type a[],int n); //声明冒泡排序函数 int main() { int n ;//物品数 int c ;//背包容量 cout<<"物品个数为："; cin>>n; cout<<"背包容量为："; cin>>c; int *p = new int[n];//物品价值下标从1开始 int *w = new int[n];//物品重量下标从1开始 cout<<"物品重量分别为："<>w[i]; } cout<<"物品价值分别为："<>p[i]; } cout<<"物品重量和价值分别为："<

数值分析—龙贝格算法

数值分析 实 验 报 告 专业：信息与计算科学 班级： 10***班 学号： 1008060**** 姓名： ******

实验目的： 用龙贝格积分算法进行积分计算。 算法要求： 龙贝格积分利用外推方法，提高了计算精度，加快了收敛速度。 1--4R R R R 1-j 1-j 1-k 1-j k 1-j k j k ，，，，+= ，k=2，3，… 对每一个k ，j 从2做到k ，一直做到|R R 1-k 1-k k k -，，| 小于给定控制精 度时停止计算。 其中： T R h k 1k =，（复化梯形求积公式），2h 1-k k a -b = 程序代码： #include #include #define M 10 static float a, b, T[M], S[M], C[M], R[M]; float f(float x) { float y; if(0.0 == x) { x = 0.0000001f; } y = (float)1/sqrt(1-x*x); return y; } int p(int n) { int i=0,t=1;

while(t!=n) { t*=2; ++i; } return i; } float t(int n) { float g,h,q=0; if(1==n) { h = (float)fabs(b-a); q = (f(a)+f(b))*h/2; } else { float x = a; g = 0; h = (float)fabs(b-a)*2/n; x = x+h/2; while(x

回溯法实验(最大团问题)

算法分析与设计实验报告第七次附加实验

} } 测试结果 当输入图如下时： 当输入图如下时： 1 2 3 4 5 1 2 3 4 5

当输入图如下时： 1 2 3 4 5

附录： 完整代码（回溯法） //最大团问题回溯法求解 #include using namespace std; class Clique { friend void MaxClique(int **,int *,int ); private: void Backtrack(int i); int **a; //图的邻接矩阵 int n; //图的顶点数 int *x; //当前解 int *bestx; //当前最优解 int cn; //当前顶点数 int bestn; //当前最大顶点数 }; void Clique::Backtrack(int i) { //计算最大团 if(i>n) //到达叶子节点 { for(int j=1;j<=n;j++) bestx[j]=x[j]; bestn=cn;

cout<<"最大团：（"; for(int i=1;i=bestn) { //修改一下上界函数的条件，可以得到 x[i]=0; //相同点数时的解 Backtrack(i+1); } } void MaxClique(int **a,int *v,int n) { //初始化Y Clique Y; Y.x=new int[n+1]; Y.a=a; Y.n=n; https://www.docsj.com/doc/658418828.html,=0; Y.bestn=0; Y.bestx=v; Y.Backtrack(1); delete [] Y.x; cout<<"最大团的顶点数："<

回溯法实验报告

实验04 回溯法 班级：0920561 姓名：宋建俭学号：20 一、实验目的 1.掌握回溯法的基本思想。 2.掌握回溯法中问题的解空间、解向量、显式约束条件、隐式约束条件以及子 集树与排列树的递归算法结构等内容。 3.掌握回溯法求解具体问题的方法。 二、实验要求 1.认真阅读算法设计教材,了解回溯法思想及方法; 2.设计用回溯算法求解装载问题、n后问题、图的m着色问题的java程序 三、实验内容 1.有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱 i的重量为wi，且∑wi≤C1+C2。装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 2.在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则， 皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。 3.给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每 个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。 这个问题是图的m可着色判定问题。 四、算法原理 1、装载问题 用回溯法解装载问题时，用子集树表示其解空间是最合适的。可行性约束可剪去不满足约束条件(w1x1+w2x2+…+wnxn)<=c1的子树。在子集树的第j+1层结点Z处，用cw记当前的装载重量，即cw=(w1x1+w2x2+…+wjxj)，当cw>c1时，以结点Z为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去。 解装载问题的回溯法中，方法maxLoading返回不超过c的最大子集和，但未给出达到这个最大子集和的相应子集。 算法maxLoading调用递归方法backtrack(1)实现回溯搜索。Backtrack(i)搜索

数值分析龙贝格实验报告

实验三 龙贝格方法 【实验类型】 验证性 【实验学时】 2学时 【实验内容】 1.理解龙贝格方法的基本思路 2.用龙贝格方法设计算法，编程求解一个数值积分的问题。 【实验前的预备知识】 1．计算机基础知识2．熟悉编程基本思想3．熟悉常见数学函数； 【实验方法或步骤】 龙贝格方法的基本思路龙贝格方法是在积分区间逐次二分的过程中，通过 对梯形之值进行加速处理，从而获得高精度的积分值。 1． 龙贝格方法的算法 步骤1 准备初值()f a 和()f b ，用梯形计算公式计算出积分近似值 ()()12b a T f a f b -=+??? ? 步骤2 按区间逐次分半计算梯形公式的积分近似值令 2i b a h -=，0,1,2,...i =计算12102122n n n i i h T T f x -+=??=+ ??? ∑，2i n = 步骤3 按下面的公式积分梯形公式：()223n n n n T T S T -=+ 辛普生公式：()2215n n n n S S C S -=+ 龙贝格公式：()2263n n n n C C R C -=+ 步骤4 精度控制 当2n n R R ε-<，（ε为精度）时，终止计算，并取2n R 为近似值否则将步长折 半，转步骤2。

[实验程序] #include #include # define Precision 0.00001//积分精度要求 # define e 2.71828183 #define MAXRepeat 10 //最大允许重复 double function(double x)//被积函数 { double s; s=2*pow(e,-x)/sqrt(3.1415926); return s; } double Romberg(double a,double b,double f(double x)) { int m,n,k; double y[MAXRepeat],h,ep,p,xk,s,q; h=b-a; y[0]=h*(f(a)+f(b))/2.0;//计算T`1`(h)=1/2(b-a)(f(a)+f(b)); m=1; n=1; ep=Precision+1; while((ep>=Precision)&&(m

回溯法实验报告

数学与计算机学院实验报告 一、实验项目信息 项目名称：回溯法 实验时间： 2016/06/08 实验学时： 03 学时 实验地点：工科楼503 二、实验目的及要求 理解回溯法的深度优先搜索策略、 掌握用回溯法解题的算法框架、 掌握回溯法的设计策略 三、实验环境 计算机Ubuntu Kylin14.04 CodeBlock软件四、实验内容及实验步骤 排兵布阵问题 某游戏中，不同的兵种处在不同的地形上其攻击能力不一样，现有n个不同兵种的角色{1,2,...,n}，需安排在某战区n个点上，角色i在j点上的攻击力为A ij。试设计一个布阵方案，使总的攻击力最大。 数据： 防卫点 角 色 1 2 3 4 5 1 2 3 4 5 回溯法： 程序： #include int position[10]; int a[10][10]; int check(int k){//每个节点检查的函数 int i; for(i=0;i=0) { sum=0; position[k]=position[k]+1; while(position[k]<=n)

if(check(k))break; else position[k]=position[k]+1; if(position[k]<=n && k==n-1) { for(i=0;i

Romberg龙贝格算法实验报告.

Romberg龙贝格算法实验报告 2017-08-09 课程实验报告 课程名称： 专业班级： CS1306班学号： U201314967 姓名：段沛云指导教师：报 告日期： 计算机科学与技术学院 目录 1 实验目的 (1) 2 实验原理 (1) 3 算法设计与流程框图 (2) 4 源程序 (4) 5 程序运行 (7) 6 结果分析 (7) 7 实验体会 (7) 1 实验目的 掌握Romberg公式的用法，适用范围及精度，熟悉Romberg算法的流程，并能够设计算法计算积分 31 得到结果并输出。 1x 2 实验原理 2.1 取k=0,h=b-a,求T0= 数)。 2.2 求梯形值T0( b-a

),即按递推公式（4.1）计算T0。 k 2 h [f(a)+f(b)]，令1→k,(k记区间[a，b]的二分次2 2.3 求加速值，按公式(4.12)逐个求出T表的第k行其余各元素Tj(k-j) (j=1,2,….k)。 2.4 若|Tk+1-Tk| n-1 11T2n=[Tn+hn∑f(xi+)] 22i=0 1 Sn=T2n+(T2n-Tn) 31 Cn=S2n+(S2n-Sn) 151 Rn=C2n+(C2n-Cn) 63 3 算法设计与流程框图 算法设计：(先假定所求积分二分最大次数次数为20) 3.1 先求T[k][0] 3.2 再由公式T (k)m 4m(k+1)1)=mTm-1-mTm(k-1(k=1,2,) 求T[i][j] 4-14-1 3.3 在求出的同时比较T[k][k]与T[k-1][k-1]的大小，如果二者之差的绝对 值小于1e-5，就停止求T[k][k]；此时的k就是所求的二分次数，而此时的T[k][k]就是最终的结果 3.4 打印出所有的T[i][j]；程序流程图

算法设计与分析：回溯法-实验报告

应用数学学院信息安全专业班学号姓名 实验题目回溯算法 实验评分表

实验报告 一、实验目的与要求 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]的个数。 五、总结 这次实验的内容都很有代表性，通过上机操作实践与对问题的思考，让我更深层地领悟到了回溯算法的思想。 回溯算法的基本思路并不难理解，简单来说就是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法的基本做法是深度优先搜索，是一种组织得井井

龙贝格积分实验报告

二、Romberg 积分法 1.变步长Romberg 积分法的原理 复化求积方法对于提高精度是行之有效的方法，但复化公式的一个主要缺点在于要事先估计出部长。若步长过大，则精度难于保证；若步长过小，则计算量又不会太大。而用复化公式的截断误差来估计步长，其结果是步长往往过小，而且''()f x 和(4)()f x 在区间[,]a b 上的上界M 的估计是较为困难的。在实际计算中通常采用变步长的方法，即把步长逐次分半（也就是把步长二等分），直到达到某种精度为止，这种方法就是Romberg 积分法的思想。 在步长的逐步分半过程中，要解决两个问题： 1. 在计算出N T 后，如何计算2N T ,即导出2N T 和N T 之间的递推公式； 2. 在计算出N T 后，如何估计其误差，即算法的终止的准则是什么。 首先推导梯形值的递推公式，在计算N T 时，需要计算1N +个点处的函数值在计算出N T 后，在计算2N T 时，需将每个子区间再做二等分，共新增N 个节点。为了避免重复计算，计算2N T 时，将已计算的1N +个点的数值保留下来，只计算新增N 个节点处的值。为此，把2N T 表示成两部分之和，即 由此得到梯形值递推公式 因此 由复化梯形公式的截断误差有 若''()f x 变化不大时，即''''12()()f f ηη≈，则有 式（2）表明，用2N T 作为定积分I 的近似值，其误差大致为21 ()3 N N T T -， 因此其终止条件为 其中ε是预先给定的精度。 积分公式 将上述方法不断推广下去，可以得到一个求积分的序列，而且这个序列很快收敛到所求的定积分。记 (0)N N T T =，将区间N 等分的梯形值。(1)N N T S =，将区间N 等分的Simpson

算法分析与设计实验四回溯法

实验四 回溯法 实验目的 1. 掌握回溯法的基本思想方法； 2. 了解适用于用回溯法求解的问题类型，并能设计相应回溯法算法； 3. 掌握回溯法算法复杂性分析方法，分析问题复杂性。 预习与实验要求 1. 预习实验指导书及教材的有关内容，掌握回溯法的基本思想； 2. 严格按照实验内容进行实验，培养良好的算法设计和编程的习惯； 3. 认真听讲，服从安排，独立思考并完成实验。 实验设备与器材 硬件：PC 机 软件：C++或Java 等编程环境 实验原理 回溯法是最常用的解题方法，有“通用的解题法”之称。当要解决的问题有若干可行解时，则可以在包含问题所有解的空间树中，按深度优先的策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，继续查找该结点的兄弟结点，若它的兄弟结点都不包含问题的解，则返回其父结点——这个步骤称为回溯。否则进入一个可能包含解的子树，继续按深度优先的策略进行搜索。这种以深度优先的方式搜索问题的解的算法称为回溯法。它本质上是一种穷举法，但由于在搜索过程中不断略过某些显然不合适的子树，所以搜索的空间大大少于一般的穷举，故它适用于解一些组合数较大的问题。 回溯法也可以形式化地描述如下：假设能够用n 元组()n i x x x x ,,,,,21 表示一个给定问题P 的解，其中i i S x ∈。如果n 元组的子组()i x x x ,,,21 ()n i <满足一定的约束条件，则称为部分解。如果它已经是满足约束条件的部分解，则添加11++∈i i S x 形成新的子组()121,,,,+i i x x x x ，并检查它是否满足约束条件，若仍满足则继续添加22++∈i i S x ，并以此类推。如果所有的11++∈i i S x 都不满足约束条件，那么去掉1+i x ，回溯到i x 的位置，并去掉当前的i x ，另选一个i i S x ∈'，组成新的子组()i x x x ',,,21 ，并判断其是否满足约束条件。如此反复下去，直到得到解或者证明无解为止。

回溯法实验(n皇后问题)(迭代法)

算法分析与设计实验报告第三次附加实验

附录： 完整代码（回溯法） //回溯算法递归回溯n皇后问题#include #include #include #include"math.h" using namespace std; class Queen

{ friend int nQueen(int); //定义友元函数，可以访问私有数据 private: bool Place(int k); //判断该位置是否可用的函数 void Backtrack(int t); //定义回溯函数 int n; //皇后个数 int *x; //当前解 long sum; //当前已找到的可行方案数 }; int main() { int m,n; for(int i=1;i<=1;i++) { cout<<"请输入皇后的个数："; //输入皇后个数 cin>>n; cout<<"皇后问题的解为："<

matlab计算方法实验报告5(数值积分)

计算方法实验报告(5) 学生姓名杨贤邦学号指导教师吴明芬实验时间2014.4.16地点综合实验大楼203 实验题目数值积分方法 实验目的●利用复化梯形、辛普森公式和龙贝格数值积分公式计算定积分的 近似植。 实验内容●梯形、辛普森、柯特斯法及其Matlab实现； ●变步长的梯形、辛普森、柯特斯法及其Matlab实现。 ●题目由同学从学习材料中任意选两题 算法分析梯形：function y=jifeng_tixing(a,b,n,fun) fa=feval(fun,a); fb=feval(fun,b); s=0; h=(b-a)/n; for k=1:n-1 xk=a+k*h; s=feval(fun,xk)+s; end y=(h/2)*(fa+fb+2*s); 辛普生：function y=jifeng_xingpu(a,b,n,fun) fa=feval(fun,a); fb=feval(fun,b); h=(b-a)/n; s=0; s2=feval(fun,a+0.5*h); for k=1:n-1 xk=a+k*h; s=feval(fun,xk)+s; s2=feval(fun,xk+(h/2))+s2; end

与源程序y=(h/6)*(fa+fb+2*s+4*s2); 龙贝格：function r2=jifeng_long(fun,a,b,e) h=b-a; t1=(h/2)*(feval(fun,a)+feval(fun,b)); k=1; r1=10; r2=0; c2=0; while abs(r2-r1)>e; s=0; x=a+h/2; while x=3 r1=r2; c2=s2+(1/15)*(s2-s1); r2=c2+(1/63)*(c2-c1); k=k+1;h=h/2; t1=t2;s1=s2; c1=c2; end end

回溯法实验(最优装载)

算法分析与设计实验报告第二次附加实验 ）用可行性约束函数可剪去不满足约束条件

附录： 完整代码（贪心法） //回溯法递归求最优装载问题#include #include #include using namespace std; template class Loading { public: void Backtrack(int i);

int n, //集装箱数 *x, //当前解 *bestx; //当前最优解 Type *w, //集装箱重量数组 c, //第一艘轮船的载重量 cw, //当前载重量 bestw, //当前最优载重量 r; //剩余集装箱重量 }; template void Loading::Backtrack(int i); template //参数为：w[]各物品重量数组，c为第一艘轮船的载重量，n为物品数量，bestx[]数组为最优解 Type MaxLoading(Type w[],Type c,int n,int bestx[]); int main() { int n=3,m; int c=50,c2=50; int w[4]={0,10,40,40}; int bestx[4]; clock_t start,end,over; //计算程序运行时间的算法 start=clock(); end=clock(); over=end-start; start=clock(); m=MaxLoading(w,c,n,bestx); //调用MaxLoading函数 cout<<"轮船的载重量分别是："<>n; cout<<"位置排列是："<0) { a[k]=a[k]+1; while((a[k]<=n) && (check(k)==0)) a[k]=a[k]+1; if(a[k]<=n) if(k==n) { num++; output(n); } else { k=k+1; a[k]=0; } else k=k-1; } cout<<"一共有"<

回溯法解0 1背包问题实验报告

实验4 回溯法解0-1背包问题 一、实验要求 1．要求用回溯法求解0-1背包问题； 要求交互输入背包容量，物品重量数组，物品价值数组；2．要求显示结果。3． 二、实验仪器和软件平台 仪器：带usb接口微机 软件平台：WIN-XP + VC++ 三、实验源码 #include \ #include #include #include<> #include using namespace std; template class Knap { public: friend void Init(); friend void Knapsack(); friend void Backtrack(int i); friend float Bound(int i); bool operator<(Knap a)const { if(fl< return true; else return false; } private: ty w; ; cout<>bag[i].v; for(i=0;i

{ bag[i].flag=0; bag[i].kk=i; bag[i].fl=*bag[i].v/bag[i].w; } }void Backtrack(int i){cw+=bag[i].w;if(i>=n) <=c) lag=1; cp+=bag[i].v; Backtrack(i+1); cw-=bag[i].w; cp-=bag[i].v; } if(Bound(i+1)>bestp)lag=0; Backtrack(i+1); }}<=cleft){; b+=bag[i].v; i++; } /bag[i].w * cleft; return b; } void Knapsack() k]=bag[k].flag; lag*bag[k].v; //价值累加 } cout<

数值计算方法实验报告

差值法实验日志 实验题目：插值法 实验目的： 1．掌握拉格朗日插值、牛顿插值、分段低次插值和样条插值的方法。 2．对四种插值结果进行初步分析。 实验要求： （1）写出算法设计思想； （2）程序清单； （3）运行的结果； （4）所得图形； （5）四种插值的比较； （6）对运行情况所作的分析以及本次调试程序所取的经验。如果程序未通过，应分析其原因。 实验主要步骤： 1．已知函数) f满足： (x x0.0 0.1 0.195 0.3 0.401 0.5 f(0.39894 0.39695 0.39142 0.38138 0.36812 x ） 0.35206 （1）用分段线性插值； 打开MATLAB，按以下程序输入： x0=-5:5; y0=1./(1+x0.^2); x=-5:0.1:5; y=1./(1+x.^2); y1=lagr(x0,y0,x); y2=interp1(x0,y0,x); y3=spline(x0,y0,x);

for k=1:11 xx(k)=x(46+5*k); yy(k)=y(46+5*k); yy1(k)=y1(46+5*k); yy2(k)=y2(46+5*k); yy3(k)=y3(46+5*k); end [xx;yy;yy2;yy3]' z=0*x; plot(x,z,x,y,'k--',x,y2,'r') plot(x,z,x,y,'k--',x,y1,'r') pause plot(x,z,x,y,'k--',x,y3,'r') 回车得以下图形:

（2） 拉格朗日插值。 创建M 文件，建立lagr 函数： function y=lagr1(x0,y0,x) n=length(x0);m=length(x); for i=1:m z=x(i); s=0.0; for k=1:n p=1.0; for j=1:n if j~=k p=p*(z-x0(j))/(x0(k)-x0(j)); end end s=p*y0(k)+s; end y(i)=s; end 新建一个M 文件，输入： x0=[0.0 0.1 0.195 0.3 0.401 0.5]; y0=[0.39894 0.39695 0.39142 0.38138 0.36812 0.35206]; x=0.0:0.01:0.5; y1=lagr1(x0,y0,x); 00.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

实验四回溯算法

实验四回溯算法的应用 一、实验目的 1．掌握回溯算法的基本思想、技巧和效率分析方法。 2．熟练掌握用回溯算法求解问题的基本步骤，非递归算法框架和递归算法框架。 3．学会利用回溯算法解决实际问题。 二、实验内容 1.问题描述： 题目一、 n后问题 在n*n格的棋盘上摆放n个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上，问有多少种摆法。 题目二、数字全排列问题 任意给出从1到N的N个连续的自然数，求出这N个自然数的各种全排列。如N=3时，共有以下6种排列方式：123，132，213，231，312，321。注意：数字不能重复，N由键盘输入。 题目三、0-1 背包问题 有N件物品和一个容量为V的背包。第i件物品的体积是v[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 题目四、连续邮资问题 假设国家发行了n种不同面值的邮票，并且规定每个信封上最多只允许贴m 张邮票。连续邮资问题要求对于给定的n和m的值,给出邮票面值的最佳设计，使得可在1张信封上贴出从邮资1开始，增量为1的最大连续邮资区间。 【输入样例】 n＝5

m=4 【输出样例】 1,3,11,15,32 含义：当n＝5，m＝4时，面值为{1，3，11，15，32}的5种邮票可以贴出邮资的最大连续区间是1到70。 2.数据输入：个人设定，由键盘输入。 3.要求： 1）上述题目任选一做。上机前，完成程序代码的编写 2）独立完成实验及实验报告 三、实验步骤 1.理解算法思想和问题要求； 2.编程实现题目要求； 3.上机输入和调试自己所编的程序； 4.验证分析实验结果； 5.整理出实验报告。