HomeHọc sinh giỏi môn tin

Seri 100 bài tập Pascal nâng cao – CHƯƠNG VIII : CHUYÊN ĐỀ DÃY CON

Like Tweet Pin it Share Share Email
Like và share giúp mình phát triển website nhé.
  •  
  •  

CHƯƠNG VIII : CHUYÊN ĐỀ DÃY CON.

  1. LÝ THUYẾT:

– Dãy con là dãy các phần tử liên tục thuộc một dãy có trước (dãy mẹ) thỏa mãn một tính chất nào đó.

– Để quản lí một dãy con cần  một chỉ số (nơi bắt đầu dãy con) và độ dài của dãy.

– Một cách quản lí khác là chỉ số đầu và chr số cuối.

– Để xây dựng một dãy con cần:

– Xây dựng giá trị ban đầu.

– Duyệt qua các phần tử của dãy, Nếu:

– Thỏa điều kiện, tăng độ dài thêm 1 ngược lại:

– Nếu dãy con đang xét cần lưu thì: Lưu lại độ dài, chỉ số đầu dãy, Xác định lại độ dài, chỉ số đầu của dãy mới.

– Nếu dãy con đang xét không cần lưu thì: Xác định lại độ dài, chỉ số đầu của dãy mới.

– Để duyệt qua tất cả các dãy con của một dãy gồm n số ta dùng thuật toán vét cạn sau:

For i:= 1 to n

For j:= 1 to n-i+1 Xét dãy con bắt đầu từ vị trí thứ i có độ dài j.

  1. BÀI TẬP:

Bài tập 1:  Cho dãy số gồm n số. Tìm dãy con lớn nhất các phần tử tăng (giảm) dần.

Giải thuật:

Sử dụng kỹ thuật xây dựng dãy con.

Cài đặt:

Program Day_con1;

Var M: array[1..100] of integer;

i,n, dau,ldau, dai,Max: integer;

Begin

Write(‘Nhap so n: ‘); Readln(n);

For i:=1 to n do

Begin Write(‘[‘,i,’]=’); Readln(M[i]); End;

{Khoi tao gia tri dau}

i:=0;

Max:=1;

dau:=1;

dai:=1;

ldau:=1;

While i<=n do

Begin

i:=i+1;

if M[i+1]>=M[i] then dai:=dai+1 else

if dai> Max then Begin Max:=dai; ldau:=dau; dai:=0 End

else Begin dau:=i+1; dai:=1 End;

End;

Write(‘Xau con dai:’,max,’ bat dau tu: ‘,ldau);

Readln

End.

Nhận xét: Bài toán trên có thể sử dụng giải thuật vét cạn dãy con để giải. Sau đây là cài đặt:

Program Day_con1b;

Type KM= array[1..100] of integer;

Var M:KM;

i,j,n, dau,ldau, dai,Max: integer;

Function KT(A:KM;m,l:byte):boolean;

Var ok:Boolean;

i:byte;

Begin

ok:=True;

For i:=m to m+l-1 do if A[i]>A[i+1] then ok:=ok and false;

KT:=ok;

End;

Begin

Write(‘Nhap so nc: ‘); Readln(n); Max:=0;

For i:=1 to n do Begin Write(‘[‘,i,’]=’); Readln(M[i]); End;

For i:= 1 to n-1 do

For  j:=1 to n-i+1 do

if KT(M,i,j) then

if j+1> Max then Begin ldau:=i; Max:=j+1 End;

Write(‘Xau con dai:’,max,’ bat dau tu: ‘,ldau);

Readln

End.

Bài tập 2: Cho dãy số gồm n số. Tìm dãy con lớn nhất các phần tử có cùng dấu, (đan dấu).

Giải thuật:

Thực hiện giống nhu bài 1, chỉ thay điều kiện là M[i+1]*M[i] >0

Cài đặt:

Program Day_con2;

Var M: array[1..100] of integer;

i,n, dau,ldau, dai,Max: integer;

Begin

Write(‘Nhap so nc: ‘); Readln(n);

For i:=1 to n do Begin Write(‘[‘,i,’]=’); Readln(M[i]); End;

i:=0;

Max:=1;

dau:=1;

dai:=1;

ldau:=1;

While i<=n do

Begin

i:=i+1;

if M[i+1]*M[i]>0 then dai:=dai+1 else

if dai> Max then Begin Max:=dai; ldau:=dau; dai:=0 End

else Begin dau:=i+1; dai:=1 End;

End;

Write(‘Xau con dai:’,max,’ bat dau tu: ‘,ldau);

Readln

End.

Nhận xét: Hãy thực hiện bài tập trên bằng kỹ thuật vét cạn dãy con.

Bài tập 3: Cho dãy gồm n số. Tìm dãy con lớn nhất đơn điệu (liên tục tăng, giảm hoặc giảm, tăng).

Giải thuật:

– Dãy đang dấu nếu M[i]*M[i+1] < 0.

Cài đặt:

Giống bài tập 2

Nhận xét:

Bài tập 4: Cho dãy số gồm n số nguyên. Tìm dãy con có tổng lớn nhất

Giải thuật:

– Sử dụng kỹ thuật vét cạn các dãy con, dùng hàm tính tổng dãy con để kiểm tra.

Cài đặt:

Program Day_con1b;

Type KM= array[1..100] of integer;

Var M:KM;

i,j,n,ldau, dai,Max: integer;

Function TONG(A:KM;m,l:byte):Integer;

Var Tam,i:integer;

Begin

Tam:=0;

For i:=m to m+l do Tam:=Tam + A[i];

TONG:=Tam;

End;

Begin

Write(‘Nhap so nc: ‘); Readln(n);

For i:=1 to n do Begin Write(‘[‘,i,’]=’); Readln(M[i]); End;

Max:=M[1];dai:=1;ldau:=1;

For i:= 1 to n do

For  j:=0 to n-i+1 do

if TONG(M,i,j)> Max then

Begin ldau:=i; Max:=Tong(M,i,j) ; dai:=j+1 End;

Write(‘Xau con co tong:’,max,’ bat dau tu: ‘,ldau, ‘ dai: ‘,dai);

Readln

End.

Nhận xét:

 

 

 

 

Comments (0)

Trả lời

Your email address will not be published. Required fields are marked *