Cho hai số nguyên có tên là 'một' và 'khác'. Mục tiêu là tìm số mảng có thể có sao cho -
-
Các phần tử trong mảng nằm trong khoảng từ 1 đến 'khác'.
-
Tất cả các phần tử của mảng sao cho arr [i] chia arr [i + 1] hoặc arr [i + 1] chia arr [i + 2] .... v.v.
-
Độ dài của mảng là 'một'.
Ví dụ
Đầu vào
one = 3, another = 2
Đầu ra
Count of arrays in which all adjacent elements are such that one of them divide the another are: 8
Giải thích
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 ]
Đầu vào
one = 2, another = 3
Đầu ra
Count of arrays in which all adjacent elements are such that one of them divide the another are: 7
Giải thích
The arrays will be: [ 1,1 ], [ 2,2 ], [ 3,3 ], [ 1,2 ], [ 1,3 ], [ 2,2 ], [ 3,3 ]
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -
Chúng ta biết rằng phần tử đầu tiên của mỗi mảng có thể là bất kỳ số nào trong phạm vi [1, khác]. Phần tử tiếp theo sẽ luôn là bội số của phần trước hoặc phần tử của phần trước để điều kiện chia hết được giữ nguyên. Ngoài ra, thừa số hoặc bội số phải nhỏ hơn 'khác'. Chúng tôi sẽ sử dụng lập trình động để lưu trữ các tính toán. Đối với điều này, chúng tôi sử dụng mảng arr [] []. Arr [1] [another] sẽ là 1 vì chúng sẽ là các mảng phần tử đơn. arr [i] [j] =arr [i − 1] [j] + thừa số của phần tử trước + bội số của phần tử trước (nhỏ hơn cái khác).
-
Lấy các số nguyên này và một số nguyên khác làm đầu vào.
-
Hàm Liền kề_elements (int đầu tiên, int thứ hai) trả về số lượng mảng trong đó tất cả các phần tử liền kề sao cho một trong số chúng chia cho phần còn lại.
-
Lấy số lượng ban đầu là 0 và mảng arr [size] [size].
-
Khởi tạo tất cả các số đếm là 0 bằng cách sử dụng memset.
-
Lấy hai vectơ - vec để lưu trữ hệ số và vec_2 để lưu trữ bội số.
-
Đảo ngược bằng cách sử dụng hai vòng lặp for từ i =t đến i =giây và j =2 * i đến j =giây. Phần tăng j của i.
-
Thêm i vào vec [j] và j vào vec_2 [i]. Sau vòng lặp j cũng thêm i vào vec [i].
-
Đặt arr [1] [i] bằng vòng lặp for.
-
Đảo ngược mảng một lần nữa và bây giờ duyệt qua vec và vec_2 và thêm các thừa số và bội số vào arr [i] [j].
-
Ở cuối, hãy thêm tất cả arr [first] [i] để đếm và xóa vec [i] và vec_2 [i].
-
Kết quả là số lượt trả lại.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of arrays in which all adjacent elements are such that one of them divide the another are: 4