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

Thuật toán tối ưu: Số siêu nguyên tố

  1. #1
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 393948
    Bài gửi
    5

    Thuật toán tối ưu: Số siêu nguyên tố

    thuật toán tối ưu nhất giải quyết bài toán này như thế nào vậy ạ
    Bài 7. Số siêu nguyên tố. (Đề thi HSG Thành phố)
    Số P gọi lầ số siêu nguyên tố, nếu nó nguyên tố và khi ta lần lượt bỏ các chữ số ở hàng đơn vị từ tái qua phải thì số mới nhận được vẫn là một số nguyên tố.
    Ví dụ: 239 là số siêu nguyên tố vì 239 là số nguyên tố và 23, 2 cũng là các số nguyên tố , còn 431 là số nguyên tô, 43 cũng là số nguyên tố, nhưng 4 không nguyên tố nên 431 không phải là số siêu nguyên tố. Cho một số n (0<n<10) Hãy đếm số lượng các số siêu nguyên tố có n chữ số .
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 177479
    Giới tính: Nam
    Bài gửi
    5.566

    Reply: thuật toán tối ưu nhất giải quyết bài toán này như thế nào vậy ạ

    Một dãy a[] = {1,2,3,5,7,9} là dãy các số con
    Chọn dãy này vì chắc chắn số đầu tiên phải là số nguyên tố
    Có số 1 vì số nguyên tố tận cùng là 1 cũng có thể là số siêu nguyên tố
    Từ dãy trên ta sẽ sắp xếp và check để kiểm tra số nguyên tố
    Bạn lập trình hay thi thuật toán không thôi để mình viết chi tiết cách của mình
    Hãy Support theo cách của bạn
    Hãy thank theo cách của tôi



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

    Reply: thuật toán tối ưu nhất giải quyết bài toán này như thế nào vậy ạ

    +1 cho bạn 365 Designer.
    Em cũng nghĩ dựa vào dãy {1, 2, 3, 5, 7, 9} để xây dựng số nguyên tố từ ít chữ số tới nhiều chữ số.

  4. #4
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 393948
    Bài gửi
    5

    Reply: thuật toán tối ưu nhất giải quyết bài toán này như thế nào vậy ạ

    mình lập trình nhờ ban 365 designer cho mình xin thuật toán đi kèm cả code mình nghiên cứu để hiểu với ạ

  5. #5
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 402126
    Giới tính: Nữ
    Bài gửi
    37

    Reply: thuật toán tối ưu nhất giải quyết bài toán này như thế nào vậy ạ

    Lần trước hỏi bạn đó cũng lặn. Em k biết Pascal. Em viết bằng C++ nha. Em thấy chuyển qua Pascal k khó đâu
    Mã:
    int n, a[4] = { 1, 3, 7, 9 };
    
    void helper(int n, int s) {
        if (int(log10(s)) + 1 == n)
            printf("%d\n", s);
        else
            for (int i = 0; i < 4; i++) {
                int t = s * 10 + a[i];
                if (prime(t)) // kiem tra t co phai la nguyen to k
                    helper(n, t);
            }
    }
    
    int main() {
        n = 8;
        helper(n, 2);
        helper(n, 3);
        helper(n, 5);
        helper(n, 7);
    }

  6. Đã cảm ơn LanSG9x:


  7. #6
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 393948
    Bài gửi
    5

    Reply: thuật toán tối ưu nhất giải quyết bài toán này như thế nào vậy ạ

    nt n, a[4] = { 1, 3, 7, 9 };//bạn nói rõ chỗ này mình với

    void helper(int n, int s) // số n và số s có ý nghĩa j bạn

    //
    {
    if (int(log10(s)) + 1 == n)//chỗ này là sao hả bạn
    printf("%d\n", s); // giải thích 2 chỗ này giùm mình
    else
    for (int i = 0; i < 4; i++) { //đây vòng lặp
    int t = s * 10 + a[i];
    if (prime(t)) // kiem tra t co phai la nguyen to k
    helper(n, t);
    }// đoạn này là một chương trình con đúng ko bạn
    Nói chung nhờ bạn giải thích dùm mình các lệnh trong đó với ạ để mình cs thể chuyển sang pascal dk

  8. #7
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 402126
    Giới tính: Nữ
    Bài gửi
    37

    Reply: Thuật toán tối ưu: Số siêu nguyên tố

    Cách làm của em là từ số nguyên tố có k chữ số, thêm 1 chữ số để tạo thành số nguyên tố có k+1 chữ số. Em bắt đầu bằng số nguyên tố có 1 chữ số, là 2, 3, 5, 7. Sau đó thêm vào những chữ số {1, 3, 7, 9} vì đó là những chữ số tận cùng của số nguyên tố.
    Mã:
    int n,   // n chữ số
        a[4] = { 1, 3, 7, 9 };   // chữ số tận cùng của số nguyên tố có nhiều hơn 1 chữ số (mảng hằng)
    
    
    // n chữ số, s là số nguyên tố hiện tại. "helper" là chương trình con như bạn ghi
    void helper(int n, int s) {
        // nếu số nguyên tố hiện tại s có đủ n chữ số như đề yêu cầu thì in ra
        // số chữ số của 1 số nguyên dương s trong hệ cơ số 10 là: phần nguyên của log cơ 10 của s, sau đó +1
        if (int(log10(s)) + 1 == n)
            printf("%d\n", s); // in ra số tìm được
        else // nếu không đủ n chữ số thì thêm các chữ số {1, 3, 7, 9} từ tập a
            for (int i = 0; i < 4; i++) {
                int t = s * 10 + a[i];
                if (prime(t)) // kiem tra t co phai la nguyen to k
                    helper(n, t);
            }
    }
    
    
    int main() {
        n = 8;
        helper(n, 2); // số nguyên tố bắt đầu là 2
        helper(n, 3); // số nguyên tố bắt đầu là 3
        helper(n, 5); // số nguyên tố bắt đầu là 5
        helper(n, 7); // số nguyên tố bắt đầu là 7
    }

  9. Đã cảm ơn LanSG9x: