Trang 1 / 2 12 LastLast
Hiển thị kết quả từ 1 đến 10 / 11

Chủ đề: Giải dùm e mn ơi

  1. #1
    Tham gia
    04-10-2015
    Bài viết
    5
    Like
    0
    Thanked 0 Times in 0 Posts

    Giải dùm e mn ơi

    Bài 1: Viết chương trình nhập vào số nguyên n. Tính tổng các số nguyên tố nhỏ hơn n
    Vd: Nhập vào số nguyên 4( các số nguyên tố nhỏ hơn 4 là 2,3 )è xuất ra S=5
    Quote Quote

  2. #2
    Tham gia
    24-10-2015
    Bài viết
    3
    Like
    2
    Thanked 0 Times in 0 Posts
    Quote Được gửi bởi nguyenphuhiep View Post
    Bài 1: Viết chương trình nhập vào số nguyên n. Tính tổng các số nguyên tố nhỏ hơn n
    Vd: Nhập vào số nguyên 4( các số nguyên tố nhỏ hơn 4 là 2,3 )è xuất ra S=5
    uses crt;
    var i,s,n:longint;
    function snt(x:longint):boolean;
    var j:longint;
    begin
    snt:=true;
    if x<1 then snt:=false else
    for j:=2 to trunc(sqrt(x)) do
    if x mod j=0 then snt:=true;
    end;
    BEGIN
    write('nhap n: '); readln(n);
    s:=0;
    for i:=2 to n-1 do if snt=true then s:=s+1;
    write('tong cac snt <',n,' la:' s);
    readln
    end.

  3. #3
    Tham gia
    15-03-2010
    Bài viết
    1,562
    Like
    84
    Thanked 1,571 Times in 860 Posts
    Quote Được gửi bởi 10mvannoi View Post
    uses crt;
    var i,s,n:longint;
    function snt(x:longint):boolean;
    var j:longint;
    begin
    snt:=true;
    if x<1 then snt:=false else
    for j:=2 to trunc(sqrt(x)) do
    if x mod j=0 then snt:=true;
    end;
    BEGIN
    write('nhap n: '); readln(n);
    s:=0;
    for i:=2 to n-1 do if snt=true then s:=s+1;
    write('tong cac snt <',n,' la:' s);
    readln
    end.
    Code viết cẩu thả sai cú pháp tùm lum. Mà dẫu có viết đúng cú pháp thì giải như thế này cũng chỉ được tối đa 5/10.

    1. Giải thuật xét số nguyên tố quá ấu trĩ. Gải thuật tối thiểu phải là:
    Xét bit nhỏ nhất, nếu 0 thì là số chẵn. Nếu 1 thì là số lẻ, tính tiếp.
    Vòng lặp khởi từ sô 3, và bước nhảy 2 (không cần thử chia số chẵn).

    2. Nhưng bài này là cần tìm các số nguyên tố nhỏ hơn n. Cho nên dùng hàm xét số nguyên tố đơn độc là sai. Giải thuật đúng là lập một mảng giữ các số nguyên tố tìm được.
    2.1 muốn thử 1 số nguyên tố thì ta chia thử nó cho các số nguyên tố nhỏ hơn hay bằng căn của nó.
    2.2 khi tìm các số nguyên tố nhỏ hơn n thì ta chỉ tính số lẻ và lướt qua số chẵn.

  4. #4
    Tham gia
    27-01-2016
    Location
    THCS Phan Đăng Lưu
    Bài viết
    57
    Like
    1
    Thanked 92 Times in 39 Posts
    Mấy bác để tui.

    - - - Updated - - -

    bài này quá dễ.

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


  6. #5
    Tham gia
    27-01-2016
    Location
    THCS Phan Đăng Lưu
    Bài viết
    57
    Like
    1
    Thanked 92 Times in 39 Posts
    program ng_to;
    ues crt;
    var i,n,j,k,l:integer;
    function ngto(n:integer):boolean;
    var kt:boolean;
    i,s:integer;
    begin
    s:=0;
    kt:=false;
    for i:=1 to n do
    if n mod i=0 then s:=s+1;
    if s=2 then kt:=true;
    ngto:=kt;
    end;
    begin
    clrscr;
    write('Nhap so n:');readln(n);]
    t:=0;
    for i:=1 to n-1 do
    if ngto(i) then t:=t+i;
    writeln('Tong cac so ngto nho hon ',n,' la: ',t);
    readln
    end.

  7. 5 thành viên Like bài viết này:


  8. #6
    Tham gia
    15-02-2016
    Bài viết
    62
    Like
    49
    Thanked 0 Times in 0 Posts
    mình nghĩ cái function ngto nên thế này thì hơn:
    function ngto(n:integer):boolean;
    var i:integer;
    begin
    if n<2 then ngto:=false else
    if n<4 then ngto:=true else
    begin
    ngto:=true;
    for i:=2 to trunc(sqrt(n)) do
    if n mod i=0 then ngto:=false;
    end;
    end;

  9. #7
    Tham gia
    27-01-2016
    Location
    THCS Phan Đăng Lưu
    Bài viết
    57
    Like
    1
    Thanked 92 Times in 39 Posts
    Sao vậy mình thấy đúng mà ?

  10. #8
    Tham gia
    15-02-2016
    Bài viết
    62
    Like
    49
    Thanked 0 Times in 0 Posts
    function của mình chỉ for i tới phần nguyên của căn n nên nó sẽ làm giảm thời gian chạy chương trình, vì ở đây ta chỉ cần tìm thấy 1 i mà n chia hết cho i thì n đó ko phải là số nguyên tố rồi

  11. #9
    Tham gia
    27-01-2016
    Location
    THCS Phan Đăng Lưu
    Bài viết
    57
    Like
    1
    Thanked 92 Times in 39 Posts
    -Còn cái của mình thì kiểm tra xem số đó có 2 ước hay không.
    ----> Nếu có 2 ước thì số đó là số nguyên tố ngược lại thì không phải (bởi vì số nguyên tố chỉ có 2 ước là 1 và chính nó).
    Mình thì chưa biết function của bạn đúng hay sai (vì chưa thử),nhưng theo cách nói thì có vẻ time chạy chương trình của bạn nhanh hơn.
    Trong khi đó thì function của mình thì phải chạy hết vòng for để kiểm tra nên time chạy chương trình có thể sẽ chậm hơn so với cái của bạn.

  12. #10
    Tham gia
    29-02-2016
    Bài viết
    6
    Like
    1
    Thanked 0 Times in 0 Posts
    Dùng sàng nguyên tố để giảm độ phức tạp,tg chạy nhah hơn

Trang 1 / 2 12 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
  •