25-伪代码详解

4.5.4　伪代码详解

（1）最少租金求解函数

设计中n表示有n个出租站，设置二维数组m[][]，初始化时用来记录从i到j之间的租金r[][]，在不同规模的子问题（d=3，4，…，n）中，按照递推公式计算，如果比原值m[][]小，则更新m[][]，同时用s[][]记录停靠的站点号，直接最后得到的r[1][n]即为最后的结果。

void rent()
{
     int i,j,k,d;
     for(d=3;d<=n;d++) //将问题分为小规模d
     {
          for(i=1;i<=n-d+1;i++)
               {
                    j=i+d-1;
                    for(k=i+1;k<j;k++)  //记录每一个小规模内的最优解
                    {
                         int temp;
                         temp=m[i][k]+m[k][j];
                         if(temp<m[i][j])
                               {
                                 m[i][j]=temp;
                                 s[i][j]=k;
                               }
                    }
               }
     }
}

（2）最优解构造函数

根据s[][]数组构造最优解，s[i][j]将问题分解为两个子问题（i，…，s[i][j]）、（s[i][j]，…，j），递归求解这两个子问题。当s[i][j]=0时，说明中间没有经过任何站点，直达站点j，输入j，返回即可。

void print(int i,int j)
{
     if(s[i][j]==0 )
     {
          cout << "--"<<j;
          return ;
     }
     print(i,s[i][j]);
     print(s[i][j],j);
}