Cho dãy X có n phần tử là các số nguyên. Xk gọi là lớn thứ 2 trong dãy nếu:

Tôi đưa ra phương án thế này, các đồng chí cho ý kiến
* Ý tưởng: 2 vòng For nhưng không lồng nhau
1. Vòng For 1: Tìm phần tử lớn nhất của dãy
2. Vòng For 2: Tìm phần tử lớn nhất của dãy nhưng khác phần tử tìm được ở vòng for 1
Như vậy tôi vẫn không hiểu độ phức tạp có phải là O(n) không?

Tôi cũng có ý tưởng như đ/c Son. Nhưng theo tôi là phải 3 vòng chứ không phải 2:

- Vòng 1: tìm Max_1.(giá trị lớn nhất)

- Vòng 2: tìm giá trị bất kì trong dãy khác Max_1

i:=1;
While A_i = Max_1 do i:=i+1;
Max_2:=A_i;

- Vòng 3: If (A_j <> Max_1) và (A_j > Max_2) thì Max_2:= A_j

Vòng 1 và 2 có độ phức tạp là n, vòng 3 có hai phép so sánh nên có độ phức tạp là 2n. Vậy 3 vòng là 4n ---> Độ phức tạp của thuật toán là O(n)

Tôi nghĩ chỉ cần 1 vòng. Ta nên đặt 1 biến Trước_Max. Trước khi gán biến Max, ta cho nó so luôn với Trước_Max (giống như với Max và bỏ qua nếu nó không đáp ứng). Độ phức tạp O(n).

* Thuật toán: -- Giả thiết dãy chỉ gồm các số tự nhiên Procedure PhanTuLonThu2(M: Dãy số);
Var Max1: integer;
Var Max2: integer;
Max1:=-1;
Max2:=-1;
	For i=1 to |M| do
		For i = 1 to |M| do
		if Mi > Max1
		Max1 := Mi;
			if Mi > Max2 And Mi < Max1
			Max2:=Mi;
if Max2 = -1
Output("Không có phần tử lớn thứ 2")
else
Output(Max2);

-- Đây là thủ tục rất tường minh các bác xem góp ý
-- Có thể dùng 1,3 vòng For nhưng tôi nghĩ một vòng For thì số phép tính vẫn
như vậy vì thực chất mình chỉ tách ra và gộp vào thôi.

Procedure PhanTuLonThu2(M: Dãy số);
Var Max1: integer;
Var Max2: integer;
Max1:=-1;
Max2:=-1;
	For i=1 to |M| do
		if Mi > Max1
		Max1 := Mi;
			if Mi > Max2 And Mi < Max1
			Max2:=Mi;
if Max2 = -1
Output("Không có phần tử lớn thứ 2")
else
Output(Max2);

Bỏ một dòng FOR

Cái thủ tục của chú Yên sai rồi
Chú thử với dãy: 1,2,5 là thấy ngay

- Son xem lại bài đi nhé, nếu hai vòng for lồng vào nhau như Son viết thì thuật toán sẽ có độ phức tạp là O(n²) đấy.

- Mình thắc mắc là đặt max1, 2 = -1 lúc ban đầu như thế liệu có ổn không nhỉ?

- Nếu gán được max1,2 = -1 thì mình có thể dùng 1 vòng for.

For i:= 1 to |M|

.....

If Ai>=max1 then max1:=Ai Else If Ai >= max2 then max2:=Ai

Bác Cường sửa sai bài em rồi

Bác thử chuỗi 1,2,3 là thấy ngay

sonld1984 đã viết:Bác Cường sửa sai bài em rồi

Chuẩn, tối qua anh vào thì vẫn còn nguyên bài ban đầu của chú. nếu anh Cường viết hai vòng For lồng vào nhau như thế thì độ phức tạp là n2 chứ ko phải là n nữa.
Phải tách ra thành 2 vòng for riêng biệt thì độ phức tạp mới là n.

Thuật toán tìm phần tử lớn thứ 2 trong dãy
Các bạn tham khảo xem thuật toán này thế nào

Procedure Phantulonthu2(X: dãy số)

max1 = 1
max2 = 2
If x(max1) < x(max2) Then
max2 = 1
max1 = 2
End If
For i = 3 To n
If x(i) > x(max1) Then
max2 = max1
max1 = i
ElseIf (x(i) < x(max1)) And (x(i) > x(max2)) Then
max2 = i
End If

Output max2;

Đ/c Tiệp xem lại dãy (3, 3, 3, 3, 1) xem thế nào nhé.

Đúng là đề bài tìm phần tử lớn thứ 2 trong dãy, nếu mình tìm giá trị lớn thứ 2 trong dãy thì không hiểu đề bài và 0 điểm. Mình phải chỉ ra trị số n, chứ không phải giá trị M(n).

Có thể do Mr.Son không đánh có cấu trúc, nên tôi nghĩ sai cấu trúc nên mới sửa lại cho dễ nhìn. Cấu trúc thế nào thì đề nghị tác giả copy vào Word dán vào table (như hướng dẫn) cho chuẩn.

Bài của đ/c Tiệp không khẳng định được có phần tử thứ 2 hay không, nếu không có thì thế nào?

public static int VTMax1 = -1;
public static int VTMax2 = -1;
public static void PTLT2(int[] Arr, int n)
{
int GTMax1 = -1;
int GTMax2 = -1;
if (VTMax1 == -1) GTMax1 = -1;
else GTMax1 = Arr[VTMax1];
if (VTMax2 == -1) GTMax2 = -1;
else GTMax2 = Arr[VTMax2];
if (n >= 0)
{
if (Arr[n] > GTMax1)
{
VTMax2 = VTMax1;
VTMax1 = n;
}
else
{
if (Arr[n] > GTMax2 && Arr[n] < GTMax1)
{
VTMax2 = n;
}
}
PTLT2(Arr, n - 1);
}
}
Output VTMax2;

Chà, đệ quy bằng C# à. [You must be registered and logged in to see this image.]

Ý tưởng:


Truyền vào 3 chỉ số:


N - số phần tử phải xét


a- chỉ số chỉ ra để xét phần tử có giá trị Max, tức xét M(a)
= Max


b- chỉ số chỉ ra để xét phần tử
có giá trị Max2, tức xét M(b) = Max2


Viết

Procedure Tim (n, a, b: chỉ số)
IF n=0 then Output b;
	ELSE IF M(n) > M(a) THEN		Tim (n-1, n, b)
		ELSE IF M(n) > M(b)	THEN Tim (n-1, a, n)
			ELSE Tim (n-1, a, b)
END