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.

Không có nhận xét nào:

Đăng nhận xét