Giáo trình Tin Đại cương - Trường Đại học Điện lực

đệ qui:
 U(0)=1, U(1)=1, U(k)=U(k-1) + U(k-2) với k>1.
 Ta viết:
 U(k) = 1 nếu k=0 hoặc k=1
 = U(k-1) + U(k-2) nếu k>1.
Công thức truy hồi trên là cơ sở để xây dựng hàm đệ qui tính U(k): để tính được một số hạng ta phải tính được hai số hạng đứng trước nó.
Chương trình sau in ra số Fibonaci thứ N bằng cách gọi hàm đệ qui Fibo.
PROGRAM VIDU_8_10; { Tính số Fibonaci thứ N }
Var N : Integer;
Function Fibo( k : Integer) : Integer; 
{ Hàm tính số Fibonaci thứ k bằng đệ qui}
Begin
 If k=0 then Fibo:= 1
 else
 if k=1 then Fibo:=1
 else
 Fibo:=Fibo(k-1) + Fibo( k-2);
End;
BEGIN
 Write(‘ Nhập N: ‘); Readln(N);
 Writeln( ‘ Số Fibo thứ ‘, N, ‘ = ‘, Fibo(N) ); 
 Readln;
END.
Ghi chú: Việc sử dụng đệ qui đòi hỏi nhiều về bộ nhớ. Do đó tránh dùng đệ qui nếu có thể được.
Ví dụ 8.11: 
Tam giác Pascal là một bảng các số có n+1 hàng (từ hàng 0 đến hàng n), mỗi một số hạng trong hàng i là tổ hợp chập k của i (với định nghĩa tổ hợp chập k của n là 
 = n!/(k!*(n-k)!). Bằng cách tạo tính tổ hợp (trong đó có sử dụng hàm tính giai thừa). Hãy in ra màn hình tam giác Pascal theo dạng:
 1 
 1 1 
 1 2 1 
 1 3 3 1 
 1 4 6 4 1 
 1 5 10 10 5 1 
 1 6 15 20 15 6 1 
..................................
Program Tam_giac_Pascal;
VAR n, i, k: Integer;
Function Giai_thua(n: integer): longint;
VAR gt : LongInt;
BEGIN
 gt := 1;
 FOR i :=1 TO n DO 
 gt := gt*i;
 Giai_thua := gt;
END;
Function To_hop(n,k: integer):LongInt; 
BEGIN { Than chuong trinh con To_hop }
 To_hop := Giai_thua(n) div ( Giai_thua(k)*Giai_thua(n-k) );
END;
BEGIN { Chuong trinh chinh }
 WRITE('Nhap n: '); READLN(n);
 FOR i:=0 TO n DO 
 BEGIN
 FOR k:= 0 TO i DO 
 WRITE(To_hop(i,k):5);{In 1 hang cua tam giac Pascal}
 WRITELN; { xuong dong }
 END; 
 READLN;
END.
Ví dụ 8.12: Bài toán Tháp Hà Nội: Có một cái tháp bao gồm n tầng, tầng trên nhỏ hơn tầng dưới. Hãy tìm cách chuyển cái tháp này từ vị trí A sang vị trí B nhờ vị trí trung gian C. Yêu cầu mỗi lần chỉ được chuyển một tầng và không được để tầng lớn trên tầng nhỏ.
Program Thap_Ha_Noi;
USES Crt;
VAR n : Integer;
Procedure Chuyen(n:Integer; VT1, VT2, VT3:Char);
BEGIN
 IF n = 1 THEN WRITELN('Chuyen tu ', VT1, ' sang ', VT2)
 ELSE 
 BEGIN
 	Chuyen(n-1, VT1, VT3, VT2);
 	Chuyen(1, VT1, VT2, VT3);
 	Chuyen(n-1, VT3, VT2, VT1);
 	 END;
END;
BEGIN
 ClrScr;
 WRITE('Thap co bao nhieu tang? '); READLN(n);
 WRITELN('Qua trinh dich chuyen nhu sau: ');
 Chuyen(n, 'A', 'B', 'C');
 READLN;
END.
BÀI TẬP CHƯƠNG 8
Bài 8.1: Phân biệt biến địa phương và biến toàn cục? Có thể đặt tên biến địa phương và biến toàn cục cùng tên không? Điều gì sẽ xảy ra? Giải thích?
Bài 8.2: Tên các tham số hình thức có thể trùng tên với biến toàn cục hay biến địa phương của chường trình con đó hay không? Điều gì sẽ xảy ra? Giải thích vì sao?
Bài 8.3: Có bao nhiêu phương thức truyền tham số cho chương trình con? Hãy phân biệt chúng? Lấy một ví dụ ?
Bào 8.4: Cho các khai báo sau:	
	Const max = 1000;
	Var x,y,z: real;
	 m,n: integer;
	Procedure CTC_1(var x, y: real; z: integer);
	Function CTC_2(i,n: integer):real;
Trong các lời gọi sau, lời gọi nào sai? Vì sao? Nếu có thể hãy sửa lại cho đúng.
CTC_1(x,y,m);
CTC_1(x,y,z);
CTC_1(x-y,x+y,5);
CTC_1(x,y,max);
CTC_1(2.5,y,3);
CTC_1(x,y,5,10);
CTC_1(x,y,m+2)
Writeln(CTC_1(x,y,m));
m = CTC_1(x,y,5);
m = CTC_2(m,n);
x = CTC_2(m,5);
CTC_2(m,3);
x = y + CTC_2(x,m);
writeln(CTC_2(m,n));
Bài 8.5: Viết chương trình tạo một bảng chọn đơn giản gồm các mục sau:
1. Giải phương trình bậc nhất
2. Giải phương trình bậc hai
3. Giải hệ phương trình bậc nhất
0. Kết thúc chương trình.
Gõ các sô 0, 1, 2, 3 để lựa chọn công việc tương ứng. Mỗi công việc sẽ được xây dựng bằng chương trình con và chỉ cần gọi ra trong chương trình chính.
Bài 8.6: Viết chương trình nhập vào một số n. In lên màn hình các số nguyên tố nhỏ hơn n.
Bài 8.7: Viết thủ tục nhập vào và in ra màn hình theo hàng dãy số thực có n phần tử. In lên màn hình các số chính phương có mặt trong dãy số.
Bài 8.8:Viết một thủ tục nhập hai ma trận vuông A, B cấp N có các phần tử là các số nguyên.
 Viết một thủ tục tính ma trận C= A+2B
 Viết một thủ tục in các ma trận A, B và C lên màn hình
 Viết một hàm kiểm tra A, B, C có phải là ma trận đối xứng khôngBài 8.9: Viết một hàm kiểm tra hàng thứ k của một ma trận A cấp MxN có lập thành một dãy tăng không?. 
Nhập ma trận A và cho biết những hàng nào của A lập thành một dãy tăng ?
Bài 8.10: Viết chương trình giải phương trình bậc hai ax2 + bx + c = 0 yêu cầu tạo hai chương trình con một chương trình con giải phương trình bậc nhất trong trường hợp hệ số a = 0 và một chương trình con giải phương trình bậc hai thực sự trong trường hợp hệ số a khác 0. 
Bài 8.11: Viết một hàm để chuẩn hóa một chuỗi: xóa bỏ mọi ký tự trắng thừa ở đầu và cuối chuỗi, và giữa hai từ chỉ giữ lại đúng một ký tự trắng. 
Bài 8.12: Viết một hàm để đổi một ký tự từ chữ hoa ra chữ thường. Dùng hàm đó đổi tất cả các ký tự của một chuỗi St nhập từ bàn phím ra chữ thường hết.
Bài 8.13: Nhập vào một chuỗi số nhị phân, đổi ra số hệ thập phân tương ứng. 
Ví dụ : nhập chuỗi ‘1111’ , đổi ra số 15. 
Bài 8.14: Viết chương trình sử dụng chương trình con tính các tổng sau với n là số nguyên dương, x là số thực bất kỳ nhập từ bàn phím khi thực hiện chương trình: 
a) S = 1 + x + x2 + x3 + ... + xn 
b) S = 1 + x + x2 + x3+ ... + (-1)nxn 
c) S = 1 + x/1! + x2/2! + x3/3! + ...+ xn/n! 
Bài 8.15: Viết một hàm đệ qui tính S= xn (x thực, n nguyên dương).
Bài 8.16:Viết một hàm đệ qui tính Sn: 
PHỤ LỤC
Bảng 1: Bảng mã ASCII với 128 ký tự đầu tiên
Hex 
0 
1 
2 
3 
4 
5 
6 
7 
0 
NUL 
0 
DLE 
16 
SP 
32 
0 
48 
@ 
64 
P 
80 
` 
96 
p 
112 
1 
SOH 
1 
DC1 
17 
! 
33 
1 
49 
A 
65 
Q 
81 
a 
97 
q 
113 
2 
STX 
2 
DC2 
18 
“ 
34 
2 
50 
B 
66 
R 
82 
b 
98 
r 
114 
3 
© 
3 
DC3 
19 
# 
35 
3 
51 
C 
67 
S 
83 
c 
99 
s 
115 
4 
¨ 
4 
DC4 
20 
$ 
36 
4 
52 
D 
68 
T 
84 
d 
100 
t 
116 
5 
§ 
5 
NAK 
21 
% 
37 
5 
53 
E 
69 
U 
85 
e 
101 
u 
117 
6 
ª 
6 
SYN 
22 
& 
38 
6 
54 
F 
70 
V 
86 
f 
102 
v 
118 
7 
BEL 
7 
ETB 
23 
‘ 
39 
7 
55 
G 
71 
W 
87 
g 
103 
w 
119 
8 
BS 
8 
CAN 
24 
( 
40 
8 
56 
H 
72 
X 
88 
h 
104 
x 
120 
9 
HT 
9 
EM 
25 
) 
41 
9 
57 
I 
73 
Y 
89 
I 
105 
y 
121 
A 
LF 
10 
SUB 
26 
* 
42 
: 
58 
J 
74 
Z 
90 
j 
106 
z 
122 
B 
VT 
11 
ESC 
27 
+ 
43 
; 
59 
K 
75 
[ 
91 
k 
107 
{ 
123 
C 
FF 
12 
FS 
28 
, 
44 
< 
60 
L 
76 
\ 
92 
l 
108 
| 
124 
D 
CR 
13 
GS 
29 
- 
45 
= 
61 
M 
77 
] 
93 
m 
109 
} 
125 
E 
SO 
14 
RS 
30 
. 
46 
> 
62 
N 
78 
^ 
94 
n 
110 
~ 
126 
F 
SI 
15 
US 
31 
/ 
47 
? 
63 
O 
79 
_ 
95 
o 
111 
DEL 
127 
Bảng 2: Bảng mã ASCII với ký tự số 128 - số 255
Hex 
8 
9 
A 
B 
C 
D 
E 
F 
0 
Ç 
128 
É 
144 
á 
160 
░ 
176 
└ 
192 
╨ 
208 
α 
224 
≡ 
240 
1 
ü 
129 
æ 
145 
í 
161 
▒ 
177 
┴ 
193 
╤ 
209 
ß 
225 
± 
241 
2 
é 
130 
Æ 
146 
ó 
162 
▓ 
178 
┬ 
194 
╥ 
210 
Γ 
226 
≥ 
242 
3 
â 
131 
ô 
147 
ú 
163 
│ 
179 
├ 
195 
╙ 
211 
π 
227 
≤ 
243 
4 
ä 
132 
ö 
148 
ñ 
164 
┤ 
180 
─ 
196 
╘ 
212 
Σ 
228 
⌠ 
244 
5 
à 
133 
ò 
149 
Ñ 
165 
╡ 
181 
┼ 
197 
╒ 
213 
σ 
229 
⌡ 
245 
6 
å 
134 
û 
150 
ª 
166 
╢ 
182 
╞ 
198 
╓ 
214 
µ 
230 
÷ 
246 
7 
ç 
135 
ù 
151 
º 
167 
╖ 
183 
╟ 
199 
╫ 
215 
τ 
231 
≈ 
247 
8 
ê 
136 
ÿ 
152 
¿ 
168 
╕ 
184 
╚ 
200 
╪ 
216 
Φ 
232 
° 
248 
9 
ë 
137 
Ö 
153 
⌐ 
169 
╣ 
185 
╔ 
201 
┘ 
217 
Θ 
233 
∙ 
249 
A 
è 
138 
Ü 
154 
¬ 
170 
║ 
186 
╩ 
202 
┌ 
218 
Ω 
234 
· 
250 
B 
ï 
139 
¢ 
155 
½ 
171 
╗ 
187 
╦ 
203 
█ 
219 
δ 
235 
√ 
251 
C 
î 
140 
£ 
156 
¼ 
172 
╝ 
188 
╠ 
204 
▄ 
220 
∞ 
236 
ⁿ 
252 
D 
ì 
141 
¥ 
157 
¡ 
173 
╜ 
189 
═ 
205 
▌ 
221 
φ 
237 
² 
253 
E 
Ä 
142 
₧ 
158 
« 
174 
╛ 
190 
╬ 
206 
▐ 
222 
ε 
238 
■ 
254 
F 
Å 
143 
ƒ 
159 
» 
175 
┐ 
191 
╧ 
207 
▀ 
223 
∩ 
239 
255 
TÀI LIỆU THAM KHẢO
[1] Turbo Pascal 5 & 6 - Giáo trình cơ sở và nâng cao kỹ thuật lập trình hướng đối tượng.
Phạm Văn Ất - NXB Giáo dục, Hà Nội - 1993.
[2] Giáo trình Tin học cơ sở
Đào Kiến Quốc, Bùi Thế Duy - NXB ĐH Quốc Gia Hà Nội - 2005.
[3] Theory and Problems of Programming with Pascal, 
Byron S. GottFried, 2/ed, Schaum's Outline Series, McGraw-Hill Int. Ed., New York, USA - 1994.
[4] Lập trình căn bản ngôn ngữ Pascal
Ðoàn Nguyên Hải, Nguyễn Trung Trực, Ng. Anh Dũng - NXB Khoa Tin học, Ðại học Bách khoa TP. HCM - 1993.
[5] Giáo trình Tin học căn bản
	Quách Tuấn Ngọc - NXB. Giáo dục, Hà Nội - 1995.  
[6] Ngôn ngữ lập trình Pascal 
	Quách Tuấn Ngọc - NXB. Giáo dục, Hà Nội - 1995.
[7] Lập trình bằng ngôn ngữ Pascal
	Nguyễn Đình Hóa - NXB Đại học Quốc gia Hà Nội - 2005
[8] Cấu trúc dữ liệu và giải thuật
	Nguyễn Đình Hóa - NXB Đại học Quốc gia Hà Nội - 2005
 [9] Bài tập Tin học I
Hồ Sĩ Ðàm, Nguyễn Tô Thành, Dương Việt Thắng, Nguyễn Thanh Tùng - NXB Giáo dục, Hà Nội - 1995.
[10] Lập trình Pascal nâng cao
	Nguyễn Tô Thành - NXB ĐH Quốc Gia Hà Nội - 2001.
[11] Giáo trình lý thuyết và bài tập Pascal, tập 1, tập 2
	Hoàng Đức Hải, Nguyễn Đình Tê - NXB Giáo dục - 1999.
[12] Lập trình bằng Pascal với các cấu trúc dữ liệu
	Larry Nyhoff, Sanford Leedstma, (người dịch: Lê Minh Trung) - NXB Đà Nẵng - 1998.
[13] Bài giảng Mạng và truyền thông dữ liệu 
 Nguyễn Đình Việt - Đại học Công nghệ, ĐH Quốc gia Hà Nội.
[14] Mạng may tính và các hệ thống mở
 Nguyễn Thúc Hải - NXB Giáo dục – 1999 
[15] Giáo trình Hệ thống mạng máy tính CCAN (Semester 1)
 Nguyễn Hồng Sơn (chủ biên), Hoàng Đức Hải - NXB Lao động - Xã hội - 2003.