数字三角问题与租用游艇问题
数字三角问题与租用游艇问题
Cynthia_x 发表于1年前
数字三角问题与租用游艇问题
  • 发表于 1年前
  • 阅读 85
  • 收藏 0
  • 点赞 0
  • 评论 0

移动开发云端新模式探索实践 >>>   

1. 数字三角问题:对于给定的由n 行数字组成的数字三角形,编程计算从三角形的顶至底的路径经过的数字和的最大值。如下图: 

                7

            3    8

         8    1    0

     2    7    4     4

  4    5    2     6    5

分析:如果得到一条由顶至底的某处的一条最佳路径,那么对于该路径上的每一个中间点来说,由顶至该中间点的路径所经过的数字和也为最大。

例 如:将5阶数字三角形问题变为4阶数字三角形问题,递推出第4层与第5层的和:9(2+7), 25(18+7), 13(9+4), 9(5+4),用同样的方法可以将4阶数字三角形问题,变为3阶数字三角形问题……最后得到的1阶数字三角形问题,就是整个问题的最优解。

其存储、求解则为:原始信息有层数和数字三角形中的数据,层数用一个整型变量n存储,数字三角形中的数据用二维数组,那么动态规划过程存储则可表示:必需用二维数组d存储各阶段的决策结果。

二维数组d的存储内容如下:d[n][j]=data[n][j]: j=1,2,……,n;i=n-1,n-2,……1,j=1,2,……,i时d[i][j]=min(d[i+1][j], d[i+1][j+1])+data[i][j]

最后d[1][1]存储的就是问题的结果(最小数值和)。即,数组d是自底向上递推定义最优值的结果。

算法复杂度分析 :外层循环用时n,内层用时1、2、…、n, 故总用时1+2+3+…+n=(1+n)*n/2=O(n^2)。

代码实现

#include<stdio.h>
#include<stdlib.h>
int a[100][100];
int b[100][100];    
int n;
void solve(){
     FILE *fp;
     int i,j;
     for(j=1;j<=n;j++)
         b[n][j]=a[n][j];
     for(i=n-1;i>=1;i--)
         for(j=1;j<=i;j++){
             if(b[i+1][j+1]>b[i+1][j])
                 b[i][j]=b[i+1][j+1]+a[i][j];
             else                
                 b[i][j]=b[i+1][j]+a[i][j];
         }
    printf("%d\n",b[1][1]);
    fp=fopen("output.txt","w");
    fprintf(fp,"%d",b[1][1]);
    fclose(fp);
}
int main(void){
    FILE *fp;
    int i,j; 
    fp=fopen("input.txt","r");
    fscanf(fp,"%d",&n);
    printf("行:%d",n);
    printf("\n");
    for(i=1;i<=n;i++){
        for(j=1;j<=i;j++)
        {
            fscanf(fp,"%d",&a[i][j]);
        }
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=i;j++)
        {
            printf("%-3d",a[i][j]);
        }
        printf("\n");
    } 
    fclose(fp);
    fflush(stdin);
    printf("\n");
    solve();
    return(0);
}

文件input.txt内容(程序运行前):            output.txt文件内容(程序运行后):

 

运行结果:

2. 游艇租用问题:长江游艇俱乐部在长江上设置了n个游艇出租站1,2,3…,n。有课可以在这些游艇出租站用游艇,并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1<=i<j=n。试设计一个算法,计算从游艇出租站i到出租站就j所需的最少租金,并分析算法的计算复杂性。

分 析: 对于题目课理解为,对于给定的游艇出租站i对游艇出租站j之间的租金为r(i,j),1≤i<j≤n,计算从游艇出租站1到游艇出租站n所需的最少租金。 

将每个出租站看作一个点,站与站之间的关系可以用有向无环图表示,同时站与站之间的租金为边的权。

此问题可转化成求站1到站n的最短路径问题。

用动态规划求解,递推方程如下所示:定义f[i][j]为站点i到站点j的最少租金。

 f[i][j] = min { f[i][k] + f[k][j] }   i<k<j, 0<=i,j<=n-1

最少租金为:f[0][n-1]

程序实现:

#include<stdio.h>
#include<stdlib.h>
int main(void){
    int num,**array,i,j,k,l;
    FILE *fp;
    fp=fopen("input.txt","r");
    fscanf(fp,"%d",&num);
    printf("一共有站:%d \n",num);
    array=(int**)malloc((num+1)*sizeof(int*));
    for(i=1;i<=num;i++)
        array[i]=(int*)malloc((num+1)*sizeof(int*));
    for(i=1;i<=num;i++)
        array[i][i]=0;
    for(i=1;i<num;i++)
        for(j=i+1;j<=num;j++)
            fscanf(fp,"%d",&array[i][j]);
   for(i=1;i<num;i++){
        for(j=i+1;j<=num;j++)
            printf("%-3d",array[i][j]);
        printf("\n");
   }
        for(i=2;i<=num;i++)
            for(j=i+1;j<=num;j++){
               k=j-i;
               for(l=k;l<j;l++)
                  if(array[k][l]+array[l][j]<array[k][j])
                      array[k][j]=array[k][l]+array[l][j];
            }
    printf("最少租金为:%d",array[1][num]);
    fp=fopen("output.txt","w");
    fprintf(fp,"%d",array[1][num]);
    fclose(fp);
    return 0;
}

文件input.txt内容(程序运行前):            output.txt文件内容(程序运行后):

       

运行结果:

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 8
码字总数 8751
×
Cynthia_x
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: