Ktl-icon-tai-lieu

Bài tập danh sách nối đơn

Được đăng lên bởi Hoang Thanh Tung
Số trang: 4 trang   |   Lượt xem: 333 lần   |   Lượt tải: 0 lần
4.6 Xét ma trận 5 x 5 ta có:
Bình thường nếu lưu trữ toàn bộ ma trận 5 x 5 theo thứ tự ưu tiên hàng , một phần
tử A[I,j] sẽ nằm ở vị trí 1 + (i-1) * 5 +j-1 ( Có thể tham khảo công thức tính vị trí phần tử
(i,j) khi lưu theo thứ tự ưu tiên hàng , trang 62 sách giáo trình)
Nhưng nó nằm ở hàng I thì trước nó sẽ có 3 *(i-1) phần tử 0 => Thực chất là
A[I,j] sẽ nằm ở vị trí 1 + (i-1) * 5 +j-1 - 3 *(i-1) = 2(i-1) + j
Vậy nếu |i-j| > 1 thì A[I,j] = 0 , nếu ngược lại thì A[I,j] = B[2*(i-1) +j]
Cách 2: Xác định phần tử (I,j) : Nó ở hàng thứ I thì trước nó ở i-1 hàng đã có 2 + 3 * (i-2)
phần tử được lưu ( hàng 1 có 2 phần tử, ở i-2 hàng tiếp theo mỗi hàng có 3 phần tử)
Trong hàng thứ I, nó ở cột thứ j , vì trong hàng I thì phần tử đầu tiên được lưu trữ là phần
tử ở cột i-1 nên số các phần tử ở bên trái phần tử ở cột j mà được lưu là j – (i-1)
Tổng số phần tử đã được lưu trước phần tử (I,j) là 2 + 3 * (i-2) + j – (i-1)
Vậy thì chỉ số của phần tử (I,j) trong vector mảng 1 chiều là 1 + 2 + 3 * (i-2) + j – (i-1)
4.7 .
Lập luận tương tự như với bài 4.6.
A(I,j) sẽ được lưu trong mảng 1 chiều A.
Nếu phần tử (I,j) được lưu thì trước nó đã có i-1 hàng được lưu.
Hàng 1 có 1 phần tử được lưu
Hàng 2 có 2 phần tử được lưu
….
Hàng i-1 có i-1 phần tử được lưu
Vậy tổng số phần tử được lưu trong i-1 hàng trước là : 1 + 2 +..+ (i-1) = I * (i-1) /2
Tại cột j thì đã có j-1 phần tử được lưu ở trước
Vậy phần tử I, j sẽ được lưu tại chỉ số 1 + I *(i-1) / 2 + j -1

startPos = 0;
for (i:=1 to n) do
{
tempSUM := 0;
startPos := i*(i+1)/2 - i; ( I (i-1) /2) { hạng tử cuối cùng của phương trình thứ I -1 }
for (j:= 1 to i-1) do
{
tempSUM := tempSUM + X[j]*A[startPos+j];
}
X[i] = (B[i] - tempSUM)/A[i*(i+1)/2];
}

4.9
a.
Procedure AddPolynomial(A,B, S)
n = A[1];
m = B[1];
if n >=m then
Begin
S[1] = n;
For i = 2 To (n – m+1) Do
S[i] = A[i];
For i = 2 To m+2 Do
S[n-m + i] = A[n-m +i] + B[i];
End;
Else
Begin
S[1] = m;
For i = 1 To (m - n +1) Do
S[i] = B[i];
For i = 2 To n+2 Do
Begin
S[m-n + i] = B[m-n +i] + A[i];
End;
End;
END.
b.
{Tim he so cua x^k trong array A}
Function GetCoefficientForTerm(A, k);
For i = 1 To A[1] Do
Begin
If A[2*i] = k Then
Begin
c = A[2*i+1];
Return c;
End;
End;
Return 0 ;
Procedure AddPolynomials(A, B, S);
Size = 1;
i = MAX(A[2], B[2]); { tim he so lon nhat cua 2 da thuc}
While i >= 0 Do
Begin
SUM = GetCoefficientForTerm(A, i) + GetCoefficientForTerm(B, i);
If SUM < > 0 Then
Begin

S[2*Size] = i;
S[2*Size + 1] = SUM;
Size = Size + 1;
End;
i = i - 1;
End;
S[1] = Size;
END.

4...
4.6 t ma trận 5 x 5 ta có:
Bình thường nếu lưu trữ toàn bộ ma trận 5 x 5 theo thứ tự ưu tiên hàng , một phần
t A[I,j] sẽ nằm ở vị trí 1 + (i-1) * 5 +j-1 ( Có thể tham khảo công thức tính vị trí phần tử
(i,j) khi lưu theo thứ tự ưu tiên hàng , trang 62 sách giáo trình)
Nhưng nó nằmhàng I thì trước nó sẽ có 3 *(i-1) phần tử 0 => Thực chất là
A[I,j] sẽ nằm ở vị t 1 + (i-1) * 5 +j-1 - 3 *(i-1) = 2(i-1) + j
Vậy nếu |i-j| > 1 thì A[I,j] = 0 , nếu ngược lại thì A[I,j] = B[2*(i-1) +j]
Cách 2: Xác định phần tử (I,j) : Nó ở hàng thứ I thì trước nó ở i-1 hàng đã có 2 + 3 * (i-2)
phần tử được lưu ( hàng 1 có 2 phần tử, ở i-2 hàng tiếp theo mi hàng có 3 phần tử)
Trong hàng thứ I, nó ở cột thứ j , trong hàng I thì phần tử đầu tiên được lưu trữ là phần
t ở cột i-1 nên số các phần tử ở bên trái phần tử ở cột j được lưu là j (i-1)
Tổng số phần tử đã được lưu trước phần tử (I,j) là 2 + 3 * (i-2) + j (i-1)
Vậy t chỉ số của phần tử (I,j) trong vector mảng 1 chiều là 1 + 2 + 3 * (i-2) + j (i-1)
4.7 .
Lập luận tương tự như với bài 4.6.
A(I,j) sẽ được lưu trong mảng 1 chiều A.
Nếu phần tử (I,j) được lưu t trước nó đã có i-1 hàng được lưu.
Hàng 1 có 1 phần tử được lưu
Hàng 2 có 2 phần tử được lưu
….
Hàng i-1 có i-1 phần tử được lưu
Vậy tng số phần tử được lưu trong i-1 hàng trước là : 1 + 2 +..+ (i-1) = I * (i-1) /2
Tại cột j thì đã có j-1 phần tử được lưu ở trước
Vậy phần tử I, j sẽ được lưu tại chỉ số 1 + I *(i-1) / 2 + j -1
startPos = 0;
for (i:=1 to n) do
{
tempSUM := 0;
startPos := i*(i+1)/2 - i; ( I (i-1) /2) { hạng tử cuốing của phương trình thứ I -1 }
for (j:= 1 to i-1) do
{
tempSUM := tempSUM + X[j]*A[startPos+j];
}
X[i] = (B[i] - tempSUM)/A[i*(i+1)/2];
}
Bài tập danh sách nối đơn - Trang 2
Bài tập danh sách nối đơn - Người đăng: Hoang Thanh Tung
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
4 Vietnamese
Bài tập danh sách nối đơn 9 10 261