THUẬT TOÁN NHÁNH CẬN
1. TƯ TƯỞNG CỦA THUẬT TOÁN NHÁNH CẬN
1.1. Trong các phương pháp giải bài toán qui hoạch nguyên, phương pháp nhánh
cận là một trong các phương pháp có hiệu quả. Phương pháp nhánh cận được Land A.H
và Doig A.G xây dựng năm 1960 giải bài toán qui hoạch nguyên (trình bày Tiết 2), đến
1963 được Little J.D, Murty K.G, Sweeney D.W và Karen C sử dụng thành công giải
bài toán người du lịch (trình bày trong Tiết 3). Năm 1979 Giáo sư Hoàng Tụy đã ứng
dụng thành công phương pháp này vào giải bài toán qui hoạch lõm. Đây là thuật toán
ứng dụng rộng rãi để giải các bài toán tối ưu khó.
Xét bài toán qui hoạch rời rạc
min , Z fX = ( ) (1)
X G ∈ (G là tập hữu hạn ) (2)
1.2. Tư tưởng của phương pháp nhánh cận gồm các phép xây dựng sau cho phép
giảm bớt khối lượng lựa chọn.
1. Tính cận dưới. Tìm cận dưới của hàm mục tiêu f ( x) trên tập các phương án
G (hoặc trên tập con G′ nào đó của G ) tức là số ζ (G) hay ζ (G′) sao cho:
f ( x G ) ≥ ζ ( ) với ∀x∈G ( hay f ( x G ) ≥ ζ ( ′) với ∀x∈G′).
2. Chia thành các tập con (rẽ nhánh ). Chia dần dần tập phương án G thành
cây các tập con (các nhánh). Việc chia nhánh thực hiện theo sơ đồ nhiều bước sau:
Bước 0. Đặt 0 G G≡ . Bằng một cách nào đó 0 G được chia thành một số hữu
hạn các tập con ( thường là không giao nhau) 1
11 1
1 2 , ,...., GG Gr .
Bước k ≥1. Có tập 1 2 , ,...., k
kk k GG Gr cần chia nhánh. Ta chọn tập ( )
k Gϑ k theo một
qui tắc nào đó và chia thành một số hữu hạn các tập con : () () () ,1 ,2 , ( ) , ,...., kk k GG G ϑϑ ϑ k k k sk ,
gồm có s( ) k tập. Khi đó, tập cần chia nhánh tiếp theo là
12 1 1 , ,...., , ,..., kk k
kk k k k GG G G G ϑ ϑ − + r , () () ()() ,1 ,2 , , ,...., kk k GG G ϑϑ ϑ k k k sk
Ta đánh số lại là 1
11 1
1 2 , ,...., k
kk k GG Gr +
++ + .
3. Tính lại đánh giá
Nếu tập G G 1 2 ⊂ thì ( ) ( ) 1 2
min min
XG XG
f X fX ∈ ∈
≥ .
Vì vậy khi chia tập G′ thành 1 2 , ,...., GG Gs ′ ′ ′ sao cho
1
'
s
i
i
G G
=
=∪ ′ thì cận của bất
kì tập Gi
′ đều có ζ ζ (G Gi s i
′ ′ ) ≥ = ( ), 1,.., ( ). Trong các tình huống cụ thể ta thường
nhận được các đánh giá tốt , tức là đối với một i nào đó ( ) ( ). G G i ζ ζ ′ ; ′
Bùi Thế Tâm VI.2 Quy hoạch rời rạc
4. Tính phương án
Đối với các bài toán cụ thể có thể chỉ ra các phương pháp khác nhau để tìm ra các
phương án trong các tập con được chia liên tiếp. Phương pháp này dựa trên đặc thù của
mỗi bài toán cụ thể. Nhờ phương án mới tìm được ở mỗi bước ta có thể cải tiến cận trên
(ban đầu gán cho cận trên giá trị là +∞ ) bằng cách gán cho cận trên giá trị hàm mục
tiêu tốt nhất tại thời điểm đó.
5. Tiêu chuẩn tối ưu. Giả sử
1
s
i
i
G G
=
=∪ và phương án X G∈ ϑ thỏa mãn điều
kiện: ( ) ( ) ( ), 1,.., i f X G G is ϑ = ≤ ∀= ζ ζ thì X là phương án tối ưu của bài toán
(1)-(2). Qui tắc này được ứng dụng ở giai đoạn chia nhánh .
6. Đánh giá độ chính xác của lời giải xấp xỉ. Giả sử
( ) 1,.., 1
, min
s
i i
i s i
GG G ζ ζ = =
= = ∪ .
Nếu X là một phương án của bài toán xuất phát thì min ( ) ( ) x G
ζ f X fX ∈
≤ ≤ . Nếu
f X( ) −ζ đủ nhỏ thì X có thể lấy làm lời giải xấp xỉ với đánh giá độ xấp xỉ là
∆= − f X( ) ζ .
1.3. Lược đồ tổng quát của phương pháp nhánh cận. Chia tập phương án
G thành cây tập con.
Bước 0. Tính ( ) ( ) 0 ζ ζ G G = . Nếu tìm được phương án X sao cho
f ( X G ) = ζ ( ) thì X là phương án tối ưu. Ngược lại, chia 0 G = 1
11 1
1 2 .... GG G ∪ ∪∪ r ,
tức là chia thành các tập con (thường là không giao nhau).
Bước k ≥1. Tính các đánh giá ( ), 1,.., k Gi r i k ζ = . Nếu tìm được phương án X ,
k X G∈ r sao cho ( ) ( ) ( ), k k
r i fX G G = ≤ ζ ζ với 1,2,.., k ∀i r = , thì X là phương án
tối ưu, quá trình kết thúc. Ngược lại, chọn ( )
k Gϑ k để chia, theo tiêu chuẩn
( ( ) ) ( ) 1,..,
min
k
k k
k i
i r
G G ϑ ζ ζ = = . Ta chia tập ( )
k Gϑ k thành một số tập con
() () () ()() ,1 ,2 , .... kk k k GG G G ϑϑ ϑ ϑ k k k k sk = ∪ ∪∪ .
Tập cần chia tiếp theo là
12 1 1 , ,...., , ,..., kk k
kk k k k GG G G G ϑ ϑ − + r , () () () ,1 ,2 , , ,...., k
kk k GG G ϑϑ ϑ k k ks
Sau đó ta đánh số lại là 1
11 1
1 2 , ,...., k
kk k GG Gr +
+ + + và sang bước k+1.
Lý thuyết về nhánh cận.
Đệ Quy Quay Lui
Có tài liệu còn gọi nó là ” Thử và sai”. đã là đệ quy quay lui thì trong thủ tục của nó là thủ tục đệ quy và có “quay lui”. Ta tìm hiểu quay lui ở đâu và như thế nào?
Trước hết ta xét ví dụ:
Một từ được gọi là chân chính loại M, N nếu nó được xây dựng từ tập hợp gồm M ký tự, có độ dài N và không có 2 từ con nào liên tiếp giống nhau.
Giả sử tập M={‘1’, ‘2’, ‘3’}
Ví dụ: 1232; 2123; 1231 là những từ chân chính loại 3,4; còn 1123;1212;1233 là những từ không phải là từ chân chính loại 3,4.
Tất nhiên ở đây không phải là ta xây dựng tất cả các từ có độ dài N, sau đó loại trừ những từ không thoả mãn, mà ta lần lượt xây dựng các xâu.
Khởi tạo ban đầu là xâu rỗng, ta tiến hành ghép các ký tự , tại mỗi bước ghép ta kiểm tra xem nó có thoả mãn điều kiện bài toán không( có hai từ con liền nhau giống nhau không). Nếu thoả mãn ta kiểm tra xem xâu có độ dài bằng N hay chưa. Nếu xâu đã có độ dài bằng N ta in kết quả, nếu chưa có độ dài bằng N ta ghép bước tiếp. Nếu tất cả các ký tự được chọn để ghép đều không thoả mãn điều kiện bài toán thì việc chọn ký tự trước đó sai, ta phải xoá ký tự trước đó đi và thay bởi ký tự khác để bước ghép tiếp được thành công. Việc xoá ký tự trước đó để tìm ký tự khác ghép vào người ta gọi là quay lui. Trong trường hợp xâu có độ dài bằng N( đã thoả mãn bài toán) thì ta được một kết quả. Để tìm kết quả khác, ta xoá ký tự cuối cùng này đi rồi tìm ký tự khác để ghép vào cũng gọi là quay lui.
Việc đó thể hiên ở thủ tục procedure find( x : integer);
Còn hàm function ok(i : integer):boolean; là để kiểm tra xem có hai từ con liền nhau giống nhau hay không
function ok(i : integer):boolean;
var k : integer;
begin
ok := true;
for k := 2 to i div 2 do
if copy(s,i-2*k+1,k) = copy(s,i-k+1,k) then
begin
ok := false;
exit;
end;
end;
procedure find( x : integer);
var i : integer;
begin
if x > n then
xuat
else
for i := 1 to m do
if s[length(s)] <> st[i] then
begin
s := s + st[i];
if ok(s) then
begin
find(x+1);
delete(s,length(s),1);{ xoá để quay lại bước trước}
end
else
delete(s,length(s),1); { xoá để quay lại bước trước}
end;
end;
Ta xét ví dụ 2: Đường đi trên lưới ô vuông
Cho lưới ô vuông cấp NxM. Trên mỗi ô (i,j) của lưới ghi một số nguyên a[i,j]. Ô (x,y) đi được sang ô (x’,y’) nếu 2 ô này chung cạnh và a[x,y]<= a[x’,y’]. Hãy lập trình giảI quyết các công việc sau:
a) Tìm tất cả các đường đi từ ô (x,y) đến ô(r,s).
b) Tìm đường đi qua ít ô nhất
( giả thiết rằng có đường đi)
Ta lần lượt xây dựng các bước đi, bắt đầu từ ô (x,y), tại mỗi bước kiểm tra xem có đi qua được một trong các ô chung cạnh với nó hay không? Nếu tồn tại một bước đI thì ta ghi nhận bước đi và đi sang ô mới, tại ô mới này ta kiểm tra xem đã đến đích hay chưa. Nếu đã đến đích ta thông báo kết quả, sau đó lùi lại bước trước để tìm đường đI khác( quay lui). Còn trong trường hợp chưa đến đích thì tìm ô chung cạnh đi tiếp( đệ quy).
Thủ tục sau minh hoạ giảI thuật này.
Procedure Try (x,y: integer);
Var j: integer;
If (x = p) and (y = q) then
Thong_bao
else
Begin
For j := 1 to 4 do
Begin
u := x + dong[j];
v := y + cot[j];
If (A[u, v] <= A[x, y])and(b[u,v]=0) then
Begin
Inc(count);
d[count] := u;
c[count] := v;
B[u,v]:=1
Try (u,v);
dec(count);
b[u,v]:=0;
End;
End;
End;
Bây giờ ta xét bài toán đặt 8 con hậu trên bàn cờ vua để không con nào ăn được nhau.
Ta lần lượt đặt từng con hậu, giả sử ta đặt được con hậu thứ k, ta tiến hành đặt con hậu thứ k+1. Giả sử ta định đặt con hậu thứ k+1 tại ô (x,k+1) của bàn cờ( ta lần lượt xét x=1..8), chúng ta tiến hành kiểm tra xem trên dòng x của bàn cờ và trên 2 đường chéo đi qua ô (x,k+1) đã có quân hậu nào chưa, nếu có một vị trí đặt hậu thoả mãn ta ghi nhận bước đặt hậu này, còn nếu không có bước nào thoả mãn thì phảI đặt lại con hậu thứ k( quay lui). Tại mỗi bước ta lùi lại bước trước để lấy tất cả các nghiệm.
Thủ tục thể hiện như sau:
procedure find( x : integer);
var y : integer;
begin
if x = 9 then
xuat
else
for y := 1 to 8 do
if ok(x,y)and(a[x,y]=0) then
begin
a[x,y] := 1;
find(x+1);
a[x,y] := 0;
end;
end;
Ta xét bài toán mã đi tuần: Trên bàn cờ vua con mã đang ở ô (x,y), hãy cho biết con mã có đi qua tất cả các ô, mỗi ô đi đúng một lần hay không?
Khởi tạo ban đầu con mã đang ở ô (x,y), ta duyệt qua các nước đi có thể của nó, tại một ô con mã có thể đi đến 8 ô như luật của đi của con mã. Tại một ô giả sử đó là bước đI thứ k của con mã, Ta chon một trong các nước đi của nó, kiểm tra xem bước đi tiếp có thoả mãn hay không ( ô đI tiếp đã đI qua lần nào chưa, có đI ra ngoài bàn cờ không.Nếu thoả mãn ghi nhận nước đI, sau đó ta kiểm tra xem bàn cờ đã đI hết chưa, nếu hết in kết quả, ngược lại đi tiếp.Nếu không còn bước đI tiếp thì phảI đI lại bước trước đó để đi tiếp được bước sau.
Thủ tục sau thể hiện thuật giảI trên.
procedure try(i:integer);
var j,dong,cot:integer;
begin
if i> n*n then
xuat
else
begin
if kt = 1 then
exit;
for j:=1 to 8 do
begin
dong:=x+d[j];
cot:=y+c[j];
if (dong in s)and(cot in s)and(a[dong,cot] = 0)then
begin
a[dong,cot]:=i;
x:=dong;
y:=cot;
try(i+1);
x:=dong-d[j];
y:=cot-c[j];
a[dong,cot]:=0;
end;
end;
end;
end;
Từ các ví dụ trên ta có sơ đồ thuật giải đệ quy quay lui:
Procedure TRY(i: integer);
Var k: integer;
Begin
For k:=1 to n do
Begin
Chọn nước đi thứ k
If đi được THEN
Begin
Ghi nhận nước đi
If i<n THEN
Try(i+1)
Else
In kết quả
Bỏ việc ghi nhận
End;
End;
End;
Lý Thuyết Đệ Quay Lui.
Đây là đề tin hsg tin Hà Nội (2017) mới có ảnh các bạn xem tạm ( sẽ có dạng văn bản trong vài ngày ).
Đề Thi HSG Tin lớp 11 Hà Nội năm 2017.
CÂU HỎI VÀ BÀI TẬP
Câu 1: Tại sao mảng là kiểu dữ liệu có cấu trúc?
- Mảng là kiểu dữ liệu có cấu trúc bởi vì mảng (một chiều, hai chiều hay nhiều chiều) là kiểu có cấu trúc được đề cập tới sớm nhất trong các ngôn ngữ lập trình. Nó được xây dựng từ những kiểu dữ liệu dã có theo quy tắc khuôn dạng do ngôn ngữ lập trình cung cấp. Nó được dùng để chỉ định một nhóm đối tượng cùng một tính chất nào đó. Chẳng hạn, vectơ là một nhóm các số mà mỗi số ta có thể xác định chỉ cần biết chỉ số. Như vậy, để khai báo kiểu mảng phải chỉ ra kiểu dữ liệu chung của các phần tử và kiểu chỉ số.
- do mảng là kiểu dữ liệu có cấu trúc, hơn nửa dữ liệu kiểu mảng lại rất tốn bộ nhớ vậy nên nhất thiết phải khai báo kích thước của mảng.
Câu 3:
- Các phần tử của mảng có thể có những kiểu sau đây: real, boolean, integer, longint.
Câu 4: Tham chiếu đến phàn tử của mảng bằng cách nào?
- Tham chiếu đến phần tử của mạng có 2 kiểu :
** Với mảng 1 chiều:
- Cách tham chiếu đến mảng: A[i] với i là chỉ số phân tử trong mảng.
vd: Vẫn xét mảng 10 20 30 5 6 7
A[1]=10; A[2]=20; A[3]=30; A[4]=50; A[5]=6; A[7]=7
- Cách khai báo mảng: Có 2 cách khai báo:
Khai báo trực tiếp: Thường thì cách khai báo trực tiếp được dùng nhiều hơn vì nó ngắn gọn.
var <tên mảng>:array[kiểu chỉ số] of <kiểu phần tử>;
vd:
a:array[1..100] of integer;
b,c:array[1..250] of integer;
Khai báo gián tiếp:
type <tên kiểu mảng>=array[kiểu phần tử] of <kiểu chỉ số>;
var <tên mảng>:<tên kiểu mảng>;
vd:
type mang=array[1..100] of integer;
var a,b,c:mang;
**Với mảng 2 chiều :
- Tham chiếu: Vì mảng 2 chiều là bảng nên sẽ cần chỉ số hàng và chỉ số cột: A[i,j] với i là chỉ số hàng, j là chỉ số cột.
- Khai báo: Tương tự như mảng 1 chiều nhưng thêm chỉ số cột.
Câu 5: Viết chương trình nhập từ bàn phím số nguyên dương N ( N <= 100) và dãy A gồm N số nguyên A1, A2, A3,… có giá trị tuyệt đối không lớn hơn 1000. Hãy cho biết dãy A có phải là 1 cấp số cộng không và thông báo kết quả ra màn hình.
b. Số lượng số nguyên tố trong dãy
F0=0, F1=1, FN= FN-1+FN-2 với N =>2
Viết chương trình nhập từ bàn phím số nguyên dương N và đưa ra màn hình số hạng thứ N của dãy Phi nô na xi . Chương trình thực hiện được với giá trị lớn nhất của N là bao nhiêu ?
Câu 1: Tại sao mảng là kiểu dữ liệu có cấu trúc?
- Mảng là kiểu dữ liệu có cấu trúc bởi vì mảng (một chiều, hai chiều hay nhiều chiều) là kiểu có cấu trúc được đề cập tới sớm nhất trong các ngôn ngữ lập trình. Nó được xây dựng từ những kiểu dữ liệu dã có theo quy tắc khuôn dạng do ngôn ngữ lập trình cung cấp. Nó được dùng để chỉ định một nhóm đối tượng cùng một tính chất nào đó. Chẳng hạn, vectơ là một nhóm các số mà mỗi số ta có thể xác định chỉ cần biết chỉ số. Như vậy, để khai báo kiểu mảng phải chỉ ra kiểu dữ liệu chung của các phần tử và kiểu chỉ số.
Chúng ta phải khai báo kích thước cùa mảng bởi vì để cách đánh số các phần tử của nó.
Câu 2: Tại sao phải khai báo kích thức của mảng?- do mảng là kiểu dữ liệu có cấu trúc, hơn nửa dữ liệu kiểu mảng lại rất tốn bộ nhớ vậy nên nhất thiết phải khai báo kích thước của mảng.
Câu 3:
- Các phần tử của mảng có thể có những kiểu sau đây: real, boolean, integer, longint.
Câu 4: Tham chiếu đến phàn tử của mảng bằng cách nào?
- Tham chiếu đến phần tử của mạng có 2 kiểu :
** Với mảng 1 chiều:
- Cách tham chiếu đến mảng: A[i] với i là chỉ số phân tử trong mảng.
vd: Vẫn xét mảng 10 20 30 5 6 7
A[1]=10; A[2]=20; A[3]=30; A[4]=50; A[5]=6; A[7]=7
- Cách khai báo mảng: Có 2 cách khai báo:
Khai báo trực tiếp: Thường thì cách khai báo trực tiếp được dùng nhiều hơn vì nó ngắn gọn.
var <tên mảng>:array[kiểu chỉ số] of <kiểu phần tử>;
vd:
a:array[1..100] of integer;
b,c:array[1..250] of integer;
Khai báo gián tiếp:
type <tên kiểu mảng>=array[kiểu phần tử] of <kiểu chỉ số>;
var <tên mảng>:<tên kiểu mảng>;
vd:
type mang=array[1..100] of integer;
var a,b,c:mang;
**Với mảng 2 chiều :
- Tham chiếu: Vì mảng 2 chiều là bảng nên sẽ cần chỉ số hàng và chỉ số cột: A[i,j] với i là chỉ số hàng, j là chỉ số cột.
- Khai báo: Tương tự như mảng 1 chiều nhưng thêm chỉ số cột.
Câu 5: Viết chương trình nhập từ bàn phím số nguyên dương N ( N <= 100) và dãy A gồm N số nguyên A1, A2, A3,… có giá trị tuyệt đối không lớn hơn 1000. Hãy cho biết dãy A có phải là 1 cấp số cộng không và thông báo kết quả ra màn hình.
PROGRAM Bai_tap;
USES CRT;
Var A:array[1..100] of integer;
i,cs,n:integer;
kt:boolean;
BEGIN
Clrscr;
Write('Nhap so luong phan tu cua day : '); Readln(n);
For i:=1 to n do
Begin
Write('Nhap phan tu thu ',i,' : ');
Readln(A[i]);
End;
kt:=True;
cs:=A[2]-A[1];
For i:=3 to n do
If (A[i]-A[i-1]) <> cs then
Begin
kt:=False;
Break;
End;
If kt=True then Writeln('Day A la mot cap so cong!')
Else Writeln('Day A khong phai la mot cap so cong!');
READLN;
END.
Câu 6: Viết chương trình nhập từ bàn phím số nguyên dương N ( N<= 100) và dãy A gồm N số nguyên dương A1, A2, A3,…An có trị tuyệt đối không lớn hơn 1000. Hyax đưa ra những thông tin sau:
a. Số lượng số chẵn và số lẻ trong dãyb. Số lượng số nguyên tố trong dãy
uses crt;
var
a:array [1..100] of integer;
n,i,x,a,b,c:integer;
begin
clrscr;
write('n:= ');readln(n);
for i:=1 to n do
begin
if a[i] mod 2 =0 then a:=a+1;
if a[i] mod 2 = 1 then b:=b+1;
for x:= 2 to trunc(sqrt(a[i])) do
if a[i] mod x <> 0 then c:=c+1;
end;
writeln('so so chan: ',a);
writeln('so so le: ',b);
writeln('so so ngto: ',c);
readln;
end.
Câu 7: Dãy F là dãy Phi nô na xa nếu :F0=0, F1=1, FN= FN-1+FN-2 với N =>2
Viết chương trình nhập từ bàn phím số nguyên dương N và đưa ra màn hình số hạng thứ N của dãy Phi nô na xi . Chương trình thực hiện được với giá trị lớn nhất của N là bao nhiêu ?
uses crt;
var m:integer;
l:longint;
function luythua(n:integer):real;
var
k,h:real;
i:integer;
begin
k:=1;
h:=1;
for i:=1 to n do k:=k*(1+sqrt(5))/2;
for i:=1 to n do h:=h*(1-sqrt(5))/2;
luythua:=k-h;
end;
begin
clrscr;
write('Nhap so hang: ');readln(m);
l:=round(luythua(m-1)/sqrt(5));
writeln('So hang thu ',m,' la: ',l);
readln;
end.
var m:integer;
l:longint;
function luythua(n:integer):real;
var
k,h:real;
i:integer;
begin
k:=1;
h:=1;
for i:=1 to n do k:=k*(1+sqrt(5))/2;
for i:=1 to n do h:=h*(1-sqrt(5))/2;
luythua:=k-h;
end;
begin
clrscr;
write('Nhap so hang: ');readln(m);
l:=round(luythua(m-1)/sqrt(5));
writeln('So hang thu ',m,' la: ',l);
readln;
end.
Câu 8: Chương trình sau đây thực hiện những gì?
- Bài toán giúp đảo ngược mảng.
Câu 10: Viết chương trình nhập từ bàn phím xâu kí tự S có độ dài không quá 100. Hãy cho biết co bao nhiêu chữ số xuất hiện trong xâu S, thông báo kết quả ra màn hình?
var
s:string[1..100];
i,dem:integer;
begin
write('nhap xau:');readln(s);
for i:=1 to length(s) do begin
case s[i] of
'1','2','3','4','5','6','7','8','9','0': dem:=dem+1;
end;
end;
writeln('so chu so: ',s);
readln;
end.
Giải bài tập Kiểu Bản Ghi (trang 79).
Giải bài tập bài thực hành số 4 tin học lớp 11
Câu 1: Nhập từ bàn phím một xâu...?
b) các bạn gõ y như câu a thay chữ p thành chữ bất kì (không bị trùng với biến trong chương trình).
Câu 2: Vết chương trình nhập từ bàn phím một xâu kí tự S và thông báo ra màn hình số lần xuất hiện của mỗi chữ cái tiếng Anh trong S (không phân biết chữ hoa hay thường).
uses crt;
var s:string;
a:array['A'..'Z'] of integer;
ch:char;
i:integer;
begin
clrscr;
write('nhap chuoi: '); readln(s);
for i:=1 to length(s) do
s[i]:=upcase(s[i]);
for ch:='A' to 'Z' do
for i:=1 to length(s) do
if s[i]=ch then inc(a[ch]);
for ch:='A' to 'Z' do
if a[ch]<>0 then
writeln(a[ch],ch);
readln;
end.
Câu 3: Nhập vào từ bàn phím một xâu. thay thế tất cả các cụm kí tự 'anh' bằng cụm kí tự 'em'?
uses crt;
var s:string;
begin
clrscr;
writeln('nhap chuoi: '); readln(s);
while pos('anh',s)<>0 do
begin
delete(s,pos('anh',s),3);
insert('em',s,pos('anh',s));
end;
writeln('chuoi sau khi chen: ');
writeln(s);
readln;
end.
Bài tập thực hành số 5 tin lớp 11 (Trang 73).
Bài tập thực hành số 2 tin học 11.(Trang 51)
Câu 1: Hãy cho biết sự giống và khác nhau của hai dạng câu lệnh if - then?
- Hai dạng câu lệnh If-then trong Pascal:
- Dạng khuyết: If <điều kiện> Then <câu lệnh>;
- Dạng đủ: If <điều kiện> Then <câu lệnh 1> Else <câu lệnh 2>;
- Sự Giống nhau: Cả hai dạng câu lệnh đều thực hiện việc kiểm tra <điều kiện> trước.
- Sự Khác nhau: Đối với dạng khuyết thiếu nếu <điều kiện sai> thì bỏ qua việc thực hiện câu lệnh sau Then và thực hiện tiếp chương trình; đối với dạng đủ nếu <điều kiện> sai thì thực hiện <câu lệnh 2>;
Begin
clrscr;
for ga:=1 to 36 do
begin
cho:=36-ga;
if (cho*4+ga*2=100) then Write('So ga: ', ga, ' So cho: ', cho);
end;
Readln;
Câu 1: Hãy cho biết sự giống và khác nhau của hai dạng câu lệnh if - then?
- Hai dạng câu lệnh If-then trong Pascal:
- Dạng khuyết: If <điều kiện> Then <câu lệnh>;
- Dạng đủ: If <điều kiện> Then <câu lệnh 1> Else <câu lệnh 2>;
- Sự Giống nhau: Cả hai dạng câu lệnh đều thực hiện việc kiểm tra <điều kiện> trước.
- Sự Khác nhau: Đối với dạng khuyết thiếu nếu <điều kiện sai> thì bỏ qua việc thực hiện câu lệnh sau Then và thực hiện tiếp chương trình; đối với dạng đủ nếu <điều kiện> sai thì thực hiện <câu lệnh 2>;
Câu 2: Câu lệnh ghép là gì? Tại sao phải có câu lệnh ghép?
- Câu lệnh ghép là một nhóm các câu lệnh được đặt trong cặp từ khóa Begin... End;
- Khi <câu lệnh> gồm nhiều thao tác phức hợp cần thiết phải có nhiều câu lệnh nhỏ để thực hiện thì các câu lệnh con được gộp với nhau trong câu lệnh ghép.
- Khi <câu lệnh> gồm nhiều thao tác phức hợp cần thiết phải có nhiều câu lệnh nhỏ để thực hiện thì các câu lệnh con được gộp với nhau trong câu lệnh ghép.
Câu 3: Có thể dùng cấu truc While-Do thay thế cho cấu trúc For-Do được không, nếu được thì làm câu 1a?
Var S: real;
a,N: integer;
Begin
clrscr;
Write('Nhap a:,') Readln(a);;
S:=1/a;
While N<100 do
begin
S:=S+1/(a+N);
N:=N+1;
End;
Writeln('Tong la: ', S:8:4);
Readln;
End.
a,N: integer;
Begin
clrscr;
Write('Nhap a:,') Readln(a);;
S:=1/a;
While N<100 do
begin
S:=S+1/(a+N);
N:=N+1;
End;
Writeln('Tong la: ', S:8:4);
Readln;
End.
Câu 4: Viết câu lệnh rẽ nhánh tính ?
a) if(sqr(x)+sqr(y)<=1) then z:=sqr(x)+sqr(y)
else if ((sqr(x)+sqr(y)>1) and y>=x) then z:=x+y
else z:=0.5;
else if ((sqr(x)+sqr(y)>1) and y>=x) then z:=x+y
else z:=0.5;
b) if (sqr(x-a)+sqr(x-b))<=R*R then z:=abs(x)+abs(y)
else z:=x+y;
else z:=x+y;
Câu 5: Lập trình tính:
a) For i:=1 to 50 do
Y:=Y+1/(1+i);
b) S:=1; N:=1;
While 1/(S*N) <2.E-6 Do
S:=S+1/(S*N);
Writeln('Tong la: ', S:8:4);
Readln;
End.
Y:=Y+1/(1+i);
b) S:=1; N:=1;
While 1/(S*N) <2.E-6 Do
S:=S+1/(S*N);
Writeln('Tong la: ', S:8:4);
Readln;
End.
Câu 6: Giải bài toán vừa gà vừa chó.
var ga, cho: integer;Begin
clrscr;
for ga:=1 to 36 do
begin
cho:=36-ga;
if (cho*4+ga*2=100) then Write('So ga: ', ga, ' So cho: ', cho);
end;
Readln;
End.
Câu 7: Tính tuổi cha và con?
var
cha, con: integer;
begin
write('Tuoi con: '); readln(con);
write('Tuoi cha: '); readln(cha);
if (con<0) or (con*2>=cha) or (con+25>cha) then
begin
write('Tuoi cha va tuoi con khong dung voi de bai'); readln;
exit;
end;
write('Sau ',cha-con*2,' nam nua thi tuoi cha gap doi tuoi con'); readln;
end.
cha, con: integer;
begin
write('Tuoi con: '); readln(con);
write('Tuoi cha: '); readln(cha);
if (con<0) or (con*2>=cha) or (con+25>cha) then
begin
write('Tuoi cha va tuoi con khong dung voi de bai'); readln;
exit;
end;
write('Sau ',cha-con*2,' nam nua thi tuoi cha gap doi tuoi con'); readln;
end.
Câu 8: Tĩnh lãi xuất?
Var A,B,TL:real;
T:integer;
BEGIN
write('Nhap so tien goi :');readln(A);
write('Nhap so tien can co ');readln(B);
TL:=A*0.3/100;
T:=0;
while A<B do
Begin
A:=A+TL;
T:=T+1;
End;
writeln('So thang can gui la ',T,' thang');
writeln('So tien linh ra sau thoi gian goi la ',A:12:0);
Readln;
END.
T:integer;
BEGIN
write('Nhap so tien goi :');readln(A);
write('Nhap so tien can co ');readln(B);
TL:=A*0.3/100;
T:=0;
while A<B do
Begin
A:=A+TL;
T:=T+1;
End;
writeln('So thang can gui la ',T,' thang');
writeln('So tien linh ra sau thoi gian goi la ',A:12:0);
Readln;
END.