Phương pháp chung Giả sử đã xác định được k-1 phần tử đầu tiên của dãy: x1,...,xk-1. Ta cần xác định phần tử thứ k. Phần tử này được xác định theo cách sau: - Giả sử Tk: tập tất cả các giá trị mà phần tử xk có thể nhận được. Vì tập Tk hữu hạn nên ta có thể đặt nk là số phần tử của Tk theo một thứ tự nào đó, tức là ta có thể thành lập một ánh xạ 1-1 từ tập Tk lên tập {1, 2, ..., nk}.

- Xét j∈{1, 2, ..., nk}. Ta nói rằng "j chấp nhận được" nếu ta có thể bổ sung phần tử thứ j trong Tk với tư cách là phần tử xk vào trong dãy x1,...,xk-1 để được dãy x1,...,xk. - Nếu k=n: Bộ (x1,...,xk) thỏa mãn yêu cầu B, do đó bộ này được thu nhận. - Nếu k

Var j:Integer;

Begin

For j:=1 To nk Do If Then Begin

;

If k=n Then

Else THU(k+1); {Quay lui} End; End; Ví dụ: Liệt kê các dãy nhị phân có độ dài n. Program DayNhiPhan; Var b:Array[1..20] Of 0..1; {Dãy nhị phân có độ dài tối đa là 20} n:Byte; Procedure InKetQua; Var i:Byte; Begin

For i:=1 To n Do Write(b[i]);

Writeln;

End; Procedure THU(k:Byte); Var j:Byte; 31 Giáo trình bài tập Pascal Begin For j:=0 To 1 Do {Tập giá trị của dãy nhị phân} Begin b[k]:= j; If k=n Then InKetQua Else THU(k+1); {Quay lui} End; End; Begin

Write('n = '); Readln(n);

THU(1);

Readln;

End. V. TẠO THƯ VIỆN (UNIT) 5.1. Cấu trúc của một Unit UNIT ; {phải trùng với tên file} INTERFACE USES........... .;

CONST..........;

TYPE............;

VAR .............; Procedure [(Các tham số)]; Function [(Các tham số)]:; IMPLEMENTATION

Procedure [(Các tham số)];

[Các khai báo]

Begin

............. End; Function [(Các tham số)]:;

[Các khai báo]

Begin

............. End; END. 32 Giáo trình bài tập Pascal Chú ý: •Tên của Unit phải trùng với tên file. •Chỉ có những chương trình con được khai báo ở phần INTERFACE mới sử dụng được ở các chương trình khác. •Các thủ tục và hàm được khai báo ở phần INTERFACE thì bắt buộc phải có trong phần IMPLEMENTATION. 5.2. Ví dụ minh họa Tạo Unit MYTOOL lưu ở file MYTOOL.PAS. UNIT MYTOOL; INTERFACE USES CRT; VAR m:Integer; Procedure WriteXY(x,y:Integer; St:String);

Function UCLN(a,b:Integer):Integer;

Function NGUYENTO(n:Word):Word;

IMPLEMENTATION Procedure WriteXY(x,y:Integer; St:String); Var i:Byte; Begin Gotoxy(x,y); Write(St); End; Function UCLN(a,b:Integer):Integer; Begin While ab Do Begin If a>b Then a:=a-b Else b:=b-a; End; UCLN:=a; End; Function NGUYENTO(n:Word):Boolean; Var d,i:Word; Begin

d:=0;

For i:=2 To n DIV 2 Do

If n MOD i=0 Then d:=d+1; NGUYENTO:=d=0; 33 Giáo trình bài tập Pascal End; END. Bây giờ, ta có thể viết một chương trình có sử dụng Unit MYTOOL. Uses Crt, MyTool; Var a,b:Integer; Begin

CLRSCR;

Write(10,5,'CHUONG TRINH MINH HOA');

Write('Nhap a = '); Readln(a);

Write('Nhap b = '); Readln(b);

Writeln('UCLN cua ',a,' va ',b,' la:',UCLN(a,b));

Write('Nhap m = '); Readln(m);

If NGUYENTO(m) Then Writeln(m,' la so nguyen to!') Else Writeln(m,' khong phai la so nguyen to!') Readln; End. BÀI TẬP MẪU Bài tập 4.1: Viết hàm tìm Max của 2 số thực x,y. Var a,b:Real;

Function Max(x,y:Real):Real;

Begin

If x>y Then Max:=x Else Max:=y; End; Begin

Write('Nhap a='); Readln(a);

Write('Nhap b='); Readln(b);

Writeln('So lon nhat trong 2 so la: ', Max(a,b));

Readln;

End. Bài tập 4.2: Viết hàm LOWCASE( c:char):char; để đổi chữ cái hoa c thành chữ thường. Ý tưởng: 34 Giáo trình bài tập Pascal Trong bảng mã ASCII, số thứ tự của chữ cái hoa nhỏ hơn số thứ tự của chữ cái thường là 32. Vì vậy ta có thể dùng 2 hàm CHR và ORD để chuyển đổi. Uses crt;

Var ch:Char;

Function LOWCASE(c:Char):Char;

Begin

If c IN ['A'..'Z'] Then LOWCASE:=CHR(ORD(c)+32) Else LOWCASE:=c; End; Begin

Write('Nhap ký tu ch='); Readln(ch);

Writeln('Ky tu hoa la: ', LOWCASE(ch));

Readln;

End. Bài tập 4.3: Viết thủ tục để hoán đổi hai gía trị x,y cho nhau. Var a,b:Real; Function Swap(Var x,y:Real); Var Tam:Real; Begin Tam:=x; x:=y; y:=Tam; End; Begin

Write('Nhap a='); Readln(a);

Write('Nhap b='); Readln(b);

Swap(a,b);

Writeln('Cac so sau khi hoan doi: a=', a:0:2,' b=',b:0:2);

Readln;

End. Bài tập 4.4: Viết hàm XMU(x:Real;n:Byte):Real; để tính giá trị xn. Var x:Real; n:Byte;

Function XMU(x:Real;n:Byte):Real;

Var i:Byte; S:Rea;

Begin

35 Giáo trình bài tập Pascal S:=1;

For i:=1 To n Do S:=S*x;

XMU:=S;

End; Begin

Write('Nhap x='); Readln(x);

Write('Nhap n='); Readln(n);

Writeln('x mu n = ', XMU(x,n):0:2);

Readln;

End. Bài tập 4.5: Viết thủ tục KHUNG(x1,y1,x2,y2:Integer); để vẽ một khung hình chữ nhật có đỉnh trên bên trái là (x1,y1) và đỉnh dưới bên phải là (x2,y2). Ý tưởng: Dùng các ký tự mở rộng trong bảng mã ASCII:(#179),(#196),(#218),(#192), (#191), (#217). Uses crt;

Procedure Khung(x1,y1,x2,y2:Integer);

Var i,j:Integer;

Begin

Gotoxy(x1,y1); Write(#218); {Vẽ} Gotoxy(x1,y2); Write(#192); {Vẽ} {Vẽ 2 viền ngang của khung} For i:=x1+1 To x2-1 do Begin

Gotoxy(i,y1); Write(#196);

Gotoxy(i,y2); Write(#196);

End; Gotoxy(x2,y1); Write(#191); {Vẽ} Gotoxy(x2,y2); Write(#217); {Vẽ} {Vẽ 2 viền dọc của khung} For j:=y1+1 To y2-1 do Begin

Gotoxy(x1,j); Write(#179);

Gotoxy(x2,j); Write(#179);

End; End; Begin Clrscr; 36 Giáo trình bài tập Pascal Khung(10,5,40,20); Readln; End. Bài tập 4.6: Viết thủ tục PHANTICH(n:Integer); để phân tích số nguyên n ra thừa số nguyên tố. Uses crt; Var n:Integer; Procedure PHANTICH(n:Integer);

Var i:Integer;

Begin

i:=2; While n1 Do Begin While n MOD i=0 Do Begin

Writeln(n:5,'|',i:2);

n:=n Div i;

End; i:=i+1; End; Writeln(n:5,'|'); End; Begin

Write('Nhap n='); Readln(n);

PHANTICH(n);

Readln;

End. BÀI TẬP TỰ GIẢI Bài tập 4.7: Viết 2 hàm tìm Max , min của 3 số thực. Bài tập 4.8: Viết hàm PERFECT(n:Word):Boolean; để kiểm tra số nguyên n có phải là số hoàn thiện hay không? Bài tập 4.9: Viết thủ tục FILL(x1,y1,x2,y2:Integer; ch:Char); để tô một vùng màn hình hình chữ nhật có đỉnh trên bên trái là (x1,y1) và đỉnh dưới bên phải là (x2,y2) bằng các ký tự ch.

Bài tập 4.10: Viết hàm tìm BSCNN của 2 số nguyên a,b được khai báo như sau: Function BSCNN (a,b:word ):word ; 37 Giáo trình bài tập Pascal Bài tập 4.11: Viết thủ tục để tối giản phân số a/b , với a, b là 2 số nguyên. Bài tập 4.12: Viết các hàm đệ quy để tính:

S1 = 1+2 +3+......+n ;

S2 = 1+1/2 +.....+ 1/n ;

S3 = 1-1/2 +......+ (-1)n+1 1/n

S4 = 1 + sin(x) + sin2(x) +......+ sinn (x)

Bài tập 4.13: Viết hàm đệ quy để tính Ckn biết : Cnn =1 , C0n = 1 , Ckn = Ck-1n-1 + Ckn-1. Bài tập 4.14: Cho m , n nguyên dương . Lập hàm đệ quy tính: A(m,n) = > ∧ > − − = − = + 0 0 , )) 1 , ( , 1 ( 0 , ) 1 , 1 ( 0 , 1 n m n m A m A n m A m n Bài tập 4.15: Lập hàm đệ qui để tính dãy Fibonaci: F(n) = 1 1 2 1 2 2 , ( ) ( ) , n n F n F n n =∨ = − + − >  Bài tập 4.16: Viết hàm đệ qui tìm USCLN của 2 số. Bài tập 4.17: Viết thủ tục để in ra màn hình số đảo ngược của một số nguyên cho trước theo 2 cách: đệ qui và không đệ qui. Bài tập 4.18: Viết chương trình in ra màn hình các hoán vị của n số nguyên đầu tiên. Bài tập 4.19: Xây dựng một Unit SOHOC.PAS chứa các thủ tục và hàm thực hiện các chức năng sau:

- Giải phương trình bặc nhất.

- Giải phương trình bặc hai.

- Tìm Max/Min của 2 số a,b.

- Tìm USCLN và BSCNN của 2 số nguyên a,b.

- Kiểm tra số nguyên dương n có phải là số nguyên tố hay không?

- Kiểm tra số nguyên dương n có phải là số hoàn thiện hay không?

- Đổi một số nguyên dương n sang dạng nhị phân.

- In ra màn hình bảng cữu chương từ 2→ 9.

Sau đó, tự viết các chương trình có sử dụng Unit SOHOC vừa được xây dựng ở trên. 38 Giáo trình bài tập Pascal Chương 5 DỮ LIỆU KIỂU MẢNG (ARRAY) I. KHAI BÁO MẢNG Cú pháp: TYPE = ARRAY [chỉ số] OF ; VAR :; hoặc khai báo trực tiếp: VAR : ARRAY [chỉ số] OF ; Ví dụ: TYPE Mangnguyen = Array[1..100] of Integer; Matrix = Array[1..10,1..10] of Integer; MangKytu = Array[Byte] of Char; VAR A: Mangnguyen; M: Matrix; C: MangKytu; hoặc: VAR A: Array[1..100] of Integer; C: Array[Byte] of Char; II. XUẤT NHẬP TRÊN DỮ LIỆU KIỂU MẢNG - Để truy cập đến phần tử thứ k trong mảng một chiều A, ta sử dụng cú pháp: A[k]. - Để truy cập đến phần tử (i,j) trong mảng hai chiều M, ta sử dụng cú pháp: M[i,j]. - Có thể sử dụng các thủ tục READ(LN)/WRITE(LN) đối với các phần tử của biến kiểu mảng. BÀI TẬP MẪU Bài tập 5.1: Viết chương trình tìm giá trị lớn nhất của một mảng chứa các số nguyên gồm N phần tử. Ý tưởng: - Cho số lớn nhất là số đầu tiên: Max:=a[1]. - Duyệt qua các phần tử a[i], với i chạy từ 2 tới N: Nếu a[i]>Max thì thay Max:=a[i]; Uses Crt; Type Mang = ARRAY[1..50] Of Integer; 39 Giáo trình bài tập Pascal Var A:Mang; N,i,Max:Integer; Begin

{Nhập mảng}

Write('Nhap N='); Readln(N);

For i:=1 To N Do Begin Write('A[',i,']='); Readln(A[i]); End;

{Tìm phần tử lớn nhất}

Max:=A[1];

For i:=2 To N Do

If Max

{In kết quả ra màn hình}

Writeln('Phan tu lon nhat cua mang: ', Max);

Readln;

End. Bài tập 5.2: Viết chương trình tính tổng bình phương của các số âm trong một mảng gồm N phần tử. Ý tưởng: Duyệt qua tất cả các phần tử A[i] trong mảng: Nếu A[i]

{Nhập mảng}

Write('Nhap N='); Readln(N);

For i:=1 To N Do Begin Write('A[',i,']='); Readln(A[i]); End;

{Tính tổng}

S:=0;

For i:=1 To N Do

40

If A[i]

Writeln('S= ', S);

Readln;

End. Bài tập 5.3: Viết chương trình nhập vào một mảng gồm N số nguyên. Sắp xếp lại mảng theo thứ tự tăng dần và in kết quả ra màn hình. Ý tưởng: Cho biến i chạy từ 1 đến N-1, đồng thời cho biến j chạy từ i+1 đến N: Nếu A[i]>A[j] thì đổi chổ A[i], A[j]. Uses Crt; Type Mang = ARRAY[1..50] Of Integer; Var A:Mang; N,i,j,Tam:Integer; Begin

{Nhập mảng}

Write('Nhap N='); Readln(N);

For i:=1 To N Do Begin Write('A[',i,']='); Readln(A[i]); End;

{Sắp xếp}

For i:=1 To N-1 Do

For j:=i+1 To N Do If A[i]>A[j] Then Begin Tam:=A[i]; A[i]:=A[j]; A[j]:=Tam; End;

{In kết quả ra màn hình}

Writeln('Ket qua sau khi sap xep:');

For i:=1 To N Do Write(A[i]:5);

Readln;

End. Bài tập 5.4: Viết chương trình nhập vào một mảng A gồm N số nguyên và nhập thêm vào một số nguyên X. Hãy kiểm tra xem phần tử X có trong mảng A hay không? 41 Giáo trình bài tập Pascal Ý tưởng: Dùng thuật toán tìm kiếm tuần tự.So sánh x với từng phần tử của mảng A. Thuật toán dừng lại khi x=A[i] hoặc i>N. Nếu x=A[i] thì vị trí cần tìm là i, ngược lại thì kết quả tìm là 0 (không tìm thấy). Uses Crt; Type Mang = ARRAY[1..50] Of Integer; Var A:Mang; N,i,x:Integer; Function TimKiem(x, N: Integer; A:Mang):Integer; Var i:Integer; Begin

I:=1;

While (I A[I]) do I:=I+1;

If I

End; Begin

{Nhập mảng}

Write('Nhap N='); Readln(N);

For i:=1 To N Do Begin Write('A[',i,']='); Readln(A[i]); End;

Write('Nhap X='); Readln(x);

{Kết quả tìm kiếm}

If TimKiem(X,N,A)0 Then

Writeln('Vi tri cua X trong mang la:', TimKiem(X,N,A))

Else Writeln('X khong co trong mang.');

Readln;

End. Bài tập 5.5: Giả sử mảng A đã được sắp xếp theo thứ tự tăng dần. Viết hàm để kiểm tra xem phần tử X có trong mảng A hay không? Ý tưởng: So sánh x với phần tử ở giữa mảng A[giua]. Nếu x=A[giua] thì dừng (vị trí cần tìm là chỉ số của phần tử giữa của mảng). Ngược lại, nếu x>A[giua] thì tìm ở đoạn sau của mảng [giua+1,cuoi], ngược lại thì tìm ở đoạn đầu của mảng [dau,giua-1].

42 Giáo trình bài tập Pascal Sau đây là hàm cài đặt cho thuật toán này: Function TimKiemNhiPhan(X, N: Integer; A: Mang):Integer; Var dau,cuoi,giua:Integer; Found:Boolean; Begin

dau:=1; {điểm mút trái của khoảng tìm kiếm}

cuoi:=N; {điểm mút phải của khoảng tìm kiếm}

Found:=False; {chưa tìm thấy}

While (dau

Begin

giua:=(dau + cuoi) Div 2;

If X = A[giua] Then Found:=True {đã tìm thấy}

Else

If X > A[giua] Then dau:=giua+1 Else cuoi:=giua-1; End; If Found Then TimKiemNhiPhan:= giua Else TimKiemNhiPhan:=0; End; Bài tập 5.6: Viết chương trình tìm ma trận chuyển vị của ma trận A. Ý tưởng: Dùng mảng 2 chiều để lưu trữ ma trận. Gọi B là ma trận chuyển vị của ma trận A, ta có: Bij = Aji. Uses Crt; Type Mang = ARRAY[1..10,1..10] Of Integer; Var A,B:Mang; m,n,i,j:Integer; Begin

{Nhập ma trận}

Write('Nhap số dòng m='); Readln(m);

Write('Nhap số cột n='); Readln(n);

For i:=1 To m Do

For j:=1 To n Do Begin Write('A[',i,j,']='); Readln(A[i,j]); End;

{Tìm ma trận chuyển vị}

For i:=1 To m Do

For j:=1 To n Do B[i,j]:=A[j,i]; 43 Giáo trình bài tập Pascal {In ma trận chuyển vị ra màn hình} For i:=1 To m Do Begin

For j:=1 To n Do Write(B[i,j]:5);

Writeln;

End; Readln; End. Bài tập 5.7: Cho một mảng 2 chiều A cấp mxn gồm các số nguyên và một số nguyên x. Viết chương trình thực hiện các công việc sau:

a/ Đếm số lần xuất hiện của x trong A và vị trí của chúng.

b/ Tính tổng các phần tử lớn nhất của mỗi dòng.

Uses Crt; Type Mang = ARRAY[1..10,1..10] Of Integer; Var A:Mang; m,n,i,j,x,dem,S,max:Integer; Begin

{Nhập ma trận}

Write('Nhap số dòng m='); Readln(m);

Write('Nhap số cột n='); Readln(n);

For i:=1 To m Do

For j:=1 To n Do Begin Write('A[',i,j,']='); Readln(A[i,j]); End;

{Nhập x}

Write('Nhap x='); Readln(x);

{Đếm số lãn xuất hiện của x và vị trí của x}

dem:=0;

Writeln('Vi tri cua x trong mang A: ');

For i:=1 To m Do

For j:=1 To n Do If x=A[i,j] Then Begin

Write(i,j,' ; ');

dem:=dem+1;

44 Giáo trình bài tập Pascal End;

Writeln('So lan xuat hien cua x trong mang A la: ',dem);

{Tính tổng các phần tử lớn nhất của mỗi dòng}

S:=0;

For i:=1 To m Do {duyệt qua từng dòng}

Begin

{Tìm phần tử lớn nhất của dòng thứ i}

Max:=A[i,1];

For j:=2 To n Do {duyệt từng phần tử của dòng thứ i}

If max

{Cộng max vào biến S}

S:=S+max;

End;

Writeln('Tong cac phan tu lon nhat cua moi dong la: ',S);

Readln;

End. Bài tập 5.8: Giải phương trình bằng phương pháp chia nhị phân. Ý tưởng: Giả sử cần tìm nghiệm của phương trình f(x)=0 trên đoạn [a,b] với y=f(x) đồng biến và đơn trị trên đoạn [a,b]. Ta giải như sau: Gọi m là trung điểm của đoạn [a,b]. Nếu f(m)*f(a)

Giả sử f(x) là một đa thức: f(x) = a0 + a1x + a2x2 + ... + anxn. Lúc này, ta có thể dùng mảng một chiều để lưu trữ các hệ số ai của đa thức. Uses Crt; Type HESO=Array[0..20] Of Real; Var a:HESO; n:Byte; Min,Max,epsilon:Real; Procedure NhapDaThuc; Var i:Byte; Begin

Write('Bac cua da thuc: n= '); Readln(n);

Writeln('Nhap cac he so cua da thuc:');

For i:=0 To n Do

Begin

Write('a[',i,']='); Readln(a[i]); 45 Giáo trình bài tập Pascal End;

Writeln('Nhap doan tim nghiem:[a,b]');

Write('a= '); Readln(Min);

Write('b= '); Readln(Max);

Write('Nhap sai so cua phuong trinh: '); Readln(epsilon);

End; {Tính giá trị của đa thức} Function f(x:Real):Real; Var S,tam:Real; i:Byte; Begin

S:=a[0]; tam:=1;

For i:=1 To n Do

Begin

tam:=tam*x;

S:=S+a[i]*tam;

End; f:=S; End; Procedure TimNghiem(Min,Max:real);

Var m:Real;

Begin

If f(Min)*f(Max)>0 Then Writeln('Phuong trinh vo nghiem.') Else If abs(f(Min))

ch:=Readkey;

Until ch=#27; End; Procedure GiaoAB(n:Byte; A:Mang;m:Byte; B:Mang); Var i:Byte; Begin For i:=1 To n Do If KiemTra(A[i],m,B) Then Write(A[i]:4); End; Begin Clrscr; Writeln('Nhap mang A: '); NhapMang(n,A);

Writeln('Nhap mang B: ');

NhapMang(m,B);

Writeln('Giao cua 2 mang A&B la: ');

GiaoAB(n,A,m,B);

Readln;

End. Bài tập 5.11: Cho một mảng số nguyên gồm n phần tử. Tìm dãy con gồm m phần tử (m≤n) sao cho dãy con này có tổng lớn nhất. (Dãy con là dãy các phần tử liên tiếp nhau trong mảng).

Uses Crt; Type Mang=ARRAY[1..50] Of Integer; Var A:Mang; n,m,i,j,k:Byte; S,Max:Integer; Begin

Write('So phan tu cua mang: n= '); Readln(n);

For i:=1 To n Do

Begin

Write('a[',i,']='); Readln(a[i]); End; Write('Nhap so phan tu cua day con: m= '); Readln(m);

k:=1; {Vị trí phần tử đầu tiên của dãy con}

{Giả sử m phần tử đầu tiên của mảng A là dãy con có tổng lớn nhất}

49 Giáo trình bài tập Pascal Max:=0; For i:=1 To m Do Max:=Max+A[i]; {Tìm các dãy con khác} For i:=2 To n-m+1 Do Begin {Tính tổng của dãy con thứ i}

S:=0;

For j:=i To i+m-1 Do S:=S+A[j];

If S>Max Then {Nếu dãy con tìm được có tổng lớn hơn dãy con trước}

Begin

Max:=S; {Thay tổng mới} k:=i; {Thay vị trí đầu tiên của dãy con mới} End; End; Writeln('Day con co tong lon nhat la:');

For i:=k To k+m-1 Do Write(A[i]:5);

Readln;

End. Bài tập 5.12: Viết chương trình in ra màn hình tam giác Pascal. Ví dụ, với n=4 sẽ in ra hình sau: 11 1 12 1

1 3 3 1

1 4 6 4 1

Ý tưởng: Tam giác Pascal được tạo ra theo qui luật sau: + Mỗi dòng đều bắt đầu và kết thúc bởi số 1. + Phần tử thứ j ở dòng k nhận được bằng cách cộng 2 phần tử thứ j-1 và j ở dòng thứ k-1. Uses Crt; Var Dong:Array[0..20] Of Byte; n,i,j:Byte; Begin

Write('n= '); Readln(n);

Clrscr;

Dong[0]:=1;

Writeln(Dong[0]:4);

50

Giáo trình bài tập Pascal {Khoi tao gia tri cua dong} For i:=1 To n Do Dong[i]:=0; {Voi moi dong i} For i:=1 To n Do Begin For j:=i DownTo 1 Do Begin

Dong[j]:=Dong[j-1]+Dong[j];

Write(Dong[j]:4);

End; Writeln(Dong[i]:4); End; Readln; End. BÀI TẬP TỰ GIẢI Bài tập 5.13: Viết chương trình nhập vào một dãy số thực và số thực x. Thông báo lên màn hình số lượng các phần tử trong dãy bằng x và vị trí của chúng. Bài tập 5.14: Nhập vào một mảng các số nguyên. a/ Xếp lại mảng đó theo thứ tự giảm dần. b/ Nhập vào một số nguyên từ bàn phím. Chèn số đó vào mảng sao cho mảng vẫn có thứ tự giảm dần. (không được xếp lại mảng) Gợi ý: - Tìm vị trí cần chèn: i. - Đẩy các phần tử từ vị trí i tới n sang phải 1 vị trí. - Gán: A[i]=x; Bài tập 5.15: Cho 2 mảng số nguyên: Mảng A có m phần tử, mảng B có n phần tử. a/ Sắp xếp lại các mảng đó theo thứ tự giảm dần. b/ Trộn 2 mảng đó lại thành mảng C sao cho mảng C vẫn có thứ tự giảm dần (Không được xếp lại mảng C). Gợi ý: - Dùng 2 chỉ số i,j để duyệt qua các phần tử của 2 mảng A, B và k là chỉ số cho mảng C. - Trong khi (i

+ Nếu A[i]>B[j] thì: C[k]:=A[i]; i:=i+1;

+ Ngược lại: C[k]:=B[j]; j:=j+1;

51 = n k kj ikB A 1 * Bài tập 5.17: Viết chương trình nhập vào 2 dãy số nguyên (a)n và (b)m, m≤n. Kiểm tra xem dãy {b} có phải là dãy con của dãy {a} không? Bài tập 5.18: Viết chương trình nhập vào một dãy số nguyên a1, a2, ..., an. Tìm trong dãy {a} một dãy con tăng dần dài nhất (có số phần tử lớn nhất) và in ra màn hình dãy con đó.

Bài tập 5.19: Cho mảng 2 chiều A cấp mxn. Viết chương trình sắp xếp lại mảng A theo yêu cầu sau: a/ Các phần tử trên mỗi dòng được sắp xếp theo thứ tự giảm dần. b/ Các dòng được sắp xếp lại theo thứ tự tăng dần của tổng các phần tử trên mỗi dòng. Bài tập 5.20: Viết chương trình để kiểm tra một dãy các số nguyên được nhập vào từ bàn phím đã được sắp theo thứ tự tăng dần hay chưa theo 2 cách: Đệ qui và không đệ qui.

Gợi ý: - Nếu dãy có 1 phần tử thì dãy tăng dần. - Ngược lại:

+ Nếu A[n-1]>A[n] thì dãy không tăng dần.

+ Ngược lại: Gọi đệ qui với dãy có n-1 phần tử (bỏ bớt đi phần tử cuối cùng).

Bài tập 5.21: Viết chương trình nhập vào 2 mảng số nguyên A, B đại diện cho 2 tập hợp (không thể có 2 phần tử trùng nhau trong một tập hợp). Trong quá trình nhập, phải kiểm tra: nếu phần tử vừa nhập vào đã có trong mảng thì không bổ sung vào mảng.

a/ In ra màn hình hợp của 2 tập hợp A, B. b/ In ra màn hình hiệu của 2 tập hợp A, B. Gợi ý: a/ - In ra màn hình tất cả các phần tử của tập hợp A. - Duyệt qua tất cả các phần tử bi∈B. Nếu bi∉A thì in bi ra màn hình. b/ Duyệt qua tất cả các phần tử ai∈A. Nếu ai∉B thì in ai ra màn hình. 52 ∑ Giáo trình bài tập Pascal - Nếu dãy nào hết trước thì đem phần còn lại của dãy kia bổ sung vào cuối dãy C. Bài tập 5.16: Viết chương trình tính tổng và tích 2 ma trận vuông A, B cấp n. Gợi ý: Công thức tính tổng 2 ma trận:Cij = Aij + Bij Công thức tính tích 2 ma trận:Cij = Giáo trình bài tập Pascal Bài tập 5.22: Viết chương trình tính tổng của 2 đa thức h(x) = f(x) + g(x). Trong đó, mỗi đa thức có dạng: a0 + a1x + a2x2 + ... + anxn. Gợi ý: Dùng các mảng A, B, C để lưu trữ các hệ số ai của các đa thức f(x), g(x) và h(x). Bài tập 5.23: Viết chương trình để tìm các phương án đặt 8 quân hậu trên bàn cờ vua (ma trận 8x8) sao cho các quân hậu không ăn được nhau. Gợi ý: Dùng giải thuật quay lui. Bài tập 5.24: Viết chương trình tính định thức của ma trận vuông cấp n. Gợi ý: Dùng cách tính định thức theo phương pháp GAUSE. 53 Giáo trình bài tập Pascal Chương 6 XÂU KÝ TỰ (STRING) I. KHAI BÁO KIỂU STRING TYPE TênKiểu = STRING[Max]; VAR Tên biến : TênKiểu; hoặc khai báo biến trực tiếp: VAR Tên biến : STRING[Max]; Trong đó Max là số ký tự tối đa có thể chứa trong chuỗi (Max∈ [0,255]). Nếu không có khai báo [Max] thì số ký tự mặ mặc định trong chuỗi là 255. Ví dụ: Type Hoten = String[30]; St80 = String[80]; Var Name : Hoten;

Line : St80;

St : String; {St có tối đa là 255 ký tự}

II. TRUY XUẤT DỮ LIỆU KIỂU STRING - Có thể sử dụng các thủ tục xuất nhập Write, Writeln, Readln để truy xuất các biến kiểu String. - Để truy xuất đến ký tự thứ k của xâu ký tự, ta sử dụng cú pháp sau:Tênbiến [k]. III. CÁC PHÉP TOÁN TRÊN XÂU KÝ TỰ

3.1. Phép nối xâu: +

3.2. Các phép toán quan hệ: =, , , >=.

Chú ý: Các phép toán quan hệ được so sánh theo thứ tự từ điển. IV. CÁC THỦ TỤC VÀ HÀM VẾ XÂU KÝ TỰ 4.1. Hàm lấy chiều dài của xây ký tự LENGTH(St : String):Integer; 4.2. Hàm COPY(St : String; Pos, Num: Byte): String; Lấy ra một xâu con từ trong xâu St có độ dài Num ký tự bắt đầu từ vị trí Pos . 4.3. Hàm POS(SubSt, St :String):Byte; Kiểm tra xâu con SubSt có nằm trong xâu St hay không? Nếu xâu SubSt nằm trong xâu St thì hàm trả về vị trí đầu tiên của xâu con SubSt trong xâu St, ngược lại hàm trả về giá trị 0.

4.4. Thủ tục DELETE(Var St:String; Pos, Num: Byte); Xoá trong xâu St Num ký tự bắt đầu từ vị trí Pos. 4.5. Thủ tục INSERT(SubSt: String; Var St: String; Pos: Byte); Chèn xâu SubSt vào xâu St bắt đầu tại vị trí Pos. 4.6. Thủ tục STR(Num; Var St:String); 54 Giáo trình bài tập Pascal Đổi số nguyên hay thực Num thành dạng xâu ký tự, kết quả lưu vào biến St. 4.7. Thủ tục VAL(St:String; Var Num; Var Code:Integer); Đổi xâu số St thành số và gán kết quả lưu vào biến Num. Nếu việc chuyển đổi thành công thì biến Code có giá trị là 0, ngược lại biến Code có giá trị khác 0 (vị trí của lỗi). BÀI TẬP MẪU Bài tập 6.1: Viết chương trình nhập vào một xâu ký tự từ bàn phím. Đổi xâu ký tự đó sang chữ in hoa rồi in kết quả ra màn hình. Ví dụ :Xâu abcdAbcD sẽ cho ra xâu ABCDABCD. Uses Crt; Var St:String; i:Byte; Begin

Write('Nhap xau St: '); Readln(St);

For i:=1 to length(St) do St[i]:=Upcase(St[i]);

Write('Xau ket qua: ', St);

Readln;

End. Bài tập 6.2: Viết chương trình nhập vào một xâu ký tự từ bàn phím. Đổi xâu ký tự đó sang chữ thường rồi in kết quả ra màn hình. Ví dụ :Xâu abCdAbcD sẽ cho ra xâu abcdabcd. Uses Crt; Var St:String; i:Byte; Begin

Write('Nhap xau St: '); Readln(St);

For i:=1 to length(St) do

If St[i] IN ['A'..'Z'] Then St[i]:=CHR(ORD(St[i])+32);

Write('Xau ket qua: ', St);

Readln;

End. Bài tập 6.3: Viết chương trình đếm số ký tự chữ số trong một xâu ký tự được nhập vào từ bàn phím. Uses Crt; Var St:String; i,d:Byte; 55 Giáo trình bài tập Pascal Begin

Write('Nhap xau St: '); Readln(St);

For i:=1 to length(St) do

If St[i] IN ['0'..'9'] Then d:=d+1;

Write('So ky tu chu so trong xau: ', d);

Readln;

End. Bài tập 6.4: Viết chương trình nhập một xâu từ bàn phím. In ra xâu đó sau khi xóa hết các ký tự trắng thừa trong xâu. (Ký tự trắng thừa là các ký tự trắng đầu xâu, cuối xâu và nếu ở giữa xâu có 2 ký tự trắng liên tiếp nhau thì có 1 ký tự trắng thừa).

Uses Crt; Var St:String; Procedure XoaTrangThua(Var St:String); Begin

{Xóa các ký tự trắng ở đầu xâu}

While St[1]=#32 Do Delete(St,1,1);

{Xóa các ký tự trắng ở cuối xâu}

While St[Length(St)]=#32 Do Delete(St,Length(St),1);

{Xóa các ký tự trắng ở giữa xâu}

While POS(#32#32,St)0 Do Delete(St,POS(#32#32,St),1);

End; Begin

Write('Nhap xau St: '); Readln(St);

XoaTrangThua(St);

Write('Xau sau khi xoa cac ky tu trang thua: ', St);

Readln;

End. Bài tập 6.5: Viết chương trình liệt kê các từ của một xâu ký tự được nhập vào từ bàn phím, mỗi từ phải được viết trên một dòng. Uses Crt; Var St:String; Procedure XoaTrangThua(Var St:String); Begin

{Xóa các ký tự trắng ở đầu xâu}

While St[1]=#32 Do Delete(St,1,1);

{Xóa các ký tự trắng ở cuối xâu}

While St[Length(St)]=#32 Do Delete(St,Length(St),1);

56 Giáo trình bài tập Pascal {Xóa các ký tự trắng ở giữa xâu} While POS(#32#32,St)0 Do Delete(St,POS(#32#32,St),1); End; Begin

Write('Nhap xau St: '); Readln(St);

XoaTrangThua(St);

St:=St+#32;

Writeln('Liet ke cac tu trong xau: ');

While POS(#32,St)0 Do

Begin

Writeln(Copy(St,1,POS(#32,St)));

Delete(St,1,POS(#32,St));

End; Readln; End. Bài tập 6.6: Viết chương trình nhập vào một xâu ký tự từ bàn phím. Tìm xâu đảo ngược của xâu đó rồi in kết quả ra màn hình theo 2 cách: Đệ qui và không đệ qui. Ý tưởng: - Nếu xâu St có 1 ký tự thì xâu đảo = St. - Ngược lại: Xâu đảo = Ký tự cuối + Đệ qui(Phần còn lại của xâu St). Uses Crt; Var St:String; {Giải thuật không đệ qui} Function XauDao(St:String):String; Var S:String; i:Byte; Begin

S:='';

For i:=Length(St) DowTo 1 Do S:=S+St[i];

XauDao:=S;

End; {Giải thuật đệ qui}

Function DeQui(St:String):String;

Begin

If Length(St)

Write('Nhap xau St: '); Readln(St);

Write('Xau dao nguoc: ', XauDao(St));

Readln;

End. Bài tập 6.7: Viết chương trình nhập vào một xâu ký tự từ bàn phím. Thông báo lên màn hình các chữ cái có trong xâu và số lượng của chúng ( Không phân biệt chữ hoa hay chữ thường).

Ý tưởng: - Dùng một mảng dem với chỉ số là các chữ cái để lưu trữ số lượng của các chữ cái trong xâu. - Duyệt qua tất cả các ký tự của xâu St: Nếu ký tự đó là chữ cái thì tăng ô biến mảng dem[St[i]] lên 1 đơn vị. Uses Crt; Var St:String; dem: Array['A'..'Z'] Of Byte;

i:Byte;

ch:Char;

Begin

Write('Nhap xau St: '); Readln(St);

{Khởi tạo mảng}

For ch:='A' To 'Z' Do dem[ch]:=0;

{Duyệt xâu}

For i:=1 To Length(St) Do

If Upcase(St[i]) IN ['A'..'Z'] Then Inc(dem[Upcase(St[i])]);

{Liệt kê các ký tự ra màn hình}

For ch:='A' To 'Z' Do

If dem[ch]>0 Then Writeln(ch,' : ',dem[ch]); Readln; End. Bài tập 6.8: Viết chương trình xóa các ký tự chữ số trong một xâu ký tự được nhập vào từ bàn phím. Uses Crt; Var St:String; 58 Giáo trình bài tập Pascal {Hàm POSNUM kiểm tra xem trong xâu St có ký tự chữ số hay không? Nếu có, hàm trả về vị trí đầu tiên của ký tự chữ số, ngược lại hàm trả về giá trị 0} Function POSNUM(St:String):Byte; Var OK:Boolean; i:Byte; Begin

OK:=False;

i:=1;

While (i

If St[i] IN ['0'..'9'] Then OK:=True Else i:=i+1; If OK Then POSNUM:=i Else POSNUM:=0; End; Begin

Write('Nhap xau St: '); Readln(St);

While POSNUM(St)0 Do Delete(St,POSNUM(St),1);

Write('Xau sau khi xoa: ',St);

Readln;

End. Bài tập 6.9: Viết chương trình để mã hoá và giải mã một xâu ký tự bằng cách đảo ngược các bit của từng ký tự trong xâu. Uses crt; Var st:string; {Hàm đảo bit ký tự c}

Function DaoBit(c:char):char;

Var n,i,s,bitcuoi,Mask:byte;

Begin

{Đổi ký tự sang số} n:=ORD(c);

{s: kết quả đảo bit, Mask: mặt nạ dùng để bật bit thứ i}

s:=0;

Mask:=128;

For i:=1 To 8 Do {duyệt qua 8 bit của n} Begin

{Lấy bit cuối cùng của n: bit cực phải}

bitcuoi:=n AND 1;

n:=n shr 1; {loại bỏ bit cuối cùng: n:=n DIV 2}

{Bật bit thứ i lên: từ trái sang phải}

if bitcuoi=1 then s:=s OR Mask;

59 Giáo trình bài tập Pascal Mask:=Mask shr 1; { Mask:= Mask DIV 2} End; DaoBit:=CHR(s); End; Function MaHoa(st:string):string; Var i:Byte; Begin

{Đảo bit từng ký tự trong xâu st}

For i:=1 To Length(st) Do st[i]:=DaoBit(st[i]);

Mahoa:=st;

End; Begin

Write('Nhap xau: '); Readln(st);

st:=MaHoa(st);

Writeln('Xau sau khi ma hoa: ',st);

Readln;

st:=MaHoa(st);

Writeln('Xau sau khi giai ma: ',st);

Readln;

End.

Bài tập 6.10: Viết chương trình thực hiện phép cộng 2 số tự nhiên lớn (không quá 255 chữ số). Uses crt; Var so1,so2,kqua:string; Procedure LamDayXau(Var st1,st2:string);

{Them so 0 vao truoc xau ngan}

var i:Byte;

Begin

If Length(st1)>Length(st2) Then For i:=1 To Length(st1)-Length(st2) Do st2:='0'+st2 Else For i:=1 To Length(st2)-Length(st1) Do st1:='0'+st1; End; Function Cong(st1,st2:string):string; Var i,a,b,c,sodu:Byte;

code:integer;

st,ch:string;

Begin st:=''; sodu:=0; 60