//
you're reading...
Bài tập huấn luyện, Chủ đề quy hoạch động, Lập trình Pascal nâng cao

Chuyên đề Quy hoạch động- Dãy Con Tăng Cực Đại

[Nguồn] []


Đề bài


Cho một dãy số nguyên dương A1,A2,.. An . Hãy tỉa bớt một số ít nhất các phần tử của dãy số nguyên đó vầ giữ nguyên thứ tự các phân tử còn lại sao cho dãy số còn lại là một dãy tăng dần. Ta gọi dãy số nguyên tăng dần còn lại sau khi đã tỉa bớt một số phần tử là dãy con của dãy đã cho .

Dữ Liệu : Vào từ File  BaiToan4.Inp :

  • Dòng đầu tiên ghi số N là số phần tử (N<=10000)
  • Dòng tiếp theo ghi N số là các số nguyên của dãy

Kết Qủa : Ghi Ra FIle : BaiToan4.Out

  • Dòng đầu tiên ghi số phần tử của dãy con lớn nhất đó
  • Dòng thứ hai ghi các số của dãy cần tìm .

 


Hướng dẫn


Gọi Maxd[I] là số phần tử lớn nhất của dãy con dài nhất của các phần tử từ 1I . Chúng ta sẽ có công thức quy hoạch động :

                Maxd[I]:=MaxMaxd[J]+1; Với J=1..I-1 , và A[J]<A[I]


Lời giải – Chương trình


uses   crt;
const  max   = 10000;
       fi    = 'd:\daytang.INP';
       fo    = 'd:\daytang.OUT';
type   mang  = array[1..max] of integer;
var    a,d,t : mang;
       n,dem : longint;
       f     : text;
procedure nhap;
     	var   i: longint;
     	begin
           fillchar(a,sizeof(a),0);
           assign(f,fi);
           reset(f);
           readln(f,n);
           for i:=1 to n do read(f,a[i]);
           close(f);
     	end;
procedure khoitri;
     	begin
          	fillchar(t,sizeof(t),0);
          	t[1]:= 0;
          	d[1]:= 1;
     	end;
function vitri_truoc(i: longint): longint;
     	var 	j,ld,lj: longint;
     	begin
          	ld:= 0;
          	lj:= 0;
          	vitri_truoc:= 0;
          	for j:=i-1 downto 1 do
          		if a[j]<=a[i] then           			
                           if d[j]>ld then
                			begin
                		 		ld:= d[j];
                				lj:= j;
                			end;
          	vitri_truoc:= lj;
     	end;
procedure tao_td;
     	var i: longint;
     	begin
          	khoitri;
	     for i:=2 to n do
          	begin
               	t[i]:= vitri_truoc(i);
   
            	if t[i]=0 then	d[i]:= 1
               	else 
					d[i]:= d[t[i]]+1;
        	end;
     	end;
function maxd: longint;
     	var 	i,p,li: longint;
     	begin
         	p	:= -maxint;
         	li	:= 0;
    		for i:=1 to n do
     		if d[i]>p then
         		begin
         			p 	:= d[i];
         			li 	:= i;
         		end;
     		maxd:= li;
     	end;
procedure timketqua;
     	var i: longint;
     	begin
         	i     := maxd;
         	d[i]  := -d[i];
         	dem   := 1;
         	repeat
           	i:= t[i];
           	if i<>0 then
           	begin
           		d[i]:= -d[i];
           		inc(dem)
           	end;
         	until i=0;
     	end;
procedure ghi;
         var     f     : text;
             i     : longint;
         begin
             assign(f,fo);
             rewrite(f);
             writeln(f,dem);
             dem:= 0;
             for i:= 1 to n do
            if d[i]<0 then
         begin
                write(f,a[i]:7);
                inc(dem);
                if dem mod 10 = 0 then writeln(f);
         end;
            close(f);
         end;
BEGIN
        clrscr;
        nhap;
        tao_td;
        timketqua;
        ghi;
END.


Tài liệu tham khảo


  1. Một số vấn đề chọn lọc trong môn Tn học – Tập 1.
  2. a

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: