-
Thông tin
-
Hỏi đáp
Bài tập phân tích và thiết kế thuật toán | Trường Đại học Quy Nhơn
Bài tập phân tích và thiết kế thuật toán | Trường Đại học Quy Nhơn. Tài liệu được biên soạn dưới dạng file PDF gồm 7 trang, giúp bạn tham khảo, ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!
Môn: Nguyên Lý kế toán (ĐHQN) 39 tài liệu
Trường: Đại học Quy Nhơn 422 tài liệu
Thông tin:
Tác giả:
Preview text:
PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN
Câu 1 (4 điểm): Giải phương trình đệ quy.
- Phương pháp truy hồi:
Bài 1: Giải phương trình đệ quy sau:
T(n)=
C1
T (n 1) C 2
Giải
n =0 n>0
Ta giải bằng phương pháp truy hồi Ta có T(n)= T(n-1) +C2
= (T(n-2)+C2) + C2= T(n-2) + 2C2
= ((T(n-3)+C2)+C2)+C2= T(n-3)+3C2
...........
= T(n-i) + iC2
Quá trình kết thúc khi n=i khi đó T(n)= T(0)+nC2=C1+nC2=O(n); Vậy T(n)= O(n).
Bài 2: Giải phương trìnhi sau:
C1
n =1
n >1
T(n)=
2T (
n ) C n
2 2
Giải: Ta có T(n)= 2T(n/2)+C2n;
n n
= 2(2T(n/4)+C2 2 ) +C2n= 22(T( 22 )+2C2n
n n
=22(2T(n/8)+ C2 4 )+C2n= 23(T( 23 )+3C2n
......
= 2iT( n
2i
)+iC2n
Quá trình kết thúc khi n=2i; i= log2n Vậy T(n)= nC1+C2 nlog2n= O(nlog2n)
- Phương pháp đệ quy tổng quát.
n
T(n)= aT( b )+ d(n);
* Nếu d(n) là hàm nhân:
- Nếu a>d(b) thì NR(nghiệm riêng)=O(nlogab)= NTN(nghiệm thuần nhất) T(n)= O(nlogba)
- Nếu a<d(b) thì T(n)= O(nlog bd(b))
- Nếu a=d(b) thì T(n)= O(nlogbaLogbn)
Bài 1: Giải phương trình: T(n) với T(1)=1 và T(n)= 4T(n/2)+n
Giải
Ta có phương trình đã ở dạng tổng quát và d(n)= n là một hàm nhân a =4; b= 2;
d(b)= b= 2;
a>d(b)
Vậy theo công thức ta có T(n)= O(nlogab)= O(nlog24)= O(n2).
Bài 2: Giải phương trình: T(1)=1; T(n)= 4T(n/2)+n2 Giải:
Ta thấy phương trình đã ở dạng chuẩn. d(n)= n2 là một hàm nhân.
a= 4; b= 2;
d(b)=d(2)= 22=4;
Như vậy a= d(b)
Vậy theo công thức ta có: T(n)= O(nlogbaLogbn)
= O(nlog24Log2n)=O(n2 Log2n)
Bài 3: Giải phương trình: T(1)=1 và T(n)= 4T(n/2)+n3
Giải:
Ta có phương trình đã ở dạng chuẩn. d(n)= n3 là một hàm nhân.
a =4; b= 2;
d(b)= d(2)= 8;
Như vậy a<d(b);
Theo công thức ta có T(n)= O(nlog d(b))
b
= O(nlog28)= O(n3)
Vậy T(n)= O(n3);
Bài 4: Giải phương trình T(1)= 1; T(n)= T(n/2)+1; Giải:
Ta thấy phương trình đã ở dạng chuẩn. d(n)= 1 là một hàm nhân.
a =1; b=2; d(b)=d(2)=1;
như vậy a=d(b);\
Theo công thức ta có T(n)= O(nlogbaLogbn)
= O(nlog 1Log n)= O(Log n);
2 2 2
Vậy T(n)= O(Log2n);
* Nếu d(n) không phải là hàm nhân:
2
Câu 2 (4 điểm): Viết chương trình:
Tìm kiếm nhị phân
program CTTKNP; uses crt;
type
Mang= array[1..100] of integer;
end; end;
end;
TKNP(a,x,dau,giua-1);
var A: Mang; i,n,x: integer;
procedure TKNP(a:mang;x,dau,cuoi:integer); var giua:integer;
begin
if (dau>cuoi) then
writeln(' Khong thoa man') else
begin
giua:= (dau+cuoi) div 2; if (x= a[giua]) then writeln(' Chuc mung ban') else
begin
if (x>a[giua]) then TKNP(a,x,giua+1,cuoi) else
BeGin clrscr;
writeln(' Chuong trinh tim kiem nhi phan. '); writeln(' Moi ban nhap so phan tu cua mang n:= ');
read(n); writeln; writeln;
for i:=1 to n do begin
writeln(' Phan tu ',i,'la: '); readln(A[i]);
end;
writeln(' Ban muon kiem tra phan tu nao ? '); readln(x);
writeln(' Ket qua: 1 la co, 0 la khong'); TKNP(A,x,1,n);
readln;readln; end.
Độ phức tạp: T(n)=
1
( n ) 1
T
2
n = 1
n >1
Max, Min
program TimMaxMin; uses crt; type Mang= array[1..100] of integer; var i,n,x,max,min: integer; A: mang; procedure TM2(M:Mang;d,c:integer;var max:integer;var min:integer); | var max1,min1,max2,min2: integer; begin if (d= c) then begin max:= M[d]; min:= M[d]; end else begin |
TM2(M,d,(d+c)div 2,max1,min1); TM2(M,(d+c)div 2 + 1,c,max2,min2); if(max1>max2) then max:= max1 else max:= max2; if(min1>min2) then min:= min2 else min:= min1; writeln(' max:= ',max); writeln(' Min:= ',min); end; writeln; end; BeGin clrscr; writeln(' CHUONG TRINH TIM MAX,MIN CUA DAY SO'); | writeln(' Nhap so phan tu cua day n:= '); read(n); writeln; writeln; for i:=1 to n do begin writeln(' Phan tu thu ',i,' la: '); read(A[i]); end; writeln; writeln(' Ket qua: '); TM2(A,1,n,max,min); readln; readln; end. |
Độ phức tạp T(n)=
0
1
2T (
n ) 2 2
Nếu n= 1
Nếu n= 2 Nếu n>2
Sắp xếp phương pháp lựa chọn
program select_sort; uses crt; Type mang=array[1..100]of integer; var a:mang; i,j,n,index,key:integer; procedure swap(var a,b:integer); var tam:integer; Begin tam:=a; a:=b; b:=tam; End; procedure sort(var a:mang;n:integer); var i,j,index,key:integer; Begin for i:=1 to n-1 do begin index:=i;key:=a[i]; for j:=i+1 to n do if(a[j]<key)then begin | key:=a[j];index:=j; end; swap(a[i],a[index]); end; end; BEGIN clrscr; write('Nhap so phan tu can sap xep:');readln(n); writeln('Nhap cac phan tu:'); for i:=1 to n do begin write('a[',i,']=');readln(a[i]); end; sort(a,n); writeln('Day da sap xep la:'); for i:=1 to n do write(a[i]:3); readln; END. |
* Độ phức tạp:
4
T(n)=
n1
(n i)
i1
n(n 1) 2
= O(n2).
Câu 3 (2 điểm): Trình bày ý tưởng, thuật toán:
a) Phương pháp phân đoạn (Quick Sort)
- Ý tưởng:
Giả sử v là một giá trị khóa mà ta gọi là chốt. Ta phân hoạch dãy a[1]..a[n] thành 2 mảng con bên trái và bên phải.Mảng con bên trái bao gồm các khóa có giá trị nhỏ hơn chốt. Mảng con bên phải bao gồm các khóa có giá trị lớn hơn hoặc bằng chốt.
- Sắp xếp mảng con bên trái và bên phải cũng theo cách trên.
- Một mảng chỉ gồm một phần tử hoặc nhiều phần tử có khóa bằng nhau thì đã có thứ tự.
- Thuật toán:
Chọn chôt:
Function FindPivot(i,j:integer): integer; Var Firstkey: keytype;
k: integer; begin
k:= i+1;
Firstkey:= a[i].key;
While (k<=j) and (a[k].key= Firstkey) do k:= k+1;
If k>j then Findpivot:= 0 Else
If (a[i].key > Firstkey) then findpivot:=
k
Else Pindpivot:= i;
End;
- Phân hoạch mảng:
Function Partition(i,j: integer; Pivot: keytype): integer;
Var L,R: integer; Begin
L:= i; R:= j;
Đánh giá độ phức tạp:
While L<=R do Begin
While a[L].key<pivot do L:= L+1; While a[R].key>=pivot do R:= R-1; If L<R then Swap(a[L],a[R]);
End; Partition:= L;
End;
- Thủ tục QuickSort:
Procedure QuickSort(i,j:integer): Var Pivot: keytype;
PivotIndext,k: integer; Begin
PivotIndex:= Finpivot(i,j); If (PivotIndex<>0) then
Begin
Pivot:= a[pivotIndex].key; K:= partition(i,j,pivot); QuickSort(i,k-1); QuickSort(k,j);
End;
End;
+ Trường hợp xấu nhât:
1
Nếu n= 1
T(n)=
T (n 1) T (1) n
Nếu n>1
Giải ra T(n)= O(n2)
5
+ Trường hợp tốt nhất:
T(n)=
1
2T (
- n
2
Nếu n= 1 Nếu n>1
Giải ra T(n)= O(nlogn)
b. Tìm dãy con có tổng cho trước.
- Ý tưởng:
- Xác định dãy con (ai0,ai1,ai2...aik) sao cho ai0+ai1+ai2+..+aik=M bằng cách chọn lần lượt ai0,ai1...
- Chọn ai0 từ (a0,a1,...an-1) mà ai0<M
- Khi đã chọn được (ai0,ai1,ai2...aik-1) thì ta có thể chọn aik với ik (ik-1,n-1)
- Giả sử dãy số đã lưu trong mảng A
-Dãy chỉ số của dãy con được lưu trong mảng I
- Thuật toán:
Void SubSequences(int A[n];int M;int I[n]); | ||
{ k= 0; I[0]= -1; int S=0; | I[k+1]= I[k]; | |
While (k>=0) | K++; | |
{ I[k]++; | } | |
If (I[k]<n) | } | |
{ if (S+A[I[k]])<=M | Else | |
iF (S+A[I[k]])==M) | { k--; | |
for (i:=1;i<=k;i++) | S= S-A[I[k]]; | |
printf(I[i]); | } | |
else { | } | |
S= S+A[I[k]]; | } |
- Tìm dãy con chung dài nhất của hai dãy số:
- Ý tưởng:
- Với mọi i{1..m}, j{1,..n};
Gọi Lij là độ dài của dãy con dài nhất của a[1..i] và b[1..j] thì Lmn chính là độ dài của dãy con c cần tìm.
- Như vậy ta cần tính Lij
- Thuật toán:
For (i=2;i<=m;i++) For (j=2;j<=n;j++)
{ if (a[i]=b[j]) x=1; Else x=0;
L[i][j]= Max{L[i][j-1],L[i-1][j], L[i-1][j-1] + x}
}
Return(L); }
Void Day_chung(a,b,m,n)
{ for (i=1;i<=m;i++)
If (b1a[1..i]) L[i][1]= 1; Else L[i][1]=0;
For (j=1;j<=n;j++)
If (a[1]b[1..j]) L[1][j]= 1; Else L[1][j]= 0;
6
7