資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告