Java教程

大数算法的总结

本文主要是介绍大数算法的总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录:

  1. 前言

  2. 大数加法

  3. 大数减法

  4. 大数乘法

  5. 大数除法

  6. 大数阶乘位数

  7. 大数阶乘求解

  8. 总结 

 


一.前言.

        众所周知,计算机数据类型的长度是有限的,因此在处理较大的数据时候会发生数据溢出,此时聪明的我们需要想办法处理这批数据,那么我们如何处理呢?答案是用数组存储数据,再做批量处理。

    不知道你们是否观察过用递归求阶乘,当n为13时(数据类型为int型),数据明显不对,有朋友可能就说了如果是longlong型数据呢?longlong型数据肯定可以求出13以上,但是100以上呢?是不是又越界了?这里我参考了其他博主的文章写了一下大数算法的有关内容。


二.正文


 一.大数加法

       所谓大数加法,就是在我们计算机数据无法存储的大数据时进行的加法运算。那我们如何实现大数加法呢,我们可以用数组,链表等结构来分段存储大数据,这里我采用 数组进行大数运算的描写。假如我们输入123456789123456 + 123这两个数据时,如果要发生相加的运算,那么第一个数字怎么存储呢?答案是用数组来存,准确点说是字符数组,我们把这两个当成一个字符串输入到一个字符数组中,然后再进行倒序处理,为什么要倒序处理呢?比如说123456789123456 + 123,这里我们把6和3相加,5和2相加,4和3相加,但是在程序中是否表达不便呢?还有一个优点是我们可以很方便的进行进位处理,所以我们采用倒序处理。那怎么倒序呢,用整形数组从下表0开始存字符数组从后往前推的字符-‘0’(这里解释一下减字符0是为了从字符转成相应的数字,如果不了解可以去查找Ascii码表)。两个数组依次进行这个操作后,那么用一个sum数组进行相加即可。具体代码实现如下:

#include "bits/stdc++.h"
#include "cstring"
using namespace std;
char s1[600],s2[600];
int a[600],b[600];
int sum[1200];
int main()
{
    int i,j,res;
    int length1,length2;
    int len;
    cin >> s1;
    cin >> s2;
    length1 = strlen(s1);
    length2 = strlen(s2);
    j = 0;
    for(i = length1 - 1 ;i >= 0;i--)
        a[j++] = s1[i] - '0';//倒转
    j = 0;
    for(i = length2 - 1;i >= 0;i--)
        b[j++] = s2[i] - '0';//倒转
    if(length1 > length2)
        len = length1;//遍历到最长的那个数字
    else
        len = length2;
    res=0;//存进位
    for(i = 0;i < len;i++)
    {
        sum[i] = (a[i] + b[i] + res) % 10;
        res = (a[i] + b[i] + res)/10;
    }
    if(res)//如果此时还存在进位
    {
        sum[i] = res;
        i++;
    }
    for(j = i - 1;j >= 0;j--)
        cout << sum[j];//从后往前打印
    cout << endl;
    return 0;
}

           


二.大数减法

      大数减法采用大数加法的思路存储数据,处理数据时从低位开始往高位减,例如123456 - 123 逆转后就是654321 - 321,这时候6 - 3,5- 2,4-1,然后其他的可以直接赋给minus数组了,如果被减数相应位数小于减数相应位数的话,我们采用借位的方式。例如1234-345,4-5<0,往前借位,借位后前一位-1,也就是3-1,(这里我默认是逆转过后的数组)。如果被减数小于减数呢?我们怎么判断呢?这时候我们只需要判断如果被减数的长度小于减数的长度,那么我们可以直接输出一个负号,然后再用减数-被减数。有人又问了,那如果两个数位数相等,且被减数小于减数呢?此时我们只需要把逆转后的数组从前往后遍历,如果发现被减数位数小于减数位数的话,我就可以判断出来了。直接输出一个负号,然后用减数减去被减数,总的来说思路就是如果被减数大于减数,那么可以直接减去就行;如果被减数小于减数,就直接输出一个负号,然后用减数减去被减数。例如123456 - 789 ,123456是被减数,789是减数,别搞混了啊。接下来贴出我的代码实现(代码有点长,有能力的小伙伴可以自行实现):

#include "bits/stdc++.h"
using namespace std;
char s1[100],s2[100];
int length1,length2;
int a1[100],b2[100];
int i,j;
int len;
int minus1[200];
int main()
{
    cin >> s1 >>s2;
    length1 = strlen(s1);
    length2 = strlen(s2);
    j=0;//从头开始添加a1数组
    for(i = length1 - 1;i >= 0;i--)
    {
        a1[j++] = s1[i] - '0';//倒置
    }
    j=0;//从头开始添加b数组
    for(i = length2 - 1;i >= 0;i--)
    {
        b2[j++] = s2[i] - '0';
    }
    len = (length1 > length2)?length1 : length2;//len为两个字符串最长的那个
    if(length1 - length2 > 0)//第一个数组减第二个
    {
        for(i = 0;i < len;i++)
        {
            if(a1[i] >= b2[i])//如果大于的话直接减
                minus1[i] = a1[i] - b2[i];
            else
            {
                minus1[i] = a1[i] + 10 -b2[i];
                a1[i+1] = a1[i+1] -1;
            }
        }
        for(j = len -1;j >= 0;j--)//因为两个数长度不一样,所以相减一定不为0,否则一定要保留最后一个0
            if(minus1[j] == 0)
                len--;//进行删0操作
            else
                break;
    }
    else if(length1 - length2 < 0)//第二个数组减第一个
    {
        cout << "-";//输出负号
        for(i = 0;i < len;i++)
        {
            if(b2[i] >= a1[i])//如果大于的话直接减
                minus1[i] = b2[i] - a1[i];
            else
            {
                minus1[i] = b2[i] + 10 -a1[i];
                b2[i+1] = b2[i+1] -1;
            }
        }
        for(j = len -1;j >= 0;j--)//因为两个数长度不一样,所以相减一定不为0,否则一定要保留最后一个0列如99-100
            if(minus1[j] == 0)
                len--;//进行删0操作
            else
                break;
    }
    else//如果相等则判断谁大谁小
    {
        for(i = len - 1;i >= 0;i--)
        {
            if(a1[i] == b2[i])
                continue;
            else if(a1[i] > b2[i])
                break;
            else
                break;
        }
        if(a1[i] > b2[i])
        {

            for(i = 0;i < len;i++)
            {
                if(a1[i] >= b2[i])//如果大于的话直接减
                    minus1[i] = a1[i] - b2[i];
                else
                {
                    minus1[i] = a1[i] + 10 -b2[i];
                    a1[i+1] = a1[i+1] -1;
                }
            }
            for(j = len -1;j >= 0;j--)//因为两个数长度不一样,所以相减一定不为0,否则一定要保留最后一个0
                if(minus1[j] == 0)
                    len--;//进行删0操作
                else
                    break;
        }
        else if(a1[i] < b2[i])
        {
            cout << "-";//输出负号
            for(i = 0;i < len;i++)
            {
                if(b2[i] >= a1[i])//如果大于的话直接减
                    minus1[i] = b2[i] - a1[i];
                else
                {
                    minus1[i] = b2[i] + 10 -a1[i];
                    b2[i+1] = b2[i+1] -1;
                }
            }
            for(j = len -1;j >= 0;j--)//因为两个数长度不一样,所以相减一定不为0,否则一定要保留最后一个0列如99-100
                if(minus1[j] == 0)
                    len--;//进行删0操作
                else
                    break;
        }
        else
        {
            printf("0");
            return 0;
        }
    }
    for(j = len-1;j >= 0;j--)
        cout << minus1[j];
    cout << endl;
    return 0;
}

 


三.大数乘法

      不知道小伙伴们是否了解过计算器的原理,我曾有幸在图书馆了解过一本有关计算器原理的书,里面就介绍了一下计算器的四则运算,所谓乘法就是多次加法,小学时候我们还不懂乘法的时候计算5*3,就会把5加上三次,其实这个就是乘法的原理,多次累加。那我们如何用程序实现它呢,比如说123 * 45 我们逆转后为321 *54 ,3*5就是15个1,3*4就是12个十, 2*5就是10个十,2*4就是8个一百,然后1*5就是五个一百,1*4就是4个1千,然后将结果进位即可。具体代码实现如下:

#include "bits/stdc++.h"
#include "cstring"
using namespace std;
char s1[100],s2[100];
int a1[100],b2[100];
int multi[200];
int main()
{
    int i,j;
    cin >> s1;
    cin >> s2;
    j = 0;
    for(i = strlen(s1) - 1;i >= 0; i--)
        a1[j++] = s1[i] - '0';
    j = 0;
    for(i = strlen(s2) - 1; i >= 0; i--)
        b2[j++] = s2[i] - '0';//翻转数字
    for(i = 0;i < strlen(s1); i++)
        for(j = 0;j < strlen(s2); j++)
        {
            multi[i + j] = multi[i + j] + a1[i] * b2[j];//先不计算进位
        }
    for(i = 0;i < strlen(s1) + strlen(s2); i++)//两数相乘最大位数为两数位数相加
        if(multi[i] >= 10)
        {
            multi[i + 1] += multi[i] / 10;//注意数组要提前开大一点,否则会越界
            multi[i] = multi[i] % 10;
        }
    for(i = strlen(s1) + strlen(s2) - 1;i >= 1; i--)//删除多余0的操作
        if(multi[i] != 0)
            break;
    while(i >= 0)
    {
        cout << multi[i--];
    }
    cout << endl;
    return 0;
}

四.大数除法

#include "bits/stdc++.h"
#include "cstring"
using namespace std;
char s1[100],s2[100];
int a1[100],b1[100];
int len1,len2,len;//len计算len1和len2之间差的长度
int z[100];
int temp;
int subtraction(int length1,int length2)
{
    int i;
    for(i = 0;i < length2;i++)
    {
        if(a1[i] >= b1[i])
        {
            a1[i] -= b1[i];
        }
        else 
        { 
            a1[i] = a1[i] + 10 -b1[i];//如果这个数小于的话,则要进位进行减
            a1[i + 1] -= 1;//借位之后减1
        }
    }
    for(i = length1;i > 0 && !a1[i];i--);//消除被除数的前缀 必须为length1开始
    return i + 1;//i每次都会进行判断,所以要加1
}
int judge(int length1,int length2)
{
    int i;
    if(length1 < length2)
        return -1;//小于返回-1
    else
    {
        for(i = len1 - 1;i >= 0;i--)
        {
            if(a1[i] == b1[i])
                continue;
            if(a1[i] < b1[i])//小于则返回-1
                return -1;
            if(a1[i] > b1[i])//大于则返回1
                return 1;
        }
    }
    return 0;//如果相等就返回0
}
int main()
{
    int i,j;
    cin >> s1;
    cin >> s2;
    len1 = strlen(s1);
    len2 = strlen(s2);
    if(len1 < len2)
    {
        cout << "consult: 0";
        cout << "mod : ";
        puts(s2);
    }
    else 
    {
        for(i = len1 - 1,j = 0;i >= 0;i--)
        {
            a1[j++] = s1[i] - '0'; //反转数组  调试成功    
        }
        for(i = len2 - 1,j = 0;i >= 0;i--)
        {
            b1[j++] = s2[i] - '0'; //反转数组  调试成功
        }  
        len = len1 - len2;
        for(i = len1 -1 ;i >= 0;i--)
            if(i >= len)
                b1[i] = b1[i-len];
            else 
                b1[i] = 0;
        len2 = len1;//同步字符位数  调试成功
        for(j = 0;j <= len;j++)//这一步主要是处理每一位上的
        {
            z[len - j] = 0;
            while((temp = judge(len1,len2)) >= 0)
            {
                z[len - j]++;//如果满足则可以加1次
                len1 = subtraction(len1,len2);
                cout << len1 << " " << j << endl;
                cout << a1[0] << " " << a1[1] << endl;
            }
            if(temp < 0 && b1[0] == 0)//除数减1 如果前缀不为0的话可以结束了
            {
                for(i = 0;i < len2 - 1;i++)
                {
                    b1[i] = b1[i + 1];
                }
                b1[len2 - 1] = 0;
                len2--;//减小除数位数
            }
        }
    }
    for(i = len;i > 0;i--)
    {
        if(z[i])
            break;//消除商的前缀0
    }
    cout << "consult:";
    while(i >= 0)
        cout << z[i--];
    cout << endl;
    cout << "mod:";
    for(i = len1 - 1;i > 0;i--)
    {
        if(a1[i])
            break;//消除商的前缀0
    }
    if(len1 == 0)
        i = len1;
    while(i >= 0)
        cout << a1[i--];
    cout << endl;
    return 0;
}

五.大数阶乘位数

不知道小伙伴是否碰到过用int型求阶乘时,会发现数据明显不对,比如说求13的阶乘,我们发现打印13的阶乘为

然而我们可以百度搜索阶乘计算器后可以得出

那么时哪里出错了呢,答案是数据类型长度不够。所以我们应该改变策略,用数组存储数据,再批量处理。接下来我们先介绍两个计算阶乘位数的算法。1.用对数函数求解阶乘位数

2.用Stirling公式求解位数。再介绍如何进行阶乘的计算。


     1.对数函数求位数

        lg1+lg2+lg3+lgn,由对数函数特性可知,lga+lgb等于lga*b,这时候我们发现真数a*b就可以替换成我们的1和2-n。但此时为什么不会越界呢,因为lg函数返回的是一个double型,所以我们用一个double型的数去存这个值就行,这个值是较小的,所以不会发生数据溢出的情况。需要注意的是我们的位数初始化为1,输出的时候应该把位数取整后输出。具体代码如下:

#include "bits/stdc++.h"
#include "cmath"
using namespace std;
int main()
{
    double sum = 0;
    int i;
    for(i = 1;i <= 200;i++)
        sum += log10(i);//计算阶乘的位数 利用log10的特性进行判断
    cout << (int)(sum + 1) << endl;//sum刚开始为1位数
    return 0;
}

     2.Stirling公式求位数

Stirling公式证明过程复杂,我只是个记公式的小菜鸡,请移步大佬的blog进行思考,这里给出链接如下https://www.cnblogs.com/jokerjason/p/9525590.html,这里我贴出代码实现

#include "bits/stdc++.h"
#include "cmath"
using namespace std;
const double e = 2.7182818284;//小数越多精度越高
const double Pi = 3.1415926535;
int main()
{
    int res = 0;
    int n;
    cin >> n;
    res = 0.5 * log10(2 * Pi * n) + n * log10(n/e);
    cout << res + 1;
    return 0;
}

六.大数阶乘求解

      阶乘求解得思路就是用一个数组存储,然后每次进来一个乘数,把每个数组元素都乘以这个乘数,如果发现了高位要溢出了,那么我们可以增加一位存高位,然后就是处理进位问题了,我们依然是从低位开始向高位遍历,如果大于10的话我们就往前进位,这里我才用的是一个数组元素存6位的方式,读者可以采用1位存法实现大数阶乘。具体代码如下:

#include "stdio.h"
int main()
{
	int i = 1,high = 0,tag = 0;//tag为低位,high为高位,i为阶乘值
	int a[1000] = {0};//计算精确度为7000位
	a[high] = 1;//把第一次运算赋初值为1
	while(i <= 100)
	{
		for(tag = 0;tag <= high; tag++)
			a[tag] *= i;
		if(a[high] >= 1000000)
			high += 1;
		for(tag = 0;tag <= high; tag++)
		{
			if(a[tag] >= 1000000)
				{
					a[tag + 1] += a[tag] / 1000000;
					a[tag] = a[tag] % 1000000;
				}
		}
		i++;
	}
	tag = high;
	while(high >= 0)
	{
		if(high == tag)
			printf("%d",a[high]);
		else
			printf("%06d",a[high]);//这是一个输出小技巧,左边补0,如果是-06d的话是右边补零
		high--;
	}
	return 0;
}

七.总结

第一次发表博客,写的不好的地方请及时指出,我会修改的!另外学习是一件很充实又很快乐的事情,一起加油吧!


 

这篇关于大数算法的总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!