切换到宽版
发帖 回复
返回列表
  • 6547阅读
  • 4回复

什么是高精度运算啊？？、谁来帮帮我 [复制链接]

 上一主题 下一主题
离线weipengjie
OIFans入门选手
 
只看楼主 倒序阅读 0 发表于: 2006-07-11
从1 到50求阶乘得和
回复
举报
分享到 淘江湖 新浪 QQ微博 QQ空间 开心 人人 豆瓣 网易微博 百度 鲜果 白社会 飞信
离线stevenjl
管理员
只看该作者 1 发表于: 2006-07-11
复制代码
  1. 阶乘程序：
  2. program jc;
  3. var
  4. m:string;
  6. function jiecheng(m:integer):string;
  7. var
  8. n,s:string;
  9. begin
  10. if m<>1 then
  11. begin
  12. n:=jiecheng(m-1);
  13. end
  14. else
  15. jiecheng:='1';
  16. exit;
  17. end;
  20. <高精度程序段>
  21. end;
  23. begin
  24. read(m)
  25. writeln(jiecheng(m));
  26. end.
  28. 高精度介绍：
  29. 所谓的高精度运算,是指参与运算的数(加数,减数,因子……）范围大大超出了标准数据类型（整型，实型）能表示的范围的运算。例如，求两个200位的数的和。这时，就要用到高精度算法了。在这里，我们先讨论高精度加法。高精度运算主要解决以下三个问题：
  31. 基本方法（如果你已经会了，那就看看优化后的方法）
  33. 1、加数、减数、运算结果的输入和存储
  34. 运算因子超出了整型、实型能表示的范围，肯定不能直接用一个数的形式来表示。在Pascal中，能表示多个数的数据类型有两种：数组和字符串。
  35. （1）数组：每个数组元素存储1位（在优化时，这里是一个重点！），有多少位就需要多少个数组元素；
  36. 用数组表示数的优点：每一位都是数的形式，可以直接加减；运算时非常方便
  37. 用数组表示数的缺点：数组不能直接输入；输入时每两位数之间必须有分隔符，不符合数值的输入习惯；
  39. （2）字符串：字符串的最大长度是255，可以表示255位。
  40. 用字符串表示数的优点：能直接输入输出，输入时，每两位数之间不必分隔符，符合数值的输入习惯；
  41. 用字符串表示数的缺点：字符串中的每一位是一个字符，不能直接进行运算，必须先将它转化为数值再进行运算；运算时非常不方便； （3）因此，综合以上所述，对上面两种数据结构取长补短：用字符串读入数据，用数组存储数据：
  42. var s1,s2:string;
  43. a,b,c:array [1..260] of integer;
  44. i,l,k1,k2:integer;
  45. begin
  46. write('input s1:');readln(s1);
  47. write('input s2:');readln(s2);
  48. {————读入两个数s1，s2，都是字符串类型}
  49. l:=length(s1);{求出s1的长度，也即s1的位数；有关字符串的知识。}
  50. k1:=260;
  51. for i:=l downto 1 do
  52. begin
  53. a[k1]:=ord(s1[i])-48;{将字符转成数值}
  54. k1:=k1-1;
  55. end;
  56. k1:=k1+1;
  57. {————以上将s1中的字符一位一位地转成数值并存在数组a中；低位在后（从第260位开始），高位在前（每存完一位，k1减1）}
  59. 对s2的转化过程和上面一模一样。
  61. 2、运算过程
  62. 在往下看之前，大家先列竖式计算35+86。
  63. 注意的问题：
  64. （1）运算顺序：两个数靠右对齐；从低位向高位运算；先计算低位再计算高位；
  65. （2）运算规则：同一位的两个数相加再加上从低位来的进位，成为该位的和；这个和去掉向高位的进位就成为该位的值；如上例：3+8+1=12，向前一位进1，本位的值是2；可借助MOD、DIV运算完成这一步；
  66. （3）最后一位的进位：如果完成两个数的相加后，进位位值不为0，则应添加一位；
  67. （4）如果两个加数位数不一样多，则按位数多的一个进行计算；
  68. if k1>k2 then k:=k1 else k:=k2;
  69. y:=0;
  70. for i:=260 downto k do
  71. begin
  72. x:=a[i]+b[i]+y;
  73. c[i]:=x mod 10;
  74. y:=x div 10;
  75. end;
  76. if y<>0 then begin k:=k-1;c[k]:=y; end;
  78. 3、结果的输出（这也是优化的一个重点）
  79. 按运算结果的实际位数输出
  80. for i:=k to 260 do write(c[i]);
  81. writeln;
  83. 4、例子：求两个数的加法
  84. program sum;
  85. var s,s1,s2:string;
  86. a,b,c:array [1..260] of integer;
  87. i,l,k1,k2:integer;
  88. begin
  89. write('input s1:');readln(s1);
  90. write('input s2:');readln(s2);
  91. l:=length(s1);
  92. k1:=260;
  93. for i:=l downto 1 do
  94. begin
  95. a[k1]:=ord(s1[i])-48;
  96. k1:=k1-1;
  97. end;
  98. k1:=k1+1;
  100. l:=length(s2);
  101. k2:=260;
  102. for i:=l downto 1 do
  103. begin
  104. b[k2]:=ord(s2[i])-48;
  105. k2:=k2-1;
  106. end;
  107. k2:=k2+1;
  109. if k1>k2 then k:=k2 else k:=k1;
  110. y:=0;
  111. for i:=260 downto k do
  112. begin
  113. x:=a[i]+b[i]+y;
  114. c[i]:=x mod 10;
  115. y:=x div 10;
  116. end;
  117. if y<>0 then begin k:=k-1;c[k]:=y;
  118. end;
  119. for i:=k to 260 do write(c[i]);
  120. writeln;
  121. end.
  125. 优化：
  127. 以上的方法的有明显的缺点：
  128. （1）浪费空间：一个整型变量（-32768~32767）只存放一位（0~9）；
  129. （2）浪费时间：一次加减只处理一位；
  131. 针对以上问题，我们做如下优化：一个数组元素存放四位数；（integer的最大范围是32767，5位的话可能导致出界）。具体方法：
  132. l:=length(s1);
  133. k1:=260;
  134. repeat {————有关字符串的知识}
  135. s:=copy(s1,l-3,4);
  136. val(s,a[k1],code);
  137. k1:=k1-1;
  138. s1:=copy(s1,1,l-4);
  139. l:=l-4;
  140. until l<=0;
  141. k1:=k1+1;
  142. 而因为这个改进，算法要相应改变：
  143. （1）运算时：不再逢十进位，而是逢万进位（mod 10000; div 10000);
  144. （2）输出时：最高位直接输出，其余各位，要判断是否足够4位，不足部分要补0；例如：1，23，2345这样三段的数，输出时，应该是100232345而不是1234567。
  146. 改进后的算法：
  147. program sum;
  148. var s1,s2:string;
  149. a,b,c:array [1..260] of integer;
  150. i,l,k1,k2,code:integer;
  153. begin
  154. write('input s1:');readln(s1);
  155. write('input s2:');readln(s2);
  156. l:=length(s1);
  157. k1:=260;
  158. repeat {————有关字符串的知识}
  159. s:=copy(s1,l-3,4);
  160. val(s,a[k1],code);
  161. k1:=k1-1;
  162. s1:=copy(s1,1,l-4);
  163. l:=l-4;
  164. until l<=0;
  165. k1:=k1+1;
  166. l:=length(s2);
  167. k2:=260;
  168. repeat
  169. s:=copy(s2,l-3,4);
  170. val(s,b[k2],code);
  171. k2:=k2-1;
  172. s2:=copy(s2,1,l-4);
  173. l:=l-4;
  174. until l<=0;
  175. k2:=k2+1;
  177. if k1<k2 then k:=k1 else k:=k2;
  178. y:=0;
  179. for i:=260 downto k do
  180. begin
  181. x:=a[i]+b[i]+y;
  182. c[i]:=x mod 10000;
  183. y:=x div 10000;
  184. end;
  185. if y<>0 then begin k:=k-1;c[k]:=y;end;
  187. write(c[k]);
  188. for i:=k+1 to 260 do
  189. begin
  190. ----if c[i]<1000 then write('0');
  191. ----if c[i]<100 then write('0');
  192. ----if c[i]<10 then write('0');
  193. ----write(c[i]);
  194. end;
  195. writeln;
  196. end.
Dream Walker...
回复
举报
离线johnson
OIFans复赛选手
只看该作者 2 发表于: 2006-08-17
var
  a       : array[1..50] of byte;  
  i,j,k,l,n : word;  
begin  
  a[1] := 1;  
  for i := 2 to 50 do a[i] := 0;
  l := 1;
  for i := 2 to 50 do begin
    k := 0;
    for j := 1 to l do begin
      k := a[j]*i+k;
      a[j] := k mod 10;
      k := k div 10;
    end;
    while k > 0 do begin
    l := l+1;
    a[l] := k mod 10;
    k := k div 10
    end;
  end;  
  write(i,'! = ');
  for k := l downto 1 do write(a[k]);  
  writeln;    
end.
回复
举报
离线wangvvs
OIFans入门选手
只看该作者 3 发表于: 2006-09-09
我有个问题：‘a[k1]:=ord(s1)-48;’
这个ord不是把一整个串的字符转成数字么？
还有‘-48’是用来干什么的？
回复
举报
离线stevenjl
管理员
只看该作者 4 发表于: 2006-09-09
a[k1]:=ord(s1[i])-48;{将字符转成数值}
抱歉，是论坛吃代码了……现在已经修正。
48是“0”的ASCII码
ord('0') = 48，同样的：
ord('1') = 49;
ord('2') = 50;
....
所以，ord('n') -48 = n;
Dream Walker...
回复
举报
发帖 回复
返回列表
快速回复
限100 字节
 
上一个 下一个