DE CUONG MON PTTKGT NE BO CON

Trường Đại học Sư phạm Tp.HCM
Khoa Toán – Tin học

ĐỀ THI HẾT HỌC PHẦN

Môn thi: Phân tích thiết kế giải thuật - Đề thi lần 1
Thời gian: 90 phút
GV ra đề: Trần Hữu Quốc Thư
Chú ý:
Sinh viên được sử dụng tài liệu
SV chỉ sử dụng ngôn ngữ C/C++ hoặc Pascal

Bài 1.
Cho doạn chương trình sau:
float Gtri(int n)
{
1 e=0;
2 for (i=1; i <=n; ++i)
3 {
4 gt = 1;
5 for (j=1; j<i; ++j)
6 gt = gt * j;
7 e:= e + (2*i -1) /gt;
8 }
9 return e;
}
Anh/Chị hãy:
a. Anh chị hãy đếm số phép gán và phép so sánh (HD: chuyển lệnh for sang while, rồi đếm)
b. Dùng qui tắc cộng và nhân, anh/chị hãy tính độ phức tạp
c. Tối ưu hoá chương trình trên

Bài 2. Bài toán chia kẹo
Cho n gói kẹo (n<=50). Gói thứ i có A[i] viên kẹo. Cần chia các gói kẹo này cho 2 em bé sao cho tổng số viên kẹo mỗi em nhận được chênh lệch là ít nhất. Mỗi em nhận được nguyên gói. Không mở gói kẹo ra để chia lại. Hãy liệt kê số kẹo trong các gói kẹo mỗi em nhận được.
Input Output
n
A[1] A[2] A[3] ... A[n] Dòng 1: Chứa 2 số M và L, với M là số lượng túi kẹo thuộc phần của em bé thứ nhất và L là số chênh lệch.
Dòng 2: Chứa m số là số hiệu (chỉ số) của các túi kẹo thuộc phần này.
Ví dụ:
Input Output
4
1 2 3 4 2 0
1 4

Yêu cầu:
d. Anh chị hãy đưa ra cách giải quyết bài toán chia kẹo ở trên
e. Với mẫu dữ liệu ở trên (phần ví dụ) anh/chị hãy áp dụng vào cách giải quyết của anh/chị ở câu a)
Bài 3. Xét định nghĩa số tổ hợp chập k của n như sau:

Viết một hàm đệ qui để tính tổ hợp n chập k theo công thức trên. Tính thời gian thực hiện của giải thuật đó

NHO THANK 1 CÁI HEN!
CHÚC BÀ CON ÔN THI TỐT NHA!

Diễn đàn mình mà có thanks thì thanks rồi nhưng mà không có thanks nên đành spam vậy!! Lời to!!

NguyenQuocViet wrote:Diễn đàn mình mà có thanks thì thanks rồi nhưng mà không có thanks nên đành spam vậy!! Lời to!!

troi oi ! tui dang lam nham cai gi vay ne ?

trời ơi mấy bác không thank thì thui chứ làm gì mà chửi rủa ghê vậy?
đề nghị không spam bậy bạ

TranLeTai wrote:trời ơi mấy bác không thank thì thui chứ làm gì mà chửi rủa ghê vậy?
đề nghị không spam bậy bạ

Có ai chửi rủa gì đâu nè! Cũng đâu có spam đâu tại nó không có nút thanks chứ bộ!! Vậy thanks nha!! Lại lời nữa )

lớp trưởng nhiệt tình thiệt cảm ơn lớp trưởng nhiều nha

chúc cả lớp thi tốt