数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中数组中算术级数子序列的计数
给定一个包含整数元素的数组arr[]。目标是计算arr[]中算术级数子序列的数量。arr[]中元素的范围是[1,1000000]。
空序列或单个元素也将被计数。
让我们通过例子来理解。
例如
输入 - arr[] = {1,2,3}
输出 - 数组中算术级数子序列的数量为：8
解释 - 以下子序列将构成算术级数：
{}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}
输入 - arr[] = {2,4,5,8}
输出 - 数组中算术级数子序列的数量为：12
解释 - 以下子序列将构成算术级数：
{}, {2}, {4}, {5}, {8}, {2,4}, {2,5}, {2,8}, {4,5}, {4,8}, {5,8}, {2,5,8}
下面程序中使用的方法如下
- 空序列也是算术级数。
- 单个值也是算术级数。
- 找到数组中的最小值和最大值，分别为max_val和min_val。所有算术级数子序列的公差将在[min_val - max_val, max_val - min_val]之间。
- 现在，对于每个公差，我们将使用动态规划查找子序列，并将结果存储在arr_2[size]中。
- 长度为2或大于2的子序列将是arr_2[i]-1的总和，其中i是[0,2]，差值为D。
- arr_2[i] = 1 + sum(arr[j])，其中i<j且arr_2[j] + D = arr_2[i]
- 为了更快地计算，将sum(arr_2[j]，其中arr[j]+D = arr[i]且j<i)添加到arr_3[max_size]中。
- 将整数数组arr[]作为输入。
- 函数AP_subsequence(int arr[], int size)接收一个输入数组，并返回数组中算术级数子序列的数量。
- 将初始计数设置为0。
- 使用变量max_val、min_val、arr_2[size]存储子序列计数，以及arr_3[max_size]存储总和。
- 使用for循环遍历arr[]，找到最大和最小元素，并将其存储在max_val和min_val中。
- 对于单个元素算术级数和空算术级数，将count = size + 1。
- 计算最大差值diff_max = max_val - min_val和diff_min = min_val - max_val作为可能的公差。
- 使用for循环从j=0遍历到j<size。
- 设置arr_2[j] = 1;
- 对于arr[j] - i >= 1且arr[j] - i <= 1000000，设置arr_2[j] += arr_3[arr[j] - i]。
- 将arr_2[j]-1添加到count中。
- 将sum更新为arr_3[arr[j]] = arr_3[arr[j]] + arr_2[j]。
- 最后返回count作为结果。
示例
#include<bits/stdc++.h>
using namespace std;
#define max_size 10000
int AP_subsequence(int arr[], int size) {
int count = 0;
int max_val = INT_MAX;
int min_val = INT_MIN;
int arr_2[size];
int arr_3[max_size];
for (int i = 0; i < size; i++) {
max_val = min(max_val, arr[i]);
min_val = max(min_val, arr[i]);
}
count = size + 1;
int diff_max = max_val - min_val;
int diff_min = min_val - max_val;
for (int i = diff_max; i <= diff_min; i++) {
memset(arr_3, 0, sizeof arr_3);
for (int j = 0; j < size; j++) {
arr_2[j] = 1;
if (arr[j] - i >= 1) {
if (arr[j] - i <= 1000000) {
arr_2[j] += arr_3[arr[j] - i];
}
}
count += arr_2[j] - 1;
arr_3[arr[j]] = arr_3[arr[j]] + arr_2[j];
}
}
return count;
}
int main() {
int arr[] = {1,1,6,7,8};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Count of AP (Arithmetic Progression) Subsequences in an array are: " << AP_subsequence(arr, size);
return 0;
}如果我们运行以上代码，它将生成以下输出：
输出
Count of AP (Arithmetic Progression) Subsequences in an array are: 17
更新于：2021年1月29日
478 次浏览
广告