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: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 ilà đ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.

1 comments:

Popular Posts