skkn cấp tỉnh phương pháp giải một số bài toán số học bồi dưỡng học sinh giỏi tin học bằng ngôn ngữ c

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 (151.65 KB, 26 trang )

Trang 1<div class="page_container" data-page="1">

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HỐ

PHỊNG GIÁO DỤC VÀ ĐÀO TẠO NƠNG CỐNG

SÁNG KIẾN KINH NGHIỆM

PHƯƠNG PHÁP GIẢI MỘT SỐ BÀI TOÁN SỐ HỌC BỒI DƯỠNG HỌC SINH GIỎI TIN HỌC BẰNG NGÔN

NGỮ C++---

Người thực hiện: Lê Thị HoaChức vụ: Giáo viên

Đơn vị công tác: Trường THCS Trần PhúSKKN thuộc lĩnh mực (mơn): Tin học

NƠNG CỐNG, NĂM 2024

</div>Trang 2<div class="page_container" data-page="2">

1.4 Phương pháp nghiên cứu 2

2.1 Cơ sở lý luận của sáng kiến kinh nghiệm 2

2.2 Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm 3

2.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 đề

2.3.6 Xử lý bài toán với kiểu dữ diệu lớn 16

2.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

</div>Trang 3<div class="page_container" data-page="3">

1. MỞ ĐẦU

1.1. Lý do chọn đề tài

Tin học được hình thành và phát triển rất mạnh mẽ, đã trở thành mộtngành khoa học độc lập với các nội dung, mục tiêu, phương pháp nghiên cứuriêng và ngày càng có nhiều ứng dụng trong hầu hết các lĩnh vực hoạt động củaxã hội loài người. Mục tiêu của tin học là khai thác thơng tin có hiệu quả nhấtphục vụ mọi mặt hoạt động của con người. Do đó ở bất kỳ lĩnh vực nào cần xửlý thơng tin thì ở đó tin học đều có thể phát huy tác dụng. Trong ngành giáo dụchiện nay cũng là một ngành đã và đang đưa công nghệ thông tin vào ứng dụngtrong việc dạy và học.

Cấp trung học phổ thông là cấp học cuối cùng của giáo dục phổ thơng cótrách nhiệm hoàn thành vệc đào tạo tiếp thế hệ học sinh của nhà trường phổthông. Đây là cấp học vừa trực tiếp tạo nguồn cho bậc cao đẳng, đại học nóiriêng, vừa góp phần quan trọng vào việc đào tạo nguồn nhân lực phục vụ cơngnghiệp hóa, hiện đại hóa đất nước nói chung. Học sinh THCS là nguồn lao độngtrẻ 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ơntrong 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ó đammê 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ôngqua 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ọcsinh u thích lập trình tơi rút ra những kinh nghiệm sau: Tạo sự đam mê lậptrình, vận dụng các kiến thức đã học để giải các bài tốn thực tế, hình thành vàphát triển tư duy logic, 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 nhiều bài toán Tin học, việc vận dụng kiến thức số học giúp đưa rađược những thuật toán tối ưu hơn. Mặt khác, những bài toán Tin học có sự vậndụng kiến thức số học cơ bản, địi hỏi sự cài đặt khơng q phức tạp và các emcó nền tảng Tốn học tốt có thể dễ dàng suy luận được. Từ đó kích thích niềmu thích của các em trong việc lập trình. Các thuật toán số học trong tin học lànội dung kiến thức khá quan trọng và được sử dụng nhiều trong thiết kế thuậttốn. Tuy nhiên, trong q trình giảng dạy tơi thấy học sinh vẫn cịn khó khăntrong việc phân tích bài tốn để có thể áp dụng được thuật tốn và cài đặt giảibài tốn. Vì vậy tơi chọn đề tài này để giúp học sinh có được hệ thống kiến thứccơ bản về toán học để giúp các em dễ dàng hơn trong giải quyết các bài toán cụthể nhất là đối các bài toán về số học.

</div>Trang 4<div class="page_container" data-page="4">

Học sinh được bồi dưỡng thi học sinh giỏi không chỉ cần nắm vững kiếnthức trong sách giáo khoa mà cịn phải có khả năng tư duy tốt để giải quyết cácbài tốn khó. Việc dạy học khơng chỉ là truyền đạt kiến thức cho các em mà giáoviên cịn phải kích thích sự sáng tạo, niềm đam mê học hỏi và muốn tìm hiểu cáimới.

Trong quá trình dạy học sinh và đứng đội tuyển học sinh giỏi tơi thấy rằngnhiều bài tốn sẽ được giải quyết nhanh nếu chúng ta biết cách phân tích từ giảthiết bài tốn, 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ề “Phương pháp giải một số bài toán số học bồi dưỡng học sinh

giỏi Tin học bằng ngôn ngữ C++”

1.2. Mục đích nghiên cứu

Góp phần đổi mới phương pháp dạy học sinh giỏi mơn Tin học theo hướngphát huy tính tích cực, chủ động và sáng tạo của học sinh giúp học sinh tiếp thutri thức một cách có hiệu quả.

Góp phần gây hứng thú học tập mơn Tin học cho học sinh tham gia thi chọnhọc sinh giỏi, tránh việc học thụ động, học vẹt. Giúp học sinh lĩnh hội tri thứcmột cách khoa học, củng cố và khắc sâu kiến thức.

Đưa ra các thuật toán cơ bản liên quan để giải quyết bài toán số học. Tạo hệthống kiến thức mở cho học sinh tiếp cận và phát huy năng lực tư duy logic,sáng tạo.

1.3. Đối tượng nghiên cứu

Học sinh khối 8,9 và đội tuyển học sinh giỏi trường THCS Trần PhúNông Cống.

1.4. Phương pháp nghiên cứu

Phương pháp phân tích thuật tố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êninternet.

1. 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 Hội nghị Trung ương 8 khóa XI về đổi mới căn bản, toàn diệngiáo dục và đào tạo nêu rõ: “Tiếp tục đổi mới mạnh mẽ phương pháp dạy học vàhọc theo hướng hiện đại; phát huy tính tích cực, chủ động, sáng tạo và vận dụngkiến thức, kỹ năng của người học; khắc phục kiến thức truyền một chiều, ghinhớ máy móc. Tập trung dạy cách học, cách nghĩ, khuyến khích tự học, tạo cơsở để người học tự cập nhật và đổi mới tri thức, kỹ năng và phát triển năng lực.

</div>Trang 5<div class="page_container" data-page="5">

Chuyển từ học chủ yếu trên lớp sang tổ chức hình thức học tập đa dạng, chú ýhoạt động xã hội, ngoại khóa, nghiên cứu khoa học. Đẩy mạnh ứng dụng côngnghệ thông tin và truyền thông trong dạy và học”.

Quyết định 711/QĐ-TTg ngày 13/6/2012 của Thủ tướng Chính phủ chỉrõ: “Tiếp tục đổi mới phương pháp dạy học và đánh giá kết quả học tập, rènluyện theo hướng phát huy tính tích cực, tự giác, sáng tạo và năng lực tự học củangười học”

Luật Giáo dục số 38/2005/QH11, Điều 28 quy định: “Phương pháp giáodụ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ủa họcsinh; 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áptự 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”.

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ọccần thiết và phát triển năng lực trí tuệ chung như: phân tích, tổng hợp, trừutượng hố, khái qt hố… 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ó.

Tin học và tốn học có mối liên quan mật thiết với nhau, có ảnh hưởng rấtlớn đến mọi lĩnh vực của cuộc sống. Các bài toán tin nếu được thuật toán trên cơsở lý thuyết toán học vững chắc sẽ đem lại kết quả tốt hơn rất nhiều so với cácthuật tốn khác. Thực tế qua những năm tơi bồi dưỡng đội tuyển học sinh giỏiTin học bắt gặp rất nhiều bài tốn số học cần lập trình trên máy tính. Từ đó tơiđưa ra những phân tích, đánh giá để làm sáng tỏ cho mỗi vấn đề được đề cập tới.Với cách tiếp cận mở như vậy, hy vọng đề tài này sẽ giúp các em học sinh cóđược một hệ thống những kiến thức cần thiết, bổ ích và thiết thự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 công nghệ thông tin trong xã hội hiện nay ai cũng biếtnhư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 THCS Trần Phú tơi có một số thuậnlợi và khó khăn sau:

</div>Trang 6<div class="page_container" data-page="6">

- Được sự giúp đỡ, tạo điều kiện của tổ nhóm chun mơn Tốn – Tin.

* Học sinh:

Nhiều học sinh đã thấy được tiềm năng phát triển của ngành công nghệthông tin trong tương lai, qua đó có ý thức và định hướng về nghề cơng nghệthông tin.

2.3.1 . Ước chung lớn nhất, bội chung nhỏ nhất của 2 số nguyên dương

- Ước số chung lớn nhất (USCLN) của hai số được tính theo thuật tốn Euclid

int ucln(int a, int b) {

int tmp;while(b > 0) {

tmp = a % b;a = b;

b = tmp; }

return a;}

- Sử dụng hàm để tính ước số chung lớn nhất của hai số:

</div>Trang 7<div class="page_container" data-page="7">

_ _gcd(a,b)

- Bội số chung nhỏ nhất (BSCNN) của hai số được tính theo cơng thức:

int bcnn(a,b)

{return (a*b)/ucln(a,b);}

Bài tốn: Trực nhật

Ở một lớp học có n học sinh. Mỗi bạn đều phải trực nhật và cứ sau một số

y ngày nhất định bạn đó mới phải trực nhật lại. Biết rằng xuất phát điểm ban đầutất cả sẽ đều trực nhật vào ngày đầu tiên. Bạn hãy giúp lớp trưởng tính xem saubao nhiêu ngày thì tất cả các bạn mới lại cùng nhau trực nhật và khi đó mỗi bạnđã trực nhật bao nhiêu lần.

Dữ liệu vào đọc từ file tn.inp:

- Dòng đầu chứa số nguyên n (2≤ n<100)

- Dòng thứ hai chứa n số nguyên y. (1≤ y<100)

Dữ liệu ra ghi vào file tn.out:

- Dòng đâu tiên ghi ra số ngày mà tất cả cùng nhau trực nhật lại.

- Dòng thứ hai chứa n số là số lần một bạn đã trực nhật cho tới lúc tất cảcùng trực nhật.

Ví dụ:

32 3 4

126 4 3

long long gcd(long long a, long long b) { if (b == 0) return a;

else return gcd(b, a % b);}

int main(){

</div>Trang 8<div class="page_container" data-page="8">

freopen("tn.inp","r",stdin); freopen("tn.out","w",stdout); long long n;

cin >> n; long long a[n];

for (long long i = 0; i < n; i++) cin >> a[i]; long long bcnn = (a[0]*a[1])/gcd(a[0],a[1]); for (long long i = 2; i < n; i++)

{ bcnn = (bcnn * a[i]) / gcd(bcnn, a[i]);} cout << bcnn << endl;

for (long long i = 0; i < n; i++) cout << bcnn / a[i] << " "; return 0;

2.3.2. Kiểm tra tính nguyên tố của một số nguyên dương

Số nguyên tố là số nguyên dương chỉ có 2 ước khác nhau là 1 và chính nó.

Cách 1. Để 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 có tồn tại số nguyên k (2 ≤ k ≤ √N) sao cho k là ước của Nhay không? Nếu tồn tại số ngun k thì N khơng phải số nguyên tố ngược lại Nlà số nguyên tố.

bool kiem_tra(int n){

if (n < 2) return flase;

for(int i = 2; i <= sqrt(n); i++)if(n%i==0) return flase;

return true;}

Tuy nhiên ta thấy cách này khơng hiệu quả vì độ phức tạp cao.

Cách 2. Dùng thuật tốn sàng ngun tố

- Tìm ra số ngun tố i, sàng để loại bỏ tất cả các bội của i.- Dùng mảng đánh dấu p[i], chỉ số i của mảng bắt đầu từ 0. p[i]=0 nếu i không nguyên tố; p[i] =1 nếu i là nguyên tố

Ban đầu phủ mảng nhận giá trị là 1. Sau đó gán giá trị khởi tạo: p[0]=p[1]=0.- Cho i chạy từ 2 đến √N:

Nếu (i ngun tố) thì loại tồn bộ bội của i ra khỏi mảng p.

void sangngto(int n){ fill(p,p+n+1,1);

</div>Trang 9<div class="page_container" data-page="9">

Cách 3. Để tránh việc phải kiểm tra k có phải là số ngun 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:- Trừ 2 các số nguyên tố đều lẻ.

if (n==2 || n==3) return true;

if (n==1 || n%2==0 || n%3==0) return false;int k=-1;

while (k<=int(sqrt(n))) { k+=6;

if (n%k==0 || n% (k+2)==0) break;}

return k>int(sqrt(n));}

Bài toán 1. Tìm tất cả các số nguyên tố trong đoạn [1,N] với N≤107

Dữ liệu vào đọc từ file nto.inp:

- Một dòng đầu chứa số nguyên n

Dữ liệu ra ghi vào file nto.out:

- Một dòng ghi ra tất cả các số là số nguyên tố trong đoạn [1,N]

</div>Trang 10<div class="page_container" data-page="10">

Chương trình:

#include <bits/stdc++.h>#define N int(1e7+1)using namespace std;int p[N];

int n;

void sangngto(int n){ fill(p,p+n+1,1);

freopen("nto.inp","r",stdin); freopen("nto.out","w",stdout); cin>>n;

sangngto(n);

for (int i=2;i<=n;i++)

if(p[i]==1) cout<<i<<" "; return 0;

Bài toán 2. Phân tích một số thành tích ra các thừa số nguyên tố.

Theo định lý cơ bản của số học: Mọi số nguyên dương đều có thể biểu diễn

duy nhất thành tích của các số nguyên tố.

Mọi số tự nhiên N>1 đều có thể biễu diễn duy nhất dưới dạng chuẩn tắcN= p1k1× p2k 2× …× psks trong đó ki là số nguyên dương và pi là các số nguyên tốvới p1< p2<…<ps .

Yêu cầu: Cho một số nguyên dương N (2<N<109) hãy phân tích N thành tíchcác thừa số nguyên tố.

Dữ liệu vào đọc từ file phantich.inp:

- Một dòng đầu chứa số nguyên n

Dữ liệu ra ghi vào file phantich.out:

- Nhiều dòng, mỗi dòng ghi ra 2 số p và k cách nhau bởi dấu cách.

</div>Trang 11<div class="page_container" data-page="11">

Ví dụ:

Thuật tốn:

Dùng một mảng p[i] để lưu lũy thừa. Mảng này có giá trị các phần tử banđầu đều bằng 0. Cho i chạy từ 2 đến √N, nếu n chia hết cho i thì tăng p[i] lên 1.Khi in kiểm tra: Nếu p[i] >0 thì in i^p[i].

Chương trình

#include <bits/stdc++.h>#define N int(1e6)

using namespace std;int p[N];

if(p[i]>0) cout<<i<<"^"<<p[i]<<'\n'; if (x>1) cout<<x<<"^"<<"1";

int main()

{ freopen("phtich.inp","r",stdin); freopen("phtich.out","w",stdout); cin>>n;

phantich(n); return 0;}

2.3.3. Đếm số ước của n

Khi N được phân tích thành thừa số nguyên tố như sau:

N= p1k1× p2k 2× …× psks

</div>Trang 12<div class="page_container" data-page="12">

Ta có các kết luận sau:

Số các ước của N là: (k 1+1)×(k 2+1)×…×(ks+1)

Yêu cầu: Cho số nguyên dương n (n ≤ 107). Đếm số ước của n.

Dữ liệu vào đọc từ file demuoc.inp:

- Một dòng đầu chứa số nguyên n

Dữ liệu ra ghi vào file demuoc.out:

- Kết quả là số lượng các ước của n.

#define ll long longusing namespace std;int p[N];

for (int i=2;i<N;i++) if(p[i]>0) d=d*(p[i]+1); if(x>1) d=d*2;

cout<<d;}

int main()

{ freopen("demuoc.inp","r",stdin); freopen("demuoc.out","w",stdout); cin>>n;

phantich(n); return 0;}

2.3.4. Lý thuyết đồng dư

</div>Trang 13<div class="page_container" data-page="13">

(a + b) % m = (a % m + b % m) % m(a-b)%m = (a % m – b % m) % m(a*b)%m = ((a % m) * (b % m)) % m

(a/b)%m = (a * 1/b) % m = (a % m)*(1/b * m)

Bài tốn: Tìm chữ số cuối khác 0 của N!

u cầu: Em hãy viết chương trình tìm chữ số tận cùng khác 0 của n! (với

Dữ liệu vào đọc từ file chuso.inp:

Gồm có nhiều dịng liên tiếp nhau, trên mỗi dịng chứa một số ngunkhơng âm N.

Dữ liệu ra ghi vào file chuso.out:

Có số dịng bằng số dịng tương ứng với dữ liệu vào. Trên mỗi dòng ghichữ số khác khơng cuối cùng của n!.

Ví dụ:

chuso.inp chuso.out24

Thuật tốn:

Các chữ số cuối cùng bằng 0 của n giai thừa được sinh ra khi và chỉ khitrong khai triển ra thừa số ngun tố của tích trên có chứa các cặp thừa số 2 và5. Vậy thì trước hết ta đếm số lượng các thừa số 2, kí hiệu là d2 và số lượng cácthừa số 5, kí hiệu là d5.

Thí dụ, với n = 15 ta có dạng khai triển ra thừa số nguyên tố của n giai thừa nhưsau:

n! = 1.2.3.(2.2).5.(2.3).7.(2.2.2).9.(2.5).11. (2.2.3).13.(2.7).(3.5)

Do đó d2 = 11 và d5 = 3. Vậy ta có ba cặp 2.5 = 10 và số mũ dôi ra củathừa số 2 so với thừa số 5 sẽ là d2 – d5 = 11 – 3 = 8. Khi đó, kết quả sẽ là: chữsố cuối cùng khác 0 của 15! = chữ số cuối cùng của k.2d2-d5.Trong đó k là tíchcủa các thừa số cịn lại.

Dễ thấy với mọi n, ta ln có d2 > d5 vì cứ hai số liên tiếp thì có một sốchẵn (chia hết cho 2), còn năm số liên tiếp mới có một số chia hết cho 5.

Việc cịn lại là lấy tích k của các số cịn lại. Vì tích này khơng bao giờ tậncùng bằng 0 cho nên ta chỉ cần giữ lại một chữ số cuối cùng bằng cách lấy mod10.

</div>Trang 14<div class="page_container" data-page="14">

Để tính chữ số tận cùng của 2m với m = d2 – d5 > 0 ta để ý đến tính tuầnhồn của nó, cụ thể là ta chỉ cần tính chữ số tận cùng của 2(m % 4) với cáctrường hợp:

Lưu ý rằng sử dụng tính chất đồng dư (a.b) % m=((a % m).(b % m)) % mcho nên ta có thể lấy % ở các bước trung gian với số lần tùy ý.

Để tránh việc tràn số khi sử dụng các biến dung lượng nhỏ chúng ta có thể tăngthêm một phép tốn % nữa. Chẳng hạn, khi tích luỹ kết quả, thay vì viết

k = (k*c) % 10; ta nên viết k = (k*(c % 10)) % 10;

Chương trình:

#include <bits/stdc++.h>#define ll long long

using namespace std;ll n;

ll tim(ll n){

ll k =1, m =0;ll tim = k;

if (n <= 1) return 0;ll d = 0,x;

for (int i = 2;i<=n;i++){x = i;

while (x%2 == 0){m = m+1; x = x/ 2;}while (x%5== 0){m = m-1; x = x/5;}k = (k*(x%10)) %10;}

switch (m % 4)

</div>

skkn cấp tỉnh phương pháp giải một số bài toán số học bồi dưỡng học sinh giỏi tin học bằng ngôn ngữ c

<b>PHƯƠNG PHÁP GIẢI MỘT SỐ BÀI TOÁN SỐ HỌC BỒI DƯỠNG HỌC SINH GIỎI TIN HỌC BẰNG NGÔN</b>

<b>NGỮ C++--- </b>

Tài liệu liên quan

Tài liệu bạn tìm kiếm đã sẵn sàng tải về