DạyhọcIntel.net  

Bộ Giáo dục
Đào tạo

Chương trình dạy học
của Intel tại Việt Nam

Tài liệu
Hướng dẫn Kỹ năng

Viện Nghiên cứu Giáo dục
ĐH Sư Phạm TP. HCM

Intel Teach Elements


Trở lại   DạyhọcIntel.net > Góc nghiệp vụ sư phạm > Công tác chuyên môn > Tin Học

Reply
 
Công cụ chủ đề Kiểu hiển thị
Old 29-10-2008, 21:58   #1
Thuật toán tìm các số nguyên tố nhỏ hơn N
Thu Ha Thu Ha is offline 29-10-2008, 21:58

Em có đọc một thuật toán đưa ra các số nguyên tố nhỏ hơn N, với N nhập từ bàn phím
Đoạn mã có đoạn
While i = 5 to n do
{
Repeat
j = -1
If (i mod 2 <>0) and (i mod 3<>0) then
inc (j,6)
Until (i mod j = 0) or (i mod (j+2) =0) or (sqr(i)>j))
If sqr(i)>j then
xuat i la so nguyen to
}
Thầy Cô nào có thể giải thích dùm em đoạn mã trên. Cảm ơn các Thầy Cô nhiều!

 
Thu Ha's Avatar
Thu Ha
Lớp mầm
Points: 2,675, Level: 14 Points: 2,675, Level: 14 Points: 2,675, Level: 14
Activity: 0% Activity: 0% Activity: 0%
Gia nhập: 07-2008
Đơn vị: Binh Duong
Bài viết: 4
Cảm ơn: 22
Được cảm ơn 1 lần trong 1 bài viết
Lượt xem: 3843
Trả lời kèm trích dẫn
Old 30-10-2008, 12:19   #2
dovannho
Đại học
Points: 266,623, Level: 100 Points: 266,623, Level: 100 Points: 266,623, Level: 100
Activity: 0% Activity: 0% Activity: 0%
 
dovannho's Avatar
 
Gia nhập: 08-2007
Đơn vị: THPT Trần Phú
Bài viết: 726
Cảm ơn: 1,060
Được cảm ơn 1,914 lần trong 521 bài
Mặc định

Trích dẫn:
Nguyên bản bởi Thu Ha Xem bài viết
Em có đọc một thuật toán đưa ra các số nguyên tố nhỏ hơn N, với N nhập từ bàn phím
Đoạn mã có đoạn
While i = 5 to n do
{
Repeat
j = -1
If (i mod 2 <>0) and (i mod 3<>0) then
inc (j,6)
Until (i mod j = 0) or (i mod (j+2) =0) or (sqr(i)>j))
If sqr(i)>j then
xuat i la so nguyen to
}
Thầy Cô nào có thể giải thích dùm em đoạn mã trên. Cảm ơn các Thầy Cô nhiều!

Đoạn chương trình này không biết minh hòa bằng ngôn ngữ gì? Hình như cả Pascal và C.
Trích dẫn:
While i = 5 to n do
Đoạn này chẳng hiểu thế nào?

Đoạn chương trình sau sẽ thực hiện 1 lần rồi dừng nếu i>=3 vì sqt(i) sẽ lớn hơn 5. (Inc(j,6) mà j ban đầu = -1)
Trích dẫn:
Repeat
j = -1
If (i mod 2 <>0) and (i mod 3<>0) then
inc (j,6)
Until (i mod j = 0) or (i mod (j+2) =0) or (sqr(i)>j))
Thuật toán này không giải quyết yêu cầu của đề.
dovannho is offline   Trả lời kèm trích dẫn
Old 30-10-2008, 13:03   #3
tungld
Cao đẳng
Points: 79,930, Level: 87 Points: 79,930, Level: 87 Points: 79,930, Level: 87
Activity: 0% Activity: 0% Activity: 0%
 
tungld's Avatar
 
Gia nhập: 02-2008
Đơn vị: Trường THPT Quảng Uyên, Cao Bằng
Bài viết: 542
Cảm ơn: 723
Được cảm ơn 955 lần trong 336 bài
Bài viết blog: 1
Mặc định

bài toán này dùng thuật toán sàng erathore sẽ hiệu quả hơn.
__________________
Biển học là vô bờ
Chuyên cần thì cập bến.
----------
Home page: thptquanguyen.edu.vn
tungld is offline   Trả lời kèm trích dẫn
Đã cảm ơn tungld:
Old 30-10-2008, 14:22   #4
huycom9999
Đại học
Points: 290,195, Level: 100 Points: 290,195, Level: 100 Points: 290,195, Level: 100
Activity: 0% Activity: 0% Activity: 0%
 
huycom9999's Avatar
 
Gia nhập: 08-2008
Đơn vị: Trường THCS Trần Cao Vân - Huế
Bài viết: 773
Cảm ơn: 1,255
Được cảm ơn 1,691 lần trong 557 bài
Bài viết blog: 3
Mặc định

Pascal làm gì có lệnh này "While i = 5 to n do", vui lòng cho biết đoạn lệnh trên viết theo NNLT nào nhé?
huycom9999 is offline   Trả lời kèm trích dẫn
Đã cảm ơn huycom9999:
Old 31-10-2008, 00:12   #5
dovannho
Đại học
Points: 266,623, Level: 100 Points: 266,623, Level: 100 Points: 266,623, Level: 100
Activity: 0% Activity: 0% Activity: 0%
 
dovannho's Avatar
 
Gia nhập: 08-2007
Đơn vị: THPT Trần Phú
Bài viết: 726
Cảm ơn: 1,060
Được cảm ơn 1,914 lần trong 521 bài
Mặc định

Trích dẫn:
Nguyên bản bởi tungld Xem bài viết
bài toán này dùng thuật toán sàng erathore sẽ hiệu quả hơn.
Thuật toán sàng erathore sẽ có một số nhược điểm sau:
- Dùng mảng để đánh dấu, nếu N lớn thì số phần tử của càng lớn
- Độ phức tạp thuật toán sàng erathore là N2 vì dùng 2 vòng lòng nhau để duyệt

Mình dùng thuật toán sau:
Mã lệnh:
Writeln(2);
Writeln(3);
Writeln(5);
{Xet cac so nguyen to >5 den N}
k:=7;l:=4;
While k<=N do
Begin
    Nt:=True;
    If (k mod 2=0) or (k mod 3=0)	Then Nt:=False;
    If nt then 
    Begin
      i:=5; j:=2;
      While i<trunc(sqrt(k)) do
      Begin
          If k mod i =0 Then
          Begin
              Nt:=False;
              Break;
          End;
          Inc(I,j); j:=6-j;
      End;
      If nt Then Writeln(k);
    End;
    Inc(k,l); l:=6-l;
End;

Trích dẫn:
Tập số cần xét của thuật toán: 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97 101 103 107 109 ...
- Không cần dùng đến mảng để đánh dấu như thuật toán sàng
- Độ phức tạp sẽ ít hơn vì các bước nhảy của là 2 và 4 không phải là 1 như For

Chỉnh sửa lần cuối bởi dovannho : 31-10-2008 lúc 00:28 Lý do: Thêm thông tin
dovannho is offline   Trả lời kèm trích dẫn
Đã cảm ơn dovannho:
Reply


Những người đang xem chủ đề này: 1 (0 thành viên và 1 khách)
 
Công cụ chủ đề
Kiểu hiển thị

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

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Nhảy đến diễn đàn

Những chủ đề liên quan
Chủ đề Người khởi xướng Diễn đàn Trả lời Bài cuối
Chỉ dùm thuật toán tìm Bội chung nhỏ nhất của 2 số nguyên dương hungchng Tin Học 29 02-11-2010 20:44
bút pháp ước lệ tượng trưng của Nguyễn Du qua đoạn trích" Thúc Sinh từ biệt Thuý Kiều hangnga14 Ngữ Văn 0 20-04-2009 21:31
Thuật tóan số nguyên tố - Tin học 10 huynhtanthong Tin Học 14 28-11-2008 15:26
Đột phá trong nhận thức về chúa Nguyễn, triều Nguyễn ProIT Góc trò chuyện 0 18-10-2008 12:46
Tặng ThiHoa, Sương Ngọc và Thuận Thuỷ nguyennga Góc trò chuyện 6 22-04-2008 08:27

Tất cả giờ đều quy về GMT +7. Bây giờ là 14:38.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Thuộc quyền sở hữu của DạyhọcIntel.net