Bài ôn tập nhập môn - Công nghệ thông tin | Trường Đại học Quy Nhơn

BÀI 3 Bài 1:
Đầu vào: Mảng a gồm n số nguyên.
Đầu ra: Số hoàn thiện lớn nhất trong mảng a. Yêu cầu: 
Xác định số hoàn thiện: o
Số hoàn thiện là số nguyên dương n mà tổng các ước số dương của nó
(không bao gồm chính n) bằng n. 
Tìm số hoàn thiện lớn nhất trong mảng. Thuật toán:
Bước 1: Xác định số hoàn thiện 
Hàm kiem_tra_so_hoan_thien(n): o
Duyệt từ 1 đến n - 1. o
Kiểm tra nếu n chia hết cho từng số i từ 1 đến n /2. o
Cộng dồn các số chia hết cho n vào biến sum. o So sánh sum với n. 
Nếu sum bằng n, trả về true (số hoàn thiện). 
Nếu sum khác n, trả về false (không phải số hoàn thiện).
Bước 2: Tìm số hoàn thiện lớn nhất trong mảng 
Hàm tim_so_hoan_thien_lon_nhat(a, n): o
Khởi tạo biến max_hoan_thien bằng 0. o
Duyệt từng phần tử a[i] trong mảng. o
Kiểm tra nếu a[i] là số hoàn thiện bằng cách gọi
hàm kiem_tra_so_hoan_thien(a[i]). 
Nếu a[i] là số hoàn thiện: 
So sánh a[i] với max_hoan_thien. 
Cập nhật max_hoan_thien bằng a[i] nếu a[i] lớn hơn. o
Trả về max_hoan_thien. Chương trình: int so_hoan_hao(int n){ int sum=0; for (i=1; i<=n/2; i++) if (n%i==0) sum+=i; return sum==n; } int max(int a(), int n){ int max=0;
for (i=0; i if (so_hoan_hao(a[i])) if (a[i]>max) max=a[i]; return max; Bài 2: Đầu vào:  Mảng a gồm n số nguyên.  Mảng b gồm m số nguyên. Đầu ra: 
True nếu a là đoạn con của b, False nếu không. Yêu cầu:  Xác định đoạn con: o
Một mảng a được gọi là đoạn con của mảng b nếu tất cả các phần tử
của a xuất hiện trong b theo cùng thứ tự. o
Ví dụ: a = [1, 2, 3] là đoạn con của b = [1, 2, 3, 4]. Thuật toán:
Bước 1: Kiểm tra độ dài mảng 
Nếu n (độ dài mảng a) lớn hơn m (độ dài mảng b), a không thể là đoạn con của b. o Trả về False.
Bước 2: Duyệt mảng b và so sánh từng phần tử với mảng a 
Bắt đầu từ vị trí i đầu tiên trong mảng b. 
Duyệt từng phần tử a[j] trong mảng a. o
So sánh a[j] với phần tử b[i + j]. 
Nếu a[j] không bằng b[i + j], 
Tăng i lên 1 và quay lại bước 2.  Nếu a[j] bằng b[i + j], 
Tiếp tục so sánh các phần tử tiếp theo của a và b. 
Nếu tất cả các phần tử của a được so sánh thành công với các phần tử tương ứng của b, o a là đoạn con của b. o Trả về True.
Bước 3: Không tìm thấy đoạn con 
Nếu đã duyệt hết mảng b mà không tìm thấy đoạn con phù hợp, o
a không phải là đoạn con của b. o Trả về False. Chương trình:
int doan_con(int a(), int n, int b(), int m){ if (n>m) return 0; int i, j=0; while ((i if (a[j]!=b[i+1]){ i+=1; j=0; } else j+=1; if (j==n) return 1 else return 0; Bài 3:
Đầu vào: Mảng a gồm n số nguyên.
Đầu ra: Liệt kê các số khác nhau xuất hiện trong mảng a. Yêu cầu: 
Sắp xếp các số theo thứ tự tăng dần. 
Chỉ in ra các số khác nhau, không in số trùng lặp. Thuật toán:
Bước 1: Sắp xếp mảng 
Sử dụng thuật toán sắp xếp để sắp xếp các phần tử trong mảng a theo thứ tự tăng dần.
Bước 2: Liệt kê các số khác nhau 
Khởi tạo biến i bằng 0 và biến flag bằng True. 
Lặp từ i đến n - 1. o
Kiểm tra nếu a[i] bằng a[i + 1]. 
Nếu bằng nhau, gán flag bằng False.  Nếu khác nhau:  In ra a[i].  Gán flag bằng True. o
Cập nhật i bằng i + 1.  Kiểm tra flag. o
Nếu flag bằng True, in ra a[n - 1]. Chương trình: def sap_xep_mang(a, n): for i in range(n - 1): for j in range(i + 1, n): if a[i] > a[j]: a[i], a[j] = a[j], a[i]
def liet_ke_so_khac_nhau(a, n): sap_xep_mang(a, n) i = 0 flag = True while i < n - 1: if a[i] == a[i + 1]: flag = False else: print(a[i]) flag = True i += 1 if flag: print(a[n - 1]) BÀI 4 Bài 4: Chương trình: Int doi_xung(int a(), int n){ Int i=0; j=n-1; While iif a[i] != a[j]{ return 0; i += 1; j -= 1; } return 1; }
Để đánh giá độ phức tạp của hàm doi_xung, chúng ta cần xem xét các bước trong hàm này:
1. Khởi tạo biến i và j có độ phức tạp là O(1).
2. Vòng lặp while i < j được thực hiện cho đến khi i không còn nhỏ hơn j. Trong
trường hợp xấu nhất, vòng lặp này cần thực hiện khoảng n/2 lần, với n là kích thước của mảng.
3. Trong mỗi lần lặp, ta thực hiện một số thao tác cố định bao gồm kiểm tra a[i] có
bằng a[j] không và cập nhật giá trị của i và j. Cả hai thao tác này đều có độ phức tạp là O(1).
Do đó, tổng độ phức tạp của hàm doi_xung là O(n/2) trong trường hợp xấu nhất. Bài 5: Chương trình: Int laSNT(int n){ If (n<=2) Return (n==2)
Else for (int i=2; i If (n%i==0) Return 0; } Return 1; }
Để đánh giá độ phức tạp của hàm laSNT, chúng ta cần xem xét từng bước trong hàm này:
1. Kiểm tra điều kiện if (n <= 2) và trả về kết quả ngay lập tức nếu n nhỏ hơn hoặc
bằng 2. Điều này có độ phức tạp là O(1).
2. Trong trường hợp n > 2, chúng ta sẽ duyệt qua một vòng lặp for từ i = 2 đến
sqrt(n). Trong trường hợp xấu nhất, vòng lặp này cần thực hiện tới sqrt(n) lần. Vì
sqrt(n) là một số lượng lớn nhất khi n là một số nguyên tố, do đó vòng lặp này có
độ phức tạp là O(sqrt(n)).
3. Trong mỗi lần lặp, chúng ta thực hiện một số phép toán cố định bao gồm kiểm tra
n % i == 0 và cập nhật giá trị của i. Cả hai thao tác này đều có độ phức tạp là O(1).
Tổng độ phức tạp của hàm laSNT sẽ là O(1) trong trường hợp n nhỏ hơn hoặc bằng 2 và
O(sqrt(n)) trong trường hợp n > 2. Bài 6: Chương trình: int so_hoan_hao(int n){ int sum=0; for (i=1; i<=n/2; i++) if (n%i==0) sum+=i; return sum==n; } Void lietke(int n){ For (int i=1; i<=n; i++) If (so_hoan_hao(i)) Printf(“%d”, i);
Để đánh giá độ phức tạp của hàm so_hoan_hao và lietke, chúng ta cần xem xét từng hàm một: 1. Hàm so_hoan_hao: 
Trong hàm này, chúng ta có một vòng lặp for chạy từ 1 đến n/2, do đó vòng lặp
này sẽ thực hiện khoảng n/2 lần. 
Trong mỗi lần lặp, chúng ta có một phép chia và một phép cộng, cả hai đều có độ phức tạp là O(1). 
Do đó, tổng độ phức tạp của hàm so_hoan_hao là O(n/2), nhưng trong phân tích
độ phức tạp chúng ta thường bỏ qua hằng số và các thành phần không quan trọng,
nên kết quả cuối cùng vẫn là O(n). 2. Hàm lietke: 
Trong hàm này, chúng ta có một vòng lặp for chạy từ 1 đến n, do đó vòng lặp này
sẽ thực hiện n lần. 
Trong mỗi lần lặp, chúng ta gọi hàm so_hoan_hao, có độ phức tạp là O(n). 
Do đó, tổng độ phức tạp của hàm lietke sẽ là O(n^2).
Tóm lại, độ phức tạp của hàm so_hoan_hao là O(n), và độ phức tạp của hàm lietke là O(n^2). Bài 7: Chương trình:
Void tim2so(int a(),int n, int sum){
For (int i=0; iFor (j=i+1; j If (a[i]+a[j]==sum)
Printf(“%d%d”,a[i], a[j]);
Hàm tim2so trong mã của bạn có mục tiêu tìm và in ra các cặp số từ mảng sao cho tổng
của chúng bằng một số sum. Để đánh giá độ phức tạp của hàm này, ta cần xem xét từng phần tử:
1. Vòng lặp for bên ngoài (i từ 0 đến n - 2): Độ phức tạp của vòng lặp này là O(n),
với n là số lượng phần tử trong mảng.
2. Trong mỗi vòng lặp for ngoài, có một vòng lặp for bên trong (j từ i + 1 đến n - 1):
Vòng lặp này cũng có độ phức tạp là O(n) trong trường hợp xấu nhất.
3. Trong mỗi lần lặp của vòng lặp bên trong, ta có một câu lệnh kiểm tra và một câu
lệnh in ra cặp số, cả hai đều có độ phức tạp là O(1).
Tổng độ phức tạp của hàm tim2so là O(n^2), với n là số lượng phần tử trong mảng. Điều
này xuất phát từ việc có hai vòng lặp lồng nhau, mỗi vòng lặp có thời gian chạy tuyến
tính theo kích thước của mảng đầu vào. Bài 8: Chương trình: Void lietke(int n, char s[]){ If (n==0) Printf(“%s\n”, s); Else { S[n-1]=’0’; lietke(n-1, s); s[n-1]=’1’; lietke(n-1, s); } }
Hàm lietke trong mã của bạn sử dụng phương pháp đệ quy để liệt kê tất cả các dãy nhị
phân có độ dài n. Đây là một cách tiếp cận khác so với cách triển khai trước đó, nhưng
vẫn là một phương pháp hợp lệ. Hãy xem xét độ phức tạp của hàm này: 
Trong mỗi lần gọi đệ quy, chúng ta thực hiện hai cuộc gọi đệ quy: một với s[n - 1]
được thiết lập thành '0' và một với s[n - 1] được thiết lập thành '1'. Do đó, số lần gọi đệ quy là 2^n. 
Trong mỗi cuộc gọi đệ quy, chúng ta thực hiện một số thao tác cố định bao gồm
gán giá trị cho phần tử trong mảng s và cuộc gọi đệ quy tiếp theo. 
Độ phức tạp của mỗi cuộc gọi đệ quy là O(1), vì chúng ta chỉ thực hiện một số thao tác cố định.
Tổng độ phức tạp của hàm lietke là O(2^n), với n là độ dài của dãy nhị phân. Đây là một
độ phức tạp tốt đối với vấn đề này.