kết quả từ 1 tới 3 trên 3

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

  1. #1
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 367175
    Bài gửi
    4

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

    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[i] < 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.
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 367175
    Bài gửi
    4

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

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

  3. #3
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    Câu 1: Mình chỉ recap thôi.
    Mã:
    bool isUgly(int n) {
        for (int i = 2; i < 6 && n; ++i)
            while (n % i == 0)
                n /= i;
        return n == 1;
    }

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

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

    Good luck.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  4. 2 thành viên đã cảm ơn tengiday: