取模运算和取余运算的区别

对于整型数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方向舍入);

第二步:计算模和余数的公式相同,但因c的值不同,求模时r = 1,求余时r = -3。

归纳:当a和b符号一致时,求模运算和求余运算所得的c的值一致,因此结果一致。

当符号不一致时,结果不一样。求模运算结果的符号和b一致,求余运算结果的符号和a一致。

另外各个环境下%运算符的含义不同,比如c/c++,java 为取余,而python则为取模。

补充:

7 mod 4 = 3(商 = 1 或 2,1<2,取商=1)

-7 mod 4 = 1(商 = -1 或 -2,-2<-1,取商=-2)

7 mod -4 = -1(商 = -1或-2,-2<-1,取商=-2)

-7 mod -4 = -3(商 = 1或2,1<2,取商=1)

这里模是4,取模其实全称应该是取模数的余数,或取模余。

增加补充内容(以上五行)后,被修改商值,但是括号内容不变,出现奇怪矛盾。

在python下 % 运算符代表取模,如要修改,请先用python做

-7 % 4

运算,或其它语言做取模运算验证,理解后再动手。

应用

判别奇偶数

奇偶数的判别是模运算最基本的应用,也非常简单。

已知一个整数n对2取模,如果余数为0,则表示n为偶数,否则n为奇数。

C++实现功能函数:

/*
函数名:IsEven
函数功能:判别整数n的奇偶性。能被2整除为偶数,否则为奇数
输入值:intn,整数n
返回值:bool,若整数n是偶数,返回true,否则返回false
*/
bool IsEven(int n)
{
return(n%2==0);
}

判别素数

一个数,如果只有1和它本身两个因数,这样的数叫做质数(或素数)。例如 2,3,5,7 是质数,而 4,6,8,9 则不是,后者称为合成数或合数。

判断某个自然数是否是素数最常用的方法就是试除法——用不比该自然数的平方根大的正整数去除这个自然数,若该自然数能被整除,则说明其非素数。

C++实现功能函数:

/*函数名:IsPrime函数功能:判别自然数n是否为素数。输入值:intn,
自然数n返回值:bool,若自然数n是素数,返回true,否则返回false*/
bool IsPrime(unsignedintn)
{
unsigned maxFactor=sqrt(n);//n的最大因子
for(unsignedinti=2;i<=maxFactor;i++)
{
if(n%i==0)//n能被i整除,则说明n非素数
{
return false;
}
}
return true;
}

求最大公约数

求最大公约数最常见的方法是欧几里德算法(又称辗转相除法),其计算原理依赖于定理:gcd(a,b) = gcd(b,a mod b)

证明:

a可以表示成a = kb + r,则r = a mod b

假设d是a,b的一个公约数,则有d|a, d|b,而r = a - kb,因此d|r

因此d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数,则d | b , d |r ,但是a = kb +r

因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证。

C++实现功能函数:

/*函数功能:利用欧几里德算法,采用递归方式,求两个自然数的最大公约数函数名:
Gcd输入值:unsigned int a,自然数a;unsigned int b,自然数b
返回值:unsigned int,两个自然数的最大公约数*/
unsigned int Gcd(unsigned int a,unsigned int b)
{
if(b==0)
return a;
return Gcd(b,a%b);
}
/*函数功能:利用欧几里德算法,采用迭代方式,求两个自然数的最大公约数函数名:
Gcd输入值:unsigned int a,自然数a;unsigned int b,自然数b
返回值:unsigned int,两个自然数的最大公约数*/
unsigned int Gcd(unsigned int a,unsigned int b)
{
unsigned int temp;
while(b!=0)
{
temp=a%b;
a=b;
b=temp;
}
return a;
}

引用资料