一、贪心算法
贪心算法暗示一种不追求最优解,只希望找到较为满意解的方法。贪心算法省去了为找最优解要穷尽所有可能而必须耗费大量时间,因此它一般可以快速得到较为满意的答案。贪心算法常常以当前情况为基础做最优选择,而不考虑各种的整体情况,所以贪心算法不需要回溯。
二、加油站问题
1、问题
一辆汽车加满油后可以行驶n千米,旅途中有若干个加油站(加油站是已经确定好的),为了使沿途加油次数最少,设计一个算法,输出最好的加油方案。
例如:假设沿途有9个加油站,总路程为100千米,加满油后汽车行驶的最远距离为20千米。
2、C语言解决
#include <stdio.h>
#define S 100
void main()
{
int i, j, n, k=0, total, dist;
int x[]= {10, 20, 35, 40, 50, 65, 75, 85, 100};
int a[10];
n= sizeof(x)/sizeof(x[0]);
printf("请输入最远行车距离(15<=n<100):");
scanf("%d",&dist);
total= dist;
j= 1;
while(total<S)
{
for(i=k; i<n; i++)
{
if(x[i]>total)
{
a[j]= x[i-1];
j++;
total= x[i-1]+dist;
k= i;
break;
}
}
}
for(i=1; i<j; i++)
printf("%4d",a[i]);
}
《The Function and Algorithm of Program Language C/C++》
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)