如何将一个数字写成其他数字的幂之和

Question

好的，首先我很抱歉我知道我不够聪明。我数学不好。

这道题我写不出算法。

系统给了我们 int x, int y, int boundary 并希望我们找到边界上的哪些数字满足规则

   some_number = x^i + y^j

   Boundary <= 10^6
   i and j > = 0 
   x and y < 100

例如 x = 2，y = 3 和边界 = 5，

       2 = 2^0 + 3^0
       3 = 2^1 + 3^0
       4 = 2^0 + 3^1
       5 = 2^1 + 3^1

输出：2,3,4,5

import java.util.ArrayList;

public class Main {
 public static ArrayList<Integer> find_numbers(int x, int y, int boundary) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        int num = 0;
        int remain_x = 0, remain_y = 0;
        int count_x = 0, count_y = 0;
        if (boundary >= 2) {
            res.add(2);
        }
        for (int i = 3; i <= boundary; ++i) {
            if(i == x+y)
                res.add(i);
            count_x = 0;
            count_y = 0;
            num = i;
            while (num > 0) {
                remain_x = num % x;
                if (remain_x == 0) {
                    count_x++;
                } else {
                    while (num > 0) {
                        remain_y = num % y;
                        if (remain_y == 0) {
                            count_y++;
                        }
                        num = num / y;
                    }
                }
                num = num / x;
            }
            System.out.println("i =>" +i);
            System.out.println("x=>" + count_x);
            System.out.println("y =>" + count_y);
        }

        return res;
    }


    public static void main(String[] args) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        int x = 1 + (int) (Math.random() * 100);
        int y = 1 + (int) (Math.random() * 100);
        int boundary = 1 + (int) (Math.random() * 1000000);
        res = find_numbers(x, y, boundary );
        System.out.println(res);
    }
}

编辑：看完鲨鱼的评论后我写了一些东西，非常感谢。它正在工作。

import java.util.ArrayList;

public class Main {

    public static ArrayList<Integer> find_numbers(int x, int y, int boundary) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        int x_k = 0;
        int y_k= 0;
       while(Math.pow(x,x_k)< boundary){
           x_k++;
       }
        while(Math.pow(y,y_k)< boundary){
            y_k++;
        }
        for(int k = 2 ; k<= boundary;++k) {
            for (int i = 0; i < x_k; ++i) {
                for (int j = 0; j < y_k; ++j) {
                    if(k == (int)Math.pow(x,i)+(int)Math.pow(y,j) && !res.contains(k)){
                        System.out.println("----------------------------------------");
                        System.out.println(k +" =>" +x + "^" +i +"+"+y+ "^" +j);
                        res.add(k);
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        int x = 1 + (int) (Math.random() * 100);
        int y = 1 + (int) (Math.random() * 100);
        int boundary = 1 + (int) (Math.random() * 1000000);
        res = find_numbers(x,  y,boundary);
        System.out.println("x:" + x);
        System.out.println("y:" + y);
        System.out.println("boundary:" + boundary);
        System.out.println("Result:" + res);
    }
}

Answer 1

我不确定这是否是最有效的方法。基本上，我递增 j 直到 x^i + y^j > boundary 然后递增 i.

    public static ArrayList<Integer> findNumbers(int x, int y, int boundary) {
        Set<Integer> result = new HashSet<>(); // make sure result is unique
        int powerX = 0, powerY = 0, total = 0, tempX = 0;
        while (true) {
            // calculate x^i
            tempX = (int) Math.pow(x, powerX);
            while (true) {
                // calculate x^i + y^j and compare against boundary
                if ((total = tempX + (int) Math.pow(y, powerY)) <= boundary) {
                    // add result to set and increment y
                    result.add(total);
                    powerY++;
                    // break if y <= 1
                    if (y <= 1)
                        break;
                } else
                    break;
            }
            // break if x <= 1 || x^i > boundary
            if (tempX > boundary || x <= 1)
                break;
            // reset j and increment i
            powerY = 0;
            powerX++;
        }
        // return sorted result
        ArrayList<Integer> arr = new ArrayList<>();
        arr.addAll(result);
        arr.sort(null);
        return arr;
    }

您可以重构代码以提高效率。

Answer 2


public class Main {

    public static ArrayList<Integer> find_numbers(int x, int y, int boundary) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        int x_k = 0;
        int y_k= 0;
       while(Math.pow(x,x_k)< boundary){
           x_k++;
       }
        while(Math.pow(y,y_k)< boundary){
            y_k++;
        }
        for(int k = 2 ; k<= boundary;++k) {
            for (int i = 0; i < x_k; ++i) {
                for (int j = 0; j < y_k; ++j) {
                    if(k == (int)Math.pow(x,i)+(int)Math.pow(y,j) && !res.contains(k)){
                        System.out.println("----------------------------------------");
                        System.out.println(k +" =>" +x + "^" +i +"+"+y+ "^" +j);
                        res.add(k);
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        int x = 1 + (int) (Math.random() * 100);
        int y = 1 + (int) (Math.random() * 100);
        int boundary = 1 + (int) (Math.random() * 1000000);
        res = find_numbers(x,  y,boundary);
        System.out.println("x:" + x);
        System.out.println("y:" + y);
        System.out.println("boundary:" + boundary);
        System.out.println("Result:" + res);
    }
}

如何将一个数字写成其他数字的幂之和

How to write a number as sum of some other numbers' power

java

arraylist