文档章节

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

Cynthia_x
 Cynthia_x
发布于 2016/11/21 18:58
字数 1147
阅读 89
收藏 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
计算可以组成三角形的三元组的个数 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
《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

没有更多内容

加载失败,请刷新页面

加载更多

浅谈“李氏代换”——从纪念金庸和斯坦李说起

李氏代换(LSP)简介 李氏代换是软件设计的一个原则,又名依赖倒转原则或依赖倒置原则,其衍生原则有接口分离原则等。该原则由Barbara Liskov于1988年提出。 该原则指出,程序中高级别的元素...

SamYjy
19分钟前
9
0
JavaScript实现在线websocket WSS测试工具 -toolfk程序员工具网

本文要推荐的[ToolFk]是一款程序员经常使用的线上免费测试工具箱,ToolFk 特色是专注于程序员日常的开发工具,不用安装任何软件,只要把内容贴上按一个执行按钮,就能获取到想要的内容结果。T...

toolfk
38分钟前
0
0
linux-scp 远程拷贝报错原因

刚拿到一台重装后的服务器,远程ssh都正常,但是一scp拷贝东西就报错: 本地确定是有scp命令的,而且如果是本地没有scp不会报后面那句lost connection,因此就是远程没有scp这个命令。因此在...

linuxprobe16
51分钟前
1
0
OSChina 周六乱弹 —— 谁小时候没当过熊孩子呀

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @小小编辑:推荐歌曲《行尸走肉》- amazarashi 《行尸走肉》- amazarashi 手机党少年们想听歌,请使劲儿戳(这里) @神话 :周五了,周末干啥...

小小编辑
今天
110
4
docker部署springboot项目

安装docker 菜鸟教程 springboot项目 maven依赖 <?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001......

yimingkeji
今天
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部