Kênh Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
Sunday, December 22, 2013



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]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 Gentrong 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).

0 comments:

Post a Comment

Popular Posts