高精度运算1

1.高精度运算_加法

AYYZOJ p1443

COGS p37

 1 type
 2   arr=array[1..200]of integer;
 3  var
 4   a,b:arr;i,la,lb:integer; n:string;
 5 procedure add(a,b:arr;la,lb:integer);
 6   var i,x,lc:integer; c:arr;
 7   begin
 8         i:=1; x:=0;
 9         while (i<=la) or(i<=lb) do
10          begin x:=a[i]+b[i]+x;
11                c[i]:=x mod 10;
12                x:=x div 10 ;
13                i:=i+1;
14          end;
15          if x>0 then begin lc:=i; c[lc]:=x; end else lc:=i-1;
16          for i:=lc downto 1 do write(c[i]);
17          writeln;
18    end;
19  begin
20   readln(n);  la:=length(n);
21   for i:=1 to la do a[i]:=ord(n[la-i+1])-ord(‘0‘);
22   readln(n);  lb:=length(n);
23   for i:=1 to lb do b[i]:=ord(n[lb-i+1])-ord(‘0‘);
24   add(a,b,la,lb);
25  end.

add

2.高精度运算_减法

AYYZOJ p1444

COGS p38

 1 type
 2   arr=array[1..200]of integer;
 3  var
 4   a,b:arr;i,la,lb:integer; n,n1,n2:string;
 5 procedure sub(a,b:arr;la,lb:integer);
 6   var i,x,lc:integer; c:arr;
 7   begin
 8     i:=1;
 9     x:=0;
10     fillchar(c,sizeof(c),0);
11     while (i<=la) or(i<=lb) do
12       begin
13         x := a[i] - b[i] + 10 + x; {不考虑大小问题,先往高位借10}
14         c[i] := x mod 10 ; {保存第i 位的值}
15         x := x div 10 - 1; {将高位借掉的1减去}
16         i := i + 1
17       end;
18     lc:=i;
19     while (c[lc]=0) and (lc>1) do dec(lc); {最高位的0 不输出}
20     for i:=lc downto 1 do write(c[i]);
21     writeln
22   end;
23  begin
24   readln(n1);
25   readln(n2); {处理被减数和减数}
26   la:=length(n1); lb:=length(n2);
27   if (la<lb) or (la=lb) and (n1<n2) then
28     begin
29       n:=n1;n1:=n2;n2:=n;
30       write(‘-‘) {n1<n2,结果为负数}
31     end;
32   la:=length(n1); lb:=length(n2);
33   for i:=1 to la do a[la-i+1]:=ord(n1[i])-ord(‘0‘);
34   for i:=1 to lb do b[lb-i+1]:=ord(n2[i])-ord(‘0‘);
35   sub(a,b,la,lb);
36  end.

sub

3.高精度运算-数列求和

AYYZOJ p1448

描述 Description  
  费波那契数列的前两项分别为1,1。以后每项为前两项之和。
输入n,求费波那契数列前n项的和(1<=n<=5000)。
输入:仅一个数,n
输出:费波那契数列前n项之和。
Sample Input
3
Sample Output
4
-------------------------------
对于样例的解释
费波那契数列前三项是1,1,2,和为4。

输入文件:fbnq.in
输出文件:fbnq.out

时间限制 Time Limitation  
  各个测试点1s

 1 program fbnq;
 2 type
 3   arr=array[1..7010] of integer;
 4 var
 5   a,b,c:arr;
 6   l,i,n:integer;
 7 procedure plus(a1,b1:arr;var x:arr);
 8   var i,k:integer;
 9   begin
10     k:=0;
11     for i:=1 to l do
12       begin
13         a1[i]:=a1[i]+b1[i]+k;
14         k:=a1[i] div 10;
15         a1[i]:=a1[i] mod 10;
16       end;
17     if k>0 then begin inc(l);a1[l]:=k;end;
18     x:=a1;
19   end;
20 begin
21   readln(n);
22   fillchar(a,sizeof(a),0);
23   fillchar(b,sizeof(b),0);
24   fillchar(c,sizeof(c),0);
25   if n=1 then begin writeln(1);halt;end;
26   if n=2 then begin writeln(2);halt;end;
27   a[1]:=1;
28   b[1]:=1;
29   l:=1;
30   for i:=3 to n+2 do
31     begin
32       plus(a,b,c);
33       a:=b;
34       b:=c;
35     end;
36   if c[1]-1<0 then
37     begin
38       c[1]:=9;
39       dec(c[2]);
40       for i:=2 to l do
41         begin
42           if (c[i]<0) then begin c[i+1]:=c[i+1]-1;c[i]:=c[i]+10; end
43             else break;
44         end;
45     end
46   else dec(c[1]);
47   while c[l]=0 do dec(l);
48   for i:=l downto 1 do write(c[i]);writeln;
49 end.

fbnq——过程

 1 program fbnq;
 2 type
 3   arr=array[1..7010] of integer;
 4 var
 5   a,b,c:arr;
 6   l,i,n:integer;
 7 function plus(a,b:arr):arr;
 8   var i,c:integer;
 9   begin
10     c:=0;
11     for i:=1 to l do
12       begin
13         a[i]:=a[i]+b[i]+c;
14         c:=a[i] div 10;
15         a[i]:=a[i] mod 10;
16       end;
17     if c>0 then begin inc(l);a[l]:=c;end;
18     plus:=a;
19   end;
20 begin
21   readln(n);
22   fillchar(a,sizeof(a),0);
23   fillchar(b,sizeof(b),0);
24   fillchar(c,sizeof(c),0);
25   if n=1 then begin writeln(1);halt;end;
26   if n=2 then begin writeln(2);halt;end;
27   a[1]:=1;
28   b[1]:=1;
29   l:=1;
30   for i:=3 to n+2 do
31     begin
32       c:=plus(a,b);
33       a:=b;
34       b:=c;
35     end;
36   if c[1]-1<0 then
37     begin
38       c[1]:=9;
39       dec(c[2]);
40       for i:=2 to l do
41         begin
42           if (c[i]<0) then begin c[i+1]:=c[i+1]-1;c[i]:=c[i]+10; end
43             else break;
44         end;
45     end
46   else dec(c[1]);
47   while c[l]=0 do dec(l);
48   for i:=l downto 1 do write(c[i]);writeln;
49 end.

fbnq——函数

4.NOIP1999_PT2_回文数

AYYZOJ p1008

COGS p40

 1 program huiwen;
 2 type arr=array[1..50] of byte;
 3 var
 4   a:arr;
 5   n,step,l,i,j:integer;
 6   m:string[20];
 7 procedure add(var a:arr);
 8   var c,i:integer;
 9       b:arr;
10   begin
11     b:=a;
12     c:=0;
13     for i:=1 to l do
14       begin
15         a[i]:=a[i]+b[l+1-i]+c;
16         c:=a[i] div n;
17         a[i]:=a[i] mod n;
18       end;
19     if c<>0 then begin inc(l);a[l]:=c; end;
20   end;
21 procedure try(var a:arr);
22   var i:integer;
23   begin
24     for i:= 1 to l div 2 do
25       if a[i]<>a[l+1-i] then exit;
26     writeln(‘STEP=‘,step);
27     halt;
28   end;
29 begin
30   readln(n);
31   readln(m);
32   l:=length(m);
33   for i:=1 to l do
34     if m[i] in [‘0‘..‘9‘] then a[l-i+1]:=ord(m[i])-ord(‘0‘)
35       else case m[i] of
36              ‘A‘,‘a‘:a[l-i+1]:=10;
37              ‘B‘,‘b‘:a[l-i+1]:=11;
38              ‘C‘,‘c‘:a[l-i+1]:=12;
39              ‘D‘,‘d‘:a[l-i+1]:=13;
40              ‘E‘,‘e‘:a[l-i+1]:=14;
41              ‘F‘,‘f‘:a[l-i+1]:=15;
42            end;
43   step:=0;
44   try(a);
45   while step<=30 do
46     begin
47       add(a);
48       inc(step);
49       try(a);
50     end;
51   writeln(‘Impossible!‘);
52 end.

huiwen

时间: 12-05

高精度运算1的相关文章

hdu4927 Series 1(组合+公式 Java大数高精度运算)

题目链接: Series 1 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 423    Accepted Submission(s): 146 Problem Description Let A be an integral series {A1, A2, . . . , An}. The zero-order series o

高精度运算

在开发中高精度运算使用并非非常频繁,float和double的精度实际上能够满足绝大多数需要,且高精度运算效率比常规的运算要慢一点,但使用高精度运算往往是为了使用其中便捷的API.官方提供的高精度运算的类主要两个 BigInteger:当数值范围超过long时使用 BigDecimal:几乎涵盖BigInteger功能,还可以保留小数点任意位数,理论上精度无穷大,以下主要说明此类 注:两者API很相似 加减乘除 BigDecimal aaa = new BigDecimal(20); BigDe

高精度运算专题3-乘法运算(The multiplication operation)

这个专题呢,我就来讲讲高精度的乘法,下面是三个计算乘法的函数,第一个函数是char类型的,要对字符串进行数字转换,而第二个是两个int类型的数组,不用转换成数字,第三个则更为优化,用a数组-b数组放回数组a里面 函数1思路:要先把char类型的转换成int类型的数,直接每个数-‘0’就可以实现把char类型的转换成int类型的了. ①记录数组a.数组b的长度,放到第一位 ②每个位相乘,用一个数来记录进位(初值为0),每个位相乘,加上进位,存入c数组的相对应的位置,每次进位要重新赋值 ③最后记得要

大数高精度运算(模板)

前言:高精度运算.是指參与运算的数(加数.减数,因子--)范围大大超出了标准数据类型(整型,实型)能表示的范围的运算. 模板:包含大数加减乘除.大数与int数的乘法,模板能够不断扩充. 代码: /* 所有亲測可用,可是不能用于负数的运算,仅仅能对正数进行大数运算 */ const int ten[4]= {1,10,100,1000}; const int maxl = 300; struct BigNumber { int d[maxl]; char s[maxl]; BigNumber(co

整数高精度运算——加法

高精度运算是信息学的一种重要算法.这种算法使用多个存储单位进行计算,因此它的计算范围超过一般使用一个存储单位的算法.也是一些信息学竞赛的常考题目. 高精度运算主要有以下几个步骤: 1.读取字符串,转换成数字倒序存储到整数数组中: 2.运算,注意进位和借位: 3.倒序输出整数数组,加法注意最高位进位,减法注意高位中的无用的0不要输出: 高精度加法代码: #include<stdio.h>#include<string.h>char s[1000];       //数组比较大时,应作

Digital Root - SGU 118(高精度运算)

题目大意:有K组测试数据,然后每组有N个正整数,A1,A2,A3.....An,求出 A1 + A1*A2 + A1*A2*A3 + .......A1*A2*...An 的数根. 分析:有个对9取余的定理是可以直接求树根的,不过拿来玩大数运算也不错.ps.每位可以保存9位数,保存10位数会溢出. 高精度代码如下: ===========================================================================================

高精度运算 Java算法

问题描述  输入两个整数a和b,输出这两个整数的和.a和b都不超过100位. 算法描述  由于a和b都比较大,所以不能直接使用语言中的标准数据类型来存储.对于这种问题,一般使用数组来处理.  定义一个数组A,A[0]用于存储a的个位,A[1]用于存储a的十位,依此类推.同样可以用一个数组B来存储b.  计算c = a + b的时候,首先将A[0]与B[0]相加,如果有进位产生,则把进位(即和的十位数)存入r,把和的个位数存入C[0],即C[0]等于(A[0]+B[0])%10.然后计算A[1]与

大数问题(高精度运算)

一.基本概念 在某些情况下,我们必须处理相当大的一个整数,运用类型int.long int.long long int 类型均无法对其进行存储.要解决这样的问题,我们就需要自己编写相应的处理程序.在处理大数的时候,可以将其作为字符串读入,然后一个数字一个数字的存储到数组中,然后编写相应运算操作的处理函数即可解决大数问题. 也就是说在对大数进行运算之前,要先解决对大数进行存储的问题.而这里一一般情况为例,对输入和输入函数进行定义. 输入处理: 输入字符串: c[0] c[1] c[2] c[3]

高精度运算-阶乘累积求和

# include <stdio.h> # include <math.h> # define N 66 int main(){ int s[N] = {0}, a[N] = {0};// s累加和,a累积求阶乘 int i,j,k,n,digit=1; //digit代表的是数字的位数 scanf("%d",&n); a[0]=1; s[0]=1; if(n==1)// 如果是1,阶乘和就是1,直接输出 printf("%d",s[