Lập trình hướng đối tượng - Chuyên đề dãy con

CHUYÊN ĐỀ DÃY CON. A. LÝ THUYẾT: - Dãy con là dãy các phần tử liên tục thuộc một dãy có trước (dãy mẹ) thỏa mãn một tính chất nào đó. - Để quản lí một dãy con cần một chỉ số (nơi bắt đầu dãy con) và độ dài của dãy. - Một cách quản lí khác là chỉ số đầu và chr số cuối. - Để xây dựng một dãy con cần: - Xây dựng giá trị ban đầu. - Duyệt qua các phần tử của dãy, Nếu: - Thỏa điều kiện, tăng độ dài thêm 1 ngược lại: - Nếu dãy con đang xét cần lưu thì: Lưu lại độ dài, chỉ số đầu dãy, Xác định lại độ dài, chỉ số đầu của dãy mới. - Nếu dãy con đang xét không cần lưu thì: Xác định lại độ dài, chỉ số đầu của dãy mới. - Để duyệt qua tất cả các dãy con của một dãy gồm n số ta dùng thuật toán vét cạn sau: For i:=1 to n-1 do For j:=i+1 to n do Xét dãy con bắt đầu từ vị trí thứ i có độ dài j B. BÀI TẬP: Bài tập 1: Cho dãy số gồm n số. Tìm dãy con lớn nhất các phần tử tăng (giảm) dần. VD :inp: 19 1 2 3 2 3 4 5 6 7 2 4 5 8 5 6 8 9 Out: 7 2 3 4 5 6 7 Giải thuật: Sử dụng kỹ thuật xây dựng dãy con. Sử dụng 2 vòng lặp while ...do... read(f,n); for i:=1 to n do read(f,a[i]); for i:=1 to n do write(g,a[i],' '); {in day vua doc ra man hinh} writeln(g); writeln; i:=1; vt:=1;d:=1;max:=1; while i<n do begin d:=1; {bat dau tu a[i]} while (i<n)and(a[i]<=a[i+1]) do {dem do dai day khong giam} begin i:=i+1; d:=d+1; end; if max<d then begin max:=d; vt:=i; end; i:=i+1; end; writeln(g,max); {in ra max la do dai cua day con lon nhat} for i:=vt-max+1 to vt do {in day dai nhat khong giam ra man hinh} begin write(g,a[i],' '); end; Bài toán trên có thể sử dụng giải thuật vét cạn dãy con để giải type km=array[1..100] of integer; var f,g:text; max,i,j,n,t,d,k:integer; b, a:km; function kt(d:km;x,y:integer):boolean; var i:integer; begin kt:=true; for i:=x to y-1 do if d[i]>d[i+1] then begin kt:=false; break; end; end; begin assign(f,'b1.inp');reset(f); assign(g,'b1.out');rewrite(g); readln(f,n); for i:=1 to n do read(f,a[i]); for i:=1 to n-1 do for j:=i+1 to n do if (kt(a,i,j)=true) and (j-i+1>max) then begin max:=j-i+1; d:=0; for k:=i to j do begin inc(d); b[d]:=a[k]; end; end; writeln(g,max); for i:=1 to d do write(g,b[i],' '); Bài tập 2: Cho dãy số gồm n số. Tìm dãy con lớn nhất các phần tử có cùng dấu, (đan dấu). Giải thuật: Thực hiện giống nhu bài 1, chỉ thay điều kiện là M[i+1]*M[i] >0 Bài tập 3: Cho dãy số nguyên (mỗi số không quá 15 chữ số ) .Trong dãy trên , xây dựng các dãy con gồm các số đứng liền nhau ( bản thân dãy cũng là 1 dãy con của nó ) .Hiện độ dài dãy con có tổng các phần tử lớn nhất, các phần tử dãy con. Giải thuật: - Sử dụng kỹ thuật vét cạn các dãy con, dùng hàm tính tổng dãy con để kiểm tra. Bài 4: Một dãy được gọi là đối xứng gương nếu các phần tử cách đều đầu và cuối thì bằng nhau . Cho dãy số A(N) . Hãy tìm một dãy con các phần tử liên tiếp nhau của dãy A(N) tạo thành một dãy đối xứng gương dài nhất . Bài 5: Dãy con biến động. Bài 6: Dãy con fibonaci. Bài 7: Dãy con cấp số cộng (A[i+1] - A[i] =d) Inp OUT 10 2 7 4 9 2 6 10 14 1 3 5 4 2 6 10 Bai 8.Cho 1 dãy N số nguyên dương. Dãy con tăng nguyên tố M phần tử là 1 dãy số có dạng Ai1 Ai2 Ai3 Aim Và thỏa điều kiện 1 <= i1 < i2 < i3 < < im <= n Ai1 <= Ai2 <= Ai3 <= <= Aim Ai là số nguyên tố (số nguyên tố là số chỉ có đúng 2 ước số là 1 và chính nó) Hãy tìm độ dài của dãy con tăng nguyên tố dài nhất Bài 9: Cho một dãy số nguyên dương a1,a2,...,aN (10 < N < 100), ai ≤ 10000 với mọi i=1..N và một số nguyên dương S (S < 100 000 000). Yêu cầu : Tìm độ dài nhỏ nhất của dãy con chứa các phần tử liên tiếp của dãy mà có tổng các phần tử lớn hơn hoặc bằng S. Dữ liệu vào: Đọc từ file BAI_1.IN gồm nhiều test, mỗi test chứa N và S ở dòng đầu. Dòng 2 chứa các phần tử của dãy. Dữ liệu ra: Kết quả ghi vào file BAI_1.OUT, mỗi test đưa một dòng chứa độ dài của dãy con tìm được. BAI_1.IN BAI_1.OUT 10 15 5 1 3 5 10 7 4 9 2 8 5 11 1 2 3 4 5 2 3