上次面试的时候遇到这么一道题目:一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。
一个简单的算法如下:只要加油站站距小于汽车可行驶距离,就将其累加,累加标记打开,当累加的和大于行车距时,上一个加油站点便是必须要加油的站点,使用当前站距为起始累加;当累加的和等于行车距时,当前站点则为必须要加油的站点,使用累加站距清零,累加标记关闭;
namespace test
{
class Program
{
static void Main(string[] args)
{
int[] point = { 40, 20, 15, 12, 22, 15, 22, 10, 20, 30, 16, 15, 22, 16, 8, 2, 40, 22, 10, 5, 3 };
int distance = 40;
findAllPoint(point,distance);
}
private static void findAllPoint(int[] point, int distance)
{
for (int i = 0; i < point.Length; i++)
{
Console.Write(point[i] + " ");
}
Console.WriteLine();
Console.WriteLine("------------------------------------------");
//累加标记
bool countFlag = false;
//第N次加油
int jPoint = 1;
//累加存放
int sumValue = 0;
for (int i = 0; i < point.Length; i++)
{
//与行车距的检查
if (point[i] > distance)
{
Console.Write("行车距过大!!!");
break;
}
//与行车距相等
if ((point[i] == distance) && (countFlag == false))
{
Console.WriteLine("第{0}次加油是在站点{1}", jPoint, i);
jPoint++;
continue;
}
//比行车距相小,开始累加
if ((point[i] < distance) && (countFlag == false))
{
countFlag = true;
sumValue = point[i];
continue;
}
//有累加
if (countFlag == true)
{
//加上当前段距
sumValue = sumValue + point[i];
//比行车距大了
if (sumValue > distance)
{
countFlag = true;
sumValue = point[i];
Console.WriteLine("第{0}次加油是在站点{1}", jPoint, i - 1);
jPoint++;
continue;
}
//与行车距相等
if (sumValue == distance)
{
countFlag = false;
sumValue = 0;
Console.WriteLine("第{0}次加油是在站点{1}", jPoint, i);
jPoint++;
continue;
}
//继续累加
continue;
}
}
}
}
}
分享到:
相关推荐
在这个“汽车加油问题”中,我们将探讨如何应用贪心算法解决实际问题。 假设我们有一辆汽车,从起点出发,需要经过一系列距离到达终点,并且汽车的油箱容量有限。汽车在途中的每个加油站都可以加油,但不允许超过...
### 汽车加油问题算法设计 在计算机科学与算法领域中,“汽车加油问题”是一个典型的动态规划问题,旨在寻找一种最优策略来决定在哪些加油站加油以确保行驶全程且加油次数最少。这个问题不仅考验了算法设计的能力,...
本文将深入探讨如何运用贪心算法、回溯算法和动态规划算法来解决“汽车加油问题”。这三种算法各有其特点,适用于不同的问题场景。 首先,我们来看贪心算法。贪心算法是一种局部最优解策略,它每次做出当前状态下...
### 汽车加油问题分析 #### 问题背景 在本问题中,我们需要解决的是一个经典的计算机科学问题:如何在给定汽车满油时的最大行驶距离 \( n \) 公里以及一系列加油站的位置的情况下,计算出从起点到终点所需的最少...
在这个"【贪心算法】汽车加油问题C++"中,我们面对的是一个经典的问题:一辆汽车在行驶过程中需要在多个加油站之间加油,目标是找出最少的加油次数,使得汽车能够完成全程。 首先,我们需要理解问题的背景。假设...
### 贪心算法解汽车加油问题实验报告 #### 实验背景 在计算机科学领域,算法设计是一项重要的技能。其中,贪心算法是一种基于局部最优选择来试图获得全局最优解的方法。本次实验聚焦于利用贪心算法解决汽车加油...
### 汽车加油问题(贪心算法)C++实现 #### 一、问题背景与描述 本篇文章将深入探讨一个经典的计算机科学问题——汽车加油问题,并通过C++语言实现贪心算法解决这一问题。该问题的核心是:一辆汽车从起点出发前往...
在解决汽车加油问题时,我们可以利用贪心策略来制定策略,使得汽车在有限次加油情况下能够行驶到最远的距离。 这个问题的基本设定是:一辆汽车在行驶过程中需要加油,每次加油后可以继续行驶一定的距离。目标是在...
贪心法的汽车加油问题 贪心法是一种常用的算法思想,它的基本思想是每一步都选择当前看起来最优的解决方案,以期待能够得到最好的结果。贪心法常用于解决一些优化问题,例如这个例子中的汽车加油问题。 在这个问题...
汽车加油问题 一辆汽车加满油后,可行使n千米。旅途中有若干个加油站。若要使沿途加油次数最少,设计一个有效算法,对于给定的n和k个加油站位置,指出应在哪些加油站停靠加油才能使加油次数最少。 实验提示: 把两...
在这个问题中,我们关注的是一个名为“汽车加油问题”的算法挑战。这个问题通常出现在面试或编程竞赛中,旨在测试候选人的逻辑思维和问题解决能力。让我们深入探讨这个问题及其解决方案。 汽车加油问题的基本设定...
### 汽车加油问题程序算法 #### 问题背景与目标 在本问题中,我们需要设计一个有效的算法来解决一个实际场景中的优化问题:给定一辆汽车加满油后可以行驶的最大距离为n公里,以及旅途中k个加油站的位置(其中k ≤ ...
算法设计与分析 汽车加油问题 java int n,k; int count=0;//加油次数 BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); System.out.println("请输入汽车加满油后可行驶路程:"); ...
贪心法解汽车加油问题 算法分析与设计 。。。。。。。。。。。。。。。。
每个测试用例输入数据的第一行有2 个正整数n和k,表示汽车加满油后可行驶n公里,且旅途中有k个加油站。接下来的1 行中,有k+1 个整数,表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地,汽车已...
int greedy(int n,int k,int *d) //贪心策略:最远加油站优先 { int num = 0; for(int i = 0;i ;i++) //无法到达目的地 { if(d[i] > n) { cout; return NULL; } } for(int i = 0,s = 0;i ;i++...