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. Lập
hệ thức
Gọi Chia(i, j) là số cách chia i phần thưởng cho j học sinh, ta thấy:
- Nếu không có học sinh nào (j
= 0) thì không có cách chia nào (Chia = 0).
-
Nếu không có phần thưởng nào (i =
0) thì chỉ có một cách chia (Chia(0,j) = 1 - mỗi học sinh nhận 0 phần thưởng). Ta cũng quy ước Chia(0, 0) = 1.
-
Nếu số phần thưởng ít hơn số học sinh (i < j) thì trong mọi phương án chia, từ học sinh thứ i + 1 trở đi sẽ
không được nhận phần thưởng nào:
Chia(i, j) = Chia(i, i) nếu i < j.
Ta xét tất cả các phương án chia trong trường hợp i ³ j. Ta tách các phương án chia
thành hai nhóm không giao nhau dựa trên số phần thưởng mà học sinh đứng cuối bảng
thành tích, học sinh thứ j, được nhận:
-
Nhóm thứ nhất gồm các
phương án trong đó học sinh thứ j không được
nhận thưởng, tức là i phần thưởng chỉ chia cho j -
1 học sinh và
do đó, số cách chia, tức là số phần tử của nhóm này sẽ là: Chia(i, j
- 1).
-
Nhóm thứ hai gồm các phương án trong đó học sinh thứ j cũng được nhận thưởng. Khi đó, do học sinh đứng cuối bảng
thành tích được nhận thưởng thì mọi học sinh khác cũng sẽ có thưởng. Do ai cũng được thưởng nên ta bớt của mỗi người một phần thưởng (để họ lĩnh
sau), số phần thưởng còn lại (i - j)
sẽ được chia cho j học sinh. Số cách chia
khi đó sẽ là Chia(i - j, j).
Tổng số cách chia cho trường hợp i ³ j sẽ là tổng số phần tử của hai nhóm, ta có:
Chia(i, j) = Chia(i, j - 1) + Chia(i - j, j).
Tổng hợp lại 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ổ chức dữ
liệu và chương trình
Ta có phương án đầu tiên của giải thuật 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 chạy chậm vì phát sinh ra quá nhiều lần gọi hàm
trùng lặp. Bảng dưới đây liệt kê số lần gọi hàm Chia khi giải bài toán
chia thưởng với bảy phần thưởng (m = 7) và 4 học sinh (n = 4). Thí dụ, hàm Chia(1,1) sẽ được gọi 9 lần,… Tổng số lần gọi hàm Chia là 79. 79 lần gọi hàm để sinh ra kết quả 11 là quá tốn kém.
Làm tốt lần 1: Phương án 1 khá dễ triển khai nhưng chương trình sẽ chạy rất lâu, bạn hãy thử gọi Chia(66,32) để trải nghiệm được điều trên. Diễn tả đệ quy thường trong sáng, nhàn tản, nhưng khi thực hiện sẽ sinh ra hiện tượng gọi lặp lại những hàm đệ quy. Cải tiến đầu tiên là tránh những lần gọi lặp như vậy. Muốn thế chúng ta tính sẵn các giá trị của hàm theo các trị của đầu vào khác nhau và điền vào một mảng hai chiều cc.
Mảng 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 phần thưởng cho j học sinh.
Theo phân tích của 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 điền trị vào bảng cc như sau:
s
Khởi
trị
s
cc[0,0
]:= 1;
s
với i
:= 1..m: cc[i,0] := 0;
s
Điền bảng: Lần lượt điền theo từng cột j:= 1..n. Tại mỗi cột 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];
Nhận kết quả: Sau khi điền bảng, giá trị cc[m,
n] chính là kết quả cần 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 tốt
lần 2: Dùng mảng hai chiều chúng ta chỉ có thể tính toán được với dữ liệu nhỏ. Bước cải tiến sau đây khá quan trọng: chúng ta
dùng mảng một chiều. Quan sát kĩ quy trình
gán trị cho mảng hai chiều theo từng cột chúng ta dễ phát hiện ra rằng cột thứ j có thể được
tính toán từ cột thứ j - 1. Nếu gọi c là mảng một chiều sẽ
dùng, ta cho số học sinh tăng dần bằng
cách lần lượt tính j bước, với j := 1..n. Tại bước thứ j, c[i] chính là số cách chia i
phần thưởng cho j học sinh. Như vậy, tại 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 đoạn c[0..(j – 1)] được bảo 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.
Biểu thức thứ hai cho biết khi cập nhật mảng c từ bước thứ j – 1 qua bước thứ j ta phải tính từ trên xuống, nghĩa là tính dần theo chiều tăng của i := j..m.
Mảng c được khởi trị ở bước j = 0 như sau:
-
c[0] = 1; c[i] = 0, với i := 1..m.
Với ý nghĩa là, nếu có 0 học sinh thì
chia 0 phần thưởng cho 0 học sinh sẽ được quy định là 1. Nếu số phần thưởng m khác 0
thì chia m phần thưởng cho 0 học sinh sẽ được 0 phương án.
Ta có phương án ba, dùng một mảng một chiều 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 bạn hãy đặt một bộ đếm nhịp của máy như sau:
nhip: longint absolute $0000:$046c;
{xac dinh nhip thoi gian }
t: longint; {ghi nhan nhip }
Sau đó bạn tạo một 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 ngẫu nhiên nhờ hàm random. Trước đó cần gọi thủ tục randomize để chuẩn bị khởi tạo bộ sinh số ngẫu nhiên.
Trong bộ nhớ của máy
tính có 4 byte bắt đầu từ địa chỉ $0000:$046c dùng để ghi số nhịp của máy tính. Mỗi lần đọc giá trị của biến Nhip ta có thể lấy được số nhịp hiện hành của máy. Hiệu số hai lần đọc nhịp liên tiếp sẽ cho ta tổng số nhịp tính từ lần đọc thứ nhất đến lần đọc thứ hai. Chia giá trị này cho
18.2 ta có thể quy ra lượng thời gian chạy máy tính bằng 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 hoạt động của chương trình bạn sẽ rút ra được ý nghĩa của các phương án cải tiến.
Chú thích
Bài toán trên
còn có cách phát biểu khác như sau: Hãy tính số cách biểu diễn số tự nhiên m thành tổng của n số tự
nhiên sắp theo trật tự không tăng. Thí dụ, với 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