枚举 模拟 高精度 —— 跟WilliamYan一起学算法

大家好!欢迎来到《跟WilliamYan一起学算法》。今天是我们见面的第一天,我们将要学习的是算法中最为简单的两种——模拟枚举,以及与之相关的高精度计算(大数计算)。

枚举法

所谓枚举法,指对要解决问题的所有可能情况,一一枚举进行检验,从中找出符合要求的答案,因此枚举法是通过牺牲时间来换取答案的全面性。一般也被称为暴力法。

枚举法算法简单,但是运算量大。对于可以确定解的值域又一时找不到更好的算法的时候可以使用枚举法。

优缺点

优点

容易理解,容易编写

算法正确性无须证明

缺点

效率过低

优化

  • 减少状态总数
  • 加快判断速度

例题

无线网络发射器选址(NOIP2014 提高D1T1)

直接枚举所有可能性即可。

模拟法

就是按照题目给的操作,用代码依次描述出来即可。 就是这么简单。

例题

金币

这是普及组的一道题,是NOIP2015的T1,这道题就是模拟,直接模拟题目中给的要求,第几天该加多少金币,然后就可得到结果。

神奇的幻方

这是2015提高组的D1T1,这道题题目非常直白,直接模拟即可。

玩具谜题

这是NOIP2016的提高组的D1T1,一样的模拟,按照题目意思做即可。

由于纯模拟几乎没有技术含量,此处不多做讨论。

高精度运算

c++实现

发现了一篇真的厉害的文章。

-[以下文章来源]: https://www.cnblogs.com/hugeNumber/articles/5376906.html "大数处理——c++实现"

  本课题来自我的c++编程作业,文章利用大数处理类,类名:hugeNumber来对大数(编译器自定义的数值类型无法处理的数)进行四则运算(大数加法、大数减法及大数乘法的运算,除暂时没实现)和按精度四舍五入,自定义科学计数法等。内容广泛涉及运算符重载、字符连接、字符加减和字符乘除等作者原创函数。重要提示:本文涉及的所有函数使用的进制皆为10进制。

一、解题思路

1 核心思想

文章用hugeNumber类对大数进行操作。前提假设,处理的数都使用科学计数法(未用科学计数法表示的大数,指数默认为0),hugeNumber类数据成员如下:


class hugeNumber{                  //定义大数,10进制
private:
      /*char deciNum[MAXSIZE];  */          
       char *deciNum;                 //尾数
       long  exponent;               //指数
       short  sign;                       //符号位,取-1或1
       int  set_dot;                     //小数点位置,-1表示没有小数点
}

我将科学计数法分解为各个组成部分如图 1所示,其中:

deciNum,科学计数法中的尾数,我用最大512字节表示该数;

exponent,科学计数法中的指数,我用long int 表示;

sign,整个数据的正负号;

set_dot,当前尾数小数点真实位置,从0开始计数。

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》
图1

当从cin输入流获得一串字符,首先判断其是否为数值

    if(!isNumber(nptr))

       {

              cout<<"This is not a number! " ;

             exit(EXIT_FAILURE);                         //非正常退出

     }

确定为数值后,hugeNumber类接受该字符串,并将其转换成如上所示4个属性,其构造函数原型为:

hugeNumber::hugeNumber(const char *nptr);

也可按提示,分别录入尾数部分、指数部分和正负号。其函数实现:


istream& operator>>(istream &in,hugeNumber &obj) //该函数声明为hugeNumber类友员函数

{
        char ch;
        in>>ch;
        if(ch = '-')obj.sign = -1;
        else obj.sign = 1;
        in>>obj.deciNum;
        in>>obj.exponent;
        return in;
}

当我们获得某一hugeNumber类对象的各个属性值,便可以对该对象进行操作了。

2 大数按精度四舍五入

函数原型及方法如下:

void my_round(hugeNumber &hu ,int prec)  //precision,规定的精度位

首先,对hugeNumber类的对象hu按指定自定义规格化。

norm(hu, -hu. exponent - prec);

该语句表示,将hu对象按指定精度规格化,并保持数值大小不变。例如,hu为$3.14159e2$,现在要求精确度为2,那么先将hu规格化为$31415.9e-2$。

接下来,判断小数点后一位是否大于0.5,如果大于0.5,给尾数个位加1,否则不加1,并且将小数点位的 . 修改为字符串结束符\0 ,因为尾数使用字符串表示,所以规格化后的小数全部被截断。如图2所示

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》
图2

2 大数加法运算

函数原型及基本算法思想描述:

2.1 两个整数大数相加

字符串a与字符串b整数字符串相加,加法考虑到进位,因为较大字符串a的2倍也只能产生1个进位,所有只预留1个进位给最终结果字符串c。

加法算法过程:

首先,判断a、b皆为整数,当hugeNumber类对象的数据成员set_dot为-1,表示该大数为整数;a、b对介后相加;c的指数为a、b对介后的指数。

其次,strlen(a)strlen(b)获得a、b字符串长度,并确定保存结果的字符串长度,c字符串长度为a、b最长的长度加1(假设a是较长的大数)clength = strlen(a) + 1;

最后,从a、b字符串尾部开始从后往前相加,相当于从数的个位开始相加,如有进位,设置int变量 flag表述进位,flag最大为1,你知道为什么不能为2吗?待短字符串相加结束,将a(假设a是较长的大数)剩余的部位复制到c中,但仍然考虑与b累加的进位,如果a余下的是9999,切好又有进位,那么就要一直进位到数的最高位。如图 3所示。

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》
图3

2.2 整数大数与带小数大数相加

整数大数与带小数大数相加,又分为两种情况:整数大数的整数部分大于带小数大数的整数部分和整数大数的整数部分小于带小数大数的整数部分。无论如何,a、b对介后才能相加;c的指数为a、b对介后的指数。所有这里尾数出现的整数和小数都是相当而已的,你完全可以把a、b都规格化成大整数,再相加。分别见图4 、图 5 。

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》

图 4 整数大数的整数部分大于带小数大数的整数部分

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》

图 5整数大数的整数部分小于带小数大数的整数部分

由图 4 所知,c字符串(保存最终结果)小数部分为b字符串小数部分,直接复制,b小数点前半段(b字符串整数部分)与整数大数a字符串相加同图 3 所示。

c的整个长度 = a 的整个长度 + b的小数长度 + 1 ;

5 表示整数大数b的整数部分小于带小数大数a的整数部分,c的整个长度 = a 的整个长度 + 1 ;a的小数点后半段直接复制到c字符串中,a整数部分与整数大数b相加算法同图 3 所示。

2.3 两个带小数的大数相加

两个带小数的大数相加,分两张情况讨论:一种是a的整数部分大于b的整数部分,但a的小数部分短于b的小数部分,如图 6 所示。另一种情况,a无论是整数部分还是小数部分,都长于等于b,如图 7 所示。无论如何,a、b对介后才能相加;c的指数为a、b对介后的指数。所有这里尾数出现的整数和小数都是相当而已的,你完全可以把a、b都规格化成大整数,再相加。

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》

图 6 字符串a的整数部分大于b的整数部分,但a的小数部分短于b的小数部分

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》

图 6-1 补0处理,a、b字符可以从个位向高位依次相加

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》

图 7 a无论是整数部分还是小数部分,都长于等于b

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》

图 7-1 补0处理小数,a、b字符可以从个位向高位依次相加

3 大数减法运算

前提:无论如何,a、b对介后才能相减;c的指数为a、b对介后的指数。

3.1 两个整数大数相减

减法虽然没有溢出,但是会有正负,我用sign返回两个大数相减后的正负。因此,在做减法运算时,先判断结果的正负,在用较大的数减去较小的数。假设c = a – b;a > b,sign为正;当a < b,sign为负,如图 8 所示。

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》

图 8两个整数大数相减

3.2 一个整数大数与另一个带小数大数间相减

减法虽然没有溢出,但是会有正负,同样用sign返回两个大数相减后的正负。此处有两种情形:一种是整数大数大于带小数的大数,另一种情形是整数大数小于带小数的大数。假设a是整数大数,b是带小数的大数。

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》

图9 整数大数大于带小数的大数

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》

图 9-1 整数大数大于带小数的大数处理

第一种情形整数大数大于带小数的大数,先将整数大数a整数减 1,其小数 设为0.999+0.001;分别将0.999与b的小数相减,整数-1后与b的整数相减。见图9-1。

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》

图 10整数大数小于带小数的大数

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》

图 10-1 整数大数小于带小数的大数处理后相减

第二种情形整数大数小于带小数的大数,sign取-1,c = a – b变换为 c = -(b – a);

b 小数位直接复制给c,整数部分按照两个整数大数相减处理。

3.3 带小数大数间相减

有下列四种情形:

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》

图 11 a的整数大于b,a的小数短于b

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》

图 12 a的整数、小数都短于b

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》

图 13 a的整数、小数都长于b

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》

图 14 a的整数小于b,a的小数长于b

3 大数乘法运算

首先将a、b规格化为尾数为整数的大数,c的指数等于a、b规格化后的指数相加。有效位数长的做被乘数,位短的做乘数。假设a的长度大于b;

《枚举 模拟 高精度 —— 跟WilliamYan一起学算法》

图 15

整个乘法过程,仿真实数据相乘,将所有中间结果累加到c中,如 c = tmp1 + tmp2 + tmp3 + … ;得到最终结果,由于博主比较懒,具体看算法实现。见图 15所示。

二、具体算法实现

请移步原博客查看

才不是我太懒了不想贴呢

提示
若编译出现下列错误:error C4996: ‘strcat’: This function or variable may be unsafe.

属兼容问题,请参照:http://heyunhuan513.blog.163.com/blog/static/160204220153894725887/

-[以上文章来源]: https://www.cnblogs.com/hugeNumber/articles/5376906.html "大数处理——c++实现"

总结

众所周知,枚举、模拟是算法中最为简单又最为基础的两种。尽管如此,在日常生活中我们也经常使用到。@FLY就曾说过,“所谓人工智能就是纯模拟”,的确不无道理。若是这两种算法学不好,接下来的算法也就无从学起了。希望大家可以多多学习,建立起一种良好的计算机思想。
—-William Yan

©2019 William Yan

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据