#include <iostream>
#include <stdio.h>
#include <cstring>
#include<cassert>
#include <cmath>using namespace std;
//大數運算最關鍵的是用進制理解，就是把一個數組元素表示的最大值作為一個進制；如此，最容易的大數運算也是最耗費空間的就是一個元素表示一位數字，即用十進制表示；還有一種折中的方案，是一個元素最大能表示9999，如此用的是10000進制，則下面的baseNum = 10000;本文的實現的是最省空間的方法，一個元素就是一個unsigned short,這樣就表示用2^16進制
const int MaxShort = 100;//最多有MaxShort * 2個字節//如果要表示64位int，MaxShort = 4
const int baseNum = pow(2.0,16.0);
const int Shift = 16;
typedef unsigned short Unshort;typedef struct BigNum
{int m_len;//可以通過m_len的正負，判斷大數的正負。本程序未實現Unshort m_data[MaxShort];
}BigNum;void Reverse(char *src);
void GetAbsDecNum(BigNum &bg,char *tgt);void PrintData(BigNum &a)
{for (int i=0;i<a.m_len;++i){cout<<a.m_data[i]<<" ";}cout<<endl;
}
void Print(BigNum &a)
{char t[MaxShort];memset(t,0,sizeof(t));GetAbsDecNum(a,t);Reverse(t);cout<<t<<endl;
}
int AbsComp(BigNum &a,BigNum &b)//a>b,1;a = b,0;a<b,-1
{if(a.m_len>b.m_len)return 1;if (a.m_len<b.m_len)return -1;int size = a.m_len -1;for (int i=size;i>=0;--i){if(a.m_data[i]>b.m_data[i])return 1;if(a.m_data[i] <b.m_data[i])return -1;}return 0;}BigNum CreateAbsBigNum(char *src)//低位放前，高位放后；
{BigNum bg;Unshort *data = bg.m_data;int b = 0;while (src[0]!='\0'){int i = 0;int reminder = 0;while (src[i]!='\0'){int divident = src[i] - '0' + reminder * 10;reminder = divident % baseNum;src[i] = divident / baseNum + '0';++i;}data[b++] = reminder;while (*src =='0')++src;}bg.m_len = b;return bg;}BigNum AbsMinus(BigNum &bg1,BigNum &bg2)//bg1 >bg2
{int left = bg1.m_len;int right = bg2.m_len;int carry = 0;BigNum bg;for (int i=0;i<right;++i){int tmp = bg1.m_data[i] - bg2.m_data[i] - carry;if(tmp<0){carry = 1;bg.m_data[i] = baseNum + tmp;}else{bg.m_data[i] = tmp;carry = 0;}}for (int i= right;i<left;++i){int tmp = bg1.m_data[i] - carry;if (tmp <0){carry = 1;bg.m_data[i] = baseNum +tmp;}else{bg.m_data[i] = tmp;carry = 0;}}bg.m_len = left;while (bg.m_len>=0 && bg.m_data[bg.m_len -1]==0){--bg.m_len;}return bg;}int AbsMinus(BigNum &bg1,int n,BigNum &bg2)//必須保證bg1的前n位的數要大于等于bg2//返回減少的位數
{if(n<bg2.m_len){cerr<<"minus error\n";exit(1);}int size = (bg1.m_len >n) ?n:bg1.m_len;int beg = bg1.m_len -size;int len2 = bg2.m_len;int len1 = bg1.m_len;int carry = 0;for (int i=0;i<len2;++i){int tmp = bg1.m_data[i+beg] - bg2.m_data[i] - carry;if (tmp < 0){carry = 1;tmp +=baseNum;}elsecarry = 0;bg1.m_data[i+beg] = tmp;}for (int i = len2 + beg;i<len1;++i){int tmp = bg1.m_data[i] -carry;if(tmp<0){carry = 1;tmp +=baseNum;}elsecarry = 0;bg1.m_data[i] = tmp;}while (bg1.m_len>=0 && bg1.m_data[bg1.m_len - 1] ==0)--bg1.m_len;return len1 - bg1.m_len;}bool AbsComp(BigNum &a,int n,BigNum &b)//大數的前n位數與b比較大小;a>=b返回true
{int size = (a.m_len>n)? n:a.m_len;if(size > b.m_len)return true;if(size <b.m_len )return false;int end = a.m_len - size;for (int i=a.m_len -1;i>=end;--i){if(a.m_data[i]>b.m_data[i-end])return true;if(a.m_data[i] < b.m_data[i-end])return false;}return true;
}BigNum AbsDiv(BigNum &bg1,BigNum &bg2)//返回商，bg1變為余數;被除數的位數為n,除數的位數為m,則商的位數最多為n-m+1
{//bg1 >=bg2BigNum c;memset(c.m_data,0,sizeof(c.m_data));int len2= bg2.m_len;int cLen = bg1.m_len -len2 ;int i=0;while(AbsComp(bg1,bg2)>=0){//cout<<"first while:"<<++i<<endl;int len1=bg1.m_len;int indx = len1 - len2;int n = len2;if(!AbsComp(bg1,len2,bg2)){--indx;++n;}//cout<<"n = "<<n<<endl;Unshort count = 0;while (AbsComp(bg1,n,bg2)){//cout<<"second while : n = "<<n<<endl;++count;//cout<<count<<endl;/*BigNum preBg1 = bg1;BigNum preBg2 = bg2;cout<<"pre \n";Print(preBg1);Print(preBg2);*/int tmp = AbsMinus(bg1,n,bg2);/*cout<<"after \n";preBg1 = bg1;preBg2 = bg2;Print(preBg1);Print(preBg2);*/n -= tmp;}//cout<<count<<endl;c.m_data[indx] = count;}while(cLen>=0 && c.m_data[cLen] ==0)--cLen;c.m_len = cLen +1;return c;
}BigNum AbsAdd(BigNum &bg1,BigNum &bg2)
{int left = bg1.m_len;int right = bg2.m_len;int size = left;int maxLen = right;BigNum *bgmax = &bg2;if(size>right){size = right;maxLen = left;bgmax = &bg1;}int carry = 0;BigNum bg;for (int i=0;i<size;++i){int tmp = bg1.m_data[i] + bg2.m_data[i] + carry;//carry = tmp /baseNum;carry = tmp>>Shift;//bg.m_data[i] = tmp &(1<<Shift - 1);bg.m_data[i] = tmp & 0xffff;}for (int i = size;i<maxLen;++i){int tmp = bgmax->m_data[i] + carry;carry = tmp>>Shift;//carry = tmp /baseNum;//bg.m_data[i] = tmp &(1<<Shift - 1);bg.m_data[i] = tmp & 0xffff;}if (carry){bg.m_data[maxLen] = 1;++maxLen;}bg.m_len = maxLen;return bg;
}BigNum AbsMul(BigNum &bg1,BigNum &bg2)
{BigNum bg;memset(bg.m_data,0,sizeof(bg.m_data));int i,j;for (i=0;i<bg1.m_len;++i){size_t carry = 0;for (j=0;j <bg2.m_len;++j){size_t tmp = bg.m_data[i+j] + bg1.m_data[i] * bg2.m_data[j] + carry;bg.m_data[i+j] = tmp %baseNum;carry = tmp /baseNum;}if (carry >0){bg.m_data[i+j] += carry; }}if(bg.m_data[bg1.m_len+bg2.m_len -1] > 0)bg.m_len = bg1.m_len+bg2.m_len;elsebg.m_len = bg1.m_len+bg2.m_len -1;return bg;}void GetAbsDecNum(BigNum &bg,char *tgt)
{int size = bg.m_len;Unshort *data = bg.m_data;int b=0;while (size>0){int i = size - 1;int reminder = 0;while (i>=0){int divident = data[i] + reminder * baseNum;reminder = divident % 10;data[i] = divident /10;--i;}tgt[b++] = reminder + '0';while(size>0 && data[size -1]==0)--size;}tgt[b] = '\0';
}void Reverse(char *src)
{int size = strlen(src);int beg = size/2 -1;for (;beg>=0;--beg){int sym = size -beg -1;char tmp = src[beg];src[beg] = src[sym];src[sym] = tmp;}
}int main()
{char t[100];memset(t,0,sizeof(t));char s[] = "6430006453235007";//6430006453235007BigNum bg = CreateAbsBigNum(s);//PrintData(bg); //BigNum bgg = bg;//Print(bg);//GetAbsDecNum(bg,t);//Reverse(t);//cout<<t<<endl;memset(t,0,sizeof(t)); char s1[]="1234567932211123423411431421246";//1234567932211123423411431421246//112126430006453235007BigNum bg1 = CreateAbsBigNum(s1);//PrintData(bg1);//BigNum bg11 = bg1;//Print(bg11);//GetAbsDecNum(bg1,t);//Reverse(t);//cout<<t<<endl;BigNum bg2 = AbsDiv(bg1,bg);memset(t,0,sizeof(t));GetAbsDecNum(bg2,t);Reverse(t);cout<<t<<endl;
}
主要參考：
http://hi.baidu.com/erennetwork/blog/item/7fcfe31164dac8134a90a7c2.html
大數除法應該是最難實現的了，假設數組a除以b，實現它有兩種方式：
1：用a-=b，循環，直到a<b，記下來執行多少次，則為計算結果；
2：模擬現實，我們手算時是怎么算的，程序就怎么寫，
假設a={2 4 2 3 1}，b={2 3}，結果result={0 0 0 0 0}：
先取a[0]a[1]即24，減去b一次，得a={0 1 2 3 1}，result={0 1 0 0 0}；
再取a[1]a[2]即12，發現它小于b，則多取一位，取a[1]a[2]a[3]即123，減b五次，得a={0 0 0 8 1}，result={0 1 0 5 0}；
再取a[3]a[4]即81，減b三次，得a={0 0 0 1 2}，result={0 1 0 5 3}。
如果按照方法一計算，效率是無法容忍的。
假如用11111除以1，方法一要計算11111次，而方法二則只要5次。
下面是方法二的代碼，經過了簡單的測試（沒做數據校驗，假設數據都是正常的）：
bool compare(int a[],int n,int b[],int m)//當a>=b時，返回true
{
?? ?int i=0;
?? ?int j=0;
?? ?int temp_n=n;
?? ?int temp_m=m;
?? ?while(a[i]==0)
?? ?{
?? ??? ?i++;
?? ??? ?temp_n--;
?? ?}
?? ?while(b[j]==0)
?? ?{
?? ??? ?j++;
?? ??? ?temp_m--;
?? ?}
?? ?if(temp_n>temp_m)
?? ??? ?return true;
?? ?else if(temp_n<temp_m)
?? ??? ?return false;
?? ?else
?? ?{
?? ??? ?for(i,j;i<n,j<m;i++,j++)
?? ??? ?{
?? ??? ??? ?if(a[i]>b[j])return true;
?? ??? ??? ?if(a[i]<b[j])return false;
?? ??? ?}
?? ??? ?return true;
?? ?}
}
void div(int a[],int n,int b[],int m)
{
?? ?int *result;
?? ?int *temp;
?? ?int start=0;
?? ?int end=start+m;
?? ?int i;
?? ?int flg=0;
?? ?int min=0;
?? ?result=new int[n];
?? ?for(i=0;i<n;i++)
?? ??? ?result[i]=0;
?? ?temp=new int[m+1];
?? ?for(i=0;i<m+1;i++)
?? ??? ?temp[i]=0;
?? ?while(compare(a,n,b,m))
?? ?{
?? ??? ?while(a[start]==0)
?? ??? ?{
?? ??? ??? ?start++;
?? ??? ??? ?end++;
?? ??? ?}
?? ??? ?for(i=start;i<end;i++)
?? ??? ?{
?? ??? ??? ?temp[i-start+1]=a[i];
?? ??? ?}
?? ??? ?if(!compare(temp,m+1,b,m))
?? ??? ?{
?? ??? ??? ?end++;
?? ??? ??? ?for(i=start;i<end;i++)
?? ??? ??? ??? ?temp[i-start]=a[i];
?? ??? ?}
?? ??? ?while(compare(temp,m+1,b,m))
?? ??? ?{
?? ??? ??? ?flg=0;
?? ??? ??? ?for(i=m;i>=1;i--)
?? ??? ??? ?{
?? ??? ??? ??? ?min=temp[i]-b[i-1]-flg;
?? ??? ??? ??? ?if(min<0)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?min+=10;
?? ??? ??? ??? ??? ?flg=1;
?? ??? ??? ??? ?}
??????????????? else
??????????????????? flg=0;
?? ??? ??? ???? temp[i]=min;
?? ??? ??? ?}
?? ??? ??? ?temp[i]-=flg;
?? ??? ??? ?result[end-1]++;
?? ??? ?}
?? ??? ?if(end-start==m)
?? ??? ?{
?? ??? ??? ?for(i=start;i<end;i++)
?? ??? ??? ?{
?? ??? ??? ??? ?a[i]=temp[i+1-start];
?? ??? ??? ??? ?temp[i+1-start]=0;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?for(i=start;i<end;i++)
?? ??? ??? ?{
?? ??? ??? ??? ?a[i]=temp[i-start];
?? ??? ??? ??? ?temp[i-start]=0;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?start++;
?? ??? ?end=start+m;
?? ?}
?? ?for(i=0;i<n;i++)
?? ??? ?cout<<result[i];
?? ?cout<<endl;
?? ?delete result;
?? ?delete temp;
}
總結
以上是生活随笔為你收集整理的大数运算--除法的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
