Dãy Số Hamming

code

Bài toán Dãy số Hamming

Dãy số nguyên dương tăng dần, trong đó ước nguyên tố của mỗi số không quá 5 được gọi là dãy Hamming. Như vậy, 10 = 2×5 sẽ là một số trong dãy Hamming, còn 26 = 2×13 – không thuộc dãy Hamming.

Phần đầu của dãy Hamming là 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, . . .

Yêu cầu: Cho số nguyên x (1 ≤ x ≤ 1018). Hãy xác định số thứ tự của x trong dãy Hamming.

Dữ liệu: Vào từ file văn bản HAMMING.INP:

  • Dòng đầu tiên chứa số nguyên t – số lượng tests (1 ≤ t ≤ 105),
  • Mỗi dòng tiếp theo chứa một số nguyên x.

Kết quả: Đưa ra file văn bản HAMMING.OUT, kết quả mỗi test đưa ra trên một dòng dưới dạng số nguyên hoặc thông báo Notinsequence.

Ví dụ:

HAMMING.INP

HAMMING.OUT

11

1

2

6

7

8

9

10

11

12

13

14

1

2

6

Not in sequence 7

8

9

Not in sequence 10

Not in sequence Not in sequence

 

Thuật toán

Để giải quyết bài toán này, ta sẽ sử dụng kỹ thuật quy hoạch động (dynamic programming) để tính toán số thứ tự của từng số trong dãy Hamming.

Giả sử ta đã tính được số thứ tự của các số nhỏ hơn x trong dãy Hamming. Để tính số thứ tự của x, ta cần kiểm tra x có phải là số Hamming hay không, và nếu có, ta cần tìm số lượng các số nhỏ hơn x và có giá trị trong dãy Hamming.

Để kiểm tra x có phải là số Hamming hay không, ta sẽ kiểm tra x có chia hết cho tất cả các ước nguyên tố không lớn hơn 5 hay không. Nếu không, x không thuộc dãy Hamming và ta đưa ra thông báo “Notinsequence”.

Nếu x là số Hamming, ta sẽ tính số lượng các số nhỏ hơn x và có giá trị trong dãy Hamming. Để làm điều này, ta sẽ duyệt qua các số nhỏ hơn x và tính số lượng các số nhỏ hơn mà có thể nhân với 2, 3 hoặc 5 để tạo thành số mới trong dãy Hamming. Số lượng này chính là số thứ tự của x.

Sử dụng một mảng dp để lưu số thứ tự của từng số trong dãy Hamming. Ban đầu, dp[1] = 1 vì số đầu tiên trong dãy Hamming là 1. Sau đó, ta sử dụng công thức sau để tính dp[i]:

dp[i] = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)

trong đó p2, p3, p5 là chỉ số của số nhỏ nhất trong dãy Hamming mà nhân với 2, 3 hoặc 5 lớn hơn hoặc bằng i.

Sau khi tính được dp[x], ta sẽ đưa ra kết quả là dp[x], hoặc đưa ra thông báo “Notinsequence” nếu x không thuộc dãy Hamming.

Độ phức tạp của giải thuật này là O(t log t), trong đó t là số lượng test case. Cụ thể, độ phức tạp của mỗi test case là O(log x) do ta cần duyệt qua các số nhỏ hơn x để tính dp[x].

Cài đặt bài toán với Python

def is_hamming_number(x):
    # kiểm tra x có phải là số Hamming hay không
    # trả về True nếu đúng, False nếu sai
    for p in [2, 3, 5]:
        while x % p == 0:
            x //= p
    return x == 1


def hamming_number_index(x):
    # tính số thứ tự của x trong dãy Hamming
    dp = [0] * (x + 1)
    dp[1] = 1
    p2 = p3 = p5 = 1

    for i in range(2, x + 1):
        while dp[p2] * 2 <= dp[i - 1]:
            p2 += 1
        while dp[p3] * 3 <= dp[i - 1]:
            p3 += 1
        while dp[p5] * 5 <= dp[i - 1]:
            p5 += 1

        dp[i] = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)

    if is_hamming_number(x):
        return dp[x]
    else:
        return "Notinsequence"


# đọc dữ liệu từ file HAMMING.INP và tính toán kết quả cho từng test case
with open("HAMMING.INP", "r") as input_file:
    t = int(input_file.readline().strip())
    results = []
    for i in range(t):
        x = int(input_file.readline().strip())
        results.append(hamming_number_index(x))

# ghi kết quả vào file HAMMING.OUT
with open("HAMMING.OUT", "w") as output_file:
    for result in results:
        output_file.write(str(result) + "\n")

Cài đặt bài toán với C++

#include <bits/stdc++.h>
using namespace std;

bool is_hamming_number(int x) {
    // kiểm tra x có phải là số Hamming hay không
    // trả về true nếu đúng, false nếu sai
    for (int p : {2, 3, 5}) {
        while (x % p == 0) {
            x /= p;
        }
    }
    return x == 1;
}

int hamming_number_index(int x) {
    // tính số thứ tự của x trong dãy Hamming
    vector<int> dp(x + 1);
    dp[1] = 1;
    int p2 = 1, p3 = 1, p5 = 1;

    for (int i = 2; i <= x; i++) {
        while (dp[p2] * 2 <= dp[i - 1]) {
            p2++;
        }
        while (dp[p3] * 3 <= dp[i - 1]) {
            p3++;
        }
        while (dp[p5] * 5 <= dp[i - 1]) {
            p5++;
        }

        dp[i] = min(dp[p2] * 2, min(dp[p3] * 3, dp[p5] * 5));
    }

    if (is_hamming_number(x)) {
        return dp[x];
    } else {
        return -1;
    }
}

int main() {
    freopen("HAMMING.INP", "r", stdin);
    freopen("HAMMING.OUT", "w", stdout);

    int t;
    cin >> t;

    vector<int> results(t);
    for (int i = 0; i < t; i++) {
        int x;
        cin >> x;
        results[i] = hamming_number_index(x);
    }

    for (int result : results) {
        if (result == -1) {
            cout << "Notinsequence" << endl;
        } else {
            cout << result << endl;
        }
    }

    return 0;
}

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *