SKKN Kỹ năng dùng mảng một chiều để xử lý số nguyên lớn giúp giải các bài toán khó trong lập trình pascal

MỤC LỤC
A. MỞ ĐẦU ..
I. Lí do chọn đề tài .
II. mục đích nghiên cứu ..
III. Đối tượng nghiên cứu ...
IV. Phương pháp nghiên cứu .
2
2
2
2
2
B. NỘI DUNG
I. Cơ sở lí luận 
3
II. Thực trạng vấn đề trước khi áp dụng .
3
III. Giải pháp sử dụng .
3
Phần một: XÂY DỰNG CÁC PHÉP TOÁN SỐ HỌC TRÊN SỐ LỚN ...
3
Biểu diễn số nguyên lớn
3
Xây dựng các phép toán số học 
5
Phép so sánh .
5
Phép cộng một số lớn với một số nhỏ ..
5
1.2.3. Cộng hai số nguyên lớn 
6
1.2.4. Phép trừ .
6
1.2.5. Phép nhân một số lớn với một số nhỏ ..
7
1.2.6. Phép nhân hai số nguyên lớn 
7
1.2.7. Phép chia một số nguyên lớn cho một số nguyên nhỏ (lấy phần thương nguyên (div) và dư (mod)) .
8
1.2.8. Phép chia hai số nguyên lớn (lấy phần thương nguyên (div) và dư (mod)) .
8
Phần hai: MỘT SỐ BÀI TOÁN ỨNG DỤNG XỬ LÝ SỐ LỚN .....
9
2.1. Bài toán 1 Tính giai thừa .
9
2.2. Bài toán 2 (Đề Bảng C Tin học trẻ không chuyên toàn quốc) .
10
2.3. Bài toán 3 (Đề thi OLIMPIC Tin học sinh viên Việt Nam 2005) ...
12
2.4. Bài toán 4 (Đề thi OLP 2004) .....
15
Phần ba: bài tập luyện tập . 
18
IV. Hiệu quả của sáng kiến .
20
C. KẾT LUẬN, KIẾN NGHỊ ...
21
I. Kết luận ...
21
II. Kiến nghị 
21
A. MỞ ĐẦU
I. Lí do chọn đề tài.
Trong mỗi ngôn ngữ lập trình thường có một số kiểu dữ liệu chuẩn cho biết phạm vi giá trị có thể lưu trữ, dung lượng bộ nhớ cần thiết để lưu trữ và xác định các phép toán có thể tác động lên dữ liệu. Chẳng hạn trong Turbo Pascal, một số kiểu dữ liệu dạng số nguyên bao gồm: byte, integer, word, longint, int64, qword. Trong đó kiểu qword có phạm vi lớn nhất, mỗi giá trị lưu trữ trong 8 byte cho phép biến lưu số tối đa có 20 chữ số. Tuy nhiên khi thực hiện các phép tính với số nguyên ngoài phạm vi biểu diễn được cung cấp (có nhiều hơn 20 chữ số) ta cần thiết kế cách biểu diễn và các hàm thực hiện các phép toán cơ bản với các số nguyên lớn.
Gần đây trong các kỳ thi học sinh giỏi người ta thường hay đưa ra các bài toán cần kết hợp cả xử lý số lớn. Vì vậy tìm hiểu về biểu diễn số lớn và các phép toán với số lớn là cần thiết. Trong khuôn khổ của đề tài này, tôi đưa ra cách biểu diễn số nguyên không âm lớn và các phép toán trên đó.
Cụ thể. Tên đề tài: “KỸ NĂNG DÙNG MẢNG MỘT CHIỀU ĐỂ XỬ LÝ SỐ NGUYÊN LỚN GIÚP GIẢI CÁC BÀI TOÁN KHÓ TRONG LẬP TRÌNH PASCAL”
II. Mục đích của đề tài
Sử dụng các ví dụ cụ thể về các số nguyên lớn để học sinh nắm được phương pháp chuyển đổi. Và thông qua các ví dụ đó hướng dẫn học sinh làm một số bài toán ứng dụng sử lí số nguyên lớn.
III. Đối tượng nghiên cứu.
Học sinh giỏi khối 11 tại trường THPT NGỌC LẶC .
Sử dụng máy tính để chạy các chương trình.
IV. Phương pháp nghiên cứu .
- Kết hợp thực tiễn việc ôn luyện học sinh giỏi ở trường THPT THPT NGỌC LẶC.
- Có tham khảo các tài liệu về ngôn ngữ lập trình Pascal và tài liệu về sáng kiến kinh nghiệm.
B. NỘI DUNG
I.Cơ sở lí luận
Khi giải quyết các bài toán về số trong pascal ta dùng các kiểu dữ liệu sau: byte, integer, word, longint, int64, qword trong đó kiểu qword có phạm vi lớn nhất cho phép biến lưu số tối đa có 20 chữ số. Khi số nguyên quá lớn vượt qua giới hạn này (ví dụ số nguyên 21 số trở lên) thì việc lưu trữ nó bằng các kiểu dữ liệu trên là điều không thể. 
II. Thực trạng vấn đề trước khi áp dụng
1. Thuận lợi:
Được sự quan tâm của Sở Giáo dục & Đào tạo và Ban giám hiệu nhà trường, bộ môn Tin học được trang bị phòng máy tính cùng với các máy chiếu phục vụ cho nhu cầu công tác giảng dạy ứng dụng CNTT của giáo viên. 
2. Khó khăn
 Chất lượng đầu vào không cao, ở trường THCS còn học sơ sài kiến thức tin học, Ngôn ngữ Pascal là ngôn ngữ khó trừu tượng đối với học sinh, 
 Những bài toán nâng cao còn khá khó đối với khả năng của học sinh dẫn đến học sinh cảm thấy sợ khi gặp những dạng toán đó, từ đó không yêu thích bộ môn.
III.Giải pháp sử dụng
Phần một: XÂY DỰNG CÁC PHÉP TOÁN SỐ HỌC TRÊN SỐ LỚN
1.1. Biểu diễn số nguyên lớn	
 Thông thường người ta sử dụng các cách biểu diễn số nguyên lớn sau:
Xâu kí tự: Mỗi kí tự của xâu tương ứng với một chữ số của số nguyên lớn tính từ trái qua phải.
Mảng các số: Sử dụng mảng lưu các chữ số (hoặc một nhóm chữ số) của số nguyên lớn.
Danh sách liên kết các số: Sử dụng danh sách liên kết các chữ số (hoặc một nhóm chữ số)
	Ở đây, ta xét cách biểu diễn thứ hai, biểu diễn số nguyên lớn bằng mảng, mỗi phần tử của mảng là một chữ số của số và chỉ xét với các số nguyên lớn không âm.
Khai báo
Const	Maxn=1000;
Type
	Chuso=0..9;
	Bigint=Array[1..maxn] of chuso;
Var X,a,b: Bigint;
	Để dễ dàng thực hiện các phép toán ta lưu mảng theo thứ tự ngược lại với số, tức là các chữ số trong mảng lưu theo chiều từ trái sang phải: chữ số hàng đơn vị là phần tử thứ nhất, chữ số hàng chục là phần tử thứ hai,  
Ví dụ: số X = 1965 thì mảng X sẽ là: (5,6,9,1,0,0,0) tức là X[1] = 5; X[2] = 6; X[3] = 9; X[4] = 1; X[5] = 0,
	Dữ liệu vào: Gồm hai số nguyên lớn hoặc số nguyên lớn và số nguyên nhỏ (số nhỏ là số có kiểu chuẩn: byte, integer, word, longint), hai số cách nhau một dòng trống, mỗi số nguyên lớn có thể ghi trên nhiều dòng.
Thủ thục đọc file dữ liệu vào gồm hai số nguyên lớn:
procedure readf;
var 
 s:string; so:chuso; code,i,n:integer;
begin
 assign(f,fi); reset(f);
 ma:=0; fillchar(a,sizeof(a),0); {a là số nguyên lớn}
 mb:=0; fillchar(b,sizeof(b),0); {b là số nguyên lớn}
 repeat readln(f,s); ma:=ma+length(s); until s='';
 repeat readln(f,s); mb:=mb+length(s); until s='';
 close(f); reset(f);
 n:=ma; {ma là độ dài của số a}
 repeat
 readln(f,s);
 for i:=1 to length(s) do begin val(s[i],so,code); a[n]:=so; n:=n-1; end;
 until s='';
 n:=mb; {mb là độ dài của số b}
 repeat
 readln(f,s); 
 for i:=1 to length(s) do begin val(s[i],so,code); b[n]:=so; n:=n-1; end;
 until s='';
 close(f);
end;
Thủ tục đọc file dữ liệu vào gồm một số nguyên lớn và một số nguyên nhỏ 
procedure readf;
var s:string; so:chuso; code,i,n:integer;
begin
 assign(f,fi); reset(f);
 ma:=0; fillchar(a,sizeof(a),0); {a là số nguyên lớn}
 repeat readln(f,s); ma:=ma+length(s); until s='';
 close(f); reset(f); n:=ma;
 repeat
 readln(f,s);
 for i:=1 to length(s) do begin val(s[i],so,code); a[n]:=so; n:=n-1; end;
 until s='';
 readln(f,num); {num là số nguyên nhỏ}
 close(f);
end;
1.2. Xây dựng các phép toán số học
1.2.1. Phép so sánh
	Để so sánh hai số nguyên lớn a, b ta so sánh độ dài của hai số. Nếu hai số có độ dài bằng nhau thì so sánh từng chữ số của hai số. Hàm cmp trả về giá trị 1 nếu a lớn hơn b, trả về giá trị -1 nếu a nhỏ hơn b và trả về giá trị 0 nếu a bằng b.
Function cmp(a,b:bigint):integer;
Var i:integer;
Begin
	If ma>mb then begin cmp:=1; exit; end
 Else if ma<mb then begin cmp:=-1; exit; end
 Else
 For i:= ma downto 1 do 
 If a[i]>b[i] then begin cmp:=1; exit; end
 Else if a[i]<b[i] then begin cmp:=-1; exit; end;
 Cmp:=0;
End;
1.2.2. Phép cộng một số lớn với một số nhỏ
Thuật toán: cộng một số nguyên lớn a với một số nhỏ num kiểu longint.
Tong:=a; nho:=num;
Thực hiện lặp:
- Cộng từng chữ số (cộng từ bậc thấp đến bậc cao, có nhớ). t:=a[k]+nho;
nho:=t div 10; 
Tong[i]:=t mod 10;
Lưu ý: nho có thể lớn hơn 10.
Procedure cong( a:bigint; num:longint; var tong:bigint);
var t,nho,k:longint;
begin
 tong:=a; nho:=num; {đặt số cần cộng vào biến nho}
 for k:=1 to ma do
 begin
 t:=a[k]+nho;
 nho:=t div 10;
 tong[k]:=t mod 10;
 if nho=0 then break;
 end;
 while nho>0 do
 begin
 ma:=ma+1;
 tong[ma]:=nho mod 10;
 nho:=nho div 10;
 end;
end;
Chú ý: Trong Turbo Pascal kết quả trả lại của hàm là các kiểu cơ sở như: số nguyên, số thực, kí tự, và kiểu xâu. Nếu muốn trả lại kết quả là kiểu cấu trúc như mảng thì chỉ có cách dùng tham biến. Nhưng Free Pascal cho phép kết quả của hàm có thể là kiểu cấu trúc. Như vậy nếu viết trong Free Pascal ta có thể thay thủ tục cộng bằng hàm cộng hai số.
1.2.3. Cộng hai số nguyên lớn
Thuật toán: Như phép cộng thông thường đã học và thực hiện trên giấy. (cộng các chữ số từ bậc thấp đến bậc cao, có nhớ).
Procedure cong( a,b:bigint;Var tong:bigint );
var i,t:longint;
begin
 if ma >=mb then begin max:=ma; for i:=mb+1 to ma do b[i]:=0; end
 else begin max:=mb; for i:=ma+1 to mb do a[i]:=0; end;
 t:=0; fillchar(tong,sizeof(tong),0);
 for i:=1 to max do
 begin
 t:=t+a[i]+b[i];
 tong[i]:=t mod 10;
 t:=t div 10;
 end;
 if t>0 then begin max:=max+1; tong[max]:=t; end;
end;
1.2.4. Phép trừ 
Thuật toán: dùng thuật toán trừ kiểu thủ công (trừ các chữ số từ bậc thấp đến bậc cao, có nhớ). Có hai trường hợp:
Trường hợp a>b thì thực hiện a trừ cho b
Trường hợp a<b thì lấy b trừ cho a sau đó thêm dấu âm đằng trước.
Procedure tru (a,b:bigint; var hieu:bigint);
var i,nho:longint;
begin
 if ma >=mb then begin max:=ma; for i:=mb+1 to ma do b[i]:=0; end
 else begin max:=mb; for i:=ma+1 to mb do a[i]:=0; end;
 nho:=0;
 for i:=1 to max do
 begin
 nho:=a[i]-b[i]-nho;
 if nho<0 then begin hieu[i]:=10+nho; nho:=1; end
 else begin hieu[i]:=nho; nho:=0; end;
 end;
 {xoa so 0 o dau}
 while (max>1) and (kq[max]=0) do max:=max-1;
end;
1.2.5. Phép nhân một số lớn với một số nhỏ
 Thuật toán: Nhân một số lớn x với số nhỏ num. Ta không cần quan tâm num có bao nhiêu chữ số cứ coi nó chỉ là số có một chữ số và nhân với từng chữ số của số lớn x từ phải sang trái, nhớ có thể lớn. 
procedure nhan (x:bigint; num:longint; var tich:bigint);
var t,nho,k:longint;
begin
 nho:=0;
 for k:=1 to max do {max là độ dài của số lớn x}
 begin
 t:=num*x[k]+nho;
 nho:=t div 10;
 tich[k]:=t mod 10;
 end;
 while nho>0 do
 begin
 max:=max+1;
 tich[max]:=nho mod 10;
 nho:=nho div 10;
 end;
end;
1.2.6. Phép nhân hai số nguyên lớn
Thuật toán: Như phép nhân thông thường đã học và thực hiện trên giấy.
Theo trên ta thấy việc nhân hai số gồm hai thao tác:
Thao tác 1: Thực hiện việc nhân mỗi chữ số (từ phải sang trái cho đến hết) của số thứ hai với số thứ nhất.
Thao tác 2: Thực hiện phép cộng tất cả các số vừa tính được ở trên.
Ví dụ:
 352
 ×
 18 
 2816
 +
 352
 6336
procedure 
procedure nhan2so(a,b:bigint; var tich:bigint); {tích hai số lớn}
var x:bigint; j,k,l:integer;
begin
 j:=0;fillchar(kq,sizeof(kq),0);
 for k:=1 to mb do
 begin
 nhan(a,b[k],tich1); {tích của số lớn a với từng chữ số của b}
 for l:=1 to j do chen(0,tich1);
 cong(kq,tich1,tich); {cộng dồn các số tính được}
 kq:=tich;
 j:=j+1;
 end;
end;
1.2.7. Phép chia một số nguyên lớn cho một số nguyên nhỏ (lấy phần thương nguyên (div) và dư (mod))
	Thuật toán chia một số lớn cho một số nhỏ thao tác từ trái qua phải, mỗi lần hạ một phần tử xuống, gộp vào biến nhớ, thực hiện phép chia trực tiếp (vì số chia là một số nhỏ).
Procedure chia( a:bigint; num:longint;var thuong:bigint;var du:longint);
var nho,k,i,j:longint;
begin
 nho:=0; k:=ma; i:=0;
 while k>=1 do
 begin
 while (nho=1) do
 begin
 nho:=nho*10+a[k];
 if nho<num then begin i:=i+1; thuong[i]:=nho div num; end;
 k:=k-1;
 end;
 if nho>=num then begin i:=i+1; thuong[i]:=nho div num; end; 
 nho:=nho mod num;
 end;
 du:=nho; max:=i;
 {Xóa số 0 ở đầu của số thuong}
 while (thuong[1]=0) and (max>1) do
 begin
 for j:=1 to max-1 do thuong[j]:=thuong[j+1];
 max:=max-1;
 end;
end;
1.2.8. Phép chia hai số nguyên lớn (lấy phần thương nguyên (div) và dư (mod))
Thuật toán: Thực hiện phép chia như chia bình thường trên giấy, bằng cách trừ liên tiếp từng đoạn của số bị chia (từ trái sang phải) cho số chia:
Cắt lần lượt từng đoạn của số bị chia tính từ bên trái (có cộng thêm phần dư của các bước trung gian)
Đem chia các đoạn đó cho số chia bằng phép toán trừ.
Thương tìm được là dãy các số. Dãy số này là kết quả của phép chia các đoạn cho số chia (được phát triển dần về phía bên phải).
Phần dư của phép chia chính là đoạn còn lại không thể chia được nữa
procedure chia(a,b:bigint;var thuong,du:bigint);
var k,i,t,j:integer;
begin
 k:=ma; i:=0;max:=0;
 while k>=1 do
 begin
 while (not ss(du,b)) and (k>=1) do {cat lan luot tung doan cua so bi chia}
 begin
 chen(a[k],du);
 if not ss(du,b) then begin i:=i+1;thuong[i]:=0; end;
 dec(k);
 end;
 if ss(du,b) then {hàm ss(du,b) trả về giá trị true nếu du>=b}
 begin
 t:=0; {dem chia bang phep tru}
 while ss(du,b) do
 begin
 inc(t);
 tru(du,b);{thủ tục tru(a,b)thực hiện trừ du cho b, kết quả trả lại lưu vào du}
 end;
 inc(i);thuong[i]:=t;
 end;
 end;
 m:=i; {m là độ dài của thuong}
 {Xóa số 0 ở đầu của số thuong}
 while (thuong [1]=0) and (m>1) do
 begin
 for j:=1 to m-1 do thuong[j]:=thuong[j+1];
 m:=m-1;
 end;
end;
Phần hai
 MỘT SỐ BÀI TOÁN ỨNG DỤNG XỬ LÝ SỐ LỚN
2.1. Bài toán 1 Tính giai thừa
	Hãy tính N! (N<=2000)
Thuật toán:N! = 1*2**N. Vì N rất lớn, như vậy khi nhân các giá trị có thể rất lớn, ta không thể dùng các kiểu số có sẵn để lưu trữ mà phải dùng xâu hoặc mảng để lưu. 
	Để tính giá trị của biểu thức ta phải thực hiện thao tác: nhân một số lớn với số x (x<=2000).
Chương trình
uses crt;
const maxn=1000;
type
 chuso=0..9;
 bigint=array[1..maxn] of chuso;
var kq,tich:bigint; max,n,i:integer;
procedure nhan(x:bigint; num:longint; var tich:bigint);
var t,nho,k:longint;
begin
 nho:=0;
 for k:=1 to max do
 begin
 t:=num*x[k]+nho;
 nho:=t div 10;
 tich[k]:=t mod 10;
 end;
 while nho>0 do
 begin
 inc(max);
 tich[max]:=nho mod 10;
 nho:=nho div 10;
 end;
end;
Begin
 clrscr;
 write('Nhap N:'); readln(n);
 fillchar(kq,sizeof(kq),1);max:=1;
 for i:=1 to n do begin nhan(kq,i,tich); kq:=tich; end;
 for i:=max downto 1 do write(kq[i]);
 readln;
end.
2.2. Bài toán 2 (Đề Bảng C Tin học trẻ không chuyên toàn quốc năm 2004)
	Xét dãy số nguyên gồm n số hạng a1, a2, , an (n được gọi là độ dài của dãy) được xác định như sau:
a1 = a2 = a3 =1; an = an-3 +an-1 với n>3
Yêu cầu: Hãy xác định độ dài lớn nhất của dãy thỏa mãn mọi giá trị số hạng đều nhỏ hơn hay bằng một giá trị nguyên k cho trước.
Dữ liệu vào: từ file văn bản DAYSO.INP gồm một dòng chứa không quá 255 chữ số viết liền nhau (không có các số 0 vô nghĩa ở đầu) biểu diễn giá trị k.
Kết quả: Ghi ra file văn bản DAYSO.OUT độ dài lớn nhất của dãy tìm được.
Ví dụ
DAYSO.INP
DAYSO.OUT
41
12
Thuật toán: Tạo dần các số của dãy thỏa mãn tính chất trên. Do giá trị của số nguyên K rất lớn (255 chữ số). Vì vậy để tạo các số của dãy ta cần sử dụng phép toán cộng hai số lớn. 
const fi='dayso.inp';
 go='dayso.out';
type
 bigint=array[1..1000] of byte;
var
 a,b,c,d,k:bigint;
 S:array[1..1000] of char;
 dem,p,l:integer; thoat:boolean; f,g:text;
procedure Openf;
begin
 assign(f,fi); reset(f); assign(g,go); rewrite(g);
end;
{================================================}
procedure Closef;
begin
 close(f); close(g);
end;
{=============================================}
procedure Input;
var i:integer;
begin
 l:=0;
 while not eoln(f) do
 begin
 l:=l+1; read(f,s[l]);
 end;
 for i:=1 to l do k[i]:=ord(s[l-i+1])-48;
end;
{=============================================}
procedure cong(a,b:bigint; var c:bigint);
var i,t:longint;
begin
 t:=0;
 for i:=1 to p do
 begin
 t:=t+a[i]+b[i]; c[i]:=t mod 10; t:=t div 10;
 end;
 if t>0 then begin p:=p+1;c[p]:=t;end;
end;
{==============================================}
function Lonhon:boolean;
var i:integer;
begin
 if p<l then begin Lonhon:=false; exit; end
 else if p>l then begin Lonhon:=true; exit; end
 else
 for i:=p downto 1 do
 if k[i]>d[i] then begin lonhon:=false; exit; end
 else if k[i]<d[i] then begin lonhon:=true; exit; end;
 lonhon:=false;
end;
{===============================================}
procedure Main;
var i:integer;
Begin
 fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0);
 fillchar(c,sizeof(c),0); fillchar(d,sizeof(d),0);
 a[1]:=1;b[1]:=1; c[1]:=1; p:=1; dem:=3;
 repeat
 inc(dem); thoat:=false; cong(a,c,d);
 a:=b; b:=c; c:=d;
 if Lonhon then thoat:=true;
 until thoat;
end;
{==============================================}
Procedure Print;
Begin writeln(g,dem-1); end;
BEGIN
 Openf; input; Main; Print; closef;
END.
2.3. Bài toán 3 (Đề thi OLIMPIC Tin học sinh viên Việt Nam 2005)
Một hệ thống giao thông gồm N nút (các nút được đánh số từ 1 đến N), trong đó bất kỳ hai nút nào cũng có đoạn đường hai chiều nối chúng. Ta gọi đường đi giữa hai nút là dãy các đoạn đường kế tiếp nhau, bắt đầu từ một nút và kết thúc tại nút kia, trong đó không có nút nào trên đường đi được lặp lại.
Yêu cầu: Cần đếm tất cả các đường đi khác nhau giữa hai nút bất kỳ của mạng giao thông đã cho.
Ví dụ: Với hệ thống giao thông 4 nút trong hình dưới đây, ta có 5 đường đi nối giữa hai nút tô đen.
Hình 1
Hình 2
Dữ liệu: Nhập từ file văn bản PCOUNT.INP gồm một số nguyên dương N (N<= 1000)
PCOUNT.INP
PCOUNT.OUT
4
5
Kết quả: Ghi ra file PCOUNT.OUT gồm một dòng chứa số các đường đi khác nhau đếm được.
Ví dụ
Thuật toán:
Ta dễ thấy rằng: tổng các đường đi từ 2 đỉnh bất kì là tổng các đường đi có độ dài bằng 1, các đường đi có độ dài bằng 2, các đường đi có độ dài bằng 3, , các đường đi có độ dài bằng n-1. Cũng chính là tổng các đường đi không đi qua đỉnh trung gian nào, đi qua 1 đỉnh trung gian, qua 2 đỉnh trung gian, , qua n-2 đỉnh trung gian.
Tổng các đường đi không đi qua đỉnh trung gian nào là 1 (chính là đường nối trực tiếp 2 đỉnh đó). Tổng các đường đi đi qua 1 đỉnh trung gian là số cách chọn có thứ tự 1 đỉnh trong số n-2 đỉnh còn lại (A1n-2), tổng các đường đi đi qua 2 đỉnh trung gian là số cách chọn có thứ tự 2 đỉnh trong số n-2 đỉnh còn lại (A2n-2), tổng các đường đi qua 3 đỉnh trung gian là số cách chọn có thứ tự 3 đỉnh trên n-2 đỉnh còn lại (A3n-2), , tổng các đường đi qua n-2 đỉnh trung gian là số cách chọn có thứ tự n-2 đỉnh trên n-2 đỉnh còn lại (An-2n-2).
Như vậy:
S = 1+ A1n-2 + A2n-2 + A3n-2 +  + An-2n-2 (1)
(1) = 1+ (n-2) + (n-2)(n-3) + (n-2)(n-3)(n-4)+  + (n-2)! (2)
(2) = 1+ (n-2)[1+ (n-3)[1+(n-4)[[1+1]]]] (3)
(3) = (((1+1)2+1)3+1)4+1)5+1)(n-3)+1)(n-2)+1 (4)
S:=1;
For i:=1 to n-2 do 
 Begin
 S:= S*i;
 S:=S+1;
 End;
Như vậy từ công thức (4) ta có thuật toán theo đoạn mã sau:
Cấu trúc dữ liệu:
Qua công thức trên ta thấy S là một số rất lớn (với N = 1000 thì S có tới 2563 chữ số), không có kiểu số nào có thể lưu trữ được, ta phải sử dụng kiểu dữ liệu khác. Tốt nhất trong trường hợp này ta nên sử dụng mảng kiểu longint, với mỗi phần tử mảng sẽ lưu 1 số có 6 chữ số của chữ số S.
Để đơn giản trong xử lý ta nên lưu ngược, a[1] sẽ chứa 6 chữ số cuối cùng của S, a[2] sẽ chứa 6 chữ số tiếp theo, 
Ví dụ: S = 1234031809283756
Ta có mảng A như sau: a[1] = 283756; a[2] = 031809; a[3] = 001234. Nhưng thực tế a[2] = 31809; a[3] = 1234 (loại bỏ các số 0 ở đầu trái), vậy khi ghi kết quả ra file ta phải xử lý thêm chỗ này để đạt được kết quả đúng (thêm 0 vào trước cho đủ 6 chữ số rồi mới ghi ra file kết quả). 
Chương trình
Const
 stout='PCOUNT.OUT';
 stinp='PCOUNT.INP';
 k=1000000; d=6;
Var i,j,n,m,l,nho:longint;
 s:string; f:text; ok:boolean;
 a:array[1..500] of longint;{mang chua day so}
procedure Khoi_tao;
Begin
 assign(f,stinp); reset(f);
 read(f,n); close(f);
 a[1]:=1; m:=1; {m là số phần tử của mảng a}
end;
{===========================}
Procedure Thuc_hien;
Begin
 For i:=1 to n-2 do
 Begin
 nho:=0; {Nhân số lớn a với số i, i<1000}
 For j:=1 to m do
 Begin
 nho:=nho+a[j]*i;
 a[j]:=nho mod k;
 nho:=nho div k;
 End;
 if nho>0 then Begin m:=m+1; a[m]:=nho; End;
 {Cộng số lớn a với 1}
 nho:=1;ok:=true; j:=0;
 while ok do
 begin
 j:=j+1;
 nho:=a[j]+nho;
 a[j]:=nho mod k;
 nho:=nho div k;
 if nho=0 then ok:=false;
 end;
 if j>m then m:=j;
 End;
End;
Procedure In_ra;
Begin
 Assign(f,stout); Rewrite(f);
 if n>1 then
 Begin
 str(a[m],s); write(f,s);
 For i:=m-1 downto 1 do
 Begin
 str(a[i],s);
 if i6 then
 Begin
 l:=length(s);
 while l6 do Begin insert('0',s,1); l:=l+1; End;
 End;
 write(f,s);
 End;
 End
 else Write(f,'0');
 close(f);
End;
BEGIN
 Khoi_tao;
 Thuc_hien;
 In_ra;
END.
2.4. Bài toán 4 (Đề thi OLP 2004)
STT
Xâu
1
2
3
4
5
6
7