• Khung trình chiếu

Bài tập: Tìm dãy "Lồi/Lõm"

Các mã nguồn được viết bằng ngôn ngữ Pascal
Gửi hồi đáp
Ảnh đại diện người dùng
huynhbuutam
Nhà sáng lập
Nhà sáng lập
Các bài viết: 112
Đã gia nhập lúc: T3 31 Th8, 2021 22:04
Địa điểm: Trường THCS Châu Lăng
Tên thật: Huỳnh Bửu Tâm

Bài tập: Tìm dãy "Lồi/Lõm"

Bài viết bởi huynhbuutam »

Dãy các số nguyên a­1, a2, …, aN được gọi là dãy lồi nếu nó giảm dần từ a1 tới ai nào đó, rồi tăng dần tới aN. Ví dụ: dãy 10 5 4 2 -1 4 6 8 12 là dãy lồi.
Yêu cầu: Lập trình nhập vào một dãy số nguyên sau đó xóa bớt một số phần tử của dãy và giữ nguyên trình tự các phần tử còn lại để được dãy con lồi dài nhất.
Dữ liệu vào:
- Dòng đầu là số tự nhiên N (3 ≤ N ≤ 5000).
- Dòng tiếp theo là N số nguyên của dãy số (các số kiểu Integer), mỗi số cách nhau một kí tự trống.
Dữ liệu ra:
- Dòng đầu tiên ghi số phần tử của dãy con lồi dài nhất tìm được (Ghi số 0 nếu không tìm được).
- Trong trường hợp tìm được, dòng tiếp theo ghi dãy con lồi dài nhất vừa tìm được ở trên, mỗi số cách nhau một kí tự trống.
Chương trình ví dụ:

Mã: Chọn tất cả

Input:
10
1 2 3 4 2 5 1 2 3 4
Output:
6
4 2 1 2 3 4
Mã nguồn (Dãy lồi):

Mã: Chọn tất cả

Program DayLoi;
Var	N, max_i : Integer;
	max : LongInt;
	A, DT, LT, DG, LG : Array[0..5000] Of LongInt;

Procedure Nhap;
Var i : Integer;
Begin
	Readln(N);
	For i := 1 To N Do Read(A[i]);
	ReadLn;
End;

Procedure TimDayGiamXuoi;
Var i, j : Integer;
Begin
	DT[1] := 1;
	LT[1] := 0;
	For i := 2 To N Do Begin
		DT[i] := 1;
		LT[i] := 0;
		For j := i-1 DownTo 1 Do
			If (A[i] < A[j]) And (DT[i] < DT[j] + 1) Then Begin
				DT[i] := DT[j] + 1;
				LT[i] := j;
			End;
	End;
End;

Procedure TimDayGiamNguoc;
Var i, j : Integer;
Begin
	DG[N] := 1;
	LG[N] := 0;
	For i := N-1 DownTo 1 Do Begin
		DG[i] := 1;
		LG[i] := 0;
		For j := i + 1 To N Do
			If (A[i] < A[j]) And (DG[i]  < DG[j] + 1) Then Begin
				DG[i] := DG[j] + 1;
				LG[i] := j;
			End;
	End;
End;

Procedure XuLi;
var i : Integer;
Begin
	max := DT[i] + DG[i];
	For i := 2 To N Do
		If max < DT[i] + DG[i] Then Begin
			max := DT[i] + DG[i];
			max_i := i;
		End;

	i := max_i;
	While LT[i] <> 0 Do Begin
		DT[i] := DT[i] * (-1);
		i := LT[i];
	End;
	DT[i] := DT[i] * (-1);

	i := LG[max_i];
	While LG[i] <> 0 Do Begin
		DT[i] := DT[i] * (-1);
		i := LG[i];
	End;
	DT[i] := DT[i] * (-1);
End;

Procedure Xuat;
Var i : Integer;
Begin
	WriteLn(max-1);
	For i := 1 To N Do
		If DT[i] < 0 Then Write(A[i], ' ');
End;
Begin
	Nhap;
	TimDayGiamXuoi;
	TimDayGiamNguoc;
	XuLi;
	Xuat;
End.
Mã nguồn (Dãy lõm):

Mã: Chọn tất cả

Program DayLom;
Var	N, max_i : Integer;
	max : LongInt;
	A, DT, LT, DG, LG : Array[0..5000] Of LongInt;

Procedure Nhap;
Var i : Integer;
Begin
	Readln(N);
	For i := 1 To N Do Read(A[i]);
	ReadLn;
End;

Procedure TimDayTangXuoi;
Var i, j : Integer;
Begin
	DT[1] := 1;
	LT[1] := 0;
	For i := 2 To N Do Begin
		DT[i] := 1;
		LT[i] := 0;
		For j := i-1 DownTo 1 Do
			If (A[i] > A[j]) And (DT[i] < DT[j] + 1) Then Begin
				DT[i] := DT[j] + 1;
				LT[i] := j;
			End;
	End;
End;

Procedure TimDayTangNguoc;
Var i, j : Integer;
Begin
	DG[N] := 1;
	LG[N] := 0;
	For i := N-1 DownTo 1 Do Begin
		DG[i] := 1;
		LG[i] := 0;
		For j := i + 1 To N Do
			If (A[i] > A[j]) And (DG[i]  < DG[j] + 1) Then Begin
				DG[i] := DG[j] + 1;
				LG[i] := j;
			End;
	End;
End;

Procedure XuLi;
var i : Integer;
Begin
	max := DT[i] + DG[i];
	For i := 2 To N Do
		If max < DT[i] + DG[i] Then Begin
			max := DT[i] + DG[i];
			max_i := i;
		End;

	i := max_i;
	While LT[i] <> 0 Do Begin
		DT[i] := DT[i] * (-1);
		i := LT[i];
	End;
	DT[i] := DT[i] * (-1);

	i := LG[max_i];
	While LG[i] <> 0 Do Begin
		DT[i] := DT[i] * (-1);
		i := LG[i];
	End;
	DT[i] := DT[i] * (-1);
End;

Procedure Xuat;
Var i : Integer;
Begin
	WriteLn(max-1);
	For i := 1 To N Do
		If DT[i] < 0 Then Write(A[i], ' ');
End;
Begin
	Nhap;
	TimDayTangXuoi;
	TimDayTangNguoc;
	XuLi;
	Xuat;
End.
Gửi hồi đáp
  • Similar Topics
    Các hồi đáp
    Lượt xem
    Bài viết cuối