高精度的十进制运算.ppt

《高精度的十进制运算.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、全国奥林匹克信息学联赛辅导讲义虽然最近五年全国奥林匹克信息学复赛中含许多可“一题多解”的试题，但如果按照较优算法标准分类的话，大致可分为题型题　　　目与课内知识和编程基础相关校门外的树、自由落体、级数求和、乒乓球、麦森数、不高兴的津津、花生采摘、津津的储蓄计划、陶陶摘苹果、循环、谁拿了最多奖学金、2k进制数、数列模拟守望者的逃离、字符串的展开构造法均分纸牌、传染病控制、火星人、篝火晚会、作业调度方案、纪念品分组数据结构字符近似查找、合并果子（堆排序）、栈、FBI树（二叉树）、神经网络（图）、等价表达式（栈

2、）、明明的随机数（快速排序）、Jam的计数法（字串处理）、奖学金（排序）、统计数据（排序）、树网的核（图）枚举法虫食算、侦探推理回溯法选数、字串变换动态规划过河卒、数字游戏、加分二叉树、合唱队形、采药、过河、能量项链、金明的预算方案、开心的金明、双塔问题（高精度）、矩阵取数游戏（高精度）几何计算矩形覆盖联赛的科学性和公信力在增强1、试题的难度和知识结构趋于合理。“抬高门槛、减少偏题”。这两年即没有可直译编程的基础题(最简单的题为排序题或动态规划),亦没有出现非“全军覆没”不可的偏题。2、去年增加了模拟题；

3、新增了排序类试题（普及组是多域数据的排序，提高组要求采用高效的排序算法）；高精度运算首次引入提高组。3、对选手解题能力和综合素质的要求逐年提高。这两年没有单纯的搜索题和可直接套用经典算法的简单题，而数据结构类、构造类和动态规划类的试题增加，以考验选手的数学建模能力和创新意识。4、分数的阶梯层次趋于科学。只懂语言、不懂数据结构和算法的选手拿低分；虽懂编程知识但缺乏数学思维和创新意识的选手拿中等分；综合素质强的选手拿高分（提高组满分的选手不多，因为有一道难度较大的综合题)。高精度运算排序思想及其应用模拟法图论

4、讲座内容高精度运算转换数据类型加法运算减法运算乘法运算除法运算改善高精度运算的效率分析近几年联赛中高精度类的试题数据类型的转换在变量运算对象的数值范围为任何数据类型所无法容纳的情况下,采用整数数组（每一个元素对应一位十进制数，由其下标顺序指明位序号）。1、采用数串形式输入，并将其转化为整数数组。2、用一个整数变量记录数据的实际长度（即数组的元素个数）3、该数组的运算规则如同算术运算。数据结构与转换方法typenumtype=array[1..500]ofword；{整数数组类型}vara，b:numtyp

5、e；{a和b为整数数组}la，lb:integer；{整数数组a的长度和b的长度}s:string；{输入数串}将数串s转化为整数数组a的方法如下：k←length(s)；fori←1tokdoa[k-i+1]←ord(s[i])-ord(‘0’)；加法运算c←a+b(a、b、c为numtype类型)vara,b,c:array[1..201]of0..9;n:string;lena,lenb,lenc,i,x:integer;beginwrite('Inputaugend:');readln(n);le

6、na:=length(n);fori:=1tolenadoa[lena-i+1]:=ord(n[i])-ord('0');{加数放入a数组}write('Inputaddend:');readln(n);lenb:=length(n);fori:=1tolenbdob[lenb-i+1]:=ord(n[i])-ord('0');{被加数放入b数组}i:=1;while(i<=lena)or(i<=lenb)dobeginx:=a[i]+b[i]+xdiv10;{两数相加，然后加前次进位}c[i]:=xmo

7、d10;{保存第i位的值}i:=i+1end;ifx>=10{处理最高进位}thenbeginlenc:=i;c[i]:=1endelselenc:=i-1;fori:=lencdownto1dowrite(c[i]);writeln{输出结果}end.N进制运算1、当前位规范由mod10改为modn2、进位处理由div10改为div103、运算规则不变求回文数若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。例如：给定一个10进制数56，将56加65（即把56从右向左读），得

8、到的121是一个回文数。又如，对于10进制数87：STEP1：87+78=165STEP2：165+561=726STEP3：726+627=1353STEP4：1353+3531=4884在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。写一个程序，给定一个N（2≤N≤10，N=16）进制数m，m的位数上限为20。求最少经过几步可以得到回文数。如果在30步以内（包括30步）不可能得到回文数，则输出“