Phần 1: Thao tác toán Cộng1. Thuật toánGiả sử chúng ta có một số nguyên (lớn) a=32145; sẽ có rất nhiều cách lưu trữ số nguyên này (do ta quy định), ở đây Peter sẽ đưa ra cách lưu số này qua mảng 1 chiều ngược, cụ thể như sau: a[0]=5, a[1]=4, a[2]=1, a[3]=2 và a[4]=3; nhưng khi xuất thì lại xuất ngược lại so với cách lưu trữ!, số nguyên này có 5 chữ số, khi nhập (input) số này vào chương trình thì chúng ta sẽ dùng dấu khoảng trắng (space) để ngăn cách các chữ số và nhập bình thường theo thứ tự thông thường, ví dụ a=32145 sẽ được nhập vào như sau: 3 2 1 4 5.
Vậy nếu cần thực hiện phép toán Cộng hai số a và b sau đó lưu vào mảng c (kết quả) thì Peter đề xuất các bước (c=a+b):
- Bước 1: Loại bỏ các chữ số 0 vô nghĩa ở 2 mảng a và b.
- Bước 2: Thêm chữ số 0 ở đầu mảng có độ dài ngắn hơn để 2 mảng có cùng độ dài (tức là nếu a=1234, b=21 thì chúng ta thấy: mảng b có 2 phần tử; mảng a có 4 phần tử; vậy để hai mảng này có số phần tử bằng nhau thì chúng ta thêm 2 chữ số 0 nữa vào mảng b; lúc này b=0021).
- Bước 3: Dùng một biến nhớ, ký hiệu là nho, để lưu trữ số nhớ sau mỗi bước tính. Được khởi tạo có giá trị là 0. Trong một bước tính thì ở vị trí thứ i, các số được tính như sau:
- Code:
-
c[i] = (a[i]+b[i]+nho)%10;
nho = (a[i]+b[i]+nho)/10.
Và cuối cùng, nếu vẫn còn nhớ thì chúng ta thêm một phần tử nữa vào mảng c mang giá trị bằng nho.
- Bước 4: Xuất kết quả theo thứ tự ngược của mảng c; đây là kết quả của phép tính.
Để làm các bạn hiểu tôi xin trình bày các bước trên với việc cộng hai số nguyên sau (để tiện không phải viết nhiều tôi sẽ thao tác với 2 số nguyên thông thường....). Thực hiện với 2 số: a=349 và b=35; c=a+b:
- Bước 1: Loại bỏ các chữ số 0 vô nghĩa; cả 2 số này đều không cần bước này.
- Bước 2: Thêm số 0 vào trước mảng b; lúc này b=035.
+ Cách lưu trữ của a là: 9 4 3 (tương ứng a[0]=9, a[1]=4 và a[2]=3).
+ Cách lưu trữ của b là: 5 3 0 (tương ứng b[0]=5, b[1]=3 và b[2]=0).
- Bước 3: Khởi tạo nho=0 và tính c
và nho sau mỗi bước nhỏ:
+ c[0] = (a[0]+b[0]+nho)%10 = (9+5+0)%10 = 4;
nho = (a[0]+b[0]+nho)/10 = (9+5+0)/10 = 1.
+ c[1] = (a[1]+b[1]+nho)%10 = (4+3+1)%10 = 8;
nho = (a[1]+b[1]+nho)/10 = (4+3+1)/10 = 0.
+ c[2] = (a[2]+b[2]+nho)%10 = (3+0+0)%10 = 3;
nho = (a[2]+b[2]+nho)/10 = (3+0+0)/10 = 0.
Vậy mảng c được lưu trữ là: 4 8 3 0.
- Bước 4: Xuất kết quả, sắp xếp ngược lại ta có c=0384 (chính là 384).
[i]2. Tổ chức chương trình theo giải thuậtSau khi phân tích và đưa ra giải thuật chúng ta đi vào việc xây dựng chương trình thực hiện; trong chương trình Peter mạnh dạn đưa biến global (các bạn có thể tuỳ mà làm, thế nào cũng được). Với lưu ý như sau:
- Nhập vào số các chữ số của số trước khi nhập lần lượt các chữ số.
- Nhập vào các chữ số ngăn cách nhau bằng dấu khoảng trắng (space) như đã nói phía trên.
Các bạn tự tìm hiểu chương trình này (có gì cứ góp ý bàn bạc!).
- Code:
-
#include <stdio.h>
#include <conio.h>
int m,n,dem,nho=0,s,i,j,a[100],b[100],c[100]; //Gia su so nguyen lon co 100 chu so; tuy y!
void nhap()
{
printf("Nhap so chu so cua so nguyen a, m= ");
scanf("%d",&m);
printf("Nhap lan luot cac chu so cua a (ngan cach nhau bang space):\n");
for(i=m-1;i>=0;i--)
scanf("%d",&a[i]);
printf("\n\nNhap so chu so cua so nguyen b, n= ");
scanf("%d",&n);
printf("Nhap lan luot cac chu so cua b (ngan cach nhau bang space):\n");
for(i=n-1;i>=0;i--)
scanf("%d",&b[i]);
//Buoc 1: Loai bo cac chu so 0 vo nghia o mang a va b
while((a[m-1]==0)&&(m>0))
m--;
if(m==0)
a[m++]=0;
while((b[n-1]==0)&&(n>0))
n--;
if(n==0)
b[n++]=0;
//Buoc 2: Them cac chu so 0 vao dau cua mang co so phan tu be hon
if(m<n)
for(i=1;i<=n-m;i++)
a[m-1+i]=0;
else
for(i=1;i<=m-n;i++)
b[n-1+i]=0;
if(m<n)m=n;
else
n=m;
}
void cong(int *a,int *b) //Buoc 3: Tinh c[i] va nho
{
for(i=0;i<m;i++)
{
c[i]=(a[i]+b[i]+nho)%10;
nho=(a[i]+b[i]+nho)/10;
}
if(nho>0)
c[m++]=nho;
}
int main()
{
nhap();
cong(a,b);
printf("\n\nTong la: \n");
for(i=m-1;i>=0;i--) //Buoc 4: Xuat ket qua
printf("%d",c[i]);
getch();
return 0;
}