Giải Thuật và Tính Độ Phức Tạp | Môn Cấu trúc dữ liệu và giải thuật - Đại học Công Nghệ Đông Á

lOMoAR cPSD| 60729183 NGUYỄN CÔNG VINH IT15K13 lOMoAR cPSD| 60729183 NGUYỄN CÔNG VINH IT15K13
 Tính độ phức tạp của thuật toán (o) - Nhập dữ liệu a,b,c lOMoAR cPSD| 60729183 NGUYỄN CÔNG VINH IT15K13 - Tính Delta = b^2-4ac
- Kiểm tra delta + delta > 0 +delta < 0 +delta = 0
2 . Tìm Tất Cả Các Số Nguyên Tố Nhỏ Hơn N
• Thiết kế cấu trúc dữ liệu lOMoAR cPSD| 60729183 NGUYỄN CÔNG VINH IT15K13 #include #include typedef struct { double a; double b; double c; } QuadraticEquation;
void solveQuadraticEquation(QuadraticEquation equation) {
double delta = equation.b * equation.b - 4 * equation.a * equation.c; if (delta > 0) {
double x1 = (-equation.b + sqrt(delta)) / (2 * equation.a); double x2 = (-equation.b - sqrt(delta)) / (2 * equation.a);
printf("Phuong trinh co 2 nghiem phan biet:\n"); printf("x1 = %f\n", x1); printf("x2 = %f\n", x2); } else if (delta == 0) {
double x = -equation.b / (2 * equation.a);
printf("Phuong trinh co nghiem kep:\n");
printf("x = %f\n", x); } else {
printf("Phuong trinh vo nghiem.\n"); } } int main() { QuadraticEquation equation;
// Thay đổ7i giá trị cu7a hệ sổ; a, b và c equation.a = 2.0; equation.b = 5.0; equation.c = -5.0;
solveQuadraticEquation(equation); return 0; } lOMoAR cPSD| 60729183 NGUYỄN CÔNG VINH IT15K13
• Cài đặt giải thuật bằng ngôn ngữ C #include #include #include #include
int* createIntegerList(int N, int* size) {
int* integerList = (int*)malloc(N * sizeof(int)); *size = 0;
for (int i = 2; i < N; i++) { bool isPrime = true;
for (int j = 2; j <= sqrt(i); j++) { if (i % j == 0) { isPrime = false; break; } } if (isPrime) { integerList[*size] = i; (*size)++; } } return integerList; }
void destroyIntegerList(int* integerList) { free(integerList); }
void printIntegerList(int* integerList, int size) {
printf("Danh sach cac so nguyen to: ");
for (int i = 0; i < size; i++) {
printf("%d ", integerList[i]); } printf("\n"); } int main() { int N; printf("Nhap N: "); lOMoAR cPSD| 60729183 NGUYỄN CÔNG VINH IT15K13 scanf("%d", &N); int size;
int* integerList = createIntegerList(N, &size); printIntegerList(integerList, size);
destroyIntegerList(integerList); return 0; }
• Tính độ phức tạp của thuật toán (o)
a) Khai báo biến N, biến size, và mảng integerList.
b) Nhập giá trị của N từ người dùng.
c) Cấp phát bộ nhớ cho mảng integerList với kích thước N.
d) Khởi tạo size bằng 0.
e) Duyệt qua các số từ 2 đến N-1:
Kiểm tra xem số hiện tại có phải là số nguyên tố hay không:
i. Đặt biến isPrime bằng true. ii. Duyệt qua
các số từ 2 đến căn bậc hai của số hiện tại:
 Nếu số hiện tại chia hết cho một số
trong khoảng này, đặt isPrime bằng
false và thoát khỏi vòng lặp.
 Nếu isPrime vẫn là true, thêm số hiện
tại vào mảng integerList và tăng size lên 1.
f) In ra danh sách các số nguyên tố từ mảng integerList.
g) Giải phóng bộ nhớ đã được cấp phát cho mảng integerList.
h) Kết thúc chương trình.