Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सरणी में AP (अंकगणितीय श्रेणी) सबसीक्वेंस की गिनती


एक सरणी arr[] दी गई है जिसमें पूर्णांक तत्व हैं। लक्ष्य arr[] के अंदर अंकगणितीय श्रेणी (AP) सबसीक्वेंस की संख्या गिनना है। arr[] के अंदर तत्वों की सीमा [1,1000000] है।

खाली अनुक्रम या एकल तत्व को भी गिना जाएगा।

उदाहरणों से समझते हैं

उदाहरण के लिए

इनपुट - arr[] = {1,2,3}

आउटपुट - सरणी में AP (अंकगणितीय श्रेणी) सबसीक्वेंस की संख्या: 8

व्याख्या - निम्नलिखित सबसीक्वेंस AP बनाएंगे:-

{}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}

इनपुट - arr[] = {2,4,5,8}

आउटपुट - सरणी में AP (अंकगणितीय श्रेणी) सबसीक्वेंस की संख्या: 12

व्याख्या - निम्नलिखित सबसीक्वेंस AP बनाएंगे:-

{}, {2}, {4}, {5}, {8}, {2,4}, {2,5}, {2,8}, {4,5}, {4,8}, {5,8}, {2,5,8}

नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण

  • एक खाली अनुक्रम भी एक AP है।
  • एक एकल मान भी एक AP है।
  • सरणी के भीतर न्यूनतम और अधिकतम मान खोजें जैसे max_val और min_val। सभी AP सबसीक्वेंस में सामान्य अंतर [ 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]
  • तेज़ दृष्टिकोण के लिए योग ( arr_2[j] जहां arr[j]+D = arr[i] और j<i ) को arr_3[max_size] में जोड़ें
  • इनपुट के रूप में पूर्णांक सरणी arr[] लें।
  • फ़ंक्शन AP_subsequence(int arr[], int size) एक इनपुट सरणी लेता है और सरणी में AP (अंकगणितीय श्रेणी) सबसीक्वेंस की संख्या लौटाता है।
  • प्रारंभिक गिनती 0 लें।
  • सबसीक्वेंस गिनती संग्रहीत करने के लिए वेरिएबल max_val, min_val, arr_2[size] और योग संग्रहीत करने के लिए arr_3[max_size] लें।
  • for लूप का उपयोग करके arr[] को पार करें और अधिकतम और न्यूनतम तत्व खोजें और max_val और min_val में स्टोर करें।
  • count = size +1 लें एकल तत्व APs और खाली AP के लिए।
  • अधिकतम अंतर 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] सेट करें।
  • count में arr_2[j]-1 जोड़ें।
  • योग को अपडेट करें 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

  1. - C++ में सॉर्टेड एरे में निरपेक्ष विशिष्ट गिनती

    एक एरे समान डेटा प्रकार के तत्वों का एक संग्रह है। एक सॉर्टेड एरे एक एरे है जिसमें तत्व आरोही या अवरोही क्रम के अनुक्रम में संग्रहीत होते हैं। विशिष्ट गिनती उन तत्वों की संख्या है जो समान नहीं हैं। निरपेक्ष विशिष्ट गिनती तत्वों के निरपेक्ष मान की विशिष्ट गिनती है यानी चिह्न के बिना मान (अनसाइन्ड मा

  1. - C++ प्रोग्राम: सरणी में इनवर्जन गिनें

    परिचयइनवर्जन काउंट का अर्थ है सरणी को सॉर्ट करने के लिए आवश्यक स्वैप की संख्या। यदि सरणी सॉर्टेड है तो इनवर्जन काउंट = 0। यदि सरणी रिवर्स ऑर्डर में सॉर्टेड है तो इनवर्जन काउंट = अधिकतम।एल्गोरिदम a[j] तो काउंट 1 बढ़ाएं। अंत में काउंट लौटाएं।उदाहरण कोड#include <iostream> using namespace std; in

  1. - C++ में पॉइंटर अंकगणित का उपयोग करके ऐरे का योग

    यह पॉइंटर का उपयोग करके ऐरे तत्वों का योग ज्ञात करने के लिए एक C++ प्रोग्राम है। एल्गोरिदम Begin उपयोगकर्ता इनपुट से मानों के साथ ऐरे तत्वों को इनिशियलाइज़ करें। s = 0 इनिशियलाइज़ करें i = 0 से लूप s = s + *(ptr + i) चर s में योग मान प्रिंट करें। End उदाहरण कोड #include &l