Bài tập viết chương trình Pascal

[snowangel1103]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

1/ Cải tiến thuật toán kiểm tra tính chất nguyên tố của số nguyên N
(gợi ý: để xác định các ước số của N...có nhất thiết phải duyệt tất cả số nguyên từ 1 -> N không?)

 

[lamdetien36]

1/ Cải tiến thuật toán kiểm tra tính chất nguyên tố của số nguyên N
(gợi ý: để xác định các ước số của N...có nhất thiết phải duyệt tất cả số nguyên từ 1 -> N không?)

Chỉ cần duyệt các số nguyên từ 2 -> phần nguyên của $\sqrt{N}$

 

[lamdetien36]

Giải thích lý do:
Giả sử ta tìm được i sao cho N chia hết cho i, tức là tồn tại j sao cho
N = i * j
Khi đó j cũng là ước của N.
Nếu như ta giả sử i <= j thì i <= $\sqrt{N}$.
Như vậy chỉ cần xét các ước từ 2 -> $\sqrt{N}$, các ước còn lại không cần phải xét.
Chương trình minh hoạ:

var
    N, i, d: integer;
begin
    write('Nhap N: '); readln(N);
    d := 0;
    for i := 2 to trunc(sqrt(N)) do
    begin
        if N mod i = 0 then d := d + 1;
    end;
    if (d = 0) and (N >= 2) then 
        write('N La SNT')
    else 
        write('N Khong Phai SNT');
    readln
end.

 

[thienvamai]

cải tiến thì cải tiến luôn thành cái này cho nhanh =))
http://vi.wikipedia.org/wiki/Kiểm_tra_Miller-Rabin

 

[lamdetien36]

Sao lại xóa bài của anh thienvamai :| Bàì post về phép thử Rabin-Miller mà sao lại xóa :|
Box Học lập trình đúng là chỉ có dân trong ngành mới làm Mod được :|

 

[binhbongut]

Mình nghĩ rằng bài này còn thiếu trường hợp đặc biệt nếu:
N = 1 => thông báo N không phải là số nguyên tố. Với thuật toán trên 1 mod i = 1 => d luôn nhận giá trị 0 => thông báo "N là số nguyên tố" => Sai
N = 2 => thông báo N là số nguyên tố vì 2 là số nguyên tố chẵn và đặc biệt (chia hết cho 2).
Với thuật toán trên khi N = 2 sẽ thỏa mãn điều kiện 2 mode 2 = 0 => d = 0 + 1 = 1 => thông báo "N không phải SNT" => Sai.
Vậy theo mình nên thêm 1 câu lệnh sau dòng lệnh nhập N như sau:
if (N = 1) then write ('N khong phai SNT')
else if (N = 2) then write ('N la so SNT')
else
begin
d := 0;
.
.
.
write('N Khong Phai SNT');
end;
readln;
END

 

[binhbongut]

Mình nghĩ rằng bài này còn thiếu một số trường hợp đặc biệt nếu:
N = 1 => thông báo N không phải là số nguyên tố. Với thuật toán trên 1 mod i = 1 => d luôn nhận giá trị 0 => thông báo "N là số nguyên tố" => Sai
N = 2 => thông báo N là số nguyên tố vì 2 là số nguyên tố chẵn và đặc biệt (chia hết cho 2).
Với thuật toán trên khi N = 2 sẽ thỏa mãn điều kiện 2 mode 2 = 0 => d = 0 + 1 = 1 => thông báo "N không phải SNT" => Sai.
Vậy theo mình nên thêm 1 câu lệnh sau dòng lệnh nhập N như sau:
if (N = 1) then write ('N khong phai SNT')
else if (N = 2) then write ('N la so SNT')
else
begin
d := 0;
.
.
.
write('N Khong Phai SNT');
end;
readln;
END

 

[lamdetien36]

Mình nghĩ rằng bài này còn thiếu trường hợp đặc biệt nếu:
N = 1 => thông báo N không phải là số nguyên tố. Với thuật toán trên 1 mod i = 1 => d luôn nhận giá trị 0 => thông báo "N là số nguyên tố" => Sai
N = 2 => thông báo N là số nguyên tố vì 2 là số nguyên tố chẵn và đặc biệt (chia hết cho 2).
Với thuật toán trên khi N = 2 sẽ thỏa mãn điều kiện 2 mode 2 = 0 => d = 0 + 1 = 1 => thông báo "N không phải SNT" => Sai.
Vậy theo mình nên thêm 1 câu lệnh sau dòng lệnh nhập N như sau:
if (N = 1) then write ('N khong phai SNT')
else if (N = 2) then write ('N la so SNT')
else
begin
d := 0;
.
.
.
write('N Khong Phai SNT');
end;
readln;
END

trunc(sqrt(2)) = 1
for i := 2 to trunc(sqrt(2)) do không được thực hiện
d = 0
2 là SNT
P/s: đọc kỹ rồi hãy nói :|

 

[binhbongut]

Đúng trường hợp N = 2 do mình ko đọc kỹ vòng FOR vì theo thói quen mình hay nghĩ là số sau sẽ tăng dần lên.
Tuy vậy như bạn đã giải thích thì trường hợp N = 1 và 0 cũng sẽ báo "N là số nguyên tố" vì d luôn = 0 => chương trình của bạn vẫn thiếu mất trường hợp N = 1 và 0 sẽ phải báo "N không phải là số nguyên tố".
Mình không có ý bắt bẻ chương trình mà chỉ muốn hỏi lại xem mình nghĩ như vậy có đúng không vì đó là một bài tập của con gái và cô sẽ chấm điểm, nếu thiếu trường hợp sẽ bị trừ điểm.
Dù sao cũng rất cảm ơn bạn thì đó là cũng là một chương trình tham khảo tốt. Có điều khi đưa chương trình cho con gái với lệnh trunc(sqrt(N)) thì con gái chưa học nên mình đã thay đổi thành N cho dễ hiểu chính vì thế mới phát sinh trường hợp N = 2.

 

[lamdetien36]

Đúng trường hợp N = 2 do mình ko đọc kỹ vòng FOR vì theo thói quen mình hay nghĩ là số sau sẽ tăng dần lên.
Tuy vậy như bạn đã giải thích thì trường hợp N = 1 và 0 cũng sẽ báo "N là số nguyên tố" vì d luôn = 0 => chương trình của bạn vẫn thiếu mất trường hợp N = 1 và 0 sẽ phải báo "N không phải là số nguyên tố".
Mình không có ý bắt bẻ chương trình mà chỉ muốn hỏi lại xem mình nghĩ như vậy có đúng không vì đó là một bài tập của con gái và cô sẽ chấm điểm, nếu thiếu trường hợp sẽ bị trừ điểm.
Dù sao cũng rất cảm ơn bạn thì đó là cũng là một chương trình tham khảo tốt. Có điều khi đưa chương trình cho con gái với lệnh trunc(sqrt(N)) thì con gái chưa học nên mình đã thay đổi thành N cho dễ hiểu chính vì thế mới phát sinh trường hợp N = 2.

N = 1 thôi vẫn chưa đủ Phải là N < 2 cơ Số âm thì cũng phải xét nữa
Dù sao cũng cảm ơn bạn, để mình sửa lại code

 

[binhbongut]

Hôm trước cô giáo có gọi một bạn khác lên bảng và mình thấy bài sửa của cô khá là hay, có thể bao gồm được tất cả các trường hợp mà không dài dòng và rất đơn giản, mình post lên bạn xem nhé.

var
N, i, d: integer;
begin
write('Nhap N: '); readln(N);
d := 0;
for i := 1 to N do
begin
if N mod i = 0 then d := d + 1;
end;
if (d = 2) then
write('N La SNT')
else
write('N Khong Phai La SNT');
readln
end.

Bạn thử xem trong thuật toán trên có gì bất cập không nhé. Cảm ơn bạn.

 

[rjnaloner]

đây là ý kiến riêng của mình
begin
write('N= ');readln(n);
kt:=true; {kt:boolean;}
for i:=2 to sqrt(n) {hoặc n-1} do
if n mod i=0 then kt:=false;
if (kt=false) or (n=1) or (n=0) then writeln(n,' khong la so nguyen to')
else writeln(n,' la so nguyen to');
readln ;
end.

 

[lamdetien36]

Hôm trước cô giáo có gọi một bạn khác lên bảng và mình thấy bài sửa của cô khá là hay, có thể bao gồm được tất cả các trường hợp mà không dài dòng và rất đơn giản, mình post lên bạn xem nhé.

var
N, i, d: integer;
begin
write('Nhap N: '); readln(N);
d := 0;
for i := 1 to N do
begin
if N mod i = 0 then d := d + 1;
end;
if (d = 2) then
write('N La SNT')
else
write('N Khong Phai La SNT');
readln
end.

Bạn thử xem trong thuật toán trên có gì bất cập không nhé. Cảm ơn bạn.

Hãy thử với N = 10^9 và cảm nhận

 

[lamdetien36]

đây là ý kiến riêng của mình
begin
write('N= ');readln(n);
kt:=true; {kt:boolean;}
for i:=2 to sqrt(n) {hoặc n-1} do
if n mod i=0 then kt:=false;
if (kt=false) or (n=1) or (n=0) then writeln(n,' khong la so nguyen to')
else writeln(n,' la so nguyen to');
readln ;
end.

N = -1 thì sao
for i:=2 to sqrt(n): báo lỗi, phải là trunc(sqrt(n)) hoặc round(sqrt(n))

 

[freid]

Cái thuật toán kiểm tra số nguyên tố có 4 cấp độ.
1. Đếm ước từ 1 đến số đó.
2. Đếm ước từ 2 đến phần nguyên của thương giữa số đó và hai.
3. Đếm ước từ 2 đến căn bậc hai của số đó.
4. Đếm chẵn lẻ. (đại khái thế)
Cái thứ 4 đòi hỏi kiến thức đại số. Còn ba cái kia không khó lắm