模拟法計算大數加減乘除 (附帶例題)

模拟法計算大數加減乘除就是模拟列豎式的方法計算

大數加法

模拟豎式加法

首先是第一步先最低位對齊吧

例如：
1 2 3 4 5 6 7 8 9
  2 0 0 0 1 1 2 8
我是這樣子在實作的
strrev(a)//char的反轉函數
reverse(a.begin(),a.end());//string的反轉函數
反轉過來就是這個
9 8 7 6 5 4 3 2 1
8 2 1 1 0 0 0 2

第二步就是上下相加，滿10進位

例如：
1 2 3 4 5 6 7 8 9
  2 0 0 0 1 1 2 8
-----------------
            1 1
1 4 3 4 5 7 9 1 7
因為我已經反轉過來了，那就是這樣的
9 8 7 6 5 4 3 2 1
8 2 1 1 0 0 0 2 
-----------------
  1 1
7 1 9 7 5 4 3 4 1
這樣看起來很好加吧，一個for循環跑到天荒地老，（當然了，要是沒得加就得退出了）
然後在反轉一下就可以了
1 4 3 4 5 7 9 1 7

很簡單吧，這樣就計算出A+B了

例題

http://sustoj.com/JudgeOnline/problem.php?id=1952

AC code:

#include <stdio.h>//c 版
#include <string.h>
#define maxn 10000500
char ans[maxn];
char *strrev(char *str){
      char *p1, *p2;
      if (! str || ! *str){
            return str;
      }
      for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2){
            *p1 ^= *p2;
            *p2 ^= *p1;
            *p1 ^= *p2;
      }
      return str;
}
const char*num_plus(char *a,char *b){
  memset(ans,0,sizeof ans);
	int lena=strlen(a);
	int lenb=strlen(b);
	strrev(a);
	strrev(b);
	int yu=0;
  for(int i=0;;i++){
    if(i<lena&&i<lenb){
      ans[i]=(yu+a[i]-'0'+b[i]-'0')%10+'0';
      yu=(yu+a[i]-'0'+b[i]-'0')/10;
    }else if(i<lena){
      ans[i]=(yu+a[i]-'0')%10+'0';
      yu=(yu+a[i]-'0')/10;
    }else if(i<lenb){
      ans[i]=(yu+b[i]-'0')%10+'0';
      yu=(yu+b[i]-'0')/10;
    }else if(yu!=0){
      ans[i]=yu%10+'0';
      yu=yu/10;
    }else break;
  }
	strrev(ans);
	return ans;
}
char a[maxn],b[maxn];
int main(){
	while(~scanf("%s %s", a, b)){
    printf("%s\n", num_plus(a,b));
  }
  return 0;
}

#include <cstring>//c++ 版
#include <iostream>
#include <algorithm>
using namespace std;
string ans;
string num_push(string a,string b){
	ans.clear();
  int lena=a.size();
  int lenb=b.size();
  reverse(a.begin(),a.end());
  reverse(b.begin(),b.end());
  int yu=0;
  for(int i=0;;i++){
    if(i<lena&&i<lenb){
      ans+=(yu+a[i]-'0'+b[i]-'0')%10+'0';
      yu=(yu+a[i]-'0'+b[i]-'0')/10;
    }else if(i<lena){
      ans+=(yu+a[i]-'0')%10+'0';
      yu=(yu+a[i]-'0')/10;
    }else if(i<lenb){
      ans+=(yu+b[i]-'0')%10+'0';
      yu=(yu+b[i]-'0')/10;
    }else if(yu!=0){
      ans+=yu%10+'0';
      yu=yu/10;
    }else break;
  }
  reverse(ans.begin(),ans.end());
  return ans;
}
string a,b;
int main(){
  while(cin>>a>>b){
    cout<<num_push(a,b)<<endl;
  }
  return 0;
}

大數減法

模拟豎式減法

首先是第一步要判讀大小吧（因為我隻學過大減小的豎式計算）

因為沒有前置零且都是正整數
是以誰位數多誰就大
要是位數一樣的話，
那就是誰的那字典序大誰就大
用到了 strcmp(a,b)  //char 類型的比較函數

字典序定義：

模拟法計算大數加減乘除 (附帶例題)

第二步就是最低位對齊

例如：
1 2 3 4 5 6 7 8 9
  2 0 0 0 1 1 2 8
我是這樣子在實作的
strrev(a)//char的反轉函數
reverse(a.begin(),a.end());//string的反轉函數
反轉過來就是這個
9 8 7 6 5 4 3 2 1
8 2 1 1 0 0 0 2

第三步就是上下相減了，借位

例如：
1 2 3 4 5 6 7 8 9
  2 0 0 0 1 1 2 8
-----------------
1 0 3 4 5 5 6 6 1
因為我已經反轉過來了，那就是這樣的
9 8 7 6 5 4 3 2 1
8 2 1 1 0 0 0 2 
-----------------
1 6 6 5 5 4 3 0 1
這樣看起來很好減吧，一個for循環跑到天荒地老，（當然了，要是沒得減就得退出了）
然後在反轉一下就可以了
1 0 3 4 5 5 6 6 1

借位

1 0 0 0 0
  9 9 9 9
----------
0 0 0 0 1
我是這樣實作借位的，先反轉過來
0 0 0 0 1
9 9 9 9
----------
因為0減不過9
是以要向後借位
是以第一位借到10後就變成了1
第二位是'0'的話就繼續向後借，
反正上面的肯定大于下面的，是以肯定能借到的
借到就減一就行了
就是這個樣子了

0 0 0 0 1
9 9 9 9
----------
1 0 0 0 0
翻轉過來就是
0 0 0 0 1 了
當然不能要前置0，是以我在反轉前就把前置零去掉，不要忘了要是小減大就要添上'-'

例題:

http://sustoj.com/JudgeOnline/problem.php?id=1948

AC code:

#include <stdio.h> //c 版
#include <string.h>
#define maxn 100000
char ans[maxn];
char* strrev(char* s)
{
    /* h指向s的頭部 */
    char* h = s;
    char* t = s;
    char ch;
    /* t指向s的尾部 */
    while(*t++){};
    t--;    /* 與t++抵消 */
    t--;    /* 回跳過結束符'\0' */
    /* 當h和t未重合時，交換它們所指向的字元 */
    while(h < t)
    {
        ch = *h;
        *h++ = *t;    /* h向尾部移動 */
        *t-- = ch;    /* t向頭部移動 */
    }
    return(s);
}
int judge(char *a, char *b){
  int lena=strlen(a);
  int lenb=strlen(b);
  if(lena>lenb) return 1;
  if(lena<lenb) return -1;
  return strcmp(a,b);
}
const char *num_sub(char *a, char *b){
  char aa[maxn],bb[maxn];
  memset(aa,0,sizeof aa);
  memset(bb,0,sizeof bb);
  memset(ans,0,sizeof ans);
  char *as=ans;
  int cnt=judge(a,b);
  bool bo=false;
  if(cnt>0){
    strcpy(aa,a);
    strcpy(bb,b);
    bo=false;
  }else if(cnt<0){
    strcpy(aa,b);
    strcpy(bb,a);
    bo=true;
  }else{
    ans[0]='0';
    return as;
  }
  int lena=strlen(aa);
  int lenb=strlen(bb);
  strrev(aa);
  strrev(bb);
  int i;
  for(i=0;;i++){
    if(i<lena&&i<lenb){
      if(aa[i]>=bb[i]){
        ans[i]=aa[i]-bb[i]+'0';
      }else {
        ans[i]=aa[i]-bb[i]+10+'0';
        for(int j=i+1;;j++){
          if(aa[j]=='0') aa[j]='9';
          else{
            aa[j]--;
            break;
          }
        }
      }
    }else if(i<lena){
      ans[i]=aa[i];
    }else if(i<lenb){
      ans[i]=bb[i];
    }else break;
  }
  while(i--){
    ans[i+1]='\0';
    if(ans[i]-'0'>0){
      break;
    }
  }
  if(bo) ans[i+1]='-';
  strrev(ans);
  return as;
}
char a[maxn],b[maxn];
int main(){
  while(~scanf("%s %s", a, b)){
    printf("%s\n", num_sub(a,b));
  }
  return 0;
}

#include <bits/stdc++.h> //c++ 版
using namespace std;
#define maxn 100000
string ans;
int judge(string a,string b){
  int lena=a.size();
  int lenb=b.size();
  if(lena>lenb) return 1;
  if(lena<lenb) return -1;
  if(a>b) return 1;
  if(a==b) return 0;
  if(a<b) return -1;
}
string num_mul(string a,string b){
  string aa,bb;
  aa.clear();
  bb.clear();
  ans.clear();
  bool bo;
  int cnt=judge(a,b);
  if(cnt>0){
    aa=a;
    bb=b;
    bo=false;
  }else if(cnt<0){
    aa=b;
    bb=a;
    bo=true;
  }else if(cnt==0){
    ans+='0';
    return ans;
  }
  reverse(aa.begin(),aa.end());
  reverse(bb.begin(),bb.end());
  int lena=aa.size();
  int lenb=bb.size();
  int i;
  for(i=0;;i++){
    if(i<lena&&i<lenb){
      if(aa[i]>=bb[i]){
        ans+=aa[i]-bb[i]+'0';
      }else{
        ans+=aa[i]-bb[i]+10+'0';
        for(int j=i+1;;j++){
          if(aa[j]=='0') aa[j]='9';
          else {
            aa[j]--;
            break;
          }
        }
      }
    }else if(i<lena){
      ans+=aa[i];
    }else if(i<lenb){
      ans+=bb[i];
    }else break;
  }
  while(i--){
    if(ans[i]-'0'>0){
      break;
    }
  }
  ans.erase(i+1,lena-i);
  if(bo) ans+='-';
  reverse(ans.begin(),ans.end());
  return ans;
}
string a,b;
int main(){
  while(cin>>a>>b){
      cout<<num_mul(a,b)<<endl;
  }
  return 0;
}

大數乘法

第一步還是要最低位對齊

例如：
1 2 3 4 5 6 7 8 9
  2 0 0 0 1 1 2 8
我是這樣子在實作的
strrev(a)//char的反轉函數
reverse(a.begin(),a.end());//string的反轉函數
反轉過來就是這個
9 8 7 6 5 4 3 2 1
8 2 1 1 0 0 0 2

第二步就是上下相乘，向後進位

9  8  7  6  5  4  3  2  1
 8  2  1  1  0  0  0  2
------------------
72 64 56 48 40 32 24 16  8---------8*(987654321)
   18 16 14 12 10  8  6  4  2 ---------2*(987654321)
       9  8  7  6  5  4  3  2  1---------1*(987654321)
          9  8  7  6  5  4  3  2  1---------1*(987654321)
             0  0  0  0  0  0  0  0  0---------0*(987654321)
                0  0  0  0  0  0  0  0  0---------0*(987654321)
                   0  0  0  0  0  0  0  0  0---------0*(987654321)
                     18 16 14 12 10  8  6  4  2 ---------2*(987654321)
-------------------------------------------------------------------------
72 82 81 79 67 55 43 49 35 21 15 11  8  6  4  2 
-------------------------------------------------------------------------
    7  8  8  8  7  6  4  5  4  2  1  1 
 2  9  9  7  5  2  9  3  0  5  7  2  9  6  4  2 
 反轉過來就是這樣了
 2469275039257992

例題

http://sustoj.com/JudgeOnline/problem.php?id=1985

AC code:

#include <stdio.h>//c 版
#include <string.h>
using namespace std;
#define maxn 500000
int ans[maxn];
char num[maxn];
char *strrev(char *str)
{
      char *p1, *p2;
      if (! str || ! *str)
      {
            return str;
      }
      for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2)
      {
            *p1 ^= *p2;
            *p2 ^= *p1;
            *p1 ^= *p2;
      }
      return str;
}
char* num_mul(char *a, char *b){
  memset(ans,0,sizeof ans);
  memset(num,0,sizeof num);
  char *as=num;
  int nu=0;
  memset(ans,0,sizeof ans);
  int lena=strlen(a);
  int lenb=strlen(b);
  strrev(a);
  strrev(b);
  for(int i=0;i<lena;i++){
    for(int j=0;j<lenb;j++){
        ans[i+j]+=(a[i]-'0')*(b[j]-'0');
    }
  }
  int i;
  int yu=0;
  int len=lena+lenb-1;
  for(i=0;;i++){
    if(i<len||yu!=0){
      yu=ans[i]+yu;
      ans[i]=yu%10;
      yu=yu/10;
    }else break;
  }
  while(i--){
    num[nu++]=ans[i]+'0';
  }
  return num;
}
char a[maxn],b[maxn];
int main(){
  while(~scanf("%s %s", a, b)){
    if(strcmp(a,"0")==0) printf("0\n");
    else if(strcmp(b,"0")==0) printf("0\n");
    else printf("%s\n", num_mul(a,b));
  }
  return 0;
}

#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 100000
int ans[maxn];
string num;
string num_mul(string a,string b){
  memset(ans,0,sizeof ans);
  num.clear();
  int lena=a.size();
  int lenb=b.size();
  reverse(a.begin(),a.end());
  reverse(b.begin(),b.end());
  for(int i=0;i<lena;i++){
    for(int j=0;j<lenb;j++){
      ans[i+j]+=(a[i]-'0')*(b[j]-'0');
    }
  }
  int yu=0;
  int i;
  int len=lena+lenb-1;
  for(i=0;;i++){
    if(i<len||yu!=0){
      yu=ans[i]+yu;
      ans[i]=yu%10;
      yu=yu/10;
    }else break;
  }
  while(i--){
    num+=ans[i]+'0';
  }
  return num;
}
string a,b;
int main(){
  while(cin>>a>>b){
    cout<<num_mul(a,b)<<endl;
  }
  return 0;
}

大數除法

已經學會大數減法了，那就不用再去模拟大數除法了

可以一直減下去用大數減了多少步，但這樣會有缺陷，比如說

10000000000 1 \frac{10000000000}{1} 110000000000 那就要跑10000000000次，這樣肯定會逾時的

那可以換一種方法

比如說 a b \frac{a}{b} ba

先給分母 b b b末尾補零直到與 a a a長度相同，得到 b ′ b^{'} b′，

比較 a a a和 b ′ b^{'} b′的大小，大的話一直減，減到 a a a小于 b ′ b^{'} b′，然後再給 b ′ b^{'} b′去掉末尾的零

一直循環上面布置，直到 b ′ b^{'} b′還原到b的時候停止

這樣可能會出現前置零，那就去掉前置零就好了

比如

10000000000 1 \frac{10000000000}{1} 110000000000 那就跑11次就好了

例題

http://sustoj.com/JudgeOnline/problem.php?id=1986

AC code :

#include <bits/stdc++.h>
using namespace std;
#define maxn 1000
char anss[maxn];
char ans[maxn];
char *strrev(char *str)
{
      char *p1, *p2;
      if (! str || ! *str)
      {
            return str;
      }
      for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2)
      {
            *p1 ^= *p2;
            *p2 ^= *p1;
            *p1 ^= *p2;
      }
      return str;
}
int judge(char *a, char *b){
  int lena=strlen(a);
  int lenb=strlen(b);
  if(lena>lenb) return 1;
  if(lena<lenb) return -1;
  return strcmp(a,b);
}
const char *num_sub(char *a, char *b){
  char aa[maxn],bb[maxn];
  memset(aa,0,sizeof aa);
  memset(bb,0,sizeof bb);
  memset(ans,0,sizeof ans);
  char *as=ans;
  int cnt=judge(a,b);
  bool bo=false;
  if(cnt>0){
    strcpy(aa,a);
    strcpy(bb,b);
    bo=false;
  }else if(cnt<0){
    strcpy(aa,b);
    strcpy(bb,a);
    bo=true;
  }else{
    ans[0]='0';
    return as;
  }
  int lena=strlen(aa);
  int lenb=strlen(bb);
  strrev(aa);
  strrev(bb);
  int i;
  for(i=0;;i++){
    if(i<lena&&i<lenb){
      if(aa[i]>=bb[i]){
        ans[i]=aa[i]-bb[i]+'0';
      }else {
        ans[i]=aa[i]-bb[i]+10+'0';
        for(int j=i+1;;j++){
          if(aa[j]=='0') aa[j]='9';
          else{
            aa[j]--;
            break;
          }
        }
      }
    }else if(i<lena){
      ans[i]=aa[i];
    }else if(i<lenb){
      ans[i]=bb[i];
    }else break;
  }
  while(i--){
    ans[i+1]='\0';
    if(ans[i]-'0'>0){
      break;
    }
  }
  if(bo) ans[i+1]='-';
  strrev(ans);
  return as;
}
char *num_div(char *a, char *b){
  memset(anss,0,sizeof anss);
  int nu=0;
  int lena=strlen(a);
  int lenb=strlen(b);
  for(int i=lenb;i<lena;i++){
    b[i]='0';
  }
  while(lena-->=lenb){
    int i=0;
    while(judge(a,b)>=0){
      i++;
      strcpy(a,num_sub(a,b));
    }
    anss[nu++]=i+'0';
    b[lena]='\0';
  }
  if(anss[0]=='\0'){
    anss[0]='0';
    return anss;
  }
  if(anss[0]=='0')
  return anss+1;
  return anss;
}
char a[maxn],b[maxn];
int main(){
  while(~scanf("%s %s", a, b)){
    printf("%s\n", num_div(a,b));
    cout<<a<<endl;
  }
}

#include <bits/stdc++.h>
using namespace std;
#define maxn 100000
string ans;
string anss;
string yu;
int judge(string a,string b){
  int lena=a.size();
  int lenb=b.size();
  if(lena>lenb) return 1;
  if(lena<lenb) return -1;
  if(a>b) return 1;
  if(a==b) return 0;
  if(a<b) return -1;
}
string num_mul(string a,string b){
  string aa,bb;
  aa.clear();
  bb.clear();
  ans.clear();
  bool bo;
  int cnt=judge(a,b);
  if(cnt>0){
    aa=a;
    bb=b;
    bo=false;
  }else if(cnt<0){
    aa=b;
    bb=a;
    bo=true;
  }else if(cnt==0){
    ans+='0';
    return ans;
  }
  reverse(aa.begin(),aa.end());
  reverse(bb.begin(),bb.end());
  int lena=aa.size();
  int lenb=bb.size();
  int i;
  for(i=0;;i++){
    if(i<lena&&i<lenb){
      if(aa[i]>=bb[i]){
        ans+=aa[i]-bb[i]+'0';
      }else{
        ans+=aa[i]-bb[i]+10+'0';
        for(int j=i+1;;j++){
          if(aa[j]=='0') aa[j]='9';
          else {
            aa[j]--;
            break;
          }
        }
      }
    }else if(i<lena){
      ans+=aa[i];
    }else if(i<lenb){
      ans+=bb[i];
    }else break;
  }
  while(i--){
    if(ans[i]-'0'>0){
      break;
    }
  }
  ans.erase(i+1,lena-i);
  if(bo) ans+='-';
  reverse(ans.begin(),ans.end());
  return ans;
}
string num_div(string a,string b){
	anss.clear();
	int lena=a.size();
	int lenb=b.size();
	for(int i=lenb;i<lena;i++){
		b+='0';
	}
	while(lena-->=lenb){
		int i=0;
		while(judge(a,b)>=0){
			a=num_mul(a,b);
			i++;
		}
		anss+=(i+'0');
		b.erase(lena);
	}
	yu=a;
	if(anss.size()==0){
		anss+='0';
		return anss;
	}
	if(anss[0]=='0')
		anss.erase(0,1);
  return anss;
}
string a,b;
int main(){
  while(cin>>a>>b){
      cout<<num_div(a,b)<<endl;
			cout<<yu<<endl;
  }
  return 0;
}

模拟法計算大數加減乘除 (附帶例題)

大數加法

大數減法

大數乘法

AC code:

大數除法

AC code :

繼續閱讀

藍橋杯算法提高 ADV-197 P1001 大數乘法

ACM--遞推加大數--HDOJ 1865--1string--水 1sting

ACdream OJ 1154 Lowbit Sum

SDUT 2143 圖結構練習——最短路徑（Dijkstra 單源最短路徑求解）

大數加法_每天一道算法題(js)(1)——大數相乘

51NOD-1005 大數加法【大數 Python、Java】

最小生成樹詳解

UVA 10604 - Chemical Reaction (狀态壓縮)

杭電 ACM 1008

sicily1031Campus之最短路徑解題報告sicily1031Campus之最短路徑解題報告

poj 2240 bellman-ford

2019南大計算機夏令營機考第一題第二題第三題

Valentine's Day Round 1001 Ferries Wheel

POJ 3159 Candies（Dijkstra算法+優先隊列+堆）

POJ 2389 Bull Math （FFT）

51NOD-1027 大數乘法【大數 Python、Java】