SKKN Sử dụng kiểu dữ liệu xâu để xử lí các bài toán cần xử lí dữ liệu số lớn

SÁNG KIẾN KINH NGHIỆM
SỬ DỤNG KIỂU DỮ LIỆU XÂU ĐỂ XỬ LÍ CÁC BÀI TOÁN CẦN XỬ LÍ DỮ LIỆU SỐ LỚN
I. ĐẶT VẤN ĐỀ.
1. Lý do chọn sáng kiến kinh nghiệm: Khi gặp các bài toán có yêu cầu về xử lý số nguyên có giá trị khá lớn trong Pascal ta thường gặp phải một số lỗi: lỗi tràn ngăn xếp stack overflow error; lỗi vượt phạm vi khai báo Range check error; lỗi tràn vùng nhớ Heap Heap overflow error và khi đó chương trình không thực hiện được. 
Hằng năm, trong kỳ thi học sinh giỏi tỉnh vẫn thường gặp những bài toán cần xử lý dữ liệu số lớn với số lượng test khá lớn đòi hỏi thí sinh phải tìm cách để xử lí( Nếu không sử dụng Free Pascal).
Vấn đề đặt ra là phải tìm một số phương pháp xử lí các số lớn mà tránh gặp phải những lỗi có thể gặp như trên. Trong phạm vi của sáng kiến này, tôi xin giới thiệu một số bài toán phải xử lí số nguyên có giá trị lớn bằng cách lưu trữ (đọc) chúng dưới dạng kiểu dữ liệu xâu .
Ngoài ra, việc sử dụng kiểu dữ liệu xâu còn giúp người lập trình có nhiều thuận tiện hơn trong việc xử lí. Điều này cũng được chỉ ra trong từng bài toán cụ thể mà sáng kiến kinh nghiệm có đệ cập đến.
2. Mục đích nghiên cứu: Sáng kiến kinh nghiệm nghiên cứu nhằm mục đích phục vụ công tác giảng dạy và bồi dưỡng học sinh giỏi trường, học sinh giỏi tỉnh, học sinh thi tin học trẻ. Ngoài ra sáng kiến kinh nghiệm còn được sử dụng làm chuyên đề báo cáo cấp tổ.
Sáng kiến kinh nghiệm chỉ ra ưu điểm của kiểu dữ liệu xâu trong việc ứng dụng nó để giải các bài toán yêu cầu xử lí dữ liệu số lớn. Kiểu dữ liệu xâu là kiểu dữ liệu được đề cập khá đầy đủ, chi tiết, sáng tỏ trong sách giáo khoa tin học 11 và các tài liệu tham khảo khác.
3. Đối tượng nghiên cứu: Kiểu dữ liệu xâu và các thao tác xử lí xâu. Cách vận dụng kiểu dữ liệu xâu để thay thế kiểu dữ liệu số. Một số dạng bài tập liên quan đến sáng kiến kinh nghiệm. Thuật toán để giải một số bài toán tiêu biểu.
4. Đối tượng khảo sát , thực nghiệm: Học sinh khối 11 đã học xong bài 12 kiểu dữ liệu xâu, học sinh giỏi trường, đội tuyển học sinh giỏi tỉnh, đội tuyển thi tin học trẻ và các đồng nghiệp.
5. Phương pháp nghiên cứu: Đi từ nhu cầu thực tiễn trong công tác giảng dạy, đặc biệt là công tác bồi dưỡng học sinh giỏi. Cụ thể là qua các bài toán xử lí dữ liệu số lớn, để tìm ra cách xử lí đơn giản, hiệu quả hơn. Đó là cách sử dụng kiểu dữ liệu xâu. Vận dụng và kiểm tra tính hiệu quả, tính tối ưu của phương pháp. Từ đó từng bước xây dựng nên sáng kiến kinh nghiệm. 
Tóm lại , phương pháp nghiên cứu là đi từ thực tiễn đến lí luận, rồi từ lí luận quay về phục vụ thực tiễn.
6. Phạm vi và kế hoạch nghiên cứu: Sáng kiến kinh nghiệm được thực hiện theo kế hoạch của ban chuyên môn nhà trường, bắt bầu từ tháng 8 /2016 đến tháng 5/2017, và là kết quả tích luỹ của nhiều năm dạy học và bồi dưỡng học sinh giỏi tỉnh.
 II. NỘI DUNG.
1. Cơ sở lí luận: Kiểu dữ liệu xâu là dãy hữu hạn các kí tự trong bộ mã ASCII. Mỗi kí tự là một phần tử của xâu. Số lượng các phần tử của xâu được gọi là độ dài của xâu. Độ dài tối đa của xâu là 255.
 Một số nguyên lớn cũng được xem như là “một xâu” mà mỗi phần tử của nó là một kí tự thuộc phạm vi [’0’..’9’]. Ngoài ra, các phép so sánh chữ số còn có thể áp dụng để so sánh các kí tự số. Do đó việc ứng dụng kiểu dữ liệu xâu vào xử lí dữ liệu số là khá thuận lợi và cho phép xử lí các số lớn có số chữ số lên tới 255 số. Tuy nhiên, các phần tử của xâu là các kí tự nên không áp dụng các phép toán số học lên nó được. Việc này được giải quyết đơn giản bằng cách sử dụng các hàm, thủ tục xử lí xâu mà học sinh đã được trang bị sẵn.
	Việc sử dụng kiểu dữ liệu xâu để giải quyết bài toán có dữ liệu số lớn thường được thực hiện qua 3 bước cơ bản như sau:
B1. Đọc số dưới dạng xâu;
B2. Xử lí các phần tử của xâu tuỳ vào yêu cầu cụ thể của từng bài toán;
B3. Đưa ra kết quả của bài toán.
2. Thực trạng và giải pháp: Sau đây là những bài toán đã sử dụng kiểu dữ liệu xâu để giải quyết và có so sánh tính hiệu quả của phương pháp này với một số phương pháp khác.
Bài toán 1. SỐ ĐƠN ĐIỆU_Bài 3. Đề thi hsg tỉnh lớp 11 bảng A năm học 2013-2014
Số a1, a2, , aN được gọi là số đơn điệu nếu ai ai+2 hoặc ai > ai+1 < ai+2 (i:=1àN-2). Số có một chữ số, số có hai chữ số khác nhau cũng được gọi là số đơn điệu lần lượt có độ dài bằng 1, 2.
Yêu cầu: Viết chương trình xác định số chữ số lớn nhất tạo thành số đơn điệu trong biểu diễn của một số cho trước.
Dữ liệu: Vào từ tệp văn bản bai1.inp là một số nguyên dương N (N có số chữ số < 256 ).
Dữ liệu ra: Ghi ra tệp văn bản bai1.out một số nguyên, là số chữ số lớn nhất tạo thành đoạn số đơn điệu của số N. Nếu không có đoạn số đơn điệu thì ghi số 0.
VD:	
Bai1.inp
Bai1.out
13243544446666
7
Xác định bài toán:
Input: Số nguyên dương N.
Output: Số chữ số lớn nhất tạo thành đoạn số đơn điệu của N.
Ý tưởng thuật toán:
Đọc N dưới dạng xâu s
Ta xét tất cả các đoạn con trong biểu diễn của N có độ dài giảm dần từ số lượng chữ số của N về 1(Xét các đoạn con của xâu s có độ dài giảm từ độ dài của xâu s về 1). Mỗi đoạn con đã xét nếu thoả mãn điều kiện bài toán thì đưa ra độ dài của đoạn con đó rồi thoát.
Sử dụng hàm để kiểm tra một đoạn con có thoả mãn điều kiện bài toán hay không.
Chương trình tham khảo
program bai1;
const fi='bai1.inp';
 fo='bai1.out';
var s:string;
 i,l:byte;
 f,g:text;
procedure motep;
begin
 assign(f,fi);reset(f);
 assign(g,fo);rewrite(g);
end;
function kt(m,n:byte):boolean;
var p:word;
begin kt:=true;
 for p:=m to n+m-2 do
 if ((s[p]>=s[p+1]) and (s[p+1]>=s[p+2])) or
 ((s[p]<=s[p+1]) and (s[p+1]<=s[p+2])) then kt:=false;
end;
procedure	xuli;
Begin 
 read(f,s);
 close(f);
 for l:=length(s) downto 3 do
 begin for i:=1 to length(s)-l+1 do
 if kt(i,l) then begin write(g,l+2);close(g);exit;end;
 end;
 write(g,0); close(g);
end;
Begin	motep;
	Xuli;
End.
Bài toán 2. SỐ VÔ HẠN_Bài 2. Đề thi giáo viên giỏi trường năm 2014; Đề thi Hsg tỉnh lớp 11 bảng B năm học 2013- 2014. 
Một số vô hạn được tạo ra bằng cách viết liên tiếp các số chính phương từ bé đến lớn. Hãy cho biết chữ số thứ N (N<256) trong số vô hạn trên là số nào?
Dữ liệu vào: Từ tệp văn bản Bai2.INP là số nguyên dương N.
Dữ liệu ra: Ghi ra tệp văn bản Bai2.OUT một số, là số ở vị trí thứ N trong số vô hạn.
VD:
Bai2.INP
Bai2.OUT
13
4
Giải thích 1491625364964
+ Xác định bài toán:
Input: Số nguyên dương N
Output: Số ở vị trí thứ N trong số vô hạn
+ Ý tưởng thuật toán:
Sử dụng xâu s để biểu diễn số vô hạn. Trong khi độ dài của xâu s còn bé thua N thì ta lấy các số chính phương lần lượt từ bé đến lớn rồi đổi thành xâu và ghép vào xâu s
Đưa ra phần tử thứ N của xâu s(S[N]).
+ Chương trình tham khảo.
Program bai2;
const fi='bai2.inp';
 fo='bai2.out';
var s,x:string;
 i,N,j:byte;
 f,g:text;
procedure motep;
begin
 assign(f,fi);reset(f);
 assign(g,fo);rewrite(g);
end;
procedure	xuli;
Begin 
 read(f,N);
 close(f);s:=’’;
	 while length(s)<=N do
	begin 	
 	 i:=1;j:=sqr(i); str(j,x); s:=s+x; inc(i);
	end;
 write(g,s[N]); close(g);
end;
Begin	motep;
	Xuli;
End.
Bài toán 3. Cho số nguyên dương N, hãy cho biết trong N có bao nhiêu chữ số ( N là số có bao nhiêu chữ số)?
	Dữ liệu vào: Từ tệp văn bản Bai3.inp chỉ một số, là số nguyên N.
	Dữ liệu ra: Ghi lên tệp văn bản Bai3.out chỉ một số, là số chữ số của N
VD:
Bai3.inp
Bai3.out
1234567891011121314
19
+/ Xác định bài toán:
Input: Số nguyên dương N
Output: Số chữ số có trong biểu diễn của N.
+/ Ý tưởng thuật toán:
Cách 1. Ta biết mỗi lần chia lấy phần nguyên của N cho 10 thì số chữ số mới của N giảm đi 1 số, ví dụ 123 div 10=12. Như vậy để đếm số lượng chữ số có trong N ta chỉ cần đếm số lần gán N:=N div 10 cho đến khi N=0. Để thực hiện công việc này ta dùng câu lệnh While_do
Cách 2. Đọc N thành xâu s. Length(s) chính là số chữ số có trong biểu diễn của N
+/ Chương trình tham khảo
Cách 1. Không sử dụng thủ tục Str
Program	bai3;
const 	fi='bai3.inp';
 	fo='bai3.out';
var 	N:word;
 	dem:byte;
 	f,g:text;
procedure 	motep;
begin
 	assign(f,fi);reset(f);
 	assign(g,fo);rewrite(g);
end;
Begin
	Motep;
 readln(f,N);
	Dem:=0;
	While N>0 do
	Begin
	N:=N div 10;
	Inc(dem);
	End;
	Write(g,dem); close(g);close(f);
End.
Cách 2. Đọc N thành xâu s
Program 	bt3;
const 	fi='bai3.inp';
 	fo='bai3.out';
var 	s:string;
 	f,g:text;
procedure 	motep;
begin
 	assign(f,fi);reset(f);
 	assign(g,fo);rewrite(g);
end;
procedure	xuli;
Begin	readln(f,s);
	Write(g,‘so chu so co trong bieu dien cua N la:’, length(s));
	Close(g); close(f);
End;
Begin	motep;
	Xuli;
End.
	Rõ ràng khi đọc N dưới dạng xâu thì ý tưởng thuật toán đơn giản hơn nhiều. Mặt khác xử lí được số N lớn( N có thể có 255 chữ số).
Bài toán 4. Cho số nguyên dương N, đếm xem trong N có bao nhiêu chữ số 0 ?
Dữ liệu vào: Từ tệp văn bản Bai4.inp chỉ một số, là số nguyên N.
	Dữ liệu ra: Ghi lên tệp văn bản Bai4.out chỉ một số, là số chữ số 0 của N
VD
Bai4.inp
Bai4.out
108108108108108108
6
Xác định bài toán:
+ input: Số nguyên dương N;
+ Output: Số chữ số 0 trong biểu diễn của N
Ý tưởng thuật toán
Cách 1. Ta tách các chữ số của N từ hàng đơn vị trở lên, mỗi lần ta tách 1 số. Khi tách được một số thì ta kiểm tra xem số đó có phải là số 0? Nếu đúng thì tăng dem lên 1 đơn vị. Việc tách số được thực hiện bằng 2 phép toán mod và div
Cách 2. Đọc N thành xâu s, sau đó đếm số lần xuất hiện của kí tự ‘0’ có trong xâu s.
Chương trình tham khảo:
Theo cách 1.
const 	fi='bai4.inp';
 	fo='bai4.out';
var 	N:longint;
	r, dem:byte;
 	f,g:text;
procedure 	motep;
begin
 	assign(f,fi);reset(f);
 	assign(g,fo);rewrite(g);
end;
procedure	xuli;
Begin	 readln(f,N);
	Dem:=0;
	While N>0 do
	Begin
	R:=N mod 10;
	N:=N div 10;
	If r=0 then inc(dem);
	End;
	Write(g,‘so chu so 0 trong N la:’,dem);
	Close(g); close(f);
End;
Begin	motep;
	Xuli;
End.
Theo cách 2.
const 	fi='bai4.inp';
 	fo='bai4.out';
var 	s:string;
	dem,i:byte;
 	f,g:text;
procedure 	motep;
begin
 	assign(f,fi);reset(f);
 	assign(g,fo);rewrite(g);
end;
procedure	xuli;
Begin	readln(f,s);dem:=0;
	For i:=1 to length(s) do if s[i]=’0’ then inc(dem);
	Write(g,‘so chu so 0 co trong bieu dien cua N la:’, dem);
	Close(g); close(f);
End;
Begin	motep;
	Xuli;
End.
Nhận xét: Với cách 1, ta thấy với học sinh có học lực môn tin trung bình vẫn còn khá trừu tượng. Mặt khác, với N rất lớn thì khả năng lưu trữ N với một kiểu dữ liệu chuẩn nào đó là không khả thi.
	Còn cách 2, ta thấy độ phức tạp và trừu tường thấp vì chỉ cần kiểm tra từng phần tử của xâu xem nó có phải là kí tự ‘0’?. Mặt khác sử dụng xâu để thay thế số có thể xử lí được số rất lớn với số chữ số là 255 số.
Bài toán 5. Cho số nguyên dương N, hãy cho biết tần số xuất hiện của mỗi chữ số có trong N.
Dữ liệu vào: Từ tệp văn bản Bai5.inp chỉ một số, là số nguyên N.
	Dữ liệu ra: Ghi lên tệp văn bản Bai5.out tần số xuất hiện của mỗi chữ số từ 0 đến 9 có trong N. Tần số của mỗi số trên một dòng.
VD
Bai5.inp
Bai5.out
1231231231231231234567800
Tan so cua 0: 2
Tan so cua 1: 6
Tan so cua 2: 6
Tan so cua 3: 6
Tan so cua 4: 1
Tan so cua 5: 1
Tan so cua 6: 1
Tan so cua 7: 1
Tan so cua 8: 1
Tan so cua 9: 0
+ Xác định bài toán:
 Input: Số nguyên dương N;
Output: Tần số xuất hiện của mỗi chữ số có trong biểu diễn của N
+ Ý tưởng thuật toán
Cách 1.Với N khá nhỏ
 - Sử dụng một mảng một chiều dem:array[0..9] of byte. Dem[i] dùng để đếm số lần xuất hiện của chữ số i trong biểu diễn của N.
- Ta tách các chữ số của N từ hàng đơn vị trở lên, mỗi lần ta tách 1 số. Khi tách được một số i thì ta tăng dem[i] lên 1 đơn vị. Việc tách số được thực hiện bằng 2 phép toán mod và div.
- Sau khi việc tách số kết thúc thì ta đưa ra các phần tử của mảng dem
Cách 2. Với N lớn
- Sử dụng một mảng một chiều dem:array[‘0’..’9’] of byte. Dem[i] dùng để đếm số lần xuất hiện của kí tự số ‘i’ có trong trong biểu diễn dạng xâu của N.
- Đọc N thành xâu sau đó đếm số lần xuất hiện của mỗi kí tự có trong xâu. 
- Đưa ra các phần tử của mảng dem
+ Chương trình tham khảo:
Theo cách 1.
const 	fi='bai5.inp';
 	fo='bai5.out';
var 	N:longint;i:byte;
	dem:array[0..9] of byte;
 	f,g:text;
procedure 	motep;
begin
 	assign(f,fi);reset(f);
 	assign(g,fo);rewrite(g);
end;
procedure	xuli;
Begin	readln(f,N);
For i:=0 to 9 do dem[i]:=0;
	While N>0 do
	Begin
	i:=N mod 10;
	Inc(dem[i]);
	N:=N div 10;
	End;
	For i:=0 to 9 do 
writeln(g,‘tan so cua ‘,i, ‘ : ’,dem[i]);
Close(g); close(f);
End;
Begin	motep;
	Xuli;
End.
Theo cách 2
Program 	bai5c2;
const 	fi='bai5.inp';
 	fo='bai5.out';
var 	s:string;i:char;
	dem:array[’0’..’9’] of byte;
 	f,g:text;
procedure 	motep;
begin
 	assign(f,fi);reset(f);
 	assign(g,fo);rewrite(g);
end;
procedure	xuli;
var	j:byte;
Begin	readln(f,s);
For i:=’0’ to ’9’ do dem[i]:=0;
	For i:=’0’ to ’9’ do 
	For j:=1 to length(s) do if s[j]=i then inc(dem[i]);
For i:=’0’ to ’9’ do 
writeln(g,‘tan so cua ‘,i, ‘ : ’,dem[i]);
Close(g); close(f);
End;
Begin	motep;
	Xuli;
End.
Bài toán 6. Cho số nguyên dương N và số nguyên k, hãy xóa k chữ số trong N để được số lớn nhất.
Dữ liệu vào: Từ tệp văn bản Bai6.inp gồm 2 số là số nguyên N và số nguyên k. Mỗi số trên 1 dòng.
	Dữ liệu ra: Ghi lên tệp văn bản Bai6.out chỉ một số, là số lớn nhất thu được.
VD
Bai6.inp
Bai6.out
1324987685
5
98785
+ Xác định bài toán:
 Input: Số nguyên dương N và số nguyên dương k
Output: Số lớn nhất tìm được sau khi đã xóa đi k chữ số.
+ Ý tưởng thuật toán
- Ta thấy với N là kiểu số thì việc xóa đi k chữ số trong N là khá phức tạp. Việc này sẽ đơn giản hơn nếu N được biểu diễn dưới dạng xâu. Từ đó ta đọc N sang xâu s.
- Để có được số lớn nhất sau khi xóa k kí tự ta có thể thực hiện như sau:
+/ Tìm kí tự lớn nhất trong k+1 kí tự đầu của xâu s. Chẳng hạn kí tự s[i]
+/ Ghép kí tự tìm thấy vào xâu kết quả P, p:=p+s[i];
+/ Xóa đi i kí tự đầu của xâu s;
+/ Gán lại giá trị mới cho k, k:=k-i+1;
Quá trình trên lặp lại cho đến khi k=0, tức là đã xóa hết k kí tự
Sau đó lấy xâu p ghép với phần còn lại của xâu s, p:=p+s; Đổi P thành số hoặc đưa ra xâu p
+ Chương trình tham khảo
Program	bai6;
const 	fi='bai6.inp';
 	fo='bai6.out';
var 	s:string; k,i:byte;
	f,g:text;
	P, S:string;
procedure 	motep;
begin
 	assign(f,fi);reset(f);
 	assign(g,fo);rewrite(g);
end;
Function	max(k:byte):byte;
Begin	max:=1;
	For i:=2 to k+1 do
	If s[i]>s[max] then max:=i;
End;
Procedure 	xuli;
Begin	readln(f,s); read(f,k);
	P:=’’;
	While (k>0) and (length(s)>0) do
	Begin
	I:=max(k);
	P:=p+s[i];
	Delete(s,1,i);
	K:=k-i+1;
	End;
	If k=0 then p:=p+s;
	Write(g,‘ so lon nhat tim duoc la: ‘, p);
	Close(f); close(g);
End;
Begin	motep;
	Xuli;
End.
Bài toán 7. Cho số nguyên dương N, hãy tìm biểu diễn nhị phân của N
Dữ liệu vào: Từ tệp văn bản Bai7.inp chỉ một số, là số nguyên N.
	Dữ liệu ra: Ghi lên tệp văn bản Bai7.out biểu diễn nhị phâ của số N.
VD
Bai7.inp
Bai7.out
Bai7.inp
Bai7.out
125
01111111
255
11111111
Xác định bài toán:
+ Input: Số nguyên dương N
+ Output: Biểu diễn nhị phân của số N
Ý tưởng thuật toán:
Cách 1: Sử dụng mảng một chiều để lưu số dư của phép chia N cho 2, sau mỗi lần chia thì N được gán lại với giá trị mới là N chia 2. Quá trình kết thúc khi N=0. Sau đó đưa ra các phần tử của mảng theo thứ tự từ phần tử có chỉ số lớn đến phần tử có chỉ số nhỏ nhất. Để xác định chỉ số cuối của mảng một chiều ta dùng một biến kiểu nguyên d. Ban đầu d:=0, sau đó mỗi lần chia lấy dư N cho 2 ta tăng biến d lên một đơn vị.
Cách 2 Sử dụng biến xâu s để lưu các số dư trong phép chia N cho 2. Ban đầu s:=’’, sau đó mỗi lần lấy được một số dư trong phép chia N cho 2, ta chuyển nó sang kiểu xâu và ghép vào biến xâu s. Dạng nhị phân của N là xâu ngược của s. 
Chương trình tham khảo
Theo cách 1.
program bai7c1;
const maxd=100;
	 fi=’bai7.inp’;
	 fo=’bai7.out’;	
var N:word;
 i,d:byte;f,g:text;
 a:array[1..maxd] of byte;
procedure 	motep;
begin
 	assign(f,fi);reset(f);
 	assign(g,fo);rewrite(g);
end;
procedure	xuli;
begin
 readln(f,N);
 d:=0;
 while N>0 do
 begin
 inc(d);
 a[d]:=N mod 2;
 N:=N div 2;
 end;
 for i:=d downto 1 do write(g,a[i]);
 close(g); close(f);
end;
Begin 	motep;
	Xuli;
End.
Theo cách 2.
program bai7c2;
const	fi=’bai7.inp’;
	fo=’bai7.out’;
var N:word;
 i:byte;
 s,x:string; f,g:text;
procedure	motep;
begin	assign(f,fi);assign(g,fo);
	reset(f); rewrite(g);
end;
procedure	xuli;
begin
 read(f,N);
 s:='';
 while N>0 do
 begin
 i:=N mod 2;
 N:=N div 2;
 str(i,x);s:=s+x;
 end;
 write(g,s);
 close(g); close(f);
end;
Begin	motep;
	Xuli;
End.
Nhận xét: Ta thấy 2 thuật toán này là tương tự nhau vì xâu cũng được xem là mảng một chiều mà mỗi phần tử là một kí tự. Tuy nhiên ở thuật toán 1 ta phải xác định được số lượng phần tử thực sự của mảng a, tức là xác định giá trị của biến d. Còn với thuật toán 2 thì không cần vì để xác định số lượng phần tử xâu s thì ta dùng hàm length(s).
Bài toán 8. Cho số nguyên dương N, hãy sắp xếp các số trong biểu diễn của N để được số lớn nhất.
Dữ liệu vào: Từ tệp văn bản Bai8.inp chỉ một số, là số nguyên N.
	Dữ liệu ra: Ghi lên tệp văn bản Bai8.out chỉ một số, là số đã được sắp xếp.
VD
Bai8.inp
Bai8.out
846759624
987665442
Xác định bài toán:
+ Input: Số nguyên dương N
+ Output: Số lớn nhất sắp xếp được trong biểu diễn của số N
Ý tưởng thuật toán:
Cách 1: Sử dụng mảng một chiều để lưu các số có trong biểu diễn của N(Với N nhỏ). Để lấy được các số có trong biểu diễn của N, ta dùng phép chia N mod 10, sau mỗi lần chia thì N được gán lại với giá trị mới là N div 10. Quá trình kết thúc khi N=0. Sau đó đưa ra các phần tử của mảng theo thứ tự từ tăng dần. Để xác định chỉ số cuối của mảng một chiều ta dùng một biến kiểu nguyên d. Ban đầu d:=0, sau đó mỗi lần chia lấy dư N cho 10, ta tăng biến d lên một đơn vị.
Cách 2: Sử dụng biến xâu s để lưu N( đọc N dưới dạng xâu). Sau đó ta đưa ra các phần tử của xâu s theo thứ tự giảm dần. 
Chương trình tham khảo
Theo cách 1.
program bai8c1;
const	fi=’Bai8.inp’; fo=’Bai8.out’;
var N:longint;
 i,j,d:byte; f,g:text;
 a:array[1..100] of byte;
procedure	motep;
begin	assign(f,fi); reset(f);
	assign(g,fo);rewrite(g);
end;
procedure	xuli;
begin
 read(f,N);
 d:=0;
 while N>0 do
 begin
 inc(d);
 a[d]:=N mod 10;
 N:=N div 10;
 end;
 for j:=9 downto 0 do
 for i:= 1 to d do
 if a[i]=j then write(g,a[i]);
 close(f); close(g);
end;
Begin
	Motep;
	Xuli;
End.
Theo cách 2.
program bai8c2;
var N:word;
 i:byte;
 j:char;
 s,x:string;
begin
 write('nhap N='); readln(N);
 s:='';
 while N>0 do
 begin
 i:=N mod 10;
 N:=N div 10;
 str(i,x);s:=s+x;
 end;
 write('so lon nhat trong bieu dien cua N la:');
 for j:='9' downto '0' do
 for i:= 1 to length(s) do
 if s[i]=j then write(s[i]);
 readln
end.
Nhận xét: Theo cách 1, ta thấy các phần tử của mảng a theo thứ tự là số đảo ngược của N và giá trị của N bị thay đổi (giá trị mới =0). Việc giữ lại giá trị của N có thể thực hiện bằng cách gán giá trị của nó cho 1 biến khác. Nhìn chung thì ý tưởng của 2 cách giải không khác nhau nhiều lắm. 
Bài toán 9. Số đối xứng là số mà ta đọc các chữ số của nó từ trước ra sau hay theo thứ tự ngược lại thì có kết quả như nhau. Cho hai số nguyên dương M, N ( M<N<=100000000), đếm xem trong đoạn [M, N] có bao nhiêu số đối xứng? .
Dữ liệu vào: Từ tệp văn bản Bai9.inp gồm 2 số, là số nguyên M, N. Hai số cách nhau 1 dấu cách
	Dữ liệu ra: Ghi lên tệp văn bản Bai9.out chỉ một số, là số chữ số đối xứng có trong đoạn [M, N].
VD
Bai9.inp
Bai9.out
10 100
9
Xác định bài toán:
+ Input: 2 số nguyên dương M, N (M<N<=10000)
+ Output: Số các số đối xứng có trong đoạn [M, N]
Ý tưởng thuật toán
Cách 1: Với mỗi số trong đoạn [M, N] ta sẽ chuyển nó thành mảng một chiều rồi kiểm tra tính đối xứng của các phần tử mảng một chiều đó. Việc kiểm tra đối xứng được thực hiện bằng một chương trình con.
Cách 2: Với mỗi số trong đoạn [M, N] ta sẽ chuyển nó thành xâu rồi kiểm tra tính đối xứng của xâu đó. Việc kiểm tra đối xứng cũng được thực hiện bằng