算法（3） - 数字相关的算法

落日映苍穹つ 2022-09-04 13:45 157阅读 0赞

参考：

*  漫画算法
 *  lubuladong的算法小抄

## 一、数字相关的算法 ##

常见的数字相关算法：

*  求出最大公约数
 *  判断一个数是不是2的次幂
 *  质数相关问题

### 1.1 求出最大公约数 ###

常见的解决方法有3种：

*  辗转相除法：又叫欧几里得算法
 *  更相减损术：另一种求最大公约数的算法
 *  辗转相除法+更相减损术+位运算：结合了前两种算法，同时通过位运算加快运算速度

#### 1.1.1 辗转相除法 ####

> 辗转相除法定理：两个正整数a和b（a>b），它们的最大公约数等于 a除以b的余数c 和 b 之间的最大公约数

思路：

*  两个正整数a和b，通过取模操作得到余数c
 *  通过递归方式计算 c和b的最大公约数
 *  直到两个数可以整除或者其中一个数为1

注：

*  当两个整数比较大时，取模运算性能比较差
 *  时间复杂度：不太好算，近似于O(log(max(a, b)))

示例代码：

/** * 计算最大公约数（辗转相除法） * * @param a * @param b * @return */
    public static int getGreatestCommonDivisor(int a, int b) { 
        // 最大、最小值
        int big = a > b ? a : b;
        int small = a < b ? a : b;
    
        int c = big % small;
        if (c == 0) { 
            return small;
        }
        // 计算 余数c 和 small的最大公约数
        return getGreatestCommonDivisor(c, small);
    }

#### 1.1.2 更相减损术 ####

更相减损术，出自《九章算术》，也是一种求最大公约数的算法。

> 更相减损术定理：两个正整数a和b（a>b），它们的最大公约数等于 a-b的差值c 和 b 之间的最大公约数

思路：

*  两个正整数a和b，通过减法操作得到差值c
 *  通过递归方式计算 c和b的最大公约数
 *  直到两个数相等

注：

*  通过减法操作避免了取模运算
 *  不稳定的算法，当两个数相差很大时，如10000和1，就要递归9999次
 *  时间复杂度：最坏情况是O(max(a, b))

示例代码：

/** * 计算最大公约数（更相减损术） * * @param a * @param b * @return */
    public static int getGreatestCommonDivisor(int a, int b) { 
    	if (a == b) { 
    		return a;
    	}
        // 最大、最小值
        int big = a > b ? a : b;
        int small = a < b ? a : b;
    
        // 计算 差值 和 small的最大公约数
        return getGreatestCommonDivisor(big - small, small);
    }

#### 1.1.3 辗转相除法+更相减损术+位运算 ####

上面两种算法都存在一定问题，那么就可以各取其优点再结合位运算进行优化。

思路：

*  a和b都是偶数：gcd(a, b) = 2 \* gcd(a / 2, b / 2) = 2 \* gcd(a >> 1, b >> 1)
 *  a为偶数、b为奇数：gcd(a, b) = gcd(a / 2, b) = gcd(a >> 1, b)
 *  a为奇数、b为偶数：gcd(a, b) = gcd(a, b / 2) = gcd(a, b >> 1)
 *  a和b都是奇数：先进行一次更相减损术运算一次，gcd(a, b) = gcd(b, a - b)，此时a-b是偶数，再进行位运算

注：

*  当两个数比较小时，看不出计算次数的优势，两数较大时，计算次数会明显减少
 *  
 *  时间复杂度：O(log(max(a, b)))

示例：

/** * 计算最大公约数（辗转相除法+更相减损术+位运算） * * @param a * @param b * @return */
    public static int gcd(int a, int b) { 
        if (a == b ) { 
            return a;
        }
    
        // a和b都是偶数
        if ((a & 1) == 0 && (b & 1) == 0) { 
            return gcd(a >> 1, b >> 1) << 1;
        }
        // a是偶数 b是奇数
        else if ((a & 1) == 0 && (b & 1) != 0) { 
            return gcd(a >> 1, b);
        }
        // a是奇数 b是偶数
        else if ((a & 1) != 0 && (b & 1) == 0) { 
            return gcd(a, b >> 1);
        }
        // a和b都是奇数
        else { 
            // 最大、最小值
            int big = a > b ? a : b;
            int small = a < b ? a : b;
            return gcd(big - small, small);
        }
    }

### 1.2 判断一个数是2的n次幂 ###

首先看一组数据：

<table> 
 <thead> 
  <tr> 
   <th>n</th> 
   <th>n的二进制</th> 
   <th>n-1的二进制</th> 
   <th>n&amp;n-1</th> 
   <th>2的次幂</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>8</td> 
   <td>0000 1000</td> 
   <td>0000 0111</td> 
   <td>0</td> 
   <td>是</td> 
  </tr> 
  <tr> 
   <td>16</td> 
   <td>0001 0000</td> 
   <td>0000 1111</td> 
   <td>0</td> 
   <td>是</td> 
  </tr> 
  <tr> 
   <td>32</td> 
   <td>0010 0000</td> 
   <td>0001 1111</td> 
   <td>0</td> 
   <td>是</td> 
  </tr> 
  <tr> 
   <td>64</td> 
   <td>0100 0000</td> 
   <td>0011 1111</td> 
   <td>0</td> 
   <td>是</td> 
  </tr> 
  <tr> 
   <td>100</td> 
   <td>0110 0100</td> 
   <td>0110 0011</td> 
   <td>0110 0000</td> 
   <td>否</td> 
  </tr> 
 </tbody> 
</table>

所以可以得出结论，判断一个整数n只需要计算 n & n - 1 是不是0即可

注：

*  时间复杂度O(1)

/** * 判断一个正整数是否是2的次幂 * * @param a * @param b * @return */
    public static boolean isPowerOf2(int num) { 
    	return (num & num - 1) == 0;
    }

### 1.3 质数相关的问题 ###

> 质数：也叫素数，在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数  
> 常见的如2 3 5 7 11 13 17 19等都是质数

#### 1.3.1 判断一个数是否是质数 ####

思路：

*  从2开始，假如能被整除，那么表示是合数，即不是质数
 *  不过需要一致计算到n-1，可以进行优化

注：时间复杂度为 O(sqrt(N))

示例：

/** * 判断是否是质数 * * @param num 大于等于2 * @return */
    public static boolean isPrime(int num) { 
    	// 从2开始，到 sqrt(num) 即可
    	// 举例：例如num=12，可能的情况：2*6 3*4 4*3 6*2 
    	// 可以看到后面的情况就是前面的因子相反的情况
    	// 所以在[2, sqrt(num)]区间内都不能整除，那么(sqrt(num), num)区间也不能整除
        for (int i = 2; i * i  <= num; i++) { 
            if (num % i == 0) { 
                return false;
            }
        }
        return true;
    }

#### 1.3.2 统计质数个数 ####

（1）遍历判断

1.3.1中已经实现了判断一个数是否是质数，那么直接判断\[2, n)区间内质数个数即可

注：时间复杂度：O(N sqrt(N))

示例：

/** * 计算 [2, n) 中质数个数（遍历判断） * * @param num * @return */
    public static int countPrimes(int num) { 
        int count = 0;
        for (int i = 2; i < num; i++) { 
            if (isPrime(i)) { 
                count++;
            }
        }
        return count;
    }

（2）排除法

由（1）中解法可以看出，2是质数，那么4 6 8 10 12等都是合数，但是遍历过程中实际上又判断了一次是否是质数，可以将这些数据排除掉。

思路：

*  1.定义数组标识每个数是否是质数，默认都是质数
 *  2.假如一个数i是质数，那么2*i、3*i、4\*i都是合数，将这些数标识修改为合数
 *  3.统计数组中质数个数即可

示例：

/** * 计算 [2, n) 中质数个数（排除法） * * @param num * @return */
    public static int countPrimes(int num) { 
        // 标记所有数是质数
        boolean[] prims = new boolean[num];
        Arrays.fill(prims, true);
    
        // 从2开始，判断到sqrt(num)即可，因为因子对称的
        // 例如：num=17
        // 2是质数，所以标识4 6 8 10 12 14 16等不是质数，
        // 3是质数，所以标识6 9 12 15不是质数
        // 那么到5的时候，会标识10 15不是质数，实际上10 15已经被 i=2、3时所标识过了，所以5就不需要再处理了
        for (int i = 2; i * i <= num; i++) { 
        	if (!prims[i]) { 
    			continue;
    		}
            // 判断i是否质数
            if (isPrime(i)) { 
                // i是质数，那么2i、3i、4i等都不可能是质数，所以将数组中标识改为false
    
                // 从 i*i 开始的原因：
                // num=17，那么i取值 2 3 4
                // i=2时，会将 4 6 8 10 12 14 16标识为false
                // i=3时，会将 6 9 12 15标识为false
                // i=4时，会将 8 12 16 标识为false
                // 由此可以发现，如果从2*i开始处理的话，那么i=3时的6 12都已经被i=2标识过了
                // 所以为了尽量减少重复标识，从i*i开始（也只是稍微优化下，不能完全避免不重复标识的情况）
                for (int j = i * i; j < num; j += i) { 
                    prims[j] = false;
                }
            }
        }
    
        // 遍历数组，统计质数个数
        int count = 0;
        for (int i = 2; i < num; i++) { 
            if (prims[i]) { 
                count++;
            }
        }
        return count;
    }