Chia mảng tỉ lệ 1:1
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ỗi đoạn bằng nhau.
Đặc tả
Ta
quy ước viết #E là "tồn tại"
và #V là "với mọi". Kí hiệu
sum(a[d..c]) là tổng các phần tử
liên tiếp nhau từ a[d] đến a[c]
của dãy a:
sum(a[d..c]) = a[d] + a[d
+1]+ ... + a[c].
Gọi t là tổng các phần tử của mảng: 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
bằng nhau ta phải có:
1. t là số chẵn (t chia hết cho 2). Đặt t2 = t div 2.
2. (#E i:
1 <= i <= n): sum(a[1..i]) = t2.
Chương trình
Hàm Chia cho
giá trị i nếu mảng a chia được thành a[1..i] và a[i+1..n]. 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 = t2 bài toán có nghiệm i. Ngược
lại, khi tr
> t2 bài toán vô nghiệm.
Ta khởi trị ngẫu nhiên
cho mảng a. Tuy
nhiên ta muốn số lần có nghiệm (mảng a chia được thành hai phần có tổng bằng nhau)
xấp xỉ bằng số lần vô nghiệm. Ta sẽ thực hiện mục tiêu đề ra như sau:
Mỗi lần khởi trị ta tung
đồng xu hai mặt. Nếu gặp mặt sấp (random(2)=0), ta sẽ khởi trị tùy ý cho mảng a, ngược
lại, nếu gặp mặt ngửa (random(2)=1) ta khởi trị a là mảng có nghiệm.
Để khởi trị sao cho mảng a có nghiệm ta lại chọn ngẫu nhiên một
điểm cắt d trong
khoảng 1..(n/2).
Sau đó ta khởi trị ngẫu nhiên cho các phần tử a[1..d]. Với các phần tử còn lại ta cũng khởi
trị ngẫu nhiên trong khoảng hợp lí sao cho tổng các giá trị của chúng đúng bằng
tổng t của đoạn a[1..d]. Bạn đọc xem chi tiết thủ tục Gen
trong chương trình.
(*
Pascal *)
(*-----------------------------------------
Chia mang nguyen
a thanh 2 doan
co tong
bang nhau
-------------------------------------------
*)
program
ChiaTiLe11;
{$B-}
uses crt;
const MN =
500; Esc = #27;
var a: array [1..MN] of integer;
n: integer;
(*-------------------------------------------
Sinh
ngau nhien n so nguyen khong am
cho
mang a
-------------------------------------------
*)
procedure
Gen(m: integer);
var i,d,t: integer;
begin
randomize;
n := m;
if random(2)=0 then
begin {khoi tri tuy y}
for i := 1 to n do a[i]:=random(m);
exit;
end;
{ Khoi tri mang co tong d phan tu dau
bang tong cac phan tu con lai }
d :=
random(n div 2)+ 1; { diem chia }
t := 0;
for i := 1 to d do
begin
a[i] := random(n);
t := t + a[i];
end; { t = sum(a[1..d]) }
for i := d+1 to n-1 do
begin { sum(a[d+1..i]) + t = sum(a[1..d]) }
a[i] := random(t);
t := t-a[i];
end;
a[n] := t; { sum(a[1..d]) = sum(a[d+1..n]) }
end;
procedure Xem:
Hiển thị mảng a, tự viết
function Chia:
integer;
var i, t, t2,
tr: integer;
begin
Chia := -1;
t := 0;
for i:=1 to n do t:=t+a[i]; {t=sum(a[1..n]}
if Odd(t) then exit; { vo nghiem }
t2 := t div 2; tr := 0;
for i:=1
to n do
begin
tr :=
tr + a[i];
if tr
> t2 then exit; {vo nghiem }
if tr
= t2 then { co nghiem i }
begin Chia:= i; exit; end;
end;
end;
procedure
Test;
var i:
integer;
begin
repeat
Gen(10); Xem; i := Chia;
if i = -1 then writeln('Khong chia duoc')
else
begin
writeln('Doan
thu nhat: a[1..',i,']');
writeln('Doan
thu hai: a[',i+1,'..',n,']');
end;
until ReadKey=Esc;
end;
BEGIN
Test;
END.
Chú ý
1. Muốn dừng chương trình hãy
nhấn phím Esc có mã ASCII
là #27.
2. Nếu mảng a có chứa một số giá trị 0 thì bài
toán có thể có nhiều nghiệm (nhiều cách chia).
Không có nhận xét nào:
Đăng nhận xét