'एक' और 'दूसरा' नाम के दो पूर्णांक दिए गए हैं। लक्ष्य संभव सरणियों की संख्या का पता लगाना है जैसे कि -
-
सरणी में तत्व 1 और 'दूसरे' के बीच की सीमा में हैं।
-
सरणी के सभी तत्व ऐसे हैं कि arr[i] arr को विभाजित करता है[i+1] या arr[i+1] arr को विभाजित करता है[i+2]....और इसी तरह।
-
सरणी की लंबाई 'एक' है।
उदाहरण के लिए
इनपुट
one = 3, another = 2
आउटपुट
Count of arrays in which all adjacent elements are such that one of them divide the another are: 8
स्पष्टीकरण
The arrays will be: [ 1,1,1 ], [ 1,1,2 ], [ 1,2,1 ], [ 1,2,2 ], [ 2,1,1 ], [ 2,1,2 ], [ 2,2,1 ], [ 2,2,2 ]
इनपुट
one = 2, another = 3
आउटपुट
Count of arrays in which all adjacent elements are such that one of them divide the another are: 7
स्पष्टीकरण
The arrays will be: [ 1,1 ], [ 2,2 ], [ 3,3 ], [ 1,2 ], [ 1,3 ], [ 2,2 ], [ 3,3 ]
नीचे दिए गए कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है -
हम जानते हैं कि प्रत्येक सरणी का पहला तत्व श्रेणी [1, अन्य] में कोई भी संख्या हो सकती है। अगला तत्व हमेशा पिछले या पिछले के गुणक का गुणक होगा ताकि विभाज्यता की स्थिति बनी रहे। साथ ही गुणनखंड या गुणन 'दूसरे' से कम होना चाहिए। हम कंप्यूटेशंस को स्टोर करने के लिए डायनेमिक प्रोग्रामिंग का उपयोग करेंगे। इसके लिए हम array arr[][].arr[1][another] 1 का उपयोग करते हैं क्योंकि वे सिंगल एलिमेंट एरे होंगे। arr[i][j]=arr[i−1][j]+पिछले तत्व के गुणनखंड+पिछले तत्व के गुणज (दूसरे से कम)।
-
इनपुट के रूप में एक और दूसरे पूर्णांक लें।
-
फंक्शन आसन्न_तत्व (इंट फर्स्ट, इंट सेकेंड) सरणियों की गिनती देता है जिसमें सभी आसन्न तत्व ऐसे होते हैं कि उनमें से एक दूसरे को विभाजित करता है।
-
प्रारंभिक गणना को 0 के रूप में लें और सरणी गिरफ्तारी [आकार] [आकार]।
-
मेमसेट का उपयोग करके सभी गणनाओं को 0 के रूप में प्रारंभ करें।
-
दो सदिश लें - vec कारकों के भंडारण के लिए और vec_2 गुणकों को संग्रहीत करने के लिए।
-
i=t से i=सेकेंड और j=2*i से j=second तक दो फॉर लूप्स का उपयोग करके ट्रैवर्स करें। वेतन वृद्धि j by i.
-
i को vec[j] और j से vec_2[i] में जोड़ें। j लूप के बाद i को vec[i] में भी जोड़ें।
-
लूप के लिए उपयोग करके गिरफ्तारी [1] [i] सेट करें।
-
सरणी को बार-बार ट्रैवर्स करें और अब vec और vec_2 को ट्रैवर्स करें और arr[i][j] में फ़ैक्टर और मल्टीपल जोड़ें।
-
अंत में vec[i] और vec_2[i] को गिनने और साफ़ करने के लिए सभी arr[first][i] जोड़ें।
-
परिणाम के रूप में वापसी की गिनती।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
#define size 1000
int adjacent_elements(int first, int second){
int count = 0;
int arr[size][size];
memset(arr, 0, sizeof arr);
vector<int> vec[size], vec_2[size];
memset(vec, 0, sizeof vec);
memset(vec_2, 0, sizeof vec_2);
for (int i = 1; i <= second; i++){
for (int j = 2*i; j <= second; j += i){
vec[j].push_back(i);
vec_2[i].push_back(j);
}
vec[i].push_back(i);
}
for (int i = 1; i <= second; i++){
arr[1][i] = 1;
}
for (int i = 2; i <= first; i++){
for (int j = 1; j <= second; j++){
arr[i][j] = 0;
for (auto it: vec[j]){
arr[i][j] += arr[i−1][it];
}
for (auto it : vec_2[j]){
arr[i][j] += arr[i−1][it];
}
}
}
for (int i = 1; i <= second; i++){
count = count + arr[first][i];
vec[i].clear();
vec_2[i].clear();
}
return count;
}
int main(){
int one = 2, another = 2;
cout<<"Count of arrays in which all adjacent elements are such that one of them divide the another are: "<<adjacent_elements(one, another);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of arrays in which all adjacent elements are such that one of them divide the another are: 4