C++实现大数除法

2024-04-20 12:18

文章标签 c++ 实现大数除法

本文主要是介绍C++实现大数除法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题外话

大数除法无疑是大数操作里最麻烦的一项，写大数不实现除法无异于画龙无鳞。

思路

最原始的，脑子最容易冒出来的思路，是一下一下的减，看能累计减多少次，最后的总次数就是结果，但这样的效率实在太慢。但我们可以一次性减去除数的1，10，100，1000倍，只要它在当前倍数下比被除数小。
例如 1210 3 ，121大于300，我们直接剪去300，给结果加100，这样的话，减的次数会大大减小。
基本的思想就是这样，具体细节见代码，这里不再赘述

进一步优化的方案

上文所述，时间复杂度最坏情况是 9(n-m)*m (解的最坏位数为n-m位，每一位的解最多要减9次，每剪一次需要O(m))
当n,m为万级时，效率仍不尽人意。看大牛代码，发现有这样一个优化的方案。
我们正常用数组来表式大数时，是按照10进制来保存的，我们可以用比如10000来保存，那么长度为n的大数，长度就变为n/4
时间复杂度为原来的1/8

代码(未优化)

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <string.h>
#include <set>
#include <stack>
#include <stdlib.h>
#include <time.h>using namespace std;const int N = 100009;struct Node
{int d[N];int len;Node() {memset(d, 0, sizeof(d));len=1;}Node(char *s){memset(d, 0, sizeof(d));len = strlen(s);int i = 0;while(s[i] != '\0'){d[len-i-1] = s[i] - '0';++i;}}int cmp(const Node &t){int l = this->len - t.len;if(l < 0)return -1;int i;for(i=t.len-1;i>=0;i--){if(this->d[i+l] < t.d[i])break;else if(this->d[i+l] > t.d[i]){return l;}}if(i < 0)return l;return l-1;}void change(int pos){this->d[pos] += 1;int i = pos;while(this->d[i] > 9){this->d[i] -= 10;this->d[i+1]++;++i;}if(i+1 > this->len)this->len = i+1;}Node operator / (const Node &t){Node ans;while(1){int p = this->cmp(t);if(p == -1)break;else{ans.change(p);for(int i=0;i<t.len;i++){this->d[i+p+1]--;this->d[i+p] = this->d[i+p]+10-t.d[i];if(this->d[i+p] > 9){this->d[i+p] -= 10;this->d[i+1+p]++;}}while(this->len > 1 && this->d[this->len - 1] == 0)this->len--;}}return ans;}};char str[N];int main()
{scanf("%s",str);Node a(str);scanf("%s",str);Node b(str);Node ans = a / b;for(int i=ans.len-1;i>=0;i--)//商printf("%d",ans.d[i]);printf("\n");for(int i=a.len-1;i>=0;i--)//模printf("%d",a.d[i]);printf("\n");return 0;
}