文档章节

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

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

       

运行结果:

© 著作权归作者所有

共有 人打赏支持
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
BASIC-6 基础练习 杨辉三角形

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

xnh_565175944
05/04
0
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
像小猪佩奇那样生活,需要多少钱?

佩奇家位于伦敦市中心(或离市中心不远) 如伦敦的肯辛顿区和切尔西区, 两区房价£13,820平,约折合人民币¥124,380, 跟上海东方明珠周边房价相当。 width="auto" src="http://ss.csdn.net...

ufv59to8
01/08
0
0
c语言菜鸟求教!!!!一个关于三角形运行的问题

我是一名大二的学生,大一时没怎麽认证学习,大一第一学期的专业课c语言才刚过(64),所以现在重新自学c语言,我编了一个关于三角形的程序,源程序如下:#include main() { float a,b,c; pr...

Mike.hjxs
2011/10/09
646
3
蓝桥杯 算法训练 数字三角形

问题描述   (图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路   径,使该路径所经过的数字的总和最大。   ●每一步可沿左斜线向下或右斜线向下走;   ...

xnh_565175944
2017/12/21
0
0
求高手关注,关于梅花桩问题

ohnny Q在你的帮助下终于进入了城堡,现在出现在他面前的是一条恐怖的黑水河。河中有大量传说中的食人怪兽------法克鱿,同时还有一个N层正三角梅花桩阵,每个桩上都印有一个数字,如图所示是一个...

小辉211
2012/05/27
545
11
Armadillo 3.6.3 发布,C++ 线性代数库

Armadillo C++ Library 3.6.3 增加了一个更快的 find() 函数,同时修复了非相邻子阵的问题。 Armadillo C++ Library 是一种C++的线性代数库(矩阵数学)以取得良好的平衡速度与易用性。整数,...

oschina
2013/02/21
728
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

shell中的函数、shell中的数组、告警系统需求分析

shell中的函数 格式: 格式: function f_name() { command } 函数必须要放在最前面 示例1(用来打印参数) 示例2(用于定义加法) 示例3(用于显示IP) shell中的数组 shell中的数组1 定义数...

Zhouliang6
今天
2
0
用 Scikit-Learn 和 Pandas 学习线性回归

      对于想深入了解线性回归的童鞋,这里给出一个完整的例子,详细学完这个例子,对用scikit-learn来运行线性回归,评估模型不会有什么问题了。 1. 获取数据,定义问题     没有...

wangxuwei
今天
1
0
MAC安装MAVEN

一:下载maven压缩包(Zip或tar可选),解压压缩包 二:打开终端输入:vim ~/.bash_profile(如果找不到该文件新建一个:touch ./bash_profile) 三:输入i 四:输入maven环境变量配置 MAVEN_HO...

WALK_MAN
今天
0
0
33.iptables备份与恢复 firewalld的9个zone以及操作 service的操作

10.19 iptables规则备份和恢复 10.20 firewalld的9个zone 10.21 firewalld关于zone的操作 10.22 firewalld关于service的操作 10.19 iptables规则备份和恢复: ~1. 保存和备份iptables规则 ~2...

王鑫linux
今天
2
0
大数据教程(2.11):keeperalived+nginx高可用集群搭建教程

上一章节博主为大家介绍了目前大型互联网项目的系统架构体系,相信大家应该注意到其中很重要的一块知识nginx技术,在本节博主将为大家分享nginx的相关技术以及配置过程。 一、nginx相关概念 ...

em_aaron
今天
1
0
Apache Directory Studio连接Weblogic内置LDAP

OBIEE默认使用Weblogic内置LDAP管理用户及组。 要整理已存在的用户及组,此前办法是导出安全数据,文本编辑器打开认证文件,使用正则表达式获取用户及组的信息。 后来想到直接用Apache Dire...

wffger
今天
2
0
HFS

FS,它是一种上传文件的软件。 专为个人用户所设计的 HTTP 档案系统 - Http File Server,如果您觉得架设 FTP Server 太麻烦,那么这个软件可以提供您更方便的档案传输系统,下载后无须安装,...

garkey
今天
1
0
Java IO类库之BufferedInputStream

一、BufferedInputStream介绍 /** * A <code>BufferedInputStream</code> adds * functionality to another input stream-namely, * the ability to buffer the input and to * sup......

老韭菜
今天
0
0
STM 32 窗口看门狗

http://bbs.elecfans.com/jishu_805708_1_1.html https://blog.csdn.net/a1985831055/article/details/77404131...

whoisliang
昨天
1
0
Dubbo解析(六)-服务调用

当dubbo消费方和提供方都发布和引用完成后,第四步就是消费方调用提供方。 还是以dubbo的DemoService举例 -- 提供方<dubbo:application name="demo-provider"/><dubbo:registry address="z...

青离
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部