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!
Wednesday, December 25, 2013



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.

0 comments:

Post a Comment

Popular Posts