Sáng kiến kinh nghiệm THPT: Lớp các bài toán cơ bản trên mảng một chiều lập trình bằng ngôn ngữ C++

Chia sẻ: Hương Hoa Cỏ Mới | Ngày: | Loại File: PDF | Số trang:81

Thêm vào BST

Báo xấu

61
lượt xem 10
download

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

Mục tiêu nghiên cứu của sáng kiến kinh nghiệm là nhận thấy ngôn ngữ lập trình C++ cung cấp nhiều thư viện nên rất tiện lợi trong quá trình lập trình giải các bài toán, đồng thời lớp các bài toán trên mảng 1 chiều cũng được vận dụng nhiều trong lập trình. Vì vậy, tôi viết đề tài này với mục đích: Thứ nhất, trao đổi cùng với các đồng nghiệp về việc vận dụng ngôn ngữ C++ trong việc lập trình. Thứ hai, là tài liệu cho giáo viên phục vụ giảng dạy, bồi dưỡng HSG.

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: Lớp các bài toán cơ bản trên mảng một chiều lập trình bằng ngôn ngữ C++

MỤC LỤC ĐẶT VẤN ĐỀ ....................................................................................................... 1 1. Lý do chọn đề tài........................................................................................... 2 2. Cấu trúc nội dung.......................................................................................... 2 3. Mục đích nghiên cứu..................................................................................... 2 4. Phương pháp nghiên cứu............................................................................... 3 5. Giới hạn phạm vi nghiên cứu của đề tài ........................................................ 3 NỘI DUNG............................................................................................................ 4 PHẦN 1. KIẾN THỨC VỀ MẢNG MỘT CHIỀU.............................................. 4 I. Khái niệm................................................................................................... 4 II. Cách khai báo .............................................................................................. 4 III. Cách truy nhập đến phần tử mảng .............................................................. 4 IV. Cách nhập/xuất mảng................................................................................. 5 V. Một số thuật toán cơ bản trên mảng một chiều ............................................ 5 PHẦN II. BÀI TẬP........................................................................................... 12 1. Bài tập chủ đề tìm giá trị nhỏ nhất, lớn nhất ............................................... 12 2. Bài tập chủ đề sắp xếp mảng ...................................................................... 17 3. Bài tập chủ tìm kiếm trên mảng.................................................................. 24 4. Bài tập chủ đề tìm đoạn con dài nhất của thỏa mãn điều kiện cho trước. .... 36 5. Bài tập chủ đề cắt mảng thành K đoạn thỏa mãn điều kiện cho trước ......... 42 KẾT QUẢ ÁP DỤNG.......................................................................................... 44 KẾT LUẬN.......................................................................................................... 44 TÀI LIỆU THAM KHẢO ................................................................................... 45 PHỤ LỤC: HƯỚNG DẪN VÀ CHƯƠNG TRÌNH MẪU ................................... 46 1. Bài tập chủ đề tìm giá trị nhỏ nhất, lớn nhất .................................................. 46 2. Bài tập chủ đề sắp xếp mảng ......................................................................... 53 3. Bài tập chủ đề tìm kiếm trên mảng ................................................................ 60 4. Bài tập chủ đề tìm đoạn con dài nhất thỏa mãn điều kiện cho trước. ............. 80 5. Bài tập chủ đề cắt mảng thành K đoạn thỏa mãn điều kiện cho trước ............ 89 1 ĐẶT VẤN ĐỀ
1. Lý do chọn đề tài Mảng 1 chiều là cấu trúc dữ liệu đầu tiên và cũng là cấu trúc dữ liệu đơn giản và phổ biến nhất. Mảng 1 chiều giúp giải quyết được nhiều lớp bài toán. Vì vậy, nó được sử dụng nhiều trong các kỳ thi học sinh giỏi Tin học. Với nhiều năm tham gia giảng dạy, bồi dưỡng học sinh giỏi và việc nghiên cứu các vấn đề về lập trình theo từng dạng bài tập từ cơ bản đến phức tạp của ngôn ngữ lập trình C++, các tài liệu về phương pháp giảng dạy phục vụ cho việc học tập, ôn thi học sinh giỏi của học sinh cũng như giảng dạy của giáo viên. Từ đó, tôi viết sáng kiến kinh nghiệm với đề tài “Lớp các bài toán cơ bản trên mảng một chiều lập trình bằng ngôn ngữ C++”. Với mong muốn phần nào giúp học sinh cũng như giáo viên có tài liệu tham khảo phục vụ cho việc học tập và giảng dạy. 2. Cấu trúc nội dung Phần 1. Kiến thức về Mảng 1 chiều 1. Khái niệm về mảng một chiều 2. Khai báo mảng 3. Truy nhập phần tử mảng 4. Nhập/xuất mảng 5. Một số thuật toán cơ bản trên mảng 1 chiều Phần 2. Bài tập 1. Tìm giá trị nhỏ nhất, giá trị lớn nhất 2. Sắp xếp trên mảng 3. Tìm kiếm trên mảng 4. Tìm đoạn con dài nhất thỏa mãn điều kiện cho trước 5. Cắt mảng thành K đoạn thỏa mãn điều kiện cho trước 3. Mục đích nghiên cứu Trong quá trình nghiên cứu và giảng dạy, tôi nhận thấy ngôn ngữ lập trình C++ cung cấp nhiều thư viện nên rất tiện lợi trong quá trình lập trình giải các bài toán, đồng thời lớp các bài toán trên mảng 1 chiều cũng được vận dụng nhiều trong lập trình. Vì vậy, tôi viết đề tài này với mục đích: - Thứ nhất, trao đổi cùng với các đồng nghiệp về việc vận dụng ngôn ngữ C++ trong việc lập trình. - Thứ hai, là tài liệu cho giáo viên phục vụ giảng dạy, bồi dưỡng HSG. 2 4. Phương pháp nghiên cứu. Kinh nghiệm bản thân, thảo luận, sưu tầm tài liệu, thử nghiệm thực tế, rút kinh nghiệm từ các tiết dạy trên lớp.
5. Giới hạn phạm vi nghiên cứu của đề tài Đề tài chủ yếu nghiên cứu hệ thống lớp các bài toán cơ bản trên mảng 1 chiều và lập trình bằng ngôn ngữ C++. Đề tài có khả năng áp dụng rộng rãi vào giảng dạy, bồi dưỡng học sinh giỏi Tin học cho giáo viên và học sinh THCS, THPT trên địa bàn toàn tỉnh Nghệ An. 3 NỘI DUNG Việc nắm vững lý thuyết về mảng một chiều và các bài toán cơ bản trên mảng
một chiều là điều rất quan trọng, đó là cơ sở để các em học sinh vận dụng và giải quyết các bài toán phức tạp và nâng cao. Sau đây, tôi xin trình bày các kiến thức và các bài tập cơ bản về mảng 1 chiều sử dụng ngôn ngữ lập trình C++ mà tôi đã tìm hiểu và vận dụng có hiệu quả trong quá trình giảng dạy. PHẦN 1. KIẾN THỨC VỀ MẢNG MỘT CHIỀU I. Khái niệm Mảng một chiều là dãy hữu hạn các phần tử có cùng kiểu dữ liệu. Khi nói đến mảng ta cần xác định được: - Kiểu dữ liệu của các phần tử mảng . - Số phần tử của mảng. II. Cách khai báo 1. Khai báo không có khởi tạo [Số phần tử]; Ví dụ: int a[5]; float b[10]; 2. Khai báo có khởi tạo [Số phần tử] = {dãy giá trị}; Hoặc: [ ] = {dãy giá trị} ; (Lưu ý: Trong trường hợp không khai báo số phần tử mảng thì mảng vừa đủ lớn để giữ các giá trị được khởi tạo) Trong đó: - Tên kiểu dữ liệu: là các kiểu dữ liệu cơ bản hoặc kiểu dữ liệu có cấu trúc. - Tên biến mảng: do người dùng đặt theo quy tắc đặt tên. - Số phần tử: kích thước mảng. Ví dụ: float x[5]={3,5,7,2,1}; int a[ ] = {0, 2, 4, 6, 8}; III. Cách truy nhập đến phần tử mảng [Chỉ số] Ví dụ: int a[5] 0 1 2 3 4 1 3 5 7 9 4 a[1] = 3; a[3]= 7; Lưu ý: - Mảng trong C++ được đánh số bắt đầu từ 0
- Khi khai báo mảng cần khai báo số phần tử thừa ra. IV. Cách nhập/xuất mảng 4.1. Nhập mảng Cách 1: Biết số phần tử của mảng cin>>n; for (int i = 1 ; i < n; i++) cin>>a[i]; Cách 2: Chưa biết số phần tử của mảng int x, n = 0; while (cin >> x) { n++; a[n] = x; } 4.2. Xuất mảng: for (int i=1 ; i
{ Min = min (Min, A[i]); Max = max (Max, A[i]) } Cout
Lấy giá trị của thành phần thứ (L+H) Div 2 gán vào biến X. - Cho i ban đầu là L. - Cho j ban đầu là H. - Lặp lại. ∙ Chừng nào còn A[i] < X thì tăng i. ∙ Chừng nào còn A[j] > X thì giảm j. ∙ ij + Sắp xếp đoạn từ A[L] đến A[j] + Sắp xếp đoạn từ A[i] đến A[H] Thuật toán 1. #include 2. using namespace std; 3. void quicksort(long a[],long l,long h) 4. { 5. long i=l,j=h,x=a[(l+h)/2]; 6. do 7. { 8. while (a[i]x) j--; 9. if(i
18. int main() 19. { 20. int n, i; int a[100000]; 21. cin>> a[i]; 22. quicksort(a,1,n); 23. for(long i=1;i
Cout
if(A[mid] == key) return mid; if(A[mid] > key) r = mid - 1; else l = mid + 1; } return 0; } b. Thuật toán toán tìm kiếm một phần tử có giá trị gần bằng x * Tìm kiếm phần tử lớn nhất nhưng nhỏ hơn hoặc bằng x int binarySearch(int A[], int key, int left, int right) { int mid, l=left, r=right; int kq=0; while(l
11 PHẦN II. BÀI TẬP 1. Bài tập chủ đề tìm giá trị nhỏ nhất, lớn nhất Bài 1: Cho dãy số gồm n phần tử a1, a2, ... , an. Tìm giá trị lớn nhất của biểu thức (aj - ai) với (1
Giải thích test ví dụ: Điểm cao nhất (thủ khoa) là 15. 12 Bài 3. Ngôi sao Một em bé khi rảnh rỗi ngồi xếp n ngôi sao (2
53 1 21534 1 3 13 Giải thích test đề bài: 3 số đầu tiên là 2 1 5 số nhỏ nhất là 1, 3 số tiếp theo 1 5 3 số nhỏ nhất là 1, 3 số cuối cùng là 5 3 4 số nhỏ nhất là 3. Bài 5. Đoạn con 9 5 Cho dãy số nguyên a1, a2,..., aN (|ai| < 10 , N < 10 ). Một tập hợp khác rỗng các số hạng liên tiếp {ai, ai+1,..., ak} (i ≤ k) gọi là một đoạn con của dãy đó. Với mỗi đoạn con ta tính tổng tất cả các số hạng của nó. Yêu cầu: Tìm giá trị lớn nhất trong số các tổng của các đoạn con của dãy đã cho. Dữ liệu: Vào từ file văn bản Subseq.inp Dòng đầu chứa số N, dòng thứ i trong N dòng tiếp theo chứa số ai. Kết quả: Ghi ra file văn bản Subseq.out Một số nguyên là giá trị tổng đoạn con lớn nhất tìm được. Ví dụ: Subseq.inp Subseq.out 7 8 1 -2 (Giải thích: đoạn con -1 tổng lớn nhất là: 4 4 – 1 + 5 = 8) -1 5 -2 (60% số test có N < 3000) Bài 6. Lập trình Trong cuộc thi lập trình có N bài thi giải đúng yêu cầu đặt ra. Ban tổ chức quyết định trao phần thưởng đặc biệt cho bài thi tốt nhất, đó là bài thi có thời gian chạy chương trình ít nhất. Cho biết bài thi thứ i (1< i < N) có thời gian chạy là một số
nguyên ai (tính theo đơn vị centisecond, 1centisecond = 1/100 giây). Yêu cầu: Hãy cho biết thời gian của bài thi được trao thưởng và có bao nhiêu bài thi được trao thưởng. Dữ liệu: Vào từ file văn bản Laptrinh.inp - Dòng 1 chứa số nguyên dương N (N < 100). - Dòng 2 chứa N số nguyên a1, ..., an (0 < ai < 100). 14 Kết quả: Ghi ra file văn bản Laptrinh.out - Dòng thứ nhất chứa một số nguyên là thời gian ít nhất tìm được - Dòng thứ hai chứa một số nguyên là số bài thi cùng đạt thời gian ít nhất. Ví dụ. Laptrinh.inp Laptrinh.out 5 8 10 8 12 8 11 2 Bài 7. Dãy số Cho dãy số nguyên a1, a2, …, an . với 9 5 ai ≤10 ,n ≤10 1. Tìm số nguyên tố lớn nhất của dãy 2. Số nào xuất hiện nhiều nhất trong dãy. Dữ liệu: Vào từ file văn bản Primemax.inp - Dòng đầu tiên là số n - Dòng thứ hai là n số nguyên mỗi số cách nhau bởi một dấu cách. Kết quả: Ghi ra file văn bản Primemax.inp - Dòng thứ nhất là số nguyên tố lớn nhất của dãy, nếu không có số nguyên tố thì in ra 0. - Dòng thứ hai là số xuất hiện nhiều nhất trong dãy, nếu có nhiều số có số lần xuất hiện bằng nhau thì in ra số đầu tiên. Ví dụ: Primemax.inp Primemax.out 16 0 0 0 0 0 1 1 1 1 -1 -1 -1 -1 4 4 4 4 0
4 5737 11873 5737 9269 7956 11873 Bài 8. Khoảng cách xa nhất Cho dãy số nguyên A kích thước N. Tìm khoảng cách xa nhất giữa hai phần tử bằng nhau trong A. Dữ liệu: Vào từ file văn bản Kcmax.inp Dòng đầu tiên chứa số nguyên T là số bộ dữ liệu kiểm tra. Mỗi bộ dữ liệu gồm: - Dòng đầu chứa số nguyên dương N là số phần tử của A. 15 - Dòng sau chứa N số nguyên cách nhau bởi dấu cách biểu diễn dãy A. Ràng buộc: 4 0 < T < 100; 0 < N < 10 4 0 < A[i] < 10 ; (0 < i < N) Kết quả: Ghi ra file văn bản Kcmax.out Gồm T dòng/ mỗi dòng chứa một số nguyên là kết quả bài toán. Ví dụ: Kcmax.inp Kcmax.out 2 5 6 10 112221 12 321214586742 Giải thích: Test 1: Hai phần tử a[1] và a[6] đều bằng 1 cách nhau xa nhất với khoảng cách bằng 5 Test 2: Hai phần tử a[2] và a[12] đều bằng 2 cách nhau xa nhất với khoảng cách bằng 10. Bài 9. Biểu thức nhân, cộng
Cho số nguyên dương , = 1. . , bạn phải đặt giữa số nguyên dương này 2 phép nhân và − 3 phép cộng sao cho kết quả biểu thức là lớn nhất. Ví dụ: với = 5 và dãy là 4, 7, 1, 5, 3 thì bạn có thể có các biểu thức: 4 + 7 * 1 + 5 * 3 4 * 7 *1 + 5 + 3 Chú ý: Không được thay đổi thứ tự xuất hiện của , = 1. . trong biểu thức thu được. Dữ liệu: Vào từ file văn bản Express.inp - Dòng 1 chứa số nguyên dương (4 ≤ ≤ 1.000) - N dòng tiếp theo, dòng thứ + 1 chứa số nguyên dương (1 ≤ ≤ 10.000, = 1. . ) Kết quả: Ghi ra file văn bản Express.out Ghi 1 số nguyên dương duy nhất là giá trị lớn nhất của biểu thức thu được. 16 Ví dụ: Express.inp Express.out Giải thích 5 44 Biểu thức thu được 4 là: 7 4 * 7 + 1 + 5*3 1 5 3 Bài 10. Minima Cho dãy số nguyên dương X= x1, x2, ..., xN. Hãy tìm số nguyên A sao cho biểu thức sau đây nhận giá trị nhỏ nhất: S =1 x A − +2 x A− + ...+ N xA−. Dữ liệu: Vào từ file văn bản minima.inp - Dòng đầu là số N(0 < N ≤ 50000). - Các dòng sau chứa N số nguyên dương mô tả dãy số X(0 ≤ xi ≤ 30000). Kết quả: Ghi ra file văn bản minima.out Gồm một dòng chứa số S tìm được.
Ví dụ: Minima.inp Minima.out 4 2 1223 2. Bài tập chủ đề sắp xếp mảng Bài 11. Khối hình chữ nhật Một viên gạch có dạng khối hộp chữ nhật với ba kích thước là a, b, c. Người ta muốn biết: có thể đưa viên gạch đó qua lỗ hổng hình chữ nhật có kích thước x, y hay không? Dữ liệu: Vào từ file văn bản Khoihcn.input Các số nguyên dương a, b, c, x và y. Kết quả: Ghi ra file văn bản Khoihcn.output Đưa ra chuỗi thông báo "CO", nếu có thể đưa viên gạch qua lỗ hổng; ngược lại, in ra chuỗi thông báo "KHONG". Ví dụ: 17 Khoihcn.input Khoihcn.output 74345 CO 54335 KHONG Bài 12. Khoảng cách Một du khách trúng một vé máy bay có thể bay đến bất kì thành phố nào trong nước, xuất phát từ thủ đô Hà Nội. Nhân dịp đó, người này muốn đi thêm các thành phố lân cận, nhưng vì lo lắng không đủ chi phí nên ông chỉ muốn tìm những thành phố gần nhau nhất . Tuy nhiên, hãng hàng không chỉ cho ông biết thông tin về khoảng cách giữa các thành phố so với thủ đô Hà Nội. Giả sử rằng tất cả các thành phố đề nằm trên một đường thẳng bắt đầu từ thủ đô Hà Nội, hãy giúp người này tìm ra khoảng cách ngắn nhất để có thể tính toán chi phí cho chuyến đi. Dữ liệu: Vào từ file văn bản Khoangcach.inp Dữ liệu của vào bao gồm một vài bộ test. Mỗi bộ test bao gồm:
6 Dòng đầu tiên là số lượng thành phố N (1
Ví dụ: Butmau.inp Butmau.out Butmau.inp Butmau.out 1733 1 7777 3 Bài 14. Vắt sữa bò Vào một buổi sáng nông dân John sắp một đàn bò gồm n con bò để vắt sữa. Ông dự kiến là vào sáng hôm đó, con bò thứ i có khả năng sẽ vắt được ai lít sữa. Tuy nhiên đàn bò của ông có đặc tính là cứ mỗi lần vắt sữa một con, những con còn lại trông thấy sợ quá nên sẽ bị giảm sản lượng mỗi con 01 lít sữa. Nếu vắt sữa con bò thứ nhất, n-1 con còn lại bị giảm sản lượng. Sau đó vắt sữa con bò thứ hai thì n-2 con còn lại bị giảm sản lượng.... Bạn hãy giúp nông dân John tính xem thứ tự vắt sữa bò như thế nào để số lượng sữa vắt được là nhiều nhất nhé. Dữ liệu: Vào từ file văn bản Milk.inp - Dòng thứ nhất là số nguyên n (1 ≤ n ≤ 100) là số lượng con bò. - Dòng thứ hai gồm n số nguyên a1, a2,..., an (1 ≤ ai ≤ 1000) là sản lượng sữa của các con bò. Kết quả: Ghi ra file văn bản Milk.out Là một số nguyên xác định số lít sữa nhiều nhất mà anh Bo có thể vắt được. Milk.inp Milk.out 4 10 4444 19 4 6 2143 Giải thích - Trong test 1: vắt sữa con bò 1 (được 4), lượng sữa còn lại là 3 3 3; vắt sữa con bò 2 (được 3), lượng sữa còn lại là 2 2, vắt sữa con bò 3 (được 2) và con bò 4 (được 1), tổng cộng 10. - Trong test 2: vắt sữa con bò 1 (được 2), lượng sữa còn lại là 0 3 2; vắt sữa con bò 3 (được 3) và vắt sữa con bò 4 (được 1) tổng cộng 6.
Bài 15. Cấp số cộng. Dãy cấp số cộng là một dãy tăng dần, trong đó số đứng sau hơn số đứng trước một giá trị d, d được gọi là công sai. Ví dụ: 1 4 7 10 là một dãy cấp số cộng 4 phần tử công sai là 3 2 6 10 14 18 là một dãy cấp số cộng 5 phần tử công sai là 4 3 5 7 10 không phải là dẫy cấp số cộng 4 phần tử vì 7 – 5 ≠ 10 – 7. Trong giờ kiểm tra Toán, Tý đã tìm được đáp án của một bài toán là 4 số tạo thành một cấp số cộng, theo yêu cầu của đề bài. Tèo ngồi bên cạnh, không chép được bài của Tý nên tìm cách chơi xỏ Tý. Lợi dụng lúc Tý không để ý Tèo dùng bút xóa xóa đi 4 số của Tý rồi viết lại 3 số nhưng không theo thứ tự ban đầu. Tý xem lại bài thấy bài mình mất 1 số nên đã nhờ bạn giúp Tý khôi phục lại số bị thiếu ban đầu. Dữ liệu: Vào từ file văn bản Capsocong.inp Gồm 3 số nguyên có giá trị tuyệt đối nhỏ hơn 1000, cả 3 số được viết trên 1 dòng. Dữ liệu vào luôn được đảm bảo có đáp án. Kết quả: Ghi ra file văn bản Capsocong.out Số còn lại bị thiếu trong cấp số cộng. Nếu có nhiều đáp án, hãy in ra số lớn nhất. Ví dụ: Capsocong.inp Capsocong.out 468 10 10 1 7 4 Giải thích: Test 1: có 2 kết quả là 2 và 10, nhưng đề bài yêu cầu đưa ra số lớn nhất nên kết quả là 10. 20 Bài 16. Biểu thức Một dãy gồm n số nguyên không âm a1, a2,…, an được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả (n-1) khoảng trắng. Người ta muốn đặt k dấu cộng và (n-1-k) dấu trừ vào (n-1) khoảng trắng đó để nhận được một biểu thức có giá trị lớn nhất. Ví dụ, với dãy gồm 5 số nguyên 28, 9, 5, 1, 69 và k = 2 thì cách đặt 28+9-5- 1+69 là biểu thức có giá trị lớn nhất. Yêu cầu: Cho dãy gồm n số nguyên không âm a1, a2,…, an và số nguyên dương k, hãy tìm cách đặt kdấu cộng và (n-1-k) dấu trừ vào (n-1) khoảng trắng để nhận được