Trang 1 / 4 1234 LastLast
Hiển thị kết quả từ 1 đến 10 / 37
  1. #1
    Tham gia
    24-01-2007
    Bài viết
    249
    Like
    0
    Thanked 0 Times in 0 Posts

    Thuật toán pascal về số nguyên tố!

    - Vấn đề đặt ra ở đây là thi tin học trẻ không chuyên dành cho HS cấp 2. Mà với trình độ toán học cấp 2, hS mới chỉ hiểu khái niệm số nguyên tố: " SNT là số chỉ có 2 ước là một và chính nó". Nếu ta sử dụng thuật toán SNT có trong SGK thì làm sao giải thích cho HS cấp 2 hiểu được. Xin các pro đề xuất thuật toán dễ làm nhưng HS cấp 2 hiểu được với trình độ toán học của cấp 2.
    +++++++++++++++++++++++++++++++++++++++++++
    Mình nghĩ ra thuật toán sau, làm good với chương trình nhưng nhào nặn thành một function thì không được. Các bạn góp ý cho với nhé
    ++++++++++++++++++++++++++
    " Nhập vào một số nguyên từ bàn phím và kiểm tra xem số vừa nhập có phải là SNT hay không rồi xuất kết quả ra màn hình!"
    *****************************************
    program snt;
    var so, d, i : integer;
    begin
    d:=0;
    write (' Nhap so='); readln(so);
    for i:=1 to so div 2 do
    if so mod i =0 then inc(d);
    if d=2 then writeln(' So vua nhap la SNT!')
    elsse writeln('So vua nhap khong la SNT!');
    readln;
    end.
    **************************
    Quote Quote

  2. #2
    Tham gia
    29-02-2004
    Bài viết
    3,619
    Like
    0
    Thanked 8 Times in 7 Posts
    Vì cấp 2 nên mò mẫm chia từng số vậy mình nghĩ không thành vấn đề, mà cấp 2 học tới căn bậc 2 chưa? Nếu rồi thì xét tới sqrt(so) là được rồi.
    Cái vòng lặp bạn nên cải tiến chút.

    Code:
           nguyen_to:=true;
     For i:=2 to sqrt(so) do
             if so mod i <> 0 then 
                    begin
                  nguyen_to:=false;
                   break;
                    end;
    À mà trong bài bạn hình như d=1 thì hiện lên SNT mới đúng thì phải
    Được sửa bởi lee_huynh306 lúc 22:54 ngày 29-11-2008

  3. #3
    Tham gia
    24-01-2007
    Bài viết
    249
    Like
    0
    Thanked 0 Times in 0 Posts
    Thật ra thì lớp 9 đã học căn bậc 2. Tuy nhiên giảng giải thuật toán SNT có liên quan tới căn bậc 2 cảm thấy kiến thưc hơi rỗng, hs khó hiểu. Mình vận dụng kiến thức căn bản " số nguyên tố là số chỉ có 2 ước là 1 và chính nó" => mình sử dụng thuật toán tìm ước của số được nhập, nếu có 2 ước thì nó là snt và ngược lại thì không phải số nguyên tố. Cho nên d=2 thì mới là SNT.
    +++++++++++++++++++++++
    => Theo riêng mình thì thuật toán dễ hiểu, vận dụng toàn kiến thức cơ bản. Tuy nhiên mình không thể viết nó thành function được. Xin các bạn góp ý thêm!

  4. #4
    Tham gia
    29-02-2004
    Bài viết
    3,619
    Like
    0
    Thanked 8 Times in 7 Posts
    Bạn chỉ xét từ 1 đến so div 2, với trường hợp so là SNT thì ở đâu ra mà 2 lần chia hết, bạn đâu xét tới so đâu :|
    Mà bạn là giáo viên à?

  5. #5
    Tham gia
    24-01-2007
    Bài viết
    249
    Like
    0
    Thanked 0 Times in 0 Posts
    Quote Được gửi bởi lee_huynh306 View Post
    Bạn chỉ xét từ 1 đến so div 2, với trường hợp so là SNT thì ở đâu ra mà 2 lần chia hết, bạn đâu xét tới so đâu :|
    Mà bạn là giáo viên à?
    - Mình viết ra hàm được rồi. Bạn xem thử chương trình này nhé. MÌnh tâm đắc ở chỗ với thuật toán này thì giảng lớp 8 cũng sẽ hiểu bạn à. Lớp 8 chưa học căn bậc 2.
    ++++++++++++++++++++++++++++++++++
    Code:
    program snt;
        var a: integer;
      {********************************}
    function snt (so: integer): booloean;
         var d, i: integer;
        begin 
             d:=0;
             snt:=false;
             for i:=1 to so div 2 do
                  if so mod i = 0 then inc(d);
                  if d=1 then snt:=true;
         end;
     +++++++++++++++++++++++++++++++++++
    begin
          write (' Nhap so='); readln(a);
          if snt(a) = true then writeln (' la so nguyen to!')
          else                  writeln (' Khong la so nguyento!');
          readln;
    end.
    ============================================
    = Mình đang làm công tác bồi dưỡng HSG tin học trẻ không chuyên. Đây là năm đầu tiên làm việc này nên còn nhiều hạn chế. Hy vọng bạn có thể chia sẻ kinh nghiệm cho mình với! thankss
    +++++ MÌNH BẢO ĐẢM THUẬT TOÁN TRÊN LÀ DO MÌNH TỰ NGỘ RA ĐÓ, KHÔNG HỀ THAM KHẢO SÁCH NÀO CẢ.+++++++++
    Được sửa bởi dongcambiz lúc 00:08 ngày 30-11-2008

  6. #6
    Tham gia
    16-02-2007
    Location
    TP:HCM
    Bài viết
    319
    Like
    1
    Thanked 0 Times in 0 Posts
    Mình thường làm như thế này
    Code:
    function kt(n:integer):boolean;
    var i:integer;
    begin
       kt:=false;
       for i:=2 to trunc(sqrt(n)) do
          if n mod i=0 then exit;
       kt:=false;
    end;
    Với n bất kỳ:
    Code:
    if kt(n) then write(n,' la so nguyen to')
    else write(n,' khong la so nguyen to');

  7. #7
    Tham gia
    29-02-2004
    Bài viết
    3,619
    Like
    0
    Thanked 8 Times in 7 Posts
    Mình xin lỗi nhưng phải nói thẳng, bạn nên xem lại kiến thức toán học của bản thân, bạn mắc phải những lỗi rất ư là... con nít. Để mình phân tích nhé:
    - Khi so/2 < i < so thì 1 < so/i < 2 => chắc chắn so/i không bao giờ là số nguyên, vậy cớ gì phải cho vòng lặp chạy từ i đến so? => chạy đến so/2 (nếu không chịu sqrt(so))là được rồi.
    - Giả dụ so = 4, function bạn chạy nó sẽ xét i toàn bộ từ 1 - 4, đây là sự phí phạm thời gian hết sức trẻ con, mà khi đi thi thì hơn nhau một vài ms đã thắng rồi. Trong khi chỉ cần xét tới i = 2 là biết chắc chắn 4 không phải là số nguyên tố, tổng quát lên tới số 1 tỷ thì bạn phải chạy vòng lặp 1 tỷ lần mới có kết quả trong khi người ta lặp có 1-2 lần là người ta biết kết quả rồi.
    - Như bài trên đã nói, mặc định số nào cũng chia hết cho 1, không phải xét, phí thời gian. Mặc định tự hiểu. Thi học sinh giỏi là cuộc thi dành cho những người giỏi, biết tìm cách optimize thuật toán thật nhanh, thật gọn chứ không phải bám sát lý thuyết mà làm cho dài dòng.
    Nói thành ra mít lòng chứ bạn đi thi chưa chắc làm lại tụi nhóc kia nữa chứ ở đó mà... T.T

  8. 2 thành viên Like bài viết này:


  9. #8
    Tham gia
    24-01-2007
    Bài viết
    249
    Like
    0
    Thanked 0 Times in 0 Posts
    he, đâu có sao! Nói thẳng coi như góp ý. thankss bạn. Mình cũng biết vấn đề optimize thuật toán. Ý tưởng của mình là truyền đạt cơ bản đã. Mình chỉ có 4 tháng để bồi dưỡng hs mà trước giờ chưa từng biết gì ngoài word. Kiến thức căn bậc 2 mới học bên toán. Nếu bồi dưỡng cấp 3 thì dễ dàng hơn rồi.
    => Mình nghiệm ra điều bạn nói và kiểm tra trên máy rồi. cảm ơn!

    [=========> Bổ sung bài viết <=========]

    Quote Được gửi bởi langtusitinh225 View Post
    Mình thường làm như thế này
    Code:
    function kt(n:integer):boolean;
    var i:integer;
    begin
       kt:=false;
       for i:=2 to trunc(sqrt(n)) do
          if n mod i=0 then exit;
       kt:=false;
    end;
    Với n bất kỳ:
    Code:
    if kt(n) then write(n,' la so nguyen to')
    else write(n,' khong la so nguyen to');
    =>> MÌnh có dùng thuật toán này mà, vấn đề là làm sao vận dụng với học sinh lớp 8?
    Được sửa bởi dongcambiz lúc 00:07 ngày 30-11-2008 Reason: Bổ sung bài viết

  10. #9
    Tham gia
    01-11-2010
    Bài viết
    1
    Like
    0
    Thanked 0 Times in 0 Posts

    Thông tin

    mình có một thuật toàn có thể nhanh hơn chút:

    function ktnguyento(x:longint):longint;
    var i:longint;
    begin
    i:=2;
    while (x mod i <>0) and (x>=2) then
    i:=i+1;
    if i=x then
    ktnguyento:=1;{nếu là số nguyên tố}
    else
    ktnguyento:=0;{nếu ko là số nguyên tố}
    end;

    procedure ketqua;
    var i:longint;
    begin
    write('Nhap so x: ');
    readln(x);
    if ktnguyento(x)=1 then
    writeln('So ',x,' là số nguyên tố')
    else
    writeln('So ',x,' ko la so nguyen to');
    end;

    bài này có thể tốn ít thời gian hơn

  11. #10
    Tham gia
    05-05-2004
    Bài viết
    219
    Like
    2
    Thanked 7 Times in 7 Posts
    mình nghĩ thuật toán số nguyên tố là thuật toán rất căn bản và dễ hiẻu do chỉ cần đùng 1 vòng lặp là giải quyết được.
    nếu cần sd thì mình thường dùng 2 cách là dùng for để đếm ước hoặc dùng một biến tạm là kt (boolean) để kiểm tra trạng thái.
    mình viết vòng lặp như thế này: for i:=2 to n-1 do
    // chẳng cần giải thích là n div 2 hay j cả,.. vì nó cũng chẳng quan trọng lắm.
    và chẳng cần chạy nhanh nữa.

Trang 1 / 4 1234 LastLast

Bookmarks

Quy định

  • Bạn không thể tạo chủ đề mới
  • Bạn không thể trả lời bài viết
  • Bạn không thể gửi file đính kèm
  • Bạn không thể sửa bài viết của mình
  •