算法设计与分析（王佳）算法分析与设计实验报告2

《算法设计与分析（王佳）算法分析与设计实验报告2》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法分析与设计实验报告(二)计科1303姓名：卢建斌学号：2013310200313实验环境：WindowsXPMicrosoftVisualC++6.0实验冃的：1.通过对汽车加油问题算法的设计进一步掌握贪心算法的核心思想，更加熟练灵活的运用贪心算法解决生活中的实际问题2.通过删数问题的算法设计，进一步掌握贪心算法的核心思想，更加熟练灵活的运用贪心算法解决生活中的实际问题实验内容：1、一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产生一个最优解一个最优解2

2、、给定一个n位正整数a,删掉其中任意k(k<=n)个位，剩下的按原顺序形成一个新的正整数。找出剩下的数字最小的删数方案实验步骤：问题一：1、分析问题，确定问题的主要内容和核心思想，解决问题的思路，确定解决问题吋所要用到的算法以及怎么样去实现算法2、打开实验环境，新建工程，开始编写代码3、实验源代码：#includeitincludeusingnamespacestd;intm[100];intmin(inta,intb,intc[]){inti,j;intsum=0;for(i=0;i<=b;i++)c

3、out«zzNoSolution〃《endl;exit(0);}}for(i=0,j=O;i〈=b;i++){j=j+c[i];if(j>a){sum++;j=c[i];}}cout«，z最少加油次数为，z«sum«endl;return0;}intmain(){intn,k,i;cout〈〈"Pleaseinputnandk"«endl;cin>>n>>k;cout«/z请输入从第0个到第，z«k«z，个加油站之间的个加油站距离，z«endl;for(i=0;i<=k;i++)min(n,k,m);return0;}4、编译解决编译问题，

4、完成编译5、运行结果：问题二：1、分析问题，确定问题的主要内容和核心思想，确定解决问题吋所要用到的算法以及怎么样去实现算法2、打开实验环境，新建工程，开始编码3、实验源代码：^include^include〈string>usingnamespacestd;stringgreedy(string&str,intn){booldel;for(inti二n;i>0;i--){del=false;//每次删除第一个比下一个数字大的数for(string::iteratorit=str・begin();it!=str.end()

5、-1;it++){if(*it>*(it+l)){str.erase(it);//删除it处的一个字符del=true;break;}}//如果所有数字递增，则删除最后几个数字直接返回if(!del){str.erase(str・end()-i,str・end());break;}}returnstr;}intmain(){intn;stringstr;cin>>str;cin>>n;cout<

6、p^[/XjtSdelete.exe请输入正整数.3和姜删降的位数口4562892S645删除后的最小数为=22564Px*ocesst;wi*ncexecu.t;xonf;xmc=20.588sPi*essanykeytocont;xnue.微软扌并音半二实验总结及感悟.这次实站G又仅是一次简单的算法的运用，更是一次运用所学知识解决现实中实际问题，把问题实现化，通过进一步掌握贪心算法的核心思想，更加熟练灵活的运用贪心算法解决生活中的实际问题，刚开始做实验没有一点的思路，通过看老师给的示例和解题思路以及网上的一些知识，慢

7、慢对问题的理解更加的深入，使问题也渐渐的清晰化,最后运用自己所学的知识去解决它，通过这次的实验，我对贪心算法的理解更加的深入，也更好的锻炼了我解决现实问题的能力。