13_经典数学问题算法(Java、Kotlin描述)

作者: 刘加城 | 来源:发表于2023-01-11 06:03 被阅读0次

本篇文章介绍一些经典的数学问题求解算法。

(1)素数

在大于1的自然数中，除了1和自身外，不能被其他自然数整除的数，称为素数，也叫质数。Java版本算法：

    boolean isPrime(int n){
        for (int i =2;i<n;i++){
            if (n % i == 0){
                return false;
            }
        }
        return true;
    }

Kotlin版本：

    fun isPrime(n: Int): Boolean {
        for (i in 2 until n) {
            if (n % i == 0) {
                return false
            }
        }
        return true
    }

(2)欧几里得最大公因数算法

Java实现：

/**
     * 最大公因数算法：欧几里得算法 O(log N)
     * 两个数的最大公因数是同时整除二者的最大整数，gcd(50,15) = 5;
     * 假设m >= n ，如果m < n ，则交换一下顺序
     */
    public static long gcd(long m, long n) {
        while (n != 0) {
            long rem = m % n;
            m = n;
            n = rem;
        }
        return m;
    }

kotlin实现：

fun gcd(m: Long, n: Long): Long {
        var m = m
        var n = n
        while (n != 0L) {
            val rem = m % n
            m = n
            n = rem
        }
        return m
    }

单看这个算法实现，是不容易理解的。因为它涉及到下面2个定理，还需要进行证明。

1）如果c可以整除a，同时c也可以整除b，那么c就可以整除ax+by (x、y为任意的整数)；
2）如果a = bx + r ,那么gcd(a,b) = gcd(b,r);

对定理2做一些说明。因为a = bx + r ,那么根据定理1，任何可以整除b、r的公因数，一定可以整除a，也就是说，b、r的公因数都是a、b的公因数。将等式转换一下，r = a - bx , 同样根据定理1，任何可以整除a、b的公因数，一定可以整除r，也就是说，a、b的公因数都是b、r的公因数。所以等式成立。
注意：如果X整除Y，那么Y/X = a ,a是某个常值。X整除Y，X在分母的位置。
注意：根据除法定理，对于任意的整数a和b,其中b!=0 ,那么一定存在一组整数q、r使得：a = qb + r ,其中0<= r < |b| 。
接下来对欧几里得算法进行证明：

假设a、b都大于0 
如果a = q1b + r1，0 <= r1 < b；
同时b = q2r1 + r2，0 <= r2 < r1;
同时r1 = q3r2 + r3, 0 <= r3 < r2;
…
这样不停的分解下去，由于b > r1 > r2 > ... >= 0 ,这样分解下去，必然有一个rn = 0 。也就是说最后两步分解一定是:
rn-3 = qn-1rn-2 + rn-1 0 < rn-1 < rn-2;
rn-2 = qnrn-1 + rn，其中rn = 0

根据上面的定理（2），gcd(a, b) = gcd(b, r1) = gcd(r1, r2) = ... = gcd(rn-2, rn-1)。由于rn-1可以整除rn-2，那么rn-1就是最大公因数。

再介绍一下它的递归版本，Java实现：

    public static long gcd1(long m, long n) {
        if (n == 0) {
            return m;
        } else {
            return gcd1(n, m % n);
        }
    }

kotlin实现：

fun gcd1(m: Long, n: Long): Long {
        return if (n == 0L) {
            m
        } else {
            gcd1(n, m % n)
        }
    }

(3)暴力穷举最大公因数算法

使用暴力穷举法也可以找到最大公因数。它的时间复杂度比不上欧几里得算法，但很容易理解。
Java实现：

/**
     * 最大公因数算法2 : 连续整数检测，暴力穷举法O(N)
     * 假设m >= n
     */
    public static long gcd2(long m, long n) {
        long result = 1;
        for (long i = n; i >= 1; i--) {
            if (m % i == 0 && n % i == 0) {
                result = i;
                break;
            }
        }
        return result;
    }

Kotlin实现：

    fun gcd2(m: Long, n: Long): Long {
        var result: Long = 1
        for (i in n downTo 1) {
            if (m % i == 0L && n % i == 0L) {
                result = i
                break
            }
        }
        return result
    }

(4)分解质因数算法

递归方式的Java实现：

    /**
     * 将一个整数分解质因数 递归方式
     */
    public static void printPrimeNum(int m) {
        //找到最小质因数
        int smallPrime = m;
        for (int i = 2; i < m / 2; i++) {
            if (m % i == 0) {
                smallPrime = i;
                break;
            }
        }
        if (smallPrime < m) {
            System.out.print(smallPrime + "*");
            printPrimeNum(m / smallPrime);
        } else {
            System.out.println(smallPrime);
        }
    }

递归方式的Kotlin实现：

    fun printPrimeNum(m: Int) {
        //找到最小质因数
        var smallPrime = m
        for (i in 2 until m / 2) {
            if (m % i == 0) {
                smallPrime = i
                break
            }
        }
        if (smallPrime < m) {
            print("$smallPrime*")
            printPrimeNum(m / smallPrime)
        } else {
            println(smallPrime)
        }
    }

迭代方式的Java实现：

    /**
     * 将一个整数分解质因数 迭代方式
     */
    public static void printPrimeNum2(int m) {
        for (int i = 2; i < m / 2; i++) {
            if (m % i == 0) {
                System.out.print(i + "*");
                m = m / i;
                i--;
            }
        }
        System.out.println(m);
    }

迭代方式的Kotlin实现：

    fun printPrimeNum2(m: Int) {
        var m = m
        var i = 2
        while (i < m / 2) {
            if (m % i == 0) {
                print("$i*")
                m = m / i
                i--
            }
            i++
        }
        println(m)
    }

(5)最大公倍数

最大公倍数可以通过最小公约数来得到。Java版本：

    int lcm(int a, int b){
        int c ,d;
        c = gcd(a,b);
        d = (a*b)/c;
        return d;
    }

    int gcd(int m, int n) {
        if (n == 0) {
            return m;
        } else {
            return gcd(n, m % n);
        }
    }

Kotlin版本：

    fun lcm(a: Int, b: Int): Int {
        val c: Int
        val d: Int
        c = gcd(a, b)
        d = a * b / c
        return d
    }

    fun gcd(m: Int, n: Int): Int {
        return if (n == 0) {
            m
        } else {
            gcd(n, m % n)
        }
    }

(6)非线性方程求解

线性方程是一元一次方程，它是一条直线。非线性方程是一元多次方程。本小节采用二分法来求解非线性方程。
主要思想：对于函数f(x)，如果x = c 时，f(c) = 0，那么把x = c称为函数f(x)的零点。求解方程就是计算该方程所有的零点。对于二分法，假定非线性方程在区间(x，y)上连续，如果存在两个实数a和b属于区间(x，y)，满足条件：f(a) * f(b) < 0，也就是说f(a)、f(b)异号，这说明在(a，b)上一定有零点，至少包含一个解。非线性方程很多时候没有精确解，如果在某个可以接受的精度内，f(x)小于该精度，就可以认为找到了方程的解。
Java版本：

    /**
     * 二分法求解非线性方程
     * @param a
     * @param b
     * @param limit 精度限制
     * @return
     */
    double binaryGet(double a, double b,double limit){
        double c = (a+b)/2;
        while (Math.abs(func(c)) > limit && Math.abs(func(a - b)) > limit){
            if (func(c) * func(b) < 0){
                a = c;
            }
            if (func(a) * func(c) < 0){
                b = c;
            }
            c = (a+b)/2;
        }
        return c;
    }

    /**
     * 可以是任意的一元n次函数，这里仅以x*x为例
     * @param x
     * @return
     */
    double func(double x){
        return x*x;
    }

Kotlin版本：

    /**
     * 二分法求解非线性方程
     * @param a
     * @param b
     * @param limit 精度限制
     * @return
     */
    fun binaryGet(a: Double, b: Double, limit: Double): Double {
        var a = a
        var b = b
        var c = (a + b) / 2
        while (Math.abs(func(c)) > limit && Math.abs(func(a - b)) > limit) {
            if (func(c) * func(b) < 0) {
                a = c
            }
            if (func(a) * func(c) < 0) {
                b = c
            }
            c = (a + b) / 2
        }
        return c
    }

    /**
     * 可以是任意的一元n次函数，这里仅以x*x为例
     * @param x
     * @return
     */
    fun func(x: Double): Double {
        return x * x
    }

(7)一维多项式求值

一个普遍的一维多项式示例如下：
P(x) = a $_{n-1}$ x $^{n-1}$ + a $_{n-2}$ x $^{n-2}$ + ··· + a $_1$ x + a $_0$
将它变换一下形式：
P(x) = (···(( a $_{n-1}$ x + a $_{n-2}$ )x + a $_{n-3}$ )x + ··· + a $_1$ )x + a $_0$
可以看出，最内层是：a $_{n-1}$ x + a $_{n-2}$ ，外层可以通过它来一层层递推得到，Java版本算法如下：

    /**
     * 一维多项式求值
     *
     * @param a 系数 数组
     * @param x 给定的某个x值
     * @param n 项数
     * @return
     */
    double polynomial(double[] a, double x, int n) {
        double result = a[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            result = result * x + a[i];
        }
        return result;
    }

Kotlin版本：

    /**
     * 一维多项式求值
     *
     * @param a 系数 数组
     * @param x 给定的某个x值
     * @param n 项数
     * @return
     */
    fun polynomial(a: DoubleArray, x: Double, n: Int): Double {
        var result = a[n - 1]
        for (i in n - 2 downTo 0) {
            result = result * x + a[i]
        }
        return result
    }

(8)斐波那契数列

来源于13世纪意大利数学家斐波那契，他记载了一个兔子产仔问题，大意：如果一个两个月大的兔子以后每一个月都可以生一对小兔子，而新生的兔子两个月后才可以生小兔子，那么如果没有意外死亡事件，一年后共有多少只兔子？
通过观察，可以得到：F $_n$ = F $_{n-1}$ + F $_{n-2}$ ，且F(1) = F(2) = 1;
Java版本算法：

    int fibonacci(int n){
        if (n == 1 || n == 2){
            return 1;
        }
        return fibonacci(n-1) + fibonacci(n-2);
    }

Kotlin版本：

    fun fibonacci(n: Int): Int {
        return if (n == 1 || n == 2) {
            1
        } else fibonacci(n - 1) + fibonacci(n - 2)
    }

上面算法的增长速度是指数级的。还有一种线性版本，记录最近算出的两个斐波那契数，它的时间复杂度是O(N)。Java版本如下：

    int fibonacci(int n) {
        if (n <= 1) return 1;
        int last = 1;
        int nextLast = 1;
        int result = 1;

        for (int i = 2; i <= n; i++) {
            result = last + nextLast;
            nextLast = last;
            last = result;
        }
        return result;
    }

Kotlin版本：

    fun fibonacci(n: Int): Int {
        if (n <= 1) return 1
        var last = 1
        var nextLast = 1
        var result = 1
        for (i in 2..n) {
            result = last + nextLast
            nextLast = last
            last = result
        }
        return result
    }

(9)圆周率计算

Monte Carlo概率算法求解圆周率 $\pi$ ，思路：一个边为1的正方形，以它的一个顶点画一个半径为1的圆，与正方形相交的部分面积(阴影面积)是 $\pi$ /4;如果均匀的向这个正方形中撒点，那么落入阴影部分的点和落入正方形中的点数之比应该是：S $_阴$ /S $_{正方形}$ = $\pi$ /4；
Java版本如下：

    static double computePI (int n){
        double PI;
        double x,y;
        int i,sum = 0;
        for (i=1;i<n;i++){
            x = Math.random();
            y = Math.random();

            if ((x*x + y*y) <= 1){ //在阴影面积内
                sum++;
            }
        }
        PI = 4.0 * sum/n;
        return PI;
    }

测试结果：

n = 100 pi = 3.04
n = 1000 pi = 3.204
n = 10000 pi = 3.1464
n = 100000 pi = 3.1378

结果总体来说在提升精度，但也有一定的随机性。n的值越大， $\pi$ 一定程度上越接近真实值。
Kotlin版本：

    fun computePI(n: Int): Double {
        val PI: Double
        var x: Double
        var y: Double
        var i: Int
        var sum = 0
        i = 1
        while (i < n) {
            x = Math.random()
            y = Math.random()
            if (x * x + y * y <= 1) { //在阴影面积内
                sum++
            }
            i++
        }
        PI = 4.0 * sum / n
        return PI
    }

(10) $X^n$ 求解算法

这里介绍两种 $X^n$ 求解算法，也叫幂等算法。先来看第一种，Java版本如下：

/**
     * 幂等运算： O(N)
     */
    public static long pow1(long x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        return x * pow1(x, n - 1);
    }

Kotlin版：

fun pow1(x: Long, n: Int): Long {
        if (n == 0) {
            return 1
        }
        return if (n == 1) {
            x
        } else x * pow1(x, n - 1)
    }

另外一种更高效，Java版如下：

/**
     * 高效的幂等运算 O(log N)
     */
    public static long pow(long x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        if ((n & 1) == 1) { //奇数
            return pow(x * x, n / 2) * x;
        } else {
            return pow(x * x, n / 2);
        }
    }

Kotlin版：

fun pow(x: Long, n: Int): Long {
        if (n == 0) {
            return 1
        }
        if (n == 1) {
            return x
        }
        return if (n and 1 == 1) { //奇数
            pow(x * x, n / 2) * x
        } else {
            pow(x * x, n / 2)
        }
    }

(10)编程实现数学递推公式

用编程实现如下数学递推公式：

C $_n$ = ( 2 / n ) $\sum_{i=0}^{n-1}$ C $_i$ + n ，其中C $_0$ = 1，n = 0, 1, 2, ······ 。

这里使用递归和迭代两种方式来实现。迭代方式其实属于动态规划算法的一种实践。
递归方式的Java版本：

    double eval(int n) {
        if (n == 0) return 1.0;
        else {
            double sum = 0.0;
            for (int i = 0; i < n; i++) {
                sum += eval(i);
            }
            return 2.0 * sum / n + n;
        }
    }

递归方式的Kotlin版本：

    fun eval(n: Int): Double {
        return if (n == 0) 1.0 else {
            var sum = 0.0
            for (i in 0..n-1) {
                sum += eval(i)
            }
            2.0 * sum / n + n
        }
    }

迭代方式的Java版本：

    double eval2(int n) {
        double[] c = new double[n + 1];
        c[0] = 1.0;
        for (int i = 1; i <= n; i++) {
            double sum = 0.0;
            for (int j = 0; j < i; j++) {
                sum += c[j];
            }
            c[i] = 2.0 * sum / i + i;
        }
        return c[n];
    }

迭代方式的Kotlin版本：

    fun eval2(n: Int): Double {
        val c = DoubleArray(n + 1)
        c[0] = 1.0
        for (i in 1..n) {
            var sum = 0.0
            for (j in 0 until i) {
                sum += c[j]
            }
            c[i] = 2.0 * sum / i + i
        }
        return c[n]
    }

Over !

13_经典数学问题算法(Java、Kotlin描述)

(1)素数

(2)欧几里得最大公因数算法

(3)暴力穷举最大公因数算法

(4)分解质因数算法

(5)最大公倍数

(6)非线性方程求解

(7)一维多项式求值

(8)斐波那契数列

(9)圆周率计算

(10) $X^n$ 求解算法

(10)编程实现数学递推公式

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

13_经典数学问题算法(Java、Kotlin描述)

(1)素数

(2)欧几里得最大公因数算法

(3)暴力穷举最大公因数算法

(4)分解质因数算法

(5)最大公倍数

(6)非线性方程求解

(7)一维多项式求值

(8)斐波那契数列

(9)圆周率计算

(10)求解算法

(10)编程实现数学递推公式

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

(10) $X^n$ 求解算法