Đăng ký Đăng nhập
Trang chủ Các dạng bài về dãy con và hướng giải quyết...

Tài liệu Các dạng bài về dãy con và hướng giải quyết

.DOC
69
11348
185

Mô tả:

SỞ GD - ĐT NAM ĐỊNH TRƯỜNG THPT CHUYÊN LÊ HỒNG PHONG ™˜ SÁNG KIẾN DỰ THI CẤP TỈNH BÁO CÁO SÁNG KIẾN: CÁC DẠNG BÀI VỀ DÃY CON VÀ HƯỚNG GIẢI QUYẾT Tác giả: TRẦN THỊ THANH HUYỀN Trình độ chuyên môn: Thạc sỹ Tin học Chức vụ: Giáo viên Nơi công tác: Trường THPT chuyên Lê Hồng Phong Nam Định, 6/6-2015 Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ 1 1. Tên sáng kiến: CÁC DẠNG BÀI VỀ DÃY CON VÀ HƯỚNG GIẢI QUYẾT 2. Lĩnh vực áp dụng: Giảng dạy trong môn Tin cho học sinh khối chuyên Tin, đội tuyển HSG đồng bằng Bắc bộ khối 10, khối 11, bồi dưỡng đội tuyển HSG Quốc gia. 3. Thời gian áp dụng: - Từ năm 2012 đến nay 4. Tác giả: Họ tên : TRẦN THỊ THANH HUYỀN Ngày sinh: 09-10-1978 Nơi thường trú: 2/24/131 TRẦN THÁI TÔNG- TP NAM ĐỊNH Trình độ chuyên môn: Thạc sỹ Tin học Chức vụ công tác: Giảng dạy bộ môn Tin học Nơi làm việc: Trường THPT chuyên Lê Hồng Phong- Tp Nam Định Địa chỉ: 76 Vị Xuyên Điện thoại: 03503. 640.297 5. Đơn vị áp dụng sáng kiến Tên đơn vị: Trường THPT chuyên Lê Hồng Phong- Tp Nam Định Địa chỉ: 76 Vị Xuyên Điện thoại: 03503. 640.297 Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ 2 BÁO CÁO SÁNG KIẾN I. ĐIỀU KIỆN HOÀN CẢNH TẠO RA SÁNG KIẾN Một công việc quen thuộc của giáo viên khi giảng dạy Tin trong các lớp chuyên đó là: bên cạnh việc thường xuyên phải hệ thống lại các dạng bài tập, lựa chọn các dạng bài phù hợp để học sinh rèn kỹ năng cài đặt bài tập sau khi đã được trang bị về lý thuyết thì một mục tiêu tối quan trọng là phân loại và phát hiện năng khiếu về môn chuyên của học sinh. Trong quá trình khai thác các dạng bài tập để dạy học và tự nghiên cứu, tôi gặp phải rất nhiều dạng bài tập liên quan đến “dãy con” và nhận thấy chúng rất đa dạng và ở nhiều mức độ khác nhau: từ dễ đến khó. Để giải quyết các bài toán về “dãy con” này có thể phải vận dụng linh hoạt các chiến lược thiết kế thuật toán như: quay lui - vét cạn, chặt nhị phân và đặc biệt là phương pháp quy hoạch động trên mảng một chiều, hai chiều được vận dụng rất nhiều để giải quyết. Đây cũng là những phương pháp thiết kế thuật toán mà học sinh chuyên cần phải được rèn luyện nhiều khi làm bài tập II. MÔ TẢ GIẢI PHÁP 1. Mô tả giải pháp trước khi tạo ra sáng kiến Trước đây, khi ôn tập cho học sinh chuyên Tin và dạy các đội tuyển, tôi đã đưa ra một số bài tập nói trong tài liệu này song đưa ra một cách riêng lẻ, không có hệ thống và theo từng chuyên đề thuật toán. Ví dụ: Đa số các bài về dãy con thường có cách giải bằng phương pháp Quy hoạch động nên chúng có trong phần ví dụ áp dụng của chuyên đề về Quy hoạch động. Tuy nhiên các bài toán về ”dãy con” rất đa dạng, nhiều thể loại, có thể có nhiều phương pháp giải khác nhau. Vì vậy, tôi thiết nghĩ: cần phải hệ thống hóa lại các bài tập liên quan đến xử lý “dãy con” và phân loại chúng thành các dạng cụ thể để qua đó học sinh có thể rút ra được phương pháp giải quyết phù hợp với từng dạng bài. 2.Mô tả giải pháp sau khi có sáng kiến Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ 3 Để góp phần giúp các em vận dụng linh hoạt và nhiều hơn nữa các phương pháp thiết kế thuật toán vào giải các bài tập cụ thể, phổ biến như các dạng bài tập về dãy con của học sinh chuyên tin cũng như góp phần xây dựng kho bài tập bồi dưỡng HSG các cấp, trong tài liệu này tôi xin được trình bày vấn đề “ Các dạng bài toán về dãy con và hướng giải quyết” NỘI DUNG A.Một số khái niệm Cho một dãy N số nguyên A=(A1, A2, …, AN) Ví dụ: A= (8 6 5 2 6 4 9) với N=7 + Dãy con của một dãy A cho trước là một dãy thu được bằng cách xóa đi một số phần tử của dãy A, các phần tử còn lại vẫn giữ đúng thứ tự. Mỗi dãy số là dãy con của chính nó. Dãy rỗng là dãy con của mọi dãy bất kỳ. Ví dụ: Dãy ( 6 5 4 9) là dãy con của A + Đoạn con (dãy đoạn con) của một dãy A cho trước là một dãy các phần tử liên tiếp có trong A Ví dụ: Dãy ( 6 5 2 6 ) là đoạn con của A * Các kiến thức cần trang bị: - Các thuật toán cơ bản: Tìm ước chung của 2 số, kiểm tra tính nguyên tố của một số nguyên dương, kiểm tra tính nguyên tố cùng nhau của một cặp số, kiểm tra một số thuộc dãy số Fibonacci,… - Các thuật toán nâng cao: tìm kiếm nhị phân, sắp xếp nhanh, trộn mảng, thuật toán sinh hoán vị, thuật toán loang, xử lý bit. - Các phương pháp thiết kế thuật toán: duyệt-vét cạn, quay lui, quy hoạch động. B. Các dạng bài tập Dạng 1: Dãy con tăng dần (giảm dần) dài nhất (ngắn nhất) Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ 4 Bài 1. Đoạn con tăng dần dài nhất Cho dãy gồm N số nguyên. Tìm đoạn con tăng dần có chiều dài lớn nhất. Dữ liệu vào: tệp văn bản DAYCON.INP Dòng thứ nhất: số tự nhiên N, 1  N  20000. Từ dòng thứ hai trở đi: các phần tử của dãy. Dữ liệu ra: tệp văn bản DAYCON.OUT DAYCON.INP DAYCON.OUT Chứa một dòng duy nhất gồm hai số tự nhiên 12 47 d – chỉ số đầu đoạn và L – số phần tử trong 15513 đoạn (chiều dài đoạn). 33579 Trong các tệp, dữ liệu trên cùng dòng cách 12 nhau qua dấu cách. Giải thích : Đó là dãy con 1 3 3 3 5 7 9 Thuật toán - Ta đọc dần các phần tử từ input file và so sánh hai phần tử liên tiếp nhau là x (phần tử đọc trước tại bước i) và y (phần tử đọc sau tại bước i+1). - Nếu y < x thì coi như kết thúc một đoạn không giảm, ta cập nhật để ghi nhận lại đoạn không giảm dài nhất. Độ phức tạp: cỡ O(N). Chương trình program DAYCON; uses crt; const fn = 'DAYCON.INP'; gn = 'DAYCON.OUT'; var f,g: text; n: longint; a: mw1; iLeft, imax: longint; MaxLen: longint; procedure Update(i: longint); begin Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ 5 if (MaxLen < i - iLeft) then begin MaxLen := i - iLeft; imax := iLeft; ileft := i; end; iLeft := i; end; procedure XuLi; var i, x, y: longint; begin assign(f,fn); reset(f); readln(f,n); read(f,x); iLeft := 1; MaxLen := 0; for i := 2 to n do begin read(f,y); if (y < x) then Update(i); x := y; end; Update(n+1); close(f); end; procedure Ghi; begin assign(g,gn); rewrite(g); writeln(g,imax,’ ‘,MaxLen); close(g); end; BEGIN XuLi; ghi; END. Bài 2. Đoạn đơn điệu dài nhất Cho dãy gồm N số nguyên. Tìm đoạn đơn điệu (không giảm hoặc không tăng) có chiều dài lớn nhất. Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ 6 Dữ liệu vào: tệp DONDIEU.INP Dòng thứ nhất: số tự nhiên N, 1N 20000. Từ dòng thứ hai trở đi: các phần tử của dãy. Dữ liệu ra:tệp văn bản DONDIEU.OUT DONDIEU.INP Chứa một dòng duy nhất gồm hai số tự nhiên d là chỉ số đầu đoạn và L là số 12 phần tử trong đoạn (chiều dài đoạn). 155133357912 DONDIEU.OUT 47 Thuật toán Nhận xét: Đoạn có 1 phần tử là đoạn đơn điệu (tăng, giảm), Đoạn gồm một dãy liên tiếp các phần tử bằng nhau là đoạn đơn điệu (tăng, giảm). Ta dùng hai biến đếm các phần tử tăng hoặc bằng nhau liên tiếp: dt và đếm các phần tử giảm hoặc bằng nhau liên tiếp: dg. - Nếu ai = ai 1 ta tăng đồng thời dt và dg 1 đơn vị. Nếu a i > ai 1 ta tăng dt thêm 1 đơn vị và đặt lại dg = 1. - Nếu ai < ai 1 ta tăng dg thêm 1 đơn vị và chỉnh lại dt = 1. Sau mỗi bước ta cập nhật đoạn đơn điệu dài nhất tìm được. Độ phức tạp: cỡ O(N). Chương trình program DonDieu; uses crt; const fn = 'DONDIEU.INP'; gn = 'DONDIEU.OUT'; var f,g: text; n: longint; dt,dg: longint; iMax, MaxLen: longint; function Max(a,b,c: longint): longint; begin Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ 7 if (a < b) then a := b; if (a > c) then Max := a else Max := c; end; procedure XuLi; var i,m,x,y: longint; begin assign(f,fn); reset(f); readln(f,n); read(f,x); dt := 1; dg := 1; MaxLen := 1; iMax := 1; for i := 2 to n do begin read(f,y); if (y = x) then begin dt := dt + 1; dg := dg + 1; end else if (y > x) then begin dt := dt + 1; else begin dg := 1; end dg := dg + 1; dt := 1; end; MaxLen := m; iMax := i - MaxLen + 1; end; m := Max(MaxLen, dt, dg); if (m > MaxLen) then begin x := y; end; close(f); end; procedure Ghi; begin assign(g,gn); rewrite(g); writeln(g, iMax,’ ‘, MaxLen); close(g); end; BEGIN XuLi; Ghi; END. Bài 3. Chuỗi ốc Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ 8 Biển Đà Nẵng được nhiều du khách biết đến như một trong những điểm nghỉ ngơi lý tưởng và được tạp chí Forbes (Mỹ) bình chọn là một trong những bãi biển đẹp nhất thế giới. Các bãi tắm có độ dốc lớn, nước trong xanh thích hợp cho những du khách muốn thưởng thức các loại hình dịch vụ giải trí nghỉ dưỡng, câu cá, lướt ván, lặn ngắm san hô, du thuyền,.. Trong một đợt đi du lịch ở Đà Nẵng, sáng sớm DONG3D thường đi dạo dọc bờ biển và nhặt những vỏ ốc rồi xâu chúng lại thành một chuỗi. Nguyên tắc tạo chuỗi ốc của DONG3D như sau: Ban đầu từ chuỗi rỗng, không có vỏ ốc; khi gặp một vỏ ốc mới, có thể lấy để xâu vào một trong hai đầu của chuỗi hoặc hoặc bỏ đi không lấy; cuối cùng nhận được một chuỗi vỏ ốc mà tính từ đầu chuỗi đến cuối chuỗi, các vỏ ốc có kích thước tăng dần và gồm càng nhiều vỏ ốc càng tốt. Yêu cầu: Cho trước dãy a1, a2,…, an là kích thước của các vỏ ốc mà DONG3D lần lượt gặp khi đi dọc bờ biển, hãy tìm cách nhặt và xâu chuỗi để được chuỗi gồm nhiều vỏ ốc nhất. BEADS.INP BEADS.OUT Dữ liệu: Vào từ file BEADS.INP 5 Dòng 1 chứa số nguyên dương N ≤ 105 44531 4 Dòng 2 chứa N số nguyên dương a1, a2,…, an (i: ai≤ 109) cách nhau bởi dấu cách. Kết quả: Ghi ra file BEADS.OUT một số nguyên duy nhất là số lượng vỏ ốc trong chuỗi tạo được. Thuật toán: - Tìm dãy con tăng dài nhất F[i] với i là phần tử đầu tiên - Tìm dãy con giảm dài nhất F2[i] với i là phần tử đầu tiên - Kết quả cần tìm của bài toán chính là max(F[i]+F2[i]-1); Chương trình: var fi,fo:text; f,a,b,f2:array[1..100000]of longint; i,n,max,tg,j:longint; procedure day1; begin Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ 9 f[n]:=1; for i:=n-1 downto 1 do begin max:=0; for j:=i+1 to n do if (maxa[i]) then max:=f[j]; f[i]:=max+1; end; end; procedure day2; begin f2[n]:=1; for i:=n-1 downto 1 do begin max:=0; for j:=i+1 to n do if (maxa[c[i]] then res:=max(res,l[c[i]]+f[v]) ; End ; //tron 2 doan da sap xep u:=x ; v:=m+1 ; for i :=x to y do Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ 12 if(v>y)or((v<=y)and(u<=m)and(a[c[u]])a[i-1]) then l[i] :=l[i-1]+1 ; End ; R[n] :=1 ; For i :=n-1 downto 1 do begin R[i] :=1 ; If (a[i]0 do begin Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ 13 Dec(ntest);enter ;solve ; Writeln(fo, res); end ; Close(fo) ; close(fi); End. Dạng 2 : Tổng, tích các phần tử của dãy con Bài 5. Tổng đoạn ngắn nhất Cho một dãy số nguyên a1, a2, a3, …, an. Tìm đoạn ngắn nhất các phần tử trong dãy thỏa ai + ai + 1 + ai + 2 + … + aj = k. Dữ liệu vào: tệp văn bản TDOAN.INP Dòng thứ nhất: hai số tự nhiên N và K, 1  N  2000. Từ dòng thứ hai trở đi: các phần tử của dãy. Dữ liệu ra: tệp văn bản TDOAN.OUT Chứa một dòng duy nhất gồm hai số tự nhiên d – chỉ số đầu đoạn và L – số phần tử trong đoạn (chiều dài đoạn). Nếu vô nghiệm thì ghi 0 0. Trong các tệp, dữ liệu trên cùng dòng cách nhau qua dấu cách. Thu Xét TDOAN.INP TDOAN.OUT 21 17 16 3 0 2 3 2 10 1 5 5 6 12 20 30 14 8 0 11 0 6 0 0 5 a[i..j] ật toán đoạn với tồng S = a[i] + a[i+1] + … + a[j], i  j. Ta cho đoạn này dịch dần sang phải và xét ba tình huống sau đây. + S = K: ta ghi nhận điểm đầu i và độ dài đoạn là ji+1. Nếu độ dài này nhỏ hơn độ dài LMin thì ta cập nhật lại các giá trị iMin và Lmin (thủ tục Update). Rồi tiếp tục xét đoạn con mới là a[i+1..j] . + S < K: Ta dịch từ j sang j+1, giữ nguyên đầu i (thủ tục Right). + S > K: Dịch từ i thành i+1 (thủ tục Left). Ta đặt phần tử a[n+1] = 0 làm lính canh. Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ 14 Chương trình: program TDoan; uses crt; const mn = 2001; fn = 'TDOAN.INP'; gn = 'TDOAN.OUT'; type mw1 = array[0..mn] of word; var f,g: text; n,k: word; a: mw1; iMin, LMin: word; iLeft,iRight: word; sum: word; procedure Doc; var i: word; begin assign(f,fn); reset(f); readln(f,n, k); for i := 1 to n do read(f,a[i]); close(f); end; procedure Left; begin sum := sum - a[iLeft]; iLeft := iLeft + 1; if (iLeft > iRight) then begin iRight := iLeft; sum := a[iLeft]; end; end; procedure Right; begin iRight := iRight + 1; sum := sum + a[iRight]; end; procedure Update; begin if (LMin > iRight - iLeft + 1) then begin iMin := iLeft; LMin := iRight - iLeft + 1; end; Left; Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ 15 end; procedure XuLi; begin iLeft := 1; iRight := iLeft; LMin := n + 1; sum := a[1]; repeat if (sum = k) then Update else if (sum < k) then Right else { sum > k } Left; until (iRight > n); if (LMin = n+1) then LMin := 0; end; procedure Ghi; begin assign(g,gn); rewrite(g); writeln(g,iMin,’ ‘,LMin); close(g); end; BEGIN Doc; XuLi; ghi; END. Bài 6. Dãy con dài nhất tổng chia hết cho k Cho một dãy số nguyên gồm N phần tử a 1 , a2, ..., aN và một số nguyên k. Giả thiết dãy cho luôn luôn tồn tại một dãy con có tổng các phần tử chia hết cho k. Yêu cầu : Hãy tìm dãy con có nhiều phần tử nhất có tổng các phần tử chia hết cho k. Dữ liệu vào: Ghi trong file text, tên file là CK.INP gồm 2 dòng: - Dòng đầu ghi 2 số nguyên N và k ( 0 2 -> 4 -> 5. Số điểm đạt được là 0 + 3 – 4 + 5 = 4. Thuật toán: - Sử dụng phương pháp Quy hoạch động. - Gọi F[i] là giá trị lớn nhất đạt được khi đến vị trí i. Khởi tạo: F[1]=max(0,a[1]); Ta có công thức tổng quát F[i]=max(F[i], F[i-j]+a[i]) với i:2 n, j: 1k - Kết quả là Max(F[i]) Chương trình uses math; var a,f:array[1..1000001] of longint; i,n,kq,j,k:longint; begin readln(n,k); for i:=1 to n do begin f[i]:=-10000; Trần Thị Thanh Huyền - GV Trường THPT chuyên Lê Hồng Phong NĐ 20
- Xem thêm -

Tài liệu liên quan