C++使用string的大数取模运算（5）

本次项目目标：使用C++完成对于大数的相关运算，具体有加减乘除取模。

项目要点

1.大数指的是远超long long int的数据

2.将大数用矩阵进行存储，并通过矩阵实现运算

3.本人采用字符串进行存储，应注意char的特点

比如：char a=161；

cout<<(int)a;

此时会输出-95，而不是161，char类型首个比特位是作为正负号的

取模运算其实和取余差不多，主要是取模在负数方面与取余不同

需要用到之前博客提到的减法运算minus

核心思想：

先来看自然数的取模运算

与取余相同，与除法思路相同

比如861mod21=861%21

先用86去减21 知道数值小于21时停止 也就是2

再添加上下一位，就变成了21

如果这个数大于等于21，则再用这个数减去它

21-21=0，当已经取出最后一位，而且这个数字小于21时停止

即得出861%21=0

接下来来看负整数的情况

假设有一个正整数k,a，(-k) mod a+k mod a=0 mod a

(-k) mod a=0 mod a - k mod a

因为k mod a<a,(-k) mod a<a

所以(-k) mod a=a - k mod a

即一个负整数的模a，就为a-其绝对值的模a

运行截图及代码如下：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define n 10
string dezero(string a)//用来去掉正数前面的0，也就是说可以输入000001类似这样的数字
{
 long int i;
 for(i=0;i<a.length();i++)
 {
 if(a.at(i)>48) break;
 }
 if(i==a.length()) return "0";
 a.erase(0,i);
 return a;
}
int judge(string a,string b)//判断两个正数的大小
{
 if(a.length()>b.length()) return 1;
 if(a.length()<b.length()) return -1;
 long int i;
 for(i=0;i<a.length();i++)
 {
 if(a.at(i)>b.at(i)) return 1;
 if(a.at(i)<b.at(i)) return -1;
 }
 return 0;
}
string minus(string a,string b)//自然数减法（在之前博客中写到过，这里直接挪过来调用了）
{
 a=dezero(a);
 b=dezero(b);
 long int i,j=0;
 string c="0";
 string c1,c2;
 string d="-";
 if(judge(a,b)==0) return c;
 if(judge(a,b)==1)
 {
 c1=a;
 c2=b;
 }
 if(judge(a,b)==-1)
 {
 c1=b;
 c2=a;
 j=-1;
 }
 reverse(c1.begin(),c1.end());
 reverse(c2.begin(),c2.end());
 for(i=0;i<c2.length();i++)
 {
 if(c2.at(i)>=48&&c2.at(i)<=57) c2.at(i)-=48;
 if(c2.at(i)>=97&&c2.at(i)<=122) c2.at(i)-=87;
 }
 for(i=0;i<c1.length();i++)
 {
 if(c1.at(i)>=48&&c1.at(i)<=57) c1.at(i)-=48;
 if(c1.at(i)>=97&&c1.at(i)<=122) c1.at(i)-=87;
 }
 for(i=0;i<c2.length();i++)
 {
 c1.at(i)=c1.at(i)-c2.at(i);
 }
 for(i=0;i<c1.length()-1;i++)
 {
 if(c1.at(i)<0)
 {
 c1.at(i)+=n;
 c1.at(i+1)--;
 }
 }
 for(i=c1.length()-1;i>=0;i--)
 {
 if(c1.at(i)>0) break;
 }
 c1.erase(i+1,c1.length());
 for(i=0;i<c1.length();i++)
 {
 if(c1.at(i)>=10) c1.at(i)+=87;
 if(c1.at(i)<10) c1.at(i)+=48;
 }
 reverse(c1.begin(),c1.end());
 if(j==-1) c1.insert(0,d);
 return c1;
}
string mod(string a,string b)//取模运算
{
 long int i,j=0;
 string c1,c2,c3,d;
 if(a.at(0)=='-') j=1;
 if(judge(a,b)==0) return "0";
 if(judge(a,b)==-1)
 {
 return a;
 }
 c1=dezero(a);
 c2=dezero(b);
 d="";
 for(i=0;i<c1.length();i++)
 {
 d=d+c1.at(i);
 while(judge(d,b)>=0)
 {
 d=minus(d,b);
 d=dezero(d);
 }
 }
 if(j==1) d=minus(b,d);
 return d;
}
int main()
{
 string a,b;
 while(cout<<"input:"&&cin>>a>>b)
 {
 cout<<"output:"<<mod(a,b)<<endl;
 }
 return 0;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • C++自定义API函数实现大数相乘算法

    前言: 之所以取题目的前部分为自定义API函数(不断更新中),是因为笔者想形成一套算法良好.接口清晰.方便编写程序的算法之意,也是为了日后更好调用算法,遇到相似的问题直接调用即可,以及方便大家使用,开发出更高效率的程序.其中的效率不敢说最好,还希望大家互相交流,共同进步!下面进入正题. 普通的乘法计算用int.long.double都可以解决,但有时候需要处理的数字过大,从而产生溢出,以下是实现任意长度的正整数A*B的算法,即大数相乘,这个算法比较简单易懂,思路如下: 1.在主函数用char型数

  • C++实现大数相乘算法

    C++实现大数相乘算法

    本文实例为大家分享了C++实现大数相乘的具体代码,供大家参考,具体内容如下 首先说一下乘法计算的算法:同样是模拟人工计算时的方法. 从低位向高位乘,在竖式计算中,我们是将乘数第一位与被乘数的每一位相乘,记录结果之后,用第二位相乘,记录结果并且左移一位,以此类推,直到计算完最后一位,再将各项结果相加,得出最后结果. 计算的过程基本上和小学生列竖式做乘法相同.为编程方便,并不急于处理进位,而将进位问题留待最后统一处理. 我们以125*53为例来说明计算过程: 1.先算125*3,3*5得到15个1,

  • 使用VC++实现打印乘法口诀表

    关于乘法口诀表,这里就不多废话了,大家都明白,下面说下用vc++实现的思路代码: 乘法口诀表.cpp 复制代码 代码如下: #include<stdio.h> int main () {  int i,j;    for(i=1;i<=9;i++)    {   for(j=1;j<=i;j++)           printf("%d ¡Á %d =%2d   ",j,i,i*j);        putchar('   \n');    }    getc

  • C++实现大整数乘法

    算法竞赛入门经典 这本书并没有对大数乘法实现,所以自己补充了一下,乘法的实现很简单,就是再其数据结构基础上把每宽为8位的十进制数看成多项式的系数,vector的下标看成多项式的指数,然后再对应相乘相加就可以了,注意系数超过8位 将超八位的补分进位. 我这里是笛卡尔相乘.一般来说是够用的. 但其实多项式乘法算法还有很多更高效的. #include <iostream> #include <vector> #include <cstring> #include <cs

  • C++实现大整数乘法（字符串乘法）

    本文实例为大家分享了C++实现大整数乘法的具体代码,供大家参考,具体内容如下 #include<iostream> #include<algorithm> #include<string> using namespace std; string add(string a,string b) { if(a.length()==0) return b; if(b.length()==0) return a; a.length()<b.length()?a.swap(b

  • C++中实现矩阵的加法和乘法实例

    C++中实现矩阵的加法和乘法实例

    C++中实现矩阵的加法和乘法实例 实现效果图: 实例代码: #include<iostream> using namespace std; class Matrix { int row;//矩阵的行 int col;//矩阵的列 int **a;//保存二维数组的元素 public: Matrix();//默认构造函数 Matrix(int r, int c); Matrix(const Matrix &is);//拷贝构造函数 void Madd(const Matrix &

  • C++实现大数乘法算法代码

    C++实现大数乘法算法代码 复制代码 代码如下: //大数乘法算法 #include<iostream> #include<string> #include<cstring> using namespace std; int main() {     string num1,num2;     cin >> num1 >> num2;     //cout << num1.size() << " " &

  • C++实现大数相乘的算法

    由于数字无法用一个整形变量存储,很自然的想到用字符串来表示一串数字.然后按照乘法的运算规则,用一个乘数的每一位乘以另一个乘数,然后将所有中间结果按正确位置相加得到最终结果.可以分析得出如果乘数为A和B,A的位数为m,B的位数为n,则乘积结果为m+n-1位(最高位无进位)或m+n位(最高位有进位).因此可以分配一个m+n的辅存来存储最终结果.为了节约空间,所有的中间结果直接在m+n的辅存上进行累加. C++实现大数相乘代码如下: #include<iostream> #include<st

  • C++稀疏矩阵的各种基本运算并实现加法乘法

    C++稀疏矩阵的各种基本运算并实现加法乘法

    代码: #include <iostream> #include<malloc.h> #include<cstdio> using namespace std; #define M 4 #define N 4 #define MaxSize 100 typedef int ElemType; typedef struct { int r; int c; ElemType d;///元素值 } TupNode; ///三元组定义 typedef struct { int

  • C++使用string的大数取模运算（5）

    C++使用string的大数取模运算（5）

    本次项目目标:使用C++完成对于大数的相关运算,具体有加减乘除取模. 项目要点 1.大数指的是远超long long int的数据 2.将大数用矩阵进行存储,并通过矩阵实现运算 3.本人采用字符串进行存储,应注意char的特点 比如:char a=161: cout<<(int)a; 此时会输出-95,而不是161,char类型首个比特位是作为正负号的 取模运算其实和取余差不多,主要是取模在负数方面与取余不同 需要用到之前博客提到的减法运算minus 核心思想: 先来看自然数的取模运算 与取余

  • Java%(取模运算)全面讲解

    目录 Java%(取模运算) Java的取模运算 C++的取模运算 注意事项:奇偶判断 编程语言中的%取模运算的本质探究 公式:a % b = a - a / b * b(对于a为正数) 公式:a - (int)a / b * b Java%(取模运算) Java的取模运算 1.实现算法 public static double ramainder(double dividend, double dividor) {         return dividend - dividend / di

  • C++快速幂与大数取模算法示例

    一.快速幂 其实就是求(a^b)% p ,(其中a,b,p都比较大在int范围内)这类问题. 首先要知道取余的公式: (a*b)%p=(a%p*b%p)%p . 那么幂不就是乘机的累积吗,由此给出代码: int fast(int a,int b,int p) { long long a1=a,t=1; while(b>0) { if(b&1) /如果幂b是奇数多乘一次,因为后边会除2变偶数,(7/2=3) t=(t%p)*(a1%p)%p; a1=(a1%p)*(a1%p)%p; b/=2;

  • Python中的取模运算方法

    所谓取模运算,就是计算两个数相除之后的余数,符号是%.如a % b就是计算a除以b的余数.用数学语言来描述,就是如果存在整数n和m,其中0 <= m < b,使得a = n * b + m,那么a % b = a - n * b = m. 取模运算的两个操作数都必须是整数,可以是负整数,但是b不可以是0,因为被除数不能为0嘛. 当a和b中存在负整数时,首先计算|a|%|b|=c,然后a%b的符号与b一致.也就是说,如果b>0,则a%b=c:如果b<0,则a%b=-c 比如: 好了,

  • python 负数取模运算实例

    举例: 340%60 = 40 ,怎么来的? 340 - 60*5 = 40 340 - (比340小的那个可以被60整除的正整数) =. 40 如果是负数: -340%60 = -340 - (比-340小的那个可以被60整除的负整数) = -340 - (-360) = 20 如图: 也可以换个思路想, -340%60 =(比340大的那个可以被60整除的正整数) - 340 = 360 - 340 = 20 举例: 1%3 = 1 -1%3 = 2 补充知识:python中对负数求余的计算

  • C++使用string的大数快速模幂运算（6）

    本次项目目标:使用C++完成对于大数的相关运算,具体有加减乘除取模. 项目要点 1.大数指的是远超long long int的数据 2.将大数用矩阵进行存储,并通过矩阵实现运算 3.本人采用字符串进行存储,应注意char的特点 比如:char a=161: cout<<(int)a; 此时会输出-95,而不是161,char类型首个比特位是作为正负号的 模幂快速算法 a,m为正整数,将m表示为二进制形式 则 可得 举个例子 代码中有之前的减法 乘法 取模 除法运算 可得以下快速指数算法以及运行

  • C语言中四种取整方式,取余/取模运算以及负数取模问题详解

    C语言中四种取整方式,取余/取模运算以及负数取模问题详解

    目录 零向取整.负无穷向取整.正无穷向取整.四舍五入取整 总结 零向取整.负无穷向取整.正无穷向取整.四舍五入取整 如果将一个浮点数赋值给整形,只会保存整数位: 这种取整方式为零向取整,C语言默认采用的是这种方式 C语言中也有对应的零向取整函数: 同理还有一种函数是负无穷大取整: 它的取整方案是向负无穷大取整: 有地板取整,当然也有正无穷大取整的函数: 它的取整方式是向正无穷大取整: 最后,还有四舍五入取整的函数: 取模/取余 取模概念: 如果a和d是两个自然数,d非零,可以证明存在两个唯一的整

  • 解析取模运算% 和位与运算& 之间的关系详解

    复制代码 代码如下: #include <stdio.h> int main (void){    unsigned int MAX = 32;    unsigned int index = 31; index = 31;    index = (index + 1) % MAX;  // 这个容易理解    printf ("index = %d\n", index); index = 31;    index = (index + 1) & (MAX - 1)

  • C++使用string的大数除法运算（4）

    C++使用string的大数除法运算（4）

    本次项目目标:使用C++完成对于大数的除法运算,供大家参考,具体内容如下 项目要点 1.大数指的是远超long long int的数据 2.将大数用矩阵进行存储,并通过矩阵实现运算 3.本人采用字符串进行存储,应注意char的特点 比如:char a=161: cout<<(int)a; 此时会输出-95,而不是161,char类型首个比特位是作为正负号的 除法,除法主要采用的还是笔算的思想,需要用到之前博客当中的减法函数minus 核心思想:比如861/21 先用86去减21 知道数值小于2

  • java 取模与取余的区别说明

    取模与取余的区别 对于整型数a,b来说,取模运算或者求余运算的方法都是: 1.求 整数商: c = a/b; 2.计算模或者余数: r = a - c * b 求模运算和求余运算在第一步不同: 取余运算在取c的值时,向0 方向舍入(fix()函数):而取模运算在计算c的值时,向负无穷方向舍入(floor()函数). 例如计算:-7 Mod 4 那么:a = -7:b = 4: 第一步:求整数商c,如进行求模运算c = -2(向负无穷方向舍入),求余c = -1(向0方向舍入): 第二步:计算模和

随机推荐