LỜI NÓI ĐẦU
Phân tích và thiết kế giải thuật là một môn học cơ sở ngành rất quan trọng đối với sinh viên
công nghệ thông tin. Có thể xem đây là nền tảng của lập trình. Đối với một bài toán nào đó, chúng
ta có thể có nhiều giải thuật khác nhau. Vấn đề đặt ra là làm thế nào để chọn được thuật toán tốt
nhất, thông thường căn cứ theo các tiêu chuẩn sau:
1. Giải thuật đúng đắn
2. Giải thuật đơn giản
3. Giải thuật thực hiện nhanh
Làm thế nào để xây dựng một thuật toán tối ưu nhất, cách tổ chức cơ sở dữ liệu hợp lí và cung
cấp kiến thức cho sinh viên về tác động của giải thuật với dữ liệu. Đó chính là mục đích của môn
học này.
Với đồ án môn học này, mục đích của chúng em là củng cố thêm kiến thức của mình về việc
thiết kế thuật toán sao cho hợp lí, đánh giá độ phức tạp của thuật toán một cách chính xác và hơn
hết là có thể xây dựng một chương trình theo yêu cầu sao cho tối ưu nhất.
Áp dụng những kiến thức về vòng lặp, mảng chúng em đã xây dựng được thuật toán giải
quyết bài toán Biểu diễn số nguyên lớn. Bài toán được thực hiện bằng ngôn ngữ C sharp để thiết
lập thêm giao diện nhằm thuận lợi cho việc sử dụng.
Dưới sự hướng dẫn nhiệt tình của thầy Lê Quý Lộc, chúng em đã hoàn thành tốt nhất đồ án
môn học Phân tích và thiết kế giải thuật. Chúng em mong sẽ nhận được sự quan tâm và góp ý từ
phía thầy để bài làm của chúng em được hoàn thiện.

ĐỀ BÀI
Số nguyên lớn là một mảng các chữ số. Yêu cầu:
 Xây dựng các hàm tiện ích để tính toán trên số lớn: tăng 1 số 1 đơn vị, tổng hai số,
tích hai số
 Viết chương trình minh họa việc sử dụng các hàm này. Các số có không quá n chữ
số. Đánh giá độ phức tạp của các hàm theo n.
 Viết chương trình nhập n và in ra số Fibonacci thứ n (n >1000).

MỤC LỤC
LỜI NÓI ĐẦU 1

ĐỀ BÀI 2
MỤC LỤC 3
I. GIỚI THIỆU 4
II. BIỂU DIỄN DỮ LIỆU VÀO RA 4
III. THUẬT TOÁN CỘNG 5
1. Thuật toán cộng 2 số 5
2. Thuật toán cộng 1 số thêm 1 đơn vị 6
3. Cài đặt 6
4. Đánh giá 7
IV. THUẬT TOÁN TRỪ 7
1. Thuật toán trừ 2 số 7
2. Thuật toán trừ 1 số đi 1 đơn vị 8
3. Cài đặt 8
4. Đánh giá 9
V. THUẬT TOÁN NHÂN 10
1. Thuật toán nhân 10
2. Cài đặt 10
3. Đánh giá 11
VI. THUẬT TOÁN CHIA 12
1. Thuật toán chia 12
2. Cài đặt 12
3. Đánh giá 15
VII. THUẬT TOÁN TÍNH SỐ FIBONACCI THỨ N 16
1. Thuật toán 16
2. Cài đặt 17
3. Đánh giá 17
KẾT LUẬN 19
CÁC NGUỒN THAM KHẢO 20



I. GIỚI THIỆU
Trong quá trình lập trình chắc có lẽ chúng ta cũng đã gặp một số trường hợp số xử lí quá lớn
mà các kiểu double hay long double cũng không lưu trữ được.
Đa phần các phương pháp đều tập trung vào chia nhỏ số lớn ra để xử lí, sau đó nối các phần
lại với nhau theo thứ tự để hoàn thiện. Tuy nhiên, có một cách đơn giản hơn và khá hiệu quả, đó
là xử lí số lớn bằng mảng. Coi số lớn như một mảng các chữ số, việc tính toán trên số lớn chính
là tính toán trên các phần tử của mảng. Sau đó thực hiện cộng các phần tử của mảng tương ứng
để được mảng mới hiện thị ra màn hình.
Chẳng hạn, muốn biểu diễn số 1 tỷ thay vì viết 1.000.000.000 thì ta thể viết thành 10
9
. Việc
làm như vậy giúp chúng ta dễ đọc hiểu hơn, tránh được tình trạng thiếu sót, thừa chữ số.
Ứng dụng trong thiên văn, mã hóa, máy tính (số bits trên đĩa cứng) …
II. BIỂU DIỄN DỮ LIỆU VÀO RA
Dữ liệu được nhập vào từ bàn phím thông qua 1 inputbox, chương trình có giao diện như
dưới đây:

Hình 1: nhập dữ liệu vào chương trình
Dữ liệu ra được xuất trên màn hình thông qua 1 textbox bên phải cửa sổ như sau:

Hình 2: dữ liệu được hiển thị thông qua textbox
III. THUẬT TOÁN CỘNG
1. Thuật toán cộng 2 số
Đầu vào: bi1 và bi2 là 2 số cần tính tổng
Đầu ra: result là kết quả của phép cộng bi1 và bi2
Xử lý:
 Bước 1:
o So sánh độ dài của bi1 và bi2. Giả sử bi1 có độ dài lớn hơn bi2
o Khởi tạo result chứa kết quả với độ dài của result bằng độ dài bi1 + 1
 Bước 2:

o Khởi tạo biến carry = 0
o Cộng lần lượt các chữ số của bi1, bi2 và carry từ hàng đơn vị lên
For i = 0 to result.length - 1 do
result.data[i] = bi1.data[i] + bi2.data[i] + carry
if result.data[i] > 9 then
carry = 1
result.data[i] -= 10
else
carry = 0
endif
endfor
 Bước 3: Tính toán lại độ dài của result cho phù hợp và kết thúc thuật toán.
Ví dụ: 1234567891011121314151617181920 + 98765432123456789 = 1234567891011220079583740638709
2. Thuật toán cộng 1 số thêm 1 đơn vị
Đầu vào: bi là số cần tăng lên 1 đơn vị
Đầu ra: bi là số đã được tăng lên 1 đơn vị
Xử lý:
 Bước 1: khởi tạo carry = 1 và tăng chiều dài bi lên 1
 Bước 2: cộng carry vào bi
for i = 0 to bi.length – 1 do
bi.data[i] += bi.data[i] + carry
if bi.data[i] > 9 then
carry = 1
bi.data[i] -= 10
else
break
endif
endfor
 Bước 3: tính toán lại độ dài của bi cho phù hợp và kết thúc thuật toán.
Ví dụ: 1234567891011121314151617181920++ = 1234567891011121314151617181921

3. Cài đặt
Thuật toán cộng 2 số:
BigInt result = new BigInt();
BigInt own = bi1.length > bi2.length ? bi1 : bi2;
result.length = own.length;
if (result.length < result.Capacity) result.length++;
byte carry = 0;
for (int i = 0; i < result.length; i++)
{
result.data[i] = (byte)(bi1.data[i] + bi2.data[i] + carry);
if (result.data[i] > 9)
{
carry = 1;
result.data[i] -= 10;
}
else
{
carry = 0;
}
}
if (carry > 0) throw new OverflowException();
result.AdjustLength();

Thuật toán tăng 1 số lên 1 đơn vị:
if (bi.length < bi.Capacity) bi.length++;
byte carry = 1;
for (int i = 0; i < bi.length; i++)
{
bi.data[i] = (byte)(bi.data[i] + carry);
if (bi.data[i] > 9)

{
carry = 1;
bi.data[i] -= 10;
}
else
{
carry = 0;
break;
}
}
if (carry > 0) throw new OverflowException();
bi.AdjustLength();

4. Đánh giá
Thuật toán cộng ở trên là thuật toán tối ưu. Độ phức tạp của nó là hàm bậc nhất theo n và
phụ thuộc vào chiều dài(số lượng chữ số) lớn nhất của trong 2 số tham gia vào phép cộng.
Trong mọi trường hợp số lần lặp luôn là n + 1 với n là chiều dài lớn nhất của 2 số tham gia
vào phép cộng vì thế nên độ phức tạp luôn là n.
Thuật toán tăng 1 số lên 1 đơn vị cũng tương tự thuật toán cộng với độ phức tạp là hàm
bậc nhất theo n với n là chiều dài của số cần tăng lên 1 đơn vị.
Ưu điểm:
 Dễ cài đặt
 Thực hiện nhanh
 Đơn giản
Nhược điểm: vì xử lý trên mảng tĩnh nên bị giới hạn kích thước bộ nhớ, nghĩa là với đầu
vào quá lớn và cài đặt tổng kích thước bộ nhớ cho phép của mảng không đáp ứng được thì sẽ
dễ bị tràn dữ liệu.
IV. THUẬT TOÁN TRỪ
1. Thuật toán trừ 2 số
Đầu vào: bi1 và bi2 lần lược là số bị trừ và số trừ

Đầu ra: result chứa kết quả của phép trừ bi1 và bi2
Xử lý:
 Bước 1: cài đặt biến carry = 0, đặt chiều dài của result bằng chiều dài lớn nhất của
1 trong 2 số bi1 hoặc bi2.
 Bước 2: trừ lần lược các chữ số của bi1, bi2 và carry từ hàng đơn vị lên.
for i = 0 to result.length - 1 do
result.data[i] = bi1.data[i] – bi2.data[i] – carry
if result.data[i] < 0 then
carry = 1
result.data[i] += 10
else
carry = 0
endif
endfor
 Bước 3: tính toán lại độ dài của result cho phù hợp và kết thúc thuật toán.
Ví dụ: 1234567891011121314151617181920 - 98765432123456789 = 1234567891011022548719493725131
2. Thuật toán trừ 1 số đi 1 đơn vị
Đầu vào: số bi là số cần giảm đi 1 đơn vị
Đầu ra: số bi là số đã giảm đi 1 đơn vị
Xử lý:
 Bước 1: cài đặt biến carry = 1
 Bước 2: trừ số bi cho biến carry
for i = 0 to bi.length - 1 do
bi.data[i] -= carry
if bi.data[i] < 0 then
carry = 1
bi.data[i] -= 10;
else
break
endif

endfor
 Bước 3: tính toán lại độ dài của số bi cho phù hợp và kết thúc thuật toán.
Ví dụ: 1234567891011121314151617181920 = 1234567891011121314151617181919
3. Cài đặt
Thuật toán trừ 2 số:
BigInt result = new BigInt();
byte[] temp1, temp2;
int comp = bi1.CompareTo(bi2, true);
if (comp == 0)
{
result.data[0] = 0;
result.length = 1;
return result;
}
else if (comp == 1)
{
temp1 = bi1.data;
temp2 = bi2.data;
result.length = bi1.length;
}
else
{
temp1 = bi2.data;
temp2 = bi1.data;
result.length = bi2.length;
}
sbyte temp, carry = 0;
for (int i = 0; i < result.length; i++)
{
temp = (sbyte)(temp1[i] - temp2[i] - carry);

if (temp < 0)
{
carry = 1;
result.data[i] = (byte)(temp + 10);
}
else
{
carry = 0;
result.data[i] = (byte)temp;
}
}
result.AdjustLength();

Thuật toán trừ 1 số đi 1 đơn vị:
byte carry = 1;
sbyte temp;
for (int i = 0; i < bi.length; i++)
{
temp = (sbyte)(bi.data[i] - carry);
if (temp < 0)
{
carry = 1;
bi.data[i] = (byte)(temp + 10);
}
else
{
bi.data[i] = (byte)temp;
break;
}
}

bi.AdjustLength();

4. Đánh giá
Thuật toán trừ ở trên là thuật toán tối ưu. Độ phức tạp của nó là hàm bậc nhất theo n và
phụ thuộc vào chiều dài (số lượng chữ số) lớn nhất của trong 2 số tham gia vào phép trừ. Trong
mọi trường hợp số lần lặp luôn là n với n là chiều dài lớn nhất của 2 số tham gia vào phép trừ
vì thế nên độ phức tạp luôn là n.
Thuật toán giảm 1 số đi 1 đơn vị cũng tương tự thuật toán trừ với độ phức tạp là hàm bậc
nhất theo n với n là chiều dài của số cần giảm đi 1 đơn vị.
Ưu điểm:
 Dễ cài đặt
 Thực hiện nhanh
 Đơn giản
V. THUẬT TOÁN NHÂN
1. Thuật toán nhân
Đầu vào: số bi1 và số bi2
Đầu ra: result là kết quả phép nhân giữa bi1 và bi2
Xử lý:
 Bước 1: kiểm tra xem nếu 1 trong 2 số bằng 0 thì gán result bằng 0 và kết thúc
thuật toán.
 Bước 2: khởi tạo 2 biến temp1 và temp2, với temp1 tham chiếu đến số có độ dài
lớn hơn, temp2 tham chiếu đến số có độ dài nhỏ hơn trong 2 số bi1 và bi2. Khởi
tạo result để lưu kết quả phép nhân. Khởi tạo biến k = 0.
 Bước 3: thực hiện nhân lần lượt từng chữ số của temp2 cho temp1
for i = 0 to temp2.length – 1 do
if temp2.data[i] = 0 then
continue
endif
carry = 0
k = i

for j = 0 to temp1.length – 1 do
temp = temp1.data[j] * temp2.data[i] + result.data[k] + carry
carry = temp / 10
result.data[k] = temp % 10
k += 1
endfor
if carry > 0 then
result.data[i + temp1.length] = carry
endif
endfor
 Bước 4: tính toán lại độ dài của result cho phù hợp và kết thúc thuật toán.
Ví dụ: 1234567891011121314151617181920 * 98765432123456789
= 121932631241458101023327185205570305877072054880
2. Cài đặt
Thuật toán nhân 2 số:
BigInt result = new BigInt();
if (bi1.length == 1
&& bi1.data[0] == 0
|| bi2.length == 1
&& bi2.data[0] == 0)
{
result.length = 1;
result.data[0] = 0;
return result;
}
BigInt temp1, temp2;
byte temp, carry;
if (bi1.length > bi2.length)
{
temp1 = bi1;

temp2 = bi2;
}
else
{
temp1 = bi2;
temp2 = bi1;
}
for (int i = 0; i < temp2.length; i++)
{
if (temp2.data[i] == 0) continue;
carry = 0;
for (int j = 0, k = i; j < temp1.length; j++, k++)
{
temp = (byte)(temp1.data[j] * temp2.data[i] + result.data[k] + carry);
carry = (byte)(temp / 10);
result.data[k] = (byte)(temp % 10);
}
if (carry > 0)
{
if (i + temp1.length >= result.Capacity) throw new OverflowException();
result.data[i + temp1.length] = carry;
}
}
result.length = bi1.length + bi2.length;
result.AdjustLength();
3. Đánh giá
Thuật toán nhân trên sẽ tiến hành nhân lần lượt từng chữ số của số có ít chữ số cho số có
nhiều chữ số do đó sẽ cần đến 2 vòng lặp lồng nhau để thực hiện. Trong trường hợp xấu nhất,
tất cả các số của số ít chữ số hơn đều khác 0 thì độ phức tạp của thuật toán là hàm bậc 2 theo
độ dài của số nhân. Trong trường hợp tốt nhất, một trong 2 số bằng 0 thì độ phức tạp chỉ bằng

1.
Ưu điểm:
 Đơn giản để cài đặt
 Hiệu quả và thực hiện nhanh
Nhược điểm: giống như phép cộng, do kích thước mảng bị cố định nên với những dữ liệu
quá lớn và vượt quá khả năng lưu trữ của mảng sẽ gây tràn dữ liệu.
VI. THUẬT TOÁN CHIA
1. Thuật toán chia
Đầu vào: 2 số bi1 và bi2 lần lược là số bị chia và số chia
Đầu ra: result là kết quả phép chia bi1 cho bi2
Xử lý:
 Thuật toán 1: thuật toán chia đơn giản, ý tưởng của thuật toán này là lấy số bị chia
trừ dần cho số chia và sau mỗi lần trừ ta tăng biến đếm lên 1 cho đến khi số bị
chia nhỏ hơn số chia thì dừng lại. Kết quả của biến đếm sẽ là thương số cần tìm.
 Bước 1: kiếm tra các trường hợp đặt biệt và các trường hợp lỗi
o Nếu bi2 = 0 thì thông báo lỗi chia cho 0.
o Nếu bi1 = 0 thì gán result bằng 0 và kết thúc thuật toán.
o Nếu bi1 = bi2 thì gán result bằng 1 và kết thúc thuật toán.
o Nếu bi2 = 1 thì gán result bằng bi1 và kết thúc thuật toán.
 Bước 2: khởi tạo biến temp và sao chép dữ liệu của bi1 vào temp.
 Bước 3: temp = temp – bi2
 Bước 4: nếu temp còn lớn hơn hoặc bằng bi2 thì tăng biến đếm lên 1 và
quay lại bước 3.
 Bước 5: gán biến đếm cho result và kết thúc thuật toán.
 Thuật toán 2: thuật toán chia phân đoạn, ý tưởng của thuật toán này là ta sẽ chia
số bị chia thành các phần (part) có độ dài bằng số chia và tiến hành chia nó cho số
chia bằng thuật toán 1.
 Bước 1: kiếm tra các trường hợp đặc biệt và các trường hợp lỗi
o Nếu bi2 = 0 thì thông báo lỗi chia cho 0.
o Nếu bi1 = 0 thì gán result bằng 0 và kết thúc thuật toán.

o Nếu bi1 = bi2 thì gán result bằng 1 và kết thúc thuật toán.
o Nếu bi2 = 1 thì gán result bằng bi1 và kết thúc thuật toán.
 Bước 2: lấy 1 phần của số bị chia (part) có độ dài bằng độ dài số chia và
lấy từ bên trái cùng sang. Thực hiện phép chia part cho bi2 bằng thuật
toán 1. Phần dư sẽ được lưu trở lại part, kết quả phép chia sẽ có giá trị từ 0
đến 9 và được lưu vào result.
 Bước 3: kiếm tra nếu part không phải là bên phải cùng thì dịch part sang
phải 1 chữ số và quay lại bước 2.
 Bước 4: tính toán lại độ dài của result và kết thúc thuật toán.
Ví dụ: 1234567891011121314151617181920 / 98765432123456789 = 12499999893362
2. Cài đặt
Các hàm hỗ trợ cho 2 thuật toán:
private static BigInt check_div(BigInt bi1, BigInt bi2)
{
// chia cho 0 thì báo lỗi
if (bi2.data.Length == 1 && bi2.data[0] == 0)
throw new DivideByZeroException();
// số bị chia = 0
if (bi1.data.Length == 1 && bi1.data[0] == 0) return new BigInt("0", false);
// so chia == 1
if (bi2.data.Length == 1 && bi2.data[0] == 1)
return (BigInt)bi1.MemberwiseClone();
int comp = bi1.CompareTo(bi2);
// giá trị số bị chia < giá trị số chia thì return 0 luôn
if (comp < 0) return new BigInt("0", false);
// giá trị số bị chia = giá trị số chia thì return 1 luôn
else if (comp == 0) return new BigInt("1", false);
return null;
}


private static int CompareArrays(byte[] a1, int l1, byte[] a2, int l2)
{
if (l1 > l2) return 1;
else if (l1 < l2) return -1;
else for (int i = l1 - 1; i >= 0; i )
if (a1[i] == a2[i]) continue;
else return a1[i] > a2[i] ? 1 : -1;
return 0;
}

private static int CompareArrays(byte[] a1,
int offset1,
int length1,
byte[] a2,
int offset2,
int length2,
bool recalcLength = false)
{
if (recalcLength)
{
while (length1 > 0 && a1[offset1 + length1 - 1] == 0) length1 ;
while (length2 > 0 && a2[offset2 + length2 - 1] == 0) length2 ;
}
if (length1 > length2) return 1;
else if (length1 < length2) return -1;
for (int i = length1 + offset1 - 1, j = length2 + offset2 - 1;
i >= offset1;
i , j )
if (a1[i] == a2[j]) continue;
else return a1[i] > a2[j] ? 1 : -1;

return 0;
}

private static byte divide_arrays(
byte[] ar1,
int offset1,
int length1,
byte[] ar2,
int length2)
{
byte carry = 0, ret = 0;
sbyte temp;
do
{
if (CompareArrays(ar1, offset1, length1, ar2, 0, length2, true) < 0)
break;
// trừ mảng ar1(với offset và length) cho ar2
for (int i = offset1, j = 0; j < length1; i++, j++)
{
temp = (sbyte)(ar1[i] - ar2[j] - carry);
if (temp < 0)
{
temp += 10;
carry = 1;
}
else
{
carry = 0;
}
ar1[i] = (byte)temp;

}
if (carry > 0) ar1[offset1 + length1 - 1] -= carry;
ret++;
} while (true);
return ret;
}

Thuật toán 1:
quotient = check_div(bi1, bi2);
if (quotient != null)
{
if (quotient.data[0] == 0) remainder = new BigInt(bi2.data, false);
else remainder = new BigInt("0", false);
return;
}
quotient = new BigInt();

sbyte temp, carry = 0;
byte[] subTemp = new byte[bi1.length];
int subLength = subTemp.Length;
Array.Copy(bi1.data, 0, subTemp, 0, bi1.length);
quotient.length = bi1.length;
quotient.data[0] = 1;
do
{
for (int i = 0; i < subLength; i++)
{
temp = (sbyte)(subTemp[i] - bi2.data[i] - carry);
if (temp < 0)
{

carry = 1;
subTemp[i] = (byte)(temp + 10);
}
else
{
carry = 0;
subTemp[i] = (byte)temp;
}
++div_count;
}
while (subLength > 1 && subTemp[subLength - 1] == 0) subLength ;
temp = (sbyte)CompareArrays(subTemp, subLength, bi2.data, bi2.length);
if (temp == 1 || temp == 0) direct_addadd(ref quotient);
if (temp == -1) break;
} while (true);
quotient.AdjustLength();

Thuật toán 2:
quotient = check_div(bi1, bi2);
if (quotient != null)
{
if (quotient.data[0] == 0) remainder = new BigInt(bi2.data, false);
else remainder = new BigInt("0", false);
return;
}
byte[] remainder_ar = (byte[])bi1.data.Clone();
byte[] bresult = new byte[bi1.length];
remainder = new BigInt(remainder_ar, true);
quotient = new BigInt();
int std_length = bi2.length;

int start_index = bi1.length - std_length + 1;
int stop_index = bi1.length - 1;
int result_pos = 0;
byte ret;
do
{
start_index ;
ret = divide_arrays(remainder_ar,
start_index,
stop_index - start_index + 1,
bi2.data, bi2.length);
while (stop_index > 0 && remainder_ar[stop_index] == 0) stop_index ;
bresult[result_pos++] = ret;
} while (start_index > 0);
quotient.length = result_pos;
for (int i = quotient.length - 1, j = 0; i >= 0; i , j++)
quotient.data[j] = bresult[i];
quotient.AdjustLength();

3. Đánh giá
Thuật toán 1 là thuật toán khá đơn giản và dễ hiểu nhưng cần số lần lặp rất lớn nếu số
lượng chữ số của số bị chia lớn hơn nhiều so với số lượng chữ số của số chia. Trong trường
hợp xấu nhất độ phức tạp của thuật toán 1 là hàm bậc nhất theo giá trị của số bị chia.
Ngược lại, thuật toán 2 tuy khá dễ hiểu nhưng lại phức tạp trong cài đặt nhưng tốc độ
thực hiện của thuật toán này lại nhanh hơn rất nhiều so với thuật toán 1. Thuật toán 2 dựa
trên việc chia nhỏ số bị chia thành các phần và thực hiện chia các phần đó cho số chia. Trong
trường hợp xấu nhất ta cũng chỉ cần chia số bị chia làm n phần với n là chiều dài của số bị
chia, đối với việc chia các phần của số bị chia cho số chia trong trường hợp xấu nhất cũng chỉ
cần thực hiện 9*n’ với n’ là chiều dài của số bị chia. Độ phức tạp của thuật toán này là hàm
bậc nhất theo độ dài của số bị chia.

Ưu điểm: với thuật toán 1 thì ưu điểm lớn nhất của nó là đơn giản và dễ cài đặt, còn đối
với thuật toán 2 thì ưu điểm của nó lại là tốc độ thực thi.
Nhược điểm: thuật toán 1 có nhược điểm là tốc độ thực thi chậm, với thuật toán 2 thì lại
khó khăn trong cài đặt.
Dưới đây là đồ thị so sánh số lần lặp để hoàn tất 1 phép chia với các đầu vào khác nhau
giữa 2 thuật toán chia ở trên, trong đồ thị bên dưới thì số bị chia là 1000000000.

Hình 3: đồ thị so sánh số lần lặp giữa thuật toán 1 và thuật toán 2
VII. THUẬT TOÁN TÍNH SỐ FIBONACCI THỨ N
1. Thuật toán
Đầu vào: số n.
Đầu ra: số fibonacci thứ n được lưu trong biến f.
Xử lý:
 Bước 1: khởi tạo các biến t1 = 1, t2 = 1, biến f = 1 lưu số fibonacci thứ n.
 Bước 2: số fibonacci thứ n bằng số fibonacci thứ n – 1 cộng cho số fibonacci thứ
n – 2
8893
888895
8888896
88888897
11 11 11 11
0
10000000
20000000
30000000
40000000
50000000
60000000
70000000
80000000

90000000
100000000
1000000 10000 1000 100
SỐ LẦN LẶP
SỐ CHIA
SO SÁNH THUẬT TOÁN 1 VÀ THUẬT TOÁN 2
Thuật toán 1
Thuật toán 2
for i = 2 to n – 1 do
f = t1 + t2
t1 = t2
t2 = f
endfor
 Bước 3: kết thúc thuật toán.
Ví dụ: số fibonacci thứ 5000 là:
38789684543883256337019163083259053120821277146462451061605972148955501390440370970108229164
62210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634
13370655865623825465670071252592990385493381392883637834751890876297071203333705292310769300
85180938498018038478139967488817655546537882916442689129803846137789690215022930824756663462
24923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422
89149127310405432875329804427367682297724498774987455569190770388063704683279481135897373999
31101062193081490185708153978543791953056175107610530756887837660336673554452588448862416192
10553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902
42080638258492915645287629157575914234380914230291749108898415520985443248659407979357131684
16928680395453095453886981146650820668628974206393234384884652409887423958738019769938203171
74208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604
639987588046985178408674382863125
2. Cài đặt
Thuật toán tính số fibonacci thứ n:
BigInt fibo = new BigInt("1");

BigInt t1 = new BigInt("1");
BigInt t2 = new BigInt("1");
for (int i = 2; i < n; i++)
{
fibo = t1 + t2;
t1 = t2;
t2 = fibo;
}

3. Đánh giá
Việc tính số fibonacci thứ n chỉ cần thực hiện n – 2 lần phép cộng(f = t1 + t2) vì thế độ
phức tạp của thuật toán là hàm bậc nhất theo n. Tuy vậy tốc độ thực hiện trong thực tế sẽ bị
ảnh hưởng bởi tốc độ thực thi của phép cộng, với t1 và t2 càng lớn thì tốc độ thực thi sẽ giảm
1 cách rõ rệt, bên dưới là đồ thị về số phép toán cần thực hiện(kể cả số phép toán cần thực
hiện của phép cộng) để tính được số fibonacci thứ n.

Hình 4: đồ thị số lần lặp để tính được số fibonacci thứ n

106536
2622572
10469839
261336847
1045142800
0
200000000
400000000
600000000
800000000
1000000000
1200000000

1000 5000 10000 50000 100000
SỐ LẦN LẶP
GIÁ TRỊ N
SỐ FIBONACCI THỨ N
Fibonacci thứ n
KẾT LUẬN
Độ phức tạp của các thuật toán trên đều phụ thuộc vào độ dài của số nhập vào hoặc có thể
phụ thuộc vào giá trị của nó. Trong thực tế, các thuật toán cộng, trừ và nhân có số lần lặp khá ổn
định với những dữ liệu đầu vào khác nhau, tuy vậy thuật toán chia lại có số lần lặp khá biến thiên
với cùng 1 với cùng 1 bộ dữ liệu đầu vào nhưng tổng thể thì số lần lặp vẫn tăng theo chiều dài
chuỗi số đầu vào. Bên dưới là đồ thị so sánh số lần lặp của mỗi phép toán cộng, trừ nhân chia với
số thứ nhất là 98765432112345678910111213141516171819 và số thứ 2 là các số nằm ở trục
hoành của đồ thị.

Hình 5: đồ thị số lần thực thi của các phép tính cộng, trừ, nhân và chia
39 39 39 39 39 39 39 39 39
38 38 38 38 38 38 38 38 38
342
380
456
532
608
684
760
836
912
803
889
1334
1484

1306
1340
1245
1198
1123
0
200
400
600
800
1000
1200
1400
1600
SỐ LẦN LẶP
SỐ THỨ 2
SỐ LẦN THỰC THI CỦA CÁC PHÉP TÍNH
Cộng
Trừ
Nhân
Chia
CÁC NGUỒN THAM KHẢO
[1] Large numbers – Wikipedia.com

[2] C# BigInteger Class – CodeProject.com

[3] Class BigInteger - docs.oracle.com

[4] Long division - Wikipedia.com


[5] Division (mathematics) - Wikipedia.com

[6] Multiple (mathematics) - Wikipedia.com


XIN CHÂN THÀNH CẢM ƠN SỰ QUAN TÂM CỦA QUÝ THẦY CÔ !