《算法设计与分析》实验报告4

 

实验名称: 汽车加油跑路程问题

系    别:xxx           

专    业:xxx           

班    级:xxx

姓    名:xxx          

学    号:xxx

实验日期:xx年xx月xx日

 

1.  算法题目

根据贪心法的设计思想和算法步骤，要求学生设计一个贪心算法，用于解决汽车加油跑路程的问题。汽车行驶n公里的路程，中间有m个加油站。每次要加油时，选择能让剩余汽油跑最远距离的加油站，加满汽油。因此，设计一个指标=剩余汽油能跑最长距离的加油站j，依次考虑在后续路程中存在的加油站，即可进行贪心操作。因此使用贪心算法可以解决该问题。

 

2.  设计思路与步骤

首先判断加油站的距离是否都不大于汽车一次最多能行驶的距离；

定义temp为汽车还能走的距离，判断temp是否大于下个加油站的距离，若不足则在下个加油站加油（令choice[i]=1），否则不在下个加油站加油（令choice[i]=0）；

最后输出选择的加油站即可。

 

3.  算法实现与代码

#include<stdio.h>

#include<stdlib.h>

int main() {

int n, m, i, journey = 0, temp = 0, j = 1;

int a[20] = {0};

int choice[20] = {0};

printf("请输入汽车加满油可以行使的路程：");

scanf("%d", &n);

printf("请输入加油站的个数：");

scanf("%d", &m);

a[0] = 0;

for(i = 1; i <= m; i++) {

printf("请输入第%d个加油站与第%d个加油站的距离：", i-1, i);

scanf("%d", &a[i]);

journey = journey + a[i];

}

for(i = 1; i <= m; i++)

if(a[i] > n) {

printf("加油站过远！汽车无法到达！请选择其他路线！\n");

exit(0);

}

temp = n;

for(i = 0; i < m; i++) {

if(temp < a[i + 1]) {

choice[i] = 1;

temp = n - a[i + 1];

}

else {

choice[i] = 0;

temp = temp - a[i + 1];

}

}

printf("\n选择的加油站为：");

for(i = 1; i <= m; i++)

if(choice[i] == 1)

printf(" %d", i);

printf(" %d", m);

return 0;

}

4.  测试用例与结果

5.  问题与总结:

答：xxx。