研究性学习报告.docx

1、研究性学习报告研究性学习报告动态规划法与图论算法在实际中的应用研究性学习课题报告 选题依据 近年来，随着信息学技术的发展，算法在实际中的应用越来越广泛。作为21世纪的高中生，我们有必要学习如何在实际中应用我们所学习的算法知识。而算法中应用最为广泛的搜索与图算法，更是我们必须学会灵活应用的。为此，六安一中学科选修1班信息学兴趣小组针对一系列仿真的实际问题展开了算法应用的大演习（全部以pascal语言为载体）。 研究的主要内容 1搜集算法在实际中的应用案例 2运用所学知识编写程序解决实际问题 3优化算法，总结在实际问题中如何灵活运用所学知识，如何学以致用。 研究的重难点 1如何在所学的有限知识范围

2、内找到实际应用案例 2如何编写正确高效的算法。 研究团队及分工 全组 人 组长：邵鑫（sx） 资料收集：陈偲（cc） 数据分析：赵一（zz） 程序编写：邵鑫（sx） 程序调试及优化：陈偲（cc） 总结整理：赵一（zz） 研究进程及安排 1、2014年7月4日课题确定2.2014年7月6日7月10日收集资料3. 2014年7月11日2014年7月13日对收集的资料进行整理4. 2014年7月14日2014年7月15日编写程序5.2014年2月8日调试，优化，总结 应用一：动态规划（Dynamic Programming) 简介：动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化问题的一种简

3、单高效的算法。1951年，美国数学家贝尔曼（R.Bellman)提出了解决这类问题的“最优化原则”，1957年出版了动态规划，该书是动态规划方面的第一本著作。动态规划问世以来，在工农业生产和经济军事工程技术等诸多发面得到了广泛的应用。 实际模拟问题：sx的背包 问题描述 组长sx来到一家商店。由于商店新开业，而sx是第一位顾客，关键sx长得实在是一表人才，所以店长允许sx拿店里的任何一个物品（一直拿到背包装不下为止），强壮的sx当然希望拿的越多越好，但他的背包有个重量限制（可惜啊，早知道就随身带个集装箱了）。现在店里有 n 件物品x1, x2, , xn , 每件物品有一个价值和一个重量，分别

4、记为： v1,v2, vn w1,w2, wn 其中所有的 wi 均为整数。 现有一个背包，其最大载重量为m，要求从这n件物品中任取若干件（这些物品每样只有一件，要么被装入要么被留下）。问背包中装入哪些物品可使得sx所装物品的价值和最大？ （我们只需要求出最大价值，不需要求出具体拿的是哪些物品）例如，m=23, n = 5, vi : 19 24 33 45 50 wi : 5 6 8 11 12 最大价值为：95 输入格式 Input Format 第1行两个整数，为n和m。第2到n+1行每行两个整数，分别为每件物品的重量和价值。 输出格式 Output Format 装入背包的最大价值。

5、小组成员提供程序如下： var n,weight,i,j,m:longint; w,v:array0.1000of longint; a:array0.1000,0.1000of longint;function max(a,b:longint):longint;begin if ab then max:=a else max:=b;end;begin readln(n,weight); for i:=1 to n do readln(wi,vi); fillchar(a,sizeof(a),0); for i:=1 to n do for j:=0 to weight do if j=wi

6、then ai,j:=max(ai-1,j-wi+vi,ai-1,j) else ai,j:=ai-1,j; m:=an,1; for j:=2 to weight do begin if an,jm then m:=an,j; end; writeln(m); end. 应用二：图论 简介：自欧拉以来，无数数学家在各种错综复杂的图中费尽了一生的心血。但图论一直被人们认为是有趣但是却无用的理论产物。不过，自从计算机问世以来，图论的应用已经深入到人们生活的方方面面。 实际模拟问题一：cc的省内建设 在sx英明组织研究性学习活动的帮助下，同学们的实际解决问题的能力远超同龄人。20年后，我们组的cc

7、同学成为了叉叉省省长，可是该省基础设施一塌糊涂。cc决心改变这种情况。现cc有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少（毕竟cc实在抠门）？ 【输入】 第一行两个数v(v=200),e，分别代表城市数和边数 以下e行，每行为两个顶点和它们之间的边权w(w1000)。【输出】 v-1行，每行为两个城市的序号，表明这两个城市间建一条公路，再加该公路的造价。 组长提供程序：var n,m,i,j,w,a,b:longint; way:array1.

8、1000,1.1000of longint; elist:array1.1001of record fromv:longint; endv:longint; weight:longint; end;procedure prim;var k,min,p:longint;begin for k:=1 to n-1 do begin min:=9999999;m:=k; for j:=k to n-1 do if elistj.weightmin then begin min:=elistj.weight;m:=j;end; if mk then begin elist1001:=elistk;el

9、istk:=elistm;elistm:=elist1001;end; j:=elistk.endv; for i:=k+1 to n-1 do begin p:=elisti.endv; if wayj,pelisti.weight then begin elisti.weight:=wayj,p;elisti.fromv:=j;end; end; end;end;begin readln(n,m); for i:=1 to m do begin readln(a,b,w); waya,b:=w; wayb,a:=w; end; for i:=1 to n do for j:=1 to n

10、do if wayi,j=0 then wayi,j:=maxlongint; for i:=1 to n-1 do begin elisti.fromv:=1; elisti.endv:=i+1; elisti.weight:=way1,i+1; end; prim; for i:=1 to n-1 do begin writeln(elisti.fromv, ,elisti.endv, ,elisti.weight); end; readln(i);end. 实际模拟问题二：一中的校园网络 许多年过去了，一中终于准备在校园网中构建校园网络（真是造福一代青年啊！我上学那会怎么没有这种好事），

11、校长请来了已经是全国著名工程师的zz。已知zz在校园网中选好了N（N1000）个点，并准备在这些点安装网络设备和电脑。若要将N个点互相连接起来，问怎样布线才能使得总距离最短（zz：要知道铜线是怪值钱的，浪费是可耻的！省下来的钱还可以多买个几个大大泡泡糖），两点间的布线长度等于这两个点的几何距离。 【输入】network.in输入文件的第一行为一个正整数N(1N100)。接下来N行，每行2个数U,V ，表示坐标。【输出】network.out输出最短路径距离（保留两位小数） 小组全上阵写程序：var n,i,j:longint; ans:real; way:array1.201,1.201of

12、real; g:array1.200,1.2of longint; elist:array1.201of record fromv:longint; endv:longint; weight:real; end;procedure prim;var m,k,s:longint; min,p:real;begin for k:=1 to n-1 do begin min:=10000000; for j:=k to n-1 do if elistj.weightmin then begin min:=elistj.weight;m:=j;end; if mk then begin elist20

13、1:=elistk;elistk:=elistm;elistm:=elist201;end; j:=elistk.endv; for i:=k+1 to n-1 do begin s:=elisti.endv;p:=wayj,s; if pelisti.weight then begin elisti.fromv:=j;elisti.weight:=p;end; end; end;end;function dis(x1,y1,x2,y2:longint):real;begin dis:=sqr(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);/计算两点间距离end;begin r

14、eadln(n); ans:=0; for i:=1 to n do readln(gi,1,gi,2); for i:=1 to n-1 do for j:=i to n do begin wayi,j:=dis(gi,1,gi,2,gj,1,gj,2); wayj,i:=wayi,j;/建立邻接矩阵 end; for i:=1 to n-1 do begin elisti.fromv:=1; elisti.endv:=i+1; elisti.weight:=way1,i+1; end; prim; for i:=1 to n-1 do ans:=ans+elisti.weight; writeln(ans:0:2); readln;end. 研究的总结与感受 通过本次活动，本小组组员充分感受到了信息学的无穷魅力，同时解决了三个有一定难度的问题，收获颇丰。今后我们会更加关注信息学在实际生活中的应用，争取做到学以致用，为我所用。