Sinh ngẫu nhiên tỉ lệ



Sinh ngẫu nhiên tỉ lệ



               Sinh ngẫu nhiên cho mảng nguyên a có n phần tử tạo thành hai đoạn liên tiếp 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ử của đoạn kia.

Thuật toán do gia sư tin học hướng dẫn:
1. Sinh ngẫu nhiên tổng t1 :=  random(n) + 1.
2. Tính t2 := k*t1.
3. Gieo đồng xu bằng cách gọi random(2) để xác định tổng nào trong số t1 và t2 được chọn trước.
4. Sinh random(n div 2)+1 phần tử cho đoạn thứ nhất sao cho tổng các phần tử của đoạn này bằng t1 (xem bài 2.4).
5. Sinh nốt các phần tử cho đoạn thứ hai sao cho tổng các phần tử của đoạn này bằng t2.
(*  Pascal  *)
program K2gen;
uses crt;
const MN = 1000;
var a: array[1..MN] of integer;
(*---------------------------
       Sinh du lieu
-----------------------------*)
procedure Gen(n,k:integer);
var i,j,t1,t2:integer;
begin
  if (k < 1) OR (k > n) then exit;
  t1 := random(n) + 1;
  {tong mot doan; tong doan con lai = k*t1 }
  {chon ngau nhien doan co tong lon dat truoc hay sau }
  if random(2)= 0 then t2 := k*t1
  else
begin
  t2 := t1; t1 := k*t2;
end;
  i := 0; {sinh doan thu nhat}
  for j := 1 to random(n div 2) do
  begin
   inc(i); a[i] := random(t1);
   t1 := t1 – a[i];
  end;
  inc(i); a[i] := t1;
  while i < n do {sinh doan thu hai }
  begin
    inc(i); a[i]:= random(t2);
    t2 := t2 – a[i];
  end;
  a[n] := a[n] + t2;
end;
procedure Xem(n: integer); tự viết
procedure Test;
var n,k: integer;
begin  
  randomize;
  repeat
    n := random(30) + 1;
    k := random(8) + 1;
    write(' n = ',n,' k = ',k);
    Gen(n,k); Xem(n);
  until ReadKey = #27;
end;
BEGIN
Test;
END.

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

Đăng nhận xét