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

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
    6

    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.628

    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
    38

    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
    6

    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
    38

    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
    6

    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
    38

    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:


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

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

    cho mình hỏi 1 chút:
    1.helper là một hàm hay thu tục vậy bạn
    2.s số nguyên tố hiện tại chỗ này là như thế nào bạn giải thích rõ hơn 1 chút không ạ.
    3.vì sao khi lấy phần nguyên cộng thêm 1
    4. helper(n, t); cái này đệ quy lại hả bạn.
    5.vì sao n =8 và gọi gọi ctc lại vói n và các số nguyên tố trên là như thế nào?
    nhờ bạn giải thích giùm

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

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

    Bạn nên hiểu cái tư tưởng trước. Giả sử n = 3 (cần tìm các số siêu nguyên tố có 3 chữ số).
    - Bắt đầu là số nguyên tố 2, tức là helper(3, 2). Tức là s = 2. Em có t là {21, 23, 27, 29}. Như vậy chỉ có 23 và 29 thỏa mãn. Tiếp theo sẽ gọi helper(3, 23) và helper(3, 29).
    - Từ số nguyên tố 23 (tức là s=23), em có t là {231, 233, 237, 239}. Chỉ có 233, 239 là prime. Tiếp theo sẽ gọi helper(3, 233) và helper(3, 239)
    - Vì 233 và 239 đã có đủ 3 chữ số nên in ra 2 số này.
    - Tiếp theo quay lui xét số nguyên tố 29, em có t là {291, 293, 297, 299}. Chỉ có 293 là prime. Tiếp theo sẽ gọi helper(3, 293).
    - Vì 293 đã có đủ 3 chữ số nên in ra số này
    Như vậy những số siêu nguyên tố bắt đầu là 2 gồm: 233, 239, 293.
    - Tương tự em làm cho số siêu nguyên tố bắt đầu là 3, 5, 7. helper(3, 3), helper(3, 5), helper(3, 7)
    Mã:
                        21 (k prime)
                                             231 (k prime)
                        23 ------------->    233
                                             237 (k prime)
                                             239
    2 ------------->    27 (k prime)
                                             291 (k prime)
                        29 ------------->    293
                                             297 (k prime)
                                             299 (k prime)

    1) helper là procedure theo ngôn ngữ Pascal
    2) Bạn xem ví dụ trên sẽ hiểu s là gì
    3) Cái này là công thức. Bạn Google xem số chữ số của 1 số nguyên dương được tính thế nào nha.
    4) Đúng rồi, cái này là đệ quy
    5) n=8 vì em cho ví dụ cho dễ làm. Chứ nhập xuất nhiều quá bạn đâu hiểu
    helper(n, 2), helper(n, 3), helper(n, 5), helper(n, 7) là bắt buộc vì em đang xét TẤT CẢ số nguyên tố bắt đầu từ 2, 3, 5, 7

    Thực ra số n k cần đưa vào helper cũng được vì nó là biến toàn cục rồi

  12. Đã cảm ơn LanSG9x: