Thủ tục hoà nhập 2 mảng đã sắp

Bài toán 1. Cho 2 mảng đã được sắp
X= < X(p) và Y =

Tạo mảng Z =< Z(t),Z(t+1),..., Z(t+m-p+n-q+1) > có thứ tự từ 2 mảng X và Y.

Mô tả thuật toán hoà nhâp 1 (HN1)
Ý tưởng:
1. So sánh 2 phần tử nhỏ nhất của 2 mảng. Đưa phần tử nhỏ hơn ra mảng đích.(Loại bỏ phần tử này ra khỏi mảng chứa nó)
2. Lặp lại thủ tục này cho đến khi vét hết một trong 2 mảng.
3. Chuyển toàn bộ phần đuôi của mảng còn lại ra mảng đích.

Thuật giải:
Proce. HN1(X,Y: dãy; p, m, q, n: chỉ số; VAR Z)
          1. t:=1; i:=p; j:=q;
          2. While ( i<=m) & (j<=n)
                              a. IF Xi < Yj THEN           { Zt: = Xi, i++ }
                                                                      else { Zt: = Yj, j++ }
                              b. t++
          3. IF i>m FOR k:=j to n
                                                                      Zt+k-j := Yk
                    ELSE FOR k:=i to m
                                                                      Zt+k-i := Xk

Thủ tục SXHN(VAR X: dãy; d, c : chỉ số)
IF d< c THEN
          1. m:= (d+c)/2
          2. SXHN (d,m); SXHN (m+1, c);
          3. HN1(X, X, p, m, m+1, n, Z)
          4. for t:=d to c
                    Xt:= Zt
                              t:=1; i:=m; j:=m+1

Mô phỏng đơn giản:
[You must be registered and logged in to see this image.]

Anh Admin có Post bài lên, nhưng em thấy sai rất nhiều
1. Chỉ số t không thể là 1.
2. Hàm đệ quy HN1(X, X, p, m, m + 1, n, Z) sai mà phải là
HN1(X, X, d, m, m+1, c, Z );
3. Không biết chỉ số t là bao nhiêu ??
Tôi nghĩ ta nên hỏi lại thày thuật toán này

Tôi thấy đọc trong sách rất là rõ ràng mà.
Ở đây chia ra mấy trường hợp;
1. Hoà nhập hai dãy x và y đã được sx không tăng hoặc không giảm. → dùng HN1 để giải quyết.
2. Hoà nhập hai nửa của một dãy đã được sx → HN2
3. SX trên một mảng A[a....b] → chính là giải thuật mà thầy viết.

Proc HN1(A:mảng; var Z:mảng; var a,c,b)
{ở đây ta dùng mảng z để lưu trữ các phần tử đã được sx, c là chỉ số giữa của mảng A: c= (a+b)/2}
{ta chia mảng A ra thành 2 mảng con [a...c] và [c+1...b] }
1. i:=a; j:= c+1; k:= 0;
{i:duyệt trên [a..c]; j: duyệt trên [c+1...b]; k: duyệt trên mảng Z}
2. {so sánh các phần tử của hai mảng con với nhau}
While (i < = c) and (j <= b) Do
          a. If A[i] < A[j] then Z[k]: = A[i]; i:= i+1;
                    Else Z[k]: = A[j]; j:= j+1;
                              b. k:=k+1;
3. If i> c then
                    For l:= j to b do Z[l+k-j] : = A[l];
                              Else
                    For l:= i to c do Z[l+k-i] : = A[l];
4. End.

Proc hoa_nhap(var A: dãy số; d,c: chỉ số);
If d < c then
1. m: = (d+c)/2;
2. hoa_nhap(d,m); hoa_nhap(m+1, c);
3. HN1(A,a,c,c+1,b,Z);
4. For t: = d to c do A[t]: = Z[t];
End.

admin cho hỏi sao không thấy thủ tục hòa nhập 2 nhỉ

Ban QT: Hãy tự viết

Các đồng chí hiểu sai hết rồi. Tôi khuyên nên lập trình đi. Nói trên đầy dài dòng lắm.

Proce. HN2(X: dãy; p, m, q, n: chỉ số; Z: dãy xuất)
1. t := p; i := p; j := q;
2. WHILE ( i ≤ m) & (j ≤ n)
          a. IF Xi < Xj THEN { Zt: = Xi, i++ }
                    ELSE { Zt: = Xj, j++ }
          b. t++
3. IF i > m FOR k := j to n
                    Zk := Xi
          ELSE FOR k := i to m
                    Zk = Xj

Ban QT: Đã sửa giúp đúng cấu trúc. Bạn nên dùng chữ c a c h (không có khoảng trắng) để đặt khoảng cách chữ. Hoặc đặt phần lập trình giả mã trong thẻ CODE [You must be registered and logged in to see this image.]
Bạn nên viết đôi dòng nói qua các biến, ví dụ bài trên là xâu có 2 đoạn đã sắp xếp không giảm rồi từ vị trí này đến vị trí này chẳng hạn để mọi người dễ hình dung.

Bài thầy cho: X(d) > X(m + 2) > ......... > X(c). Tạo Y(dc) không giảm. Mình viết như sau có ok không, các bạn check hộ mình vơi.

Proc HN2P(X: mảng; d, c, m: Chỉ số; Var Y: mảng);
1) t = 1; i = d; j = c;
2) WHILE (i ≤ m) & (j ≥ m) DO
          a) IF Xi < Xj THEN Yt = Xj; i = i + 1;
                    ELSE Yt = Xi; j = j-1;
          b) t = t + 1;
3) a) IF (i > m) & (j > m) THEN
          FOR k = j DOWNTO m DO Yt = Xk; t = t + 1;
b) IF (i FOR k = i TO m DO Yt = Xk; t = t + 1;

Ban QT: Bạn check lại dòng tô màu, không hiểu dòng lệnh đó của bạn.

các bạn tham khảo tại đây.
[You must be registered and logged in to see this link.]
Có code và Video minh họa luôn, rất hay