01/10/2018, 17:21

Giúp mình hiểu chỗ code này

Edit: Mình đã hiểu ra vấn đề… thực ra khá dễ hiểu chắc tại hôm nay đầu óc không được minh mẫn

Mình đang học mấy thuật toán trong sách Tài liệu chuyên tin 1 của Lê Minh Hoàng , và học đến phần qhđ thì có bài ví dụ tìm dãy con đơn điệu tăng dài nhất nhưng có một chỗ mình đọc mãi không hiểu nhưng gõ code chạy trên máy thì ra kq đúng

a[0]:=low(longint);
a[n+1]:=high(longint);
L[n+1]:=1;
for i:= n downto 0 do
	Begin 
		jmax := n+1;
		for j:= i+1 to n+1 do 
			if (a[j]>a[i]) and (L[j] > L[jmax]) then jmax:=j; 
			l[i]:=l[jmax] + 1;
			t[i] := jmax;
		end;
		writeln(l[0]-2);
end

Đây ở chỗ này

if (a[j]>a[i]) and (L[j] > L[jmax]) then jmax:=j;

theo mình nghĩ thì lúc khai báo mảng trong pascal các giá trị trong mảng đều mang gt = 0 , vậy làm sao mà điều kiện L[j] > L[jmax] lại thỏa mãn được.
các bạn giải thích giùm mình với , thắc mắc cả ngày hôm nay rồi

Phạm Việt Quang viết 19:37 ngày 01/10/2018

cảm ơn ad @hungsteve đã edit bài giúp mình tại mình ít khi post bài nên chưa rõ lắm chỗ ấy

Anh chàng Doggo viết 19:35 ngày 01/10/2018

Nó không thoả thì cứ suy nghĩ theo kiểu nó không thoả thôi, xD
Ngay vòng lặp đầu tiên, L[j] (hay L[n+1]) bằng 1, vẫn bằng giá trị của L[jmax] (cũng tức L[n+1]), thế nên không thực hiện phần jmax:= j, vậy jmax lúc này vẫn bằng n + 1. Sau đó gán L[i] := L[jmax] + 1 = 2. (hay L[n] := L[n+1] + 1). Nghĩa là đằng sau phần tử n có một phần tử lớn hơn nó, tính cả nó thì dãy con tăng từ n đến n+1 = 2 phần tử.
Vậy thằng L[0] sẽ có giá trị bằng với 1 + 1 + L[max], (với con 1 đằng trước là phần tử cầm canh, max là index của phần tử lớn nhất của mảng L sao cho thoả a[0] < a[max], sau đó cộng thêm 1, tức là tính cả chính nó). Xuất thì ta trừ đi 2 thằng cầm canh, vậy nên ra được dòng