DE CUONG MON PTTKGT NE BO CON

Go down

DE CUONG MON PTTKGT NE BO CON

Post  TranLeTai on Sun Jun 29, 2008 5:00 pm

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 tŕ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 tŕ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] Ḍ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.
Ḍ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! sunny sunny sunny
CHÚC BÀ CON ÔN THI TỐT NHA!
avatar
TranLeTai

Posts : 46
Join date : 2008-04-09

View user profile

Back to top Go down

Re: DE CUONG MON PTTKGT NE BO CON

Post  NguyenQuocViet on Tue Jul 01, 2008 1:52 pm

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!! lol!
avatar
NguyenQuocViet

Posts : 105
Join date : 2008-04-08
Age : 31

View user profile http://tuoitrenangdong.net

Back to top Go down

Re: DE CUONG MON PTTKGT NE BO CON

Post  anh truc on Tue Jul 01, 2008 8:40 pm

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!! lol!
troi oi ! tui dang lam nham cai gi vay ne ?
avatar
anh truc

Posts : 14
Join date : 2008-04-10

View user profile

Back to top Go down

Re: DE CUONG MON PTTKGT NE BO CON

Post  TranLeTai on Fri Jul 04, 2008 8:19 pm

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

Posts : 46
Join date : 2008-04-09

View user profile

Back to top Go down

Re: DE CUONG MON PTTKGT NE BO CON

Post  NguyenQuocViet on Mon Jul 07, 2008 1:36 am

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

Có ai chửi rủa ǵ đâ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 Wink)
avatar
NguyenQuocViet

Posts : 105
Join date : 2008-04-08
Age : 31

View user profile http://tuoitrenangdong.net

Back to top Go down

Re: DE CUONG MON PTTKGT NE BO CON

Post  nguyenhoanganh on Sat Jul 12, 2008 9:44 pm

lớp trưởng nhiệt t́nh thiệt cảm ơn lớp trưởng nhiều nha
Shocked
chúc cả lớp thi tốt
avatar
nguyenhoanganh

Posts : 74
Join date : 2008-04-08
Age : 31

View user profile

Back to top Go down

Re: DE CUONG MON PTTKGT NE BO CON

Post  Sponsored content


Sponsored content


Back to top Go down

Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum