资源预览内容
第1页 / 共17页
第2页 / 共17页
第3页 / 共17页
第4页 / 共17页
第5页 / 共17页
第6页 / 共17页
第7页 / 共17页
第8页 / 共17页
第9页 / 共17页
第10页 / 共17页
亲,该文档总共17页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
高精度教案,(by vilinov),高精度运算是什么?,就是有很多很多位数的运算。,那这个问题如何处理?,比如说计算2128。 这个数大大小已经超过了int64,如果使用一个int64来存储那么最后得出的结果一定是0。,如何实现高精度?,刚才那个问题2128,如果一个int64不过,那用两个不就完了。是的,高精度就是这个思想,用多个变量去存储比较大的数。,如何实现,创建高精度量?,字符 甲255。 #中文伪码,可以用每个字符存储一位数字的方法来实现。,高精运算,加 减 乘 除*(noip不做要求),其实各个运算都是用的我们笔算的算法。,关于存储方式,高精度其实使用的是逆序存储比如序列:123456789 在计算机里的存储顺序是987654321。 为什么这样存呢? 加、减、乘的时候都需要从低位到依次去运算,加和乘运算时可能会增加位数,如果顺序存储对扩充位数不利。,高精加,void add() lenAns=max(lenX,lenY); for(int i=0;ilenAns;i+) ansi+=xi+yi; ansi+1=ansi/10; ansi%=10; anslenAns?lenAns+:0; ,char x255; char y255; char ans255; lenX=strlen(x); lenY=strlen(y);,高精乘,void mul() lenAns=lenX+lenY; for(int i=0;ilenX;i+) for(int j=0;jlenY;j+) ansi+j+=xi*yj; ansi+j+1+=ansi+j/10; ansi+j%=10; anslenAns-1?:lenAns-; ,高精减,void min()/保证xy lenAns=lenX; for(int i=0;ilenAns;i+) ansi=(xiyi?xi+1-,10:0)+xi-yi; for(;anslenAns=0 ,如何读入一个高精度?,文件读入: 字符 甲255。 文件读入,文件指针等于“1.in”,甲。 #打开文件,“pi.in”。 #读入,甲。,内部读入: 略(大体思想就是找到最高一位,然后依次。),然后将数组逆序。Ok。,输出,逆序输出,ok。,逆序代码,输入:for(int i=0;ilenX;i+) xi=alenX-i-1-0;,输出:for(int i=lenAns-1;i=0;i-) fputc(ansi+0,out);,做个题,算吧! 1.78+96-9992 2.50!,优化,一个int存储4位,一个例子: 输入:239685421 存储:5421 3968 2,只用修改输入输出,因为只把char改成了int。p语言要把乘改一下。,难题:输入输出,长度的确定,string a,b; int xMAXLEN/4+1,yMAXLEN/4+1; 读入字符串a; 读入字符串b; int lenA=len(a); int lenB=len(b); int lenX=(lenA+3)/4; int lenY=(lenB+3)/4;,麻烦的转换,for(int i=0;ilenX;i+) xi=alenA-4*i-1+ alenA-4*i-2*10+ alenA-4*i-3*100+ alenA-4*i-4*1000;,输出,for(int i=lenAns-1;i=0;i-) fprintf(out,%04d,ansi);,运算,与前面几乎一样,看我的程序就有体现。,题目,有一些神奇的材料,这些材料都有自己的属性值p,当一个材料被加工的时候,将会收到p*(2k)个收益。当前只有一个工匠加工,k为加工的材料的顺位。如p=3的材料第二个被加工,则收益为12。没有浪费的材料。 输入格式(m.in): n(n个材料) 下面n行是每个材料的属性值 输出 最大总收益。 样例输入: 3 2 3 4 数据规模:争取卡没优化的高精,样例输出: 46,高精度的一些说明,一般数据的输入,或中间过程,或输出数据中有超过2.1*109,使用高精度。要根据数据规模计算极端数据大小。如07年第三题,通过计算数据规模可得知此题使用高精度。 高精度运算的时间复杂度与位数有关加减为o(n),乘为o(n2) 一般出现高精度后会降低o(N)中N的大小。,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号