首页 > 其他分享 >关于大数乘法的数组类型问题(int 还是char)

关于大数乘法的数组类型问题(int 还是char)

时间:2023-04-18 23:12:55浏览次数:61  
标签:lenc 10 last 大数 int char ++

可以知道在处理高精度乘法的时候,我们是不考虑当场进位的,在所有位数都模拟完竖式乘法后才进行逐位进位,这就要求存储每个位的数组保证不会爆掉溢出

众所周知char类型最多只能存储到255,非常非常容易溢出成负数,对于char型数组要考虑每一步乘法都要进位。

而int型数组最大21亿就不用考虑这种问题,当然是在内存允许的前提下

P1045 [NOIP2003 普及组] 麦森数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn),举个例子

这道题要求高精度的乘法,我一开始开的就是char型数组,当输入P较小时尚可,当P超过50时就会爆负数,我真的会谢,找了半天没找到问题,最终发觉应该是char型变量爆了,随后改为int就好了

如图

void Big_Multiple(char A[], char B[], int* lena, int lenb)
{
    char C[1000000]={0};
    for (int i = 0; i < *lena; i++)
    {
        for (int j = 0; j < lenb; j++)
        {
            C[i + j] += A[i] * B[j];
        }
    }
    int lenc = *lena + lenb - 1;
    int last = 0;
    for (int i = 0; i < lenc; i++)
    {
        int Temp = C[i] + last;
        C[i] = Temp % 10;
        last = Temp / 10;
    }
    while (last)
    {
        C[lenc++] = last % 10;
        last /= 10;
    }
    for (int i = 0; i < lenc; i++)
        A[i] = C[i];
    *lena = lenc;
}

char型数组,结果如下

(算的是2的P次方,用了快速幂),可以看到当P大于30就开始爆负数了

下面是改为int后的

void Big_Multiple(int A[], int B[], int* lena, int lenb)
{
    int C[1000000]={0};
    for (int i = 0; i < *lena; i++)
    {
        for (int j = 0; j < lenb; j++)
        {
            C[i + j] += A[i] * B[j];
        }
    }
    int lenc = *lena + lenb - 1;
    int last = 0;
    for (int i = 0; i < lenc; i++)
    {
        int Temp = C[i] + last;
        C[i] = Temp % 10;
        last = Temp / 10;
    }
    while (last)
    {
        C[lenc++] = last % 10;
        last /= 10;
    }
    for (int i = 0; i < lenc; i++)
        A[i] = C[i];
    *lena = lenc;
}

可以看到即使P为10000还没爆负数,完美

当然不难发现我们并不需要将所有数组都开成int型,只有一个数组需要为int型那就是高精度乘法时接受加和的那个数组,其他数组为char型即可

void Big_Multiple(char A[], char B[], int* lena, int lenb)
{
    int C[1000000]={0};//就是这个数组需要设为int型,其他数组设为char型即可
    for (int i = 0; i < *lena; i++)
    {
        for (int j = 0; j < lenb; j++)
        {
            C[i + j] += A[i] * B[j];
        }
    }
    int lenc = *lena + lenb - 1;
    int last = 0;
    for (int i = 0; i < lenc; i++)
    {
        int Temp = C[i] + last;
        C[i] = Temp % 10;
        last = Temp / 10;
    }
    while (last)
    {
        C[lenc++] = last % 10;
        last /= 10;
    }
    for (int i = 0; i < lenc; i++)
        A[i] = C[i];
    *lena = lenc;
}

 

标签:lenc,10,last,大数,int,char,++
From: https://www.cnblogs.com/WKWKSL/p/17331587.html

相关文章

  • ASUS ZenBook Duo 14 UX481电脑 Hackintosh 黑苹果efi引导文件
    原文来源于黑果魏叔官网,转载需注明出处。(下载请直接百度黑果魏叔)硬件型号驱动情况主板ASUSZenBookDuo14UX481处理器•IntelCorei7-10510U•IntelCorei5-10210U已驱动内存Internal4GB2666+Changeable8GB2666memory已驱动硬盘Intel660pNVMeSSD已驱动显卡IntelUH......
  • MASA MAUI Plugin (八)Android相册多选照片(Intent 方式)
    MASAMAUIPlugin(八)Android相册多选照片(Intent方式)背景MAUI的出现,赋予了广大Net开发者开发多平台应用的能力,MAUI是Xamarin.Forms演变而来,但是相比Xamarin性能更好,可扩展性更强,结构更简单。但是MAUI对于平台相关的实现并不完整。所以MASA团队开展了一个实验性项目,意在对微软MA......
  • echarts相关问题
    解决echarts下钻地图,在平移和缩放后,下钻到下一级时生成的地图不在容器中间,会跑到容器外面去。 myChart.setOption(option,true)问题:echart地图三级下钻地图在平移和缩放后,点击到省,由于中心点的偏移,省跑到容器以外的地方去了,导致新生成的地图看不见。解决方法:后来发现,是重新绘制......
  • Go: default print format
      slice,map即使为nil打印格式和空元素的情况一样,chan,func,interface,pointer为nil时,打印<nil>当chan,func,pointer赋值后,都打印地址,interface赋值后,永远打印其dynamicvalue的格式packagemainimport"fmt"typeIinterface{m()}typeT[]bytefu......
  • 分投趣(Fintoch)系统开发(详细及方案)
    什么是佛萨奇原力FORGE?佛萨奇原力FORCE是在链上部署的一个智能合约BSC智能链是基于全球第一交易所网的数字钱包智能链公链开发的一个独立公链。FORGE循环仪中使用的矩阵大小为3×1和2×2。3×1矩阵本质上很简单,只需要填充三个位置即可。2×2矩阵从第一层的两个位置开始,然后扩展......
  • 分投趣Fintoch系统开发案例智能合约搭建
    在这个技术教程中,你会学习到怎样开发一个end-to-end的dApp。在dApp中,用户可以通过一个智能合约,获取和存储ETH的当前价格。这个教程demo代码存储在Github中。 编译之后,就可以部署到区块链上。 在migrations文件夹下已经有一个1_initial_migration.js部署脚本,用来部署Migrations.so......
  • 人工智能、大数据、云计算、机器学习和深度学习,主要有什么关系?
    这些概念是当下的热点,它们本身并不复杂。相信我的回答能让你对这些概念以及它们之间的联系有一个清晰的了解。我的主要研究方向是大数据和人工智能,所以机器学习、深度学习、云计算等技术也都接触过。这些概念之间也确实有很多关联,下面我主要从应用的角度来阐述一下他们之间的联系。......
  • 大数据的快速崛起,离不开数据、区块链和算法的支持
    事实上,自2001年来,大数据已然呈现出爆炸式增长。经过多年发展,大数据的应用已经帮助我们开发了更多、更高端的技术在我们的工作、生活中。与此同时,大数据也衍生出了其他技术,比如人工智能、机器学习等。那么,放眼未来,大数据又将如何开启新征程?1.通过数据,更好赋权这个意思就是我们应该给......
  • 大数据的安全防护,带来了哪些全新的挑战,建设数据防护体系的思路是什么?
    大数据时代,数据的产生、流通和应用更加普遍和密集。然而,新的技术、新的需求和新的应用场景给数据安全防护带来了全新的挑战。一是新技术带来的挑战。分布式计算存储架构、数据深度发掘及可视化等新型技术能够大大提升数据资源的存储规模和处理能力,但也为数据安全保护带来......
  • 企业运用大数据,需要以下三种人才?
    大数据的意思是,企业能汇集到庞大的资料量,也有能力分析这些资料,统计身为汇整说明资料意义的科学,因而成为当红的趋势。因此,为了善加运用大数据,经理人更需要具备统计的素养。大数据能够做到什么,可以从一个故事讲起。有一天,百货公司寄了一份婴儿用品型录给你未婚的女儿。你认为这是对你......