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.