Giải bài dãy a và b đặc biệt

Đề:

Trích dẫn :

Có hai dãy số: a và b rất đặc biệt. Dãy a là một hoán vị của 1;2;3;..;n và dãy b được tính theo dãy a như sau: phần tử b[i] bằng số lượng các phần tử đứng trước i trong a và lớn hơn i.

Ví dụ dãy a là 3 4 2 5 1 6 thì dãy b là 4 2 0 0 0 0 . Giải thích: xét với i=1, với quy luật trên đề bài thì phần tử b[i] bằng số lượng các phần tử đứng trước số 1 trong dãy a mà lớn hơn 1. Trong dãy a, có các số 3 4 2 5 đứng trước số 1, trong đó tất cả chúng đều lớn hơn 1. Vậy b[1]=4. Tương tự với các b[2],b[3]...

a) Cho dãy a, hãy tính và xuất ra dãy b.
b) Cho dãy b, hãy tính và xuất ra dãy a.

Câu a: Câu này thì có lẽ không cần nói nhiều. Thuật toán chỉ đơn giản là tìm kiếm thôi.
Bài cụ thể:

Code:

Program day_a_va_b_dac_biet;
uses crt;
const max=100;
var a,b:array[1..max] of integer;
    i,j,n,k,l:integer;

procedure nhap;
 begin
  clrscr;
  write('nhap n: ');readln(n);
  for i:=1 to n do
  begin
    write('a[',i,']=');readln(a[i]);
  end;
 end;

procedure tinh;
 begin
  for i:=1 to n do
  begin
    j:=1; l:=0;
    while a[j]<>i do inc(j);
    for k:=1 to j-1 do
    if a[k]>i then inc(l);
    b[i]:=l;
  end;
 end;

procedure xuat;
 begin
  writeln('day b la: ');
  for i:=1 to n do write(b[i],' ');
  readln;
 end;

begin
 nhap;
 tinh;
 xuat;
end.

Câu b: Khi đọc đề bài này có lẽ nhiều bạn đã có khả năng lập trình kha khá sẽ có ý tưởng dùng đệ quy lướt qua. tuy nhiên thử nghĩ xem nhé, nếu n=100 thì coi như đệ quy vài phút là ít. Với bài này mình có giải thuật khác.

Ta sẽ đi ngược lại với giải thuật câu a. Tức là ta sẽ điền lần lượt từng phân tử từ lớn đến nhỏ vào mảng a.

Ta gán a[1]=n. Bây giờ ta sẽ tìm cách điền phần tử n-1 vào mảng a. Ta có hai trước hợp sau, b[n-1]=1 hoặc b[n-1]=0. Cái này thì các bạn có lẽ nhận ra. Với b[n-1]=0 thì ta sẽ suy ra phần tử n-1 đứng trước phần tử có giá trị n. Ngược lại nếu b[n-1]=1 thì phần tử n-1 sẽ đứng sau phần tử n. Từ đó ta suy ra cách chèn phần tử n-1.

Tương tự ta sẽ suy ra cách chèn các phần tử còn lại. Tổng quát, với phần tử k, ta sẽ chèn k vào vị trí b[k]+1 trong mảng a hiện hành.

Bài cụ thể để tham khảo:

Code:

Program day_a_va_b_dac_biet;
uses crt;
const max=100;
var a,b:array[1..max] of integer;
    i,j,n,k,l:integer;

procedure nhap;
 begin
  clrscr;
  write('nhap n: ');readln(n);
  for i:=1 to n do
  begin
    write('b[',i,']=');readln(b[i]);
  end;
 end;

procedure tinh;
 begin
  a[1]:=n;l:=1;
  for i:=n-1 downto 1 do
  begin
    for k:=l+1 downto b[i]+2 do a[k]:=a[k-1];
    a[b[i]+1]:=i;
    inc(l);
  end;
 end;

procedure xuat;
 begin
  writeln('day a la: ');
  for i:=1 to n do write(a[i],' ');
  readln;
 end;

begin
 nhap;
 tinh;
 xuat;
end.