C++自写类实现大数阶乘
本帖最后由 bin554385863 于 2020-1-7 04:20 编辑#include "E:\Users\admin\Documents\VScode\Code\My Class\lnum\lnum.cpp"
lnum fact(const lnum &n)
{
lnum fact = "1";
for (lnum i = "1"; i <= n; i++)
{
fact *= i;
}
return fact;
}
int main(int argc, char const *argv[])
{
lnum a = "1";
for (lnum i = "10"; i != "110"; i += "10")
{
std::cout << i<<"! = "<<fact(i) << std::endl;
}
return 0;
}
=============================================================================
Microsoft Windows [版本 10.0.18363.535]
(c) 2019 Microsoft Corporation。保留所有权利。
E:\Users\admin\Documents\VScode\Code>c:\Users\admin\.vscode\extensions\ms-vscode.cpptools-0.26.2\debugAdapters\bin\WindowsDebugLauncher.exe --stdin=Microsoft-MIEngine-In-bln4vusc.bgf --stdout=Microsoft-MIEngine-Out-pkxxzoxc.0jt --stderr=Microsoft-MIEngine-Error-tn53w3yl.5hv --pid=Microsoft-MIEngine-Pid-ddmgmwek.eog --dbgExe=D:\MinGW\bin\gdb.exe --interpreter=mi
10! = 3628800
20! = 2432902008176640000
30! = 265252859812191058636308480000000
40! = 815915283247897734345611269596115894272000000000
50! = 30414093201713378043612608166064768844377641568960512000000000000
60! = 8320987112741390144276341183223364380754172606361245952449277696409600000000000000
70! = 11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000
80! = 71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000
90! = 1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000
100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
E:\Users\admin\Documents\VScode\Code>
完整代码
当字符串出现其他非数字字符时(有效的负号和小数点除外)全部按"0"处理.
代码不能识别顺序错误的数字字符串,如"0005000"这样的数字字符串,请输入正确的数字字符串如:"1365458", "-0.1234566"等等(可以实现在构造对象时清除无效零的功能,相应函数已经写好,但这样会在计算带小数位的乘法时造成额外的逻辑判断)
已经重载输出流符号<<和输入流符号>>,可以向基础类型一样使用cout/cin进行输入输出.
lnum.cpp
#ifndef LNUM_H
#define LNUM_H
#include <iostream>
#include <string>
#include <vector>
using std::istream;
using std::ostream;
using std::string;
using std::vector;
class lnum
{
struct ndata
{
int sign;
string nstr;
vector<int> nvec;
size_t isize, dsize;
};
struct align
{
vector<int> first, second;
};
private:
static size_t pre;
ndata data;
//(0)判断是否含有小数点
const bool hasDecPoint(const string &s) const;
//(1)判断字符串是否有效
const bool isInvalidStr(const string &s) const;
//(2)判断字符串元素是否全为零
const bool isStrElemAllZero(const string &s) const;
//(3)清除无效的零
const string clearInvalidZero(const string &s) const;
//(4)转换数组
const vector<int> strToVec(const string &s) const;
//(-4)转换字符串
const string vecToStr(const vector<int> &vint, int sgn, size_t dsz) const;
//(5)提取信息
const ndata getInfo(const string &s) const;
//(6)小数位对齐
align dAlign(const lnum &l) const;
//(7)整体对齐
align wAlign(const lnum &l) const;
//(8)满十进一
void carry(vector<int> &v) const;
//(9)借一补十
void borrow(vector<int> &v) const;
//(10)输出设置
const string setPrint() const;
//(11)lnum*n
const lnum operator*(const int &n) const;
public:
lnum(const char *cstr = "0") : data(getInfo(cstr))
{
}
lnum(const string &s):data(getInfo(s)){}
void showinfo() const;
static void setprecision(const size_t p);
//(1)>号
const bool operator>(const lnum &l) const;
//(2)==
const bool operator==(const lnum &l) const;
//(3)>=
const bool operator>=(const lnum &l) const;
//(4)<
const bool operator<(const lnum &l) const;
//(5)<=
const bool operator<=(const lnum &l) const;
//(5)!=
const bool operator!=(const lnum &l) const;
//(6)+
const lnum operator+(const lnum &l) const;
//(7)-反转正负
const lnum operator-() const;
//(7.5)-
const lnum operator-(const lnum &l) const;
//(8)+=
const lnum &operator+=(const lnum &l);
//(9)++
const lnum &operator++(const int i);
//(10)-=
const lnum &operator-=(const lnum &l);
//(11)--
const lnum &operator--(const int i);
//(12)lnum*lnum
const lnum operator*(const lnum &l) const;
//(10)*=
const lnum &operator*=(const lnum &l);
//(F)<<
friend ostream &operator<<(ostream &os, const lnum &l);
//(F)>>
friend istream &operator>>(istream &is, lnum &l);
~lnum(){}
};
size_t lnum::pre = 6;
#endif
方法实现
lnum.cpp
#include "E:\Users\admin\Documents\VScode\Code\My Class\lnum\lnum.h"
//(0)判断是否含有小数点
const bool lnum::hasDecPoint(const string &s) const
{
return int(s.find('.')) > -1 ? true : false;
}
//(1)判断字符串是否有效
const bool lnum::isInvalidStr(const string &s) const
{
bool f = true;
string str = s;
if (str == '-')
{
str.erase(0, 1);
}
if (!hasDecPoint(str))
{
for (char c : str)
{
if (!isdigit(c))
{
f = false;
break;
}
}
}
else
{
size_t dpinx = str.find('.');
f = (dpinx == 0) || (dpinx == (str.size() - 1)) || (dpinx != str.rfind('.')) ? false : true;
str.erase(dpinx, 1);
for (char c : str)
{
if (!isdigit(c))
{
f = false;
break;
}
}
}
return f;
}
//(2)判断字符串元素是否全为零
const bool lnum::isStrElemAllZero(const string &s) const
{
string str = s;
str == '-' ? str.erase(0, 1) : str;
hasDecPoint(str) || false ? str.erase(str.find('.'), 1) : str;
return str == string(str.size(), '0') ? true : false;
}
//(3)清除无效的零
const string lnum::clearInvalidZero(const string &s) const
{
string str = s;
if (isInvalidStr(s))
{
size_t i = 0;
if (str == '-')
{
str.erase(0, 1);
}
if (!hasDecPoint(s))
{
size_t sz = str.size();
while (i != sz)
{
if (str != '0')
{
break;
}
i++;
}
if (i == sz)
{
str.erase(0, i - 1);
}
else if (i > 0)
{
str.erase(0, i);
}
}
else
{
i = 0;
while (str != '.')
{
if (str != '0')
{
break;
}
i++;
}
if (i == str.find('.'))
{
str.erase(0, i - 1);
}
else if (i > 0)
{
str.erase(0, i);
}
i = str.size() - 1;
while (str != '.')
{
if (str != '0')
{
break;
}
i--;
}
if (i == str.find('.'))
{
str.erase(i);
}
else if (i < str.size() - 1)
{
str.erase(i + 1);
}
}
}
if (s == '-' && str != "0")
{
str.insert(0, 1, '-');
}
return str;
}
//(4)转换数组
const vector<int> lnum::strToVec(const string &s) const
{
vector<int> vint;
string str = s;
str == '-' ? str.erase(0, 1) : str;
hasDecPoint(str) > false ? str.erase(str.find('.'), 1) : str;
for (char c : str)
{
vint.push_back(c - 48);
}
return vint;
}
//(-4)转换字符串
const string lnum::vecToStr(const vector<int> &vint, int sgn, size_t dsz) const
{
string str;
for (int i : vint)
{
str.push_back(i + 48);
}
if (str != "0")
{
dsz == 0 ? str : str.insert(str.size() - dsz, 1, '.');
sgn == -1 ? str.insert(0, 1, '-') : str;
}
return str;
}
//(5)提取信息
const lnum::ndata lnum::getInfo(const string &s) const
{
ndata ndt = {0, "0", {0}, 1, 0};
if (isInvalidStr(s))
{
ndt.nstr = s;
ndt.sign = ndt.nstr != "0" ? (ndt.nstr == '-' ? -1 : 1) : 0;
ndt.dsize = hasDecPoint(ndt.nstr) || false ? ndt.nstr.size() - ndt.nstr.find('.') - 1 : 0;
ndt.nvec = strToVec(ndt.nstr);
ndt.isize = ndt.nvec.size() - ndt.dsize;
}
return ndt;
}
//(6)小数位对齐
lnum::align lnum::dAlign(const lnum &l) const
{
align agn;
vector<int> &f = agn.first, &s = agn.second;
f = data.nvec;
s = l.data.nvec;
const size_t &fds = data.dsize, &sds = l.data.dsize;
fds > sds ? s.insert(s.end(), fds - sds, 0) : f.insert(f.end(), sds - fds, 0);
return agn;
}
//(7)整体对齐
lnum::align lnum::wAlign(const lnum &l) const
{
align &&agn = this->dAlign(l);
vector<int> &f = agn.first, &s = agn.second;
const size_t &fws = data.isize, &sws = l.data.isize;
fws > sws ? s.insert(s.begin(), fws - sws, 0) : f.insert(f.begin(), sws - fws, 0);
return agn;
}
//(8)满十进一
void lnum::carry(vector<int> &v) const
{
v.insert(v.begin(), 1, 0);
const size_t s = v.size();
for (size_t i = s - 1; i != 0; i--)
{
int t = v;
v = t % 10;
v += t / 10;
}
if (v == 0)
{
v.erase(v.begin(), v.begin() + 1);
}
}
//(9)借一补十
void lnum::borrow(vector<int> &v) const
{
const size_t s = v.size();
for (size_t i = 1; i < s; i++)
{
v -= 1;
v += 10;
}
}
//(10)输出设置
const string lnum::setPrint() const
{
const size_t &tds = data.dsize;
string str = data.nstr;
if (pre == 0)
{
if (tds != 0)
{
str.erase(str.find('.'));
}
}
else if (tds > pre)
{
str.erase(str.size() - (tds - pre));
}
return clearInvalidZero(str);
}
//(11)lnum*n
const lnum lnum::operator*(const int &n) const
{
vector<int> t = data.nvec;
for (int &i : t)
{
i *= n;
}
carry(t);
lnum r = vecToStr(t, data.sign, data.dsize);
return r;
}
//==========================================================================
//(0)显示信息
void lnum::showinfo() const
{
std::cout << "正/负/零: " << data.sign << "\n"
<< "原始数字: " << data.nstr << "\n"
<< "数组元素: ";
for (int i : data.nvec)
{
std::cout << i << " ";
}
std::cout << std::endl;
std::cout << "整数位数: " << data.isize << "\n"
<< "小数位数: " << data.dsize << std::endl;
}
void lnum::setprecision(const size_t p)
{
pre = p;
}
//(1)>号
const bool lnum::operator>(const lnum &l) const
{
bool f = true;
const int &tsgn = data.sign, &lsgn = l.data.sign;
if (tsgn < lsgn)
{
f = false;
}
else if (tsgn == lsgn)
{
const align &agn = this->wAlign(l);
f = agn.first > agn.second;
if (tsgn == -1)
{
f = !f;
}
}
return f;
}
//(2)==
const bool lnum::operator==(const lnum &l) const
{
return (data.sign == l.data.sign) && (data.nvec == l.data.nvec);
}
//(3)>=
const bool lnum::operator>=(const lnum &l) const
{
return (*this > l) || (*this == l);
}
//(4)<
const bool lnum::operator<(const lnum &l) const
{
return !(*this >= l);
}
//(5)<=
const bool lnum::operator<=(const lnum &l) const
{
return !(*this > l);
}
//(5.5)!=
const bool lnum::operator!=(const lnum &l) const
{
return !(*this == l);
}
//(6)+
const lnum lnum::operator+(const lnum &l) const
{
lnum r;
if (*this != (-l))
{
align agn = this->wAlign(l);
vector<int> &fst = agn.first,
&sec = agn.second,
&greater = fst >= sec ? fst : sec,
&less = sec <= fst ? sec : fst;
const int &tsgn = data.sign,
&lsgn = l.data.sign;
const size_t &sz = fst.size();
for (size_t i = 0; i < sz; i++)
{
greater += (lsgn * tsgn) * less;
}
int sgn = 1;
if (tsgn == lsgn)
{
sgn = tsgn;
}
else if (tsgn != lsgn)
{
sgn = ((greater == fst && tsgn < lsgn) || (less == fst && tsgn > lsgn)) || false ? -1 : sgn;
}
if (tsgn * lsgn == -1)
{
borrow(greater);
}
carry(greater);
size_t dsz = data.dsize >= l.data.dsize ? data.dsize : l.data.dsize;
r = vecToStr(greater, sgn, dsz);
}
return r;
}
//(7)-反转正负
const lnum lnum::operator-() const
{
lnum r = *this;
if (data.sign != 0)
{
r.data.sign = -data.sign;
r.data.nstr = vecToStr(data.nvec, -data.sign, data.dsize);
}
return r;
}
//(7.5)-
const lnum lnum::operator-(const lnum &l) const
{
return *this + (-l);
}
//(8)+=
const lnum &lnum::operator+=(const lnum &l)
{
return *this = *this + l;
}
//(9)++
const lnum &lnum::operator++(const int i)
{
return *this = *this + "1";
}
//(10)-=
const lnum &lnum::operator-=(const lnum &l)
{
return *this = *this + (-l);
}
//(11)--
const lnum &lnum::operator--(const int i)
{
return *this = *this + "-1";
}
//(12)lnum*lnum
const lnum lnum::operator*(const lnum &l) const
{
lnum r;
const int &tsgn = data.sign,
&lsgn = l.data.sign;
if (tsgn * lsgn == 0)
{
r = "0";
}
else
{
const vector<int> &tvec = data.nvec,
&lvec = l.data.nvec;
const size_t &tsz = data.dsize,
&lsz = l.data.dsize,
&tvsz = tvec.size(),
&lvsz = lvec.size(),
&shrtsz = tvsz <= lvsz ? tvsz : lvsz;
lnum loong = tvsz >= lvsz ? *this : l;
const vector<int> &shrtv = lvsz <= tvsz ? lvec : tvec;
vector<int> &lovec = loong.data.nvec,
&rvec = r.data.nvec;
for (size_t i = shrtsz - 1; i != -1; i--)
{
r += loong * shrtv;
if (i > 0)
{
lovec.push_back(0);
}
}
r = vecToStr(rvec, tsgn * lsgn, tsz + lsz);
}
return r;
}
//(10)*=
const lnum &lnum::operator*=(const lnum &l)
{
return *this = *this * l;
}
//(F)<<
ostream &operator<<(ostream &os, const lnum &l)
{
os << l.setPrint();
return os;
}
//(F)>>
istream &operator>>(istream &is, lnum &l)
{
string str;
(std::cin >> str).get();
l = str;
return is;
} >>> import math
>>> math.factorial(200)
788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000 本帖最后由 bin554385863 于 2020-1-6 12:07 编辑
wp231957 发表于 2020-1-6 09:13
>>> import math
>>> math.factorial(200)
7886578673647905035523632139321850622951359776871732632947 ...
这里是C++，
不是Python OR go lang 至于除法我能想到的是模拟竖式计算... bin554385863 发表于 2020-1-6 12:19
至于除法我能想到的是模拟竖式计算...
减法可以用加法模拟，100 - 10 == 100 + (-10)
乘法可以用加法模拟，2 * 3 == 3 + 3 == 2 + 2 + 2
除法可以用乘法模拟
10 / 3
1 * 3 < 10
2 * 3 < 10
3 * 3 < 10
4 * 3 > 10
10 / 3 == 3
人造人 发表于 2020-1-6 13:41
减法可以用加法模拟，100 - 10 == 100 + (-10)
乘法可以用加法模拟，2 * 3 == 3 + 3 == 2 + 2 + 2
除法 ...
加减乘我已经写出来了,就除法 我之前就是这样做的，只实现了加法操作
至于减法、乘法、除法、取余、乘方、开方 。。。
这些都是向下调用
例如，除法循环调用乘法函数，乘法函数循环调用加法函数
我的这个版本能够得到正确答案，就是非常慢，不骗你，因为都是向下调用，最终调用加法操作，真的非常慢，如果你没有好的思路，可以用这种方法试一试，^_^ 本帖最后由 bin554385863 于 2020-1-6 18:17 编辑
人造人 发表于 2020-1-6 13:47
我之前就是这样做的，只实现了加法操作
至于减法、乘法、除法、取余、乘方、开方 。。。
这些都是向下调 ...
我的想法是模拟手算竖式,最终也是递归个加法,
除不过就在末尾添0,添几个0就说明商是几位小数
比如
7
/
5
7-5 = 1-------2商的整数位是1
2/5除不过
2后面添0
同样的存储2/5的商的数组也填个0={0}
20-5(循环减) 4次正好为0
然后尾部插入数组中正好是{0,4}且小数位数是1
再加上第一个没有小数的数组{1}
相加既得结果数组{1,4}且小数位数为一,然后在转换成字符串输出
伪代码已经写出来了,正在考虑怎么写正式代码 bin554385863 发表于 2020-1-6 16:00
我的想法是模拟手算竖式,最终也是递归个加法,
除不过就在末尾添0,添几个0就说明商是几位小数
比如
也行，不过我还是认为我的方法好，起码好理解，只是运行没有效率罢了，^_^
bin554385863 发表于 2020-1-6 16:00
我的想法是模拟手算竖式,最终也是递归个加法,
除不过就在末尾添0,添几个0就说明商是几位小数
比如
所以我之前说过的。。底层设计成2进制，在显示的时候再把二进制的数据转化为十进制显示。
这样除法就非常好算，直接减法模拟就好：
比如10011（19）除以101 （5）：
首先除数左移，与被除数对齐：
10011
10100
然后能相减记1，不能相减记0，每次相减之后右移一位，直到位移量为0：
10011
10100
不能相减：记0
10011
101
能相减，记1，减去后剩余01001：
01001
00101
能相减，记1，减去后剩余00100：
位移量为0，结束
所以商为011（3），余数为00100（4）
本帖最后由 bin554385863 于 2020-1-6 18:01 编辑
Croper 发表于 2020-1-6 17:05
所以我之前说过的。。底层设计成2进制，在显示的时候再把二进制的数据转化为十进制显示。
这样除法就 ...
直接使用二进制肯定不现实.
使用字符串模拟二进制的话,数字小还好.数组长度不算太长.但是数字如果太大的话十进制数组的长度可能要到上百个了更别说二进制了
比如100的阶乘!
#include "E:\Users\admin\Documents\VScode\Code\My Class\lnum\lnum.cpp"
#include <ctime>
#include <cmath>
lnum fact(const lnum &n)
{
lnum fact = "1";
for (lnum i = "1"; i <= n; i++)
{
fact *= i;
}
return fact;
}
int main(int argc, char const *argv[])
{
lnum a = "1";
// for (lnum i = "10"; i != "110"; i += "10")
// {
// std::cout << i<<"! = "<<fact(i) << std::endl;
// }
fact("100").showinfo();
return 0;
}
正/负/零: 1
原始数字: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
数组元素: 9 3 3 2 6 2 1 5 4 4 3 9 4 4 1 5 2 6 8 1 6 9 9 2 3 8 8 5 6 2 6 6 7 0 0 4 9 0 7 1 5 9 6 8 2 6 4 3 8 1 6 2 1 4 6 8 5 9 2 9 6 3 8 9 5 2 1 7 5 9 9 9 9 3 2 2 9 9 1 5 6 0 8 9 4 1 4 6 3 9 7 6 1 5 6 5 1
8 2 8 6 2 5 3 6 9 7 9 2 0 8 2 7 2 2 3 7 5 8 2 5 1 1 8 5 2 1 0 9 1 6 8 6 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
整数位数: 158
小数位数: 0
数组的元素越少,长度越短,计算起来肯定越快
所以我觉得可以用十六进制,但是进制转换有很蛋疼
十进制的好处是数组和字符串可以用 '0'进行一对一的转换,而不用考虑进制.你的这种方法给我提了另一个很好的思路 人造人 发表于 2020-1-6 16:04
也行，不过我还是认为我的方法好，起码好理解，只是运行没有效率罢了，^_^
我这种想法就是模拟小学除法竖式来的,加法也是.'
bin554385863 发表于 2020-1-6 17:43
我这种想法就是模拟小学除法竖式来的,加法也是.'
我的加法函数用的算法就是竖式，^_^ 人造人 发表于 2020-1-6 17:45
我的加法函数用的算法就是竖式，^_^
本来考虑使用其他进制来着,嫌进制转换太麻烦,而且使用的是字符串和数组,还不如直接使用十进制了
页:
[1]