Chúng tôi được cung cấp một số num làm đầu vào. Mục đích là để đếm số lượng các chuỗi có độ dài num sao cho tất cả các ký tự liền kề có sự khác biệt giữa các giá trị ascii là 1.
Nếu num là 2 thì các chuỗi sẽ là “ab”, “ba”, “bc”, “cb”, …… .. ”yz”, “zy”.
Hãy cho chúng tôi hiểu với các ví dụ
Đầu vào - num =3
Đầu ra - Số lượng các chuỗi trong đó các ký tự liền kề khác nhau một là - 98
Giải thích - Một số chuỗi mẫu là:“abc”, “aba”, “cde”… .. ”xyx”, “zyz”, “xyz”.
Đầu vào - num =2
Đầu ra - Số lượng các chuỗi trong đó các ký tự liền kề khác nhau một là - 50
Giải thích - Một số chuỗi mẫu là:“ab”, “ba”, “cd”… .. ”xy”, “zy”, “yz”.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Đối với chiều dài =2.
Chuỗi bắt đầu bằng a =“ab”
Các chuỗi bắt đầu bằng b =“ba”, “bc”
Các chuỗi bắt đầu bằng c =“cd”, “cb” ...............
Đối với length =n.
Chuỗi bắt đầu bằng a =cách số chuỗi có độ dài n-1 bắt đầu bằng b
Chuỗi bắt đầu bằng b =cách số chuỗi có độ dài n-1 bắt đầu bằng a hoặc c
Chuỗi bắt đầu bằng c =cách số chuỗi có độ dài n-1 bắt đầu bằng b hoặc d
Chúng tôi sẽ giải quyết vấn đề này bằng cách sử dụng lập trình động.
Lấy mảng arr [num + 1] [27]. Chứa một số chuỗi có độ dài i bắt đầu bằng số j trong bảng chữ cái trong arr [i] [j]. Tất cả arr [1] [j] sẽ là 1 cho các chuỗi “a”, “b” ... ”z”.
Phần còn lại cho arr [2 đến num + 1] [0 đến 25], đặt arr [i] [j] =arr [i-1] [j + 1] cho j =0. Tập hợp khác arr [i] [j] =arr [i-1] [j-1] + arr [i-1] [j + 1];
Kết quả sẽ là tổng số hàng thứ n.
-
Lấy số nguyên đầu vào
-
Hàm diff_strings (int num) nhận num và trả về số lượng các chuỗi trong đó các ký tự liền kề khác nhau một
-
Lấy số lượng ban đầu là 0.
-
Khởi tạo arr [num + 1] [27] với tất cả các số 0.
-
Khởi tạo arr [1] [0 đến 25] với tất cả 1.
-
Traverse mảng 2D arr [] [] bằng cách sử dụng hai vòng lặp for từ hàng thứ 2 đến hàng cuối cùng và cột 0 đến 25 cho tất cả 26 bảng chữ cái.
-
Đối với j =0, ký tự bắt đầu là ‘a’. Đặt số lượng hiện tại là arr [i] [j] =arr [i - 1] [j + 1];
-
Nếu không thì đặt arr [i] [j] =(arr [i - 1] [j - 1] + arr [i - 1] [j + 1])
-
Bây giờ, sau khi kết thúc các vòng ở trên, lướt qua hàng cuối cùng và thêm arr [num] [0 đến 25] để đếm.
-
Kết quả là số lượt trả lại.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int difference_strings(int num){
long int count = 0;
long int arr[num + 1][27];
memset(arr, 0, sizeof(arr));
for (int i = 0; i <= 25; i++){
arr[1][i] = 1;
}
for (int i = 2; i <= num; i++){
for (int j = 0; j <= 25; j++){
if (j == 0){
arr[i][j] = arr[i - 1][j + 1];
}
else{
arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1]);
}
}
}
for (int i = 0; i <= 25; i++){
count = (count + arr[num][i]);
}
return count;
}
int main(){
int num = 2;
cout<<"Count of strings where adjacent characters are of difference one are: "<<difference_strings(num);
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 strings where adjacent characters are of difference one are: 50