当 xˣ = N 时求 x 值的递归程序

Question

当x^x = N时，我需要求x的值，N是输入的值。假设 N 为 27。在此示例中，x 值为 3，因为 27 的立方根为 3，即 3³ = 27。如果 N 为 256，则 x 将为4、由于4⁴ = 256.

我需要找出一个计算出 x 值的递归程序。这是我目前所拥有的：

public static void main(String[] args) {
    
    Scanner n = new Scanner(System.in);

    System.out.println("Enter a number");
    double number = n.nextDouble();


}

public static void findXValue(double n) {

    double logn = Math.log(n);
...

findXValue功能使用了日志，但也不起作用。而且我还需要使用递归方法。任何帮助将不胜感激

Answer 1

    public static double findXValue(double n) {
        double result = 0.0;
        double number = 0.0;
        while(result <= n) {
            result = Math.pow(number, number);
            if(result == n) {
                return number;
            }

            number++;
        }

        return -1;
    }

Answer 2

我假设 x 可以是浮点数，因为你没有说。

您可以将此视为求函数 F(x) = x^x - N 的根的问题。最简单的方法称为二分法，它可以工作像二进制搜索。

从区间 [a, b] 开始，使得 F(a) 和 F(b) 的符号相反。对于这个问题，由于函数的性质，它总是 F(a)<0 和 F(b)>0。如果 N > 1，则从 [1,N] 开始。如果 0 <= N < 1，则使用 [N,1]。（如果 N = 1，则 x = 1）。

之后，迭代。计算 x = (a+b)/2。如果 F(x) 和 F(a) 同号（负），则设 a=x。否则 F(x) 必须与 F(b) 具有相同的符号（正数），因此设置 b=x.

当a和b最多相差一个unit-of-least-precision（可能的最小浮点差）时，停止并return a.

这种迭代很容易表示为递归。我不会给你答案。

double solve(double a, double b, double n) {
  if (b - a <= ULP) return a;

  // all the fun happens here
}

同样的技术也适用于整数，但在计算中点时要注意溢出和舍入错误。

Answer 3

使用Newton's method求根。

import java.util.Scanner;

public class XPowerX {
    static final double PRECISION = 0.00001;
    static final int MAX_RECURSION = 10000;

    public static void main(String[] args) {

        Scanner n = new Scanner(System.in);

        System.out.println("Enter a number");
        double number = n.nextDouble();

        System.out.println(findXValue(number));
    }

    public static double findXValue(double n) {
        double seed = Math.random();
        double y = Math.pow(seed, seed);
        double derivative;
        for(int i = 0; i < MAX_RECURSION; i++) {
            if (Math.abs(y) <= PRECISION) {
                return seed;
            }

            y = Math.pow(seed, seed);
            derivative = y * Math.log(seed) + y;
            y -= n;
            // The derivative is used as the slope of tangent line

            // Newton's method
            seed = seed - y / derivative;

            if(seed < 0) {
                seed = 0;
            }
        }
        return -1;
    }
}

输出：

Enter a number
16
2.7453680235674636

Enter a number
0.8
0.7395336501071896

Enter a number // No real root
0.3
-1.0

Enter a number // Overflow (NaN)
125000
-1.0

当 xˣ = N 时求 x 值的递归程序

Recursive program to find the value of x when xˣ = N

java

math

recursion

input

function