Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

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

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Giải bài dãy a và b đặc biệt   Sun 28 Mar 2010, 10:22

Đề:
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.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Giải bài dãy a và b đặc biệt   Sun 28 Mar 2010, 11:00

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.
Về Đầu Trang Go down
 
Giải bài dãy a và b đặc biệt
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến