算法设计：模幂（递归）介绍和代码实现

2021年3月11日17:58:38 发表评论 781 次浏览

本文概述

建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
C ++
C
Java
Python3
C#
的PHP

给定三个数字a, b和c, 我们需要找到(ab) ％ C

现在为什么在求幂后执行"％c", 因为b即使a, b的值相对较小, 它的大小也会非常大, 这是一个问题, 因为我们尝试对问题进行编码的语言的数据类型很可能不会让我们存储这么大的数字。

例子：

Input : a = 2312 b = 3434 c = 6789
Output : 6343

Input : a = -3 b = 5 c = 89 
Output : 24

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

该想法基于以下属性。

属性1：

(m * n)％p具有一个非常有趣的属性：

(m * n)％p =(((m％p)*(n％p))％p

属性2：

如果b是偶数：

(a ^ b)％c =((a ^ b / 2)*(a ^ b / 2))％c？这表明分而治之

如果b是奇数：

(a ^ b)％c =(a *(a ^(b-1))％c

属性3：

如果必须返回绝对值小于y的负数x的mod：

然后(x + y)％y就可以了

注意：

另外, 由于(a ^ b / 2)*(a ^ b / 2)和a *(a ^(b-1)的乘积可能会导致溢出, 因此我们必须注意那些情况

C ++

// Recursive C++ program to compute modular power 
#include <bits/stdc++.h> 
using namespace std;
  
int exponentMod( int A, int B, int C) 
{ 
     // Base cases 
     if (A == 0) 
         return 0; 
     if (B == 0) 
         return 1; 
  
     // If B is even 
     long y; 
     if (B % 2 == 0) { 
         y = exponentMod(A, B / 2, C); 
         y = (y * y) % C; 
     } 
  
     // If B is odd 
     else { 
         y = A % C; 
         y = (y * exponentMod(A, B - 1, C) % C) % C; 
     } 
  
     return ( int )((y + C) % C); 
} 
  
// Driver code 
int main() 
{ 
     int A = 2, B = 5, C = 13; 
     cout << "Power is " << exponentMod(A, B, C); 
     return 0; 
} 
  
// This code is contributed by SHUBHAMSINGH10

C

// Recursive C program to compute modular power 
#include <stdio.h> 
  
int exponentMod( int A, int B, int C)
{
     // Base cases
     if (A == 0)
         return 0;
     if (B == 0)
         return 1;
  
     // If B is even
     long y;
     if (B % 2 == 0) {
         y = exponentMod(A, B / 2, C);
         y = (y * y) % C;
     }
  
     // If B is odd
     else {
         y = A % C;
         y = (y * exponentMod(A, B - 1, C) % C) % C;
     }
  
     return ( int )((y + C) % C);
}
  
// Driver program to test above functions 
int main() 
{ 
    int A = 2, B = 5, C = 13;
    printf ( "Power is %d" , exponentMod(A, B, C)); 
    return 0; 
}

Java

// Recursive Java program 
// to compute modular power 
import java.io.*; 
  
class GFG 
{ 
static int exponentMod( int A, int B, int C) 
{ 
          
     // Base cases 
     if (A == 0 ) 
         return 0 ; 
     if (B == 0 ) 
         return 1 ; 
      
     // If B is even 
     long y; 
     if (B % 2 == 0 )
     { 
         y = exponentMod(A, B / 2 , C); 
         y = (y * y) % C; 
     } 
      
     // If B is odd 
     else 
     { 
         y = A % C; 
         y = (y * exponentMod(A, B - 1 , C) % C) % C; 
     } 
      
     return ( int )((y + C) % C); 
} 
  
// Driver Code
public static void main(String args[]) 
{ 
     int A = 2 , B = 5 , C = 13 ; 
     System.out.println( "Power is " + 
                         exponentMod(A, B, C)); 
} 
} 
  
// This code is contributed 
// by Swetank Modi.

Python3

# Recursive Python program 
# to compute modular power 
def exponentMod(A, B, C):
      
     # Base Cases
     if (A = = 0 ):
         return 0
     if (B = = 0 ):
         return 1
      
     # If B is Even
     y = 0
     if (B % 2 = = 0 ):
         y = exponentMod(A, B / 2 , C)
         y = (y * y) % C
      
     # If B is Odd
     else :
         y = A % C
         y = (y * exponentMod(A, B - 1 , C) % C) % C
     return ((y + C) % C)
  
# Driver Code
A = 2
B = 5
C = 13
print ( "Power is" , exponentMod(A, B, C))
      
# This code is contributed 
# by Swetank Modi.

C#

// Recursive C# program 
// to compute modular power 
class GFG 
{ 
static int exponentMod( int A, int B, int C) 
{ 
          
     // Base cases 
     if (A == 0) 
         return 0; 
     if (B == 0) 
         return 1; 
      
     // If B is even 
     long y; 
     if (B % 2 == 0)
     { 
         y = exponentMod(A, B / 2, C); 
         y = (y * y) % C; 
     } 
      
     // If B is odd 
     else
     { 
         y = A % C; 
         y = (y * exponentMod(A, B - 1, C) % C) % C; 
     } 
      
     return ( int )((y + C) % C); 
} 
  
// Driver Code
public static void Main() 
{ 
     int A = 2, B = 5, C = 13; 
     System.Console.WriteLine( "Power is " + 
                     exponentMod(A, B, C)); 
} 
} 
  
// This code is contributed 
// by mits

的PHP

<?php
// Recursive PHP program to 
// compute modular power 
function exponentMod( $A , $B , $C ) 
{ 
     // Base cases 
     if ( $A == 0) 
         return 0; 
     if ( $B == 0) 
         return 1; 
      
     // If B is even 
     if ( $B % 2 == 0) 
     { 
         $y = exponentMod( $A , $B / 2, $C ); 
         $y = ( $y * $y ) % $C ; 
     } 
      
     // If B is odd 
     else
     { 
         $y = $A % $C ; 
         $y = ( $y * exponentMod( $A , $B - 1, $C ) % $C ) % $C ; 
     } 
      
     return (( $y + $C ) % $C ); 
} 
  
  
// Driver Code
$A = 2;
$B = 5;
$C = 13; 
echo "Power is " . exponentMod( $A , $B , $C ); 
  
// This code is contributed 
// by Swetank Modi. 
?>

输出如下：