Chia mảng tỉ lệ 1:k - gia sư tin học, dạy pascal nâng cao.
Tìm cách chia dãy số nguyên không âm a1, a2,...,an, n > 1 cho trước thành hai đoạn có tổng các phần tử trong một đoạn gấp k lần tổng các phần tử trong đoạn kia, k nguyên dương.
Đặc tả
Gọi t là tổng các phần tử của dãy a,
t = sum(a[1..n])
Muốn chia a thành hai đoạn a[1..i] và a[i
+ 1..n] có tổng gấp nhau k lần ta phải có:
1. t chia hết cho (k + 1).
Đặt t1 = t div (k + 1) và tk = t
- t1.
2. (#E i: 1 <= i
<= n): sum(a[1..i]) = t1 hoặc sum(a[1..i]) = tk.
Để ý rằng nếu k = 1 thì t1 = tk; nếu k > 1 thì t1 < tk, do đó bài này
là trường hợp riêng của bài trước khi k
= 1.
Trong chương trình dưới
đây, hàm Chia(k)
cho giá trị i nếu mảng a chia được thành hai đoạn a[1..i]
và a[(i + 1)..n]
có tổng gấp k lần nhau. Trong trường hợp vô nghiệm Chia = -1. Ta gọi i
là điểm chia và dùng biến tr (tổng
riêng) để tích luỹ tổng các phần tử của đoạn đang xét a[1..i]. Khi tr = t1 bài toán có nghiệm I, ngược
lại, khi tr > t1 ta chưa thể kết luận là bài toán vô nghiệm. Trường hợp này ta
phải tiếp tục tích luỹ tr để hi vọng đạt được tổng tr = tk. Nếu sau khi tích luỹ ta thu được
tr = tk thì bài toán có nghiệm i, ngược lại, khi tr > tk ta kết luận là bài toán vô nghiệm.
Function
Chia(n,k: integer): integer;
var i: integer;
t, t1, tk, tr: longint;
begin
Chia := -1;
t := 0; { t = sum(a[1..n]) }
for i := 1 to n do t := t+a[i];
if (t mod (k+1) <> 0) then exit; { vo
nghiem }
{ Xu li truong hop co nghiem }
t1 := t div (k+1); { doan tong nho }
tk := t - t1; { tk = k * t1}
tr := 0; { tong rieng tr = sum(a[1..i]) }
for i := 1 to n do
begin
tr := tr + a[i];
if (tr = t1) or (tr = tk) then
begin { lay nghiem i }
Chia:= i; exit;
end;
end;
end;
Ta gọi thủ tục Gen
để sinh dữ liệu kiểm thử. Cũng giống như bài trước, ta sẽ sinh ngẫu nhiên dữ
liệu kiểm thử cho hai trường hợp: chắc chắn có nghiệm và có thể vô nghiệm. Với
trường hợp có thể vô nghiệm ta sinh ngẫu
nhiên như bình thường,
for i := 1 to n do a[i] :=
random(n);
Với trường hợp có nghiệm, ta sinh ngẫu nhiên mảng a gồm hai
đoạn:
Đoạn thứ nhất a[1..d] và
đoạn thứ hai a[d + 1..n] trong đó d là một điểm chia được sinh ngẫu nhiên
d := random(n div 2)+1;
{diem chia}
Ta lại chọn ngẫu nhiên
một trong hai trường hợp:
Trường hợp thứ nhất:
đoạn thứ nhất gấp k lần đoạn thứ hai.
Trường hợp thứ hai: đoạn
thứ hai gấp k lần đoạn thứ nhất.
(* Pascal
*)
(*-------------------------------------------
Chia mang nguyen a thanh 2 doan
co tong ti le 1:k
------------------------------------------
*)
{$B-}
uses Crt;
const MN =
500;
Esc = #27;{ dau thoat }
bl = #32; { dau cach }
nl = #13#10; { xuong dong }
var a: array [0..MN] of integer;
n: integer;
(*----------------------------------------------
Sinh ngau nhien n so nguyen khong am cho mang a
-----------------------------------------------
*)
Procedure
Gen(m,k: integer);
var i,d: integer; t: longint;
begin
n := m; t := 0;
if random(2) = 0 then { vo nghiem }
begin
for i := 1 to n do a[i]:= random(n);
exit;
end;
{ co nghiem }
d := random(n div 2)+1; { diem chia }
for i := 1 to d do
begin
a[i] := random(n); t := t+a[i];
end;
if (random(2) = 0) then
{ doan a[1..d] gap k lan doan cuoi }
a[d] := a[d]+(k-1)*t
else { doan cuoi gap k lan doan a[1..d] }
t := k*t;
for i := d+1 to n-1 do
begin
a[i] := random(t); t := t-a[i];
end;
a[n] := t;
end;
Procedure Xem;
Hiển thị mảng a, tự viết
Function
Chia(n,k: integer): integer; Tự viết
Procedure
Test;
var j,i,k: integer; t: longint;
begin
randomize;
repeat
n := 10 + random(10);
k := random(5)+1;
writeln(nl,' n = ',n,' k = ',k);
Gen(n,k); Xem; i := Chia(n,k);
if i < 0 then writeln('Khong chia
duoc')
else
begin
t
:= 0;
for
j := 1 to i do t := t+a[j];
write('Doan 1: a[1..',i,'].');
writeln('
Tong = ',t);
t := 0;
for j:=i+1 to n do t := t+a[j];
write('Doan
2: a[',i+1,'..',n,'].');
writeln('
Tong = ',t);
end;
until ReadKey = Esc;
end;
BEGIN
Test;
END.
Không có nhận xét nào:
Đăng nhận xét