//
you're reading...
00 - Chủ đề chung

Đề tài số nguyên lớn

PHẦN I. ĐẶT VẤN ĐỀ

  1. Lý do chọn đề tài

Trong quá trình đào tạo bồi dưỡng học sinh giỏi ở trường phổ thông, chúng tôi nhận thấy khả năng số học đối với số nguyên lớn của ngôn ngữ lập trình Free Pascal khi biểu diễn các số nguyên có hàng chục nghìn chữ số đến hàng trăm nghìn chữ số gây rất nhiều khó khăn cho học sinh. Nhằm khắc phục nhược điểm trên và để đáp ứng được yêu cầu của công tác bồi dưỡng học sinh giỏi của thầy và trò trường trung học phổ thông Vinh Xuân, chúng tôi mạnh dạn nghiên cứu đề tài “KĨ THUẬT LẬP TRÌNH ĐỐI VỚI SỐ NGUYÊN LỚN TRONG CÔNG TÁC BỒI DƯỠNG HỌC SINH GIỎI TẠI TRƯỜNG TRUNG HỌC PHỔ THÔNG VINH XUÂN” nhằm phục vụ công tác bồi dưỡng học sinh giỏi có hiệu quả hơn.

  1. Mục đích nghiên cứu

– Hệ thống hóa cơ sở lý thuyết về lập trình đối với số nguyên lớn.

– Xây dựng bộ công cụ lập trình đối với số nguyên lớn nhằm hỗ trợ cho hoạt động dạy và học của thầy và trò của nhà trường trong quá trình tiếp xúc và làm việc với số nguyên lớn.

– Trên cơ sở nghiên cứu, từ đó đưa ra nhận xét, đánh giá và đề xuất giải pháp góp phần hoàn thiện công tác dạy và học lập trình đối với các bài toán mà dữ liệu vào hay kết quả ra có giá trị nguyên dương rất lớn.

  1. Đối tượng nghiên cứu

Kỹ thuật lập trình đối với số nguyên lớn trong công tác dạy và học bồi dưỡng của thầy và trò tại trường THPT Vinh Xuân.

  1. Phạm vi nghiên cứu

Tập hợp số nguyên dương lớn và hệ thống bài tập có dữ liệu vào hay kết quả ra là kiểu số nguyên dương có giá trị rất lớn.

  1. Phương pháp nghiên cứu

– Phương pháp nghiên cứu cơ sở lý luận

– Phương pháp thu thập tài liệu

– Phương pháp xử lý số liệu và lập trình

– Phương pháp thực nghiệm

– Phương pháp điều tra phát vấn

  1. Kết cấu đề tài

Phần I. Đặt vấn đề

Phần II. Nội dung và kết quả nghiên cứu

Chương 1. Cơ sở lý luận về lập trình số nguyên lớn

Chương 2. Giải pháp cho một số bài toán số nguyên lớn

Phần III. Kết luận


PHẦN II. NỘI DUNG VÀ KẾT QUẢ NGHIÊN CỨU

Chương 1. CƠ SỞ LÝ LUẬN VỀ LẬP TRÌNH VỀ SỐ NGUYÊN LỚN

1.1. TỔ CHỨC KIỂU DỮ LIỆU MẢNG MỘT CHIỀU BIỂU DIỄN SỐ NGUYÊN LỚN.

Trong thực tế có những bài toán số học có giá trị lớn từ hàng chục nghìn đến hàng trăm nghìn chữ số, nhưng khả năng biểu diễn và lưu trữ của các kiểu dữ liệu chuẩn trong Free Pascal là hữu hạn nên không thể đáp ứng những bài toán số học có giá trị lớn. Từ đó chúng tôi xây dựng mảng một chiều có 1.000.001 phần tử, mỗi phần tử biểu diễn một hay một số chữ số của số nguyên lớn.

Trong phần lý thuyết, chúng tôi khai báo mảng một chiều mỗi phần tử biểu diễn một chữ số của số nguyên lớn, được khai báo như sau:

Const Hang_so = 1000000;

                  Type   Big_Number = Array[0..Hang_so] of Longint;

                  Var     A: Big_Number;

trong đó:

+ Chữ số hàng đơn vị của số nguyên lớn được biểu diễn bởi phần tử A[1.000.000]

+ Chữ số hàng chục của số nguyên lớn được biểu diễn bởi phần tử A[999.999]

+ ………..

+ Chữ số hàng cao nhất của số nguyên lớn được biểu diễn bởi phần tử A[i] và giá trị i được quản lý bởi giá trị của phần tử A[0].

Với số nguyên lớn A = 876328 được biểu diễn trên các phần tử mảng và quản lý giá trị A[0] như sau:

A 999.995 0 0 0 0 8 7 6 3 2 8
  0 1 2 3 …….. 999.995 999.996 999.997 999.998 999.999 1.000.000

Với A := 0 được viết:

Fillchar(A, Sizeof(A),0); A[0]:= Hang_So;

Với A := 1 được viết:

Fillchar(A,Sizeof(A),0);

A[0]:= Hang_So; A[Hang_so]:=1;

Trên cơ sở biểu diễn số nguyên lớn như vậy, chúng tôi xây dựng các phép toán trên tập hợp số nguyên dương lớn như phép toán quan hệ, phép toán cộng, phép trừ, phép nhân, phép chia lấy phần nguyên (Div), phép chia lấy phần dư (Mod) và ứng dụng các phép toán đó để giải quyết một số bài toán trong công tác bồi dưỡng học sinh giỏi.

1.2. PHÉP TOÁN QUAN HỆ

1.2.1. Phép toán so sánh bằng

* Thuật toán: Hai số nguyên dương lớn A B kiểu Big_number được biểu diễn bằng mảng một chiều, mỗi phần tử mảng biểu diễn một chữ số của số nguyên lớn. Ta dựa vào các giá trị A0, B0, Ai với A0 ≤ i ≤ Hang_so và Bk với B0 ≤ k ≤ Hang_so để thực hiện so sánh và trả về giá trị True hoặc False.

      Function Bằng(A,B:Big_number): Boolean

Begin

Nếu A0 <> B0 thì Bằng:=false

Ngược lại

{ + i:= A0; Trong khi (i ≤ Hang_so) và (Ai = Bi) làm i:= i+1;

+ Bằng:= i > Hang_so;}

End;

* Chương trình

Function Bang(A,B:Big_Number):Boolean;

Var     I:Longint;

Begin

If A[0]<>B[0] Then Bang:=False

Else  Begin

I:=A[0]; While (I<=Hang_So) And (A[I]=B[I]) Do I:=I+1;

Bang:=I>Hang_So;

End;

End;

1.2.2. Phép toán so sánh lớn hơn

* Thuật toán: So sánh hai số A, B: Big_Number; nếu A lớn hơn B thì trả về kết quả True nếu không thì trả về giá trị False.


      Function Lớn_hơn(A,B:Big_number):Boolean

Begin

Nếu A0 < B0 thì Lớn_hơn:= true

Ngược lại

Nếu A0 > B0 thì Lớn_hơn:= false

Ngược lại

{ + i:= A0;

+ Trong khi (i<=Hang_so) và (Ai = Bi) làm i:= i+1;

+ Nếu i > Hang_so thì Lớn_hơn:= False

ngược lại i:= Ai > Bi}

End;

* Chương trình

Function Lon_Hon(A,B:Big_Number):Boolean;

Var     I:Longint;

Begin

If A[0]<B[0] Then Lon_Hon:=True

Else If A[0]>B[0] Then Lon_Hon:=False

Else Begin

I:=A[0]; While (I<=Hang_So) And (A[I]=B[I]) Do I:=I+1;

If I>Hang_So Then Lon_Hon:=False

Else Lon_Hon:=A[I]>B[I];

End;

End;

1.2.3. Phép toán so sánh nhỏ hơn

* Thuật toán: So sánh hai số A, B: Big_Number; nếu A nhỏ hơn B thì trả về kết quả True nếu không thì trả về giá trị False.

      Function Nhỏ_hơn(A,B:Big_number):Boolean

Begin

* Nếu A0 < B0 thì Lớn_hơn:= False

Ngược lại

– Nếu A0 > B0 thì Lớn_hơn:= True

Ngược lại

{ + i:= A0;

+ Trong khi (i<=Hang_so) và (Ai = Bi) làm i:= i+1;

+ Nếu i > Hang_so thì Lớn_hơn:= False

ngược lại i:= Ai<Bi}

End;

* Chương trình

Function Nho_Hon(A,B:Big_Number):Boolean;

Var     I: Longint;

Begin

If A[0]<B[0] Then Nho_Hon:=False

Else If A[0]>B[0] Then Nho_Hon:=True

Else Begin

I:=A[0];  While (I<=Hang_So) And (A[I]=B[I]) Do I:=I+1;

If I>Hang_So Then Nho_Hon:=False

Else Nho_Hon:=A[I]<B[I];

End;

End;

1.3. PHÉP TOÁN SỐ HỌC

1.3.1. Phép cộng

1.3.1.1. Cộng số nguyên lớn với số nguyên nhỏ

* Thuật toán: Thực hiện cộng một số nguyên lớn A kiểu Big_number với một số nguyên nhỏ k kiểu dữ liệu chuẩn như Integer, Word hay Longint như sau:

Procedure Cong_min(Var C:Big_number; A:Big_number; k:Longint);

Begin

– Fillchar(C,sizeof(C),0);

– Cho i:= Hang_so về A0 làm {k:= k+Ai; Ci:= k Mod 10; k:= k Div 10;}

– Trong khi (k >0) làm {i:= i-1; Ci:= k Mod 10; k:= k Div 10}

– C0:= i

End;


* Chương trình

Procedure Cong_Min(Var C:Big_Number; A:Big_Number; k:Longint);

Var     I: Longint;

Begin

Fillchar(C,Sizeof(C),0);

For I:=Hang_So Downto A[0] Do

Begin  K:=K+A[I]; C[I]:=K Mod 10; K:= K Div 10; End;

While K>0 Do Begin I:=I-1;C[I]:=K Mod 10;K:=K Div 10; End;

C[0]:=I;

End;

1.3.1.2. Cộng hai số nguyên lớn

* Thuật toán: Phép cộng hai số nguyên dương lớn được thực hiện từ phải sang trái và phần nhớ được mang sang trái một chữ số.

Procedure Cong_Max(Var C:Big_Number;A,B:Big_Number);

Begin

Fillchar(C,sizeof(C),0); Tg:= 0;

Cho i:= Hang_so về Min(A0, B0) làm

{Tg:= Tg + Ai + Bi; Ci:= Tg Mod 10; Tg:= Tg Div 10}

Nếu Tg = 0 thì C0:= i Ngược lại {C0:= i -1; Ci-1:= Tg}

End;

* Chương trình

Procedure Cong_Max(Var C:Big_Number;A,B:Big_Number);

Var     I,Min,Tg:Longint;

Begin

Fillchar(C,Sizeof(C),0); Tg:=0;

If A[0]>=B[0] Then Min:=B[0] Else Min:=A[0];

For I:=Hang_So Downto Min Do

Begin Tg:=Tg+A[I]+B[I]; C[I]:=Tg Mod 10; Tg:=Tg Div 10; End;

If Tg=0 Then C[0]:= i Else  Begin C[0]:= i – 1; C[i -1]:=Tg; End;

End;

1.3.2. Phép trừ

1.3.2.1. Trừ số nguyên lớn với số nguyên nhỏ

* Thuật toán: Nếu A ≥ k thì C:= A – k nếu không thì C:= – (k – A).

Procedure Tru_Min(Var C:Big_Number; A:Big_Number; K:Longint);

Begin

Trường hợp A≥ k: C:= A – k

Fillchar(c,sizeof(C),0); Tg:= 0

Trong khi (k>0) và (i≥ A0) làm

{+ Tg:= k Mod 10; k := k Div 10;

+ Nếu Ai ≥ Tg thì Ci:= Ai – Tg

Ngược lại   {Ci:= Ai +10 – Tg; k:= k+1;}

+ I:= i + 1}

Trong khi I ≥ A0 làm {Ci:=Ai; i:= i – 1}

i:=A0; Trong khi (i<Hang_So) và (Ci=0) làm i:=i+1;

C0:=i;

Trường hợp A < k: C:= -(k – A)

                              k:= k – Ai * 10Hang_so – i với A0 ≤ i ≤ Hang_so

Biểu diễn giá trị k vào mảng C kiểu Big_number;

C[c0]:= – C[c0]

End;

* Chương trình

Procedure Tru_Min(Var C:Big_Number;A:Big_Number;K:Longint);

Var     I,M,Tg,Lt: Longint;

Begin

Fillchar(C,Sizeof(C),0); C[0]:=Hang_So; Tg:=0; I:=Hang_So; M:=K;

While (K>0) And (I>=A[0]) Do

Begin

Tg:=K Mod 10; K:=K Div 10;

If A[I]>=Tg Then C[I]:=A[I]-Tg

Else Begin C[I]:=A[I]+10-Tg; K:=K+1; End;

I:=I-1;

End;

If K=0 Then

Begin

While I>=A[0] Do Begin C[I]:=A[I]; I:=I-1; End;

I:=A[0]; While (I<Hang_So)And(C[I]=0)Do I:=I+1;

C[0]:=I;

End

Else

Begin

I:=Hang_So; Lt:= 1;

While I>=A[0] Do

Begin M:=M-A[I]*Lt; Lt:=Lt*10; I:=I-1; End;

Fillchar(C,Sizeof(C),0); I:=Hang_So;

While M>0 Do

Begin C[I]:=M Mod 10; M:=M Div 10; I:=I-1; End;

C[0]:=I+1; C[C[0]]:=-C[C[0]];

End;

End;

1.3.2.2. Trừ hai số nguyên lớn

* Thuật toán: Thực hiện trừ từng chữ số từ trái sang phải và giá trị vay mượn 1 ở hàng cao hơn được nhớ bằng biến Tg làm cơ sở cho phép trừ kế tiếp ở hàng cao hơn; xét cả hai trường hợp A ≥ B và A < B:

Nếu A ≥ B thì C:= A – B nếu không thì C:= – (B – A).

Procedure Tru_Min(Var C: Big_Number; A,B: Big_Number);

Begin

Fillchar(C,sizeof(C),0); Ok:= A ≥ B;

Nếu Ok thì

{          Tg:= 0;

Cho i:= Hang_so về A0 làm

Nếu Ai ≥ Tg + Bi thì {Ci:= Ai – Bi – Tg; Tg:= 0;}

Ngược lại {Ci:= Ai + 10 – Bi – Tg; Tg:= 1;}

Trong khi (i< Hang_so) và (Ci = 0) làm i:= i+1;

C0:= i;}

Ngược lại

{          Tg:= 0;

Cho i:= Hang_so về B0 làm

Nếu Bi ≥ Tg + Ai thì {Ci:= Bi – Ai – Tg; Tg:= 0;}

Ngược lại {Ci:= Bi + 10 – Ci – Tg; Tg:= 1;}

Trong khi (i< Hang_so) và (Ci = 0) làm i:= i+1;

C0:= i; Ci:= 1 – Ci}

End;

* Chương trình

Procedure Tru_Max(Var C:Big_Number;A,B:Big_Number);

Var     I,Tg:Longint; Ok:Boolean;

Begin

Fillchar(C,Sizeof(C),0);

If A[0]<B[0] Then Ok:=True

Else If A[0]>B[0] Then Ok:=False

Else Begin

I:=A[0];While (I<=Hang_So) And (A[I]=B[I]) Do I:=I+1;

If I>Hang_So Then Ok:=False Else Ok:=A[I]>B[I];

End;

If Ok Then

Begin

Tg:=0;

For I:=Hang_So Downto A[0] Do

If A[I]>=B[I]+Tg Then

Begin C[I]:=A[I]-B[I]-Tg;  Tg:=0 End

Else Begin C[I]:=A[I]+10 – B[I] – Tg; Tg:=1; End;

While (I<Hang_So)And(C[I]=0) Do I:=I+1;

C[0]:=I;

End

Else Begin

Tg:=0;

For I:=Hang_So Downto B[0] Do

If B[I]>=A[I]+Tg Then

Begin C[I]:=B[I]-A[I]-Tg; Tg:=0; End

Else Begin C[I]:=B[I]+10-A[I]-Tg; Tg:=1 End;

While (I<Hang_So)And(C[I]=0) Do I:=I+1;

C[I]:=-C[I];C[0]:=I;

End;

End;

1.3.3. Phép nhân

1.3.3.1. Nhân số nguyên lớn với số nguyên nhỏ

* Thuật toán: thực hiện nhân từ phải sang trái từng chữ số Ai với số k sau đó lấy hàng đơn vị của tích trả về cho Ci còn phần bội số của 10 (sau khi bỏ đi chữ số hàng đơn vị của tích số) được cộng vào tích của phép nhân sau.

Procedure Nhan_Min(Var C:Big_Number;A:Big_Number;K:Longint);

Begin

Fillchar(C,Sizeof(C),0); Tg:=0;

Cho i:=Hang_So về A0 làm

{Tg:= Tg+Ai * k; Ci:= Tg Mod 10; Tg:= Tg Div 10;}

Trong khi Tg>0 làm   {i:= i – 1; Ci:= Tg Mod 10; Tg:= Tg Div 10;}

C0:=i;

End;

* Chương trình

Procedure Nhan_Min(Var C:Big_Number;A:Big_Number;K:Longint);

Var     I, Tg,Schia,Min:Longint;

Begin

Fillchar(C,Sizeof(C),0);Tg:=0;

For I:=Hang_So Downto A[0] Do

Begin Tg:=Tg+A[I]*K; C[I]:=Tg Mod 10; Tg:=Tg Div 10; End;

While Tg>0 Do Begin I:=I-1; C[I]:=Tg Mod 10; Tg:=Tg Div 10; End;

C[0]:=I;

End;

1.3.3.2. Nhân hai số nguyên lớn

* Thuật toán: Thực hiện nhân từ phải sang trái các chữ số Ai với số nguyên lớn B được tích bằng D; ứng với mỗi giá trị D được cộng dồn vào cho C và kết thúc khi i = A0; suy ra được kết quả bằng số nguyên lớn C.

Procedure Nhan_Max(Var C:Big_Number;A,B:Big_Number);

Begin

C:=0;

Cho i:= Hang_so về A0 làm {D:= Ai * B* 10Hang_so – i; C:= C + D;}

End;

* Chương trình

Procedure Nhan_Max(Var C:Big_Number;A,B:Big_Number);

Var     I,J,U,Tg: Longint; D: Big_Number;

Begin

Fillchar(C,Sizeof(C),0);C[0]:=Hang_So;U:=0;

For I:=Hang_So Downto A[0] Do

Begin

Fillchar(D,Sizeof(D),0); Tg:=0;

For J:=Hang_So Downto B[0] Do

Begin  Tg:=Tg+A[I]*B[J];

D[J-U]:=Tg Mod 10; Tg:=Tg Div 10;

End;

If Tg=0 Then D[0]:=J-U

Else   Begin D[J-U-1]:=Tg; D[0]:=J-U-1; End;

U:=U+1; Tg:=0;

For J:=Hang_So Downto D[0] Do

Begin      Tg:=Tg+C[J]+D[J];

C[J]:=Tg Mod 10;  Tg:=Tg Div 10;

End;

If Tg=0 Then C[0]:= D[0]

Else  Begin C[J-1]:=Tg;  C[0]:=J-1;  End;

End;

End;

1.3.4. Phép chia

1.3.4.1. Chia lấy phần nguyên

1.3.4.1.1. Số nguyên lớn chia số nguyên nhỏ

* Thuật toán: Thực hiện từ trái sang phải, lấy các giá trị Ai chia k lấy phần nguyên trả về cho Ci và phần dư nhân 10 cộng với Ai+1 để xác định giá trị Ci+1; sau đó xác định giá trị Ci khác không đầu tiên tính từ trái sang và cho C0 bằng i.

Procedure Div_Min(Var C:Big_Number;A:Big_Number;K:Longint);

Begin

C:= 0; Tg:= 0;

Cho A0 đến Hang_so làm

{Tg:=10*Tg+Ai; Ci:= Tg Div 10; Tg:= Tg Mod 10}

i:=A0; Trong khi (i<Hang_so) và (Ci=0) làm i:=i+1;

C0:=i;

End;

* Chương trình

Procedure Div_Min(Var C:Big_Number;A:Big_Number;K:Longint);

Var     I,Tg:Longint;

Begin

Fillchar(C,Sizeof(C),0);C[0]:=Hang_So;Tg:=0;

For I:=A[0] To Hang_So Do

Begin Tg:=10*Tg+A[I]; C[I]:=Tg Div K; Tg:=Tg Mod K; End;

I:=A[0]; While (I<Hang_So)And(C[I]=0)Do I:=I+1;

C[0]:=I;

End;

1.3.4.1.2. Số nguyên lớn chia số nguyên lớn

* Thuật toán:

Procedure Div_Max(Var C:Big_Number;A,B:Big_Number);

Begin

C:=0;

Schia:=BB0 BB0+1 ….. BB0+i lấy tối đa 7 chữ số đầu của số nguyên lớn B  làm số chia thay cho B; với mọi 0 ≤ i ≤ 6 và không nhất thiết bằng 6 mà phụ thuộc vào số chữ số của B.

U:=Hang_So–BB0 + i {là số chữ số còn lại của B sau khi tách lấy Schia}

Nếu U>0 thì Schia:= Schia + 1;

Repeat

Ok:= A bỏ đi U chữ số cuối cùng < Schia;

Nếu Ok = False thì

{          D:= A Div Schia;

C:= C + D;

E:= B * D;

A:= A – E; }

Until Ok;

Nếu A ≥ B thì C:= C + 1;

End;

* Chương trình

Procedure Div_Max(Var C:Big_Number;A,B:Big_Number);

Var     I,J,Min,U,V,Schia,Tg:Longint;  Ok:Boolean;

Begin

Fillchar(C,Sizeof(C),0);C[0]:=Hang_So; I:=B[0]; Schia:=B[I];

While (I<Hang_So)And(Schia<10000000)Do

Begin  I:=I+1; Schia:=Schia*10+B[I]; End;

U:=Hang_So-I;

If U>0 Then Schia:=Schia+1;

Repeat

Tg:=0;

If A[0]<B[0] Then Ok:=False

Else If A[0]>B[0] Then Ok:=True

Else Begin

I:=A[0];Tg:=A[I];

While I<Hang_So-U Do

Begin I:=I+1; Tg:=Tg*10+A[I];End;

Ok:=(Tg<Schia)

End;

If Ok=False Then

Begin

 {D:=A Div Schia} Fillchar(D,Sizeof(D),0);D[0]:=Hang_So; Tg:=0;

For I:=A[0] To Hang_So-U Do

Begin

Tg:=10*Tg+A[I];

D[I+U]:=Tg Div Schia; Tg:=Tg Mod Schia;

End;

I:=A[0]+U;  While (I<Hang_So)And(D[I]=0) Do I:=I+1;

D[0]:=I;

             {C:=C+D} Tg:=0;

If C[0]<D[0] Then Min:=C[0] Else Min:=D[0];

For I:=Hang_So Downto Min Do

Begin

Tg:=Tg+C[I]+D[I];

C[I]:=Tg Mod 10; Tg:=Tg Div 10;

End;

If Tg>0 Then C[Min-1]:=Tg;

I:=Min-1; While (I<Hang_So)And(C[I]=0) Do I:=I+1;C[0]:=I;

{E:=B*D} Fillchar(E,Sizeof(E),0);E[0]:=Hang_So;V:=0;

For I:=Hang_So Downto D[0] Do

Begin

Fillchar(K,Sizeof(K),0); Tg:=0;

For J:=Hang_So Downto B[0] Do

Begin

Tg:=Tg+D[I]*B[J];

K[J-V]:=Tg Mod 10; Tg:=Tg Div 10;

End;

If Tg=0 Then K[0]:=J-V

Else  Begin K[0]:=J-V-1; K[K[0]]:=Tg; End;

V:=V+1;Tg:=0;

If E[0]<K[0] Then Min:=E[0] Else Min:=K[0];

For J:=Hang_So Downto Min Do

Begin  Tg:=Tg+K[J]+E[J];

E[J]:=Tg Mod 10; Tg:=Tg Div 10;

End;

If Tg=0 Then E[0]:=Min

Else Begin  E[Min-1]:=Tg;  E[0]:=Min-1; End;

End;

              {A:=A-E} Tg:=0;

For I:=Hang_So Downto A[0] Do

If A[I]>=E[I]+Tg Then  Begin A[I]:=A[I]-E[I]-Tg; Tg:=0; End

Else  Begin A[I]:=A[I]+10-E[I]-Tg; Tg:=1; End;

While (I<Hang_So)And(A[I]=0) Do I:=I+1; A[0]:=I;

End;

Until Ok;

If A[0]<B[0] Then Ok:=True

Else If A[0]>B[0] Then Ok:=False

Else  Begin

I:=A[0]; While (I<=Hang_So) And (A[I]=B[I]) Do I:=I+1;

If I>Hang_So Then Ok:=True Else Ok:=A[I]>=B[I];

End;

If Ok Then

Begin

Tg:=1;

For I:= Hang_So Downto C[0] Do

Begin Tg:=Tg+C[I];  C[I]:=Tg Mod 10; Tg:=Tg Div 10; End;

If Tg >0 Then Begin C[0]:= C[0]-1; C[C[0]]:=Tg; End;

End;

End;

1.3.4.2. Chia lấy phần dư (Mod)

1.3.4.2.1. Số nguyên lớn chia số nguyên nhỏ

* Thuật toán: Thực hiện trừ trái sang phải, lấy các giá trị Ai chia cho giá trị k phần dư nhân 10 cộng với Ai+1 rồi chia k cho đến khi kết thúc ta thu được phần dư cần tìm.

Procedure Mod_Min(Var C:longint;A:Big_Number;K:Longint);

Begin

C:=0;  Cho i:= A0 đến Hang_so làm {C:=(10*C+Ai) Mod k;

End;

* Chương trình

Procedure Mod_Min(Var C:longint;A:Big_Number;K:Longint);

Var     I, Tg: Longint;

Begin

C:=0; For I:=A[0] To Hang_So Do C:= (10*C + Ai) Mod k

End;

1.3.4.2.2. Số nguyên lớn chia số nguyên lớn

* Thuật toán:  Tương tự phép chia lấy phần nguyên giữa hai số nguyên lớn nhưng lấy giá trả về là số dư của phép chia A Mod B.

* Chương trình

Procedure Mod_Max(Var C:Big_Number;A,B:Big_Number);

Var     I,J,Min,U,V,Schia,Tg:Longint; Ok:Boolean;

Begin

Fillchar(C,Sizeof(C),0);C[0]:=Hang_So; I:=B[0];Schia:=B[I];

While (I<Hang_So)And(Schia<10000000)Do

Begin I :=I+1; Schia:=Schia*10+B[I]; End;

U:=Hang_So-I;

If U>0 Then Schia:=Schia+1;

Repeat

Tg:=0;

If A[0]<B[0] Then Ok:=False

Else  If A[0]>B[0] Then Ok:=True

Else Begin

I:=A[0];Tg:=A[I];

While I<Hang_So-U Do

Begin I:=I+1;Tg:=Tg*10+A[I]; End;

Ok:=(Tg<Schia)

End;

If Ok=False Then

Begin

       {D:=A Div B} Fillchar(D,Sizeof(D),0);D[0]:=Hang_So; Tg:=0;

For I:=A[0] To Hang_So-U Do

Begin

Tg:=10*Tg+A[I]; D[I+U]:=Tg Div Schia;

Tg:=Tg Mod Schia;

End;

I:=A[0]+U;

While (I<Hang_So)And(D[I]=0) Do I:=I+1;

D[0]:=I;

   {E:=B*D}  Fillchar(E,Sizeof(E),0);E[0]:=Hang_So;V:=0;

For I:=Hang_So Downto D[0] Do

Begin

Fillchar(K,Sizeof(K),0); Tg:=0;

For J:=Hang_So Downto B[0] Do

Begin

Tg:=Tg+D[I]*B[J];

K[J-V]:=Tg Mod 10; Tg:=Tg Div 10;

End;

If Tg=0 Then K[0]:=J-V

Else Begin K[0]:=J-V-1; K[K[0]]:=Tg; End;

V:=V+1;Tg:=0;

If E[0]<K[0] Then Min:=E[0]  Else Min:=K[0];

For J:=Hang_So Downto Min Do

Begin  Tg:=Tg+K[J]+E[J];

E[J]:=Tg Mod 10; Tg:=Tg Div 10;

End;

If Tg=0 Then E[0]:=Min

Else Begin E[Min-1]:=Tg; E[0]:=Min-1; End;

End;

             {A:=A-E} Tg:=0;

For I:=Hang_So Downto A[0] Do

If A[I]>=E[I]+Tg Then

Begin A[I]:=A[I]-E[I]-Tg; Tg:=0;End

Else       Begin A[I]:=A[I]+10-E[I]-Tg; Tg:=1;End;

While (I<Hang_So)And(A[I]=0) Do I:=I+1;

A[0]:=I;

End;

Until Ok;

If A[0]<B[0] Then Ok:=True

Else If A[0]>B[0] Then Ok:=False

Else Begin

I:=A[0]; While (I<=Hang_So) And (A[I]=B[I]) Do I:=I+1;

If I>Hang_So Then Ok:=True  Else Ok:=A[I]>=B[I];

End;

If Ok Then

Begin

Tg:=0;

For I:=Hang_So Downto A[0] Do

If A[I]>=B[I]+Tg Then  Begin A[I]:=A[I]-B[I]-Tg; Tg:=0; End

Else   Begin A[I]:=A[I]+10-B[I]-Tg; Tg:=1; End;

While (I<Hang_So)And(A[I]=0) Do I:=I+1;

A[0]:=I;

End;

For I:=A[0] To Hang_So Do C[I]:=A[I];  C[0]:=A[0];

End;

Lưu ý: Tùy thuộc vào giá trị của dữ liệu vào và kết quả ra của bài toán để chúng ta khai báo giá trị Hang_so phù hợp sẽ giảm thiểu bộ nhớ lưu trữ cho các biến không cần thiết giúp cho chương trình thực hiện nhanh hơn.

 

Chương II. GIẢI PHÁP CHO MỘT SỐ BÀI TOÁN SỐ NGUYÊN LỚN

2.1. TÍNH GIÁ TRỊ GIAI THỪA

  1. Đề bài:

Cho dãy số A1, A2, ……, AN là các số nguyên dương và Ai ≤ 20.000. Hãy tính các giá trị Ai! với mọi 1 ≤ i  ≤ N (biểu diễn chính xác đến hàng đơn vị).

* Dữ liệu vào: cho trong file văn bản Dulieu.INP có nhiều dòng mỗi dòng lưu một số nguyên dương (0 < Ai ≤ 20.000).

* Kết quả ra: ghi ra file văn bản Ketqua.OUT có nhiều dòng; dòng thứ i lưu các giá trị giai thừa tương ứng của Ai.

Ví dụ:

Dulieu.INP Ketqua.OUT
2

8

10

20

30

2

40320

3628800

2432902008176640000

265252859812191058636308480000000

  1. Cấu trúc dữ liệu và giải thuật

* Cấu trúc dữ liêu:

– Xây dựng mảng A: để lưu giá trị số nguyên lớn X!.

– Sử dụng thủ tục nhân một số nguyên lớn A với một số nguyên nhỏ k Nhan_Min(C,A,k) để tính giá trị của X!.

* Giải thuật

Trong khi Not Eof(f1) làm:

+Readln(f1, m);

+ A:=1;

+ Cho i:= 1 đến M làm Nhan_Min(A,A,m);

+ Write(f2, A);

  1. Chương trình: được lưu theo đường dẫn E:\Chuyen De\Tinh Giai Thua

Program GIAI_THUA;

Const        Hang_So = 1000000;

Type          Big_Number = Array[0..Hang_So] Of  Longint;

Var            A: Big_Number; I, M: Longint; F1, F2: Text;

{========================}

Procedure Nhan_Min(Var C: Big_Number; A: Big_Number; K: Longint);

Var     I, Tg: Longint;

Begin

Tg:= 0;

For I:= Hang_So Downto A[0] Do

Begin Tg:= Tg + A[I] * K; C[I]:= Tg Mod 10000; Tg:= Tg Div 10000; End;

While Tg>0 Do  Begin I:=I-1; C[I]:= Tg Mod 10000; Tg:= Tg Div 10000; End;

C[0]:= I;

End;

{========================}

Begin

Assign(F1, ‘E:\Chuyen De\Tinh Giai Thua\Dulieu.Inp’); Reset(F1);

Assign(F2, ‘E:\Chuyen De\Tinh Giai Thua\Ketqua.Out’); Rewrite(F2);

While Not Eof(F1) Do

Begin

Readln(F1,M); A[0]:=1000000; A[1000000]:=1;

For I:=1 To M Do Nhan_Min(A,A,I);

Write(F2, A[A[0]]);

For I:=A[0]+1 To Hang_So Do

If A[I]>=1000 Then Write(F2, A[I])

Else If A[I]>=100 Then Write(F2, ‘0’, A[I])

Else If A[I]>=10 Then Write(F2, ’00’, A[I])

Else Write(F2, ‘000’, A[I]);

Writeln(F2);

End;

Close(F1);  Close(F2);

End.

2.2. BÀI TOÁN BIÊN DỊCH

  1. Đề bài: (đề thi học sinh giỏi tỉnh Thừa Thiên Huế 2013)

Một nhà lập trình soạn một trình biên dịch quyết định phát triển một ánh xạ giữa mỗi từ có 20 kí tự với một số nguyên duy nhất. Việc lập ra bản đồ để biên dịch rất đơn giản  và được đánh dấu bởi từ abc… và sau đó theo thứ tự của từ đó. Một phần của danh sách được hiển thị dưới đây:

a                                    1

b                                    2

…                                  …

z                                    26

aa                                   27

ab                                  28

…                                  …

snowfall                        157.118.051.752

…                                  …

Yêu cầu: Viết một chương trình có thể dịch (hai chiều) giữa các số, từ duy nhất dựa theo bản đồ trên.

* Dữ liệu vào: cho trong file văn bản với tên là BIENDICH.INP trong đó có nhiều dòng. Đầu vào cho chương trình là các từ và các con số. Một số sẽ chỉ có các chữ số thập phân (0 đến 9, không có dấu chấm ở các số). Một từ sẽ bao gồm một đến hai mươi kí tự viết thường (a đến z).

* Dữ liệu ra: file văn bản với tên là BIENDICH.OUT có nhiều dòng.

Đầu ra có một dòng duy nhất cho mỗi từ hoặc số tương ứng với dữ liệu đầu vào. Trên mỗi dòng sẽ có hai cột , cột đầu tiên là các từ, cột thứ 2 là các số giữa hai cột cách nhau ít nhất một dấu cách. Các số có nhiều hơn ba chữ số phải được phân cách bằng dấu chấm tại hàng nghìn, hàng triệu, ….

Ví dụ:

BIENDICH.INP
29697684282993

transcendental

28011622636823854456520

computationally

zzzzzzzzzzzzzzzzzzzz

 

BIENDICH.OUT
elementary                                                                29.697.684.282.993

transcendental                                             51.346.529.199.396.181.750

prestidigitation                                    28.011.622.636.823.854.456.520

computationally                                      232.049.592.627.851.629.097

zzzzzzzzzzzzzzzzzzzz         20.725.274.851.017.785.518.433.805.270

  1. Cấu trúc dữ liệu và giải thuật

* Cấu trúc dữ liệu:

– Xây dựng mảng một chiều kiểu Big_Number để tổ chức lưu trữ số nguyên lớn của bài toán và được khai báo như ở phần lý thuyết.

– Xây dựng thủ tục Tru_1(Var A: Big_Number): A:= A – 1 được thực hiện khi A chia hết cho 26.

– Sử dụng các thủ tục sau:

+ Cong_Max(A,B,C): A:= B + C với A, B, C kiểu Big_Number.

+ Nhan_Min(A,B,k): A:= B * k với A, B kiểu Big_Number và k kiểu Longint.

+ Mod_Min(c,A,k): C:= A Mod k với A kiểu Big_Number và c, k kiểu Longint.

+ Div_Min(A,B,k): A:= B Div k với A, B kiểu Big_Number và k kiểu Longint.

* Giải thuật:

– Xây dựng thủ tục mã hóa để mã hóa một từ thành một số:

Procedure Ma_Hoa(St: một từ để biểu diễn thành số);

Begin

A0:= Hang_So – Length(St) + 1

AHang_So + i – Length(St) := Ord(Sti) – 96; với mọi i =1 .. Length(St)

B:=AHang­_So; C:=1;

For I:= Hang_So – 1 Downto A0 Do

Begin

Nhan_Min(C, C, 26);

Nhan_Min(D, C, Ai);

Cong_Max(B, B, D);

End;

Writeln(F2, St, B);

End;

– Xây dựng thủ tục giải mã để phân tích một số thành một từ:

Procedure Giai_Ma(St: Số để biểu diễn thành một từ);

Begin

A0:= Hang_So – Length(St) + 1;

AHang_So + i – Length(St) := Ord(Sti) – 48; với mọi i =1 .. Length(St)

B[0]:= Hang_So + 1;

Trong khi (A0<Hang_So) Or (AHang_So>0) làm:

+ B0:= B0 – 1;

+ Mod_Min(BB[0], A, 26);

+ Div_Min(A, A, 26);

+ If BB[0]=0 Then Tru_1(A);

S:= ”;

Cho i:= B0 đến Hang_So làm

Nếu Bi=0 Thì S:= S + ‘Z’ ngược lại S:= S + Chr(B[i]+96);

i:= Length(St) – 2;

Trong khi i >1 Làm

+ Insert(‘.’,St,i);

+ i:= i – 3;

Ghi file(F2, S:20, St:45);

End;

–  Chương trình chính

BEGIN

Trong khi Not Eof(F1) làm:

+ Readln(F1, St);

+ Nếu St1<=’9′ thì Giai_Ma(St) ngược lại Ma_Hoa(St);

END.

  1. Chương trình được lưu trong đường dẫn E:\Chuyen De\Bien Dich

Const Hang_So = 10000;

Type    Big_Number= Array[0..Hang_So] Of Longint;

Var  St: String;  F1, F2: Text;

{========== A:= B + C ==========}

Procedure Cong_Max(Var A: Big_Number; B, C: Big_Number);

Var     I, Min, Tg: Longint;

Begin

Fillchar(A,Sizeof(A),0);

For I:=1 To B[0]-1 Do B[I]:= 0;

For I:=1 To C[0]-1 Do C[I]:= 0;

If C[0]>=B[0] Then Min:=B[0] Else Min:=C[0];

Tg:=0;

For I:=Hang_So Downto Min Do

Begin Tg:= Tg + C[I] + B[I]; A[I]:= Tg Mod 10; Tg:= Tg Div 10; End;

If Tg = 0 Then A[0]:= Min

Else   Begin  A[0]:= Min-1;  A[Min-1]:= Tg;  End;

End;

{========== A:= B * k ===========}

Procedure Nhan_Min(Var A: Big_Number; B: Big_Number; k: Longint);

Var     I, Tg: Longint;

Begin

Fillchar(A,Sizeof(A),0); Tg:=0;

For I:=Hang_So Downto B[0] Do

Begin Tg:= Tg + B[I] * K; A[I]:= Tg Mod 10; Tg:= Tg Div 10;  End;

While Tg>0 Do Begin I:= I-1; A[I]:=Tg Mod 10; Tg:= Tg Div 10; End;

A[0]:= I;

End;

{==========C:= A Div K ===========}

Procedure Div_Min(Var C: Big_Number; A:Big_Number; K: Longint);

Var     I,Tg: Longint;

Begin

Fillchar(C,Sizeof(C),0); C[0]:= Hang_So; Tg:= 0;

For I:= A[0] To Hang_So Do

Begin  Tg:= 10 * Tg + A[I];  C[I]:= Tg Div K; Tg:= Tg Mod K;  End;

I:= A[0]; While (I<Hang_So) And (C[I]=0) Do I:= I + 1;

C[0]:= I;

End;

{========== C:= A Mod K ===========}

Procedure Mod_Min(Var C:Longint; A:Big_Number; K:Longint);

Var     I, Tg: Longint;

Begin

Tg:= 0;

For I:= A[0] To Hang_So Do  Begin Tg:= 10 * Tg + A[I]; Tg:= Tg Mod K; End;

C:= Tg;

End;

{============ A:= A – 1 ============}

Procedure Tru_1(Var A: Big_Number);

Var     I: Longint;

Begin

If A[Hang_So]>0 Then A[Hang_So]:= A[Hang_So] – 1

Else Begin

I:= Hang_So;

While (I>A[0]) And (A[I]=0) Do Begin A[I]:= 9; I:= I – 1 End;

A[I]:= A[I] – 1;

If A[A[0]]=0 Then A[0]:= A[0] + 1;

End;

End;

{========================}

Procedure Ma_Hoa(St: String);

Var     I: Longint; A, B, C, D: Big_Number;

Begin

Fillchar(A,Sizeof(A),0); A[0]:= Hang_So – Length(St) + 1;

For I:=Length(St) Downto 1 Do A[Hang_So+I-Length(St)]:= Ord(St[I]) – 96;

B[Hang_So]:= A[Hang_So] Mod 10;

B[Hang_So-1]:= (A[Hang_So] Div 10) Mod 10;

If A[Hang_So]>9 Then B[0]:= Hang_So – 1 Else B[0]:= Hang_So;

C[0]:= Hang_So; C[Hang_So]:= 1;

For I:= Hang_So – 1 Downto A[0] Do

Begin

Nhan_Min(C,C,26);

Nhan_Min(D,C,A[I]);

Cong_Max(B,B,D);

End;

S:= Chr(B[Hang_So] + 48);

For I:= Hang_So – 1 Downto B[0] Do

If (Hang_So – I) Mod 3 <> 0 Then S:= Chr(B[I]+48) + S

Else S:=Chr(B[I]+48) + ‘.’ + S;

Writeln(F2, St:20, S:45);

End;

{========================}

Procedure Giai_Ma(St: String);

Var     I, J: Longint; A, B: Big_Number;

Begin

A[0]:= Hang_So – Length(St) + 1;

For I:= Length(St) Downto 1 Do

A[Hang_So + I – Length(St)]:=Ord(St[I]) – 48;

B[0]:= Hang_So + 1;

While (A[0]<Hang_So) Or (A[Hang_So]>0) Do

Begin

B[0]:= B[0] – 1;

Mod_Min(B[B[0]], A, 26);

Div_Min(A, A, 26);

If B[B[0]]=0 Then Tru_1(A);

End;

S:= ”;

For I:= B[0] To Hang_So Do

If B[I]=0 Then S:= S + ‘Z’

Else S:= S + Chr(B[I]+96);

I:= Length(St) – 2;

While I>1 Do Begin  Insert(‘.’,St,I); I:= I-3;  End;

Writeln(F2, S:20, St:45);

End;

{========================}

Begin

Assign(F1, ‘E:\Chuyen De\Bien Dich\Bien Dich.Inp’); Reset(F1);

Assign(F2, ‘E:\Chuyen De\Bien Dich\Bien Dich.Out’); Rewrite(F2);

While Not Eof(F1) Do

Begin

Readln(F1, St);

If St[1]<=’9′ Then Giai_Ma(St) Else Ma_Hoa(St);

End;

Close(F1);

Close(F2);

End.

2.3. BÀI TOÁN BỘI CHUNG NHỎ NHẤT

  1. Đề bài

Cho dãy số A1, A2, ….., AN là các số nguyên dương (N ≤ 100; Ai ≤ 109). Tìm bội số chung của N số trên và không biểu giá trị diễn dưới hình thức dấu phẩy động (Lưu ý: bội số chung nhỏ nhất có thể rất lớn).

* Dữ liệu vào: từ file văn bản DULIEU.INP: gồm N dòng, dòng thứ i lưu một giá trị nhỏ hơn 109 tương ứng với giá trị của Ai.

* Dữ liệu ra: ghi ra file văn bản KETQUA.OUT: ghi một giá trị duy nhất là bội chung nhỏ nhất của các giá trị Ai với 0 ≤  i ≤ 109.

Ví dụ:

DULIEU.INP KETQUA.OUT
4337123

2497192

3442357

191233

3451237

1333935

4689038856757446007119839630000423160
  1. Cấu trúc dữ liệu và giải thuật

* Cấu trúc dữ liệu:

– Xây dựng mảng A[0..Hang_so] kiểu Big_Number để ghi nhận các số nguyên tố được phân tích từ nguồn dữ liệu vào.

–  Xây dựng mảng B[0..Hang_so] kiểu Big_Number để lưu giá trị bội chung nhỏ nhất của nguồn dữ liệu vào:  B := B * Ai với 0 ≤ i ≤ A0.

– Xây dựng thủ tục Tách(X,A) để tách số nguyên dương X thành tích các thừa số nguyên tôvà lưu các số nguyên tố đó vào mảng A.

– Sử dụng thủ tục Nhan_Min(C,A,k) là thủ tục thực hiện phép nhân một số nguyên lớn A với một số nguyên nhỏ k.

* Giải thuật:

A[0]:= Hang_So + 1;

Lặp

– Đọc file(F1,M);

– Tách(M,A);

Đến khi: (M>1) Or Eof(F1);

Trong khi Not Eof(F1) Làm

– Readln(F1, M);

– For I:= Hang_So Downto A[0] Do

+ Nếu M Mod A[I] = 0 Thì M:= M Div A[I];

– Tách(M, A);

B:=1;

Cho i:= A[0] đến Hang_so làm Nhan_min(B,B,A[i])

In(B)

  1. Chương trình được lưu trong đường dẫn E:\Chuyen De\BCNN

Program BOI_CHUNG_NHO_NHAT;

Const   Hang_So = 1000000;

Type    Big_Number = Array[0..Hang_So] Of Longint;

Var      A, B: Big_Number; I, M, J: Longint; F1,F2:Text;

{========================}

Procedure Tach(X: Longint; Var A: Big_Number);

Var     K: Longint;

Begin

K:= 2;

While X>1 Do

If (X Mod K =0) And (K <= X) Then

Begin A[0]:= A[0]-1; A[A[0]]:= K; X:= X Div K; End

Else K:= K+1;

If X>1 Then  Begin A[0]:= A[0]-1; A[A[0]]:= X;  End;

End;

{========================}

Procedure Nhan_Min(Var C: Big_Number; A: Big_Number; K: Longint);

Var     I, Tg: Longint;

Begin

Tg:= 0;

For I:= Hang_So Downto A[0] Do

Begin Tg:= Tg+A[I] * K;  C[I]:= Tg Mod 10; Tg:= Tg Div 10; End;

While Tg > 0 Do Begin  I:= I-1; C[I]:= Tg Mod 10; Tg:= Tg Div 10; End;

C[0]:= I;

End;

{========================}

Begin

Assign(F1,’E:\Chuyen De\BCNN\Dulieu.Inp’); Reset(F1);

Assign(F2,’E:\Chuyen De\BCNN\Ketqua.OUT’); Rewrite(F2);

A[0]:= Hang_So + 1;

Repeat  Readln(F1,M); Tach(M,A); Until (M>1) Or Eof(F1);

While Not Eof(F1) Do

Begin

Readln(F1, M);

For I:= Hang_So Downto A[0] Do

If M Mod A[I] = 0 Then M:= M Div A[I];

Tach(M, A);

End;

Fillchar(B,Sizeof(B),0); B[0]:=Hang_So; B[Hang_So]:=1;

For I:=Hang_So Downto A[0] Do Nhan_Min(B, B, A[I]);

For I:=B[0] To Hang_So Do Write(F2, B[I]);

Close(F1);

Close(F2);

End.

2.4. SỐ KHÁC KHÔNG CUỐI CÙNG

  1. Đề bài: (đề thi HSG cấp tỉnh tỉnh Thừa Thiên Huế năm 2012)

Cho dãy số nguyên dương A1, A2, A3, ….., AN (Ai ≤ 105). Hãy xác định chữ số khác không cuối cùng của các giá trị Ai! với 1 ≤ i ≤ N.

Ví dụ:       + 4! = 1.2.3.4 = 24 chữ số khác không cuối cùng là 4.

+ 5! = 1.2.3.4.5 = 120 chữ số khác không cuối cùng là 2.

+ 10! = 1.2….10 =3628800 chữ số khác không cuối cùng là 8

* Dữ liệu vào: từ file văn bản DULIEU.INP:

Có nhiều hàng, trên hàng thứ i lưu một số nguyên dương tương ứng với giá trị của Ai.

* Kết quả ra: ghi ra file văn bản KETQUA.OUT

Gồm nhiều dòng, mỗi dòng ghi 2 giá trị:

+ Giá trị thứ nhất: là Ai

+ Giá trị thứ hai: là giá trị số khác không cuối cùng của Ai!

Ví dụ:

DULIEU.INP KETQUA.OUT
1

5

10

50

100

300

1000

10000

100000

              1      1

5      2

10      8

50      2

100      4

300      6

1000      2

10000      8

100000      6

  1. Cấu trúc dữ liệu và giải thuật

* Cấu trúc dữ liệu:

– Xây dựng biến mảng A: Big_Number để lưu giá trị N! = 1.2.3.4.5…..N

– Sử dụng thủ tục Nhan_Min(C,A,k): C := A * k với biến A, C kiểu Big_Number và biến k kiểu Longint.

* Giải thuật:

Begin

– Trong khi  Not Eof(F1)  làm

+ Readln(F1,M);

+ A:=1;

+ For cho i:=1 đến M làm Nhan_Min(A,A,i);

+ i:=Hang_So;

+ Trong khi Ai=0 làm i:= i – 1;

+ Trong khi Ai Mod 10 = 0 làm Ai:=Ai Div 10;

+ Writeln(F2,M,A[J] Mod 10);

End.

  1. Chương trình được lưu trong đường dẫn E:\Chuyen De\Dvi Giai Thua

Program HANG_DON_VI_GIAI_THUA;

Const Hang_So=1000000;

Type    Big_Number=Array[0..Hang_So]Of Longint;

Var      A: Big_Number; I,M,J:Longint;  F1,F2:Text;

{========================}

Procedure Nhan_Min(Var C:Big_Number;A:Big_Number;K:Longint);

Var     I,Tg:Longint;

Begin

Tg:=0;

For I:=Hang_So Downto A[0] Do

Begin Tg:=Tg+A[I]*K;  C[I]:=Tg Mod 10000; Tg:=Tg Div 10000; End;

While Tg>0 Do Begin I:=I-1; C[I]:=Tg Mod 10000; Tg:=Tg Div 10000; End;

C[0]:=I;

End;

{========================}

Begin

Assign(F1,’E:\Chuyen De\Dvi Giai Thua\Dulieu.Inp’);Reset(F1);

Assign(F2,’E:\Chuyen De\Dvi Giai Thua\Ketqua.Out’);Rewrite(F2);

While Not Eof(F1) Do

Begin

Readln(F1,M);

A[0]:=Hang_So;A[Hang_So]:=1;

For I:=1 To M Do Nhan_Min(A,A,I);

J:=Hang_So; While (J>=A[0])And(A[J]=0)Do J:=J-1;

While A[J] Mod 10 = 0 Do A[J]:=A[J] Div 10;

Writeln(F2,M:10,A[J] Mod 10:5);

End;

Close(F1); Close(F2);

End.

NHẬN XÉT: Chương trình này chỉ hiệu quả với giá trị của các Ai ≤ 5.104 nhưng khi Ai>5.104 thì thời gian thực hiện tương đối lâu. Để thực hiện bài toán hiệu quả hơn chúng tôi mạnh dạn đưa ra phương án sử dụng tính chất số học để giải quyết bài toán thì hiệu quả hơn rất nhiều so với ban đầu và phạm vi dữ liệu có thể mở rộng hơn đến 108.

Tính chất:

+ Hàng đơn vị của một tích bằng tích hàng đơn vị của các thừa số.

+ Nếu tách hết tất cả các thừa số 2 và thừa số 5 ra khỏi tích 1.2.3.4.5…..N thì tích của các thừa số còn lại có hàng đơn vị là một số lẻ.

+ Hàng đơn vị của N! luôn luôn là một số chẵn với mọi N > 1.

* Giải thuật: Xây dựng hàm xác định giá trị chữ số cuối cùng của N! khác không như sau:

Function Dvi(N:longint): Longint

Begin

Nếu N<2 thì Dvi:=1

Ngược lại

Cso_2:=0; Cso_5:=0; Dvi_gthua:=1;

Cho j:=2 đến N làm

I:= j; Tách các thừa số 2 trong i;

Tách các thừa số 5 trong i;

Dvi_Gthua:= (Dvi_gthua * (I Mod 10)) Mod 10;

Cho J:= 1 đến Cso_2 – Cso_5 làm

Dvi_Gthua:= (Dvi_gthua * 2) Mod 10;

Dvi:=Dvi_Gthua;

End;

– Vận dụng hàm Dvi(N) để xác định hàng đơn vị của các giá trị đầu vào:

BEGIN

Reset(f1); Rewrite(f2)

Trong khi Not Eof(f1) làm {Readln(f1,m); Writeln(f1,m,dvi(m))}

Close(f1); Close(f2)

END.

* Chương trình:                  E:\Chuyen De\Dvi Giai Thua\Dvi Giai Thua (so hoc).pas

Program HANG_DON_VI_GIAI_THUA;

Var            M: Longint;    F1, F2: Text;

Function Dvi(N:Longint): Longint;

Var     Cso_2, Cso_5, I, Dvi_Gthua, J: Longint;

Begin

If N<2 Then Dvi:=1

Else  Begin

Cso_2:= 0; Cso_5:= 0; Dvi_Gthua:= 1;

For J:=2 To N Do

Begin

I:= J; While (I > 1) And (I Mod 2 = 0) Do

Begin Cso_2:= Cso_2 + 1;  I:= I Div 2; End;

While (I > 1) And (I Mod 5 = 0) Do

Begin Cso_5:= Cso_5 + 1; I:= I Div 5; End;

Dvi_Gthua:= (Dvi_Gthua * (I Mod 10)) Mod 10;

End;

For J:= 1 To Cso_2 – Cso_5 Do

Dvi_Gthua:= (Dvi_Gthua * 2) Mod 10;

Dvi:=Dvi_Gthua;

End;

End;

Begin

Assign(F1,’E:\Chuyen De\Dvi Giai Thua\Dulieu.Inp’);Reset(F1);

Assign(F2,’E:\Chuyen De\Dvi Giai Thua\Ketqua.out’);Rewrite(F2);

While Not Eof(F1) Do

Begin  Readln(F1,M); Writeln(F2, M:10, Dvi(M):5); End;

Close(F1); Close(F2);

End.

2.5. ĐẾM SỐ ƯỚC

  1. Đề bài:

Cho dãy số A1, A2, ……, AN là các số nguyên dương và Ai ≤ 105. Hãy đếm xem các giá trị Ai! có bao nhiêu ước số với 1 ≤ i  ≤ N.

* Dữ liệu vào: được lưu bởi file văn bản DU LIEU.INP có cấu trúc như sau:

+ Dòng đầu tiên: có một số duy nhất là giá trị của số nguyên dương N.

+ Dòng thứ 2: gồm N số nguyên dương Ai với mọi 1 ≤ i  ≤ N

* Dữ liệu ra: file văn bản với tên là KET QUA.OUT có nhiều dòng.

Đầu ra của mỗi giá trị Ai! có một hoặc nhiều dòng tùy thuộc vào giá trị của số ước của nó và được lưu theo cấu trúc như sau: 100! co so uoc la: 39001250856960000

(Không biểu diễn kết quả dưới dạng dấu phẩy động)

Ví dụ:

DU LIEU.INP KET QUA.OUT
5

2 5 50 100 500

2! co so uoc la: 2

5! co so uoc la: 16

50! co so uoc la: 4464046080

100! co so uoc la: 39001250856960000

500! co so uoc la:

303234214864803135635216296618578056852499175

8336000000000000

  1. Cấu trúc dữ liệu và giải thuật

* Cấu trúc dữ liệu:

– Biến N nguyên dương: lưu giá trị số phần tử của dãy A.

– Xây dựng mảng A[1..N] lưu giá trị của dãy số.

– Xây dựng mảng  B[1..K] lưu các số nguyên tố từ 2 cho đến Max(Ai) với  1 ≤ i  ≤ N.

– Xây dựng mảng C[1..K] với Ci = j với j là số chữ số nguyên tố Bi được tách ra từ  Ai!.

– Xây dựng biến mảng D: Big_Number lưu giá trị số ước đếm được từ Ai!

* Giải thuật:

– Sử dụng thủ tục nhân một số nguyên lớn A với một số nguyên nhỏ k: Nhan_Min(C,A,k) nghĩa là C:= A * k.

– Thủ tục TÁCH(X:Longint; C: Big_Number): Tách biểu thức X! thành tích các thừa số nguyên tố.

PROCEDURE TACH(X: LONGINT; Var C: Big_Number);

BEGIN

Fillchar(C,SIZEOF(C),0);

FOR i:= 2 TO X DO

Tách i thành các thừa số nguyên tố và lưu vào mảng C.

END;

– Chương trình chính:

Cho i:=1 đến N làm

+ Write(F, A[I],’! Co So Uoc La: ‘);

+ TACH(A[I],C);

+ D:=1;

+ Cho J:= 1 đến K làm

Nếu C[J]>0 Thì Nhan_Min(D,D,C[J]+1);

+ Writeln(F,D);

  1. Chương trình được lưu theo đường dẫn E:\Chuyen De\UocSo

Program DEM_SO_UOC;

Const        Hang_So=1000000;

Type          Big_Number=Array[0..Hang_So] Of Longint;

Var            A, B, C, D: Big_Number; I, M, N, K, J: Longint; F: Text;

{========================}

Procedure Doc_File;

Var        I, J, Max, U: Longint;

Begin

Assign(F,’E:\Chuyen De\Uocso\Dulieu.Inp’); Reset(F);

Readln(F,N); Max:= 0;

For I:=1 To N Do

Begin Read(F, A[I]); If Max < A[I] Then Max:= A[I]; End;

Close(F);

        {Xây dựng dãy số B có K phần tử là các số nguyên tố từ 2 đến (Max(Ai)}

B[1]:=2; B[2]:=3; K:=2;

For I:= 5 To Max Do

Begin

J:= 1;

While (B[J] <=Trunc(Sqrt(I))) And (I Mod B[J] <>0) Do J:= J+1;

If B[J] > Sqrt(I) Then   Begin K:= K+1; B[K]:= I; End;

End;

End;

{========================}

Procedure Tach(X: Longint; Var C: Big_Number);

Var     I, U, J: Longint;

Begin

Fillchar(C,Sizeof(C),0);

For I:= 2 To X Do

Begin

U:= I; J:= 1;

Repeat

If U Mod B[J] = 0 Then

Begin  C[J]:= C[J] + 1;  U:= U Div B[J];  End

Else J:= J + 1;

Until U = 1;

End;

End;

{===========================}

Procedure Nhan_Min(Var C: Big_Number; A: Big_Number; K: Longint);

Var     I, TG: Longint;

Begin

Tg:= 0;

For I:= Hang_So Downto A[0] Do

Begin Tg:= Tg + A[I] * K; C[I]:= Tg Mod 10; Tg:= Tg Div 10; End;

While Tg > 0 Do Begin I:= I – 1; C[I]:= Tg Mod 10; Tg:= Tg Div 10; End;

C[0]:= I;

End;

{========================}

Begin

DOC_FILE;

Assign(F,’E:\Chuyen De\Uocso\Ketqua.OUT’); Rewrite(F);

For I:=1 To N Do

BEGIN

Write(F, A[I],’! Co So Uoc La: ‘);

TACH(A[I],C);

Fillchar(D,Sizeof(D),0); D[0]:= Hang_So; D[Hang_So]:= 1;

For J:= 1 To K Do

If C[J]>0 Then Nhan_Min(D,D,C[J]+1);

For J:= D[0] To Hang_So Do Write(F, D[J]);Writeln(F);

END;

Close(F);

End.

2.6. MỘT SỐ BÀI TOÁN ĐỀ XUẤT

Bài 1. TỔNG SỐ LỚN

Cho dãy số A1, A2, …, AN là các số nguyên dương (N ≤ 106; Ai ≤ 10100) và 0 ≤ K ≤ 1000.

* Yêu cầu: Xác định K chữ số cuối cùng của tổng S = A1 + A2 + A3 + …. + AN.

* Dữ liệu vào: lưu trong file văn bản SO LON.INP có cấu trúc như sau:

– Dòng thứ nhất: ghi số nguyên K.

– Các dòng tiếp theo: mỗi dòng ghi một số nguyên Ai

* Kết quả ra: ghi ra file văn bản SO LON.OUT là một giá trị duy nhất có K chữ số cuối cùng của tổng S.

Ví dụ:

SO LON.INP SO LON.OUT
4

423242344244234234

324234423422342323

5435344654895388583

8967867967969765835498209752

768687675897583748539845639856

80279764987499459478978697396873986

8734

(Chương trình được ghi trên đĩa với đường dẫn CHUYEN DE\SO LON)

Bài 2. LŨY THỪA

Xác định K chữ số cuối cùng của XY với X, Y là các số nguyên dương X ≤ 106
Y ≤ 106 và K ≤ 100.

* Dữ liệu vào: từ file văn bản LUY THUA.INP:

Dòng thứ nhất: số nguyên dương K.

– N dòng tiếp theo: mỗi dòng ghi hai số Ai và Bi

* Kết quả ra: ghi ra file văn bản LUY THUA.OUT gồm N dòng, trên mỗi dòng ghi một số duy nhất có K chữ số cuối cùng của AiBi

(lưu ý: kết quả trả về có thể ít hơn K chữ số nếu giá trị của lũy thừa không đủ K chữ số).

LUY THUA.INP LUY THUA.OUT
15

2 5

2 10

2 20

2 30

2 40

2 50

32

1024

1048576

1073741824

1099511627776

125899906842624

 

(Chương trình được ghi trên đĩa với đường dẫn E:\CHUYEN DE\LUY THUA)

Bài 3. CẶP NGOẶC

Đếm xem có bao nhiêu cách sắp xếp N cặp ngoặc () để tạo thành một biểu thức có nghĩa.

* Dữ liệu vào: từ file văn bản SO NGOAC.INP lưu một số duy nhất nguyên dương
N ≤ 105.

* Kết quả ra: ghi ra file văn bản SO NGOAC.OUT

Có một số duy nhất là số cách sắp xếp N cặp ngoặc được lưu trên một hoặc nhiều dòng phụ thuộc vào kết quả ra.

Ví dụ 1:

SO NGOAC.INP SO NGOAC.OUT
3 5

Ví dụ 2:

SO NGOAC.INP SO NGOAC.OUT
300 448863594671741755862042783981742625904431712455792292112842929523169934910317996551330498997589600726489482164006103817421596314821101633539230654646302151568026806610883615856

(Chương trình được ghi trên đĩa – đường dẫn E:\CHUYEN DE\CATALAN)

Bài 4. BỘI SỐ

Với số nguyên dương X (X ≤ 106). Hãy xác định số nguyên dương Y là bội số nhỏ nhất X sao cho biểu diễn Y trong hệ đếm thập phân chỉ chứa các chữ số 0 và 1.

* Dữ liệu vào: từ file văn bản BOISO.INP gồm nhiều dòng, dòng thứ i là số nguyên dương Ai (Ai ≤ 109)

* Kết quả ra: đưa vào file văn bản BOISO.OUT như sau: trên mỗi dòng có số là Ai và bội số nhỏ nhất của Ai.

Ví dụ:

BOISO.INP BOISO.OUT
2

4

20

25

3000

99

      2      10

4      100

20      100

25      100

3000      111000

99      111111111111111111

(Chương trình được ghi trên đĩa theo đường dẫn E:\CHUYEN DE\BOI SO)

Bài 5. TỔNG ƯỚC SỐ

Cho dãy số A1, A2, ……, AN là các số nguyên dương và Ai ≤ 20000. Hãy đếm xem các giá trị Ai! có bao nhiêu ước số với 1 ≤ i  ≤ N.

* Dữ liệu vào: được lưu bởi file văn bản DU LIEU.INP có cấu trúc như sau:

+ Dòng đầu tiên: có một số duy nhất là giá trị của số nguyên dương N.

+ Dòng thứ 2: gồm N số nguyên dương Ai với mọi 1 ≤ i  ≤ N

* Dữ liệu ra: file văn bản với tên là KET QUA.OUT có nhiều dòng.

Đầu ra của mỗi giá trị Ai! có một hoặc nhiều dòng tùy thuộc vào giá trị của tổng ước của nó và được lưu theo cấu trúc như sau:    8!            159120

(Không biểu diễn kết quả dưới dạng dấu phẩy động)

DU LIEU.INP KET QUA.OUT
  5

5 8 10 12 13

     5!                       360

8!                 159120

10!             15334088

12!         2217441408

13!       31044179712

(Chương trình được ghi trên đĩa với đường dẫn CHUYEN DE\TONG UOC)


Phần III. KẾT LUẬN

Trong quá trình nghiên cứu và ứng dụng đề tài vào quá trình giảng dạy bồi dưỡng học sinh giỏi hai năm qua tại trường trung học phổ thông Vinh Xuân, và đề tài này đã giúp thầy trò chúng tôi gặt hái một số thành công nhất định (chọn được 2 học sinh trong đội tuyển HSG môn Tin học của trường tham gia hai kỳ thi HSG cấp tỉnh vào năm 2012 và 2013 do Sở GD-ĐT tỉnh Thừa Thiên Huế tổ chức; đã  đạt được hai giải Nhì cấp Tỉnh ở hai kỳ thi trên). Qua quá trình ứng dụng đề tài này chúng tôi nhận thấy có một số ưu nhược điểm như sau:

* Về ưu điểm:

– Biểu diễn được các số nguyên lớn có hàng trăm nghìn chữ số giúp cho miền giá trị của số nguyên lớn miền giá trị kiểu số thực trong Free Pascal là Real hay Extended.

– Giải quyết được các bài toán liên quan đến số nguyên lớn và biểu diễn được giá trị chính xác đến hàng đơn vị mà không sử dụng đến dấu phẩy động.

– Xây dựng được bộ công cụ hỗ trợ hữu hiệu giúp cho quá trình bỗi dưỡng học sinh giỏi của giáo viên trường trung học phổ thông Vinh Xuân đạt kết quả cao hơn và là bộ tài liệu hiệu quả giúp học sinh học lập trình gải quyết bài toán số nguyên lớn tốt hơn để tham gia các kỳ thi cấp tỉnh đạt thành tích cao.

* Về nhược điểm: Thuật toán để giải quyết một số bài toán ở trên là chưa tối ưu, thời gin thực hiện lâu khi gặp dữ liệu vào lớn; chương trình tương đối dài và phức tạp để giải quyết một bài toán nguyên dương lớn. Giá trị trả về của các phép toán đa số nằm trên mảng một chiều nên chưa linh động trong quá trình ứng dụng để giải những bài toán khác.

* Hướng phát triển của đề tài: Do một số vấn đề khách quan nên đề tài chỉ giới hạn trên tập số nguyên, do đó khi gặp tình huống số nguyên âm thì kết quả trả về của các giá trị đầu ra sai. Vì thế chúng tôi sẽ mở rộng và hoàn chỉnh đề tài trong những năm tiếp theo.

 

Phú Vang, ngày 12 tháng 3 năm 2014
Người viết chuyên đề

Lê Văn Lộc

 

TÀI LIỆU THAM KHẢO

  1. Bộ Giáo dục và Đào tạo (2008), Sách giáo khoa Tin học 11, NXB Giáo dục.
  2. Bộ Giáo dục và Đào tạo, Tài liệu giáo khoa chuyên Tin quyển 1, NXB Giáo dục.
  3. Bộ Giáo dục và Đào tạo, Tài liệu giáo khoa chuyên Tin quyển 2, NXB Giáo dục.
  4. Bộ Giáo dục và Đào tạo (2010), Tài liệu tập huấn phát triển chuyên môn giáo viên trường THPT chuyên môn Tin học, NXB Giáo dục.
  5. Bộ Giáo dục và Đào tạo (2011) Tài liệu tập huấn phát triển chuyên môn giáo viên trường THPT chuyên môn Tin học, NXB Giáo dục.
  6. Bộ Giáo dục và Đào tạo (2012) Tài liệu tập huấn phát triển chuyên môn giáo viên trường THPT chuyên môn Tin học, NXB Giáo dục.
  7. Kenneth H.Rosen, Toán học rời rạc ứng dụng trong Tin học (sách dịch).
  8. TS. Nguyễn Xuân My (), Tuyển chọn các bài toán Tin học dành cho học sinh giỏi THPT, NXB Giáo dục.
  9. Nguyễn Quang Vịnh (2007) Bài tập thực hành Pascal, NXB Giáo dục.

 

 

MỤC LỤC

PHẦN I. ĐẶT VẤN ĐỀ.. 1

  1. Lý do chọn đề tài 1
  2. Mục đích nghiên cứu. 1
  3. Đối tượng nghiên cứu. 1
  4. Phạm vi nghiên cứu. 1
  5. Phương pháp nghiên cứu. 1
  6. Kết cấu đề tài 2

PHẦN II. NỘI DUNG VÀ KẾT QUẢ NGHIÊN CỨU.. 3

Chương 1. CƠ SỞ LÝ LUẬN VỀ LẬP TRÌNH VỀ SỐ NGUYÊN LỚN.. 3

1.1. TỔ CHỨC KIỂU DỮ LIỆU MẢNG MỘT CHIỀU BIỂU DIỄN SỐ NGUYÊN LỚN. 3

1.2. PHÉP TOÁN QUAN HỆ.. 4

1.2.1. Phép toán so sánh bằng. 4

1.2.2. Phép toán so sánh lớn hơn. 4

1.2.3. Phép toán so sánh nhỏ hơn. 5

1.3. PHÉP TOÁN SỐ HỌC.. 6

1.3.1. Phép cộng. 6

1.3.1.1. Cộng số nguyên lớn với số nguyên nhỏ. 6

1.3.1.2. Cộng hai số nguyên lớn. 7

1.3.2. Phép trừ. 8

1.3.2.1. Trừ số nguyên lớn với số nguyên nhỏ. 8

1.3.2.2. Trừ hai số nguyên lớn. 9

1.3.3. Phép nhân. 11

1.3.3.1. Nhân số nguyên lớn với số nguyên nhỏ. 11

1.3.3.2. Nhân hai số nguyên lớn. 12

1.3.4. Phép chia. 13

1.3.4.1. Chia lấy phần nguyên. 13

1.3.4.1.1. Số nguyên lớn chia số nguyên nhỏ. 13

1.3.4.1.2. Số nguyên lớn chia số nguyên lớn. 13

1.3.4.2. Chia lấy phần dư (Mod). 17

1.3.4.2.1. Số nguyên lớn chia số nguyên nhỏ. 17

1.3.4.2.2. Số nguyên lớn chia số nguyên lớn. 17

Chương II. GIẢI PHÁP CHO MỘT SỐ BÀI TOÁN SỐ NGUYÊN LỚN.. 20

2.1. TÍNH GIÁ TRỊ GIAI THỪA.. 20

2.2. BÀI TOÁN BIÊN DỊCH.. 22

2.3. BÀI TOÁN BỘI CHUNG NHỎ NHẤT. 28

2.4. SỐ KHÁC KHÔNG CUỐI CÙNG.. 31

2.5. ĐẾM SỐ ƯỚC.. 35

2.6. MỘT SỐ BÀI TOÁN ĐỀ XUẤT. 38

Phần III. KẾT LUẬN.. 42

 

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Chuyên mục

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Staithes

Reflecting Pool

Golden Hour

More Photos

Thống kê

  • 115,384 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: