Đếm số chuỗi ký tự nơi các ký tự liền kề khác nhau 1 đơn vị ASCII trong C++

Cho một số num làm đầu vào. Mục tiêu là đếm số chuỗi có độ dài num sao cho tất cả các ký tự liền kề có hiệu số giá trị ASCII bằng 1.

Nếu num = 2 thì các chuỗi sẽ là "ab", "ba", "bc", "cb", ..."yz", "zy".

Ví dụ

Đầu vào - num=3

Đầu ra - Số chuỗi nơi ký tự liền kề khác nhau 1 đơn vị là 98

Giải thích - Một số chuỗi mẫu: "abc", "aba", "cde" ..."xyx", "zyz", "xyz".

Đầu vào - num=2

Đầu ra - Số chuỗi nơi ký tự liền kề khác nhau 1 đơn vị là 50

Giải thích - Một số chuỗi mẫu: "ab", "ba", "cd" ..."xy", "zy", "yz".

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

Đối với độ dài = 2:

• Chuỗi bắt đầu bằng 'a' = "ab"
• Chuỗi bắt đầu bằng 'b' = "ba", "bc"
• Chuỗi bắt đầu bằng 'c' = "cd", "cb"...............

Đối với độ dài = n:

• Chuỗi bắt đầu bằng 'a' = số cách chuỗi độ dài n-1 bắt đầu bằng 'b'
• Chuỗi bắt đầu bằng 'b' = số cách chuỗi độ dài n-1 bắt đầu bằng 'a' hoặc 'c'
• Chuỗi bắt đầu bằng 'c' = số cách chuỗi độ dài n-1 bắt đầu bằng 'b' hoặc 'd'

Ta giải bằng quy hoạch động. Mảng arr[num+1][27] chứa số chuỗi độ dài i bắt đầu bằng chữ cái thứ j trong arr[i][j]. Tất cả arr[1][j] = 1 cho chuỗi "a", "b"..."z".

Còn lại cho arr[2 đến num+1][0 đến 25], gán arr[i][j] = arr[i-1][j+1] cho j=0. Ngược lại arr[i][j] = arr[i-1][j-1] + arr[i-1][j+1].

Kết quả là tổng các số hàng thứ num.

• Nhập số nguyên num
• Hàm difference_strings(int num) nhận num và trả về số chuỗi
• Khởi tạo count = 0
• Khởi tạo mảng arr[num + 1][27] với toàn 0
• Khởi tạo arr[1][0 đến 25] với toàn 1
• Duyệt mảng 2D bằng 2 vòng lặp từ hàng 2 đến cuối, cột 0 đến 25
• Với j=0 (ký tự 'a'): arr[i][j] = arr[i-1][j+1]
• Ngược lại: arr[i][j] = arr[i-1][j-1] + arr[i-1][j+1]
• Sau vòng lặp, duyệt hàng cuối cộng arr[num][0 đến 25] vào count
• Trả về count

Chương trình minh họa

#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 << "Số chuỗi nơi ký tự liền kề khác nhau 1 đơn vị là: " << difference_strings(num);
    return 0;
}

Đầu ra

Số chuỗi nơi ký tự liền kề khác nhau 1 đơn vị là: 50