• Không có kết quả nào được tìm thấy

Chuyên đề đoạn con

N/A
N/A
Protected

Academic year: 2022

Chia sẻ "Chuyên đề đoạn con"

Copied!
11
0
0

Loading.... (view fulltext now)

Văn bản

(1)

Phần 1: Mở đầu.

I) Lý do chọn chuyên đề

Việc đa tin học vào trờng phổ thông đợc bộ GDĐT, các Sở GDĐT hết sức quan tâm . Là một giáo viên tham gia giảng dạy bộ môn tin học trong nhà trờng đặc biệt là giúp các em bớc đầu làm quen với ngôn ngữ lập trình PASCAL. Qua thời gian giảng dạy và tìm tòi , chắt lọc nghiên cứu tôi xin trình bày một chuyên đề nhỏ “Giải một số bài toán về đoạn con”

Để học sinh bớc đầu làm quen vối ngôn ngữ lập trình PASCAL II) Phạm vi, mục đích của chuyên đề

1) Phạm vi của chuyên đề:

Do điều kiện hạn chế về thời gian và khả năng có hạn, chuyên đề chỉ nêu đợc một số thuật giải qua các ví dụ minh hoạ về “ đoạn con”

2) Mục đích của chuyên đề:

- Giúp học sinh hiểu đợc thế nào là số đối xứng và cách cách cài

đặt khác nhau .

Phần 2: Nội dung cụ thể

I) Cơ sở lí luận:

Thông qua chuyên đề này học sinh biết vận dụng và đợc cung cấp các kiến thức cần thiết về phơng pháp sử dụng các vòng lặp các kỹ thuật lập trình cơ bản những kinh nghiệm cụ thể trong qua trình tìm tòi lời giải, giúp học sinh rèn luyện các thao tác t duy, phơng pháp suy luận và khả năng sáng tạo.

II. Các bài tập minh hoạ :

Chuyên đề :

Đoạn con liên tục thoả mãn điều kiện ...

Khái niệm : đ

oạn con ( dãy con )

Cho một dãy số nguyên (A) : A

1

,A

2

,...,A

N

. Một dãy gồm 1 hoặc nhiều số hạng liên tiếp của dãy gọi là dãy con liên tục của dãy (A).

Ví dụ : A={ -2 -1 6 4 3 8 0 -5 } dãy con : 6 4 3 8 dãy con dơng liên tục của dãy A.

DạNG I:

Các phần tử liên tiếp trong dãy con có thể so sánh với nhau VD: A[i]<A[i+1],...

Ví dụ 1:

(2)

Nhập vào một dãy số nguyên(A) : A

1

,A

2

,...,A

N

.

a) Có bao nhiêu dãy con lớn hơn 1 phần tử đơn điệu tăng (a[i]<=a[i+1], i=1, 2,..., n) .

b) Đọc ra màn hình dãy con lớn nhất trong trờng hợp có nhiều đoạn con lớn nhất thoả mãn hãy đọc mỗi dãy con đó trên một dòng.

Cài đặt :

uses crt;

var a,d,c:array[1..1000] of Longint;

i,j,n,k,h,max:integer;

BEGIN clrscr;

write('vao so so hang cua day n = ');readln(n);

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

writeln('...');

i:=1; max:=1;

while i<n do begin

while (a[i]>a[i+1])and(i<n) do inc(i);

j:=i;

while(a[i]<=a[i+1])and(i<n) do inc(i);

if i-j+1>=2 then begin max:=i-j+1 ;inc(h);d[h]:=j;c[h]:=i;end;

end;

if h>0 then begin

writeln('CO’,h,’DOAN CON DUONG LON HON 1 PHAN TU ') for i:=1 to h do

begin

if (c[i]-d[i]+1=max)AND (max>1) then begin

inc(k);

if k=1 then writeln(‘CAC DOAN CON DUONG LON NHAT ’) ; write('DOAN THU: ',k,':');

for j:=d[i] to c[i] do write(a[j],' ');

writeln;

end;

end

else writeln('KHONG CO DOAN CON DUONG LON HON 1 PHAN TU') readln

END.

...

Ví dụ 2:

Nhập vào một dãy số nguyên(A) : a

1

,a

2

,...,a

N

. Đọc ra màn hình dãy con lớn nhất lớn hơn 2 phần tử lập thành cấp số cộng.Trong trờng hợp có nhiều đoạn con thoả mãn hãy đọc mỗi

đoạn con đó trên một dòng.

{DOAN CON LON NHAT LON HON 2 PHAN TU LAP THANH CAP SO CONG } uses crt;

var A,d,c:array[1..100]of integer;

j,n,i,max,k,h,cs:integer;

BEGIN clrscr;

write('Nhap n= ');readln(n);

for i:=1 to n do begin write('A[',i,']=');readln(A[i]);end;

i:=1;max:=2;

while i<=n do

(3)

begin

while (a[i+1]-a[i]<=0)and(i<=n) do inc(i);

cs:=A[i+1]-A[i];

j:=i;

while (i<=n) and (A[i+1]-A[i]=cs) do inc(i);

if i-j+1>max then max:=i-j+1;

end;

i:=1;

while i<=n do begin

while (a[i+1]-a[i]<=0)and(i<=n) do inc(i);

cs:=A[i+1]-A[i];

j:=i;

while (i<=n) and (A[i+1]-A[i]=cs) do inc(i);

if (i-j+1=max)and(max<>1) then begin inc(h);d[h]:=j;c[h]:=i;end;

end;

if h=0 then writeln('KHONG CO !') else

begin

for i:=1 to h do begin

inc(k);

write('DAY THU: ',k,':');

for j:=d[i] to c[i] do write(a[j],' ');

writeln;

end;

end;

readln END.

...

Ví dụ 3:

Nhập vào một dãy số nguyên(A) : a

1

,a

2

,...,a

N

. Đọc ra màn hình dãy con lớn nhất lớn hơn 1 phần tử liên tiếp của dãy cùng dấu, trong trờng hợp có nhiều đoạn con thoả mãn hãy đọc mỗi đoạn con đó trên một dòng.

{ Doc ra DAY CON LON HON MOT PHAN TU gom cac so hang lien tiep cua day cung dau}

uses crt;

var a,d,c:array[1..1000] of Longint;

i,j,n,k,h,max:integer;

BEGIN clrscr;

write('vao so so hang cua day n = ');readln(n);

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

writeln('...');

i:=1; max:=1;

while i<n do begin

while (a[i]*a[i+1]<=0)and(i<n) do inc(i);

j:=i;

while(a[i]*a[i+1]>0)and(i<n) do inc(i);

if i-j+1>max then begin inc(h);d[h]:=j;c[h]:=i;end;;

end;

if h=0 then writeln('KHONG CO !') else

begin

for i:=1 to h do begin

inc(k);

(4)

write('DAY THU ',k,':');

for j:=d[i] to c[i] do write(a[j],' ');

writeln;

end;

end;

readln END.

...

Ví dụ 4 : Dãy số phản thứ tự.

Viết chơng trình nhập vào một số nguyên dơng N ( 3<N <21), tiếp theo nhập vào một dãy số nguyên(A) : a

1

,a

2

,...,a

N

.Dãy (A) đợc gọi là “ dãy số phản thứ tự nếu tồn tại một vị trí i (1 <i “

<N ) b của (A) sao cho hai dãy số a

1

,a

2

,...,a

i

và a

i

,a

i+1

,...,a

N

có một dãy là dãy số tăng, dãy số còn lại là dãy số giảm .(dãy số gọi là dãy số tăng nếu phần tử đứng sau có giá trị lớn hơn giá

trị phần tử đứng trớc; dãy số gọi là dãy số giảm nếu phần tử đứng sau có giá trị nhỏ hơn giá

trị phần tử đứng trớc ). Yêu cầu đa ra màn hình thông báo cho biết (A) có là “ dãy số phản thứ tự không ? ” Dữ liệu nhập vào coi nh là chuẩn, không cần kiểm tra.

Ví dụ : Nhập N=5, Nhập dãy 1 2 3 2 1, phải đọc ra dòng thông báo : CO LA DAY PHAN THU TU

...

program bai3;

uses crt;

var A:array[1..21]of longint;

n,i,j:longint;

begin clrscr;

repeat

write('Nhap n (3<n<21) = ');readln(n);

until (3<n)and(n<21);

for i:=1 to n do begin

write('A[',i,']= ');readln(A[i]);

end;

if A[1]<A[2] then begin

j:=1;while (A[j]<A[j+1])and(j<n) do inc(j);

while (A[j]>A[j+1])and(j<n) do inc(j);

if (j>=n)and(A[n]<A[n-1]) then writeln('CO LA DAY PHAN THU TU') else writeln('KHONG LA DAY PHAN THU TU');

end else

if A[1]>A[2] then begin

j:=1;while (A[j]>A[j+1])and(j<n) do inc(j);

while (A[j]<A[j+1])and(j<n) do inc(j);

if (j>=n)and(A[n]>A[n-1]) then writeln('CO LA DAY PHAN THU TU') else writeln('KHONG LA DAY PHAN THU TU');

end else

writeln('KHONG LA DAY PHAN THU TU');

readln end.

...

dạng II:

 Các phần tử liên tiếp trong dãy con không thể so sánh với nhau VD: đoạn con có tổng lớn nhất

Ví dụ 1:

(5)

Cho dãy số nguyên a1, a2, ...,an (ai<1000 , n<10^6). Tìm vị trí đầu ,vị trí cuối của một hoặc một số phần tử liên tiếp của dãy có tổng lớn nhất và tổng của đoạn con đó.

{Cho day so nguyen a1,a2,...,an(ai<1000,n<10^6) .Tim vi tri dau ,vi tri cuoi cua doan co lien tiep co tong lon nhat va tong cua doan con do }

Uses Crt;

var a:Array[1..100] of longint;

i,j,n,dau,cuoi,d,t,max:longint;

BEGIN clrscr;

write('vao n=');readln(n);

cuoi:=1;

dau:=1;

t:=0;d:=1;

max:=-maxlongint;

for i:=1 to n do begin

write('a',i,'=');readln(a[i]);

t:=t+ a[i];

if t>max then begin max:=t ; dau:=d;

cuoi:=i;

end;

if t<0 then begin t:=0;

d:=i+1;

end;

end;

writeln('Daula:',dau, ' cuoi la:',cuoi) ; writeln('Tong cua day la:',max);

readln;

end.

Ví dụ 2:

Trên đờng thẳng cho trớc ngời ta đánh dấu n điểm khác nhau : A

1

, A

2

,..., A

n

(n>=4 ), mỗi điểm

đợc đánh dấu bằng một trong bốn màu: xanh, đỏ, tím, vàng. Mỗi màu đợc sử dụng ít nhất một lần trong quá trình đánh dấu .

Lập chơng trình thực hiện các công việc sau :

a) Nhập thông tin về vị trí các điểm màu dùng để đánh dấu các điểm tơng ứng đó từ bàn phím (xanh : X , đỏ : D , tím : T ,vàng : V ) . Hiển thị kết quả trên màn hình .

b) Chỉ ra một đoạn thẳng (vị trí ) trong đó thoả mãn : Có đúng hai màu, mỗi màu xuất hiện

đúng một lần và hai màu còn lại , mỗi màu xuất hiện ít nhất một lần .

c) Chỉ ra một đoạn thẳng dài nhất (vị trí ) trong đó thoả mãn : Có đúng hai màu, mỗi màu xuất hiện đúng một lần và hai màu còn lại, mỗi màu xuất hiện ít nhất một lần .

Ví dụ : Với n=10 và (A

1

,A

2

,...,A

10

) =(T, V, V, D, T, V, D, X, T,V) thì thông báo:

b) DOAN THOA MAN LA : V D X T (hoặc D X T V hoặc một đoạn bất kì thoả mãn) c) DOAN THOA MAN DAI NHAT LA: V V D T V D X

...

Cài đặt:

USES CRT;

var n,k,i,j,c,d1,h,max:integer;

d,dau,cuoi:array[1..255] of integer;

MAU: string;

BEGIN CLRSCR;

write('VAO DAY MAU LA CAC KI TU IN HOA: ');readln(MAU);

WRITELN(************************);

(6)

i:=1;

repeat j:=4;

repeat

for k:=1 to 4 do d[k]:=0;

for k:=i to j do begin

if (MAU[k]='X') then inc(d[1]);

if (MAU[k]='D') then inc(d[2]);

if (MAU[k]='T') then inc(d[3]);

if (MAU[k]='V') then inc(d[4]);

end;

if((d[1]=1)and(d[2]=1)and(d[4]<>0)and(d[3]<>0)) or ((d[1]=1)and(d[3]=1)and(d[2]<>0)and(d[4]<>0)) or ((d[1]=1)and(d[4]=1)and(d[2]<>0)and(d[3]<>0)) or((d[3]=1)and(d[2]=1)and(d[1]<>0)and(d[4]<>0)) or((d[4]=1)and(d[2]=1)and(d[1]<>0)and(d[3]<>0)) or((d[3]=1)and(d[4]=1)and(d[2]<>0)and(d[1]<>0)) then

begin inc(h);

if j-i+1 >max then max:=j-i+1;

dau[h]:=i;cuoi[h]:=j;

end;

inc(j);

until j>length(MAU);

inc(i);

until i>length(MAU);

if h>0 then begin

write(' DOAN MAU THOA MAN LA :');

for i:=dau[1] to cuoi[1] do write(MAU[i]);writeln;

for i:=1 to h do begin

if cuoi[i]-dau[i]+1=max then begin

write(' DOAN MAU DAI NHAT THOA MAN LA :');

for j:=dau[i] to cuoi[i] do write(MAU[j]);writeln;

end;

end;

end

else writeln('KHONG CO DOAN MAU NAO THOA MAN');

readln END.

...

Bài số : ( Dãy con dài nhất ) (Dành cho học sinh THCS và THPT)

Cho dãy gồm n số nguyên a1, a2,..., an. Tìm dãy con gồm một hoặc một số phần tử liên tiếp của dãy đã cho với tổng các phần tử trong dãy là lớn nhất.

Dữ liệu: Vào từ file văn bản SUBSEQ.INP

(7)

- Dòng đầu tiên chứa số nguyên dương n (n < 106).

- Dòng thứ i trong số n dòng tiếp theo chứa số ai (|ai | < 1000).

Kết quả: Ghi ra file văn bản SUBSEQ.OUT

- Dòng đầu tiên ghi vị trí của phần tử đầu tiên của dãy con tìm được.

- Dòng thứ hai ghi vị trí của phần tử cuối cùng của dãy con tìm được - Dòng thứ ba ghi tổng các phần tử của dãy con tìm được.

Ví dụ

:

SUBSEQ.INP SUBSEQ.OUT 8

12 -14 1 23 -6 22 -34 13

3 6 40

Bài số : ( Dãy con CHIA HET )

Cho một dãy số gồm N số nguyên và một số nguyên dương k. Hãy tìm một dãy con dài nhất liên tiếp nhau sao cho tổng chia hết cho k.

Dữ liệu vào: từ file DAYSO.INP có dạng:

- Dòng đầu tiên là hai số N và k (N<=500000; k<=10000);

- Các dòng tiếp theo là N số nguyên của dãy (các số kiểu Longint), mỗi số trên một dòng.

Kết quả: ra file DAYSO.OUT gồm một dòng duy nhất chứa hai số m và s, trong đó m là độ dài lớn nhất tìm được và s là vị trí bắt đầu của dãy đó.

Ví dụ

:

(8)

DAYSO.INP DAYSO.OUT 3 2

1 2 3 3 1

...

{De thi hsg 04-05 }

program doan_con_dai_nhat_co_tong_chia_het_cho_k;

uses crt;

var P1,n,i,j,k,h,S,P:longint;

A,C,D:array[1..16] of longint;

BEGIN

clrscr; textmode(co80);

write('Nhap so N=');readln(N);

write('Nhap so K=');readln(K);

writeln('Nhap vao day A:');

for i:=1 to n do begin write('A[',i,']=');readln(A[i]);end;

writeln('...');

i:=1;

S:=1; {S la do dai cua doan con chia het k it nhat 1 phan tu}

repeat P:=0;

for j:=i to n do P:=P+A[j];

j:=n;

while (P mod K<>0) and(j>=i) do begin P:=P-A[j];dec(j);end;

if j-i+1>=S then begin S:=j-i+1;inc(h);D[h]:=i;C[h]:=j;end;

inc(i);

until i>n;

if h>0 then begin

for i:=1 to h do

if C[i]-D[i]+1=S then writeln(S,' ',D[i],' ',C[i]);

end

else writeln(' 0 ');

readln END.

...

Bài số : ( Dãy con l

ồi

)

Dãy giá trị nguyên A=(A1, A2, ..., AN) được gọi là lồi, nếu nó giảm dần từ A1 đến một Ai nào đó, rồi tăng dần tới AN.

Ví dụ dãy lồi: 10 5 4 2 −1 4 6 8 12

Yêu cầu: Lập trình nhập vào một dãy số nguyên, bằng cách xóa bớt một số phần tử của dãy và giữ nguyên trình tự các phần tử còn lại, ta nhận được dãy con lồi dài nhất.

Dữ liệu vào trong file: Dayloi.inp có dạng - Dòng đầu là N (N<=2000)

- Dòng tiếp theo là N số nguyên của dãy số (các số kiểu integer)

(9)

Kết quả ra file: Dayloi.out gồm:

- Dòng đầu tiên ghi số phần tử lớn nhất của dãy con tìm được

- Dòng tiếp theo ghi các số thuộc dãy con (không thay đổi trật tự các phần tử trong dãy ban đầu) Ví dụ :

DAYLOI.INP DAYLOI.OUT

10

1 2 3 4 2 5 1 2 3 4

6

42 1 2 3 4

...

.

Bài số : Bạn hãy gạch số

Chúng ta viết liên tiếp 10 số nguyên tố đầu tiên theo thứ tự tăng để tạo thành một số có nhiều chữ số. Trong số này hãy gạch đi một nửa số chữ số để số còn lại là:

a. Nhỏ nhất b. Lớn nhất

Trong từng trường hợp phải nêu cụ thể thuật giải (tại sao lại gạch như vậy)?

Số chung lớn nhất

Cho 2 xâu:

X = x

1

x

2

..x

M

. (Với xi là các kí tự số từ ‘0’ đến ‘9’) Y = y

1

y

2

..y

N

.( Với yi là các kí tự số từ ‘0’ đến ‘9’) (M, N <= 250)

Ta gọi: Z = z

1

z

2

..zk là xâu chung của 2 xâu X, Y nếu xâu Z nhận đợc từ xâu X bằng cách xoá đi một số kí tự và cũng nhận được từ xâu Y bằng cách xoá đi một số kí tự.

Yêu cầu: Tìm một xâu chung của 2 xâu X, Y sao cho xâu nhận được tạo thành một số lớn nhất có thể được.

Dữ liệu vào file: String.inp

Gồm 2 dòng, dòng 1 là xâu X, dòng 2 là xâu Y.

Kết quả ra file: String.out

Gồm 1 dòng duy nhất là số lớn nhất có thể nhận được.

Ví dụ :

(10)

STRING.INP STRING.OUT

19012304

034012 34

Phần 3: Kết luận

Chuyên đề: Giải một bài Toán về số đối xứng giúp học sinh chủ “ ”

động lĩnh hội kiến thức hơn, phù hợp với việc đổi mới phơng pháp dạy học hiện nay, phát huy vai trò tích cực học tập của học sinh. Khắc sâu những kiến thức học sinh tự tìm tòi, khám phá để chất lợng của việc học bộ môn tin học.

Qua thực tế giảng dạy, chúng tôi thấy rằng: Việc tìm tòi thuật giải một bài Toán Tin là yêu cầu rất quan trọng đối với bộ môn Tin học , đã có thuật giải rồi thì việc tìm thêm lời giải mới cho bài Toán giúp cho giáo viên và học sinh có sự vận dụng linh hoạt hơn với các kiểu và dạng bài tập, làm cho học sinh hứng thú, tích cực học tập hơn.

Nhng, đòi hỏi ngời giáo viên cũng nh học sinh họcmôn tin học phải có kiến thức cơ bản, vững chắc và phải biết luôn tìm tòi và sáng tạo trong học tập

Trên đây là một số bài tập mà tôi đã su tầm biên soạn, mong muốn

đóng góp một dạng bài tập nhỏ giúp cho học sinh có thêm một t liệu để học tập . Chuyên đề này còn hạn chế về thời gian và cha giới thiệu đợc nhiều cách giải cho các bài toán hay, cha đa ra đợc các bài tập có cách suy nghĩ và lời giải tơng tự và không tránh khỏi những thiếu sót. Tôi đợc rất mong đợc sự góp ý và bổ sung của đồng nghiệp.

Hết

Tài liệu tham khảo

Tài liệu liên quan

[r]

Vì oâng laø ngöôøi nöôùc ngoaøi, khoâng phaûi laø coâng daân Vieät Nam, oâng khoâng coù quoác tòch Vieät Nam.... Quyền có

Tập huấn kỹ thuật đã cung cấp khái niệm thống nhất của WHO về nguyên nhân tử vong, bao gồm nguyên nhân chính (Underlying Cause of Death), nguyên nhân trực

[r]

Transparenc , nancial accounting information and corporate governance: The link with achievement.Economic Polic Review - Federal Reserve Bank of New York, 65-87.. Robert

[r]

(2005), Econometric Analysis of Panel Data, West Sussex, England, John Wiley

Lµ mét gi¸o viªn tham gia gi¶ng d¹y bé m«n tin häc trong nhµ trêng ®Æc biÖt lµ gióp c¸c em bíc ®Çu lµm quen víi ng«n ng÷ lËp