算法复习题(全)(1)(5)

int x; int y;

int count=1; int tempx; int tempy;

while(count) {

count=0;

for (x=1;x<=N;x++) //其实x为内层，y为外层，对应坐标以及s的坐标系 {

for (y=1;y<=N;y++) {

if (x==1&&y==1) {

continue; }

int min_temp=100; int temp; int tx,ty; int fhop; int minfhop;

for (k=0;k<4;k++) {

tx=x+s[k][0]; ty=y+s[k][1];

if (tx<1||tx>9||ty<1||ty>9) //边界检查！！ {

continue; }

temp=f[tx][ty][0]+s[k][2]; fhop=f[tx][ty][1]-1;

if (p[x][y]==1) //有加油站 {

temp+=A; fhop=K; }

if ((fhop==0)&&(p[x][y]==0)&&(x!=N||y!=N)) //没有加油站，并且没有油了 {

temp+=A+C; fhop=K; }

21

if (temp

min_temp=temp; minfhop=fhop; tempx=tx; tempy=ty; } } if (f[x][y][0]>min_temp) //如果发现周围有更好的解，则替换f,c等记录路径 {

count++;

f[x][y][0]=min_temp; f[x][y][1]=minfhop; c[x][y].x=tempx; c[x][y].y=tempy; } } } }

for (i=1;i

for (j=1;j

cout<

cout<

cout<

while ((x!=1)||(y!=1)) {

int tempx;

printf(\ tempx=x; x=c[x][y].x; y=c[tempx][y].y; }

printf(\

22

free(c); free(p); }

3章 最优时间表问题，动态规划

#include #define maxn 100 #define maxk 20

void insertsort(int s[],int t[],int n) { int j;

for(int i=1;i

int temp1=s[i]; int temp2=t[i]; j=i-1;

while(j>=0&&s[j]>temp1) {

s[j+1]=s[j]; t[j+1]=t[j]; j--; }

s[j+1]=temp1; t[j+1]=temp2; } }

int main(int argc, char *argv[]) { int n,k;

int s[maxk],t[maxk]; int i,j;

int ans[maxn]; int sum[maxk]; scanf(\for(i=0;i

scanf(\%d\}

insertsort(s,t,k);//插入排序，以s[i]进行排序，这样做是为了方便求最小值

23

for(i=n+1;i>=1;i--) {

//若i大于最大的s[i]值，则m[i]等于0，因为没有维修任务 if(i>s[k-1]) ans[i]=0; //其他值赋值为-1 else ans[i]=-1; }

// 遍历数组s[i],ans[x]表示x到n的最小维修时间 for(j=k-1;j>=0;j--) {

//如果ans[x]没有计算过，则把第一次算到的值直接赋值给它 //此时还要做的一步是把s[j]到s[j+1]的ans赋值为ans[s[j+1]] //这一段就相当于没有维修任务的时刻 if(ans[s[j]]==-1) {

if(j!=(k-1))

for(i=s[j]+1;i

ans[s[j]]=ans[s[j]+t[j]]+t[j]; }

//若不为-1，则计算每次取最小值 else {

if(ans[s[j]]>ans[s[j]+t[j]]+t[j]) ans[s[j]]=ans[s[j]+t[j]]+t[j]; } }

//别忘了对0到s[0]的ans赋值 for(i=0;i

24

3，4章 石子合并问题，动态规划，贪心算法 1.动态规划算法

25