Bài toán chia phần thưởng

Chia sẻ: Abcdef_45 Abcdef_45 | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

965
lượt xem 43
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Cần chia hết m phần thưởng cho n học sinh sắp theo thứ tự từ giỏi trở xuống sao cho mỗi bạn nhận được phần thưởng không ít hơn phần thưởng của bạn xếp sau mình (có thể số phần thưởng = 0), 1i.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài toán chia phần thưởng

Bài toán chia phần thưởng Cần chia hết m phần thưởng cho n học sinh sắp theo thứ tự từ giỏi trở xuống sao cho mỗi bạn nhận được phần thưởng không ít hơn phần thưởng của bạn xếp sau mình (có thể số phần thưởng = 0), 1
Có i phần thưởng mà chia cho 0 học sinh thì có 0 cách chia (vì không thỏa  điều kiện: Tất cả phần thưởng đều phải được thưởng hết cho học sinh). Vậy với mọi i, C[i,0]=0. Có 0 phần thưởng mà chia cho j học sinh thì có 1 cách chia (không ai có  phần thưởng cả). Vậy với mọi j, C[0,j]=1. Nếu số phần thưởng (i) ít hơn số học sinh (j) thì những học sinh thứ i+1 đến  j sẽ không có phần thưởng, do đó số cách chia i phần thưởng cho j người sẽ bằng số cách chia i phần thưởng cho i người . Vậy với mọi i=j, C[ i ] [ j ] = C[ i ][ j-1 ] + C[ i-j ][ j ]. Cài đặt bằng ngôn ngữ Pascal: PROGRAM chia_phan_thuong; VAR C:ARRAY[0..70,0..70] OF LONGINT;
m,n,i,j:INTEGER; BEGIN write('So phan thuong: '); readln(m); write('So hoc sinh: '); readln(n); FOR i:=1 TO m DO C[i,0]:=0; FOR j:=1 TO n DO C[0,j]:=1; FOR i:=1 TO m DO FOR j:=1 TO n DO IF i
int main() { cin>>m>>n; int i,j; for (i=1; i
P:ARRAY[0..70] OF LONGINT; PROCEDURE Chia(i,j:LONGINT); {Chia i phan thuong cho nhung nguoi tu vi tri thu j} VAR k:INTEGER; BEGIN IF (j>n) THEN {Da xet xong n nguoi} BEGIN IF i=0 THEN {Chia het toan bo phan thuong} BEGIN inc(r);{Tang so cach chia} FOR k:=1 TO n DO write(P[k],' ');{Xuat ra mot cach chia} writeln; END; END ELSE FOR k:=P[j-1] DOWNTO 0 DO {So phan thuong cua nguoi sau phai nho hon hoac bang cua nguoi truoc} IF i-k>=0 THEN {So phan thuong con lai phai khong am} BEGIN
P[j]:=k; Chia(i-k,j+1); {Chia so phan thuong con lai cho nhung nguoi sau.} END; END; BEGIN readln(m,n); r:=0; P[0]:=m; Chia(m,1); writeln('Co ',r,' cach chia!'); readln; END. Cài đặt bằng ngôn ngữ C++ #include using namespace std; int m,n,r; int P[71]; void Chia(int m, int n)
{ if (n>::n) { if (m==0) { r++; for (int i=1; i
{ cin>>m>>n; r=0; P[0]=m; Chia(m,1); cout