具有最大可能因子n的k个不同因子的可能乘法

Question

设M(n,k)是具有最大可能因子n的k个不同因子的所有可能乘法的总和,其中顺序是无关的.

例如,M(5,3)= 225,因为:

• 1*2*3 = 6
• 1*2*4 = 8
• 1*2*5 = 10
• 1*3*4 = 12
• 1*3*5 = 15
• 1*4*5 = 20
• 2*3*4 = 24
• 2*3*5 = 30
• 2*4*5 = 40
• 3*4*5 = 60

6 + 8 + 10 + 12 + 15 + 20 + 24 + 30 + 40 + 60 = 225.

人们可以很容易地注意到存在C(n,k)这样的乘法,对应于可以从n个可能对象中挑选k个对象的方式的数量.在上面的例子中,C(5,3)= 10,并且确实存在10次这样的乘法,如上所述.

这个问题也可以被视为可能的n个大小的集合,其中包含正好的k 0,其中每个不包含0的单元格,其内部的索引值为+ 1.例如,一个可能的这样的集合是{0,2,3,0,5}.从这里开始,需要将集合中不同于0的值相乘.

我的方法是递归算法.Similiarly到的上述定义 M(N,K),我定义M(N,J,K)是准确的所有可能的乘法的总和ķ不同因素与最大可能的因素Ñ,的和最小可能的因素Ĵ.因此,如果在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个因子的补充.

函数'sum(j,n)'返回从j开始的所有数字之和的值,直到n,因此sum(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)旁边的系数"i" . 说我们现在有唯一的因素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;
    }
}

Answer 1

我看到你得到了答案，我真的很喜欢你的算法，但我无法控制自己发布更好的算法。这是这个想法

M(n,k) = coefficient of x^k in (1+x)(1+2*x)(1+3*x)...(1+n*x)

您可以通过分而治之算法来解决上述表达式单击此处了解如何将上述表达式相乘并得到以下形式的多项式函数ax^n + bx^(n-1)....+c

整体算法时间复杂度为 O(n * log^2 n)

上述算法最好的部分是

in the attempt of finding solution for M(n,k) , u will find solution for M(n,x) where 1<=x<=n

我希望了解一下会有用:)