月度存档: 12月 2005

[C] 贪心算法

去图书馆借了本算法与数据结构,第一节里有个贪心算法,回寝室便试了下,不想碰到了一些问题。

例1.1 快速送达疫苗

已 知有邻近的五个村子发生了疫情,见图1-1。我们要用汽车快速地将疫苗送达到5个村子,目标是寻找一条耗时最少的路线。

画图不方便就不放 了:)代码里s数组存放的就是各个村子之间的距离。

我用C写的代码如下:

#include <stdio.h>

int s[5][5]={

{0,1,2,7,5},

{1,0,4,4,3},

{2,4,0,1,2},

{7,4,1,0,3},

{5,3,2,3,0},

};

int visited[5]={0};

int mindis(int start)

{

int i;

int d=10;

int n;

for(i=0;i<5;i++)

{

if(visited[i]==0&&s[start][i]<d)

{

d=s[start][i];

n=i;

}

}

visited[n]=1;

return n;

}

void greedy(int start)

{

int cost;

int i;



阅读全文 »