月度存档: 十二月 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;

int n;

int ss;

ss=start-1;

printf(“%d”,start);

visited[ss]=1;

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

{

n=mindis(ss);

cost+=s[ss][n];

printf(“-%d”,n+1);

ss=n;

}

cost+=s[ss][start-1];

printf(“-%d\ncost is:%d\n”,start,cost);

}

int main()

{

greedy(1);

return 0;

}

在 写时,调试了好几次,再查了一下书才真正搞定。

1. 数组的初始化。

在初始化村子距离数组时,我先用的是这样语句:

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),

};

结 果弄了半天得不到正确结果,把小括号改成花括号后才解决了问题。数组初始化时用花括号是按行初始化。

2. 数组下标起始值

数 组的下标起始值应为0,在开始时我却没有想到,在mail()里传过来的1就直接用进去了,结果是输出里有一个超大的值。

当然了,我写的这 个并不好,以上的问题也只是我个人的见解,如果有什么错误还望指点一二:)