Tìm dãy con thỏa điều kiện trong pascal
Tìm dãy con thỏa điều kiện nào đó: Viết chương trình nhập vào mảng n số nguyên (n < 1000). Tìm dãy con đơn điệu giảm dài nhất (Dãy đơn điệu giảm là dãy chỉ gồm các phần tử giảm dần)
Dữ liệu vào file: day_con.inp | Dữ liệu ra file: day_con.out |
– Dòng 1: chứa số n- Dòng 2 chứa n số cách nhau ít nhất 1 khoảng trắng | Chứa dãy con dài nhất |
VD: n = 112 ; 7 ; 5 ; 8 ; 6 ; 4 ; 12 ; 8 ; 7 ; -4 ; 6 | Kết quả: 12 ; 8 ; 7 ; -4 |
Ý tưởng: Tìm tất cả các dãy đơn điệu giảm và chọn ra dãy dài nhất:[2] ; [7 ; 5 ] ; [8 ; 6 ; 4] ; [12 ; 8 ; 7 ; -4] ; [6] - Dùng 1 biến lưu vị trí đầu tiên của các dãy đơn điệu giảm- 1 biến đếm số phần tử của các dãy giảm- 1 biến lưu độ dài dãy giảm lớn nhất- 1 biến để đánh dấu vị trí đầu tiên của dãy dài nhất khi được chọn (biết vị trí đầu tiên và số phần tử sẽ biết được dãy từ đâu tới đâu) |
Chú ý: Bài toán có thể thay cách hỏi (tìm dãy giảm dài nhất, tìm dãy không tăng dài nhất, dãy các số âm (dương) dài nhất, …)
code 1
var i,l,j,k,luu,dem,max,n:integer; kt:boolean; a: array[1..100] of integer; f:text; begin assign(f,'day_con.inp'); reset(f); readln(f,n); for i:=1 to n do read(f,a[i] ); close(f); {------------------} max:=1;luu:=1; for i:=1 to n-1 do for j:=i+1 to n do begin dem:=j-i+1; kt:=true; for k:=i to j-1 do if a[k] <=a[k+1] then kt:=false; if kt and (max<dem) then begin max:=dem; luu:=i; end; end; {----Mo file de ghi----} assign(f,'day_con.out'); rewrite(f); for i:=luu to luu+max-1 do write(f,a[i] ,' '); close(f); end.
code 2
var i,l,j,k,p,luu,dem,max,n:integer; kt:boolean; a: array[1..100] of integer; f:text; begin assign(f,'day_con.inp'); reset(f); readln(f,n,k); for i:=1 to n do read(f,a[i] ); close(f); {------------------} max:=1;luu:=1; for i:=1 to n-1 do for j:=i+1 to n do begin dem:=j-i+1; kt:=true; for p:=i to j-1 do if ((a[p] mod k)<>0) or ((a[p+1] mod k)<>0) then kt:=false; if kt and (max<dem) then begin max:=dem; luu:=i; end; end; {----Mo file de ghi----} assign(f,'day_con.out'); rewrite(f); for i:=luu to luu+max-1 do write(f,a[i] ,' '); close(f); end.