文章目录
- 序言
-
-
- #1什么是高精度
- #2高精度的作用
-
- 正文
-
- 高精度中需要处理好的问题
-
-
- 数据的接收和存贮
- 高精度数位数的确定
- 高精度进位,借位的处理
- 商和余数的求法
-
- 高精度的四则运算
-
-
- 高精度加法:
- 高精度减法:
- 高精度乘法:
- 高精度除法:
- 高精度四则运算完整代码(含进位借位):
-
- 高精度经典例题
-
- [NOIP1998 普及组] 阶乘之和
-
- 题目描述
- 输入格式
- 输出格式
-
- 样例输入 #1
- 样例输出 #1
- 提示
- 分析
- 例题代码
序言 #1什么是高精度
高精度算法,是一种处理大数字的数学计算方法。在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几百亿的大数字。
一般的,这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方,阶乘等运算。
对于非常庞大的数字无法在计算机中正常存储。于是,将这个数字拆开成一位一位的,或者是四位四位的存储到一个数组中, 用一个数组去表示一个数字,这样这个数字就被称为是高精度数。
#2高精度的作用
实际上高精度就是说参与运算的数据和运算结果的范围,超出标准数据类型能表示的数据大小范围的运算。
这种时候,如果要得到正确的计算结果,就不能依靠普通方法实现了,而要在普通运算原理的基础上,加以辅助算法来实现超大数据的计算。
例如:
求两个 500 位的数据相乘的结果,这时就要用到高精度算法了。
正文 高精度中需要处理好的问题 数据的接收和存贮 当输入的数很长时,我们可以采用字符串方式输入,这样可输入数字很长的数,利用字符串函数和操作运算,将每一位数取出,存入数组中。
字符数组储存与输入:
void init(int a[])
{
char s[1000];
//通过字符数组的形式输入数字
gets(s);
a[0]=strlen(s);
//a[0]保存字符数组s的位数
for(int i=1;
i<=a[0];
i++)
{
a[i]=s[a[0]-i]-'0';
//将字符数组转换为整形数组,并逆序储存
}
}
【洛谷|高精度算法详解 [包括高精除低精与高精除高精]】字符串输入和存储:
void init(int a[])
{
string s;
//通过字符串的形式输入数字
getline(cin,s);
//或cin>>s;
a[0]=s.size();
//a[0]保存字符串s的位数 或s.length();
for(int i=1;
i<=a[0];
i++)
{
a[i]=s[a[0]-i]-'0';
//将字符串转换为整形数组,并逆序储存
}
}
高精度数位数的确定 字符数组的长度:
位数等于接收的字符数组的长度,为了节省空间和便于查找使用,将其保存在 a[0]中。
a[0]=strlen(s);
字符串的长度:
位数等于接收的字符数串的长度,为了节省空间和便于查找使用,将其保存在 a[0]中。
getline(cin,s);
或cin>>s;
高精度进位,借位的处理 加法进位:
void jia()
{
c[i]=a[i]+b[i];
//对应位相加
if(c[i]>=10)//进位了(和大于10)
{
c[i+1]++;
//向前进一位 c[i]%=10;
//进位后剩下的数字
}
}
减法借位:
void jian()
{
if(a[i]
乘法进位:
void cheng()
{
c[i+j-1]=a[i]*b[j]+x+c[i+j-1];
//对应位的值
x=c[i+j-1]/10;
//进位数
c[i+j-1]%=10;
//进位后剩下的数字
}
商和余数的求法 商和余数处理:视被除数和除数的位数情况进行处理。
高精度的四则运算 高精度加法:
#includeusing namespace std;
int a[1000],b[1000],c[1000];
void init1(int a[])
{
char s[1000];
//通过字符数组的形式输入数字
gets(s);
a[0]=strlen(s);
//a[0]保存字符数组s的位数
for(int i=1;
i<=a[0];
i++)
{
a[i]=s[a[0]-i]-'0';
//将字符数组转换为整形数组,并逆序储存
}
}void init2(int a[])
{
string s;
//通过字符串的形式输入数字
getline(cin,s);
//或cin>>s;
a[0]=s.size();
//a[0]保存字符串s的位数 或s.length();
for(int i=1;
i<=a[0];
i++)
{
a[i]=s[a[0]-i]-'0';
//将字符串转换为整形数组,并逆序储存
}
}void jiafa(int a[],int b[],int c[])
{
int x=0;
//暂存进位,从0开始
int i=1;
//位数的下标
while(i<=a[0]||i<=b[0])
{
c[i]=a[i]+b[i]+x;
//对应位相加+上一次的位数 x=c[i]/10;
//进位 c[i]=c[i]%10;
//进位后剩下的数字 i++;
//模拟下一位
}
c[i]=x;
//最后的位数
c[0]=i;
//将和c的位数统一保存在c[0]中
}void aa(int a[])//删除数组a的前导0
{
while(a[0]>=1&&a[a[0]]==0)
{
a[0]--;
}
} int main()
{
init1(a);
init1(b);
//输入
aa(a);
aa(b);
//删除前导0
jiafa(a,b,c);
//a+b=c
aa(c);
//删除c的前导0
for(int i=c[0];
i>=1;
i--)
{
cout<
注意: 两个数相加,结果的位数,应该比两个数中大的那个数多一位。
高精度减法:
#includeusing namespace std;
int a[1000],b[1000],c[1000];
void init1(int a[])
{
char s[1000];
//通过字符数组的形式输入数字
gets(s);
a[0]=strlen(s);
//a[0]保存字符数组s的位数
for(int i=1;
i<=a[0];
i++)
{
a[i]=s[a[0]-i]-'0';
//将字符数组转换为整形数组,并逆序储存
}
}void init2(int a[])
{
string s;
//通过字符串的形式输入数字
getline(cin,s);
//或cin>>s;
a[0]=s.size();
//a[0]保存字符串s的位数 或s.length();
for(int i=1;
i<=a[0];
i++)
{
a[i]=s[a[0]-i]-'0';
//将字符串转换为整形数组,并逆序储存
}
}void jianfa(int a[],int b[],int c[])
{
int i=1;
//位数的下标
while(i<=a[0])
{
if(a[i]=1&&a[a[0]]==0)
{
a[0]--;
}
} int main()
{
init1(a);
init1(b);
//输入
jianfa(a,b,c);
//a-b=c
aa(c);
//删除c的前导0
for(int i=c[0];
i>=1;
i--)
{
cout<
高精度乘法:
#includeusing namespace std;
int a[1000],b[1000],c[1000];
void init1(int a[])
{
char s[1000];
//通过字符数组的形式输入数字
gets(s);
a[0]=strlen(s);
//a[0]保存字符数组s的位数
for(int i=1;
i<=a[0];
i++)
{
a[i]=s[a[0]-i]-'0';
//将字符数组转换为整形数组,并逆序储存
}
}void init2(int a[])
{
string s;
//通过字符串的形式输入数字
getline(cin,s);
//或cin>>s;
a[0]=s.size();
//a[0]保存字符串s的位数 或s.length();
for(int i=1;
i<=a[0];
i++)
{
a[i]=s[a[0]-i]-'0';
//将字符串转换为整形数组,并逆序储存
}
}void chengfa(int a[],int b[],int c[])
{
for(int i=1;
i<=b[0];
i++)
{
int x=0;
//暂存进位,开始为0 for(int j=1;
j<=a[0];
j++)
{
c[i+j-1]=c[i+j-1]+x+b[i]*a[j];
//原数+上一次进的位数+当前的乘积 x=c[i+j-1]/10;
//进位 c[i+j-1]%=10;
//进位后的结果
}c[a[0]+i]=x;
//每次向前进一位
}
c[0]=a[0]+b[0];
//乘积c最多的位数
}void aa(int a[])//删除数组a的前导0
{
while(a[0]>=1&&a[a[0]]==0)
{
a[0]--;
}
} int main()
{
init1(a);
init1(b);
//输入
chengfa(a,b,c);
//a*b=c
aa(c);
//删除c的前导0
for(int i=c[0];
i>=1;
i--)
{
cout<
高精度除法: 高精除以低精:
#includeusing namespace std;
int a[1000],b[1000],c[1000];
//int b;
void init1(int a[])
{
char s[1000];
//通过字符数组的形式输入数字
gets(s);
a[0]=strlen(s);
//a[0]保存字符数组s的位数
for(int i=1;
i<=a[0];
i++)
{
a[i]=s[a[0]-i]-'0';
//将字符数组转换为整形数组,并逆序储存
}
}void init2(int a[])
{
string s;
//通过字符串的形式输入数字
getline(cin,s);
//或cin>>s;
a[0]=s.size();
//a[0]保存字符串s的位数 或s.length();
for(int i=1;
i<=a[0];
i++)
{
a[i]=s[a[0]-i]-'0';
//将字符串转换为整形数组,并逆序储存
}
}void chudi(int a[],int b,int c[])
{
int t=0;
int x=0;
//余数
for(int i=1;
i<=a[0];
i++)//模拟除法
{
t=x*10+a[i];
c[i]=t/b;
//商 x=t%b;
//每次相除后的余数
}
}int main()
{
init1(a);
cin>>b;
//输入
chudi(a,b,c);
//a/b=c
int k=1;
//商的下标
while(c[k]==0&&k<=a[0])
{
k++;
//删除前导0
}
for(int i=k;
i<=a[0];
i++)
{
cout<
高精除以高精:
#includeusing namespace std;
int a[1000],b[1000],c[1000];
int B;
//为除以低精 void init1(int a[])
{
char s[1000];
//通过字符数组的形式输入数字
gets(s);
a[0]=strlen(s);
//a[0]保存字符数组s的位数
for(int i=1;
i<=a[0];
i++)
{
a[i]=s[a[0]-i]-'0';
//将字符数组转换为整形数组,并逆序储存
}
}void init2(int a[])
{
string s;
//通过字符串的形式输入数字
getline(cin,s);
//或cin>>s;
a[0]=s.size();
//a[0]保存字符串s的位数 或s.length();
for(int i=1;
i<=a[0];
i++)
{
a[i]=s[a[0]-i]-'0';
//将字符串转换为整形数组,并逆序储存
}
}int com(int a[],int b[])//比较a,b;
若a>b为1;
若ab[0])
{
return 1;
}
else
{
if(a[0]0;
i--)
{
if(a[i]>b[i])
{
return 1;
}if(a[i]b
{
for(int i=1;
i<=a[0];
i++)//模拟减法
{
if(a[i]0&&a[a[0]]==0)//删除前导0
{
a[0]--;
}return ;
}
}void chugao(int a[],int b[],int c[])//高精除高精
{
int t[1000];
c[0]=a[0]-b[0]+1;
//商最多的位数
for(int i=c[0];
i>0;
i--)//模拟除法
{
memset(t,0,sizeof(t));
//每次清空for(int j=1;
j<=b[0];
j++)//把数组b复制给t
{
t[i+j-1]=b[j];
//下标右偏移i-1位
} t[0]=b[0]+i-1;
//位数while(com(a,t)>=0)
{
c[i]++;
//商加1 jian2(a,t);
//模拟减法(a=a-t)
}
}
}void print(int a[])
{
while(a[0]>0&&a[a[0]]==0)//删除前导0
{
a[0]--;
//位数-1
} if(a[0]==0)//结果为0
{
cout<<0<=1;
i--)
{
cout<
高精度四则运算完整代码(含进位借位):
#includeusing namespace std;
int a[1000],b[1000],c[1000];
int B;
//为除以低精 void init1(int a[])
{
char s[1000];
//通过字符数组的形式输入数字
gets(s);
a[0]=strlen(s);
//a[0]保存字符数组s的位数
for(int i=1;
i<=a[0];
i++)
{
a[i]=s[a[0]-i]-'0';
//将字符数组转换为整形数组,并逆序储存
}
}void init2(int a[])
{
string s;
//通过字符串的形式输入数字
getline(cin,s);
//或cin>>s;
a[0]=s.size();
//a[0]保存字符串s的位数 或s.length();
for(int i=1;
i<=a[0];
i++)
{
a[i]=s[a[0]-i]-'0';
//将字符串转换为整形数组,并逆序储存
}
}/*void jia()
{
c[i]=a[i]+b[i];
//对应位相加
if(c[i]>=10)//进位了(和大于10)
{
c[i+1]++;
//向前进一位 c[i]%=10;
//进位后剩下的数字
}
}*//*void jian()
{
if(a[i]b为1;
若ab[0])
{
return 1;
}
else
{
if(a[0]0;
i--)
{
if(a[i]>b[i])
{
return 1;
}if(a[i]b
{
for(int i=1;
i<=a[0];
i++)//模拟减法
{
if(a[i]0&&a[a[0]]==0)//删除前导0
{
a[0]--;
}return ;
}
}void chugao(int a[],int b[],int c[])//高精除高精
{
int t[1000];
c[0]=a[0]-b[0]+1;
//商最多的位数
for(int i=c[0];
i>0;
i--)//模拟除法
{
memset(t,0,sizeof(t));
//每次清空for(int j=1;
j<=b[0];
j++)//把数组b复制给t
{
t[i+j-1]=b[j];
//下标右偏移i-1位
} t[0]=b[0]+i-1;
//位数while(com(a,t)>=0)
{
c[i]++;
//商加1 jian2(a,t);
//模拟减法(a=a-t)
}
}
}void aa(int a[])//删除数组a的前导0
{
while(a[0]>=1&&a[a[0]]==0)
{
a[0]--;
}
} void print(int a[])
{
while(a[0]>0&&a[a[0]]==0)//删除前导0
{
a[0]--;
//位数-1
} if(a[0]==0)//结果为0
{
cout<<0<=1;
i--)
{
cout<=1;
i--)
{
cout<=1;
i--)
{
cout<=1;
i--)
{
cout<>B;
//输入
chudi(a,B,c);
//a/b=c
int k=1;
//商的下标
while(c[k]==0&&k<=a[0])
{
k++;
//删除前导0
}
for(int i=k;
i<=a[0];
i++)
{
cout<
高精度经典例题 [NOIP1998 普及组] 阶乘之和
题目描述 用高精度计算出S = 1 ! + 2 ! + 3 ! + ? + n ! S = 1! + 2! + 3! + \cdots + n! S=1!+2!+3!+?+n!( n ≤ 50 n \le 50 n≤50)。
其中
!
表示阶乘,定义为n ! = n × ( n ? 1 ) × ( n ? 2 ) × ? × 1 n!=n\times (n-1)\times (n-2)\times \cdots \times 1 n!=n×(n?1)×(n?2)×?×1。例如, 5 ! = 5 × 4 × 3 × 2 × 1 = 120 5! = 5 \times 4 \times 3 \times 2 \times 1=120 5!=5×4×3×2×1=120。输入格式 一个正整数n n n。
输出格式 一个正整数S S S,表示计算结果。
样例输入 #1
3
样例输出 #1
9
提示 【数据范围】
对于100 % 100 \% 100% 的数据, 1 ≤ n ≤ 50 1 \le n \le 50 1≤n≤50。
分析 该题是一道简单的高精度乘法与高精度加法的模板题,我们只需套进去就行了。
例题代码
#includeusing namespace std;
int n,a[1000],s[1000];
void cheng(int s)//高精度乘法
{
int x=0;
for(int i=100;
i>=0;
i--)
{
a[i]=a[i]*s+x;
x=a[i]/10;
a[i]=a[i]%10;
}
}void jia()//高精度加法
{
int x=0;
for(int i=100;
i>=0;
i--)
{
s[i]=s[i]+a[i]+x;
x=s[i]/10;
s[i]=s[i]%10;
}
}int main()
{
cin>>n;
s[100]=a[100]=1;
for(int i=2;
i<=n;
i++)//求阶乘
{
cheng(i);
jia();
}
int K;
for(int i=0;
i<=100;
i++)
{
if(s[i]!=0)
{
K=i;
break;
}
}
for(int i=K;
i<=100;
i++)
{
cout<[i];
} return 0;
}
文章没有更多内容啦~~~
推荐阅读
- 算法|人工神经网络案例分析题,人工神经网络算法实例
- Java|求所有质因子(Java)
- 随想随写|归并排序(MergeSort)
- c++|P5661 [CSP-J2019] 公交换乘
- 剑指offer第二版|剑指offer 44. 从1到n整数中1出现的次数
- c++|Codeforces 693 D. Even-Odd Game
- 数据结构|Leetcode——989. 数组形式的整数加法
- 刷题记录|力扣周赛310场题解
- C++基础|C++实现Fibonacci数列