《算法設(shè)計與分析》實驗報告4

?

實驗名稱: 汽車加油跑路程問題

系????別:xxx???????????

專????業(yè):xxx? ? ? ? ? ?

班????級:xxx

姓????名:xxx? ? ? ? ??

學(xué)????號:xxx

實驗日期:xx年xx月xx日

?

1. ?算法題目

根據(jù)貪心法的設(shè)計思想和算法步驟，要求學(xué)生設(shè)計一個貪心算法，用于解決汽車加油跑路程的問題。汽車行駛n公里的路程，中間有m個加油站。每次要加油時，選擇能讓剩余汽油跑最遠(yuǎn)距離的加油站，加滿汽油。因此，設(shè)計一個指標(biāo)=剩余汽油能跑最長距離的加油站j，依次考慮在后續(xù)路程中存在的加油站，即可進(jìn)行貪心操作。因此使用貪心算法可以解決該問題。

?

2. ?設(shè)計思路與步驟

首先判斷加油站的距離是否都不大于汽車一次最多能行駛的距離；

定義temp為汽車還能走的距離，判斷temp是否大于下個加油站的距離，若不足則在下個加油站加油（令choice[i]=1），否則不在下個加油站加油（令choice[i]=0）；

最后輸出選擇的加油站即可。

?

3. ?算法實現(xiàn)與代碼

#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("請輸入加油站的個數(shù)：");

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("加油站過遠(yuǎn)！汽車無法到達(dá)！請選擇其他路線！\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. ?測試用例與結(jié)果

5. ?問題與總結(jié):

答：xxx。

?