乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。

问题分析

题设要求按照给定方式截取数组得到所有可能片段，然后求各个片段和的总和。截取片段的方式是, 截取任意连续的几个数即可, 也就是取连续子数组。

截取片段并求和的方法

最直接的方案是按照题设要求, 设置片段长度从1到N, 然后以每个元素位开头, 截取制定长度的片段. 大致形式如下:

total_sum = 0
for slice_length in range(1, length(input)):
    for index in range(0, length(input) - slice_length):
        slice = input[index: index+slice_length]
        total_sum += sum(slice)

这里用到了两层循环, 然后截取数组片段也是一个隐形的循环。可能会导致程序超时。先不论是否超时, 我们尝试优化程序性能, 寻找操作更少的计算方案。

寻找每一个元素被累加次数的规律

以题目样例的"0.1 0.2 0.3 0.4"为例, 得到的片段为: (0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) (0.4) 看到这个梯状结构，我们可以认为存在规律的可能性很大。以下列出几个找出规律的途径:

观察法

将各个元素以不同颜色高亮, 如下在这里插入图片描述

我们可以看到各个数的累计次数（即,每组的个数*组数）为: 0.1: 4 * 1 = (4-0) * (0 + 1) 0.2: 3 * 2 = (4-1) * (1 + 1) 0.3: 2 * 3 = (4-2) * (2 + 1) 0.4: 1 * 4 = (4-3) * (3 + 1) 所以每一个元素的次数可以总结为: (length - index) * (index + 1)

化简二重循环

我们最开始根据直觉写出的二重循环就是在累加各个数组元素。如果我们观察每个元素被累加的次数, 可以发现, index在区间[0, length - slice_length)的元素会被累加 slice_length从1到N, 所以index为0的会有1次被累加N遍, 为1的会有2次被累加N-1遍, ...... 我们同样可以得到元素累加次数为: (length - index) * (index + 1)

数学法

题目要求截取的片段是连续的。所以选定片段开头元素后, 可能生成片段可能情况等于该开头元素之后的元素个数+1; 由于选定开头元素后生成的片段都一定会有这个开头元素, 一定没有开头元素前面的元素. 所以元素累加次数=前面元素的累加次数 - 索引值 + 后面的元素个数 + 1

前面元素的累加次数需要减去索引值为了排除前面元素独自作为片段的情况
最后的"加1"是为了加上当前元素独自作为片段的情况所以以"0.1 0.2 0.3 0.4"为例, 累加次数为: 0.1: 4 - 0 = 4 0.2: 4 - 1 + 2 + 1 = 6 0.3: 6 - 2 + 1 + 1 = 6 0.4: 6 - 3 + 0 + 1 = 4

完整描述步骤

获取输入数组
初始化总和计数器sum
对每一个索引为index的元素number, 进行操作: sum += number * (length - index) * (index + 1)
输出sum

伪代码描述

get input: numbers, number_amount
init sum = 0;
for index of numbers: sum += (number_amount - index) * numbers[index] * (index + 1);
print sum

完整提交代码

/*
# 问题分析
题设要求按照给定方式截取数组得到所有可能片段，然后求各个片段和的总和。
截取片段的方式是, 截取任意连续的几个数即可, 也就是取连续子数组。
 
# 截取片段并求和的方法
最直接的方案是按照题设要求, 设置片段长度从1到N, 然后以每个元素位开头, 截取制定长度的片段.
大致形式如下:
 
total_sum = 0
for slice_length in range(1, length(input)):
    for index in range(0, length(input) - slice_length):
        slice = input[index: index+slice_length]
        total_sum += sum(slice)
 
这里用到了两层循环, 然后截取数组片段也是一个隐形的循环。可能会导致程序超时。
先不论是否超时, 我们尝试优化程序性能, 寻找操作更少的计算方案。
 
## 寻找每一个元素被累加次数的规律
以题目样例的"0.1 0.2 0.3 0.4"为例, 得到的片段为:
(0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2)
(0.2, 0.3) (0.2, 0.3, 0.4) 
(0.3) (0.3, 0.4) 
(0.4) 
看到这个梯状结构，我们可以认为存在规律的可能性很大。以下列出几个找出规律的途径:
### 观察法
将各个元素以不同颜色高亮, 如下
[  
    (<span style="background-color: rgba(255, 0, 0, 0.4); "><font background-color="blue">0.1</font></span>),  
    (<span style="background-color: rgba(255, 0, 0, 0.4);">0.1</span>, <span style="background-color: rgba(0, 255, 0, 0.4);">0.2</span>),  
    (<span style="background-color: rgba(255, 0, 0, 0.4);">0.1</span>, <span style="background-color: rgba(0, 255, 0, 0.4);">0.2</span>, <span style="background-color: rgba(0, 0, 255, 0.4);">0.3</span>),  
    (<span style="background-color: rgba(255, 0, 0, 0.4);">0.1</span>, <span style="background-color: rgba(0, 255, 0, 0.4);">0.2</span>, <span style="background-color: rgba(0, 0, 255, 0.4);">0.3</span>, <span style="background-color: rgba(0, 255, 255, 0.4);">0.4</span>),  
    (<span style="background-color: rgba(0, 255, 0, 0.4);">0.2</span>),  
    (<span style="background-color: rgba(0, 255, 0, 0.4);">0.2</span>, <span style="background-color: rgba(0, 0, 255, 0.4);">0.3</span>),  
    (<span style="background-color: rgba(0, 255, 0, 0.4);">0.2</span>, <span style="background-color: rgba(0, 0, 255, 0.4);">0.3</span>, <span style="background-color: rgba(0, 255, 255, 0.4);">0.4</span>),  
    (<span style="background-color: rgba(0, 0, 255, 0.4);">0.3</span>),  
    (<span style="background-color: rgba(0, 0, 255, 0.4);">0.3</span>, <span style="background-color: rgba(0, 255, 255, 0.4);">0.4</span>),  
    (<span style="background-color: rgba(0, 255, 255, 0.4);">0.4</span>),  
]
我们可以看到各个数的累计次数（即,每组的个数*组数）为:
0.1: 4 * 1 = (4-0) * (0 + 1)
0.2: 3 * 2 = (4-1) * (1 + 1)
0.3: 2 * 3 = (4-2) * (2 + 1)
0.4: 1 * 4 = (4-3) * (3 + 1)
所以每一个元素的次数可以总结为: (length - index) * (index + 1)
 
### 化简二重循环
我们最开始根据直觉写出的二重循环就是在累加各个数组元素。
如果我们观察每个元素被累加的次数, 可以发现, index在区间[0, length - slice_length)的元素会被累加
slice_length从1到N, 
所以index为0的会有1次被累加N遍,
为1的会有2次被累加N-1遍,
......
我们同样可以得到元素累加次数为: (length - index) * (index + 1)
 
### 数学法
题目要求截取的片段是连续的。
所以选定片段开头元素后, 可能生成片段可能情况等于该开头元素之后的元素个数+1;
由于选定开头元素后生成的片段都一定会有这个开头元素, 一定没有开头元素前面的元素.
**所以元素累加次数=前面元素的累加次数 - 索引值 + 后面的元素个数 + 1**
- 前面元素的累加次数 需要减去索引值为了排除前面元素独自作为片段的情况
- 最后的"加1"是为了加上当前元素独自作为片段的情况
所以以"0.1 0.2 0.3 0.4"为例, 累加次数为:
0.1: 4 - 0 = 4
0.2: 4 - 1 + 2 + 1 = 6
0.3: 6 - 2 + 1 + 1 = 6
0.4: 6 - 3 + 0 + 1 = 4
 
# 完整描述步骤
1. 获取输入数组
2. 初始化总和计数器sum
3. 对每一个索引为index的元素number, 进行操作:
    sum += number * (length - index) * (index + 1)
4. 输出sum
 
# 伪代码描述
1. get input: numbers, number_amount
2. init sum = 0;
3. for index of numbers:
    sum += (number_amount - index) * numbers[index] * (index + 1);
4. print sum
 
*/
 
 
#include<stdio.h>
#define MULTIPLE 1000
 
int main() {
  int number_amount;
  scanf("%d", &number_amount);
 
  long long numbers[number_amount];
  double num;
  for (int i = 0; i < number_amount; i++) {
    scanf("%lf", &num);
    numbers[i] = num * 1000;
  }
 
  long long sum = 0;
  for (int i = 0; i < number_amount; i++) {
    sum += (number_amount - i) * numbers[i] * (i + 1);
  }
 
  printf("%.2f\n", sum / (double)MULTIPLE);
  return 0;
}

「PAT乙级真题解析」Basic Level 1049 数列的片段和 (问题分析+完整步骤+伪代码描述+提交通过代码)

Table of Contents