Thiết kế và đánh giá thuật toán

Lời Nói Đầu Xây Dựng Một Thuật Toán Tốt Để Giải Bài Bài Toán Đã Cho Là Bước Quan Trọng Nhất Trong Việc Giải Bài Toán Đó Trên Máy Tính Điện Tử. Để Có Được Một Thuật Một Thuật Toán Tốt Cần Phải Nắm Vững Các Kỹ Thuật ...

Khối lệnh 2 . case nk khối lệnh k [ default khối lệnh k+1] } Với ni là các số nguyên, hằng ký tự hoặc biểu thức hằng. Các ni cần có giá trị khác nhau. Đoạn chương trình nằm giữa các dấu { } gọi là thân của toán tử switch. default là ...

Ví dụ 1.3. Giải thuật tính giá trị của e x theo công thức gần đúng: e x = 1 + x/1! +x 2 /2! + …+ x n /n! với x và n cho trước EXP1(); { scanf(x) ; S =1; for (i=1;i<=n;i++) { p =1; for(j=1;j<=i;j++) p=p*x/j; S = S +p; } } Ta có thể coi phép toán tích cực ở ...

Do đó, T(n) = O(n). Ví dụ 1.9. T(n) = Giải phương trình truy hồi sau: Ta có với n>1: T(n) = 2T( n )+c 2 n 2 n n c 1 nếu n=1 2 T( n )+c 2 n nếu n>1 2 n 2 n = 2(2T( )+c 2 ) + c 2 n = 4 T( ) + 2c 2 n = 2 T( ) + 2c 2 n 4 2 4 2 2 n n n 3 n = 4( 2T( )+c 2 ) + 2c 2 n = 8T( ) + 3c ...

Ví dụ 1.16. Giải phương trình truy hồi sau: T(n) = 1 nếu n =1 4T(n/2)+ n nếu n >1 Giải: Phương trình có dạng (1) với a=4, b=2 và d(n) = n. Vì d(n) = n nên dễ thấy rằng d(n) là hàm nhân và d(b) = d(2) =2< a. 2 Vậy T(n) = O( n l og 2 4 ) = O( n l og 2 2 ) ...

2.1. Néi dung kü thuËt Chương 2 KỸ THUẬT CHIA ĐỂ TRỊ Có thể nói rằng kĩ thuật quan trọng nhất, được áp dụng rộng rãi nhất để thiết kế các thuật toán có hiệu quả là kĩ thuật "chia để trị". Nội dung của nó là: Ðể ...

Mỗi bước lặp sau( sau một lần phân bố và trộn ), số phần tử p sẽ khởi động lại là : p = p * 2 . Ví dụ 2.1. Giả sử a là dãy sau: 11 34 20 8 65 25 11 45 21 70 15 20 8 Đầu tiên ta phân bố luân phiên từng phần tử của dãy a vào các dãy trung ...

= O(log 2 n) 2.2.4. Nh©n c¸c sè nguyªn lín. 1) Bài toán Cho hai số nguyên X và Y, mỗi số gồm n chữ số. Tính tích của hai số nguyên đó. 2) Ý tưởng Biểu diễn X và Y dưới dạng X = A10 n/2 + B và Y = C10 n/2 + D Trong đó A, B, C, D là các số có n/2 ...

7. Bài toán tìm cặp điểm gần nhất (láng giềng gần nhất) Trong mặt phẳng cho n điểm phân biệt. Hãy tìm hai điểm gần nhau nhất (khoảng cách Ơcolit là nhỏ nhất). Hướng dẫn: Xây dựng một thuật toán dựa trên kỹ thuật chia để trị ...

} /* Xây dựng phương án*/ for(i=1;i<=n - 1;i++) { Dsdv[i].Phuong_an:= Chon(dsdv[i].Trong_luong, W); W := W – dsdv[i].phuong_an * dsdv[i].Trong_luong; } } Trong trường hợp trọng lượng của các vật và W là các số nguyên thì ta bỏ hàm Chon(d,S) và khi đó thuật ...

For (x  V\V T ) if (b x > c[p, x]) { b x :=c[p, x]; a x :=p; } } } 3) Độ phức tạp tính toán của thuật toán Trong thuật toán ta coi phép toán tích cực là phép so sánh (bx<bp) khi tìm đỉnh có nhãn tốt nhất để bổ sung vào cây khung. Phép so sánh ...

Được kết quả (số ngày ít nhất cần tổ chức thi ). 4. Bài toán trả tiền của máy rút tiền tự động ATM. Trong máy rút tiền tự động ATM, ngân hàng đã chuẩn bị sẵn các loại tiền có mệnh giá 100.000 đồng, 50.000 đồng, 20.000 đồng ...

X i = j nghĩa là quân hậu dòng i được xếp vào cột j. Các giá trị đề cử cho x i là từ 1 đến 8. Giá trị j là được chấp nhận nếu ô (i, j) chưa bị quân hậu nào chiếu đến (quân hậu có thể ăn ngang, dọc và hai đường chéo). Để ...

Ta dùng mảng a lưu trữ các sai khác về chỉ số hàng của các ô trên so với x và dùng mảng b lưu trữ caùc sai khác về chỉ số cột của các ô trên so với y thì mảng a và mảng b sẽ được khởi tạo như sau: Mảng a: Mảng b: a[0] = 2; a[1] = 1; ...

Khoitao() { scanf(n); scanf(k); d=0; for(i=1;i<=n;i++) b[i]=0; } try(i) { for(j=1;j<=n;j++) if(b[j] 0) { c[i]=a[j]; b[j]=1; if(i k) ht(); else try(i+1); b[j]=0; } } 5. Ma phương bậc n là ma trận vuông cấp n với các phần tử là các số tự nhiên từ 1 đến n 2 thoả ...

For(j = 1; j <= n; j++) if(Cmin>C[i][j]) Cmin = C[i][j]; f * = maxint;//Gia tri toi uu f* S = 0; // Chi phi x[1] = 1; // Xuat phat tu dinh 1 } Try(i) /* xác định thành phố đến thứ i*/ { for (j = 2; j <= n; j++) if(!Daxet[j]) { x[i] = j; Daxet[j] = 1; S = S + C[x[i-1]][x[i]]; // ...

1 2 3 4 5 1  0 2 0 0 6 2 0  2 8 1 4 3 11 2  0 3 5 4 0 0 0  8 6 5 10 3 10 0  5 1 3 2 C = Tổng các hằng số rút gọn: 6 + 4 + 5 + 6 + 5 + 1 + 3 + 2 = 32. Đây là cận dưới của mọi hành trình. * Chọn cạnh phân nhánh Ta có số 0 ở hàng 5 cột 4 là số 0 ...

BÀI TẬP CHƯƠNG 5 1 2 3 4 5 6 1  5 23 6 18 5 2 4  9 12 7 11 3 16 8  5 10 7 4 6 7 9  16 21 5 15 9 18 5  30 6 8 12 7 4 28  1. Dùng thuật toán nhánh cận (bằng cách chọn cạnh phân nhánh) tìm hành trình tối ưu của người du lịch có ma trận chi phí ...

Như vậy là một giải thuật thời gian mũ, trong khi chỉ có một đa thức các bài toán con. Ðiều đó chứng tỏ rằng có những bài toán con được giải nhiều lần. Chẳng hạn: Để tính Comb(4,2) ta phải tính Comb(3,1) và Comb(3,2). Ðể tính ...

Chỉ có đường chéo chính và tam giác phía trên được dùng trong mảng M và chỉ tam giác phía trên được dùng trong mảng O. Phần tử ở hàng i cột j của mảng M lưu trữ số ít nhất các phép tính để nhân A i ×.× A j . Chẳng hạn M[2][5]=7125 ...

Mỗi giá trị c[i,j] trong bảng c[0.m, 0.n] được tính toán theo thứ tự chính là hàng; nghĩa là hàng đầu tiên của c được điền từ trái qua phải, sau đó là hàng thứ 2 .v.v. Song song với bảng c, ta tính toán một bảng b[0.m, 0.n] có giá trị ...

F[i,j]:= max(f[i-1,j - x[i]] + x[i] , f[i-1,j]) Nếu không thì f[i,j]:= f[i-1,j] Đánh giá độ phức tạp của thuật toán: 0(n.m) 3. Bài toán đường đi của người giao hàng Có một người giao hàng cần đi giao hàng tại n thành phố. Xuất phát từ một ...

} } void InPA() { int i; i = 1; while(pa[i]) { printf("%3d", pa[i]); i++; } printf("-%3d", vmax); } main() { DocDL(); QHD(); TruyVet(); InPA(); getch(); } 2. Cài đặt thuật toán quay lui giải bài toán chiếc ba lô /*Doc du lieu tu file Balo.txt Dong thu nhat ghi so ...

Int k=0; while(i && j) { if(L[i][j] L[i-1][j]) i ; if(L[i][j] L[i][j-1]) j ; if(a[i] b[j]) { c[k] = a[i]; i ; j ; k++; } } c[k] = '\0'; } void InPA() { int l; l= strlen(c); for(int i=l-1; i>=0; i ) printf("%c", c[i]); } int main() { DocDL(); puts(a); puts(b); QHD(); ...

Else Try(i+1); daxet[j] = 0; c -= matran[pa[i-1]][j]; } } void inmt() { for(int i=1; i<=n; i++) { puts(""); for(int j=0; j<=n; j++) printf("%3d", matran[i][j]); } } int main() { DocDL(); daxet[1] = 1; pa[1] = 1; c = 0; Try(2); getch(); } 7. Cài đặt thuật toán ...