簡介
大數運算,
顧名思義,就是很大的數值的數進行一系列的運算。
我們知道,在
數學中,數值的大小是沒有上限的,但是在計算機中,由於字長的限制,計算機所能表示的範圍是有限的,當我們對比較小的數進行運算時,如:1234+5678,這樣的數值並沒有超出計算機的表示範圍,所以可以運算。但是當我們在實際的套用中進行大量的數據處理時,會發現參與運算的數往往超過計算機的基本數據類型的表示範圍,比如說,在天文學上,如果一個星球距離我們為100萬光年,那么我們將其化簡為公里,或者是米的時候,我們會發現這是一個很大的數。這樣計算機將無法對其進行直接計算。
可能我們認為實際套用中的大數也不過就是幾百位而已,實際上,在某些領域裡,甚至可能出現幾百萬位的數據進行運算,這是我們很難想像的。如果沒有
計算機,那么計算效率可想而知。
既然在計算機中無法直接表示,那么大數到底如何進行運算呢,學習過數據結構的都知道線性表,將大數拆分然後存儲線上性表中,不失為一個很好的辦法。
大數除法,可以類比人類手算,添位比較取商,中間結果與除數相減所得到的差參與下一輪運算,直到結束。這裡需要注意添位時,商有時需要補零,而且除法運算需要使用加、減、乘、比較運算。
原理
利用數組連續性,將大數每一位上的數字單獨取出放入對應的數組格中,然後再對每一位做單獨的加減乘運算。形象的說,類似於國小學習加減乘所列的式子。
套用
HDUOJ——1002 A + B Problem II
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 69615Accepted Submission(s): 12678
Problem Description
I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B.
Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000.
Output
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line is the an equation "A + B = Sum", Sum means the result of A + B. Note there are some spaces int the equation. Output a blank line between two test cases.
Sample Input
2
1 2
112233445566778899 998877665544332211
Sample Output
Case 1:
1 + 2 = 3
Case 2:
112233445566778899 + 998877665544332211 = 1111111111111111110
Author
Ignatius.L
HDUOJ 1002 代碼
#include <stdio.h>#include <string.h>int main(){ char str1[1001],str2[1001]; int t,i,len_str1,len_str2,len_max,num=1,k; scanf("%d",&t); while(t--) { int a[1001]={0},b[1001]={0},c[1001]={0}; scanf("%s",str1); len_str1=strlen(str1); for(i=0;i<=len_str1-1;++i) a[i]=str1[len_str1-1-i]-'0'; scanf("%s",str2); len_str2=strlen(str2); for(i=0;i<=len_str2-1;++i) b[i]=str2[len_str2-1-i]-'0'; if(len_str1>len_str2) len_max=len_str1; else len_max=len_str2; k=0; for(i=0;i<=len_max-1;++i) { c[i]=(a[i]+b[i]+k)%10; k=(a[i]+b[i]+k)/10; } if(k!=0) c[len_max]=1; printf("Case%d:\n",num); num++; printf("%s+%s=",str1,str2); if(c[len_max]==1) printf("1"); for(i=len_max-1;i>=0;--i) { printf("%d",c[i]); } printf("\n"); //if(t>=1) //printf("\n"); } return 0;}