Chia thưởng



Chia 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 không nhận ít phần thưởng hơn bạn xếp sau mình.
1 £m, n £ 70.
Hãy tính số cách chia.
Thí dụ, với số phần thưởng m= 7, và số học sinh n = 4 sẽ có 11 cách chia 7 phần thưởng cho 4 học sinh theo yêu cầu của đầu bài. Đó là:

Phương án
j
k
l
m
1
7
0
0
0
2
6
1
0
0
3
5
2
0
0
4
5
1
1
0
5
4
3
0
0
6
4
2
1
0
7
3
3
1
0
8
3
2
2
0
9
4
1
1
1
10
3
2
1
1
11
2
2
2
1
Bài giải
1. Lp h thc
Gi Chia(i, j) là s cách chia i phn thưởng cho j hc sinh, ta thy:
-       Nếu không có hc sinh nào (j= 0) thì không có cách chia nào (Chia = 0).
-       Nếu không có phn thưởng nào (i = 0) thì ch có mt cách chia (Chia(0,j) = 1 - mi hc sinh nhn 0 phn thưởng). Ta cũng quy ước Chia(0, 0) = 1.
-       Nếu s phn thưởng ít hơn s hc sinh (i < j) thì trong mi phương án chia, t hc sinh th i + 1 tr đi skhông được nhn phn thưởng nào:
Chia(i, j) = Chia(i, i) nếu i < j.
Ta xét tt c các phương án chia trong trường hp i ³ j. Ta tách các phương án chia thành hai nhóm không giao nhau da trên s phn thưởng mà hc sinh đứng cui bng thành tích, hc sinh th j, được nhn:
-       Nhóm th nht gm các phương án trong đó hc sinh th j không được nhn thưởng, tc là i phn thưởng ch chia cho j - 1 hc sinh và do đó, s cách chia, tc là s phn t ca nhóm này s là: Chia(i, j- 1).
-       Nhóm th hai gm các phương án trong đó hc sinh th j cũng được nhn thưởng. Khi đó, do hc sinh đứng cui bng thành tích được nhn thưởng thì mi hc sinh khác cũng s có thưởng. Do ai cũng được thưởng nên ta bt ca mi người mt phn thưởng (để h lĩnh sau), s phn thưởng còn li (i - j) s được chia cho j hc sinh. S cách chia khi đó s là Chia(i - j, j).
Tng s cách chia cho trường hp i ³ j s là tng s phn t ca hai nhóm, ta có:
Chia(i, j) = Chia(i, j - 1) + Chia(i - j, j).
Tng hp li ta có:

Điều kiện
i: số phần thưởng
j: số học sinh
Chia(i, j)
j = 0
Chia(i, j) = 0
i = 0 and j ¹ 0
Chia(i, j) = 1
i < j
Chia(i, j) = Chia(i, i)
i ³ j
Chia(i, j) = Chia(i, j – 1) + Chia(i – j, j)
Các tính chất của hàm Chia(i, j)
Chia i phần thưởng cho j học sinh
2. T chc dliu và chương trình
Ta có phương án đầu tiên ca gii thut Chia như sau:
(*-------------------------------------
PHUONG AN 1: de quy.
So cach Chia i phan thuong cho j hs
--------------------------------------*)
function Chia(i,j: integer):longint;
begin
if j = 0 then Chia := 0
    else {j > 0 }
   if i = 0 then {i = 0; j > 0 }
       Chia := 1
       else {i,j > 0 }
         if i < j then {0 < i < j }
            Chia  :=  Chia(i,i)
           else {i >= j > 0 }
               Chia  :=  Chia(i,j-1)+Chia(i-j,j);
end;


t
u
v
w
x
i
0
9
1
1
0
j
9
9
2
1
0
k
6
6
1
0
0
l
5
5
2
1
1
m
3
3
1
1
0
n
2
2
1
0
0
o
1
1
0
0
0
p
1
1
1
1
1
Số lần gọi hàm Chia cục bộ
khi  tính hàm Chia(p,x)
Phương án này chy chm vì phát sinh ra quá nhiu ln gi hàm trùng lặp. Bng dưới đây lit kê s ln gi hàm Chia khi gii bài toán chia thưởng vi by phn thưởng (m = 7) và 4 hc sinh (n = 4). Thí d, hàm Chia(1,1) s được gi 9 ln,… Tng s ln gi hàm Chia là 79. 79 ln gi hàm để sinh ra kết qu 11 là quá tốn kém.
Làm tt ln 1: Phương án 1 khá d trin khai nhưng chương trình s chy rt lâu, bn hãy th gi Chia(66,32) để trải nghiệm được điu trên. Din t đệ quy thường trong sáng, nhàn tn, nhưng khi thc hin s sinh ra hin tượng gi lp li nhng hàm đệ quy. Ci tiến đầu tiên là tránh nhng ln gi lp như vy. Mun thế chúng ta tính sn các giá tr ca hàm theo các tr ca đầu vào khác nhau và đin vào mt mng hai chiu cc.
Mng cc được mô t như sau:


  j - 1
 j






 i - j


[i-j,j]

...


...

i

[i,j-1]
[i,j]






const
MN = 70;{ gioi han tren cua m va n }
type
ml1 = array[0..MN] of longint;
ml2 = array[0..mn] of ml1;
var cc: ml2;
 Ta quy ước cc[i, j] chứa s cách chia i phn thưởng cho j hc sinh.
Theo phân tích ca phương án 1, ta có:
s         cc[0, 0] = 1; cc[i, 0] = 0, với i:=1..m.
s         cc[i, j] = cc[i, i], nếu i < j
s         cc[i, j] = cc[i, j-1]+cc[i-j, j], nếu i ³ j.
T đó ta suy ra quy trình đin tr vào bng cc như sau:
s         Khi tr  
s         cc[0,0 ]:= 1;
s         với i  :=  1..m: cc[i,0] :=  0;
s         Đin bng: Ln lượt đin theo tng ct j:= 1..n. Ti mi ct j ta đặt:
s         với i := 0..j-1: cc[i,j] :=  cc[i,i];
s         với i :=  j..m: cc[i,j] := cc[i,j-1]+cc[i-j,j];
Nhn kết qu: Sau khi đin bng, giá tr cc[m, n] chính là kết qu cn tìm.
(*-------------------------------------
PHUONG AN 2: dung mang 2 chieu cc
cc[i,j] = Chia(i,j) - so cach chia i
 phan thuong cho j hs
-------------------------------------*)
function Chia2(m,n: integer):longint;
var i,j: integer;
begin
cc[0,0] :=  1;
for i := 1 to m do cc[i,0] := 0;
for j := 1 to n do
begin
for i :=  0 to j-1 do cc[i,j] :=  cc[i,i];
for i :=  j to m do
   cc[i,j] :=  cc[i,j-1]+cc[i-j,j];
end;
Chia2 := cc[m,n];
end;
Làm tt ln 2: Dùng mng hai chiu chúng ta ch có th tính toán được vi d liu nh. Bước ci tiến sau đây khá quan trng: chúng ta dùng mng mt chiu. Quan sát kĩ quy trình gán tr cho mng hai chiu theo tng ct chúng ta d phát hin ra rng ct th j có th được tính toán t ct th j - 1. Nếu gi c là mng mt chiu sdùng, ta cho s hc sinh tăng dn bng cách ln lượt tính j bước, vi j := 1..n. Ti bước th j, c[i] chính là s cách chia iphn thưởng cho j hc sinh. Như vy, ti bước th j ta có:
-          c[i] tại bước j = c[i] tại bước (j – 1), nếu i < j. T đây suy ra đon c[0..(j – 1)] được bo lưu.
-          c[i] tại bước j  = c[i] tại bước (j – 1) + c[i j] tại bước j, nếu i ³ j.
Biu thc th hai cho biết khi cp nht mng c t bước th j – 1 qua bước th j ta phi tính t trên xung, nghĩa là tính dn theo chiu tăng ca i :=  j..m.
Mng c được khi tr bước j = 0 như sau:
-          c[0] = 1; c[i] = 0, vi i :=  1..m.
Vi ý nghĩa là, nếu có 0 hc sinh thì chia 0 phn thưởng cho 0 hc sinh s được quy định là 1. Nếu s phn thưởng m khác 0 thì chia m phn thưởng cho 0 hc sinh s được 0 phương án.
Ta có phương án ba, dùng mt mng mt chiu c như sau:
(*----------------------------------------
      PHUONG AN 3: dung mang 1 chieu c
      Tai buoc j, c[i] = so cach chia i
      phan thuong cho j hoc sinh.
-----------------------------------------*)
function Chia1(m,n: integer):longint;
var i,j: integer;
begin
fillchar(c,sizeof(c),0);
c[0] := 1;
for j := 1 to n do
for i  :=  j to m do c[i] :=  c[i]+c[i-j];
Chia1  :=  c[m];
end;
Để so sánh các phương án bn hãy đặt mt b đếm nhp ca máy như sau:
nhip: longint absolute $0000:$046c;
{xac dinh nhip thoi gian }
t: longint; {ghi nhan nhip }
Sau đó bạn to mt dữ liệu kiểm thử để so sánh ba phương án đã phân tích phần trên như sau:
procedure test;
begin
randomize; {Khoi dong bo sinh so ngau nhien }
repeat
m := random(mn)+1; {sinh ngau nhien so phan thuong m }
n := random(mn)+1; {sinh ngau nhien so hs n }
writeln(m,bl,n); {xem du lieu vao }
t := Nhip; {dat nhip cho PA 3 }
{Phuong an 3 }
writeln('Mang 1 chieu: ',Chia1(m,n));
{bao thoi gian }
writeln((Nhip-t)/18.2):0:0,' giay');
t := Nhip;  {dat nhip cho PA 2}
writeln('Mang 2 chieu: ',Chia2(m,n)); {PA 2 }
{bao thoi gian }
writeln((Nhip-t)/18.2):0:0,' giay');
t := Nhip;  {dat nhip cho PA 1 }
writeln('De quy: ',Chia(m,n));
{bao tgian}
writeln((Nhip-t)/18.2):0:0,' giay');
until readkey = #27; {lap den khi bam ESC }
end;
Các giá tr m – số phần thưởng và n – số học sinh được sinh ngu nhiên nh hàm random. Trước đó cn gi th tc randomize để chun b khi to b sinh s ngu nhiên.
Trong b nh ca máy tính có 4 byte bt đầu t địa ch $0000:$046c dùng để ghi s nhp ca máy tính. Mi ln đọc giá tr ca biến Nhip ta có th ly được s nhp hin hành ca máy. Hiu s hai ln đọc nhp liên tiếp s cho ta tng s nhp tính t ln đọc th nht đến ln đọc th hai. Chia giá tr này cho 18.2 ta có th quy ra lượng thi gian chy máy tính bng giây. Lệnh write(r:d:p)hiển thị số thực r với d vị trí và p chữ số sau dấu phẩy. Nếu đặt d= p = 0 thì số thực r sẽ được hiển thị đầy đủ.
(*  Pascal  *)
uses crt;
const
 MN = 70; {gioi han tren cua m va n }
 nl = #13#10; {xuong dong }
 bl = #32; {dau cach }
type
 ml1 = array[0..MN] of longint;
 ml2 = array[0..mn] of ml1;
var
 cc: ml2; {cho phuong an 2 - mang 2 chieu }
 m,n: integer;
 c: ml1; {cho phuong an 3 – mang 1 chieu }
 nhip: longint absolute $0000:$046c;
{xac dinh nhip thoi gian }
t: longint; {ghi nhan nhip }
(*-------------------------------------
          PHUONG AN 1: de quy
So cach Chia i phan thuong cho j hs
--------------------------------------*)
function Chia(i,j: integer):longint; tự viết
(*-------------------------------------
PHUONG AN 2: dung mang 2 chieu cc
cc[i,j] = so cach chia i phan thuong
          cho j hs
-------------------------------------*)
function Chia2(m,n: integer):longint;  tự viết
(*----------------------------------------
      PHUONG AN 3: dung mang 1 chieu c
      Tai buoc j, c[i] = so cach chia i
      phan thuong cho j hoc sinh.
-----------------------------------------*)
function Chia1(m,n: integer):longint;  tự viết
procedure test;  tự viết
BEGIN
Test;
END.
Quan sát hot động ca chương trình bn s rút ra được ý nghĩa ca các phương án ci tiến.
Chú thích
               Bài toán trên còn có cách phát biu khác như sau: Hãy tính s cách biu din s t nhiên m thành tng ca n s tnhiên sp theo trt t không tăng. Thí d, vi m = 7, n = 4 ta có:
7 = 7 + 0 + 0 + 0 = 6 + 1 + 0 + 0 = ...

Không có nhận xét nào:

Đăng nhận xét