Bố cục của chủ đề: Chủ đề sẽ hướng dẫn các bạn qua 4 phần:
Code:
- Phần 1: Thao tác toán Cộng
- Phần 2: Thao tác toán Trừ
- Phần 3: Thao tác toán Nhân
- Phần 4: Thao tác toán Chia
1. Thuật toán
Giả 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.
- 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[i] 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).
2. Tổ chức chương trình theo giải thuật
Sau 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.
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;
}
peterdrew
nguồn: congdongCviet)
---------- Bài thêm lúc 14:29 ---------- Bài trước là lúc 14:21 ----------Phần 2: Thao tác phép toán Trừ
1. Thuật toán
Lưu trữ các số hạng của phép trừ cũng thực hiện tương tự như thực hiện với phép toán cộng, khi xuất thì cũng xuất theo thứ tự ngược lại; các chữ số cũng được ngăn cách nhau bằng một khoảng trắng (space).
Việc tiếp là kiểm tra xem số trừ lớn hơn hay nhỏ hơn số bị trừ (?!), để thực hiện điều này chúng ta phải xây dựng một thủ tục kiểm tra, nếu lớn hơn thì thực hiện thêm một thao tác nữa là đảo lại hai mảng này và thực hiện bình thường theo thuật toán sau và sau đó thêm dấu “-“ vào kết quả: Giả sử cần thực hiện phép toán Trừ 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:
+ Nếu a[i]-nho>=b[i] thì
Code:
c[i]=(a[i]-b[i]-nho)%10;
nho=0.
Code:
c[i]=(a[i]+10-nho-b[i])%10;
nho=1.
Sau đây Peter sẽ ví dụ cho các bạn hiểu về thuật toán trên: Ta cần thực hiện a-b=c với a=349 và b=35.
- 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[i] và nho:
+ Kiểm tra a[0]-nho và b[0]:
a[0]-nho=9-0=9; b[0]=5 nên a[0]-nho>b[0], vậy:
c[0] = (a[0]-b[0]-nho)%10 = (9-5-0)%10 = 4;
nho = 0.
+ Kiểm tra a[1]-nho và b[1]:
a[1]-nho=4-0=4; b[1]=3 nên a[1]-nho>b[1], vậy:
c[1] = (a[1]-b[1]-nho)%10 = (4-3-0)%10 = 1;
nho = 0.
+ Kiểm tra a[2]-nho và b[2]:
a[2]-nho=3-0=3; b[2]=0 nên a[2]-nho>b[2], vậy:
c[2] = (a[2]-b[2]-nho)%10 = (3-0-0)%10 = 3;
nho = 0.
Vậy mảng c được lưu trữ là: 4 1 3.
- Bước 4: Xuất kết quả, sắp xếp ngược lại ta có c=314.
Rất lấy làm không tự nhiên khi lấy một ví dụ không có tính tổng quát, tuy nhiên nó cũng là ví dụ để minh chứng cho thuật toán thôi! Peter mong các bạn tiếp tục lấy các ví dụ khác để hiểu kỹ hơn về thuật toán này, còn lại hãy tham khảo code dưới.
2. Tổ chức chương trình theo giải thuật
Sau 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; chúng ta phải viết thủ tục kiểm tra so sánh hai số trừ và số bị trừ; chương trình được thực hiện như sau:
Code:
#include <stdio.h>
#include <conio.h>
int m,n,dem,nho=0,i,a[100],b[100],c[100];
void Input()
{
printf("Nhap so cac chu so cua a: ");
scanf("%d",&m);
printf("\nNhap so a (cac chu so cach nhau boi dau space): ");
for(i=m-1;i>=0;i--)
scanf("%d",&a[i]);
printf("\n\nNhap so cac chu so cua b: ");
scanf("%d",&n);
printf("\nNhap so b (cac chu so cach nhau boi dau space): ");
for(i=n-1;i>=0;i--)
scanf("%d",&b[i]);
if(m>n)
for(i=1;i<=m-n;i++)
b[n-1+i]=0;
else
for(i=1;i<=n-m;i++)
a[m-1+i]=0;
if(m<n)
m=n;
else n=m;
}
bool Sosanh()
{
i=m-1;
while((a[i]==b[i])&&(i>=0))
i--;
if((i<0)||(a[i]>b[i]))
return true;
else
return false;
}
void Tru(int *a,int *b)
{
int tam;
if(!Sosanh())
{
printf("-");
for(i=0;i<n;i++)
{
tam=a[i];
a[i]=b[i];
b[i]=tam;
}
}
for(i=0;i<m;i++)
if(a[i]-nho>=b[i])
{
c[i]=(a[i]-b[i]-nho)%10;
nho=0;
}
else
{
c[i]=(a[i]+10-b[i]-nho)%10;
nho=1;
}
while(c[m-1]==0)
m--;
if(m==0)c[m++]=0;
}
int main()
{
Input();
Tru(a,b);
for(i=m-1;i>=0;i--)
printf("%d",c[i]);
getch();
return 0;
}
---------- Bài thêm lúc 14:33 ---------- Bài trước là lúc 14:29 ----------Phần 3: Thao tác phép toán Nhân
1. Thuật toán
Giả sử a có m chữ số, b có n chữ số; chúng ta lưu trữ số a và b như sau: Cho a và b có cùng chiều dài là m+n-1 bằng cách thêm vào n-1 số 0 trước a; m-1 số 0 trước b; sau đó a và b được lưu trữ giống như phép toán cộng và trừ; ví dụ a=349, b=35 thì m=3, n=2 và a lúc này có thêm 2-1=1 chữ số 0 đứng trước và trở thành 0349; b tương tự thành 0035; vậy a được lưu trữ thành 9 4 3 0; còn b được lưu trữ là 5 3 0 0.
Vậy tại sao chúng ta lại quy về chiều dài cùng nhau của a và b như vậy? Nếu các bạn để ý thì thấy rằng tích của 2 số có số các chữ số max nhất cũng chính bằng tổng số chữ số của 2 số hạng trừ với 1 nữa, chúng ta quy về như vậy để tiện lợi cho thực hiện các bước tính sau này.
Thuật toán trên được thực hiện qua các bước sau (c=a*b):
- Bước 1: Lưu trữ a và b theo quy tắc trên!
- Bước 2: Khởi tạo nho=0. Tính c[i] và nho theo công thức sau: Đặt s[i]=Tổng j chạy từ 0 đến i của a[j]*b[i-j]; với i là một số nguyên nằm trong đoạn [0,m+n-2].
Code:
c[i]=(s[i]+nho)%10;
nho=s[i]/10.
- Bước 3: Xuất kết quả theo thứ tự ngược lại!
Ví dụ cho dễ hiểu nào?!!! Lấy a=349, b=35.
- Bước 1: Lưu trữ a=9 4 3 0 và b=5 3 0 0.
Vậy a[0]=9; a[1]=4; a[2]=3; a[3]=0 và b[0]=5; b[1]=3; b[2]=0; b[3]=0.
- Bước 2: nho=0. Tính c[i] và nho:
+ s[0]=a[0]*b[0]=9*5=45;
c[0]=(s[0]+nho)%10=(45+0)%10=5;
nho=s[0]/10=4;
+ s[1]=a[0]*b[1]+a[1]*b[0]=9*3+4*5=47;
c[1]=(s[1]+nho)%10=(47+4)%10=1;
nho=s[1]/10=5;
+ s[2]=a[0]*b[2]+a[1]*b[1]+a[2]*b[0]=9*0+4*3+3*5=27;
c[2]=(s[2]+nho)%10=(27+5)%10=2;
nho=s[2]/10=3;
+ s[3]=a[0]*b[3]+a[1]*b[2]+a[2]*b[1]]+a[3]*b[0]=9*0+4*0+3*3+0*5=9;
c[3]=(s[3]+nho)%10=(9+3)%10=2;
nho=s[3]/10=1;
Đến đây thì thuật toán kết thúc; do nho=1 nên ta phải thêm phần tử nhớ này vào mảng c; và c[4]=1.
- Bước 3: Xuất mảng c=5 1 2 2 1; kết quả được sắp xếp lại thành 12215 (đây chính là kết quả của phép nhân 349 với 35)
2. Tổ chức chương trình theo giải thuật
Với việc phân tích thuật toán trên thì sau đây là code của phép toán nhân 2 số nguyên lớn:
Code:
#include <stdio.h>
#include <conio.h>
int m,n,chdaichung,nho=0,s,i,j,a[100],b[100],c[100];
void Nhan(int *a,int *b)
{
chdaichung=m+n-1;
for(i=0;i<chdaichung;i++)
{
s=0;
for(j=0;j<=i;j++)
s+=a[j]*b[i-j];
c[i]=(s+nho)%10;
nho=(s+nho)/10;
}
if(nho>0)
c[chdaichung++]=nho;
}
void Input()
{
printf("Nhap so cac chu so cua a: ");
scanf("%d",&m);
printf("\nNhap so a (cac chu so cach nhau space): ");
for(i=m-1;i>=0;i--)
scanf("%d",&a[i]);
printf("\n\nNhap so cac chu so cua b: ");
scanf("%d",&n);
printf("\nNhap so b (cac chu so cach nhau space): ");
for(i=n-1;i>=0;i--)
scanf("%d",&b[i]);
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;
}
int main()
{
Input();
for(i=1;i<=n;i++)
a[m-1+i]=0;
for(i=1;i<=m;i++)
b[n-1+i]=0;
Nhan(a,b);
for(i=chdaichung-1;i>=0;i--)
printf("%d",c[i]);
getch();
return 0;
}
---------- Bài thêm lúc 14:34 ---------- Bài trước là lúc 14:33 ----------Phần 4: Thao tác toán Chia
1. Thuật toán
Với phép chia thì thuật toán sẽ phức tạp hơn thuật toán của 3 phép toán trên (Cộng, Trừ và Nhân); việc lưu trữ cũng bị biến đổi, cụ thể như sau:
a, Lưu trữ các số hạng tham gia toán chia
Giả sử ta cần kết quả c=a/b; và phép toán này có dư. Các số a, b, c được lưu trữ thành mảng 1 chiều thuận (ngược lại với cách lưu trữ các số hạng của 3 phép toán trước đó), đặc điểm là dùng mảng a để lưu trữ số dư qua từng bước và mảng c để lưu trữ thương!
b, Các khái niệm dùng trong bài toán
Ví dụ một phép chia: 236/13; các bước thực hiện như sau:
- Lấy 23 chia cho 13 (do 2 không chia hết nên phải thêm 3); kết quả được 1 và dư là 10.
- Tiếp tục gán 6 sang 10 ta được 106; chia cho 13 được 8 và dư là 2.
Các số 23 và 106 được gọi là Các phần nhỏ của các bước chia, gọi tắt là Phần nhỏ.
Các số 1 và 2 là các số dư của các Phần nhỏ cho 13 được gọi là các Số dư phần nhỏ.
Ta quy ước một khái niệm gọi là Độ lệch, trong một bước chia mà có k chữ số đầu tiên của a không chia hết cho b thì độ lệch được tăng lên 1 đơn vị, ban đầu chưa chia thì quy ước giá trị của độ lệch là 0. Ký hiệu độ lệch là d; như vậy giả sử a có m chữ số, b có n chữ số, thế thì Độ lệch lớn nhất để chia a cho b là m-n. Khi d>m-n thì phép chia bị kết thúc.
Với ví dụ trên thì số 2 đầu tiên của a không chia hết cho 13 (b) nên độ lệch tăng lên 1, tức d=1; sau khi thêm 3 thì chia được; dư 10 thêm 6 ta vẫn chia được, vậy thuật toán kết thúc và độ lệch d của phép chia luôn là 1.(???).
c, Thuật toán chính
Thuật toán của phép chia cực kỳ phức tạp; có lẽ Peter cũng không thể nêu cụ thể được (các bạn hãy bàn thêm); sau đây là một số nét chính:
- Bước 1: Nếu k chữ số đầu của a nhỏ hơn b thì tăng d lên 1.
- Bước 2: Trong khi d<=m-n thực hiện:
+ Dùng biến Tam (tạm) để lưu trữ thương của các Phần nhỏ cho b; trừ dần ở Phần nhỏ đã xét, lưu số lần trừ được vào biến Tam. Đó là kết quả mỗi chữ số trong thương ở mỗi lần chia.
+ Thêm vào c giá trị của Tam và tăng d lên 1.
+ Nếu a[i]=0 thì tăng i (loại bỏ 1 chữ số 0, không tính đến nó nữa nhưng chú ý là chỉ bỏ 1 chữ số 0, vì nếu còn 1 chữ số nữa thì ở bước tiếp theo Tam=0 và vẫn có kết quả).
- Bước 3: Kiểm tra và xóa các chữ số 0 vô nghĩa ở số dư.
- Bước 4: Xuất kết quả.
Peter không ví dụ thuật toán trên nữa; các bạn hãy tìm hiểu chúng trong đoạn code dưới đây và tham gia thảo luận!
2. Tổ chức chương trình theo giải thuật
Thuật toán trên vẫn còn “mập mờ”! Gây khó hiểu cho nhiều bạn, và đây là code mẫu để các bạn tham khảo thuật toán:
Code:
#include <stdio.h>
#include <conio.h>
int m,n,i,j,Tam,d,t,a[100],b[100],c[100];
bool duoc;
bool Sosanh(int *a,int*b,int d)
{
int i;
if((a[d-1]!=0)&&(d>0))
return true;
for(i=0;i<n;i++)
if(a[i+d]>b[i])
return true;
else
if(a[i+d]<b[i])
return false;
return true;
}
void Tru(int *a,int*b,int d)
{
int i,nho;
nho=0;
for(i=n-1;i>=0;i--)
if(a[i+d]-nho<b[i])
{
a[i+d]=a[i+d]+10-nho-b[i];
nho=1;
}
else
{
a[i+d]=a[i+d]-nho-b[i];
nho=0;
}
if(nho==1)
a[d-1]--;
}
void Ktraso0()
{
duoc=true;
int j=0,k;
while((b[j]==0)&&(j<n))
j++;
if(j==n)
duoc=false;
else
{
for(k=j;k<n;k++)
b[k-j]=b[k];
n-=j;
}
j=0;
while((a[j]==0)&&(j<m))
j++;
if(j==m)
{
m=1;a[0]=0;
}
else
{
for(k=j;k<m;k++)
a[k-j]=a[k];
m-=j;
}
}
void Chia(int *a,int *b)
{
if(m>=n)
{
if(!Sosanh(a,b,d))
d++;
while(d<=m-n)
{
Tam=0;
while(Sosanh(a,b,d))
{
Tam++;
Tru(a,b,d);
}
c[t++]=Tam;
d++;
if(a[i]==0)
i++;
}
if(t==0)
c[t++]=0;
}
else
c[t++]=0;
while((a[i]==0)&&(i<m))
i++;
if(i==m)
a[--i]=0;
}
int main()
{
printf("Nhap so cac chu so cua a: ");
scanf("%d",&m);
printf("\nNhap so a (cac chu so cach nhau bang space): ");
for(i=0;i<m;i++)
scanf("%d",&a[i]);
printf("\n\nNhap so cac chu so cua b: ");
scanf("%d",&n);
printf("\nNhap so b (cac chu so cach nhau bang space): ");
for(i=0;i<n;i++)
scanf("%d",&b[i]);
d=0;
i=0;
t=0;
Ktraso0();
if(duoc)
{
Chia(a,b);
printf("\nThuong cua phep chia la: ");
for(j=0;j<t;j++)
printf("%d",c[j]);
printf("\nSo du cua phep chia: ");
for(j=i;j<m;j++)
printf("%d",a[j]);
}
else
printf("Chia cho 0!!!! Vui long lam lai....");
getch();
return 0;
}
(tác giả:
peterdrew
nguồn: congdongCviet)
0 nhận xét:
Đăng nhận xét