学生实验贪心算法解汽车加油问题

汽车加油问题
1.题目：
汽车加油问题：一辆汽车加满油后可行驶n 公里。

旅途中有若干个加油站。

设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。

2.算法步骤：
1.请求输入数组并规定格式以及代表意义。

2.以字符串形式读取数组并初始化数组。

3.建立循环求距离之和并判断是否需要加油，如果需要继续
执行否则停止程序。

4.建立循环判断当前油量是否足够到达下一个加油站，如果
不够则输出当前加油站的序号并刷新油量为最大油量，如果足够则仅刷新油量进入下一次循环。

3.源代码：
package汽车加油问题贪心;
import class Greedy {
public static void main(String[] args) {
"请输入一个数组，数组元素依此表示：汽车满油量行驶距离、距第一个加油站的距离、各个加油站之间的间距");
"(注意加油站距离不得大于最大行驶距离)");
Scanner in=new Scanner;
int f=0,b=0,c=0;
String h=();
2.。

实验3贪心算法（定稿）第一篇：实验3 贪心算法（定稿）《算法设计与分析》实验报告实验3贪心算法姓名学号班级实验日期实验地点一、实验目的1、掌握贪心算法的设计思想。

2、理解最小生成树的相关概念。

二、实验环境1、硬件环境 CPU：酷睿i5 内存：4GB 硬盘：1T2、软件环境操作系统：Windows10 编程环境：jdk 编程语言：Java三、实验内容：在Prim算法与Kruskal算法中任选一种求解最小生成树问题。

1、你选择的是：Prim算法2、数据结构（1）图的数据结构——图结构是研究数据元素之间的多对多的关系。

在这种结构中，任意两个元素之间可能存在关系，即结点之间的关系可以是任意的，图中任意元素之间都可能相关。

图形结构——多个对多个，如（2）树的数据结构——树结构是研究数据元素之间的一对多的关系。

在这种结构中，每个元素对下(层)可以有0个或多个元素相联系，对上(层)只有唯一的一个元素相关，数据元素之间有明显的层次关系。

树形结构——一个对多个，如3、算法伪代码 Prim(G,E,W)输入：连通图G 输出：G的最小生成树T 1.S←{1};T=∅ 2.While V-S ≠∅ do3.从V-S中选择j使得j到S中顶点的边e的权最小；T←T∪{e}4.S←S∪{j}3、算法分析时间复杂度：O(n)空间复杂度：O(n^2)4、关键代码（含注释）package Prim;import java.util.*;publicclass Main { staticintMAXCOST=Integer.MAX_VALUE;staticint Prim(intgraph[][], intn){ /* lowcost[i]记录以i为终点的边的最小权值，当lowcost[i]=0时表示终点i加入生成树 */ intlowcost[]=newint[n+1];/* mst[i]记录对应lowcost[i]的起点，当mst[i]=0时表示起点i加入生成树 */ intmst[]=newint[n+1];intmin, minid, sum = 0;/* 默认选择1号节点加入生成树，从2号节点开始初始化*/ for(inti = 2;i<= n;i++){/* 标记1号节点加入生成树 */ mst[1] = 0;/* n个节点至少需要n-1条边构成最小生成树 */ for(inti = 2;i<= n;i++){/* 找满足条件的最小权值边的节点minid */ for(intj = 2;j<= n;j++){/* 输出生成树边的信息:起点，终点，权值 */System.out.printf(“%c1, minid + 'A''A' + 1;intj = chy-'A' + 1;graph[i][j] = cost;graph[j][i] = cost;for(intj = 1;j<= n;j++){ } graph[i][j] = MAXCOST;} } System.out.println(”Total:"+cost);} }5、实验结果（1）输入（2）输出最小生成树的权值为：生成过程：(a)(b)(d)(e)(c)四、实验总结（心得体会、需要注意的问题等）这次实验，使我受益匪浅。

贪心算法实验报告贪心算法实验报告引言：贪心算法是一种常用的算法设计策略，它通常用于求解最优化问题。

贪心算法的核心思想是在每一步选择中都选择当前最优的解，从而希望最终能够得到全局最优解。

本实验旨在通过实际案例的研究，探索贪心算法的应用和效果。

一、贪心算法的基本原理贪心算法的基本原理是每一步都选择当前最优解，而不考虑整体的最优解。

这种贪婪的选择策略通常是基于局部最优性的假设，即当前的选择对于后续步骤的选择没有影响。

贪心算法的优点是简单高效，但也存在一定的局限性。

二、实验案例：零钱兑换问题在本实验中，我们以零钱兑换问题为例，来说明贪心算法的应用。

问题描述：假设有不同面值的硬币，如1元、5元、10元、50元和100元，现在需要支付给客户x元，如何用最少的硬币数完成支付？解决思路：贪心算法可以通过每次选择当前面值最大的硬币来求解。

具体步骤如下：1. 初始化一个空的硬币集合，用于存放选出的硬币。

2. 从面值最大的硬币开始，如果当前硬币的面值小于等于待支付金额，则将该硬币放入集合中，并将待支付金额减去该硬币的面值。

3. 重复步骤2，直到待支付金额为0。

实验过程：以支付金额为36元为例，我们可以通过贪心算法求解最少硬币数。

首先，面值最大的硬币为100元，但36元不足以支付100元硬币，因此我们选择50元硬币。

此时，剩余待支付金额为36-50=-14元。

接下来，面值最大的硬币为50元，但待支付金额为负数，因此我们选择下一个面值最大的硬币，即10元硬币。

此时，剩余待支付金额为-14-10=-24元。

继续选择10元硬币，剩余待支付金额为-24-10=-34元。

再次选择10元硬币，剩余待支付金额为-34-10=-44元。

最后，选择5元硬币，剩余待支付金额为-44-5=-49元。

由于待支付金额已经为负数，我们无法继续选择硬币。

此时，集合中的硬币数为1个50元和3个10元，总共4个硬币。

实验结果：通过贪心算法，我们得到了36元支付所需的最少硬币数为4个。

贪心算法实验报告心得前言贪心算法是一种常见且重要的算法设计思想，通过每一步都选择当下最优的解决方案，以期望最终得到全局最优解。

在学习与实践贪心算法的过程中，我有了许多心得与体会。

什么是贪心算法？贪心算法是一种求解问题的算法思想，它的特点是每一步都选择当前最优的解决方案，而不考虑该选择对以后步骤的影响。

贪心算法通常适用于可以将问题分解为若干个子问题，并且通过每次选择当前最优解来得到整体最优解的情况。

贪心算法的基本步骤贪心算法的基本步骤可以总结为以下几个方面：1.确定问题的解空间，并找到问题的最优解。

贪心算法通常通过穷举法或者利用问题的特殊性质来确定解空间。

2.制定贪心策略。

贪心算法的核心是确定每一步选择的贪心策略，即选择当前最优解。

3.确定贪心策略的正确性。

贪心算法的一个关键问题是如何证明贪心策略的正确性。

可以通过数学证明、反证法或者举反例等方式来进行证明。

4.实现贪心算法。

将贪心策略转化为实际可执行的算法步骤，编写代码来求解问题。

贪心算法实验结果分析在本次实验中，我使用贪心算法解决了一个经典问题：找零钱问题（Change-Making Problem）。

给定一定面额的硬币和需找的金额，我们的目标是使用最少的硬币来完成找零钱。

贪心算法的思路是每次选择面额最大的硬币进行找零。

实验设计1.实验输入：我设计了多组输入来测试贪心算法的性能。

每组输入包括一个需找的金额和一个硬币集合。

2.实验输出：对于每组输入，贪心算法输出一个最优的硬币找零方案，以及使用的硬币数量。

3.实验评价：我使用了实际需找金额与贪心算法计算得到的找零金额的差值来评估算法的准确性，并统计了算法的时间复杂度。

实验结果从多组实验结果中可以观察到，贪心算法在大部分情况下给出了正确的找零金额，并且算法的时间复杂度较低。

结果分析贪心算法在找零钱问题中的应用是合理的。

每次选择面额最大的硬币进行找零，可以快速接近最优解，并且相对其他算法具有较低的时间复杂度。

汽车加油问题之贪心算法（一）问题描述一辆汽车加满油后可以行驶N千米。

旅途中有若干个加油站。

指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。

给出N，并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。

要求：算法执行的速度越快越好。

（二）问题分析（前提行驶前车里加满油）对于这个问题我们有以下几种情况：设加油次数为k，每个加油站间距离为a[i]；i=0，1，2，3……n1.始点到终点的距离小于Ｎ，则加油次数k=0；2.始点到终点的距离大于N，A 加油站间的距离相等，即ａ[i]=a[j]=L=N，则加油次数最少k=n；B 加油站间的距离相等，即ａ[i]=a[j]=L>N，则不可能到达终点；C 加油站间的距离相等，即ａ[i]=a[j]=L<N，则加油次数k=n/N(n%N==0)或k=[n/N]+1(n%N！=0)；D 加油站间的距离不相等，即ａ[i]！=a[j]，则加油次数k通过以下算法求解。

（三）算法描述贪心算法的基本思想该题目求加油最少次数，即求最优解的问题，可分成几个步骤，一般来说，每个步骤的最优解不一定是整个问题的最优解，然而对于有些问题，局部贪心可以得到全局的最优解。

贪心算法将问题的求解过程看作是一系列选择，从问题的某一个初始解出发，向给定目标推进。

推进的每一阶段不是依据某一个固定的递推式，而是在每一个阶段都看上去是一个最优的决策（在一定的标准下）。

不断地将问题实例归纳为更小的相似的子问题，并期望做出的局部最优的选择产生一个全局得最优解。

贪心算法的适用的问题贪心算法适用的问题必须满足两个属性：（１）贪心性质：整体的最优解可通过一系列局部最优解达到，并且每次的选择可以依赖以前做出的选择，但不能依赖于以后的选择。

（２）最优子结构：问题的整体最优解包含着它的子问题的最优解。

贪心算法的基本步骤（１）分解：将原问题分解为若干相互独立的阶段。

A卷一、选择题1.二分搜索算法是利用（A ）实现的算法。

A、分治策略B、动态规划法C、贪心法D、回溯法2. 回溯法解旅行售货员问题时的解空间树是（ A ）。

A、子集树B、排列树C、深度优先生成树D、广度优先生成树3.下列算法中通常以自底向上的方式求解最优解的是（B ）。

A、备忘录法B、动态规划法C、贪心法D、回溯法4．下面不是分支界限法搜索方式的是（ D ）。

A、广度优先B、最小耗费优先C、最大效益优先D、深度优先5．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为 ( B ) 。

A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）6．分支限界法解最大团问题时，活结点表的组织形式是（ B）。

A、最小堆B、最大堆C、栈D、数组7、下面问题（B ）不能使用贪心法解决。

A 单源最短路径问题B N皇后问题C 最小花费生成树问题D 背包问题8.下列算法中不能解决0/1背包问题的是（A ）A 贪心法B 动态规划C 回溯法D 分支限界法9.背包问题的贪心算法所需的计算时间为（ B ）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）10.背包问题的贪心算法所需的计算时间为（B ）。

A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）二、填空题1.算法的复杂性有复杂性和复杂性之分。

2.算法是由若干条指令组成的有穷序列，且要满足输入、、确定性和四条性质。

其中算法的“确定性”指的是组成算法的每条是清晰的，无歧义的。

3.解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是，需要排序的是，。

4.动态规划算法的两个基本要素是. 性质和性质。

5.回溯法是一种既带有又带有的搜索算法；分支限界法是一种既带有又带有的搜索算法。

6. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。

在任何时刻，算法只保存从根结点到当前扩展结点的路径。

贪⼼算法--汽车加油问题基本要素：贪⼼选择：在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

最优⼦结构：当⼀个问题的最优解包含其⼦问题的最优解时，称此问题具有最优⼦结构性质。

过程：1. 建⽴数学模型来描述问题；2. 把求解的问题分成若⼲个⼦问题；3. 对每⼀⼦问题求解，得到⼦问题的局部最优解；4. 把⼦问题的解局部最优解合成原来解问题的⼀个解。

汽车加油问题⼀辆汽车加满油后可⾏驶 n公⾥。

旅途中有若⼲个加油站。

设计⼀个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。

输⼊格式:第⼀⾏有 2 个正整数n和 k（k<=1000 )，表⽰汽车加满油后可⾏驶n公⾥，且旅途中有 k个加油站。

第⼆⾏有 k+1 个整数，表⽰第 k 个加油站与第k-1 个加油站之间的距离。

第 0 个加油站表⽰出发地，汽车已加满油。

第 k+1 个加油站表⽰⽬的地。

输出格式:输出最少加油次数。

如果⽆法到达⽬的地，则输出“No Solution!”。

输⼊样例:7712345166输出样例:4贪⼼性质分析：找到汽车满油量时可以⾏驶的最⼤路程范围内的最后⼀个加油站，加油后则继续⽤此⽅法前进。

需要检查每⼀⼩段路程是否超过汽车满油量时的最⼤⽀撑路程。

代码#include<iostream>using namespace std;int n,k;int a[1000];int main(){ cin>>n>>k; for(int i=0;i<=k;i++) cin>>a[i]; int minCount=0,drive=n; bool flag=true; for(int i=0;i<=k;i++){ if(drive-a[i]>=0) drive-=a[i]; else{ drive=n; drive-=a[i]; if(drive<0)flag=false; minCount++;}} if(!flag)cout<<"No Solution!"<<endl; else cout<<minCount<<endl; return 0;}遇到的问题及结对情况刚开始解决输出"No Solution!"时，采⽤直接打印然后break，犯了⽐较低级的错误。

汽车加油问题1. 问题描述一辆汽车加油满后可行驶n千米，旅途中有若干加油站（不包含汽车的出发点）。

假如在出发时已加满油，设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少，并给出加油的地点。

证明算法能产生一个最优解。

算法设计：对于给定的n和k个加油站位置，计算最少加油次数。

2. 算法流程分析设汽车加满油后可行驶n千米，且除了出发点和目的地，旅途中有k个加油站。

把目的地假设为最后一个加油站，有k个加油站。

令数组x存储加油站间距，x[i]表示第i-1个加油站到第i 个加油站之间的距离。

x[0]即出发地到0号加油站的距离。

x[k-1]是第k-2个加油站到第k-1个加油站即终点的距离。

判断s加上x[i]后是否超出n，若超出则必定在i-1处加了油a[i-1]=true ，sum加1表示加油次数加一，且加油后里程从0开始计算，从i-1到达到i处里程为x[i]。

i++进入下一轮，即判断下一个加油站是否能到达。

3. 算法正确性证明通过几组实例证明合法的输入可以得到正确的输出。

实例见附录第2部分。

4. 算法复杂度分析O（n）5.参考文献[1] 王晓东编著，计算机算法设计与分析（第4版）。

北京：电子工业出版社，2012.26.附录（1）可执行代码如下：#include<iostream>using namespace std;int main(){int j,n,k,x[10],c=0,m=0;bool a[10];cout<<"请输入汽车加满油后可行驶的距离（km）: ";cin>>n;cout<<"请输入旅途中所经过的加油站个数：";cin>>k;cout<<"请输入每两个相邻加油站之间的距离："<<endl;for(int i=0;i<=k;i++)cin>>x[i];for(i=0;i<=k;i++)a[i]=false;for(j=0;j<=k;j++){m+=x[j];if(m+x[j+1]>=7){a[j+1]=true;m=0;}}cout<<"在第";for(int s=0;s<=k;s++)if(a[s]==true){c++;cout<<s<<" ";}cout<<"个加油站加油了。

实验2、《贪心算法实验》一、实验目的1. 了解贪心算法思想2. 掌握贪心法典型问题，如背包问题、作业调度问题等。

二、实验内容1. 编写一个简单的程序，实现单源最短路径问题。

2. 编写一段程序，实现找零。

【问题描述】当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少）。

3. 编写程序实现多机调度问题【问题描述】要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m 台机器加工处理完成。

约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。

作业不能拆分成更小的子作业。

三、算法思想分析1.初始化将源点设计为红点集，其余点设计为蓝点，重复选择蓝点集中与源点路径最短的点加入红点集，更新剩余的蓝点集路径，直至蓝点集为空或者只剩下没有连通的点，那么源点到其余所有点的最短路径就出来了。

2.找零问题是典型的贪心问题，但是并不代表所有的找零都能用贪心算法找到最优解。

只有满足贪心选择性质的找零才能找到最优解，本题满足贪心选择性质，直接先一直选面值最大的硬币，再一次减小即可。

3.先对作业按时长进行重排序，再依次找目前用时最短的机器安排工作并加上对应时长，最后总时长为机器中用时最长的那个时长。

四、实验过程分析1.单源最短路径的算法思想并不难，但是在实际编码过程中还是有很多小问题需要注意，首先，一定要新建数组存储路径变化，因为后面计算路径时会用到原数组，如果直接在原数组上更改后面就找不到原数据了，那么就会出现偏差。

其次就是建议先写个伪代码，判断的if-else语句比较多，容易搞混，在代码中一定要及时备注，某些代码的功能是什么，不然再次看代码时需要思考很久甚至忘记。

2.找零问题直接用while循环或者不断取余取模即可解决。

3.作业调度问题大致分为三步，一是排序，二是不断找最短时长的机器安排作业，三是找最长时间为作业完成时间。

五、算法源代码及用户屏幕1.（1）算法源码/**********************单源最短路径问题。

贪心算法实验报告实验报告题目实验四贪心算法开课实验室:数学实验室指导老师:韩逢庆时间:2011.12 学院:理学院专业:信息与计算科学班级:2009级2班姓名:古月学号:09180230一、实验目的1(加深学生对贪心算法设计方法的基本思想、基本步骤、基本方法的理解与掌握;2(提高学生利用课堂所学知识解决实际问题的能力;3(提高学生综合应用所学知识解决实际问题的能力。

二、实验内容题目见P143:4-16,4-23.三、实验要求(1)用分治法求解最少加油次数和最少硬币个数问题;(2 )再选择自己熟悉的其它方法求解本问题;(3)上机实现所设计的所有算法;四、实验过程设计(算法设计过程)(1) 最少加油次数实验题目一辆汽车加满油以后可以行使n公里，旅途中有若干个加油站，设计一个有效算法，指出应在哪些加油站停靠加油，使沿路加油次数最少。

并证明算法能产生一个最优解。

过程设计贪心算法总是作出在当前看来最好的选择。

也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

当然，希望贪心算法得到的最终结果也是整体最优的。

虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。

比如说最少加油次数的问题。

在这个算法中，我采用的贪心算法的策略。

首先人机互动的设定加满油以后最长能够行使的距离，然后输入了各个站点之间的距离，在程序的设计中，首先检查了程序的可行性。

要是遇到当某两个站点之间的距离大于汽车一次加油以后所能够行使的最大距离时，我们认为此问题是不可行的。

这个在实际情况中也是很容易理解的。

然后在满足可行性条件下，依次采用贪心算法对问题得以实现。

采用s这个来保存现在车里面留下的油，当此时留下的有能够行驶完这一站点到下一站点之间的距离是，在这一站点的时候就不加油。

但是若不能行使完这一段路程的时候，就加满油。

核心算法如下:for(i=0,s=0;i<n;i++){s=s+a[i];if(s>n){sum++;s=a[i];}}(2) 最少硬币个数问题实验题目考虑下面的用最少硬币个数找出n分钱的问题:当使用2角5分，1角，5分和1分四种硬币面值时，设计一个找n分钱的贪心算法，并证明算法能产生最优解。

中原工学院计算机学院实验报告实验项目名称实验二、最少活动会场安排问题课程名称算法设计与分析学生姓名梁斐燕学生学号************所在班级网络14卓越学科专业网络工程任课教师吴志刚完成日期2016年月日实验二最少活动会场安排问题一、实验目的1．掌握贪心算法的基本概念和两个基本要素2．熟练掌握贪心算法解决问题的基本步骤。

3．学会利用贪心算法解决实际问题。

二、实验内容•问题描述：•题目一：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。

设计一个有效的贪心算法来进行安排，试编程实现。

•题目二：一辆汽车加满油后,可行使n千米。

旅途中有若干个加油站。

若要使沿途加油次数最少,设计一个有效算法，指出应在哪些加油站停靠加油。

•数据输入：个人设定，由键盘输入。

•要求：–上述题目任选一做。

上机前，完成程序代码的编写–独立完成实验及实验报告三、实验步骤㈠、数据结构与核心算法的设计描述提示：题目一：参考教材活动安排问题；有关队列操作参考数据结构。

void GreedySelector(int n, int *s, int *f, int *A) {//用集合A来存储所选择的活动A[1] = TURE; //默认从第一次活动开始执行int j = 1; //j记录最近一次加入到A中的活动for (int i = 2; i <= n; i++) { //f[j]为当前集合A中所有活动的最大结束时间//活动i的开始时间不早于最近加入到集合A中的j的时间f[j]if (s[i] >= f[j]) {A[i] = TURE; //当A[i]=TURE时，活动i在集合A中j = i;}else A[i] = FALSE;}}㈡、函数调用及主函数设计㈢程序调试及运行结果分析㈣实验总结在做本实验之前，自己看了课本上所列举的贪心法解活动安排问题的代码，代码很简单，很容易理解，于是就按课本的代码实现。

通过几个测试用例测试发现结果不对，后来发现自己忘了进行贪心法的一个前提条件，事先没有按各个活动结束时间对所有活动进行非递减排序，所以才会导致结果错误。

华东师范大学计算机科学技术系上机实践报告课程名称：算法设计与分析年级：05上机实践成绩：指导教师：柳银萍姓名：张翡翡上机实践名称：贪心算法学号：10052130119上机实践日期：2007-4-10上机实践编号：NO.2组号：上机实践时间：10:00-11:30一、目的了解熟悉掌握贪心算法实质并学会灵活运用，从而解决生活中一些实际问题。

二、内容与设计思想1.超市的自动柜员机(POS)要找给顾客各种数值的现金，表面上看，这是一个很简单的任务，但交给机器办就不简单了。

你作为一个计算机专家，要求写一个程序来对付这个“简单”的问题。

你的自动柜员机有以下的币种：100元，50元，20元，10元，5元，2元，1元。

你可以假设每种钱币的数量是无限的。

现在有一笔交易，需要找个客户m元，请你设计一个算法，使得找给顾客的钱币张数最少。

要求：输入：第一行仅有一个整数n(0<n<=10000),表示有几组测试数据。

每组测试数据仅有一行，每行只有一个整数m(0<m<2000000000)，表示需要找的钱币数。

(提示：对于大量的输出，请使用scanf,不要使用cin)输出：每组测试数据输出一行，每行有7个整数(两两之间有一个空格，结尾不能有空格)，表示100元，50元，20元，10元，5元，2元，1元所需要的张数。

1.1其思路是：1)定义相关变量；2)接收相关数据，如测试数据组数n和要找的钱币数；3)依次考虑100，50，20，10，5，2，1的需要找的钱币张数，用最简单的加减乘除；4)输出其值。

1.2具体算法是：while(n--)m 输入a=m/100b=(m-100*a)/50c=(m-100a-50b)/20d=(m-100a-50b-20c)/10e=(m-100a-50b-20c-10d)/5f=(m-100a-50b-20c-10d-5e)/2g=m-100a-50b-20c-10d-5e-2fend while2.若在0-1背包问题中各物品是依重量递增排列时，其价值恰好依递减序排列。

题目汽车加油问题论文提要一辆汽车加满油后可行驶n公里，旅途中有若干个加油站，设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少，对于给定的n和k个加油站位置，编程计算最少加油次数。

可以利用贪心选择性质来求解汽车加油问题，也就是所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。

这是贪心选择算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

在动态规划算法中，每步所做的选择往往信赖于相关子问题的解，因而只有在解出相关子问题后，才能做出选择。

而在贪心算法中仅在当前状态下做出最好选择，即局部最优选择，然后再去解出这个选择后产生的相应的子问题，贪心算法所做的贪心选择可以依赖于以往所做过的选择，但决不依赖于将来所做的选择，也不依赖于子问题的解。

关于汽车加油问题摘要：汽车行驶过程中，应走到自己能走到并且离自己最远的那个加油站，在那个加油站加油后再按照同样的方法，其中保持车子每次加油都能够行驶最远距离。

当然有可能是达到不了终点的情况，也就是存在某两个加油站之间的距离大于每次加油能够行驶的最远距离，首先检测各加油站之间的距离，若发现其中有一个距离大于汽车加满油能跑的距离，则输出“No Solution”。

否则，对加油站间的距离进行逐个扫描，尽量选择往远处走，不能走了就让num++，最终统计出来的num便是最少的加油站数。

关键词：汽车加油贪心性质最优化问题一、汽车加油问题描述一辆汽车加满油后可行驶n公里，旅途中有若干个加油站，设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。

对于给定的n和k个加油站位置，编程计算最少加油次数。

并证明算法能产生一个最优解。

输入：第一行有个正整数n和k，表示汽车加满油后可行驶n公里，且旅途中有k个加油站。

接下来的行驶中，有k+1 个整数，表示第k个加油站与第k-1 个加油站之间的距离。

第k个加油站表示出发地，汽车已加满油。

第k+1 个加油站表示目的地。