Cho ba biến kích thước, max_val, last_element làm đầu vào. Mục tiêu là tìm số lượng các mảng khác nhau có thể được tạo thành theo cách chúng có các phần tử kích thước, có các phần tử từ 1 đến max_val và phần tử đầu tiên luôn là 1 và phần tử cuối cùng luôn là max_val. Đồng thời đảm bảo rằng không có hai phần tử liên tiếp nào giống nhau.
Hãy cho chúng tôi hiểu với các ví dụ.
Ví dụ
Đầu vào - size =5, max_val =3, last_element =3
Đầu ra - Số mảng có phần tử liên tiếp với các giá trị khác nhau là:5
Giải thích - Các mảng sẽ là:-
[1, 2, 3, 1, 3], [1, 2, 3, 2, 3], [1, 2, 1, 2, 3], [1, 3, 1, 2, 3], [1 , 3, 2, 1, 3].
Đầu vào - size =3 max_val =2 last_element =2
Đầu ra - Số mảng có phần tử liên tiếp với các giá trị khác nhau là:0
Giải thích - Không thể có mảng nào có 3 phần tử và có [1, _, 2] là phần tử liên tiếp vì chúng tôi không thể điền bất kỳ thứ gì ngoại trừ 1 hoặc 2 cho phần tử ở giữa và điều này sẽ vi phạm điều kiện của các phần tử khác nhau liên tiếp.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
- Trong cách tiếp cận này, chúng tôi sẽ sử dụng lập trình động và tổ hợp để tìm số mảng như vậy.
- Phần tử đầu tiên và cuối cùng sẽ được cố định là 1 và last_element. Đối với bất kỳ kích thước nào của mảng, cách điền nó sẽ chỉ dành cho các phần tử có kích thước 2.
- Để điền các phần tử [1 đến max_val] vào các vị trí có kích thước-2. Cách sẽ là cách (max_val) =cách (kích thước) / (max_val - 1)
- Đối với mỗi phạm vi từ 1 đến i, các cách sẽ là các cách (i) =cách (kích thước) / (max_val - 1) [cách (kích thước) =số cách phần tử cuối cùng có thể được điền từ số 2 đến max_val).
- Nếu last_element là 1 thì các cách sẽ là các cách (kích thước-1) vì phần tử cuối cùng chỉ có thể là 1.
- Phần tử cuối cùng thứ hai luôn có thể nằm trong khoảng từ 1 đến max_val.
- Nếu phần tử cuối cùng thứ hai không phải là 1 thì các cách sẽ là (max_val-2) * các cách (i-1) vì arr i không thể là 1 hoặc arr i-1
- Nếu phần tử cuối cùng thứ hai là 1 thì các cách sẽ là (max_val-1) * cách (i-1) là arr i-1 là 1 và arr i-2 không phải là 1.
- Cách (i) sẽ là:- (max_val - 2) * cách (i-2) + (max_val-2) * cách (i-1)
- Lấy các biến size, max_val và last_element làm đầu vào.
- Hàm diff_val (int size, int max_val, int last_element) nhận tất cả các đầu vào và trả về số lượng mảng có các phần tử liên tiếp với các giá trị khác nhau.
- Lấy số lượng ban đầu là 0.
- Lấy mảng arr [Max_N] ={0} lưu trữ số cách điền vào mảng. Khởi tạo arr [0] với 0 và arr [1] với 1.
- Chuyển từ i =2 sang i
- Lấy temp_1 =(max_val - 2) * arr [i - 1] và temp_2 =(max_val - 1) * arr [i - 2]
- Đặt arr [i] =temp_1 + temp_2.
- Trong trường hợp last_element ==1 thì đặt count =(max_val - 1) * arr [size - 2].
- Nếu không, trả về arr [size - 1].
- Kết quả là số lượt trả lại cuối cùng.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
#define Max_N 109
int diff_val(int size, int max_val, int last_element) {
int count = 0;
int arr[Max_N] = {
0
};
arr[0] = 0;
arr[1] = 1;
for (int i = 2; i < size; i++) {
int temp_1 = (max_val - 2) * arr[i - 1];
int temp_2 = (max_val - 1) * arr[i - 2];
arr[i] = temp_1 + temp_2;
}
if (last_element == 1) {
count = (max_val - 1) * arr[size - 2];
} else {
return arr[size - 1];
}
return count;
}
int main() {
int size = 5;
int max_val = 3;
int last_element = 3;
cout << "Count of arrays having consecutive element with different values are: " << diff_val(size, max_val, last_element);
return 0;
} Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Đầu ra
Count of arrays having consecutive element with different values are: 5