一些通过数学分析解决的算法题汇总

た入场券 2023-02-10 01:21 11阅读 0赞

## 写在前面 ##

**如果觉得写得好，或者有所帮助，记得点个关注和点个赞，不胜感激！**  
我发现最近经常会遇到一些需要通过数学分析去解决的问题，做的时候想着各种方法，然后看到题解，发现可以用数学分析的方式，找到非常快的解决办法，整个人就emmmmm了，所以这里开这篇博文，用来记录自己碰到的可以用数学分析的方式解决的算法问题，不断更新。

## “树根”相关问题 ##

“树根”在维基百科的定义如下：

在数学中，数根(又称位数根或数字根Digital root)是自然数的一种性质，换句话说，每个自然数都有一个数根。数根是将一正整数的各个位数相加（即横向相加），若加完后的值大于10的话，则继续将各位数进行横向相加直到其值小于十为止，或是，将一数字重复做数字和，直到其值小于十为止，则所得的值为该数的数根。例如`54817`的数根为`7`，因为`5+4+8+1+7=25`，`25大于10`则再加一次，`2+5=7`，`7小于10`，则`7为54817的数根`。

那么“树根”又有什么用途呢？

数根可以计算模运算的同余，对于非常大的数字的情况下可以节省很多时间。数字根可作为一种检验计算正确性的方法。例如，两数字的和的数根等于两数字分别的数根的和。另外，数根也可以用来判断数字的整除性，如果数根能被3或9整除，则原来的数也能被3或9整除。

接下来讨论我们怎么求出树根。我们把 1 到 30 的树根列出来。

原数: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
    数根: 1 2 3 4 5 6 7 8 9  1  2  3  4  5  6  7  8  9  1  2  3  4  5  6  7  8  9  1  2  3

可以发现`数根 9 个为一组`， 1 - 9 循环出现。我们需要做就是把原数映射到树根就可以，循环出现的话，想到的就是取余了。结合这个规律，对于给定的 n 有三种情况。

*  n 是 0 ，数根就是 0。
 *  n 不是 9 的倍数，数根就是 n 对 9 取余，即 n mod 9。
 *  n 是 9 的倍数，数根就是 9。

我们可以把两种情况统一起来，我们将给定的数字减 1，相当于原数整体向左偏移了 1，然后再将得到的数字对 9 取余，最后将得到的结果加 1 即可。原数是 n，树根就可以表示成 `(n-1) mod 9 + 1`，可以结合下边的过程理解。

原数: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
    偏移: 0 1 2 3 4 5 6 7 8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
    取余: 0 1 2 3 4 5 6 7 8  0  1  2  3  4  5  6  7  8  0  1  2  3  4  5  6  7  8  0  1  2  
    数根: 1 2 3 4 5 6 7 8 9  1  2  3  4  5  6  7  8  9  1  2  3  4  5  6  7  8  9  1  2  3

所以，求一个数的树根，一句代码就可以实现，即`(num - 1) % 9 + 1;`，这里给出一个题目，一句代码即可。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center]

public int addDigits(int num) { 
        return (num - 1) % 9 + 1;
    }

## 计算阶乘0的个数 ##

这个我之前单独写过一篇文章，这里就不赘述了，[地址][Link 1]。

## 四平方和定理 ##

四平方和定理，意思是任何正整数都能表示成四个平方数的和。少于四个平方数的，像  12 12 12 这种，可以补一个  0 0 0 也可以看成四个平方数， 12 = 4 + 4 + 4 + 0 12 = 4 + 4 + 4 + 0 12=4\+4\+4\+0。知道了这个定理，对于题目要找的解，其实只可能是  1 , 2 , 3 , 4 1, 2, 3, 4 1,2,3,4 其中某个数。

[Legendre’s three-square theorem][Legendre_s three-square theorem] ，这个定理表明，如果正整数 n 被表示为三个平方数的和，那么  n n n 不等于  4 a ∗ ( 8 b + 7 ) 4^a\*(8b+7) 4a∗(8b\+7)， a a a 和  b b b 都是非负整数。换言之，如果  n = = 4 a ∗ ( 8 b + 7 ) n == 4^a\*(8b+7) n==4a∗(8b\+7) ，那么他一定不能表示为三个平方数的和，同时也说明不能表示为一个、两个平方数的和，因为如果能表示为两个平方数的和，那么补个  0 0 0，就能凑成三个平方数的和了。

一个、两个、三个都排除了，所以如果  n = = 4 a ∗ ( 8 b + 7 ) n == 4^a\*(8b+7) n==4a∗(8b\+7)，那么  n n n 只能表示成四个平方数的和了。所以代码的话，我们采取排除的方法。

*  首先考虑答案是不是  1 1 1，也就是判断当前数是不是一个平方数。
 *  然后考虑答案是不是  4 4 4，也就是判断 n 是不是等于  4 a ∗ ( 8 b + 7 ) 4^a\*(8b+7) 4a∗(8b\+7)。
 *  然后考虑答案是不是  2 2 2，当前数依次减去一个平方数，判断得到的差是不是平方数。
 *  以上情况都排除的话，答案就是  3 3 3。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 1]

public int numSquares(int n) { 
        if (isSquare(n)) { 
            return 1;
        }
    
        int temp = n;
        while (temp % 4 == 0) { 
            temp /= 4;
        }
        if (temp % 8 == 7) { 
            return 4;
        }
    
        for (int i = 1; i * i < n; i++) { 
            if (isSquare(n - i * i)) { 
                return 2;
            }
        }
    
        return 3;
    }
    
    private boolean isSquare(int n) { 
        int sqrt = (int) Math.sqrt(n);
        return sqrt * sqrt == n;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200519171705869.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE=,size_16,color_FFFFFF,t_70#pic_center
[Link 1]: https://dengbocong.blog.csdn.net/article/details/105921706
[Legendre_s three-square theorem]: https://en.wikipedia.org/wiki/Legendre%27s_three-square_theorem
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200521120018376.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RCQ18xMjE=,size_16,color_FFFFFF,t_70#pic_center