让 M(n,k) 是 总和 所有可能的 乘法的 k 独特 与 的因素最大可能的因素 , 其中 订单无关 .
例如, M(5,3) = 225 , 因为:
6+8+10+12+15+20+24+30+40+60 = 225。
人们很容易注意到有 C(n,k) 这样的乘法,对应于可以选择的方式数 k 对象外 可能的对象。在上面的例子中, C(5,3) = 10 确实有 10 个这样的乘法,如上所述。
问题也可以尽量形象化 n 尺寸 完全包含 的集合k 0 ,其中每个不包含 0 的单元格的值是 索引+1 在里面。例如,一种可能的此类集合是 {0,2,3,0,5}。 从这里开始,需要将集合中不为 0 的值相乘。
我的方法是递归算法。类似于上面的定义
M(n,k), 我定义 M(n,j,k) 是的所有可能乘法的总和k 具有最大可能因子的不同因子 , 和最小的 可能的因素 j .因此,如果继续运行,我的方法将产生所需的值
M(n,1,k)。 所以我开始我的递归 M(n,1,k), 使用以下代码,用 Java 编写:
public static long M (long n, long j, long k)
{
if (k==1)
return usefulFunctions.sum(j, n);
for (long i=j;i<=n-k+1+1;i++)
return i*M(n,i+1,k-1);
}
代码说明:
例如,以 开头n=5, j=1, k=3 ,只要我们需要更多的因子,算法就会继续运行, (k>=1), 由于 for 循环,它确保只运行不同的因子,这增加了最小可能值 j 随着更多因素的加入。循环运行并减少“添加”所需因子的数量,这是通过应用实现的
M(n,j+1,k-1)。 j+1 确保因子将是不同的,因为因子的最小值增加,并且 k-1 表示我们需要少 1 个因子来添加。
函数 '总和(j,n)'返回从 开始的所有数字之和的值j 直到 , 所以 总和(1,10)=55 .这是通过一个正确、优雅和简单的数学公式完成的,没有循环: sum(j,n) = (n+1)*n/2 - (i-1)*i/2
public static long sum (long i, long n)
{
final long s1 = n * (n + 1) / 2;
final long s2 = i * (i - 1) / 2;
return s1 - s2 ;
}
在 时应用此金额的原因k=1 ,我用一个例子来解释:
假设我们从 1*2 开始。现在我们需要第三个因子,它可以是 3、4、5 中的任何一个。因为所有的乘法:1*2*3, 1*2*4, 1*2*5 都是有效的,我们可以返回 1*2*(3+4+5) = 1*2*sum(3,5) = 24 .
类似逻辑解释系数 “我”旁边 M(n,j+1,k-1)。
假设我们现在有唯一的因子 2。因此我们还需要 2 个因子,所以我们将 2 乘以下一次迭代,这应该导致:
2*(3*sum(4,5) + 4*sum(5,5))
但是,由于我还无法解释的原因,代码不起作用。它返回错误的值并且还有导致函数不返回任何内容的“返回”问题,不知道为什么。
这就是我在这里发布这个问题的原因,希望有人能帮助我。通过修复此代码或共享他自己的代码。解释我哪里出错将是最可观的。
非常感谢提前,很抱歉这个很长的问题,
马坦。
-----------------------EDIT------------------------
下面是我的固定代码,它解决了这个问题。发布它以防万一有人需要它:) 玩得开心!
public static long M(long n, long j, long k)
{
if (k == 0)
return 0;
if (k == 1)
return sum(j,n);
else
{
long summation = 0;
for (long i=j; i<=n; i++)
summation += i*M(n, i+1, k-1);
return summation;
}
}
最佳答案
我不确定你的算法,但你肯定搞砸了你的 sum 函数。您遇到的问题与整数的类型转换和除法有关。尝试这样的事情:
public static long sum (long i, long n)
{
final long s1 = n * (n + 1) / 2;
final long s2 = (i * i - i) / 2;
return s1 - s2 ;
}
关于java - k 个不同因子与最大可能因子 n 的可能乘法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30125765/