文档章节

数字三角问题与租用游艇问题

Cynthia_x
 Cynthia_x
发布于 2016/11/21 18:58
字数 1147
阅读 87
收藏 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文件内容(程序运行后):

       

运行结果:

© 著作权归作者所有

共有 人打赏支持
Cynthia_x
粉丝 0
博文 8
码字总数 8751
作品 0
西安
前端工程师
Python3 欧拉计划 问题11-15

问题6-10参见:http://www.jianshu.com/p/6a8236cf7751 问题11、数字方阵中的最大乘积 在下面20×20的数字方阵中,以第7行第9列的数字26开始,右下对角线方向的3个数字分别是63,78,14。 这四...

AiFan
2017/11/19
0
0
Java数据结构与算法(第六章递归)

递归是一种方法(函数)调用自己的编程技术。 三角数字 数字序列 1、3、6、10、15、21、。。。。 这个数列中的第n项是由第n-1项加n得到了。 这个序列中数字被称为三角数字,因为他们可以被形...

小风89
2015/10/25
207
0
《Java数据结构和算法》Six 递归

递归是一种自己调用自己的编程技术。 1、三角数字 1、3、6、10、15、21……第n项=n-1项的值+n package Structure; import java.io.IOException; import java.io.InputStreamReader; import ...

DouDouLee
2016/03/26
43
0
计算可以组成三角形的三元组的个数 Valid Triangle Number

问题: Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengt......

叶枫啦啦
01/12
0
0
BASIC-6 基础练习 杨辉三角形

杨辉三角形又称Pascal三角形,它的第i+1行是(a+b)i的展开式的系数。    它的一个重要性质是:三角形中的每个数字等于它两肩上的数字相加。    下面给出了杨辉三角形的前4行:    1   ...

xnh_565175944
05/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

tomcat 设置虚拟路径

Tomcat无法管理<Tomcat安装目录>/webapps目录以外的Web应用程序 在server.xml中配置虚拟目录 <Context path="/imgDetail" docBase="/pictureServer/img/resource"/> 配置前访问图片路径:h......

west_coast
9分钟前
0
0
数据结构

wu

盼望明天
23分钟前
0
0
Bash脚本输入参数的使用

Bash脚本输入参数的使用 Bash脚本传入的参数,在脚本中以位置的形式进行访问,即 $n 。例如,$1 为执行脚本的第一个参数,$2 为执行脚本的第二个参数。另外Bash中还提供了一些其它的便捷操作...

小陶小陶
40分钟前
2
0
多线程场景下,触发OOM的线程是否会影响其他线程的工作

public static void main(String[] args) { Thread t1 = new Thread(new Runnable() { @Override public void run() { int i = 0;......

麦馍
44分钟前
2
0
模拟Dubbo的zookeeper一致性Hash发现

接之前一篇<手写zookeeper来模拟dubbo的注册/发现>,使用一致性Hash来进行查找需要寻找的服务. Hash处理接口 public interface HashFunc { public Long hash(Object key);} 一致性Has...

算法之名
55分钟前
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部