算法设计与分析（王佳）《算法分析与设计》实验二.docxVIP

《算法分析与设计》实验二 问题一：汽车加油问题 实验目的： 通过对汽车加油问题算法的设计进一步掌握贪心算法的核心思想，更加熟练灵活的运用贪心算法解决生活中的实际问题。 实验内容： 1）内容描述：一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产生一个最优解。 2）编程任务：对于给定的n 和k 个加油站位置，编程计算最少加油次数。 3）数据输入： 第一行有2个正整数n和k，表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1 行中，有k+1 个整数，表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地，汽车已加满油。第k+1 个加油站表示目的地。 4）结果输出: 输出编程计算出的最少加油次数。如果无法到达目的地，则输出”No Solution”。 思路：汽车行驶过程中，应走到自己能走到并且离自己最远的那个加油站，在那个加油站加油后再按照同样的方法继续行进。运用贪心算法的贪心思想，每一步是局部最优从而达到全局最优。开始时，将汽车中的油的数量初始化为给定的最大值，每到一个加油站就在油的基础上减去所经过的这段距离所消耗的油的数量，再将剩余的油量再与从该加油站到下一个加油站的距离所需要的油量相比，若剩余油量大，则在此站不加油，若剩余油量小，则在此站再次将油加满，记录加油次数的变量加一，并记录该加油站的编号，依此类推。 问题二：删数问题 实验目的： 通过删数问题的算法设计，进一步掌握贪心算法的核心思想，更加熟练灵活的运用贪心算法解决生活中的实际问题。 实验内容： 给定一个n位正整数a，删掉其中任意k(k=n)个位，剩下的按原顺序形成一个新的正整数。找出剩下的数字最小的删数方案。 1）编程任务： 给定正整数a，删掉k位数字，计算剩下的最小数字。 2）数据输入： n位正整数a0，删掉的位数k（0k=n）。 3）结果输出: 最小的剩下的数。 示例输入输出： 输入 a=178543，k=4 输出 13 参考代码 问题一： #include stdio.h void greedy(int d[],int n,int k) { int num = 0; for(int i = 0;i k;i++) { if(d[i] n) { printf(no solution/n); return; } } for(int i = 0,s = 0;i k;i++) { s += d[i]; if(s n) { num++; s = d[i]; } } printf(%d/n,num); } int main() { int i,n,k; int d[1000]; scanf(%d %d,n,k); for(i = 0;i k;i++) scanf(%d,d[i]); greedy(d,n,k); }