Trắc nghiệm: Cho bài toán kiểm tra tính nguyên tố của một số nguyên dương N. Hãy xác định output của bài toán này?
A. N là số nguyên tố
B. N không là số nguyên tố
C. N là số nguyên tố hoặc N không là số nguyên tố
D. Tất cả các ý trên đều sai
Trả lời:
Đáp án đúng: C. Output của bài toán này là N là số nguyên tố hoặc N không là số nguyên tố.
Output là các thông tin cần tìm vì vậy bài toán kiểm tra tính nguyên tố của một số nguyên dương N, Output của bài toán này là N là số nguyên tố hoặc N không là số nguyên tố.
Cùng Top tài liệu mở rộng kiến thức về bài toán và thuật toán để hiểu rõ câu hỏi trên nhé!
– Là việc nào đó mà ta muốn máy tính thực hiện để từ thông tin đưa vào [Input] tìm được thông tin ra [Output].
+ Khi máy tính giải bài toán cần quan tâm đến 2 yếu tố:
– Input : Thông tin đã có.
– Output: thông tin cần tìm từ Input
– Ví dụ:
Xác định Input và Output của các bài toán sau:
Giải phương trình
ax2 + bx + c = 0 [a ≠ 0]
Input: Số nguyên a, b, c với a 0.
Output: Nghiệm của phương trình.
– Khái niệm: là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện các thao tác ấy, từ Input của bài toán ta nhận được Output cần tìm.
– Tác dụng của thuật toán: Dùng để giải một bài toán:
– Các tính chất của thuật toán:
+ Tính xác định: các bước giải phải rõ ràng không gây ra sự lẫn lộn hoặc nhập nhằng.
+ Tính dừng: Thuật toán phải dừng lại sau một số bước giải.
+ Tính đúng: Kết quả sau khi thực hiện thuật giải phải là kết quả đúng dựa theo một định nghĩa hoặc một kết quả cho trước.
+ Tính hiệu quả:
Phải sử dụng dung lượng bộ nhớ là nhỏ nhất.
Số phép toán ít nhất.
Thuật toán dễ hiểu không?
Dễ khai báo trên máy tính.
– Liệt kê các bước.
– Sơ đồ khối
– Các quy định khi biễu diễn thuật toán bằng sơ đồ khối :
Ví dụ 1 : Cho 3 số a, b, c bất kì. Tìm số lớn nhất trong ba số. Viết thuật toán dưới hai dạng.
Lời giải
* Xác định bài toán
Input: a, b, c
Output: Max[a,b,c].
– Ý tưởng:
– Cho max = a.
– Nếu b> max thì max = b
– Nếu c> max thì max = c
* Thuật toán
a. Cách liệt kê
B1: Nhập vào a, b, c.
B2: max := a.
B3: nếu max ai+1 thì tráo đổi ai và ai+1 cho nhau;
– Bước 8: Quay lại bước 5;
b. Sơ đồ khối
Bài toán: Kiểm tra tính nguyên tố của một số nguyên dương N?
2/ Thuật toán
b/ Cách sơ đồ khối
1/ Xác định bài toán
- Input: N là số nguyên dương;
- Output: "N là số nguyên tố" hoặc "N không là số nguyên tố".
a/ Cách liệt kê
B1. Nhập số nguyên dương N;
B2. Nếu N = 1 thì thông báo N không là số nguyên tố rồi kết thúc;
B3. Nếu N < 4 thì thông báo N là số nguyên tố rồi kết thúc;
B4. i := 2;
B5. Nếu i > [Căn bậc 2 của N] thì thông báo N là số nguyên tố rồi kết thúc;
B6. Nếu N chia hết cho i thì thông báo N không là số nguyên tố rồi kết thúc;
B7. i := i + 1 rồi quay lại bước 5.
Tính nguyên tố của một số nguyên và sử dụng tính nguyên tố để giải quyết một số bài toán
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây [116.42 KB, 19 trang ]
MỤC LỤC
TRANG
1. MỞ ĐẦU......................................................................................................2
1.1
1.2
1.3
1.4
Lý do chọn đề tài..............................................................................2
Mục đích nghiên cứu........................................................................2
Đối tượng nghiên cứu.......................................................................3
Phương pháp nghiên cứu..................................................................3
2. NỘI DUNG CỦA SÁNG KIẾN KINH NGHIỆM....................................3
1
2
3
Cơ sở lý luận của sáng kiến kinh nghiệm....................................................3
Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm...................3
Các sáng kiến kinh nghiệm hoặc các giải pháp đã sử dụng
để giải quyết vấn đề...................................................................................4
2.3.1 Kiểm tra tính nguyên tố của một số nguyên dương..…………….....4
2.3.2 Phân tích một số thành tích các thừa số nguyên tố ………..……….6
2.3.3 Một số ví dụ…………………………………………………………7
4
Hiệu quả của sáng kiến kinh nghiệm đối với hoạt động
giáo dục, với bản thân, đồng nghiệp và nhà trường...................................17
3. KẾT LUẬN, KIẾN NGHỊ..........................................................................17
1. Kết luận...................................................................................................17
2. Kiến nghị.................................................................................................17
1
1. MỞ ĐẦU
1.1 Lý do chọn đề tài:
Công nghệ thông tin của nước ta hiện nay đang rất phát triển đưa ra nhiều
triển vọng cho tất cả các ngành trong việc tin học hoá xã hội. Công nghệ tông tin
có ý nghĩa rất quan trọng đối với rất nhiều lĩnh vực của đời sống, máy tính hiện
nay cũng không còn xa lạ đối với mọi người. Trong ngành giáo dục hiện nay
cũng là một ngành đang đưa công nghệ thông tin vào ứng dụng trong việc dạy
và học.
Thực hiện Nghị quyết số 26/NQ-CP ngày 15/4/2015 của Chính phủ ban
hành Chương trình hành động thực hiện Nghị quyết số 36-NQ/TW ngày
01/7/2014 của Bộ Chính trị Ban Chấp hành Trung ương Đảng Cộng sản Việt
Nam về đẩy mạnh ứng dụng, phát triển công nghệ thông tin [CNTT] đáp ứng
yêu cầu phát triển bền vững và hội nhập quốc tế; thực hiện Quyết định số
1755/QĐ-TTg ngày 22/9/2010 của Thủ tướng Chính phủ phê duyệt Đề án “Đưa
Việt Nam sớm trở thành nước mạnh về công nghệ thông tin và truyền thông”;
thực hiện Chỉ thị số 16/CT-TTg ngày 04/5/2017 của Thủ tướng Chính phủ về
việc tăng cường năng lực tiếp cận cuộc Cách mạng công nghiệp lần thứ 4, Bộ
Giáo dục và Đào tạo hướng dẫn cơ chế đặc thù đào tạo các ngành thuộc lĩnh vực
CNTT trình độ đại học giai đoạn 2017-2020 để đáp ứng nhu cầu của thị trường
lao động và hội nhập quốc tế.
Học sinh THPT là nguồn lao động trẻ có thể sử dụng ngay sau khi tốt
nghiệp do vậy việc được tiếp cận công nghệ thông tin từ trong nhà trường phổ
thông sẽ giúp cho học sinh có thể tự tin hơn trong công việc. Việc đào tạo học
sinh có nền tảng lập trình cơ bản và có đam mê lập trình có vai trò quan trọng
trong sự phát triển sau này của các em. Thông qua việc dạy đội tuyển học sinh
giỏi, dạy những lớp mũi nhọn nhiều năm để học sinh yêu thích lập trình tôi rút ra
những kinh nghiệm sau:
+ Tạo sự đam mê lập trình và đọc sách.
+ Vận dụng các kiến thức đã học để giải các bài toán thực tế
+ Hình thành và phát triển tư duy logic
+ Hình thành các bước để giải quyết vấn đề nêu ra
+ Dạy học thông qua các chuyên đề độc lập hay liên hệ giữa toán học và
tin học để giải quyết các bài toán.
Trong quá trình dạy học sinh và đứng đội tuyển học sinh giỏi tôi thấy rằng
nhiều bài toán sẽ được giả quyết nhanh nếu chúng ta biết tính chất của các số và
áp dụng hợp lý. Với những lý do trên tôi chọn đề tài về “Tính nguyên tố của
một số nguyên và sử dụng tính nguyên tố để giải quyết một số bài toán”
1.2 Mục đích nghiên cứu.
Đưa ra tính nguyên tố của một số nguyên, các thuật toán cơ bản liên quan
đến số nguyên tố. Đưa ra một số bài toán có sử dụng tính nguyên tố của một số
nguyên để giải quyết. Qua các bài toán này giúp học sinh yêu thích việc tư duy
logic và thấy được sự kỳ diệu của các con số.
2
1.3 Đối tượng nghiên cứu.
Học sinh khối 11 và đội tuyển học sinh giỏi trường THPT Nông Cống 1.
1.4 Phương pháp nghiên cứu
Phương pháp phân tích thuật toán, kiểm tra đánh giá năng lực học sinh,
phát triển tư duy logic. Một số tài liệu tham khảo và tìm kiếm thông tin trên
internet.
2. Nội dung sáng kiến
2.1. Cơ sở lí luận của sáng kiến kinh nghiệm.
- Nghị quyết số 44/NQ-CP, ngày 09/6/2014 Ban hành chương trình hành
động của chính phủ thực hiện nghị quyết số 29-NQ/TW ngày 04/11/2013 Hội
nghị lần thứ 8 Ban chấp hành Trung ương khóa XI về đổi mới căn bản, toàn diện
giáo dục và đào tạo, đáp ứng yêu cầu công nghiệp hóa trong điều kiện kinh tế thị
trường định hướng xã hội chủ nghĩa và hội nhập quốc tế xác định “Đổi mới hình
thức, phương pháp thi, kiểm tra và đánh giá kết quả giáo dục theo hướng đánh
giá năng lực của người học; kết hợp đánh giá cả quá trình với đánh giá cuối kỳ
học, cuối năm học theo mô hình của các nước có nền giáo dục phát triển”.
- Luật Giáo dục số 38/2005/QH11, Điều 28 quy định: “Phương pháp giáo
dục phổ thông phải phát huy tính tích cực, tự giác, chủ động, sáng tạo cảu học
sinh; phù hợp với đặc điểm của từng lớp học, môn học; bồi dưỡng phương pháp
tự học, khả năng làm việc theo nhóm; rèn luyện kỹ năng kiến thức vào thực tiễn;
tác động đến tình cảm, đem lại niềm vui, hứng thú học tập cho học sinh”
+ Ngoài việc tạo điều kiện cho học sinh chiếm lĩnh những tri thức và kỷ
năng Tin học cần thiết, Tin học còn có tác dụng phát triển năng lực trí tuệ chung
như: phân tích, tổng hợp, trừu tượng hoá, khái quát hoá…rèn luyện những đức
tính, phẩm chất của người lao động mới. Học sinh sẽ thấy rõ hiệu quả mạnh mẽ
của công nghệ thông tin và nhận thức cần có.
2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm.
Sự quan trọng của CNTT trong xã hội hiện nay ai cũng biết nhưng để
được sự quan tâm của các em học sinh, phụ huynh, nhà trường là cả một khó
khăn.
Quá trình thực hiện đề tài tại trường THPT Nông Cống 1 tôi có một số
thuận lợi và khó khăn sau:
2.2.1. Thuận lợi:
* Nhà trường:
- Ban giám hiệu nhà trường luôn đạo điều kiện tốt nhất để giáo viên và
học sinh học tập.
- Nhà trường đã đầu tư một phòng thực hành tin với 24 máy tính xách tay
để cho các em đam mê lập trình và đội tuyển học sinh giỏi học tập.
- Được sự giúp đỡ, tạo điều kiện của tổ nhóm chuyên môn Toán – Tin.
3
* Học sinh:
Nhiều học sinh đã thấy được tiềm năng phát triển của ngành CNTT trong
tương lai, qua đó có ý thức và định hướng về nghề CNTT.
2.2.2. Khó khăn:
* Nhà trường:
Nhà trường đã tạo điều kiện tối đa nhưng vì nhiều lý do nên cơ sở vật chất
để có thể học tốt môn tin học chưa đáp ứng được nhu cầu của học sinh.
* Giáo viên:
Tài liệu của môn tin học trong nhà trường khá ít do đó gây khó khăn cho
việc nâng cao trình độ.
Đời sống giáo viên còn nhiều khó khăn nên việc tập trung tối đa cho môn
học cũng bị ảnh hưởng.
* Học sinh:
Lập trình có đặc trưng riêng so với các môn học khác nên sự tiếp cận của
học sinh khá khó khăn.
Nhiều học sinh yêu thích và đam mê lập trình nhưng điều kiện kinh tế gia
đình chưa đủ để các em có thể chuyên tâm học tập.
Tư tưởng học để thi đại học vẫn còn nặng trong học sinh nên thời gian
học dành cho sự đam mê môn tin học là không đủ.
2.3Các sáng kiến kinh nghiệm hoặc các giải pháp đã sử dụng để giải quyết vấn
đề.
Khái niệm số nguyên tố [prime number]: Số nguyên tố là số nguyên dương
chỉ chia hết cho 1 và chính nó. Từ đó suy ra số một không phải là một số nguyên
tố [có rất nhiều em mới học lập trình nhầm số 1 là số nguyên tố]. Một kết quả
khác cũng không kém quan trọng được rút ra đó là số 2 là số nguyên tố đầu tiên
[nhỏ nhất] và cũng là số số nguyên tố chẵn duy nhất.
2.3.1 Kiểm tra tính nguyên tố của số nguyên dương.
a. Kiểm tra tính nguyên tố của một số nguyên dương
Để kiểm tra một số nguyên dương N có là số nguyên tố hay không ta
kiểm tra xem N có tồn tại số nguyên k sao cho k là ước của N hay không? Nếu
tồn tại số nguyên k thì N không phải số nguyên tố ngược lại N là số nguyên tố.
Ta có thể tìm số k bằng cách lấy N chia cho các số từ 2 cho đến N-1. Nếu N
không phải số nguyên tố thì N có thể phân tách N= với vì nên . Do đó ta chỉ
cần kiểm tra k từ 2 đến mà không cần kiểm tra từ 2 đến N-1.
Ta có đoạn chương trình sau:
function ngto[n:longint]:boolean;
var k :longint;
begin
if n=1 then exit[false];
4
for k:=2 to trunc[sqrt[n]] do
if [n mod k=0] then exit[false]; exit[true];
end;
Hàm ngto[n] kiểm tra lần lượt các nguyên trong đoạn để giảm thiểu số cần
kiểm tra ta có nhận xét: Để kiểm tra số N là số nguyên tố hay không ta kiểm tra
xem có tồn tại số nguyên tố k [] mà k là ước của N. Nếu tồn tại k thì N không
phải số nguyên tố ngược lại thì N là số nguyên tố. Để tránh việc phải kiểm tra k
có phải là số nguyên tố hay không ta có thể dựa vào một trong hai tính chất đơn
giản của số nguyên tố sau:
1. Trừ 2 các số nguyên tố đều lẻ.
2. Trừ số 2, 3 các số nguyên tố có dạng
Do vậy kiểm tra số N có phải là số nguyên tố hay không ta chỉ cần kiểm tra
xem N có chia hết cho số 2, số 3 và các số có dạng trong khoảng
Ta có đoạn chương trình sau:
function ngto[n:longint]:boolean;
var k,sqrt_n:longint;
begin
if [n=2]or[n=3] then exit[true];
if [n=1] or [n mod 2=0] or [n mod 3=0] then exit[false];
sqrt_n:=trunc[sqrt[n]];
k:=-1;
repeat
inc[k,6];
if [n mod k=0]or[n mod [k+2]=0] then break;
until k>sqrt_n;
exit[k>sqrt_n];
end;
b. Liệt kê các số nguyên tố trong đoạn
Ta có thể dùng hàm ngto[n] để kiểm tra lần lượt các số trong đoạn
Đoạn chương trình:
For i := 2 to N do
If ngto[i] then write[i];
Cách này là cách đơn giản nhưng chạy chậm nên ta cải tiến bằng cách sử dụng
sàng nguyên tố. Cách làm được thực hiện như sau:
Trước tiên xóa số 1 ra khỏi tập số nguyên tố. Số tiếp theo là số 2 là số
nguyên tố ta xóa tất cả các số là bội của 2. Số đầu tiên sau số 2 không bị xóa là
số 3 ta lại xóa tất cả các số là bội của 3…thuật toán tiếp tục đến khi gặp số
nguyên tố lớn hơn thì dừng lại. Các số chưa bị xóa là các số nguyên tố.
Ta có đoạn chương trình sau:
Const max=10000;
Procedure sangngto[N:longint];
5
Var i,j: longint
A: array[1..max] of byte;
Begin
fillchar[a,sizeof[a],0];
for i:=2 to trunc[sqrt[N]] do
if a[i]=0 then
begin
j:=i*i;
while j1 đều có thể biễu diễn duy nhất dưới dạng
chuẩn tắc
trong đó ki là số nguyên dương và pi là các số nguyên tố với .
Ta có bài toán: Cho một số nguyên dương N [2