Sinh ngẫu nhiên đều

Sinh ngẫu nhiên đều

               Sinh ngẫu nhiên n phần tử cho mảng nguyên a thoả điều kiện n phần tử tạo thành k đoạn liên tiếp có tổng các phần tử trong mỗi đoạn bằng nhau và bằng giá trị t cho trước.

Gia sư tin học hướng dẫn Thuật toán

1. Chọn số lượng các phần tử trong mỗi đoạn là random(n div k) + 1, khi đó số lượng các phần tử được phát sinh ngẫu nhiên sẽ không vượt quá

k*(n div k) ≤ n

Sau đó ta sẽ chỉnh sao cho số lượng các phần tử đúng bằng n.

2. Giả sử a[d..c] là đoạn thứ j cần được sinh ngẫu nhiên sao cho

a[d] + a[d + 1] + ... + a[c] = t

Ta sinh đoạn này như sau:

2.1. Gán tr :=  t; { tr - giá trị còn lại của tổng }.

2.2. Gán trị ngẫu nhiên 0..tr-1 cho các phần tử a[d..(c - 1)]

(i  =  d..c ): a[i] :=  random(tr)

2.3. Đồng thời chỉnh giá trị còn lại của tr:

tr  :=  tr - a[i]

Ta có:

a[d] < t

a[d+1] < t - a[d]

a[d+2] < t - a[d+1] - a[d]

...

a[c - 1] < t - a[d] - a[d + 1] - ... - a[c - 2]

Chuyển vế các phần tử a[*] trong biểu thức cuối cùng, ta thu được

a[d] + a[d + 1] + ... + a[c – 1] < t

2.4. Ta đặt giá trị còn lại của tổng riêng vào phần tử cuối đoạn: a[c] :=  tr sẽ thu được  a[d] + a[d + 1] + ... + a[c] = t.

(*  Pascal  *)

(*-----------------------------------------

    Sinh ngau nhien cho mang nguyen a

    n phan tu tao thanh k doan lien tiep

    co tong bang nhau

------------------------------------------*)

program KGen;

uses crt;

const MN = 1000; {kich thuoc toi da cua mang a}

            Esc = #27; {dau thoat}

            BL = #32; {dau cách}

var a: array[1..MN] of integer;

(*---------------------------

        Sinh du lieu

-----------------------------*)

procedure Gen(n,k,t: integer);

var i,j,p,tr,s: integer;

begin

  if (k < 1) or (k > n) then exit;

  s := n div k;{s - so toi da phan tu trong moi doan}

  i := 0; {chi dan lien tuc cho cac phan tu moi sinh}

  for j := 1 to k do {sinh doan thu j}

  begin

tr := t;

for p := 1 to random(s) do

{ random(s)+1 = so phan tu trong 1 doan }

begin

 inc(i);

 a[i] := random(tr);

 tr := tr – a[i]; {gia tri con lai cua tong}

end;

inc(i); {i phan tu cuoi cung cua doan j}

a[i] := tr;

end;

  {bu 0 cho cac phan tu con lai}

for i := i+1 to n do a[i] := 0;

end;

procedure Xem(n: integer); Hiển thị mảng a, tự viết

procedure Test;

var n,k: integer;

begin

randomize;

repeat

n := random(30) + 1;

k := random(8) + 1;

t := random(30)+10;

writeln('n = ',n,' k = ',k,' t = ',t);

Gen(n,k,t); Xem(n);

until ReadKey = Esc;

end;

BEGIN

Test;

END.