Tin học - Bài: Tiết kiệm bộ nhớ stack trong khai báo biến

 UBND HUYỆN SÓC SƠN
TRƯỜNG THCS TIÊN DƯỢC
CHUYÊN ĐỀ BỒI DƯỠNG HỌC SINH GIỎI
MÔN TIN HỌC – PHẦN LẬP TRÌNH
Bài: TIẾT KIỆM BỘ NHỚ STACK TRONG KHAI BÁO BIẾN
I – Yêu cầu:
Kiến thức:
Biết được kích thước dung lượng của một số kiểu dữ liệu thường dùng;
Biết lợi ích của việc tiết kiệm khai báo biến.
Kỹ năng:
Rè kỹ năng sử dụng ngôn ngữ lập trình Pascal.
Thực hiện được việc khai náo đúng và đủ biến mà không thừa biến, không thừa rộng quá của kiểu dữ liệu.
Phát triển tư duy tốt hơn.
Thái độ: Nghiêm túc, xây dựng, tìm tòi, khám phá, phát huy sáng tạo
II – Nội dung
Hoạt động 1: Giới thiệu về kích thước một số kiểu dự liệu thường dùng
Hoạt động của thầy
Nội dung
Trong Pascal có một số kiểu dữ liệ thường dùng như Integer, Real, Longint, String,  Trong quá trình viết chương trình ta không để ý đến kích thước của các kiểu dữ liệu này bời vì chưa phải là các bài toán lớn, bài toán cần nhiều biến. Ta cũng cần phải biết, mặc định trong Pascal thì bộ nhớ Stack chỉ cấp cho 16384 byte. Đã bao giờ em gặp lỗi thông báo “structure too large” chưa? Đây là thông báo “cấu trúc qua lớn” do khai báo biến có tổng kích thước bộ nhớ vượt quá cho phép của bộ nhớ Stack. Làm thế nào để biết được khi nào ta khai báo vượt quá cho phép? 
Riêng kiểu dữ liêu String là 256 byte, nếu String[100] thì là 101 byte. Vậy kích thước khai báo string là báo n thì tốn hết n+1 byte.
Mỗi biến hay thành phần của biến nào đều dùng đến số lượng byte tương ứng.
Nếu khai báo:
Var n,m: integer; thì đã dùng hết 8byte.
Var a:array[1..100] of real; thì đã dùng hết 100x6 = 600 byte.
Khi lập trình chúng ta cần phải tiết kiệm bộ nhớ trong khai báo biến, đặc biệt cần thiết khi giải một bài toán lớn có cần sử dụng nhiều biến. Vậy làm thế nào ta tìm hiểu thêm qua bài toán cụ thể
1. Kích thước bộ nhớ của kiểu dữ liệu
STT
Tên kiểu
Phạm vi giá trị
Kích thước
(byte)
1
Integer
-32768..32767
2
2
Byte
0 .. 255
1
3
Word
0 .. 65535
2
4
Longint
-2147483648..2147483647
4
5
Sortint
-128 .. 127
1
6
Real
2.9e-39..1.7e38
6
7
Single
1.5e-45..3.4e38
4
8
Double
5.0e-324..1.7e308
8
9
Char
Kí tự bất kì
1
10
Boolean
True, False
1
11
String
Xâu tối đa 255 kí tự
1  256
- Ví dụ:
Var a,b,c : Integer; 
Dùng hết 3x2 = 6 byte.
Var a,b : Array[1..100] of longint;
Dùng hết 2x100x6 = 1200 byte.
Var tb : string;
 ten: Array[1..50] of String[30];
dùng hết 256 + 50x31 = 1806 byte.
Hoạt động 2: Áp dụng
Hoạt động của thầy
Nội dung
Bây giờ chúng ta tìm hiểu qua một bài toán cụ thể xem nên tiết kiệm bộ nhớ như thế nào khi khái bái biến để viết chương trình giải một bài toán
- Khi viết chương trình xong để kiểm tra nghiệm và chỉnh sửa lại chương trình thi ta hay dùng bộ nghiệm có giá trị nhỏ để còn dễ nhẩm. Thế nhưng cần chú ý đến điều kiện là K có thể khá lớn, có thể phải thông báo giá trị của F1000.
- Theo công thức đệ quy của dãy Fibo thì dễ nhận thấy K càng lớn thì Fk cũng càng lớn. Chắc chắn kiểu Integer không đủ để biểu diễn số lớn như vậy. Có thể kiểu Longint cũng vẫn là chưa đủ. Vậy cần phải sử dụng kiểu Int64 trong Free Pascal. Như thế thì M có thể cũng là số nguyên rất lớn nên M cũng phải có kiểu Int64.
 Vậy chương trình được viết như thế nào?
- Rõ ràng chương trình trên chỉ đúng với giá trị của M ≤ Fk. Nếu giá trị của M > Fk+1 thì sẽ không đưa ra thông báo kết quả. Vậy chương trình trên được hiệu chỉnh thế nào?
- Như vậy chương trình trên hoàn toàn có thể thực hiện được và đúng. Tuy nhiên ở đây ta lại thấy việc khai báo biến F là một mảng có nhiều nhất là 1000 phần tử (hầu như không có chương trình nào klhai báo mảng rộng đến như vậy), nhưng Fmax≤ M lại là F1000 + 1 trở lên thì sẽ không có giá trị F nào như thế. Và lại việc khai báo như vậy sẽ tốn rất nhiều bôn nhớ.
- Để ý sẽ thấy ta chỉ cần lấy giá trị Fk còn các giá trị nhỏ hơn thì không cần. Tuy nhiên ta lại cần có các giá trị Fi< Fk để còn tìm được Fk. Khi tìm được Fk thì cần thêm Fk-1 để tính tiếp đến giá trị Fk+1 nên Fk-2 sẽ không còn cần dùng đến nữa. Như vậy, mỗi lần tìm ra một số Fibo ta chỉ cần biẻt giá trị của hai số trước đó. Tóm lại mỗi một lần tìm ta chỉ cần có ba biến để lưu giá trị của các số Fibo cần thiết.
Chương trình sẽ được viết thế nào?
- Bây giờ ta kiểm tra hai chương trình đèu đúng này xem nên sử dụng chương trình nào hợp lý hơn? Ở đây ta chỉ xét đến mỗi chương trình tiêu tốn hết bao nhiêu bộ nhơ khi khai báo biến? Ở cả hai chương trình khác nhau ở phần khai báo biến mảng (CT trước) và không có biến mảng (CT sau).
Như thế ta thấy sự chênh lệch rất nhiều trong hai chương trình.
* Đây chỉ là một bài toán nhỏ, sử dụng rất ít biến và kiểu dữ liệu của biến cũng không phải là lớn lắm. Nếu khi gặp bài toán lớn thì việc khai báo lãng phí ngư CT đầu thì liệu điều gì sẽ xảy ra?
* Nếu khai bào i, K: Integer ta cũng khai báo kiểu dữ liệu rộng ra là Longint thì có nên không?
Chúng ta phải biết tiết kiệm bộ nhơ vì bộ nhớ có hạn, nhưng việc phải sử dụng đến kiểu dữ liệu lại là bắt buộc.
2. Vận dụng
Bài toán: Dãy số Fibonaci cho bởi công thức F1 = F2 = 1, Fn = Fn-1 + Fn-2 (n≥3).
Hãy tìm số Fibonaci thứ K (1≤K≤1000)
Hãy tìm số Fibonaci lớn nhất nhưng không vượt quá số M (1<M<109) cho trước.
* Yêu cầu nhập vào số nguyên K và M rồi thông báo kết quả.
Program Fibonaci;
Var i,K:integer;
 F:Array[1..1000] of longint;
 M:longint;
Begin
 Write(' Nhap K = '); Readln(K);
 Write(' Nhap M = '); Readln(M);
 F[1] := 1; F[2] := 1;
 For i := 3 to K do 
F[i] := F[i-1] + F[i-2];
 Writeln(' F',K,' = ',F[K]);
 For i := 2 to K do
 If F[i] > M then 
Writeln(F[i-1]);
 Readln;
End.
Program Fibonaci;
Var i,K:integer;
 F:Array[1..1000] of longint;
 M:longint;
Begin
 Write(' Nhap K = '); Readln(K);
 Write(' Nhap M = '); Readln(M);
 F[1] := 1; F[2] := 1;
 For i := 3 to K do 
F[i] := F[i-1] + F[i-2];
 Writeln(' F',K,' = ',F[K]);
 i := 2;
 While F[i]<=M do
 Begin
 i := i + 1;
 F[i] := F[i-1] + F[i-2];
 End;
 Writeln(F[i-1]);
 Readln;
End.
Program Fibonaci;
Var i,K:integer;
 F,a,b: longint;
 M:longint;
Begin
 Write(' Nhap K = '); Readln(K);
 Write(' Nhap M = '); Readln(M);
 a := 1; b := 1;
 For i := 3 to K do
 Begin
 F := a + b;
 a := b;
 b := F;
 End;
 Writeln(' F',K,' = ',F);
 a := 1; b := 1; F := 1;
 While F<=M do
 Begin
 F := a + b;
 a := b;
 b := F;
 End;
 Writeln(a);
 Readln;
End.
- Khai báo F:Array[1..1000] of longint; đã dùng hết 1x1000x4 = 4000 byte
- Khai báo F,a,b: longint; đã dùng hết 3x4 = 12 byte.
III – Giao nhiệm vụ
Tìm hiểu thêm kích thước của một số kiểu dữ liệu khác;
Khi định nghĩa kiểu dữ liệu mới là đoạn con thì kích thước của nó so với kiểu cơ sở như thế nào?