信息发布软件,b2b软件,广告发布软件

标题: C++ 高精度计算阶乘真正高级实例教程一看就能懂 [打印本页]

---

作者: 群发软件    时间: 2017-6-26 23:44
标题: C++ 高精度计算阶乘真正高级实例教程一看就能懂


C++ 高精度计算阶乘真正高级实例教程一看就能懂
利用计算机进行数值计算，基本的运算可以直接使用运算符对数字进行操作，而对于位数达到几十位甚至是上百位的大数字，计算机的计算就没办法满足我们对数字精度的要求，所以我们开始设计程序对此类问题进行解决，那也就是我们的高精度运算。
高精度运算对学生来说本来就是一大难点，高精度的加减法相对比较好理解，而对于高精度的乘除法的理解是比较困难的。高精度运算的思维其实就是按位计算，无论是输入还是输出，对于高精度数字都不是采用数字的方法（数字的类型无法满足），那这个时候我们选择使用字符串进行读取，利用字符串函数和操作运算，将每一位数字取出，存储在字符数组里，也可以直接用循环加数组方法读取。高精度运算经常会出现进位（加法和乘法）和借位（减法）的问题，其实最终的目的都是按位进行计算和输出。



高精度求N的阶乘，其中N是一个可以以一般整数输入的数字，只是最终的计算结果数字大位数多精度要求高，所以我们必须对结果的每一位上的数字进行精确计算并存储输出。以下是使用C++高精度求N的阶乘的C++程序，我们采用数组a[]来存储运算的结果，其中对于每一个步骤我都有相对应给出解释，不懂得同学可以多看看，自己思考一下。


#include
#include
using namespace std;
int main( )

{
int carry,n,temp,i,j;
int a[20000];
int digit=1;

cout<<"please enter n:"<<endl;
cin>>n;
a[0]=1;   //数组a[]用来存储最终高精度数字的结果 a[0]表示第一位上的数字
for(i=2; i<=n; i++)
{
   for(carry=0,j=1; j<=digit; ++j)
{
temp=a[j-1]*i+carry;  //j从1开始 ，a[j-1]表示的是求第 j位上的数字 ，carry表示进位
a[j-1]=temp;  
carry=temp/10;
}    //经过这重循环求出了第digit-1位上的数字
   while(carry)
{
a[digit++]=carry;   //求出的是第digit位上的数字  
carry/=10;
}
}
cout<<"the result is:"<<endl;
for(int k=digit; k>=1; --k)
cout<<a[k-1];  //按位输出，因为前面多加了一个1，所以从第digit位开始输出
cout<<endl;
return 0;
}
有关阶乘的算法，不外乎两个方面：一是高精度计算；二是与数论相关。
　　一、 高精度计算阶乘
　　这实际上是最没有技术含量的问题，但是又会经常用到，所以还是得编写，优化它的计算。
　　首先看小于等于12的阶乘计算（计算结果不会超出32位范围）：
　　int factorial（int n） {
　　if （n == 1 || n == 0）
　　return 1;
　　return factorial（n-1）*n;
　　}
　　这个递归程序简单明了，非常直观，然而一旦n > 12，则超过32位int型的范围出现错误结果，所以上面这个递归程序仅适合n <= 12的阶乘计算，为了计算较大n的阶乘，需要将高精度乘法算法纳入到阶乘计算中来，高精度乘法过程可以如下简单的描述：（其中A * B = C，A[0], B[0], C[0]分别存储长度）
　　for （i = 1; i <= A[0]; i++）
　　for （j = 1; j <= B[0]; j++） {
　　C[i+j-1] += A*B[j];      　　// 当前i+j-1位对应项 + A * B[j]
　　C[i+j] += C[i+j-1]/10;     　　// 它的后一位 + 它的商（进位）
　　C[i+j-1] %= 10;              　　// 它再取余即可
　　}
　　C[0] = A[0] + B[0];
　　while （C[0] > 1 && C[C[0]] == 0） C[0]--;   // 去头0，获得实际C的长度
　　有了这个高精度乘法之后，计算阶乘就可以简单的迭代进行：
　　for （i = 2; i <= n; i++） {
　　将i转换成字符数组；
　　执行高精度乘法：将上一次结果乘上i
　　}
　　二、 与数论有关
　　由于阶乘到后面越来越大，巧妙的利用数论求得一些有趣的数字（数值）等成为阶乘算法的设计点，下面给出几道相关的问题与分析：
　　（1）   计算阶乘末尾第一个非0数字：
　　这是一个比较经典的问题，比较复杂的算法是利用一个艰难的数学公式，可惜我不会，从网上的资料学习中，整理出下面这个简单易懂的算法：
　　观察n!，可以发现在乘的过程中，对于任意 n > 1，n!的末尾第一个非0数字都是偶数。我们只需保留最后一位非零数。当要乘的数中含有因数5时，我们可以把所有的因数5都当作8来乘。这是因为：
　　…x2*5=…10（舍）或…60，最后一位非零数为6。而恰好2*8=16，末位为6。
　　…x4*5=…70（舍）或…20，最后一位非零数为2。而恰好4*8=32，末位为2。
　　…x6*5=…30（舍）或…80，最后一位非零数为8。而恰好6*8=48，末位为8。
　　…x8*5=…90（舍）或…40，最后一位非零数为4。而恰好8*8=64，末位为4。
　　（对于n > 1时，最后一位不会出现 1, 7, 3, 9，而永远是2, 4, 6, 8的循环出现）
　　因此，在迭代作乘法时，主要就是计算因子5的数量，同时可见因子5的个数以4为循环节（即只需要取它的数量对4取模）。那么对于不同情况下的因子5的数量，可以通过res[5][4] = {{0,0,0,0}, {2,6,8,4}, {4,2,6,8}, {6,8,4,2}, {8,4,2,6}}来得到，使用nonzero表示i的阶乘的最后一位，那么：
　　如果t是偶数，则直接乘：nonzero = （nonzero[i-1]*t）%10。
　　否则nonzero = res[（（nonzero[i-1]*t）%10）/2][five];
　　其中t是除掉所有因子5的结果，five为因子5数量对4的模。
　　（2）。 阶乘末尾有多少个0
　　分析发现，实际上形成末尾0，就是因子5的数量，而计算1~n之间包含一个因子i的个数的简单算法就是：
　　cnt = 0; while （n） { n /= i; cnt += n; }
　　因此，直接将i换成5，就可以得到因子5的数量，也即n!末尾0的数量。
　　（3）。 返回阶乘左边的第二个数字
　　简单算法：用实数乘，超过100就除以10，最后取个位即可。因为整数部分的个位就是阶乘结果左边的第二个数字。相关题目：
　　（4）。 判断数值 m 是否可以整除 n!
　　算法：使用素因子判断法
　　A. 首先直接输出两种特殊情况：
　　m == 0 则 0肯定不会整除n!；
　　n >= m 则 m肯定可以整除n!;
　　B. 那么就只剩最后一种情况：m > n，我们从m的最小素因子取起，设素因子为i那么可以 　　求得m的素因子i的个数 nums1；再检查闭区间 i ~ n 之间的数，一共包含多少个素因子i，就可以简单的利用上面（2）中所介绍的数学公式进行计算得到nums2。如果nums2 < nums1，就表示1 ~ n中包含素因子的数量 < 除数m包含素因子i的数量，那么m必然不能整除n!，置ok = false。
　　C. 最后：如果 !ok or m > n or m == 0 则不能整除；否则可以整除
　　（5）。数字N能否表示成若干个不相同的阶乘的和：
　　这里可以选择的阶乘为：0! ~ 9!，实际上这一题与数论无关，与搜索有关。
　　分析，由于可供选择的阶乘数量较少，直接可以利用DFS搜索来做：
　　A. 首先将0 ~ 9的阶乘作一个表A[10]；再设置一个可以组成“和”的数组ans[N]。
　　B. 深度优先搜索方法：
　　search（n） {
　　for（i = n; i <= 9; i++） {
　　sum += A;    　　//求和
　　如果sum在ans数组中不存在，则将sum插入到ans[]数组中
　　search（n+1）；
　　sum -= A;     　　//回溯
　　}
　　}
　　C. 最后对于输入n，就在ans数组中查找是否存在n，如果存在，则表示n可以表示成不同的阶乘和，否则不行。

下面给大家带来的是高精度计算阶乘实例

　　#include

　　#define MAX 100000

　　using namespace std;

　　int main()

　　{

　　int n,a[MAX];

　　int i,j,k,count,temp;

　　while(cin>>n)

　　{

　　a[0]=1;

　　count=1;

　　for(i=1;i<=n;i++)

　　{

　　k=0;

　　for(j=0;j=0;j--)

　　if(a[j])

　　break;//忽略前导0

　　for(i=count-1;i>=0;i--)

　　cout<

---

作者: bysqb    时间: 2017-6-29 10:14
。服务非常好。

---

作者: zdxhz    时间: 2017-7-1 12:11
服务超好

---

作者: nidalma001    时间: 2017-7-2 20:25
很实用，用着很好。辛苦了两天，有技术小哥专业的指导，总算完成了

---

作者: 261741908    时间: 2017-7-6 23:34
意思，出差一直没顾上。微信平台开发找你们做绝对是正确的选择。服务是值得肯定的，售后也非常到位，技术支持很强大，重点是热心.不厌其烦。不像有些玩技术的那个清高啊，那个沟通难度啊真不是一般的高。

---

作者: ufo50200    时间: 2017-7-6 23:36
，服務員耐心教授，網站成功完成，多謝大家幫忙

---

作者: qiaozong01    时间: 2017-7-9 12:52
，非常满意，还会再来的。

---

作者: weipinzongmeng    时间: 2017-7-11 21:00
很快效果也很完美，特别感谢技术加班帮忙制作!@!@~~客服沟通也很愉快，好多不明白的地方客服也都耐心解答，辛苦啦

---

作者: 123    时间: 2017-7-15 13:21
师赞，服务好技术牛

---

作者: 小白    时间: 2017-7-18 21:49
不错的教程

---

作者: 西充    时间: 2017-7-19 20:45
很好，热情有耐心！

---

欢迎光临 信息发布软件,b2b软件,广告发布软件 (http://www.postbbs.com/)

Powered by Discuz! X3.2