第九周习题

ゝ一世哀愁。 2022-10-21 03:59 224阅读 0赞

记录

  • A、最大字段和升级版
    • 代码
  • B、斜线最大最小值
    • 代码
  • C、矩阵连乘问题-备忘录法求最优值
    • 代码
  • D、矩阵连乘问题-动态规划求最优值
    • 代码
  • E、矩阵连乘问题-构造最优解
    • 代码
  • F、石子合并问题
    • 代码

A、最大字段和升级版

题目描述

  • 使用动态规划算法求整数数组（可能包含负整数）的最大子段和，以及和最大子段的起始位置和结束位置：
    例如：输入数组(6,-1,5,4,-7)，输出14, 1,4，其中14表示最大子段和，1表示和最大的子段从第1个数字开始，4表示和最大的子段到第4个数字结束，即(6, -1 , 5, 4)。

输入

  • 每组输入两行，第1行为数组中包含的整数个数n，第2行为n个整数（可能包含负整数），两两之间用空格隔开。

输出

  • 输出最大子段和，以及和最大子段的起始位置和结束位置，两两之间用空格隔开。

样例输入 Copy

  1. 5
  2. 6 -1 5 4 -7

样例输出 Copy

  1. 14 1 4

【这个题目，直接贯穿了我的整个五一假期，还多加了几天的时间，其实大部分代码我都写好了，只有一个地方有问题，就是输入1，它只会输出1 0 0，不是输出1 1 1 ，然而就是这个问题困扰了我好久好久，然后就是，因为五一也出去完了，更加没思路了，好不容易问了室友才恍然大悟，就是我设置的起始位置和终止位置的初始化一直都是设置的0，改成1就行了，所以我那么久CSDN也没找到答案，哭了~我室友是直接在循环的过程记录起始位置的，所以直接调用输出就行，但是我懒得改了，放一个链接吧，对后面的题目有很大帮助哈：和我一样的题目~戳她戳她！】

代码

  1. import java.util.Scanner;
  3. public class Main { 
  5.     public static int []a = new int[105];
  6.     public static int []b = new int[105];
  7.     public static int n,maxSum,index,maxIndex,max_S;
  9.     public static void solve(){ 
  10.         b[0] = a[0];
  11.         maxSum = b[0];
  12.         index = 1;
  13.         maxIndex = 1;
  15.         for(int j=1;j<n;j++){ 
  17.             if(b[j-1]>0)
  18.                 b[j] = b[j-1]+a[j];
  19.             else{ 
  20.                 b[j] = a[j];
  22.             }
  24.             if(b[j]>maxSum){ 
  25.                 maxSum = b[j];
  26.                 maxIndex = j+1;
  27.             }
  29.            max_S = maxSum;
  30.             for(int i = maxIndex-1;i>=0;i--){ 
  31.                 max_S-=a[i];
  32.                 if(max_S==0)
  33.                     index = i+1;
  34.             }
  35.     }
  36. }
  38.     public static void main(String[] args) { 
  39.         // TODO Auto-generated method stub
  40.        Scanner sc = new Scanner(System.in);
  41.        while(sc.hasNext()){ 
  42.            n = sc.nextInt();
  43.                for(int i=0;i<n;i++)
  44.                    a[i] = sc.nextInt();
  45.                solve();
  46.                System.out.println(maxSum+" "+index+" "+maxIndex);
  47.            }
  50.        }
  51.    }

B、斜线最大最小值

题目描述

  • 求如图所示一个上三角矩阵中每一条斜线中的最大元素(L)和最小元素(S)。
    在这里插入图片描述
    输入
  • 每组输入包括两部分，一部分为数字n，表示三角矩阵的行数。
  • 第二部分即为三角矩阵。

输出

  • 每一个对角线输出一行，每行包括Lx=Max,
    Sx=Min，其中x为斜线序号（序号从1开始），Max为该斜线上的最大值，Min为该斜线上的最小值。

样例输入 Copy

  1. 6
  2. 1 3 5 7 11 20
  3. 0 6 8 2 3 13
  4. 0 0 7 4 8 9
  5. 0 0 0 18 3 10
  6. 0 0 0 0 12 6
  7. 0 0 0 0 0 15

样例输出 Copy

  1. L1=18, S1=1
  2. L2=8, S2=3
  3. L3=10, S3=2
  4. L4=9, S4=3
  5. L5=13, S5=11
  6. L6=20, S6=20
  8. 【有问题的话就戳上面的那个链接吧~我就是根据那个来的】

代码

  1. import java.util.Scanner;
  3. public class Main { 
  4.     public static int a[][] = new int[105][105];
  5.     public static int max,min;
  7.     public static void main(String[] args) { 
  8.         // TODO Auto-generated method stub
  9.         Scanner sc = new Scanner(System.in);
  10.         while(sc.hasNext()){ 
  11.             int n = sc.nextInt();
  13.             max = 0;min = 0;
  14.             for(int i=1;i<=n;i++)
  15.                 for(int j=1;j<=n;j++)
  16.                     a[i][j] = sc.nextInt();
  19.             for(int r=1;r<=n;r++){ 
  20.                 max = a[1][r];
  21.                 min = a[1][r];
  23.                 for(int i=1;i<=n-r+1;i++){ 
  24.                     int j=r+i-1;
  26.                     if(max<a[i][j])//最大值
  27.                         max = a[i][j];
  29.                     else if(min>a[i][j])//最小值
  30.                         min = a[i][j];
  31.                 }
  33.                 System.out.println("L"+r+"="+max+", "+"S"+r+"="+min);
  35.             }
  37.         }
  39.     }
  41. }

C、矩阵连乘问题-备忘录法求最优值

题目描述

  • 使用备忘录法求解矩阵连乘问题，输出最少乘法次数。

输入

  • 每组数据包括两行，第一行为数组长度n，第二行为存储矩阵维数的一维数组。

输出

  • 矩阵连乘最优计算次数。

样例输入 Copy

  1. 7
  2. 30 35 15 5 10 20 25

样例输出 Copy

  1. 15125

代码

  1. import java.util.Scanner;
  3. public class Main { 
  4.     public static int m[][] = new int[105][105];
  5.     public static int s[][] = new int[105][105];
  6.     public static int p[] = new int[105];
  7.     public static int n;
  9.     public static int lookup(int i,int j){ 
  11.         for(int k=0;k<n;k++)
  12.             for(int t=0;t<n;t++)
  13.                 m[k][t] = 0;
  16.         if(m[i][j]>0)
  17.             return m[i][j];
  19.         if(i==j)
  20.             return 0;
  21.         int u = lookup(i+1,j)+p[i-1]*p[i]*p[j];
  22.         s[i][j] = i;
  23.         for(int k = i+1;k<j;k++){ 
  24.             int t = lookup(i,k)+lookup(k+1,j)+p[i-1]*p[k]*p[j];
  25.             if(t<u){ 
  26.                 u = t;
  27.                 s[i][j] = k;
  28.             }
  30.         }
  31.         m[i][j] = u;
  32.         return u;
  33.     }
  35.     public static void main(String[] args) { 
  36.         // TODO Auto-generated method stub
  37.         Scanner sc = new Scanner(System.in);
  38.         while(sc.hasNext()){ 
  39.             n = sc.nextInt();
  40.             for(int i=0;i<n;i++)
  41.                 p[i] = sc.nextInt();
  42.             System.out.println(lookup(1,n-1));
  43.         }
  45.     }
  47. }

D、矩阵连乘问题-动态规划求最优值

题目描述

  • 使用动态规划算法求解矩阵连乘问题，输出最少乘法次数。

输入

  • 每组数据包括两行，第一行为数组长度n，第二行为存储矩阵维数的一维数组。

输出

  • 矩阵连乘最优计算次数。

样例输入 Copy

  1. 7
  2. 30 35 15 5 10 20 25

样例输出 Copy

  1. 15125

代码

  1. import java.util.Scanner;
  3. public class Main { 
  5.     public static int m[][] = new int[105][105];
  6.     public static int s[][] = new int[105][105];
  7.     public static int p[] = new int[105];
  8.     public static int n;
  10.     public static void matrixChain(int []p,int [][]m,int [][]s){ 
  12.         for(int i=1;i<=n;i++)
  13.             m[i][i] = 0;
  15.         for(int r=2;r<=n;r++)
  16.             for(int i=1;i<=n-r+1;i++){ 
  18.                 int j = i+r-1;
  19.                 m[i][j] = m[i+1][j]+p[i-1]*p[i]*p[j];
  20.                 s[i][j] = i;
  22.                 for(int k = i+1;k<j;k++){ 
  24.                     int t = m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
  25.                     if(t<m[i][j]){ 
  26.                         m[i][j] = t;
  27.                         s[i][j] = k;
  28.                     }
  29.                 }
  30.             }
  31.     }
  32.     public static void main(String[] args) { 
  33.         // TODO Auto-generated method stub
  34.         Scanner sc = new Scanner(System.in);
  35.         while(sc.hasNext()){ 
  36.             n = sc.nextInt();
  37.             for(int i=0;i<n;i++)
  38.                 p[i] = sc.nextInt();
  39.             matrixChain(p,m,s);
  40.             System.out.println(m[1][n-1]);
  41.         }
  43.     }
  45. }

E、矩阵连乘问题-构造最优解

题目描述

  • 使用动态规划算法求解矩阵连乘问题。

输入

  • 每组数据包括两行，第一行为数组长度n，第二行为存储矩阵维数的一维数组。

输出

  • 矩阵连乘最优计算次序。

样例输入 Copy

  1. 7
  2. 30 35 15 5 10 20 25

样例输出 Copy

  1. A[2:2] * A[3:3]
  2. A[1:1] * A[2:3]
  3. A[4:4] * A[5:5]
  4. A[4:5] * A[6:6]
  5. A[1:3] * A[4:6]

代码

  1. import java.util.Scanner;
  3. public class Main { 
  5.     public static int m[][] = new int[105][105];
  6.     public static int s[][] = new int[105][105];
  7.     public static int p[] = new int[105];
  8.     public static int n;
  10.     public static void matrixChain(int []p,int [][]m,int [][]s){ 
  12.         for(int i=1;i<=n;i++)
  13.             m[i][i] = 0;
  15.         for(int r=2;r<=n;r++)
  16.             for(int i=1;i<=n-r+1;i++){ 
  18.                 int j = i+r-1;
  19.                 m[i][j] = m[i+1][j]+p[i-1]*p[i]*p[j];
  20.                 s[i][j] = i;
  22.                 for(int k = i+1;k<j;k++){ 
  24.                     int t = m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
  25.                     if(t<m[i][j]){ 
  26.                         m[i][j] = t;
  27.                         s[i][j] = k;
  28.                     }
  29.                 }
  30.             }
  31.     }
  33.     public static void traceback(int [][]s,int i,int j){ 
  34.         if(i==j)
  35.             return;
  36.         traceback(s,i,s[i][j]);
  37.         int t = s[i][j]+1;
  38.         traceback(s,t,j);
  39.         System.out.println("A["+i+":"+s[i][j]+"] * "+"A["+t+":"+j+"]");
  40.     }
  41.     public static void main(String[] args) { 
  42.         // TODO Auto-generated method stub
  43.         Scanner sc = new Scanner(System.in);
  44.         while(sc.hasNext()){ 
  45.             n = sc.nextInt();
  46.             for(int i=0;i<n;i++)
  47.                 p[i] = sc.nextInt();
  48.             matrixChain(p,m,s);
  49.             traceback(s,1,n-1);
  51.         }
  53.     }
  55. }

F、石子合并问题

题目描述

  • 在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。例如：输入{1，2，3，4，5}，输出33。【3+6+9+15=33】

输入

  • 本题应该处理到文件尾，每组输入包括两行，第一行为石子堆的个数n，第二行则为每堆石子的个数。

输出

  • 输出最小花费。

样例输入 Copy

  1. 5
  2. 1 2 3 4 5

样例输出 Copy

  1. 33

代码

  1. import java.util.Scanner;
  3. public class Main { 
  5.     public static int m[][] = new int[105][105];
  6.     public static int s[][] = new int[105][105];
  7.     public static int p[] = new int[105];
  8.     public static int n;
  10.     public static void matrixChain(int []p,int [][]m,int [][]s){ 
  12.         for(int i=1;i<=n;i++)
  13.             m[i][i] = 0;
  15.         for(int r=2;r<=n;r++)
  16.             for(int i=1;i<=n-r+1;i++){ 
  18.                 int j = i+r-1;
  19.                 m[i][j] = m[i+1][j]+s[i][j];
  21.                 for(int k = i+1;k<j;k++){ 
  23.                     int t = m[i][k]+m[k+1][j]+s[i][j];
  24.                     if(t<m[i][j]){ 
  25.                         m[i][j] = t;
  26.                     }
  27.                 }
  28.             }
  29.     }
  30.     public static void main(String[] args) { 
  31.         // TODO Auto-generated method stub
  32.         Scanner sc = new Scanner(System.in);
  33.         while(sc.hasNext()){ 
  34.             n = sc.nextInt();
  35.             for(int i=1;i<=n;i++)
  36.                 p[i] = sc.nextInt();
  38.             for(int i=1;i<=n;i++)
  39.                 s[i][i] = p[i];
  41.             for(int i=1;i<=n;i++)
  42.                 for(int j=i+1;j<=n;j++)
  43.                     s[i][j] = s[i][j-1]+p[j];
  44.             matrixChain(p,m,s);
  45.             System.out.println(m[1][n]);
  46.         }
  48.     }
  50. }

【鉴于小编五一的时候学骑自行车摔伤了，所以就不和你们唠嗑了，小编虽然五一摔伤了，但是还是和室友出去玩了，去拍了很多照片，吃了臭豆腐，吃了炸鸡，吃了凉皮，吃了好多好多东西，O(∩_∩)O哈哈~，开心！】

句子君：
“但是啊，这世界上不是所有的事情都能如你所愿，有样东西必定会成为你成功的绊脚石，知道是什么吗？就是人的感情！无聊的嫉妒、傲慢、偏见、迷恋都是绊脚石，压制住这些感情，权衡眼前的利益取舍，这就是胜负的关键，只有成功才能开创人生道路，不管别人怎样把你当傻瓜，怎样被社会无视，只要拿出成果就会让人重新认识你，只要通过这一场考试，就能使生活环境发生巨变，被一时感情冲昏而损失利益的只能称之为傻瓜。”

发表评论

表情：
评论列表 （有 0 条评论，224人围观）

还没有评论，来说两句吧...

相关阅读

    相关 第九周题目

    Java继承和多态之abstract类 > 任务描述 :完成抽象类的定义与使用 相关知识 > Java 语言提供了两种类，分别为具体类和抽象类。前面学习接触的类都是具

    我会带着你远行我会带着你远行/ 0 赞/ 544 阅读