[Programming] Vấn đề : Cộng hai số nguyên lớn ! |
02/02/2007 13:07:50 (+0700) | #1 | 39528 |
newbie_newbie
Member
|
0 |
|
|
Joined: 15/01/2007 22:55:15
Messages: 78
Offline
|
|
Các bạn ơi, cho mình hỏi cách làm bài này tí !
Mình muốn làm 1 bài cộng 2 số lớn thật là lớn ! Vậy, làm thế nào để lưu số lớn đó bây giờ ?
Và khi nhập một số đầu vào rất lớn, làm thế nào để có thể nhận nó ? Nếu dùng kiểu chuỗi thì có thể ép sang kiểu int được ko ?
Các bạn giúp mình với ! |
|
|
|
|
[Question] Re: Vấn đề : Cộng hai số nguyên lớn ! |
02/02/2007 22:17:34 (+0700) | #2 | 39569 |
|
delua
Locked
|
0 |
|
|
Joined: 28/12/2006 00:48:39
Messages: 102
Offline
|
|
Tui là dân mù lập trình.Vô tình thấy source "nhân số lớn".Tôi up lên đây cho bạn.Hy vọng bạn sẽ "biến" nó thành "cộng số lớn"
Code:
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#include<string.h>
int n1,n2,n;
int s1[1000],s2[1000];
char s[1000];
void nhan(void);
void main()
{
int i;
clrscr();
printf("chuong trinh nhan so lon\n");
printf("so thu nhat: ");
gets(s);
n1=strlen(s)-1;
for (i=0;i<=n1;i++) s1[n1-i]=s[i]-48;
printf("so thu hai: ");
gets(s);
n2=strlen(s)-1;
for (i=0;i<=n1;i++) s2[n2-i]=s[i]-48;
printf("\ntich la: ");
nhan();
getch();
}
void nhan(void)
{
int nho,i,bac,tich,j;
int tong[1000]={0},tg[1000]={0};
int nmax,ntg;
n=0;bac=1;tich=1;nho=0;nmax=0;
for (j=0;j<=n2;j++)
{
bac=j;
for (i=0;i<=n1;i++)
{
tich=s1[i]*s2[j]+nho;
tg[i+bac]=tich%10;
nho=tich/10;
}
ntg=n1+bac;
while (nho)
{
ntg++;
tg[ntg]=nho%10;
nho/=10;
}
for (i=bac;i<=ntg;i++)
{
tong[i]+=tg[i]+nho;
nho=tong[i]/10;
tong[i]%=10;
}
while (nho)
{
ntg++;
tong[ntg]=tong[ntg]+nho%10;
nho=nho/10;
}
if (ntg>nmax) nmax=ntg;
}
for (i=nmax;i>=0;i--) printf("%d",tong[i]);
}
Thân, |
|
|
|
|
[Question] Vấn đề : Cộng hai số nguyên lớn ! |
02/02/2007 22:21:06 (+0700) | #3 | 39570 |
|
delua
Locked
|
0 |
|
|
Joined: 28/12/2006 00:48:39
Messages: 102
Offline
|
|
Sorry ban quản trị,không phải câu bài.Mà vì khi post xong thì mới nhớ lại cần nói vài câu với bạn newbie_newbie.Mà ko có chức năng edit nên đành post 1 bài nữa.Sory all !
================
Nguyên tắc làm thì giống như bạn đã nói vậy.Nhập vào dạng chuỗi.Sau đó chuyển sang dạng nhị phân để làm. |
|
|
|
|
[Question] Vấn đề : Cộng hai số nguyên lớn ! |
03/02/2007 01:20:48 (+0700) | #4 | 39617 |
|
K4i
Moderator
|
Joined: 18/04/2006 09:32:13
Messages: 635
Location: Underground
Offline
|
|
newbie_newbie wrote:
Các bạn ơi, cho mình hỏi cách làm bài này tí !
Mình muốn làm 1 bài cộng 2 số lớn thật là lớn ! Vậy, làm thế nào để lưu số lớn đó bây giờ ?
Và khi nhập một số đầu vào rất lớn, làm thế nào để có thể nhận nó ? Nếu dùng kiểu chuỗi thì có thể ép sang kiểu int được ko ?
Các bạn giúp mình với !
Về vấn đề cộng số lớn thì bạn phải nghĩ cách lưu được số lớn đó vào trong bộ nhớ. Vê lưu số lớn thì có 2 cách: bạn có thể dùng một mảng số nguyên hoặc dùng một xâu kí tự để lưu nó lại.
==> chính vì thế, khi nhập số lớn cái bạn nhập vào là một xâu kí tự (hoặc một mảng số nguyên). Ví dụ nhé: bạn định nhập vào số 1234 ==> bạn cần có một mảng ít nhất có 4 phần tử để lưu 1, 2, 3, 4 hoặc một string "1234"; Mỗi thằng có một lợi điểm riêng, như dùng mảng số nguyên thì không phải mất công chuyển đổi từ kiểu char sang int để tính toán, .. ==> cái này thì tùy vào khả năng của bạn.
Đó là việc lưu trữ. Còn về việc tính toán thì lúc này bạn có thể sử dụng cách nhân thủ công của ta: tức là cộng lần lượt từ phải sang trái, và có nhớ khi cộng.
Ví dụ: 1234 + 3456 thì lấy 4 + 6 = 10, viết 0, nhớ 1, sau đó là 3 + 5 nhớ 1 là 9, viết 9 nhớ 0, cứ tương tự như vậy cho đến khi duyệt hết tất cả các phẩn tử của mảng (hoặc string). Sau đó in ra kết quả.
Với các số lớn vượt quá kiểu của int (4 bytes) thì việc ép kiểu là không thể. (nguyên nhân rất đơn giản, nó sẽ làm tràn bộ nhớ của int). Thông thường với các bài toán số lớn, mình thường dùng một class số lớn, trong đó mình định nghĩa lại toàn bộ các toán tử +, -, *, / (giờ mới làm đến thế). Tốt nhất là khi dùng đến số lớn, thì bạn nên quên đi việc ép kiểu, bắt buộc xây dựng lại từ đầu.
Đây mới chỉ là bài toán cộng 2 số dương. Bạn có thể mở rộng bài toán này cho các số nguyên và các phép tính khác.
Thân |
|
Sống là để không chết chứ không phải để trở thành anh hùng |
|
|
|
[Question] Vấn đề : Cộng hai số nguyên lớn ! |
03/02/2007 05:20:11 (+0700) | #5 | 39647 |
newbie_newbie
Member
|
0 |
|
|
Joined: 15/01/2007 22:55:15
Messages: 78
Offline
|
|
K4i wrote:
Về vấn đề cộng số lớn thì bạn phải nghĩ cách lưu được số lớn đó vào trong bộ nhớ. Vê lưu số lớn thì có 2 cách: bạn có thể dùng một mảng số nguyên hoặc dùng một xâu kí tự để lưu nó lại.
==> chính vì thế, khi nhập số lớn cái bạn nhập vào là một xâu kí tự (hoặc một mảng số nguyên). Ví dụ nhé: bạn định nhập vào số 1234 ==> bạn cần có một mảng ít nhất có 4 phần tử để lưu 1, 2, 3, 4 hoặc một string "1234"; Mỗi thằng có một lợi điểm riêng, như dùng mảng số nguyên thì không phải mất công chuyển đổi từ kiểu char sang int để tính toán, .. ==> cái này thì tùy vào khả năng của bạn.
Bạn có thể nói rõ hơn về cách xử lý dữ liệu đầu vào bằng cách dùng mảng không ? Ví dụ như mình nhập 1 số là 1234, vậy làm sao để có phần tử của mảng a như sau : a[0] là 4, a[1] là 3.... ? Vì nó là 1 số liền nhau mà ?
VÀ theo cách thứ 2 mà bạn nói ! Làm thế nào để ép kiểu từ string sang int ?
K4i wrote:
Với các số lớn vượt quá kiểu của int (4 bytes) thì việc ép kiểu là không thể. (nguyên nhân rất đơn giản, nó sẽ làm tràn bộ nhớ của int). Thông thường với các bài toán số lớn, mình thường dùng một class số lớn, trong đó mình định nghĩa lại toàn bộ các toán tử +, -, *, / (giờ mới làm đến thế). Tốt nhất là khi dùng đến số lớn, thì bạn nên quên đi việc ép kiểu, bắt buộc xây dựng lại từ đầu.
Thân
Vì sao ko thể ép kiểu vậy bạn ? Vì ý tưởng của mình là nếu như nhập 1 số là 1234, thì mình sẽ dùng 1 mảng string để lưu trữ nó, như vậy, mình sẽ ép kiểu từng phần tử a[o] -> a[3] sang string ! như thế, sẽ ko làm trản bộ nhớ đúng ko bạn ? Không biết là ý tưởng của mình có thực hiện được không ? Mình chưa hiểu rõ ý bạn nói ?
Cám ơn hai bạn nhiều lắm !
|
|
|
|
|
[Question] Vấn đề : Cộng hai số nguyên lớn ! |
03/02/2007 10:18:28 (+0700) | #6 | 39690 |
|
K4i
Moderator
|
Joined: 18/04/2006 09:32:13
Messages: 635
Location: Underground
Offline
|
|
Bạn có thể nói rõ hơn về cách xử lý dữ liệu đầu vào bằng cách dùng mảng không ? Ví dụ như mình nhập 1 số là 1234, vậy làm sao để có phần tử của mảng a như sau : a[0] là 4, a[1] là 3.... ? Vì nó là 1 số liền nhau mà ?
VÀ theo cách thứ 2 mà bạn nói ! Làm thế nào để ép kiểu từ string sang int ?
==> đọc toàn bộ dữ liệu đầu vào là một string sau đó, convert từng thằng kí tự một sang kiểu int và gán vào mảng.
Còn cái ép kiểu. Mình không hiểu cái ép kiểu của bạn nghĩa là gì?
Vì sao ko thể ép kiểu vậy bạn ? Vì ý tưởng của mình là nếu như nhập 1 số là 1234, thì mình sẽ dùng 1 mảng string để lưu trữ nó, như vậy, mình sẽ ép kiểu từng phần tử a[o] -> a[3] sang string ! như thế, sẽ ko làm trản bộ nhớ đúng ko bạn ? Không biết là ý tưởng của mình có thực hiện được không ? Mình chưa hiểu rõ ý bạn nói ?
Cám ơn hai bạn nhiều lắm !
Nhắc lại nhé: string là một mảng kí tự , còn từng phần tử của nó vẫn là kiểu char và mình nghĩ bạn nên đọc lại cách biểu diễn số trong máy tính: tại sao nói kiểu int có 4 bytes, một số nguyên như int a = 3 được biểu diễn như thế nào trong máy tính (số nhị phân) và tại sao lại xuất hiện hiện tượng tràn bộ nhớ khi mà nhập một số quá lớn), bạn cũng nên đọc lại cách ép kiểu trong C/C++ nó là như thế nào. Bởi vì bạn chưa hiểu cách làm việc với số lớn: biểu diễn lại số đó theo cách mà mình hiểu và máy tính hiểu.
Thân. |
|
Sống là để không chết chứ không phải để trở thành anh hùng |
|
|
|
[Question] Vấn đề : Cộng hai số nguyên lớn ! |
03/02/2007 12:58:52 (+0700) | #7 | 39728 |
newbie_newbie
Member
|
0 |
|
|
Joined: 15/01/2007 22:55:15
Messages: 78
Offline
|
|
[quote=K4i]
==> đọc toàn bộ dữ liệu đầu vào là một string sau đó, convert từng thằng kí tự một sang kiểu int và gán vào mảng.
[/quote]
Convert như thế nào bạn ? Hay bạn cho mình xin tài liệu nói về vấn đề này cũng được ! Sẵn tiện, bạn cho mình xin tài liệu về string, char với ! mình còn yếu về vấn đề này lắm ! Cám ơn bạn ! Chắc bài tập này lại để sang năm wá ! Hic hic !
Còn cái ép kiểu. Mình không hiểu cái ép kiểu của bạn nghĩa là gì?
Còn nếu như với số nguyên quá lớn, làm thế nào để tạo một định nghĩa mới để lưu trữ số lớn hơn ?
Cám ơn bạn nhiều !
|
|
|
|
|
[Question] Vấn đề : Cộng hai số nguyên lớn ! |
04/02/2007 12:08:39 (+0700) | #8 | 39921 |
|
hakuso
HVA Friend
|
Joined: 04/01/2004 13:28:06
Messages: 287
Location: làng Đo Đo
Offline
|
|
@newbie_newbie: nếu bạn có nhu cầu xử lý số thật lớn trong chương trình thì có thể dùng thư viện http://www.swox.com/gmp/ |
|
Live, fight, work and study |
|
|
|
[Question] Vấn đề : Cộng hai số nguyên lớn ! |
19/02/2007 02:07:03 (+0700) | #9 | 41950 |
quoctuan90
Member
|
0 |
|
|
Joined: 20/09/2006 16:19:38
Messages: 4
Offline
|
|
Quay về học ASM đi bà con , Hoc mấy ngôn ngữ cấp cao làm B*** gì , nó thiếu thốn đủ mọi thứ , tương tác với phần cúng khó bỏ mẹ ... MR TUAN NGUYEN |
|
|
|
|
[Question] Vấn đề : Cộng hai số nguyên lớn ! |
21/02/2007 12:57:38 (+0700) | #10 | 42206 |
hoangmac
Member
|
0 |
|
|
Joined: 08/07/2006 15:53:56
Messages: 50
Location: hcm
Offline
|
|
newbie_newbie wrote:
Các bạn ơi, cho mình hỏi cách làm bài này tí !
Mình muốn làm 1 bài cộng 2 số lớn thật là lớn ! Vậy, làm thế nào để lưu số lớn đó bây giờ ? theo mình thì dùng chuỗi
Và khi nhập một số đầu vào rất lớn, làm thế nào để có thể nhận nó ? Nếu dùng kiểu chuỗi thì có thể ép sang kiểu int được ko ?có thể ép chuỗi thành int dc, chỉ cần lấy mỗi ký tự trong chuỗi làm phép toán trừ cho số không là ok
Các bạn giúp mình với !
đây là đoạn code mình viết cho bồ, có lẽ chưa gôd lắm nhưng cũng xài tạm dc :lol
Code:
#include<string.h>
#include<stdio.h>
#include<conio.h>
#define in "input_CONG.txt"
#define out "output.txt"
#define max 50
int n1,n2;//do dai cua 2 dai so nguyen
char s1[max],s2[max];//luu 2 dai so nguyen"output.txt"
void swap(char &a,char &b)
{
char temp=a;
a=b;
b=temp;
}
void DaoChuoi()
{
for(int i=0, j=n1-1; i<n1/2; i++,j--)
swap(s1[i],s1[j]);
for(i=0, j=n2-1; i<n2/2; i++,j--)
swap(s2[i],s2[j]);
}
void nhap()
{
FILE *f=fopen(in,"rt");
fgets(s1,max,f); n1=strlen(s1);
if(s1[n1-1]=='\n') n1--;
fgets(s2,max,f); n2=strlen(s2);
if(s2[n2-1]=='\n') n2--;
DaoChuoi();
fclose(f);
}
void xuat()
{
FILE *f=fopen(out,"wt");
for(int i=n1-1; i>=0; i--)
fprintf(f,"%c",s1[i]);
fclose(f);
}
int max_so()
{
if(n1>n2)
{
for(int k=n2; k<n1; k++)
s2[k]='0';
return n1;
}
else
if(n1<n2)
{
for(int k=n1; k<n2; k++)
s1[k]='0';
return n2;
}
else
return n1;
// return n1>n2?n1:n2;
}
void cong()
{
int nho=0;
n1=max_so();
for(int i=0; i<n1; i++)
{
int temp=(s1[i]-'0')+(s2[i]-'0')+nho;
nho=temp/10;
s1[i]=temp%10+'0';
}
if(nho==1) s1[n1++]=nho+'0';
}
void main()
{
nhap();
cong();
xuat();
}
|
|
|
|
|
[Question] Vấn đề : Cộng hai số nguyên lớn ! |
22/02/2007 00:38:25 (+0700) | #11 | 42264 |
|
K4i
Moderator
|
Joined: 18/04/2006 09:32:13
Messages: 635
Location: Underground
Offline
|
|
Có 2 ý kiến về phần này như sau:
1. Không cần thiết phải sử dụng hàm DaoChuoi() và swap().
2. Nên comment để cho mọi người dễ đọc và dễ hiểu bạn định làm cái gì
|
|
Sống là để không chết chứ không phải để trở thành anh hùng |
|
|
|
[Question] Vấn đề : Cộng hai số nguyên lớn ! |
22/02/2007 14:10:54 (+0700) | #12 | 42425 |
hoangmac
Member
|
0 |
|
|
Joined: 08/07/2006 15:53:56
Messages: 50
Location: hcm
Offline
|
|
cần thủ tục DaoChuoi() và thủ tục swap() chứ
tớ đâu tạo thêm một chuỗi để lưu kq, tớ lưu thẳng lên s1. vì:
n1<n2: (s1="6789" s2="56789")cậu ko thể cộng s1[n1]=s1[n1]+s2[n2] vì khi n1=0 thì n2=1 ko lẽ bỏ số đó.
n1=n2: nho=1 thì lại chen nhó vào vtrí s1[0] phiền lắm
tớ tiếc kiệm bộ nhớ nhưng làm cho ctrinh chạy ... chậm & rắc rối vô duyên )
có lẽ tớ nên tạo thêm s3 để lưu kq thì code sẽ đơn giản hơn...thank vì đã góp ý
vì đoạn code trên vô duyên wa nên khỏi comment |
|
|
|
|
[Question] Vấn đề : Cộng hai số nguyên lớn ! |
24/02/2007 13:41:56 (+0700) | #13 | 42788 |
|
K4i
Moderator
|
Joined: 18/04/2006 09:32:13
Messages: 635
Location: Underground
Offline
|
|
|
Sống là để không chết chứ không phải để trở thành anh hùng |
|
|
|
[Question] Vấn đề : Cộng hai số nguyên lớn ! |
25/02/2007 03:51:00 (+0700) | #14 | 42897 |
hoangmac
Member
|
0 |
|
|
Joined: 08/07/2006 15:53:56
Messages: 50
Location: hcm
Offline
|
|
Cậu thử nghĩ xem liệu có bỏ được không còn về lưu kết quả thì tốt nhất nên lưu ra một mảng mới là tốt nhất không nên để kết quả trùng lên biến cũ. Cậu sẽ hiểu tại sao lại thế khi cậu làm phép chia .
à, nếu có chuỗi s3 để lưu kq thì bỏ 2 thù tục kia dc
Còn việc xét số lớn nhỏ hơn thì không cần thiết nếu như cậu chỉ tập trung làm số dương, còn số âm thì cần đó.
tớ chỉ xét chiều dài 2 số thôi
Điểm lưu ý khác, chương trình vô duyên hay không vô duyên thì chưa cần biết nhưng theo ý mình thì cậu nên tôn trọng người đọc bằng cách comment để cho người ta hiểu cậu đã làm cái gì thay vì đau đầu dịch lại code của cậu. Nó cũng chứng tỏ khả năng làm việc cẩn thận của cậu (tuy nhiên comment đừng quá dài dòng
thừa nhận với bác là HOANGMAC rất cẩu thả, sẽ rút kinh nghiệm
|
|
|
|
|
[Question] Vấn đề : Cộng hai số nguyên lớn ! |
02/03/2007 00:54:46 (+0700) | #15 | 43939 |
NEY26514
Member
|
0 |
|
|
Joined: 27/03/2004 20:08:52
Messages: 11
Offline
|
|
cho tui hỏi một câu nha. Nếu các bác dùng mảng thì với số có 100 chử số cộng với số có 100 chử số là đơn giản. nhưng nâng cao hơn là nhân 2 số lớn thì sao? chẳng lẻ dùng như phép cộng sao? theo tôi không được.
|
|
|
|
|
[Question] Re: Vấn đề : Cộng hai số nguyên lớn ! |
02/03/2007 04:20:47 (+0700) | #16 | 43976 |
|
K4i
Moderator
|
Joined: 18/04/2006 09:32:13
Messages: 635
Location: Underground
Offline
|
|
==> ai bảo không được :? |
|
Sống là để không chết chứ không phải để trở thành anh hùng |
|
|
|
[Question] Re: Vấn đề : Cộng hai số nguyên lớn ! |
18/03/2007 23:48:55 (+0700) | #17 | 47634 |
|
bongtoicodon
Member
|
0 |
|
|
Joined: 20/02/2007 21:23:03
Messages: 14
Offline
|
|
Tiểu đệ có một chương trình có thể tính được 1000! và trên nữa,cũng có liên quan đến phép cộng hai số nguyên cực lớn đấy ... You có muốn xem thử không,tiểu đệ sẽ gửi cho (Viết bằng VB6.0) |
|
|
|
|
[Question] Vấn đề : Cộng hai số nguyên lớn ! |
25/03/2007 14:46:39 (+0700) | #18 | 49212 |
cockvn
Member
|
0 |
|
|
Joined: 10/03/2007 18:00:35
Messages: 14
Offline
|
|
Mình nghĩ cộng 2 số nguyên lớn với nhau thì cậu nên dùng 2 xâu để lưu 2 số bạn nhập vào cùng 1 xâu để lưu kết quả.
Sau đó bạn sẽ cộng 2 số này như là khi ta cộng bằng tay tức là bận cộng từ cuối các xâu này về trước kiểu như khi ta mới tập cộng vậy.(Chuyển từ char -> int và ngược lại)
Mình nghĩ vấn đề cộng 2 số nguyên lớn này bạn có thể phát triển thêm thành nhân 2 số nguyên lớn với nhau với ý tưởng là chia phép nhân thành nhiều phép cộng,dùng thêm 1 hàm nhân số có 1 chữ số với 1 dãy số. |
|
|
|
|
[Programming] Vấn đề : Cộng hai số nguyên lớn ! |
28/10/2010 16:48:48 (+0700) | #19 | 223867 |
beginnerC++
Member
|
0 |
|
|
Joined: 24/10/2010 17:48:19
Messages: 1
Offline
|
|
Cái trang web của bạn newbie_newbie sao mình ko vô được? |
|
|
[Programming] Vấn đề : Cộng hai số nguyên lớn ! |
17/04/2014 09:24:33 (+0700) | #20 | 280346 |
|
echtroi
Member
|
0 |
|
|
Joined: 09/04/2014 21:27:20
Messages: 7
Offline
|
|
Ngày trước mình cũng cài đặt 1 lần. Chia sẻ với bạn mã nguồn http://tuvantinhoc.vn/chia-se-ma-nguon-cai-dat-so-nguyen-lon/ |
|
|
Users currently in here |
1 Anonymous
|
|
Powered by JForum - Extended by HVAOnline
hvaonline.net | hvaforum.net | hvazone.net | hvanews.net | vnhacker.org
1999 - 2013 ©
v2012|0504|218|
|
|