有个算法题here关于 n 次幂的总和,我尝试使用递归来解决问题,但在我在线检查解决方案之前它不起作用,我得到了这个:
public class Main {
public static void main(String[] args){
Scanner s = new Scanner(System.in);
int x = s.nextInt(), n = s.nextInt();
int end = (int)Math.pow(x, 1.0/n);
System.out.print(sumOfPower(x, n, end));
}
static int sumOfPower(int number, int power, int end) {
int[] temp = new int[number + 1];
temp[0] = 1;
for(int i = 1; i <= end; i++) {
int value = (int)Math.pow(i, power);
for(int j = number; j > value - 1; j--) {
temp[j] += temp[j-value];
}
}
return temp[number];
}
我试图通过在每个循环中记录结果来研究代码,所以 sumOfPower
方法现在看起来像这样:
static int sumOfPower(int number, int power, int end) {
int[] temp = new int[number + 1];
temp[0] = 1;
for(int i = 1; i <= end; i++) {
int value = (int)Math.pow(i, power);
for(int j = number; j > value - 1; j--) {
System.out.println( "j:"+j+"\tj-value:"+(j-value)+ "\ttemp[j]:" + temp[j] + "\ttemp[j-value]:" + temp[j-value] );
temp[j] += temp[j-value];
System.out.println(i + ": " + Arrays.toString(temp));
}
}
return temp[number];
}
我了解循环和动态编程逻辑在某种程度上如何与我使用 x=10
和 n=2
的日志一起工作。日志看起来像:
10
2
j:10 j-value:9 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:9 j-value:8 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:8 j-value:7 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:7 j-value:6 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:6 j-value:5 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:5 j-value:4 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:4 j-value:3 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:3 j-value:2 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:2 j-value:1 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:1 j-value:0 temp[j]:0 temp[j-value]:1
1: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:10 j-value:6 temp[j]:0 temp[j-value]:0
2: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:9 j-value:5 temp[j]:0 temp[j-value]:0
2: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:8 j-value:4 temp[j]:0 temp[j-value]:0
2: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:7 j-value:3 temp[j]:0 temp[j-value]:0
2: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:6 j-value:2 temp[j]:0 temp[j-value]:0
2: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:5 j-value:1 temp[j]:0 temp[j-value]:1
2: [1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0]
j:4 j-value:0 temp[j]:0 temp[j-value]:1
2: [1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0]
j:10 j-value:1 temp[j]:0 temp[j-value]:1
3: [1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1]
j:9 j-value:0 temp[j]:0 temp[j-value]:1
3: [1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1]
我目前需要知道的是这背后的数学逻辑,我怎么知道循环后 temp['number']
是可能的总路数 x
可以表示为唯一自然数的 n 次
次幂之和。非常感谢任何帮助。
最佳答案
让我们从问题的抽象模型开始,给出一个 DAG directed acyclic graph , 从一个节点到另一个节点有多少种方式?
让我们调用函数来回答这个问题是f(start, end)
我们很容易看出
f(start, end) = sum f(x , end) with x are the neighbours of start
对于基本案例 f(end, end) = 1
(有一种从头到尾的方式,因为这个图没有循环)。而且,由于这是一个 DAG,所以上述函数会收敛。
类似地,你可以看到同样的模型可以应用到这个问题上。
假设我们需要计算 f(X, 0)
其中X是初始值,我们可以看到从X值可以达到所有值X - y
, 与 y
是N次方数。
所以
f(X, 0) = sum f(X - y, 0) with y is all Nth power number less than or equal X
f(0,0) = 1
在您提供的代码中,temp
正在存储 f
的答案来自 f(0, 0) to f(value, 0)
.
那么,为什么这是 DAG?因为 N 次方的值为正,所以我们无法回到之前的状态。
关于java - 求和算法的幂,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47791542/