基数排序
#include <stdio.h>
int Max(int a[],int n)
{
int max=a[0],i;
for(i=1;i<n;i++) if(a[i]>max) max=a[i];
return max;
}
int T[100000];
void countSort(int a[], int n, int exp)
{
int i,b[10]={0};
for(i=0;i<n;i++) b[a[i]/exp%10]++;
for(i=1;i<10;i++) b[i]+=b[i-1];
for(i=n-1;i>=0;i--)
{
int t=a[i]/exp%10;
T[b[t]-1]=a[i];
b[t]--;
}
for(i=0;i<n;i++) a[i]=T[i];
}
除了除法我们都应该将倒过来,因为要进行进位或借位
比较大小先比较长度,长度相等字典序就是其大小
加法倒序相加,记得保存进位
减法倒序相减,借1为10,⚠️大减小,去除前导0
乘法直接算到当前为商,去除前导0
除法比较困难,可以满足列除法式子时进行减法,最后也减9次,注意这个0的处理,比较复杂
非负整数实现,负数的话需要特判符号
应该注释还算清楚,适合有一定水平的入门者。基础设计来源于crq
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N], c[N];
//字符串类型转换为数组,并且倒过来
void stringToArr(string s, int a[])
{
int len = s.length();
//倒过来进行赋值
for (int i = 0; i < len; i++)
{
a[i] = s[len - i - 1] - '0';
}
}
//初始化字符串转换为数组
void init(string s1, string s2)
{
//清0,全局变量只有第一次是0
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
//将其转为数字串,并倒过来
stringToArr(s1, a);
stringToArr(s2, b);
}
//数组转换为字符串,并且倒过来
string arrToString(int a[], int n)
{
string s = "";
//倒过来进行字符的还原
for (int i = n - 1; i >= 0; i--)
{
s += (char)(a[i] + '0');
}
return s;
}
//两数比较,大于等于返回true
bool cmp(string a, string b)
{
//位数不等,位数大的数大
if (a.length() != b.length())
{
return a.length() > b.length();
}
//位数相等字典序大小即大小关系
return a >= b;
}
//加法
string add(string s1, string s2)
{
//先把s1和s2初始化到ab数组里
init(s1, s2);
//长度为两数最大的那个数
int len = max(s1.length(), s2.length());
//进位
int step = 0;
for (int i = 0; i < len; i++)
{
//当前位就是两数相加及进位的个位
c[i] = (a[i] + b[i] + step) % 10;
//当前位就是两数相加及进位的十位
step = (a[i] + b[i] + step) / 10;
}
//进位不为0,所以要多一位
if (step != 0)
c[len++] = step;
return arrToString(c, len);
}
//减法,只能大减小
string sub(string s1, string s2)
{
//先把s1和s2初始化到ab数组里
init(s1, s2);
//s1是大数,所以他的长度就是ans的长度
int len = s1.length();
for (int i = 0; i < s1.length(); i++)
{
//小于就借位
if (a[i] < b[i])
{
a[i] += 10;
a[i + 1]--;
}
//进行减法
c[i] = a[i] - b[i];
}
//去除前导0
while (len > 1 && c[len - 1] == 0)
len--; //把c数组转换为string类型输出,m作为位数传递
return arrToString(c, len);
}
//乘法
string mul(string s1, string s2)
{
//先把s1和s2初始化到ab数组里
init(s1, s2);
for (int j = 0, i; j < s2.length(); j++)
{
//进位为step
int step = 0;
for (i = 0; i < s1.length(); i++)
{
//就是列乘法计算,直接加进去目标位
c[i + j] += a[i] * b[j] + step;
//有可能产生进位,需要保存
step = c[i + j] / 10;
//目标位是一位数
c[i + j] = c[i + j] % 10;
}
//最终进位还是空的,直接给进位吧
c[i + j] = step;
}
//最终可能有两个总长的位数
int len = s1.length() + s2.length();
//去除前导0
while (len > 1 && c[len - 1] == 0)
len--;
return arrToString(c, len);
}
//除法,返回余数,c是商
string div(string a, string b, string &c)
{
//remainder的缩写,代表余数,也就是当前的被除数
string rem = "";
//c有可能会被操作了,清空一下
c = "";
for (int i = 0; i < a.length(); i++)
{
//余数为0,就是当前一位。否则加上当前位
if (rem == "0")
rem = a[i];
else
rem = rem + a[i];
int t = 0;
//如果被除数比除数大,进行减法,t最大也是9
while (cmp(rem, b))
{
rem = sub(rem, b);
t++;
}
//c还是空且t是0,直接进行下一次循环,解决了商的前导0
if (c == "" && t == 0)
continue;
//商加上求出的当前位
c = c + char(t + '0');
}
if (c == "")
c = "0";
return rem;
}
int main()
{
string a, b, c;
while (cin >> a >> b)
{
//加法
cout << add(a, b) << "n";
//减法,需先判断a b大小,小于交换,输出负号
if (!cmp(a, b))
{
cout << "-";
swap(a, b)
}
cout << sub(a, b) << "n";
//乘法
cout << mul(a, b) << "n";
//除法使用,依次输出商和余数
string d = div(a, b, c);
cout << c << " " << d << "n";
}
return 0;
}
以上乘法的复杂度还是不是太满意(是n*m的),我们可以用fft来做
把每一项作为系数进行fft,这个范围我竟然算错了,是2097152要大于所以是2.1e6,2e6就一直RE。代码可以通过https://www.luogu.com.cn/problem/P1919
优雅的fft高精度
#include <bits/stdc++.h>
using namespace std;
const int N = 2.1e6;
const double Pi = acos(-1);
int n, m, r[N], P, ans[N];
struct C
{
double x, y;
} a[N], b[N];
C operator+(C a, C b) { return (C){a.x + b.x, a.y + b.y}; }
C operator-(C a, C b) { return (C){a.x - b.x, a.y - b.y}; }
C operator*(C a, C b) { return (C){a.x * b.x - a.y * b.y, a.x * b.y + b.x * a.y}; }
void FFT(C f[], int opt)
{
for (int i = 0; i < n; ++i)
if (i < r[i])
swap(f[i], f[r[i]]);
for (int len = 1, nl = 2; len < n; len = nl, nl <<= 1)
{
C rot = (C){cos(Pi / len), opt * sin(Pi / len)};
for (int l = 0; l < n; l += nl)
{
C w = (C){1, 0};
int r = l + len;
for (int k = l; k < r; ++k, w = w * rot)
{
C x = f[k], y = w * f[k + len];
f[k] = x + y, f[k + len] = x - y;
}
}
}
}
string arrToString(int a[], int n)
{
string s = "";
while (n > 1 && a[n - 1] == 0)
n--;
for (int i = n - 1; i >= 0; i--)
{
s += (char)(a[i] + '0');
}
return s;
}
void stringToArr(string s, C a[])
{
int len = s.length();
for (int i = 0; i < len; i++)
{
a[i].x = s[len - i - 1] - '0';
}
}
int main()
{
string s, c;
cin >> s;
stringToArr(s, a);
cin >> c;
stringToArr(c, b);
n = max(s.length(), c.length());
for (m = n + n, n = 1; n <= m; n <<= 1, ++P)
;
for (int i = 0; i < n; ++i)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (P - 1));
//蝴蝶变换FFT
FFT(a, 1), FFT(b, 1);
for (int i = 0; i < n; ++i)
a[i] = a[i] * b[i];
FFT(a, -1);
for (int i = 0; i <= m; ++i)
ans[i] = (int)(a[i].x / n + .5);
for (int i = 0, tmp1, tmp2; i < m; ++i)
ans[i + 1] += (ans[i] / 10), ans[i] %= 10;
cout << arrToString(ans, m + 1) << "n";
}
View Code
原文链接: https://www.cnblogs.com/BobHuang/p/12264376.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/192722
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!