Đếm số mảng có các phần tử liên tiếp khác nhau bằng C++

Cho ba biến size, max_val, last_element làm đầu vào. Mục tiêu là tìm số lượng mảng khác nhau có thể tạo ra sao cho: mảng có size phần tử, các phần tử từ 1 đến max_val, phần tử đầu tiên luôn là 1, phần tử cuối cùng luôn là max_val, và không có hai phần tử liên tiếp nào giống nhau.

Hiểu qua ví dụ

Ví dụ 1

Đầu vào: size = 5, max_val = 3, last_element = 3

Đầu ra: Số mảng thỏa mãn: 5

Giải thích: Các mảng 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].

Ví dụ 2

Đầu vào: size = 3, max_val = 2, last_element = 2

Đầu ra: Số mảng thỏa mãn: 0

Giải thích: Không thể tạo mảng 3 phần tử [1, _, 2] vì phần tử giữa chỉ có thể là 1 hoặc 2, vi phạm điều kiện phần tử liên tiếp khác nhau.

Phương pháp sử dụng

• Sử dụng quy hoạch động và tổ hợp để đếm các mảng như vậy.
• Phần tử đầu và cuối cố định là 1 và last_element. Với mảng độ dài size, chỉ cần điền size - 2 phần tử.
• Số cách điền các giá trị [1 đến max_val] vào size - 2 vị trí. Số cách sẽ là ways(max_val) = ways(size) / (max_val - 1).
• Với mỗi phạm vi 1 đến i, số cách ways(i) = ways(size) / (max_val - 1) [ways(size) = số cách phần tử cuối được điền bằng số 2 đến max_val].
• Nếu last_element == 1 thì số cách là ways(size - 1) vì phần tử cuối chỉ có thể là 1.
• Phần tử kế cuối luôn nằm giữa 1 và max_val.
• Nếu phần tử kế cuối không phải 1 thì số cách là (max_val - 2) * ways(i - 1) vì arr[i] không thể là 1 hoặc arr[i-1].
• Nếu phần tử kế cuối là 1 thì số cách là (max_val - 1) * ways(i - 1) vì arr[i-1] là 1 và arr[i-2] không phải 1.
• Công thức: Ways(i) = (max_val - 2) * ways(i - 2) + (max_val - 1) * ways(i - 1).
• Nhập các biến size, max_val, last_element.
• Hàm diff_val(int size, int max_val, int last_element) trả về số lượng mảng thỏa mãn.
• Khởi tạo count = 0.
• Mảng arr[Max_N] = {0} lưu số cách điền. Khởi tạo arr[0] = 0, arr[1] = 1.
• Duyệt từ i = 2 đến i < size.
• Tính temp_1 = (max_val - 2) * arr[i - 1] và temp_2 = (max_val - 1) * arr[i - 2].
• Gán arr[i] = temp_1 + temp_2.
• Nếu last_element == 1 thì count = (max_val - 1) * arr[size - 2].
• Ngược lại trả về arr[size - 1].
• Trả về count.

Ví dụ mã nguồn

#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; 
}

Chạy mã trên cho kết quả:

Kết quả

Count of arrays having consecutive element with different values are: 5