#include<iostream>
#include<string>
#include<vector>
#include<cstdio>
using namespace std;
/******************************************************/
/*************** 大整数类 BigNum 定义 *************/
/******************************************************/
#define maxnum 9999
class BigNum
{
// Data fields
public:
vector<unsigned int> a; //
int sign; // -1 代表负数, 0 表示0, 1 表示正数.
unsigned int len; //
// 基本运算操作
private:
BigNum & Sub(const BigNum &); //减法运算
BigNum & Multiply(const BigNum &); //乘法运算
BigNum & Add(const BigNum &); //加法运算
// 用户接口
public:
// 构造类
BigNum(){ sign = 1; len = 1; a.resize(1, 0);}
BigNum(const unsigned int n);
BigNum(const string & );
BigNum(const BigNum & );
// 赋值操作
BigNum & operator=(const unsigned int n);
BigNum & operator=(const string &);
BigNum & operator=(const BigNum &);
// 数学运算操作重构
BigNum operator-(const BigNum &) const;
BigNum operator-(const unsigned int n) const;
BigNum operator-() const;
BigNum operator+(const BigNum &) const;
BigNum operator+(const unsigned int n) const;
BigNum operator*(const BigNum &) const;
BigNum operator*(const unsigned int n) const;
unsigned int Length() const; // 数字长度
void Print() const; // 数字输出
};
BigNum::BigNum(const unsigned int n) //
{
int c,d = n;
len = 0;
if(d < 0)
{
d = -d;
sign = -1;
}
else if(d == 0)
{
sign = 0;
a.resize(2, 0);
len = 1;
}
else
{
a.resize(4, 0);
while(d > maxnum)
{
c = d - d / (maxnum + 1) * (maxnum + 1);
d = d / (maxnum + 1);
a[len++] = c;
}
sign = 1;
a[len++] = d;
}
}
BigNum::BigNum(const string & T)
{
int ts = T.size(), pos = 0, i, d;
for(pos = 0; pos < ts; pos++)
if(49<=T[pos] && T[pos]<=57)
break;
if(pos >= ts)
{
len = 1;
sign = 0;
a.resize(2, 0);
a[0] = 0;
}
else
{
string str;
len = 0;
a.resize((ts-pos+4)/4 + 1, 0);
for(i = ts; i-pos > 3; i -= 4)
{
str = T.substr(i-4, 4);
d = atoi(str.c_str());
a[len++] = d;
}
if(i-pos > 0)
{
str = T.substr(pos, i-pos);
d = atoi(str.c_str());
a[len++] = d;
}
if(pos>0 && T[0]=='-') sign = -1;
else sign = 1;
}
}
BigNum::BigNum(const BigNum & T)
{
len = T.len;
int i;
sign = T.sign;
a.resize(len+2, 0);
for(i = 0 ; i < len ; i++)
a[i] = T.a[i];
}
BigNum & BigNum::operator=(const unsigned int n)
{
*this = BigNum(n);
return *this;
}
BigNum & BigNum::operator=(const string & s)
{
*this = BigNum(s);
return *this;
}
BigNum & BigNum::operator=(const BigNum & n)
{
len = n.len;
sign = n.sign;
a.resize(len+1, 0);
for(int i = 0 ; i < len ; i++)
a[i] = n.a[i];
return *this;
}
BigNum& BigNum::Sub(const BigNum & T)
{
int i,j,big;
big = T.len > len ? T.len : len;
vector<unsigned int> b;
b.resize(big+2, 0);
for(i = 0 ; i < len ; i++)
b[i] = a[i];
for(i = 0 ; i < big ; i++)
{
if(i<T.len)
{
if(b[i] < T.a[i])
{
j = i + 1;
while(b[j] == 0)
j++;
b[j--]--;
while(j > i)
b[j--] += maxnum;
b[i] = b[i] + maxnum + 1 - T.a[i];
}
else b[i] -= T.a[i];
}
}
len = big;
while(b[len - 1]==0 && len>1)
len--;
a = b;
return *this;
}
BigNum& BigNum::Multiply(const BigNum& T)
{
int i,j,up;
unsigned int num,num1;
BigNum ret;
ret.a.resize(len + T.len + 1);
for(i = 0 ; i < len ; i++)
{
up = 0;
for(j = 0 ; j < T.len ; j++)
{
num = a[i] * T.a[j] + ret.a[i + j] + up;
if(num > maxnum)
{
num1 = num % (maxnum + 1);
up = num / (maxnum + 1);
ret.a[i + j] = num1;
}
else
{
up = 0;
ret.a[i + j] = num;
}
}
if(up != 0)
ret.a[i + j] = up;
}
ret.len = i + j;
while(ret.a[ret.len - 1] == 0 && ret.len > 1)
ret.len--;
*this = ret;
return *this;
}
BigNum & BigNum::Add(const BigNum & T)
{
int i,big;
big = T.len > len ? T.len : len;
vector<unsigned int> b;
b.resize(big+2, 0);
for(i = 0 ; i < len ; i++)
b[i] = a[i];
for(i = 0 ; i < big ; i++)
{
if(i < T.len)
{
b[i] = b[i] + T.a[i];
if(b[i] > maxnum)
{
b[i + 1]++;
b[i] = b[i] - maxnum - 1;
}
}
}
if(b[big] != 0) len = big + 1;
else len = big;
a = b;
return *this;
}
BigNum BigNum::operator-(const BigNum & T) const
{
BigNum b = *this;
b.Sub(T);
return b;
}
BigNum BigNum::operator-(const unsigned int n) const
{
BigNum b = *this;
b.Sub(BigNum(n));
return b;
}
BigNum BigNum::operator-() const //取相反数
{
BigNum b = *t
没有合适的资源?快使用搜索试试~ 我知道了~
2_4.rar_4 3 2 1
共1个文件
cpp:1个
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 131 浏览量
2022-09-24
02:40:04
上传
评论
收藏 3KB RAR 举报
温馨提示
c,c++实现单调序列问题:给定一个正整数n,求出对于n个整数集合{1,2,3,…,n-1,n}所有的排列中,单调序列的数量。
资源详情
资源评论
资源推荐
收起资源包目录
2_4.rar (1个子文件)
2_4.cpp 21KB
共 1 条
- 1
weixin_42653672
- 粉丝: 94
- 资源: 1万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0