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 :slightly_smiling_face: chắc tại hôm nay đầu óc không được minh mẫn :neutral_face:


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 :roll_eyes:

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;
		trace[i]:= jmax;
	end;
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 :slightly_frowning_face:

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

1 Like

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

writeln(l[0]-2);

Hmm, mình giải thích phần cầm canh đúng chưa nhỉ, hơi băn khoăn chỗ đấy.

2 Likes

tks bạn , để mình suy nghĩ thêm xíu nữa

Kí hiệu như cũ thì:

  • L[1] = 1
  • L[n] = 1 + L[1..n-1].max_if( (_, index) => a[index] < a[n], 0) số 0 này là có lí do.

hay L << 1 + L.max_if...

p/s: Bài này có hai lính canh là vì:

  • Lính canh ở đuôi (theo code trên): max của tập rỗng bằng mấy :smiley:
  • Lính canh ở đầu: để max tụ hết về đầu thay vì phải đi lấy max lần nữa. Nhưng do 0 là lính canh :smiley: nên suy cho cùng chỉ có một lính canh là buộc phải có.
2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?