算法设计原则验证实验报告_算法设计与分析实验报告.docx

小灰灰 2022-11-01 15:56 23阅读 0赞

![41528d3028836879cd698677c3999917.gif][]算法设计与分析实验报告.docx

声明此文档只作为学习参考，不得用作它途算法设计与分析实验教学大纲实验学时32实验个数7实验学分1课程性质适用专业计算机科学与技术、软件工程教材及参考书1计算机算法设计与分析，王晓东，北京电子工业出版社，20122算法与数据结构，傅清祥等著，北京电子工业出版社，20033计算机算法导引设计与分析，卢开澄著，北京清华大学出版社，2001大纲执笔人刘芳大纲审定人郭涛一、实验课的性质与任务算法的设计与分析是计算机科学的核心问题之一，也是计算机科学与技术专业本科及研究生的一门重要的专业基础课，其内容是研究计算机领域及其有关领域中的一些非数值计算的常用算法。课程将覆盖计算机软件实现中常用的、有代表性的算法，并具有一定的深度和广度，通过实验，使学生理解并掌握算法设计的基本技术，让学生具有针对所给的问题设计和实现高效算法的基本能力。二、实验课程目的与要求计算机科学的一个核心问题是算法理论，本课程介绍非数值算法设计的策略与技术，同时介绍算法的复杂性的概念通过对一些代表性算法的使用达到了解掌握与运用的目的。通过完成课程实验，使学生达到如下要求1熟悉各种基本常用算法的基本思想、适用范围，初步掌握算法分析的基本技巧以及如何根据实际问题设计一个有效的算法。2能对给定问题分析出恰当的数学模型，并设计出解决方案，将算法用高级语言(C，VC等)编程实现。三、实验项目及内容提要算法设计与分析实验课程序实实验名称学必选学实验类型内容提要号验项目编号时做做分数基本操作验证综合设计11算法设计基础4√√通过本次实验，程序设计语言基础知识，熟悉文件操作等22递归与分治策略及其应用6√√√掌握递归算法的设计思想，提高应用分治法设计算法的技能33动态规划及其应用6√√√掌握设计动态规划算法的步骤，并编程实现有关算法。44贪心算法及其应用6√√√通过本次实验，掌握设计贪心算法的步骤，并编程实现有关问题的求解545回溯法及其应用6√√√通过本实验，理解回溯法的深度搜索策略，掌握用回溯法解题的算法框架。66分支限界法及其应用4√√√通过本实验，理解分支限界法的剪枝搜索策略，掌握用分支限界法算法框架77线性规划问题的求解4√√理解线性规划的算法模型，了解求解线性规划的单纯形算法，学会使用EXCEL求解线性规划问题。三、实验内容安排实验一算法设计基础(验证型实验4学时)1实验目的(1)巩固程序设计语言基础知识，熟悉文件操作等。(2)对给定问题，能设计算法并编程实现问题的求解，并分析算法的时间复杂性。2实验要求(1)认真填写实验报告，附加源代码(主要代码)和运行记录；(2)对设计好的算法，测试运行实验数据，检查输出是否正确。并对算法的时间和空间复杂度进行分析。3实验内容(1)统计数字问题(P8)INCLUDE“IOSTREAM“INCLUDEINCLUDEIFSTREAMFIN“TXT“OFSTREAMFOUT“OUTPUTTXT“USINGNAMESPACESTDINTI,N,MINTPAGE//PAGE是书的总页数INTNUMBER10\{0\}VOIDMAIN\{FINPAGEFORINTJ1JINCLUDEIFSTREAMFIN“TXT“OFSTREAMFOUT“OUTPUTTXT“USINGNAMESPACESTDVOIDMAIN\{INTA,B,I,J,MAXFINABINTNUMBER100\{0\}//约数个数FORIAINUMBERI1MAXNUMBERIELSEMAXNUMBERI1\}FOUTUSINGNAMESPACESTDINTQINTM,INTN\{IFNMNCOUTINCLUDEIFSTREAMFIN“TXT“OFSTREAMFOUT“OUTPUTTXT“USINGNAMESPACESTDINTCOUNT0INTCHECKCHARLIST,INTK,INTM//判断是否互异，重复返回0\{IFMKFORINTIKINUMBER//NUMBER数组为待排元素WHILENUMBERI \\0 \{NI\}PERMNUMBER,0,N1FOUTINCLUDEIFSTREAMFIN“TXT“OFSTREAMFOUT“OUTPUTTXT“USINGNAMESPACESTDVOIDMAIN\{INTNUMBER,RESULTINTCOUNT1FINNUMBER//输入整数FORINTI2IUSINGNAMESPACESTDINTMAXSUBSUMINTA,INTLEFT,INTRIGHT//最大子段和分治法\{INTSUM0IFLEFTRIGHTSUMALEFT0ALEFT0ELSE\{INTCENTERLEFTRIGHT/2INTLEFTSUMMAXSUBSUMA,LEFT,CENTERINTRIGHTSUMMAXSUBSUMA,CENTER1,RIGHTINTS10INTLEFTS0FORINTICENTERILEFTI\{LEFTSAIIFLEFTSS1S1LEFTS\}INTS20INTRIGHTS0FORICENTER1IS2S2RIGHTS\}SUMS1S2IFSUM0BAIELSEBAIIFBSUMSUMB\}RETURNSUM\}VOIDMAIN\{INTA\{0,1,2,3,4,5,6,7\}INTNCOUTINCLUDE“IOSTREAM“INCLUDEUSINGNAMESPACESTDDEFINEMAXA,BABAB//MAXA,BA,B中的最大值DEFINEMINA,BAVOIDKNAPSACKTYPEV,INTW,INTC,INTN,TYPEM\{//递归初始条件//V价值,W重量,C容量,N件数,M价值数INTJMAXMINWN1,CFORINTJ0J1I\{JMAXMINWI1,CFORINTJ0JW1\{M1CMAXM1C,M2CW1V1COUTVOIDTRACEBACKTYPEM,INTW,INTC,INTN,INTX\{//物品装入XI为1，反之为0；背包容量C减少当前装入物品的重量FORINTI1IV,W,C,N,PPMTRACEBACKPPM,W,C,N,XFORI1IVOIDMAIN\{INTA100100INTI,J,NPRINTF“输入行数“SCANF“D“,FORI1I0IFORJIJ0J\{AIJAI1J1AI1JAI1J1AI1J//AIJ选AI1J1,AI1J中最大的\}PRINTF“最大路径和是D\\N“,A11RETURN\}(9)设计算法求解最小M段和问题，并编程实现。(P81题38)(10)设计算法求解最少费用购物问题，并编程实现。(P88算法实现题314)注至少选择其中3题完成。3主要仪器设备及软件(1)PC机(2)TC、VC、JAVA等任一编程语言实验四贪心算法及其应用(验证型、设计型实验6学时)1目的要求(1)理解贪心算法的概念和基本要素；(2)掌握设计贪心算法的步骤，并编程实现有关问题的求解。2实验内容(1)编程实现活动安排问题的求解。(P91)VOIDSORTINTF,INTN\{//结束时间F排序INTTEMPFORINTI1IFJ1\{//结束时间按从早到晚排序TEMPFJFJFJ1FJ1TEMP\}\}COUTFJ\{//若下一活动开始时间晚于上一活动，则下一活动可安排，活动数COU

[41528d3028836879cd698677c3999917.gif]: /images/20221024/4ffcd276f71b4d6c8ec830a029989662.png