tailieunhanh - 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), 1i. | 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 m n 70. Tính số cách chia phần thưởng. Cách phát biểu khác của bài toán Có m phần thưởng được chia cho n học sinh giỏi được xếp hạng thừ 1 đến n. Tính số cách chia phần thưởng sao cho thỏa các điều kiện sau Số phần thưởng của học sinh hạng i phải lớn hơn hoặc bằng số phần thưởng của học sinh hạng j nếu j i. Tất cả phần thưởng đều phải được thưởng hết cho học sinh. Ví dụ Có 7 phần thưởng chia cho 4 học sinh sẽ có 11 cách chia sau Cách chia HS 1 HS2 HS3 HS 4 1 7 0 0 Ũ 2 6 1 0 Ũ 3 5 2 Ũ ũ 4 5 1 1 ũ 5 4 3 0 ũ B 4 2 1 ũ ĩ 4 1 1 1 8 3 3 1 ũ 8 3 2 2 ũ 1Q 3 2 1 1 11 2 2 2 1 1. Phương pháp quy hoạch động Gọi C i j là số các chia i phần thưởng cho j học sinh ta có một số nhận xét sau 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 i . Nếu số phần thưởng i nhiều hơn hoặc bằng số học sinh j thì có 2 trường hợp TH1 người cuối cùng không có phần thưởng tức là chỉ chia i phần thưởng cho j-1 người trường hợp này số cách chia là C i j-1 . TH2 người cuối cùng chắc chắn có phần thưởng khi đó ta sẽ lấy j phần thưởng chia cho j người mỗi người sẽ có được 1 phần thưởng trước lúc này còn lại i-j phần thưởng tiếp tục lấy số còn lại này chia cho j người trường hợp này số cách chia là C i-j j . Như 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 OF LONGINT m n i j INTEGER BEGIN