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

算法分析与设计实验报告PAGE 1PAGE 算法分析与设计实验报告（二） 计科1303 姓名：卢建斌 学号：2013310200313实验环境： Windows XP Microsoft?Visual?C++?6.0?实验目的： 1.通过对汽车加油问题算法的设计进一步掌握贪心算法的核心思想，更加熟练 灵活的运用贪心算法解决生活中的实际问题 2. 通过删数问题的算法设计，进一步掌握贪心算法的核心思想，更加熟练灵活 的运用贪心算法解决生活中的实际问题实验内容： 1、一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算 法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产生 一个最优解一个最优解 2、给定一个n位正整数a，删掉其中任意k(k=n)个位，剩下的按原顺序形成一 个新的正整数。找出剩下的数字最小的删数方案 实验步骤： 问题一:1、分析问题，确定问题的主要内容和核心思想，解决问题的思 路，确定解决问题时所要用到的算法以及怎么样去实现算法 2、打开实验环境，新建工程，开始编写代码 3、实验源代码: #includeiostream #include cstdlib using namespace std; int m[100]; int min(int a,int b,int c[]) { int i,j; int sum=0; for(i=0;i=b;i++) { if(c[i]a) { coutNo Solutionendl; exit(0); } }for(i=0,j=0;i=b;i++){ j=j+c[i]; if(ja) { sum++; j=c[i]; }}cout最少加油次数为sumendl;return 0;}int main(){int n,k,i;coutPlease input n and kendl;cinnk;cout请输入从第0个到第k个加油站之间的k+1个加油站距离endl; for(i=0;i=k;i++) { cinm[i]; } min(n,k,m); return 0;}编译解决编译问题，完成编译运行结果： 问题二:1、分析问题，确定问题的主要内容和核心思想，确定解决问题 时所要用到的算法以及怎么样去实现算法 2、打开实验环境，新建工程，开始编码 3、实验源代码: #include iostream #include string using namespace std; string greedy(string str, int n) { bool del; for (int i = n; i 0; i--) { del = false; // 每次删除第一个比下一个数字大的数 for (string::iterator it = str.begin(); it != str.end()-1; it++) { if (*it *(it+1)) { str.erase(it);//删除it处的一个字符 del = true; break; } } //如果所有数字递增，则删除最后几个数字直接返回 if (!del) { str.erase(str.end()-i, str.end()); break; } } return str; } int main() { int n; string str; cin str; cin n; c