快速幂应用

超、凢脫俗 2022-06-06 23:06 150阅读 0赞

快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。

假设我们要求a^b,按照朴素算法就是把a连乘b次，这样一来时间复杂度是O(b)，即是O(n)级别，快速幂能做到O(logn)。它的原理如下：  
假设我们要求a^b，那么其实b是可以拆成二进制的，该二进制数第i位的权为2^(i-1)，例如当b==11时，a^11=a^(2^0+2^1+2^3)  
11的二进制是1011，11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1，因此，我们将a¹¹转化为算 a^(2^0)\*a^(2^1)\*a^(2^3) 。由于是二进制，使用位运算实现更加简洁： &  和 >>。

&运算用于二进制取位操作：例如b&1，表示取b二进制的最低位,判断和1是否相同，相同返回1，否则返回0；也可用于判断奇偶：b&1==0为偶数，b&1==1为奇数。

>>运算把b的二进制右移一位，即去掉其二进制位的最低位。

实现快速幂的代码如下：

public static int FastPower(int a,int b){  
            int ans = 1,base = a;  
            while(b != 0){  
                if((b&1) != 0)  
                    ans *= base;  
                base*=base;  
                b >>=1;  
            }  
            return ans; 
    }

`可将快速幂应用到实际编程题中。`

问题描述：有W个位置，每个位置有一种状态，共有N种状态。求相邻两个位置状态相同的共有多少种情况。

分析：利用排列组合思想来解题。直接求相邻两个位置状态相同考虑的情况不好解决，因为连续2个位置、连续3个位置，...,连续W个位置状态相同的都有连续两个位置状态相同，比较复杂。可以先求W个位置N中状态的所有情况，共N^W种；W个位置相邻两个位置不相同的有N(N-1)^(W-1)种，用总的情况种数减去相邻两个位置不相同的情况总数，即为相邻两个位置状态相同的情况种数，问题就变成了求：N^W-N(N-1)^(W-1)，快速幂就派上用场了。

import java.util.Scanner;
    
    public class FastPower {
    
    	public static int FastPower(int a,int b){
    		int ans = 1,base = a;
    		while(b != 0){
    			if((b&1) != 0)
    				ans *= base;
    			base*=base;
    			b >>=1;
    		}
    		return ans;
    	}
    		
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		Scanner scanner = new Scanner(System.in);		
    		int n = scanner.nextInt();
    		int w = scanner.nextInt();
    		int ans = FastPower(n, w) - n * FastPower(n-1,w-1);
    		System.out.println(ans);
    	}
    }