Báo cáo chuyên đề BDGV tin học (Dạy học sinh giỏi)
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (290.21 KB, 43 trang )
Chuyên đề 3
BỒI DƯỠNG HỌC SINH GIỎI
I. BỔ SUNG KIẾN THỨC CƠ BẢN VỀ NGÔN NGỮ LẬP TRÌNH PASCAL
1.1 Sự cần thiết phải có kiểu mảng
Xét bài toán 1 “ Nhập vào nhiệt độ trung bình của mỗi ngày trong tuần, đưa
ra nhiệt độ trung bình của tuần và số ngày trong tuần có nhiệt độ trung bình cao hơn
nhiệt độ TB của tuần”.
Cần khai báo bao nhiêu biến lưu trữ nhiệt độ ngày ? Cần 7 biến.
Nếu yêu cầu bài toán không là 7 ngày mà là 1 năm thì có giải quyết được
không?
Bản chất thuật toán không có gì thay đổi nhưng phải khai báo quá nhiều biến,
chương trình phải viết nhiều câu lệnh nên rất dài.
Để khắc phục những hạn chế trên, NNLT ghép chung 7 biến trên thành một
dãy, đặt cho nó chung một tên và đánh dấu cho mỗi phần tử là một chỉ số. Đó chính
là kiểu dữ liệu mảng.
1.2 Kiểu mảng một chiều
Khái niệm: Mảng một chiều là một dãy hữu hạn các phần tử có cùng kiểu dữ
liệu.
Mảng là kiểu dữ liệu có cấu trúc.
Khi xây dựng kiểu mảng một chiều cần xác định:
- Tên mảng một chiều
- Số lượng phần tử trong mảng
- Kiểu dữ liệu của phần tử
- Cách khai báo biến mảng một chiều
- Cách truy cập vào từng phần tử của mảng
a. Khai báo
Cách 1: Khai báo biến trực tiếp:
Var <Tên biến mảng> : array [kiểu chỉ số] of <kiểu phần tử>;
Cách 2: khai báo biến gián tiếp
- Khai báo kiểu dữ liệu mảng
Type <Tên kiểu mảng> = array [Kiểu chỉ số] of <Kiểu phần tử>;
Var <Tên biến mảng> : <tên kiểu mảng>;
Trong đó:
- Tên kiểu mảng, Tên biến mảng do người lập trình đặt theo qui tắc đặt tên.
1
- Kiểu chỉ số thường là một đoạn số nguyên liên tục n1 .. n2 (n1<=n2). n1 gọi là
chỉ số đầu, n2 gọi là chỉ số cuối. Kiểu chỉ số phải có kiểu đếm được.
- Kiếu phần tử là các kiểu dữ liệu chuẩn và kiểu có cấu trúc ngoại trừ kiểu file
Ví dụ:
+ Khai báo biến lưu trữ nhiệt độ từng ngày trong 1 năm
C1: Var NhietDo= array[1..366] of Real;
C2:
Type Kmang1= array[1..366] of Real;
Var NhietDo: Kmang1;
b. Qui tắc tham chiếu đến phần tử mảng
<Tên biến mảng>[<Chỉ số>]
Trong đó: n1<= Chỉ số <=n2
Lưu ý: chỉ số <n1 hoặc > n2 sẽ sai
Khi tham chiếu đến phần tử xem như 1 biến có kiểu dữ liệu của phần từ
Ví dụ:
+ Nhiệt độ ngày đầu tiên:
NhietDo[1]
+ Nhiệt độ ngày 1 tháng 2:
NhietDo[32]
+ DiemTB[5]:=9
+ Nhập nhiệt độ từ ngày 1 đến ngày n
For i:= 1 to n do
Begin
Write(‘Nhap ngay thu’,i);
Readln(NhietDo[i]);
End;
+ Xem nhiệt độ từ ngày 1 đến ngày n
For i:= 1 to n do Write(Nhietdo[i]:6:2)
+ Tính tổng nhiệt độ trong năm
Tong:=0;
For i:= 1 to n do Tong:= Tong +Nhietdo[i];
+ Đếm số ngày có nhiệt độ lớn hơn nhiệt độ TB.
Dem:=0;
For i:= 1 to n do
If Nhietdo[i]>TB then dem:=dem+1
1.3 Mảng 2 chiều
+ Mảng 2 chiều là 1 bảng các phần tử cùng kiểu. Với bBảng cần quan tâm đến
số hàng, số cột.
a. Khai báo
Cách 1: Khai báo trực tiếp
2
Var <tên mảng>: array [Kiểu chỉ số dòng, kiểu chỉ số cột] of
tử>;
Cách 2: Khai báo gián tiếp:
Type <tên kiểu mảng>= array [Kiểu chỉ số dòng, kiểu chỉ số cột] of
Var <tên mảng>:<tên kiểu mảng>;
Ví dụ: Cho mảng a gồm 5 dòng, 4 cột, kiểu số nguyên ta khai báo như sau:
Type mang=array [1..5,1..4] of integer;
Var a: mang;
Var BangDiem: array[1..40,1..13] of real;
b Tham chiếu đến phần tử
<Tên biến mảng>[chỉ số dòng, chỉ số cột]
VD: BangDiem[1,6]
1.4 Một số bài tập
1. Viết chương trình nhập n, nhập dãy số nguyên có n phần tử lưu trữ vào mảng sau
đó tính:
a. Đếm số số dương (số lượng số chẵn, số lượng số nguyên tố).
b. Tính tổng các số trong mảng (tổng các số chẵn, trung bình cộng các số
dương, trung bình cộng các số âm, tổng các số ở vị trí chẵn)
c. Biến đổi các số dương trong mảng thành số 1, các số còn lại thành số 0
d. Tìm giá trị lớn nhất (bé nhất), tìm vị trí phần tử đầu tiên có giá trị bé nhất (số
dương bé nhất, số âm lớn nhất, vị trí đầu tiên của số lẻ, vị trí cuối cùng của
số chẵn)
e. Nhập một số nguyên x. Tìm vị trí xuất hiện của x nếu có, ngược lại thì thông
báo không có số này ( đếm xem số này xuất hiện bao nhiêu lần trong mảng)
f. Đổi chỗ giữa số lẻ đầu tiên và số chẵn cuối cùng của mảng nếu có.
g. Tìm vị trí của số có giá trị “gần” với giá trị trung bình cộng nhất. Khoảng
cách giữa 2 số là trị tuyệt đối của hiệu 2 số đó.
2: Viết chương trình nhập n, Sinh một dãy ngẫu nhiên n số từ 1 đến 100 sau đó xử
lý.
Hàm random(100): sinh số từ 0 đến 100.
a. Nhập vị trí k, xóa phần tử ở vị trí thứ k. Đưa dãy đã xóa ra màn hình
b. Nhập vị trí k và một số x tùy ý. Chèn số x vào vị trí k. Đưa dãy đã chèn ra
màn hình
c. Sắp xếp để thu được dãy tăng dần, (dãy giảm dần). Đưa dãy đã sắp xếp ra
màn hình. Cho biết có bao nhiêu lần hoán chuyển 2 phần tử trong dãy khi sắp
xếp
3
d. Nhập 0
e. Sắp xếp thành một dãy tăng dần. Nhập số nguyên x,
chèn x vào tại vị trí thích hợp để dãy vẫn là một dãy
tăng. Đưa dãy đã chèn ra màn hình
f. Kiểm tra dãy có là dãy tăng không? (dãy là các số lẻ,
dãy là cấp số cộng, là dãy fibonacy, là các số nguyên
tố)
1
2
3
4
5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
3. Viết chương trình nhập n, sinh ngẫu nhiên bangr2 chiều nxn số từ 1 đến 100 sau
đó xử lý:
a.
In các số trong mảng ra màn hình như gồm n dòng , n cột
b.
Tính tổng các phần tử đường chéo chính (đường chéo phụ, trên mỗi
dòng)
c.
Đếm xem trong mảng có bao nhiêu số chẵn.
d.
Tìm phần tử lớn nhất và phần tử nhỏ nhất hoán đổi giá trị hai phần tử
này.
2. Nhập n <20, đưa ra ma hình ma trận hình xoắn ốc. ví dụ với n =5 như hình trên
5. Nhập n, đưa ra màn hình tam giác pascal. Với n =5 đưa ra kết quả sau
n= 0
1
n= 1
1
1
n=2
1
2
1
n= 3
1
3
3
1
n=4 1
4
6
4
1
2. Kiểu xâu
2.1 Đặt vấn đề
Để lưu trữ và xử lý họ tên của một người, các kiểu dữ liệu đã học có đáp ứng
được?
Kiểu mảng một chiều gồm 35 kí tự. Khai báo một biến mảng A để lưu trữ họ
tên của một học sinh
Viết chương trình nhập họ tên của 30 học sinh trong lớp. Ta sẽ chọn kiểu dữ liệu
như thế nào? Khai báo biến như thế nào?
Mảng các ký tự để lưu trữ họ tên, sau đó khai báo mảng của mảng để lưu
danh sách họ tên.
Tuy nhiên các NNLT đều có kiểu dữ liệu xâu dùng để lưu trữ 1 dãy các ký tự,
như vậy ta chỉ cần có mảng kiểu xâu.
2.2 Một số khái niệm
4
- Xâu là một dãy kí tự trong bảng mã ASCII.
- Mỗi kí tự gọi là một phần tử của xâu.
- Số lượng kí tự trong xâu được gọi là độ dài của xâu.
- Xâu có độ dài bằng 0 gọi là xâu rỗng.
- Tham chiếu tơí phần tử trong xâu được xác định thông qua chỉ số của phần tử
trong xâu.
- Chỉ số phần tử trong xâu được đánh số là 1.
Ví dụ: Những đối tượng cần khai báo kiểu xâu: Họ tên, tên môn học, địa chỉ,
quê quán.
2.3 Khai báo biến xâu
Var <tên biến> : String [độ dài lớn nhất của xâu ] ;
Ví dụ
Var
Ten:String [7 ] ;
HoDem:String [33] ;
Ten1:String[40] ;
Chú ý:
- Nêu không khai báo độ dài tối đa cho biến xâu kí tự thì độ dài ngầm định của
xâu là 255
- Độ dài lớn nhất của xâu là 255 kí tự
2.4 Các thao tác xử lý xâu
+ Hằng xâu: đặt trong cặp nháy đơn ‘ ‘
+ Xâu rỗng: ‘’
+ Phép gán: :=
+ Tham chiếu tới từng kí tự xâu: <tên biến xâu>[chỉ số]
+ Ghép xâu: + : Ghép nhiều xâu lại thành 1 xâu
VD: ‘Ha’ +’ noi’ cho kết quả ‘Ha noi’
+ Các phép so sánh:<, <=, >, >=, =, <>,
VD:
‘AB’<’AC’
’ABC’>’ABB’
‘ABC’<’ABCD’
2.5 Các hàm xử lý xâu
+ Length(s): độ dài xâu
+ Delete(s, 5, 2): xóa xâu s từ vị trí thứ 5 và xóa 2 ký tự
+ Insert(S1, S2, vt) : chèn S1 vào S2 bắt đầu từ vị trí vt
5
+ Copy(S, vt, N) tạo xâu gồm N kí tự liên tiếp bắt đầu từ vt của xâu S.
+ Pos(S1,S2): trả về vị trí xuất hiện đầu tiên của xâu S1 trong xâu S2
+ UpCase(ch): trả về kí tự là chữ in của ch
Ví dụ: Giả sử S=’TrungTamTinHoc’
Length(s) 14
Delete(s,9,3) S=’TrungTamHoc’
Insert(“Tin”,s,9) S=’TrungTamTinHoc’
S1 = copy(S,9,3) S1= ‘Tin’
n=Pos(‘n’,S) n = 4
2.6 Bài tập
1. Nhập vào một chuỗi họ và tên có thừa các dấu cách, sau đó chuẩn hóa họ tên
nguời này và đưa kết quả truớc khi chuẩn hóa và sau khi chuẩn hóa ra màn hình.
2. Nhập 1 xâu họ tên đầy đủ (theo cách đặt tên nguời việt). Sau đó in ra màn
hình Họ,Họ đệm, Tên của nguời đó.
3. Nhập vào 1 xâu s kiểm tra xâu đã nhập có đối xứng không
4. Đọc một loạt các kí tự từ bàn phím cho đến khi ấn Enter thì ngừng nhập. In ra
số lượng của từng chữ số 0,1,…,9 đã nhập .
Ví dụ : Chuỗi kí tự đọc vào là : 12345079 ABcdA452210.
In ra : Số chữ số 0 là 2
Số chữ số 1 là 2
Số chữ số 2 là 3
Số chữ số 3 là 1
5. Xét một dãy các chữ số A nhận được từ cách ghép liên tiếp các chữ số
nguyên dương liên tiếp tăng dần bắt đầu từ 1,2,3, 4 .. đến số m cho trước (m>30 và
m<=1000). Cho biết một số nguyên dương N hãy tìm vị trí đầu tiên của số N trong
dãy A. Biết rằng vị trí trong dãy A được tính từ 1 nếu không tìm thấy số N trong
dãy A thì trả lời vị trí là 0.
Ví dụ:
m= 31
Dãy A: 12345678910111213141516171819202122232425262728293031
Số N= 89 thì vị trí là 8
N = 212 thì vị trí là 32.
3. Kiểu bản ghi
3.1 Đặt vấn đề
- Cần lưu trữ 1 bảng điểm: Tên, ngày sinh, điểm toán, lý, hóa …
6
Có thể dùng nhiều mảng 1 chiều để lưu trữ, mỗi mảng lưu trữ 1 cột.
khi lấy thông tin người thứ 3 cần phải làm với nhiều mảng Bất tiện
Ngôn ngữ lập trình bậc cao có cách tốt hơn để quản lý dữ liệu trên gọi là Kiểu
bản ghi. Một hàng là 1 biến có kiểu bản ghi, mỗi cột thể hiện thuộc tính của đối
tượng gọi là Trường.
3.2 Một số khái niệm
-
Kiểu bản ghi (Record) là một kiểu dữ liệu có cấu trúc.
Một bản ghi gồm các thành phần (gọi là trường), các trường có thể thuộc các
kiểu dữ liệu khác nhau.
-
Kiểu bản ghi dùng để mô tả nhiều đối tượng có cùng một số thuộc tính.
-
Khi làm việc với bản ghi cần biết;
+ Tên kiểu bản ghi;
+ Tên các trường;
+ Kiểu dữ liệu của mỗi trường;
+ Cách khai báo biến;
+ Cách tham chiếu đến trường.
3.3 Khai báo
Khai báo kiểu:
Type <tên kiểu bản ghi> = record
<tên trường 1>:<kiểu trường 1>;
……………………….
<tên trường n>:<kiểu trường n>;
End;
Khai báo biến:
Var <tên biến>: <tên kiểu bản ghi>;
Ví dụ:
+ Kiểu bản ghi lưu trữ thông tin của HS
Type hocsinh=record
Hoten: string [30];
Ngaysinh:string [10];
GiơiTinh: Boolean;
Tin, Toan, ly,hoa:real;
End;
+ Khai báo biến để lưu trữ dữ liệu cho 3 học sinh
7
Var hs, hs1, hs2: HocSinh;
+ Khai báo biến lưu trữ dữ liệu cho cả lớp
Var Lop: array [1..50] of HocSinh;
3.4 Tham chiếu đến từng trường
Khi làm việc với bản ghi tức là làm viêc với từng thành phần của nó.
Qui tắc tham chiếu đến từng trường
<tên biến bản ghi>. <tên trường>
Hoăc
WITH <Tên biến kiểu bản ghi> DO <Câu lệnh tác động đến tên trường>;
Ví dụ:
+ Biến hs: hs.HoTen, hs.toan
+ Biến Lop chúng ta cần tham chiếu đến phần tử mang Lop[i] sau đó tham chiếu
đến trường: Lop[i].HoTen
3.5 Gán giá trị
Có hai cách để đưa giá trị cho bản ghi.
a) Dùng lệnh gán trực tiếp: A:=B
Yêu cầu A, B cùng kiểu
b) Đưa giá trị cho từng trường tùy thuộc vào kiểu dữ liệu của từng trường.
- Nếu trường có kiểu dữ liệu cơ sở ta có thể gán như sau:
<Tên biến>. <Tên trường>:= <biểu thức>;
Readln(<Tên biến>. <Tên trường>);
Ví dụ: Cho biến HS lưu trữ thông tin như sau:
Hs.Hoten :=’Lan’;
Hs.NgaySinh:=’10-10-1995’
Hs. Toan:=8; Hs.Ly:=9; Hs.Hoa:=7; Hs.Tin:=10
+ Xem tên, điểm TB của 4 môn trong biến hs
Writeln(hs.HoTen, (Hs.Toan+Hs.Ly+Hs.Hoa+Hs.Tin)/4 :6:2);
4. Kiểu file
4.1 Đặt vấn đề
Các biến khi chạy chương trình, các giá trị này không còn có lưu trữ khi kết
thúc chương trình. Muốn lưu trữ DS học sinh lâu dài ta cần lưu trên đĩa (bộ nhớ
ngoài). Vậy cần phải có cách thức để trao đổi dữ liệu với bộ nhớ ngoài.
4.2 Vai trò của kiểu tệp
8
+ Kiểu dữ liệu tệp tin giúp chúng ta trao đổi dữ liệu với bộ nhớ ngoài thông
qua các tệp tin.
+ Tệp được lưu trữ lâu dài ở bộ nhớ ngoài, lượng dữ liệu lưu trữ trên tệp có thể
rất lớn và chỉ phụ thuộc vào dung lượng ổ đĩa.
4.3 Phân loại tệp và thao tác với tệp
Các loại tệp tin đã biết: văn bản, chương trình, hình ảnh, âm thanh
Đọc từ đầu đến cuối tệp văn bản
Đọc từng phần của tệp như âm thanh có thể nghe từ nửa bài tệp cấu trúc
+ Tệp văn bản (text): dữ liệu ghi vào tệp dưới dạng từng kí tự. Đọc và ghi tệp
được thực hiện tuần tự, từ đầu đến cuối tệp.
+ Tệp có cấu trúc: dữ liệu được lưu trữ theo cấu truc nhất định. Đọc và ghi dữ
liệu có thể làm trực tiếp đến từng phần tử.
4.4 Thao tác với tệp văn bản
Với tệp tin cần làm gì? Đọc dữ liệu đưa ra màn hình, ghi dữ liệu được vào
tệp tin.
Các bước thao tác với tệp văn bản:
Bước 1: Khai báo biến tệp
Var <Tên biến tệp> : Text;
Ví dụ: Var Tep1, Tep2: Text;
Bước 2: Gắn tên tệp
Assign(<Tên biến tệp>,<Tên tệp>);
Ví dụ: ASSIGN(Tep1,'DULIEU.DAT');
+ Tên tệp: Là biến xâu hoặc hằng xâu, tên tệp tin đã có trên đĩa gồm <= 8 ký tự,
3 kí tự mở rộng, không có khoảng cách.
Bước 3: Mở tệp
- Mở tệp để ghi dữ liệu: Rewrite(<Tên biến tệp>);
Ví dụ: Rewrite(
Ví dụ: Reset(Tep1);
Lưu ý: Ghi: luôn ghi mới, tên tệp chứa có trên đĩa tự tạo tệp mới, nếu tệp đã có sẽ
ghi đè.
Đọc: đọc tuần tự bắt đầu từ đầu tệp, nếu tệp chưa có trên đĩa sẽ báo lỗi.
Bước 4: Các thao tác đọc và ghi dữ liệu vào tệp
*Đọc dữ liệu từ tệp:
Read(<Tên biến tệp>,<DS biến>);
9
Hoặc Readln(<Tên biến tệp>,<DS biến>);
Lưu ý: DS biến phải cùng kiểu với dữ liệu cần đọc hoặc đọc xâu hay đọc từng
kí tự
Hàm Eof(Biến tệp): có giá trị true khi đã đọc đến cuối tệp.
*Ghi dữ liệu vào tệp:
Write(<Tên biến tệp>,<DS biến>);
Hoặc
Writeln(<Tên biến tệp>,<DS biến>);
Ví dụ:
Write(tep1, ‘A=’,A);
Readln(tep1, s)
Bước 5: Đóng tệp
Close(<Tên biến tệp>);
Ví dụ: Close(Tep1);
Đóng tệp: thao tác này bắt buộc phải có, nếu không có thể dữ liệu ttrong tệp sẽ
bị mất. Khi đã đóng tệp muốn đọc hoặc ghi dữ liệu vào tệp ta cần thực hiện từ B3
(mở tệp)
4.5 Ví dụ
Ví dụ 1: Một file văn bản có tên DaySo.Dat có dạng sau:
- Dòng đầu tiên của số n chỉ số phần tử của dãy số
- Dòng tiếp theo ghi n số, mỗi số cách nhau ít nhất một khoảng trống trên một
dòng.
Viết chương trình đọc dãy số từ file lưu vào trong mảng.
PROGRAM VI_DU1;
USES CRT;
VAR F:TEXT;
A:array[1..100] of INTEGER;
I,j,tg,n: LONGINT;
BEGIN
ASSIGN(F,'so.dat');
RESET(F);
READLN(F,n); {doc dong dau tien vao bien n}
For i :=1 to n do readln(f,a[i]); {doc n dong sau vao cac bien a[i]}
Close(f);
Writeln(‘day so la:’);
For i:=1 to n do write(a[i]:7);
Readln;
END.
10
Ví dụ 2: Một file văn bản ghi số liệu của một bảng số n x m và có dạng sau:
- Dòng đầu tiên của file ghi 2 số n, m cách nhau ít nhất bởi một dấu cách.
- N dòng tiếp theo của file ghi số liệu của n hàng, mỗi hang bao gồm n số cách
nhau ít nhất một dấu cách..
VD: File so.dat có dạng sau :
33
1
0
1
10
11 10
8
9
8
Viết chương trình đọc số liệu của file trên vào một mảng số n x m và in dữ liệu
của mảng trên ra màn hình.
PROGRAM VI_DU2;
USES CRT;
VAR F:TEXT;
A:array[1..20,1..20] of INTEGER;
I,j,m,n: LONGINT;
BEGIN
ASSIGN(F,'BangSo.dat');
RESET(F);
READLN(F,n,m); {doc dong dau tien vao bien n,m}
For i :=1 to n do
For j:=1 to m do read(f,a[i,j]); {doc cac so tren cung mot dong }
Close(f);
For i:=1 to n do
begin
For j:=1 to m do Write(a[I,j]:7);
Writeln;
End;
Readln;
END.
II. MỘT SỐ THUẬT TOÁN
1. Tính thời gian thực hiện chương trình.
Mục đích: Đánh giá độ phức tạp của giải thuật
a. Tính số lần thực hiện:
Uses windows;
Var time: longint;
11
Begin
Time:= gettickcount;
{ đoạn lệnh}
Write(gettickcount – time);
End;
b. Lấy thời gian của máy bằng gettime(h,m,s,x);
Uses Dos;
Var h, m, s,x, h1,m1, s1, x1: word;
Begin
getTime(h,m,s,x);
{ Đoạn lệnh}
getTime(h1,m1,s1,x1);
Write(‘So giay:’,(h1-h)*3600+ (m1-m)*60 +(s1-s));
End;
2. Một số thuật toán về số
1. Nhân nhanh, chống tràn số
Ta có :
x.y = ( x div 2) * 2y + y nếu x lẻ
x.y = ( x div 2) * 2y nếu x chẵn
Function FastMult(x,y: longInt): LongInt;
Begin
Z:=0;
While (x<>0) do
Begin
If x mod 2 =1 then z:= z+y;
X= x div 2;
Y := y*2;
End;
FastMult:=z
End;
2. Lũy thừa, chống tràn số
Ta có:
ax = ( a2)x div 2 * a nếu x lẻ
ax = ( a2)x div 2 * a nếu x chẵn
Function FastExp(a,x: longInt):LongInt;
Begin
Z:=1;
12
While (x<>0) do
Begin
If x mod 2 =1 then z:= z*a;
X= x div 2;
a:= a*a;
End;
FastMult:=z
End;
3. Phép toán Mod chống tràn số (phép nhân, phép lũy thừa)
Function FastModMult(x,y,n: longInt);
Function FastModExp(a,x,n: longInt);
Begin
Begin
Z:=0; x= x:= x mod n; y:=y mod n;
Z:=1;
While (x<>0) do
While (x<>0) do
Begin
Begin
If x mod 2 =1 then
If x mod 2 =1 then z:= z*a mod n;
Begin z:= z+y;
X= x div 2;
If z > n then z:=z-n;
a:= a*a mod n;
End;
End;
X= x div 2;
FastModExp:=z
Y := y*2 mod n;
End;
End;
FastModMult:=z
End;
4. Kiểm tra số nguyên dương n có là số nguyên tố hay không.
Input: n nguyên dương
Output: n có là số nguyên tố?
Thuật toán KTNT
Bước 1: Nếu n <=1 thì n không là số NT chuyểnB6
Bước 2: i =2
Bước 3: Nếu i >
n thì n là số NT CB6
Bước 4: Nếu n chia hết cho i thì n không là số NT CB6
Bước 5: i:=i+1 quay lại B3
Bước 6: Kết thúc
Function KTNT(n:LongInt): Boolean;
Var kiemTra: boolean; i: LongInt;
13
Begin
kiemTra:= true;
IF n <= 1 then kiemTra:=false
Else
For i:=2 to trunc(sqrt(n) do
If n mod i =0 then Begin kiemTra:=false;
Exit End;
KTNT:=kiemTra;
End
Bài tập tương tự:
- Sinh số nguyên tố nhỏ nhất sau số nguyên dương n.
- Liệt kê các số nguyên tố từ 2 đến n.
- Liệt kê các số nguyên tố trong các số a1, a2 … an.
- Đếm các số nguyên tố từ 2 đến n.
5. Phân tích một số nguyên dương n ra thừa số nguyên tố.
Procedure PhanTichTSNT(n:Integer);
Var d: Integer;
Begin
d:=2;
While n>1 do
If n mod d<>0 do d:=d+1
Else
Begin
n:= n div 2
write(d);
End
End
6. Liệt kê các số nguyên hoàn hảo từ 1 đến n.
Procedure SoHoanHao(n: Integer);
Var x,y: Integer;
Begin
For x:= 1 to n do
Begin
S:=1; y:=2;
While (y<= x/2) and (S<=x) do
Begin
14
If x mod y =0 then S:=s+i;
y:= y +1;
End
If S =x then write(x:4)
End
End
7. Tìm số tam tam có 3 chữ số (số tam tam là số mà nó và số đảo nguyên tố cùng
nhau).
Bài toán cần giải quyết các bài toán con:
+ Tìm ước chung lớn nhất của 2 số a, b
+ Tìm số đảo của số x
+ Kiểm tra một số x có là sỗ tam tam không?
+ Liệt kê các số tam tam từ 100 đến 999.
Function UCLN(a,b: Integer);
Function SoDao(x:Integer):Integer
Begin
Begin
While a<>b do
If a> b then a:=a-b
y := 0;
While (x<>0) do
Else b:=b-1;
Begin
UCLN:=a;
y:=y*10 + x mod 10;
End;
x:= x div 10;
End
SoDao=y;
End
Function SoTamTam(x: Integer): Boolean;
Procedure LietKeSoTT
Begin
Begin
If UCLN(x, SoDao(x))=1 then SoTT:=true
For x:= 100 to 999 do
Else SoTamTam:=false;
End
IF SoTamTam(x) Then write(x, ‘ ‘);
End
Bài tập tương tự:
1. Số đẹp là số có tận cùng là 36. Đếm số các số đẹp nguyên dương nhỏ hơn n.
2. Số nguyên tố hoàn hảo là số nguyên tố và số đảo của nó cũng là số nguyên
tố. Đếm số nguyên tố hoàn hảo nhỏ hơn n.
3. Một số bài tập xử lý số lớn
- Số trong pascal: single (7 chữ số); longInt( 9 chữ số); real (11 chữ số); double
(15 chữ số); extended (19 chữ số), khi dùng extended phải bật chế độ {$N+}.
15
- Trong Freepascal int64(19 chữ số)
Nếu số từ 10 chữ số trở lên nên dùng mảng hoặc xâu để lưu trữ.
- Cách lưu trữ bằng mảng
1
2
3
Type SNL = array [1…max] of byte;
Bài tập 1: Cho a, b là số nguyên ( 0 ≤a, b, k≤ 1010) cho biết chữ số thứ k sau phần
thập phân của phép a/b.
Ví dụ:
a/b:
a
b
k
Kết quả
100
8
2
0
99
140
12
2
1
240
5
6
55555 12345
67890
?
666666 13579
24680
?
777777 9999991
999999999 ?
Chương trình:
{$N+}
var a,b,k,t,i : extended;
function chia(var a:extended; b:extended):extended;
var k:extended;
begin
k:=0;
while(a>=b) do begin k:=k+1; a:=a-b; end;
chia:=k;
end;
Begin
a:=100; b:=8; k:=2;
i:=1;
while (i<=k) do
begin
if a=0 then a:=a*10; t:= chia(a,b);
i:=i+1;
end;
write(t:0:0);
readln;
end.
16
Bài tập tương tự: Cho a, b là số nguyên ( 0 ≤a, b, k≤ 1020) . Đưa ra màn hình
kết quả phép toán: a mod b, a div b.
Bài tập 2: Nhập n, sinh một số bằng cách viết liên tiếp các số từ 1 đến n. Tính tổng
các chữ số trong số này. Ví dụ n= 12; X=123456789101112.
Kết quả kiểm tra:
N
S
12
51
123
15868
1379
23538
123456789
4366712385
976543210
44325601330
123123123123
601859517180
Hướng dẫn:
Cách 1: Với n <= 109 , chia bài toán thành 2 bài toán con
+ Tính tổng các chữ số của số n
+ Tính tổng các chữ số được sinh ra
program tinhtong;
var s,i,n: real;
Begin
write('nhap n'); readln( n);
code :integer;
s:=0; i:=1;
t,c:string;
while i<=n do
function Tongcs(t:integer):Integer;
begin
var s:Integer;
s:=s+tongcs(c) ;
begin
i:=i+1;
s:=0;
end;
while t>0 do
writeln(s:0:0);
begin
readln;
s := s + n mod 10;
end.
t:=t div 10;
end;
tongcs:=s;
end;
17
Cách 2: Sử dụng xâu làm được với n <= 107, tuy nhiên tốn thời gian chuyển từ xâu
sang số và chuyển từ số sang xâu.
program tinhtong;
Begin
var s,i,n: real;
write('nhap n'); readln( n);
code :integer;
s:=0; i:=1;
t,c:string;
while i<=n do
function Tongcs(t:integer):real;
begin
var s:real; n,i:byte;
str(i:10:0,c);
begin
s:=s+tongcs(c) ;
s:=0;
i:=i+1;
for i:= 1 to length(t) do
end;
begin
writeln(s:8:0);
Val(t[i],n, code);
s:=s+n;
end;
readln;
end.
tongcs:=s;
end;
Cách 3: Với n khá lớn, thời gian tính nhanh. Chia bài toán thành các bài toán con
+ Tính tổng: a[i] là tổng các chữ số của tất cả các số có i chữ số.
a[1] =45; a[2] = a[1]*10 +10*45; a[3]= a[2]*10 + 102* 45
+ Tính TongTron(k,n): tổng tất cả các chữ số của số bắt đầu bằng k có n chữ số
+ Tính các chữ số được sinh ra đến n= 231
Ví dụ: TinhTong(231) = tongTron(2,3)+ 2* 32 + TinhTong(31)
TinhTong(31)= tongTron(3,2) + 3*3 +TinhTong(1)
{$M 35000,0, 65000}
function Tinhtong:real;
program tinhtongchuso;
var code,x,t:integer; z,tong,y:real;
var s:string;
Begin
i,n:longint; code :integer;
z:=0; y:=0;
tong:real;
while(S<>'') do
a:array[0..20] of real;
begin
procedure luutong;
val(s[1],x, code);
var i:byte; x,y,t:real;
Begin
a[0]:=1;
a[1]:=45; t:=1;
for i:=2 to n do Begin t:=t*10;
tong:=0;
tong:= tongTron(x,length(s))+ y*(z+1)+
tong;
y:=x;
delete(s,1,1); val(s,z,code);
end;
18
a[i]:=t*45+10*a[i-1];
End;
TinhTong:=tong;
End;
End;
Begin
function tongTron(k,n:integer):real;
write(' nhap s=');readln(s);
var i:integer;
n:=length(s);
t:real;
begin
luutong;
t:=1;
writeln(Tinhtong:8:0);
for i:=1 to n-1 do t:=t*10;
readln;
tongTron:=k*(k-1)/2*t+k*a[n-1];
end.
end;
4. Xử lý bít
Nếu mảng chỉ cần có 2 trạng thái (thường dùng ghi nhận thông tin về đối tượng)
nhưng nếu cần mảng số phần tử khá lớn khi đó nên dùng mảng bít, 1 biến cần mảng
600000 phần tử khi xử lý bít chỉ cần mảng 600000/8 phần tử kiểu byte.
Một số cách xư lý:
- Cần biết i ở bít thứ mấy: (i-1) mod 8
- Cần biết i ở byte thứ mấy: i div 8 +1
- Để tăng tốc độ tính toán nên sử dụng phép dịch bít
a mod 2n ⇔ a and (2n-1)
a div 2n ⇔ a shr n
- Nhận giá trị của bit thứ i của x : if (x and (1 shl i) =0 then gt:=0 else gt =1
- Đặt bit i của x giá trị 0 hoặc 1: Đặt 0: x:= x and(not (1 shl i))
Đặt 1: x:= x or (1 shl i);
Ví dụ: Bật bít 17; Tắt bít 2; Nhận bít thứ 3.
{$R-}
type mang= array[1..1]of byte;
var i:word;
a: ^mang;
begin
writeln;
getmem(a,10*sizeof(byte));
for i:=1 to 10 do a^[i]:=0; { khong truy cập được a^[3] mà phải truy câp qua biến i}
i:=17;
a^[ (i -1) div 8+1]:= a^[(i-1) div 8+1] or (1 shl (7- ((i-1) mod 8))); {bat bit}
for i:=1 to 10 do a^[i]:=255;
19
i:=2;
a^[ (i -1) div 8+1]:= a^[(i-1) div 8+1] and not(1 shl (7- ((i-1) mod 8))); {tat bit}
for i:=1 to 10 do
writeln(a^[i]);
i:=3;
write( a^[ (i -1) div 8+1] shr (7- ((i-1) mod 8)) and 1); {nhan bit}
freemem(a,10);
readln;
end.
Bài tập 3: Một tệp văn bản chứa các số từ 1 đến 1000000, hãy loại bỏ các số trùng
nhau và sắp xếp lại tệp tăng dần.
Hướng dẫn:
- Đọc các số lưu vào 1 mảng byte với số phần tử 1000000/8
- Đọc giá trị x đánh dấu mảng tại vị tri bít thứ x bằng 1;
- Ghi mảng vào tệp như sau: Nếu tại bit thứ x bằng 1 thì ghi x.
5. Thuật toán sắp xếp nhanh
procedure Quick_Sort;
procedure Sort(L,R:integer);
var i,j,Tg: integer;
x: Item;
procedure Heap_Sort;
var q,r: integer;
x:Item;
procedure sift(r,e:integer);
Begin
var j:integer;
x= a[(L+R) div 2].key ; i=L; j=R;
Begin
repeat
x=a[r] ;con t=true;
while a[i] < x do i=i+1;
while x
while (r *2<=e) and cont do
< a[j] do j=j-1;
Begin
if i <=j then
j=r*2;
Begin
if (j
Doi_Cho(a[i],a[j]);
if a[j] < a[j+1] then j=j+1;
i=i+1; j=j-1;
if x >= a[j] then cont=false
End;
else
until i>j;
Begin a[r]=a[j]; r=j;
if l < j then sort(l,j);
End;
if i < r then sort(i,r);
a[r]=x;
End;
Begin
End;
End;
Begin
Sort(1,,n);
End;
cont:boolean;
for r=(n div 2) downto 1 do sift(r,n);
for r=n downto 2 do
Begin Doi_cho(a[1],a[r]); sift(1,r-1);
20
End
End;
III. TÌM KIẾM LỜI GIẢI
1. Mô hình hóa bài toán
Trạng thái
↔
T: Tập các trạng thái của bài toán
↔ Các đỉnh đồ thị
Đỉnh
F: Tập các toán tử chuyển trạng thái ↔ Cạnh, cung của đồ thị
S: Trạng thái ban đầu
↔ Đỉnh xuất phát
G: Trạng thái kết thúc
↔ Đỉnh kết thúc
2. Mô tả dữ liệu cho bài toán
Cần lưu trữ T hiệu quả, S,G là tập con của T.
F: Thường viết thành 1 hàm xây dựng trạng thái mới từ trạng thái cũ. Cần
lựa chọn một dạng mô tả nào đó của các trạng thái
T: Thường được sử dụng kiểu tập hợp.
Thông thường các giải thuật tìm kiếm đều yêu cầu đánh dấu các trạng thái đã đi
qua để tránh lặp lại do vậy việc đánh dấu nên dùng BitSet khi không gian trạng thái
nhỏ, khi không gian trạng thái quá lớn nên dùng cây tìm kiểm nhị phân để tìm kiếm
cho nhanh. Nếu cần lưu trữ để lấy kết quả thì dùng mảng Truoc[u] = v để lưu trữ
trạng thái trước trạng thái u.
Ví dụ:
1. Bảng số: Một bảng số có n dòng m cột mỗi ô lưu một số nguyên dương. Tìm
cách đi từ ô (x,y) đến ô (x1, y1) theo một cách thức cho trước.
+ Mô hình hóa bài toán
Không gian trạng thái lưu trữ bằng mảng 2 chiều.
Trạng thái các ô: (x,y)
T = { (x,y) / 1<=x,y<=n}
F={ cách thức đi từ ô (x,y) đến các ô khác}
S={(1,1)}
G= {(n,n)}
+ Mô tả dữ liệu
Trạng thái của ô:
Type Dinh = record
x,y: longint;
End;
21
Cần mảng lưu trọng số c[u] = c[u.x,u.y] = giá trị tại ô (x,y)
Mảng đánh dấu ô đã đi qua sử dụng bitset:
b[u] = b[u.x,u.y] =0 hoặc 1
Mảng lưu đường đi: truoc[u]=truoc[u.x,u.y] = v
2. Trò chơi ô chữ: không gian trạng thái rất lớn 9! do vậy nên dùng Cây tìm kiếm
nhị phân
+ Mô hình hóa bài toán
Trạng thái : bảng
T = { bảng)/ 0<=ai<=8}
F= {cách thức đi từ ô (x,y) trống đến các ô bên cạnh}
Type Dinh = record
a:array[1..3,1..3] of 0..8;
x,y:1..3;
so: longint;
End;
3. Giải quyết bài toán bằng phương pháp vét cạn
Các dạng bài tập:
+ Tìm 1 kết quả
+ Có bao nhiêu kết quả
+ Tìm kết quả tốt nhất
Phương pháp vét cạn áp dụng cho tất cả các bài toán và luôn tìm ra lời giải, tuy
nhiên bị hạn chế về thời gian. Vét cạn thường dùng với các bài toán đưa ra tất cả
các kết quả, hoặc tìm kết quả tốt nhất.
Dùng đệ qui, quay lui + nhánh cận tìm lời giải. Khi đó lời gọi đệ qui phụ thuộc
rất nhiều vào bộ nhớ stack mặc định của máy tính. Khởi tạo kích thước của Stack
bằng câu lệnh {$M 65520, 0, 655360}. Mỗi lần gọi đệ qui chương trình sẽ lưu tất cả
các biến cục bộ, giá trị của hàm. Số lần gọi tính tương đối không quá 65520/
(size(biến)+8). Do đó với những bài toán có cấu hình tìm kiếm lớn không phù hợp
với đệ qui khi đó cần phải khử đệ qui.
Thuật toán đệ qui quay lui
L(u)= { v/For j:=1 to nu do
ChuyenTT(j,u,v);} lân cận của đỉnh u
22
Procedure Try(u)
Procedure Try(k) {thực hiện lần thứ k}
Var v
Var v, x
Begin
Begin
For v ∈L(u)
For v ∈ L(u)
Begin
Begin
If < chấp nhận v> then
If < chấp nhận v> then
Begin
Begin
<Ghi nhận v>
ghinhan[k]:=v;
<Đánh dấu v đã chấp nhận>
<Đánh dấu v đã chấp nhận>
Truoc[v]:=u;
x:=u;
If v là đích then InKQ(v)
u:=v;
Else Try(v)
If k=n then InKQ(u)
<Trả lại trạng thái v>
Else Try(k+1)
End;
<Trả lại trạng thái u>
End
u:=x
End
End;
End;
End;
+ Giảm thời gian tính toán bằng cách giảm lời gọi đệ qui hoặc giảm các bước
tính trung gian:
- Dùng nhánh cận để hạn chế tối đa lời gọi đệ qui.
- Hạn chế biến cục bộ và chỉ dùng số thực khi thật sự cần thiết.
Ví dụ 1: Đệ qui tính n giai thừa.
{$N+}
{$M 65520, 0, 655360}
uses dos;
function gtdq(n:integer):longint;
var a,b,c:integer;
begin
if n=1 then gtdq:=1
else begin a:=1; a:=b; gtdq:=gtdq(n-1)*1; end;
end;
begin
writeln(gtdq(4000));
end.
23
Ví dụ 2: Đệ qui và quay lui
Bài toán xếp hậu: Một bàn cò 8x8 ô. Đưa ra số cách xếp quân hậu vào bàn
cờ sao cho không có 2 quân hậu nào ăn được nhau.
program Eight_Queen;
var a: array[1..8] of boolean ;
b: array[-7.. 7] of boolean;
c: array[2..16] of boolean;
x: array[1..8] of integer;
d:integer;
procedure Init;
var i:integer;
Begin
for i= 1 to 8 do a[i]=true;
for i= -7 to 7 do b[i]=true;
for i= 2 to 16 do c[i]=true;
d=0;
End;
procedure Print;
var i: integer;
Begin
writeln;
for i= 1 to 8 do write(x[i]:3);
d=d+1;
readln;
End;
procedure try(i:integer);
var j: integer;
Begin
for j=1 to 8 do
if a[j] and b[i-j] and c[i+j] then
Begin
x[i]=j;
a[j]=false; b[i-j]=false; c[i+j]=false;
if (i=8) then print
else try(i+1);
a[j]=true; b[i-j]=true; c[i+j]=true;
End;
24
End;
Begin
Init;
Try(1);
writeln('so lan', d:4);
readln;
End.
Bài tập 3: Cân vật
Có n quả cân có trọng lượng 1, 2, … n và một vật có trọng lượng m (n,m
<100). Tính số cách để đặt quả cân lên 2 bên bàn cân để cân vật m.
Dữ liệu kiểm tra với các quả cân là 1, 2, … n
N
m
Số cách cần
4
2
7
10
22
602
Hướng dẫn:
Một cách cân vật thì với quả cân thứ k có 3 trạng thái
j=0: quả cân không tham gia vào cân.
j= -1: quả cân nằm bên đĩa cân có vật m
j=1: quả cân nằm bên đĩa cân không có vật m.
Biến y để tính trọng lượng khi chọn quả cân thứ i. Khi đó y:=y+k*j
Nếu y = m thì tính một lần cân, dùng biến d dùng để đếm số lần cân.
Quá trình thực hiện từ quả cân 1 đến quả cân n,
program Can_Vat;
var n,m,y,d: integer ;
b: array[1.. 100] of byte;
procedure Init;
var i:integer;
Begin
Write(‘ Nhap n, m); readln(n,m);
for i= 1 to n do b[i]=0;
d=0;
End;
procedure try(k:integer);
var j: integer;
Begin
for j=-1 to 1 do
25
