Bài tập C trước tết: số xấu, số siêu xấu

LittleABC · 31/12/16

Số xấu là số khi phân tích ra thừa số nguyên tố thì chỉ gồm các số 2, 3, hoặc 5. Giả sử 1 luôn luôn là số xấu.
Ví dụ: 6 và 8 là số xấu, 14 không phải là số xấu.
1) Cho một số tự nhiên 0 < N < 2^31. Viết chương trình kiểm tra N có phải là số xấu hay không?

2) Cho một số tự nhiên 0 < N <= 3000. Viết chương trình in ra số xấu thứ N.
Ví dụ: N = 10 thì in ra 12 bởi vì dãy 10 số xấu đầu tiên là: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12.

3) Số siêu xấu là số mà khi phân tích ra thừa số nguyên tố chỉ gồm các số nguyên tố được cho trước trong "danh sách số nguyên tố", gọi là primes. Giả sử 1 luôn luôn là số siêu xấu. Ví dụ: nếu primes = {2, 7, 13, 19} thì dãy số siêu xấu là: 1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32.
Input:
- Danh sách số nguyên tố 'primes' được sắp xếp theo thứ tự tăng dần có tối đa 100 số, mỗi số 0 < primes < 1000.
- Một số tự nhiên 0 < N <= 10^6.
Output:
- Số siêu xấu thứ N.

Input cho 3 bài sẽ đảm bảo kết quả không vượt quá 2^31. Ví dụ: bài 3 sẽ không bao giờ có test case primes = {2} và n = 32.

Mình đã làm được bài 1. Riêng bài 2 và bài 3 mình không có cách làm nào tốt cả. Mong mọi người giúp đỡ.

Edit 1: Thầy mới thêm vào yêu cầu dữ liệu.

LittleABC · 2/1/17

Ai giúp mình làm mấy bài này với. Xin cám ơn.

tengiday · 4/1/17

Câu 1: Mình chỉ recap thôi.
[ah]

Mã:

bool isUgly(int n) {
    for (int i = 2; i < 6 && n; ++i)
        while (n % i == 0)
            n /= i;
    return n == 1;
}

[/ah]
Câu 2: Câu này trọng điểm là có một số xấu f[k] thì số xấu tiếp theo phải là min(2 * f[k2], 3 * f[k3], 5 * f[k5]). Tức có nghĩa rằng bạn cần dùng 3 pointers cho hệ số 2, 3, và 5.
[ah]

Mã:

int nthUglyNumber(int n) {
    int * F = (int *)malloc(sizeof(int) * n), r2 = 0, r3 = 0, r5 = 0;
    F[0] = 1;
    for (int i = 1; i < n; ++i) {
        F[i] = std::min(2 * F[r2], std::min(3 * F[r3], 5 * F[r5]));
        if (F[i] == 2 * F[r2])
            ++r2;
        if (F[i] == 3 * F[r3])
            ++r3;
        if (F[i] == 5 * F[r5])
            ++r5;
    }
    int answer = F[n - 1];
    free(F);

    return answer;
}

[/ah]
Câu 3: Đây là generalization của bài 2. Tư tưởng tương tự như câu 2, chỉ là bây giờ số pointers bằng với số lượng các số trong primes.
[ah]

Mã:

int nthSuperUglyNumber(int n, std::vector<int> &primes) {
    int * F = (int *)malloc(sizeof(int) * n); F[0] = 1;
    int * index = (int *)malloc(sizeof(int) * primes.size());
    memset(index, 0, sizeof(int) * primes.size());
    for (int i = 1; i < n; ++i) {
        F[i] = INT_MAX;
        for (int j = 0; j < (int)primes.size(); ++j)
            F[i] = std::min(F[i], primes[j] * F[index[j]]);
        for (int j = 0; j < (int)primes.size(); ++j)
            index[j] += F[i] == primes[j] * F[index[j]];
    }
    int answer = F[n - 1];
    free(F);
    free(index);

    return answer;
}

[/ah]
Good luck.

Bài tập C trước tết: số xấu, số siêu xấu

LittleABC

tengiday

Happy life

Bài viết mới nhất

Thống kê