3.1 Function Ack(m,n)
Input: m, n là hai số nguyên không âm Begin
1. {Trường hợp cơ sở 1} if (m==0) return n+1; 2. else if (m>=1) if (n==0) return Ack(m-1, 1); 3. else return Ack(m-1, Ack(m,n-1)); End 3.2 Function USCLN (p,q)
Input : p, q là hai số nguyên dương, p > q Begin If (p mod q = 0) Return q ; Else Return (USCLN(q, p mod q)); End. 3.3 Function C (n,k)
Input: n, k là số nguyên không âm , k <= n Begin If (n == k) Return 1; Else if (k==0) Return 1;
Else return (C(n-1, k-1) + C(n-1,k)); End 3.4 Algorithm INDAO (S)
Input : S là một xâu ký tự Begin If (S rỗng ) return ; Else
In ký tự cuối cùng của S
S’ = S trừ đi ký tự cuối cùng INDAO(S’); End. Algorithm INDAO (S)
Input : S là một xâu ký tự Begin If (S rỗng ) return ; Else
C = ký tự đầu tiên trong S
S’ = S trừ đi ký tự đầu tiên INDAO(S’); In C; End.
Cấu trúc dữ liệu và Giải thuật – Bài tập chương 4 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
Cấu trúc dữ liệu và Giải thuật – Bài tập chương 4 S[2*Size] = i; S[2*Size + 1] = SUM; Size = Size + 1; End; i = i - 1; End; S[1] = Size; END. 4.10
1. Tính số các nút trong danh sách Function DEM (L) p= L; dem = 0;
while p < > NULL do begin dem= dem + 1; p= NEXT(p); end. return dem.
2. Tìm nút thư k trong danh sách Function TIMK (L,k) p= L; i = 1; while (i NULL) do begin i= i + 1; p= NEXT(p) ; end. return p.
3. Bổ sung một nút vào sau nút thứ k Procedure BOSUNGSAUK(L, X,k) call New(p) ; INFO(p) = X;
if L = NULL then begin NEXT(p) = NULL; L= p; return ; end. q = TIMK(L,k) ; if q <> NULL then begin NEXT(p) = NEXT(q) ; NEXT(q) = p; end;
4. Loại bỏ nút đứng trước nút thứ k Procedure LOAIBO(L, k) p= L; q= r= NULL; i = 1; while (i NULL then begin i= i + 1; r= q; q= p; p= NEXT(p) ; end;
if r <> NULL then NEXT(r ) = p;
Cấu trúc dữ liệu và Giải thuật – Bài tập chương 4
else if q<> NULL then L = p;
else write(‘Danh sach co 1 nút’ ); Call Dispose (q); return.
5. Chèn danh sách trỏ bởi P vào sau nút trỏ bởi M trong danh sách
6. Tách danh sách thành 2 danh sách con, nút đầu danh sách con là nút trỏ bởi M Procedure TACH(L,M) p= L;
while NEXT(p) <> M do p= NEXT(p) ; NEXT(p) = NULL;
7. Đảo ngược danh sách đã cho (danh sách mới trỏ bởi L’) Procedure DAO(L); r= L; q= null; While r <> NULL Do Begin p= q;
q= r ; r= NEXT(r); NEXT(q) : = p; End; l’ = q; END.