Sáng kiến kinh nghiệm THPT: Phương pháp giải các bài toán về Số nguyên tố trong ngôn ngữ lập trình C++

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:47

Thêm vào BST

Báo xấu

41
lượt xem 10
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích nghiên cứu sáng kiến "Phương pháp giải các bài toán về Số nguyên tố trong ngôn ngữ lập trình C++" nhằm tìm hiểu lí thuyết chung về số nguyên tố để bổ sung thêm một số kiến thức giúp cho việc cho việc giải quyết các bài toán trong phần này. Hướng cho học sinh phương pháp giải các bài toán cơ bản trên cơ sở đó giải quyết được các bài toán với những hình thức biến tướng của nó.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sáng kiến kinh nghiệm THPT: Phương pháp giải các bài toán về Số nguyên tố trong ngôn ngữ lập trình C++

SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN TRƯỜNG THPT NAM ĐÀN 1 SÁNG KIẾN KINH NGHIỆM “ÁP DỤNG PHƯƠNG PHÁP SÀNG ERATOSTHENE VÀO GIẢI CÁC BÀI TOÁN VỀ SỐ NGUYÊN TỐ TRONG NGÔN NGỮ LẬP TRÌNH C++” MÔN: TIN HỌC Tác giả: Bùi Thị Hồng Tổ: Tự nhiên 1 Điện thoại: 0396036370 Năm học: 2021-2022
MỤC LỤC TT Nội dung Trang PHẦN 1 PHẦN MỞ ĐẦU 3 1 Lý do chọn đề tài 3 2 Mục tiêu đề tài 3 3 Nhiệm vụ đề tài 4 4 Đối tượng và phương pháp nghiên cứu 4 5 Tính đổi mới và đóng góp của đề tài 4 PHẦN 2 NỘI DUNG NGHIÊN CỨU 6 1 Cơ sở lý luận 6 2 Thực trạng của vấn đề 6 3 Nội dung và giải pháp thực hiện 7 4 Các bài toán áp dụng 9 Bài toán 1: Liệt kê các số nguyên tố 9 Bài toán 2: Tìm số 11 Bài toán 3: Khóa số 14 Bài toán 4: Tìm số Fibonacci nguyên tố 16 Bài toán 5: Vòng số nguyên tố 18 Bài toán 6: Dãy số đặc biệt 20 Bài toán 7: Biểu diễn số 22 Bài toán 8: Dãy nguyên tố 25 Bài toán 9: Siêu nguyên tố 27 Bài toán 10: Phân tích thừa số nguyên tố 29 Bài toán 11: Số nguyên tố Mersen 31 Bài toán 12: Beauty 34 Bài toán 13: Số nguyên tố đối xứng 36 1
Bài toán 14: Dãy con tăng nguyên tố 39 5 Một số kết quả đạt được 41 6 Đóng góp của đề tài 44 PHẦN 3 KẾT LUẬN 45 1 Quá trình nghiên cứu 45 2 Ý nghĩa, tác dụng của đề tài 45 3 Kiến nghị đề xuất 45 TÀI TIỆU THAM KHẢO 46 2
PHẦN I. ĐẶT VẤN ĐỀ 1. Lý do chọn đề tài Khoa học luôn phát triển, công nghệ được cải tiến hàng ngày góp phần lớn thúc đẩy xã hội hiện đại hơn. Bởi vậy, Giáo dục cũng phải thay đổi nhằm đáp ứng được yêu cầu cấp thiết của xã hội. Trong thời đại thông tin bùng nổ ngày nay, việc lập được các chương trình tự hoạt động cho máy tính, máy gia dụng là cần thiết. Và để làm được việc đó cần có một quá trình nghiên cứu, học tập về ngôn ngữ lập trình lâu dài, qua đó nhà lập trình có thể chọn một ngôn ngữ lập trình thích hợp. Mọi thứ đều có điểm khởi đầu của nó, với học sinh việc học Pascal là bắt đầu cho việc tiếp cận ngôn ngữ lập trình bậc cao, qua đó giúp các em hình dung được sự ra đời, cấu tạo, hoạt động cũng như ích lợi của các chương trình hoạt động trong máy tính, các máy tự động. Tuy nhiên để phát huy tốt nhất tiềm năng, khả năng sáng tạo của mỗi cá nhân thì trong dạy học cần có một sự thay đổi, cải tiến trong giáo dục, đó là định hướng cho các em một ngôn ngữ lập trình mới. Hiện nay đã có rất nhiều ngôn ngữ lập trình được tạo ra nhằm phục vụ cho nhiều mục đích khác nhau. Những ngôn ngữ lập trình mới luôn đem lại đặc điểm, tính năng phù hợp cho các nhu cầu, vấn đề hiện đại. Nhưng trong đó vẫn có một ngôn ngữ lập trình đã xuất hiện từ lâu nhưng vẫn còn phát triển mạnh mẽ đến hiện nay đó là ngôn ngữ lập trình C++. C++ có một hiệu suất cao cùng khả năng tiêu tốn ít tài nguyên phần cứng khiến chương trình chạy nhanh hơn. Chính vì vậy tôi đã định hướng cho học sinh chuyển sang học ngôn ngữ này để lập trình giải các bài toán. Các bài toán về “Số nguyên tố” luôn để lại những vấn đề mới mẻ cho người đọc. Trong các bài toán hóc búa, thú vị hầu hết là bài toán về số nguyên tố. Từ trước công nguyên, Ơclít đã khẳng định số nguyên tố là phạm trù cơ bản của số học. Thực tế đã chứng minh, toán học dù phát triển đến đâu thì vai trò của số nguyên tố cũng không hề thay đổi. Nó vẫn là một vùng đất kì lạ dù bao năm qua đã có nhiều người thám hiểm. Do vậy không thể tránh khỏi hiện tượng các em học sinh lo sợ khi gặp các bài toán về số nguyên tố, đa phần các em không định hình được phương pháp giải. Đây cũng chính là lý do mà tôi chọn nghiên cứu đề tài: Phương pháp giải các bài toán về “Số nguyên tố ” trong ngôn ngữ lập trình C++. Tôi chỉ là một giáo viên mới chập chững bước vào công việc nghiên cứu khoa học, với rất ít tài liệu cùng với sự hiểu biết nhỏ bé của mình trong quá trình bồi dưỡng học sinh giỏi tỉnh mong rằng đề tài này sẽ không nhàm chán mà có thể hữu ích một phần nhỏ trong việc giải quyết các bài toán dể dàng, linh hoạt, đúng đắn hơn. 2. Mục tiêu đề tài + Với giáo viên:  Hỗ trợ giáo viên trong lập trình giải các bài toán về số nguyên tố một cách nhanh chóng và chính xác.  Phục vụ việc bồi dưỡng HSG. + Với học sinh. 3
 Học sinh thấy được sự liên kết giữa các môn học, thấy được ứng dụng của lý thuyết Toán học và ngôn ngữ lập trình trong Tin học vào thực tiễn. Học sinh được tiếp cận với tri thức trong nhiều lĩnh vực, đem lại nhiều điều mới mẻ và hứng thú hơn trong học tập.  Giúp ôn thi HSG.  Tìm hiểu lí thuyết chung về số nguyên tố để bổ sung thêm một số kiến thức giúp cho việc cho việc giải quyết các bài toán trong phần này. Hướng cho học sinh phương pháp giải các bài toán cơ bản trên cơ sở đó giải quyết được các bài toán với những hình thức biến tướng của nó. 3. Nhiệm vụ đề tài Giúp học sinh thấy được sự gần gũi giữa Toán học với Tin học lập trình, từ đó thấy được sự yêu thích cách tư duy logic của bộ môn này. Đề tài giới thiệu về phương pháp Sàng số nguyên tố và phát triển chuyên sâu vào chuyên đề này trong bồi dưỡng học sinh giỏi. 4. Đối tượng và Phương pháp nghiên cứu - Học sinh giỏi ở các trường THPT bước vào học môn Tin học lập trình, thi học sinh giỏi trường, từ đó phát triển làm tốt các bài toán trong các kỳ thi học sinh giỏi Tỉnh ở bậc trung học phổ thông. - Nghiên cứu, khảo sát thực trạng, nhu cầu của học sinh đối với môn học lập trình. - Nghiên cứu thực tiễn công tác tổ chức hoạt động dạy học trong nhà trường và các văn bản hướng dẫn thực hiện chương trình dạy học hiện nay. - Tìm hiểu tâm lý học lứa tuổi gắn liền với nhiệm vụ dạy học. - Tổ chức khảo sát: khảo sát đánh giá mức độ đáp ứng các yêu cầu hoạt động giáo dục. - Tham khảo ý kiến của các đồng nghiệp và cốt cán đầu ngành về lĩnh vực giáo dục và CNTT. Tham khảo các tài liệu về sáng kiến kinh nghiệm và một số tại liệu liên quan. - Tham khảo tài liệu, nghiên cứu các đề thi, các bài toán thiên về tư duy toán học cơ bản chuyển về bài toán lập trình,... - Có tham khảo các tài liệu về ngôn ngữ lập trình C++, một số đề thi HSG trường và tỉnh và tài lệu về sáng kiến kinh nghiệm. 5. Tính mới và đóng góp của đề tài Việc chuyển đổi từ ngôn ngữ lập trình Pascal sang ngôn ngữ lập trình C++ tại trường THPT nâng cao hiệu quả hoạt động giáo dục, đáp ứng các yêu cầu đổi mới giáo dục hiện nay nhằm đẩy mạnh ứng dụng CNTT vào hỗ trợ đổi mới nội dung, phương pháp dạy và học góp phần đổi mới căn bản và toàn diện đáp ứng yêu cầu của cuộc cách mạng Công nghiệp đưa Việt Nam trở thành quốc gia Công 4
nghiệp hóa, hiện đại hóa. Đề tài giới thiệu về phương pháp Sàng số nguyên tố, một thuật toán tìm số ngyên tố trong một khoảng nhất định, hướng học sịnh giải quyết các bài toán về số nguyên tố dể dàng, linh hoạt, đúng đắn và hiệu quả hơn. Đề tài đã được áp dụng ở trường THPT Nam Đàn 1 có những đóng góp sau: Giúp học sinh yêu thích môn học lập trình, nắm được phương pháp giải các bài toán cơ bản về số nguyên tố trên cơ sở đó giải quyết được các bài toán với những hình thức biến tướng của nó. Từ đó, giúp việc học trở nên đơn giản và hiệu quả hơn. Giúp giáo viên không chỉ nắm chắc kiến thức mình dạy mà còn không ngừng nâng cao năng lực CNTT. Phù hợp với tình hình thực tế hiện nay. 5
PHẦN II. NỘI DUNG NGHIÊN CỨU 1. Cơ sở lý luận. Khi tiếp cận với kiến thức lập trình của bộ môn tin học, vấn đề đầu tiên và quan trọng nhất là giáo viên phải truyền cho học sinh được niềm đam mê và dạy cho học sinh được cách tư duy logic. Các bài toán về “Số nguyên tố” luôn để lại những vấn đề mới mẻ cho học sinh. Trong chuyên đề này tôi muốn giới thiệu phương pháp Sàng Ơ-ra-tô-xten, đây là phương pháp tìm tất cả các số nguyên tố trong một giới hạn nào đó và phát triển chuyên sâu về chuyên đề này. Từ đó để vận dụng giải quyết các bài toán mở rộng và phức tạp hơn. 2. Thực trạng của vấn đề. Trường THPT Nam đàn 1 là ngôi trường ở vùng nông thôn nằm dưới chân đê dải Sông Lam nên đa số học sinh chưa có cơ hội, điều kiện tiếp xúc với công nghệ và máy tính. Vì vậy, tin học là một môn học tương đối lạ lẫm và khó đối với học sinh trường tôi. Đặc biệt là chương trình tin học lập trình, với các em học lập trình còn khó hơn học toán, lí, hóa, .. vì điều kiện cơ sở vật chất của trường còn nhiều khó khăn, học sinh chỉ học chính khóa trên lớp về nhà lại không có máy tính để thực hành. Điều này dẫn đến ý thức tự giác của học sinh chưa cao, đặc biệt là các em học để thi học sinh giỏi lại càng khó. Với đội tuyển học sinh giỏi, hầu hết các em đều chưa có bất kì kiến thức cơ bản nào liên quan đến lập trình, gia đình chưa có máy tính để các em thực hành. Vì vậy giáo viên dạy đội tuyển phải bắt đầu rèn luyện cho các em từ những câu lệnh cơ bản nhất. Trải qua quá trình dạy học và bồi dưỡng học sinh giỏi. Tôi đã đúc rút được kinh nghiệm khi giải quyết các bài toán phức tạp cần chia nhỏ bài toán đó ra thành các mô đun, mỗi mô đun là 1 chương trình con giải quyết 1 việc nào đó, đồng thời biết phân luồng các dạng bài toán tương ứng với các mảng để học sinh dễ giải quyết. Để đáp ứng được sự đổi mới trong thời đại 4.0 tôi đã định hướng cho học sinh chuyển sang ngôn ngữ lập trình C++ thay đổi cho ngôn ngữ lập trình truyền thống pascal. Cơ sở trên đã giúp tôi áp dụng đề tài: “Áp dụng phương pháp sàng Ơ-ra-tô-xten vào giải các bài toán về số nguyên tố trong lập trình C++ “ và chuyên sâu về chuyên đề này để giải các bài toán cơ bản, bài toán khó. Thực trạng việc bồi dưỡng học sinh giỏi bằng ngôn ngữ lập trình C++ trong các trường phổ thông tại Nam Đàn trong thời gian qua: Năm học 2020-2021 chúng tôi đã làm một cuộc điều tra nhỏ với 5 trường THPT trên địa bàn huyện Nam Đàn, tỉnh Nghệ An (THPT Nam Đàn I, THPT Nam Đàn 2, THPT Sào Nam, THPT Mai Hắc Đế và THPT Kim Liên) về thực trạng sử dụng ngôn ngữ lập trình C++ trong bồi giỏi và thi học sinh giỏi tỉnh, có kết quả như sau: Bảng thông số về việc sử dụng ngôn ngữ lập trình C++ trong bồi giỏi và thi học sinh giỏi tỉnh tại một số trường THPT trên địa bàn huyện Nam Đàn năm học 2020-2021. 6
TT Tên trường Học sinh thi C++ Học sinh thi Pascal 1 THPT Nam Đàn 1 1(100%) 0 2 THPT Nam Đàn 2 0 1(100%) 3 THPT Kim Liên 1(100%) 0 4 THPT Sào Nam 0 1(100%) 5 THPT Mai Hắc Đế 0 1(100%) Nhận xét: Các giáo viên chưa thực sự chú trọng việc đưa ngôn ngữ lập trình C++ thay thế cho ngôn ngữ truyền thống Pascal. Trong 5 trường THPT thì có 3 trường học sinh thi bằng ngôn ngữ lập trình Pascal chiếm 60%. 3. Nội dung và giải pháp thực hiện. Trước hết tôi đưa ra bài toán như sau: Bài toán 1. Viết chương trình nhập vào từ bàn phím số nguyên N (N>10), in ra màn hình các số nguyên tố trong khoảng từ 2 đến N. *Khái niệm số nguyên tố: Một số nguyên dương N là số nguyên tố nếu nó có đúng 2 ước số khác nhau là 1 và chính nó. Như vậy ta có thể giải bài toán 1 theo cách sau: C1: Viết một hàm kiểm tra số nguyên k có phải số nguyên tố không kt(k). Sau đó cho vòng for chạy i=2 đến N để kiểm tra số i là số nguyên tố và in ra. Để cải tiến cần giảm thiểu số các số cần kiểm tra. Thay vì kiểm tra các số i ta sẽ chỉ kiểm tra các số i có tính chất giống tính chất của số nguyên tố. **Tính chất số nguyên tố: Trừ số 2 và số 3 các số nguyên tố có dạng 6k  1 ( vì các số có dạng 6k  2 thì chia hết cho 2, 6k  3 thì chia hết cho 3). vậy bài toán 1 giải theo cách: C2: Sử dụng tính chất số nguyên tố. Phương pháp Sàng nguyên tố Sàng Ơ-ra-tô-xten (Eratosthene) Đây là phương pháp để tìm được tất cả các số nguyên tố trong một giới hạn nào đó. Nhà toán học cổ Hi Lạp Ơ-ra-tô-xten (thế kỉ III trước công nguyên) là người đấu tiên tìm ra cách làm này. Ông viết các số trên giấy cỏ sậy căng trên một cái khung rồi dùi thủng các hợp số được một vật tương tự như cái sàng: Các hợp số được sàng qua, các số nguyên tố được giữ lại. Bảng số nguyên tố này được gọi là sàng Ơ-ra-tô-xten. Ta làm như sau: Trước hết xóa số 1. 7
Giữ lại số 2 rồi xóa tất cả các bội của 2 mà lớn hơn 2. Giữ lại số 3 rồi xóa tất cả các bội của 3 mà lớn hơn 3. Giữ lại số 5 (số 4 đã bị xóa) rồi xóa tất cả các bội của 5 mà lớn hơn 5. Giữ lại số 7 (số 6 đã bị xóa) rồi xóa tất cả các bội của 7 mà lớn hơn 7. Các số 8, 9, 10, đã bị xóa. Không cần xóa tiếp các bội của các số lớn hơn 10 cũng kết luận được rằng không còn hợp số nào nữa. Thật vậy, giả sử n là một hợp số chia hết cho một số a lớn hơn 10 thì do n10 nên n phải chia hết cho một số b nhỏ hơn 10, do đó n đã bị xóa. Tôi đã áp dụng phương pháp sàng Ơ-ra-tô-xten vào để giải hệ thống các bài toán về số nguyên tố trong ngôn ngữ lập trình C++ Trong quá trình lập trình tôi kết hợp sử dụng Vector, dữ liệu kiểu tập hợp Set chương trình sẽ gọn hơn và hiệu quả hơn. Một số điểm nổi trội của vector: - Không cần phải khai báo kích thước của mảng ví dụ: int a[100] …, vì vecter có thể tự động nâng kích thước lên. - Khi thêm 1 phần tử vào vector đã đầy rồi, thì nó sẽ tự động tăng kích thước của nó lên để dành chỗ cho giá trị mới này. - Vector còn cho biết số lượng các phần tử lưu trong đó. - Dùng số phần tử âm vẫn được trong vecter ví dụ A[-6], a[-9], rất tiện trong cài đặt các giải thuật. Tập hợp Set trong C++ - Cấu trúc dữ liệu kiểu tập hợp (Set) dùng để lưu các phần tử cùng kiểu dữ liệu, trong đó các phần tử không được trùng nhau. Khi chèn mỗi phần tử vào trong Set, Set sẽ kiểm tra và chỉ thêm phần tử đó khi nó không có trong set. Các phần tử được thêm vào được sắp xếp theo thứ tự tăng dần. Do set chỉ chứa các phần tử không trùng nhau, nên ta có thể sử dụng cấu trúc dữ liệu này cho một số bài toán liên quan đến tập hợp như: Cho dãy gồm n phần tử. hãy đếm số phần tử khác nhau trong mảng… ***Thuật toán Sàng nguyên tố Eratosthenes Void sang() { bool f[n+1] ={0}; f[0]=1; f[1]=1; For(int i=2; i
Ta có mảng f, f[i]=0 nếu i là số nguyên tố và ngược lại i là hợp số. Thuật toán này chỉ có độ phức tạp là O(n), nên ta hoàn toàn có thể thực hiện với n=108. 4. Các bài toán áp dụng Bài toán 1: Viết chương trình liệt kê các số nguyên tố trong khoảng từ [2,N] Dữ liệu vào: từ tệp văn bản nguyento.inp. Chứa duy nhất chỉ số nguyên N (N>=10) Kết quả: Ghi vào tệp văn bản nguyento.out các số nguyên tố tìm được, mỗi số cách nhau ít nhất 1 kí tự trống. NGUYENTO.INP NGUYENTO.OUT 20 2 3 5 7 11 13 17 19 Ý tưởng: Dùng phương pháp sàng số nguyên tố. - Khởi tạo 1 mảng bool kích thước n+1, với giá trị các phần tử của mảng = 0 (giả sử tất cả các phần tử trong mảng bool là số nguyên tố). - Khởi tạo một vector: vt có giá trị int (lưu các phần tử là số nguyên tố). - Sàng các số từ 2n +Nếu (!F[i])=1 thì i là số nguyên tố ta đưa i vào vector: vt. Tạo vòng lặp j=2 đến i*j
Kết quả cuối cùng sau khi sàng: Các phần tử là số nguyên tố nằm trong vector: vt. Chương trình cụ thể như sau: #include using namespace std; typedef long long ll; void xl () { ifstream inp{"nguyento.inp"}; ofstream out{"nguyento.out"}; ll n; inp >>n; vector vt; bool f[n+1] ={0}; for(ll i=2; i
Test 1: n =100 Test 2: n=150 Bài toán 2: Tìm Số (Đề thi chọn học sinh giỏi tỉnh lớp 11 THPT năm học 2012-2013 tỉnh Quảng Bình). Cho số nguyên dương X, khi đảo ngược trật tự các chữ số của X ta sẽ thu được một số nguyên dương Y, Y được gọi là số đảo ngược của X. Ví dụ: X=613 thì Y=316 là số đảo ngược của X. 11
Số nguyên dương Y được gọi là số nguyên tố nếu nó chỉ có hai ước số là 1 và chính nó, số 1 không phải là số nguyên tố. Cho hai số nguyên dương P và Q (1
typedef long long ll; void xl() {ll p,q; ifstream inp{"TIMSO.INP"}; ofstream out{"TIMSO.OUT"}; inp >>p>>q; ll max=pow(10,(int(log10(q)+2))); bool f[max+1]={0}; f[0]=1; f[1]=0; for(int i=2; i
Bài toán 3. Khóa số Vườn quốc gia Xuân Sơn, tỉnh Phú Thọ nổi tiếng với vẻ đẹp hoang sơ tự nhiên, có hệ sinh thái phong phú và đa dạng. Du khách khi tới đây có thể tận mắt chiêm ngưỡng khu rừng chò trỉ đẹp nhất miền bắc cùng một số loài thực vật số lượng lớn như cây rau sắng, dẻ, mộc lan… Ngoài sức hấp dẫn của hệ động thực vật phong phú, Xuân Sơn còn có nhiều cảnh quan thiên nhiên kỳ thú thu hút khách du lịch như núi Voi, núi Ten và núi Cẩn. Cùng với các con suối như suối Lấp, suối Thang; với nhiều thác nước có độ cao trên 50m. Màu thác bạc hoà quyện với màu xanh của rừng già làm cho phong cảnh nơi đây vừa hùng vĩ vừa thơ mộng. Tại đây, các nhà khảo cổ học đã phát hiện ra một số kho báu bí mậtcủa được các vua Hùng xây dựng rất kiên cố và không thể phá bỏ. Họ cho rằng trong đó có thể là những khối tài sản về lịch sử và văn hóa rất có giá trị và họ tìm cách mở cánh cửa của những kho báu đó. Trên cửa mỗi kho báu có một bảng gồm 2 hàng, hàng 1 đã ghi sẵn số nguyên dương N (≤106), hàng 2 chứa 2 khoá số K1 và K2 như hình bên. Trong khi khảo sát, các nhà khảo cổ đã phát hiện một phiến đá có ghi cách để mở khoá như sau: cửa có bảng chứa số N sẽ tương ứng với K1 và K2 là: - Điều chỉnh khoá số K1 về số bằng số lượng ước nguyên tố của N; N - Điều chỉnh khoá số K2 về số bằng tổng các ước K1 K2 nguyên tố của N thì cánh cửa sẽ tự động mở ra và nhà khảo cổ có thể vào bên trong kho báu một cách dễ dàng. Ví dụ: Ở nhà kho trên cửa ghi số N=12, có các ước của N là 1, 2, 3, 4, 6, 12 chỉ có 2 ước nguyên tố là 2 và 3 nên K1=2 và K2=5. Dữ liệu: vào từ filevăn bản PASS.INPchứa duy nhất một số nguyên dương N; Kết quả: Ghi ra filevăn bản PASS.OUT hai số nguyên K1 và K2. Ví dụ: PASS.INP PASS.OUT 12 2 5 14
Ràng buộc: • Có 30% số các test ứng với 30% số điểm của bài có 𝑁 ≤ 1000; • Có 40% số test khác ứng với 40% số điểm của bài có 𝑁 ≤ 104; • Có 30% số test còn lại ứng với 30% số điểm của bài có 𝑁 ≤ 106. Ý tưởng: Dùng phương pháp sàng ngyên tố + Sàng các số nguyên tố nhỏ hơn hoặc bằng N. Đếm số lượng số nguyên tố và tính tổng các số nguyên tố đó. Chương trình cụ thể như sau: #include using namespace std; void sang() {ifstream inp{"PASS.INP"}; ofstream out{"PASS.OUT"}; int n; inp >>n; bool f[n+1]={0}; int t=0, d=0; f[0]=1; f[1]=1; for(int i=2; i
Bài toán 4: Tìm số Fibonacci nguyên tố Dãy số Fibonacci là dãy được xác định như sau: f0=0, f1=1 và fn= fn-1+ fn-2 với n=2,3…. Em hãy tìm số Fibonacci lớn nhất là số nguyên tố và nhỏ hơn số M cho trước. Dữ liệu vào: Từ file văn bản Fibonacci.inp là một số nguyên dương M (2
typedef long long ll; const ll MAX = 1e9; bool F[MAX]={0}; void sangnt() { for(ll i = 2; i < MAX; i++) {if(!F[i]) for(ll j = 2; i*j < MAX; j++) F[i*j] = 1; } return ; } void xl() { ll m; ifstream inp{"fibonacci.inp"}; inp >> m; ll i1 = 0, i2= 1, cnt , i3 = 1; ofstream out{"fibonacci.out"}; sangnt(); out
Bài toán 5. Vòng số nguyên tố Một vòng tròn chứa 2*n vòng tròn nhỏ. Các vòng tròn nhỏ được đánh số từ 1 đến 2*n theo chiều kim đồng hồ. Cần điền các số tự nhiên từ 1 đến 2*n mỗi số vào một vòng tròn nhỏ sao cho tổng của hai số trên hai vòng tròn nhỏ liên tiếp là số nguyên tố. Số điền ở vòng tròn nhỏ 1 luôn là số 1. Dữ liệu vào: Từ File văn bản Vongtron.inp là một số nguyên dương n ( 1 < n < 10 ) . Dữ liệu ra: Ghi ra File văn bản vongtron.out dòng đầu tiên ghi ra số k là số cách tìm được. K dòng tiếp theo mỗi dòng ghi ra 1 cách điền các số vào các vòng tròn nhỏ. Cách điền nào có thứ tự từ điển nhỏ hơn thì xếp trước. Nếu K > 10000 thì chỉ cần ghi ra 10000 cách đầu tiên. Vongtron.inp Vongtron.out 4 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2 Ý tưởng: + Dùng phương pháp sàng nguyên tố 18
+ Áp dụng thuật toán quay lui để chọn các số, kiểm tra điều kiện dựa trên mảng sàng nguyên tố. Chương trình cụ thể như sau: #include using namespace std; const int MAX = 30; int N = 0; int total = 0; int a[MAX], check[MAX]; bool isEnough = false; string result = ""; int isPrime[2*MAX]; void sieve() { const int BOUND = (int)sqrt(2*MAX); for (int i = 2; i 10000) { --total; isEnough = true; return; } for (int i = 1; i