[转帖]模运算及其应用二基本应用_Android, Python及开发编程讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  Android, Python及开发编程讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 3343 | 回复: 0   主题: [转帖]模运算及其应用二基本应用        下一篇 
mengyuanye
注册用户
等级:少校
经验:1413
发帖:108
精华:7
注册:2012-11-14
状态:离线
发送短消息息给mengyuanye 加好友    发送短消息息给mengyuanye 发消息
发表于: IP:您无权察看 2012-11-22 14:16:34 | [全部帖] [楼主帖] 楼主

二 基本应用:

1.判别奇偶数

    奇偶数的判别是模运算最基本的应用,也非常简单。易知一个整数n对2取模,如果余数为0,则表示n为偶数,否则n为奇数。

C++实现功能函数:

/*

函数名:IsEven

函数功能:判别整数n的奇偶性。能被2整除为偶数,否则为奇数                         

输入值:int n,整数n 

返回值:bool,若整数n是偶数,返回true,否则返回false 

*/
bool IsEven(int n)
{
      return (n % 2 == 0);
}


2.判别素数

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

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

C++实现功能函数:

/*

函数名:IsPrime

函数功能:判别自然数n是否为素数。                                                                          

输入值:int n,自然数n 

返回值:bool,若自然数n是素数,返回true,否则返回false 

*/
bool IsPrime(unsigned int n)
{
      unsigned maxFactor = sqrt(n); //n的最大因子 
      for (unsigned int i=2; i<=maxFactor; i++)
      {
            if (n % i == 0) //n能被i整除,则说明n非素数 
            {
                  return false;
            }
      }
      return true;
}


3. 最大公约数

    求最大公约数最常见的方法是欧几里德算法(又称辗转相除法),其计算原理依赖于定理: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;
}


4.模幂运算

    利用模运算的运算规则,我们可以使某些计算得到简化。例如,我们想知道3333^5555的末位是什么。很明显不可能直接把3333^5555的结果计算出来,那样太大了。但我们想要确定的是3333^5555(%10),所以问题就简化了。

    根据运算规则(4)ab % p = ((a % p)b) % p  ,我们知道3333^5555(%10)= 3^5555(%10)。由于3^4 = 81,所以3^4(%10)= 1。

根据运算规则(3) (a * b) % p = (a % p * b % p) % p ,由于5555 = 4 * 1388 + 3,我们得到3^5555(%10)=(3^(4*1388) * 3^3)(%10)=((3^(4*1388)(%10)* 3^3(%10))(%10)

=(1 * 7)(%10)= 7。


       计算完毕。

    利用这些规则我们可以有效地计算X^N(% P)。简单的算法是将result初始化为1,然后重复将result乘以X,每次乘法之后应用%运算符(这样使得result的值变小,以免溢出),执行N次相乘后,result就是我们要找的答案。

    这样对于较小的N值来说,实现是合理的,但是当N的值很大时,需要计算很长时间,是不切实际的。下面的结论可以得到一种更好的算法。

    如果N是偶数,那么X^N =(X*X)^[N/2];

    如果N是奇数,那么X^N = X*X^(N-1) = X *(X*X)^[N/2];

其中[N]是指小于或等于N的最大整数。

C++实现功能函数:

/*

函数功能:利用模运算规则,采用递归方式,计算X^N(% P)     

函数名:PowerMod

输入值:unsigned int x,底数x 

    unsigned int n,指数n 

    unsigned int p,模p 

返回值:unsigned int,X^N(% P)的结果 

*/
unsigned int PowerMod(unsigned int x, unsigned int n, unsigned int p)
{
      if (n == 0)
      {
            return 1;
      }
      unsigned int temp = PowerMod((x * x)%p, n/2, p); //递归计算(X*X)^[N/2] 
      if ((n & 1) != 0) //判断n的奇偶性 
      {
            temp = (temp * x) % p;
      }
      return temp;
}




赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论