高精度整数加法、减法与乘法

2024-06-07 16:18

本文主要是介绍高精度整数加法、减法与乘法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


更新:2018/8/26
内容:采用int数组模拟高进制位的加法与乘法。

1 高精度加法与乘法

(手懒,直接上代码哈……)

#include<stdio.h>
#include<string.h>
#include<stdlib.h>#define MAX_V 100const int hexa = 10000;
#define HEXA_L "04"typedef struct{int v[MAX_V];//倒序装入int len;//长度
}int_x;void itox(int n, int_x *x){if(!x){printf("x is NULL!\n");exit(0);}x->len = 0;x->v[x->len] = 0;//初始化为0while(n > 0){x->v[x->len ++] = n % hexa;n /= hexa;}
}void print_x(int_x *x){int i;if(!x){printf("x is NULL!\n");exit(0);}i = x->len - 1;printf("%d", x->v[i --]);while(i >= 0){printf("%"HEXA_L"d", x->v[i --]);}printf("\n");
}void add(int_x *a, int_x *b, int_x *c){//c = a + bint flag = 0, i, temp;if(!a || !b || !c){printf("a/b/c is NULL!\n");exit(0);}for(i = 0; i < a->len || i < b->len || flag; i ++){temp = 0;if(i < a->len){temp += a->v[i];}if(i < b->len){temp += b->v[i];}c->v[i] = temp % hexa + flag;flag = temp / hexa;}c->len = i;
}void multi(int_x *a, int_x *b, int_x *c){//c = a * bint flag = 0, i, j, temp;if(!a || !b || !c){printf("a/b/c is NULL!\n");exit(0);}int_x x = {{0x0}, 0x0}, y = {{0x0}, 0x0};;for(i = 0; i < a->len; i ++){flag = temp = 0;memset(&y, 0x0, sizeof(int_x));y.len = i;for(j = 0; j < b->len || flag; j ++){if(j < b->len){temp = a->v[i] * b->v[j];}else{temp = 0;}y.v[y.len ++] = temp % hexa + flag;flag = temp / hexa;}add(&x, &y, &x);//print_x(&x);}c->len = x.len;for(i = 0; i < x.len; i ++){c->v[i] = x.v[i];}
}int int_x_compare(int_x *a, int_x *b){//0 equal, 1 bigger, -1 smallerif(!a || !b){printf("a/b is NULL!\n");exit(0);}if(a->len > b->len){return 1;}if(a->len < b->len){return -1;}int i;for(i = a->len - 1; i >= 0; i --){if(a->v[i] > b->v[i]){return 1;}else if(a->v[i] < b->v[i]){return -1;}}return 0;
}int main(int argc, char *argv[]){int a = 11;int_x a_x;int_x b_x = {{0x0}, 0x0};itox(a, &a_x);print_x(&a_x);int i;for(i = 0; i < a; i ++){add(&a_x, &b_x, &b_x);}print_x(&b_x);a_x.len = 0;itox(a, &a_x);for(i = 0; i < 4; i ++){multi(&a_x, &a_x, &a_x);}print_x(&a_x);printf("%d\n", int_x_compare(&a_x, &a_x));return 0;
}

1 大数加法

#include<stdio.h>
#include<string.h>int judge(char *num){char *p = num;int c = 0;while(*(p + c)){if(*(p + c) < '0' || *(p + c) > '9'){return -1;}c ++;}return c;
}void reverse(char *p){int i;int l1 = strlen(p);for(i = 0; i < l1 / 2; i ++){char c = p[i];p[i] = p[l1 - 1 - i];p[l1 - 1 - i] = c;}
}void add(char *num1, char *num2, char *sum)
{int i;reverse(num1);reverse(num2);char *p1 = num1;char *p2 = num2;int later = 0;char *p3 = sum;while(*p1 || *p2){int t = later;if(*p1){t += (*p1 - '0');p1 ++;}if(*p2){t += (*p2 - '0');p2 ++;}later = t / 10;*p3 = (t % 10) + '0';p3 ++;}if(later > 0){*p3 = (later + '0');p3 ++;}*p3 = '\0';reverse(sum);
}
int main(int argc, char *argv[]){char num1[10000];char num2[10000];scanf("%s", num1);scanf("%s", num2);printf("%s + %s = ?\n", num1, num2);int num1_len = judge(num1);if(num1_len < 0){printf("num1 error!\n");return -1;}int num2_len = judge(num2);if(num2_len < 0){printf("num2 error!\n");return -1;}char sum[10000];add(num1, num2, sum);printf("%s\n", sum);return 0;
}

2 大数减法

#include<stdio.h>
#include<string.h>int judge(char *num){char *p = num;int c = 0;while(*(p + c)){if(*(p + c) < '0' || *(p + c) > '9'){return -1;}c ++;}return c;
}void reverse(char *p){int i;int l1 = strlen(p);for(i = 0; i < l1 / 2; i ++){char c = p[i];p[i] = p[l1 - 1 - i];p[l1 - 1 - i] = c;}
}void minus(char *num1, char *num2, char *res)
{int i;reverse(num1);reverse(num2);int num1_len = strlen(num1);int num2_len = strlen(num2);if(num1_len < num2_len){for(i = num1_len; i < num2_len; i ++){num1[i] = '0';}}else{for(i = num2_len; i < num1_len; i ++){num2[i] = '0';}}char *big = num1;char *small = num2;for(i = (num1_len > num2_len ? num1_len : num2_len) - 1; i >= 0; i ++){if(num1[i] < num2[i]){big = num2;small = num1;break;}else if(num1[i] > num2[i]){big = num1;small = num2;break;}}int token = 0;int a, b;for(i = 0; i < (num1_len > num2_len ? num1_len : num2_len); i ++){a = big[i] - '0' - token;token = 0;b = small[i] - '0';if(a < b){token = 1;a += 10;}res[i] = a - b + '0';}reverse(res);
}
int main(int argc, char *argv[]){char num1[10000];char num2[10000];memset(num1, 0x0, sizeof(num1));memset(num2, 0x0, sizeof(num2));scanf("%s", num1);scanf("%s", num2);printf("|%s - %s| = ?\n", num1, num2);int num1_len = judge(num1);if(num1_len < 0){printf("num1 error!\n");return -1;}int num2_len = judge(num2);if(num2_len < 0){printf("num2 error!\n");return -1;}char res[10000];minus(num1, num2, res);char *p = res;while(*p == '0'){p ++;}if(!*p){printf("0\n");}else{printf("%s\n", p);}return 0;
}

3 大数乘法

#include<stdio.h>
#include<string.h>#define MAX_LEN 1000000int judge(char *num){char *p = num;int c = 0;while(*(p + c)){if(*(p + c) < '0' || *(p + c) > '9'){return -1;}c ++;}return c;
}void reverse(char *p){int i;int l1 = strlen(p);for(i = 0; i < l1 / 2; i ++){char c = p[i];p[i] = p[l1 - 1 - i];p[l1 - 1 - i] = c;}
}void multi(char *num, char c, int I, char *res){int a;int i, ii;int later = 0;for(ii = 0; ii < I; ii ++){res[ii] = '0';}for(i = 0; i < strlen(num); i ++){a = (c - '0') * (num[i] - '0') + later;res[ii ++] = a % 10 + '0';later = a / 10;}while(later){res[ii ++] = later % 10 + '0';later /= 10;}res[ii] = '\0';
}void add(char *num1, char *sum){char *p1 = num1;int later = 0;char *p3 = sum;while(*p1 || *p3){int t = later;if(*p1){t += (*p1 - '0');p1 ++;}if(*p3){t += (*p3 - '0');}later = t / 10;*p3 = (t % 10) + '0';p3 ++;}if(later > 0){*p3 = (later + '0');p3 ++;}*p3 = '\0';
}char t[MAX_LEN];
void compute(char *num1, char *num2, char *sum)
{int i;reverse(num1);reverse(num2);for(i = 0; i < strlen(num2); i ++){memset(t, 0x0, sizeof(t));multi(num1, num2[i], i, t);add(t, sum);}reverse(sum);
}char num1[MAX_LEN / 2 - 1];
char num2[MAX_LEN / 2 - 1];
char res[MAX_LEN];
int main(int argc, char *argv[]){int i;scanf("%s", num1);scanf("%s", num2);printf("%s * %s = ?\n", num1, num2);int num1_len = judge(num1);if(num1_len < 0){printf("num1 error!\n");return -1;}int num2_len = judge(num2);if(num2_len < 0){printf("num2 error!\n");return -1;}memset(res, 0x0, sizeof(res));compute(num1, num2, res);int is = 1;for(i = 0; i < strlen(res); i ++){if(res[i] != '0' && is){is = 0;}if(!is){printf("%c", res[i]);}}if(is){printf("0");}printf("\n");return 0;
}

备注:写出来做个备份。

这篇关于高精度整数加法、减法与乘法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1039667

相关文章

PTA求一批整数中出现最多的个位数字

作者 徐镜春 单位 浙江大学 给定一批整数,分析每个整数的每一位数字,求出现次数最多的个位数字。例如给定3个整数1234、2345、3456,其中出现最多次数的数字是3和4,均出现了3次。 输入格式: 输入在第1行中给出正整数N(≤1000),在第二行中给出N个不超过整型范围的非负整数,数字间以空格分隔。 输出格式: 在一行中按格式“M: n1 n2 ...”输出,其中M是最大次数,n

uva 10069 DP + 大数加法

代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>#include <cl

整数Hash散列总结

方法:    step1  :线性探测  step2 散列   当 h(k)位置已经存储有元素的时候,依次探查(h(k)+i) mod S, i=1,2,3…,直到找到空的存储单元为止。其中,S为 数组长度。 HDU 1496   a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 。 x在 [-100,100] 解的个数  const int MaxN = 3000

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

单精度浮点数按存储格式转为整数的程序

///#include<cstdio>//-----------------union int_char{unsigned char ch[4];float i;};void out_put(union int_char x)//x86是小端对其模式,即最数据的最低位存储在地址的最低位上。{printf("单精度浮点数值为:%f\n",x.i,x.i);printf("存储位置从左到右

高精度计算(代码加解析,洛谷p1601,p1303)除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时,正常加法不能得到精确解。在小学,我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位: c[i] = a[i] + b[i];if(c[i] >=

高精度打表-Factoring Large Numbers

求斐波那契数,不打表的话会超时,打表的话普通的高精度开不出来那么大的数组,不如一个int存8位,特殊处理一下,具体看代码 #include<stdio.h>#include<string.h>#define MAX_SIZE 5005#define LEN 150#define to 100000000/*一个int存8位*/int num[MAX_SIZE][LEN];void

高精度计算----减法运算(浮点型)

基于上一贴,修改减法运算适合于高精度浮点型计算。 因为减法比加法难度大一点,考虑的地方也要多一些,可能代码有欠缺,欢迎指出。 运算说明: 1、相减函数依旧没改变,包括上一贴的判断被减数与减数的大小函数也没变。 2、增加两个函数,取小数位数函数和结果处理(回归小数点)函数 3、与加法浮点高精度运算相比,这里改变较多的是结果处理函数,加法加完后,位数不减反增,而且最多增一位。减法会消失掉好多

高精度计算----减法运算

处理大数减法运算: 1、首先要判断被减数与减数哪个更大,再相应的带入减法函数去处理。具体的比较可以使用字符串的相关知识去比较。 2、相减要先对齐数组,依照减数的长度,执行相应的减法运算次数。 3、不需要借位相减的话,直接减去;需要的话,向前借一位,若前一位是0,则再前借(此时前一位的0变为10)。 测试程序效果如下:   以下代码包括相减函数,比较被减数减数函数,若有错误,请指出:

高精度加法,乘法,阶乘

#include <iostream>#include <map>#include <string>#include <algorithm>using namespace std;const int Max = 50000;string str1,str2;/***********乘法***********/void chenfa(){cin >> str1>>str2;int a