可能使用最大因子n的k个不同因子进行乘法运算

Question

可能使用最大因子n的k个不同因子进行乘法运算

7

让M(n, k)成为所有具有最大可能因子n、k个不同因子的乘积之和，其中顺序无关紧要。例如，M(5, 3) = 225，因为有10种这样的乘法，它们是1*2*3、1*2*4、1*2*5、1*3*4、1*3*5、1*4*5、2*3*4、2*3*5、2*4*5和3*4*5，它们之和为225。可以轻松地注意到，有C(n,k)这样的乘法，对应于从n个可能对象中选择k个对象的方式数量。在上面的例子中，C(5,3) = 10，确实有这样的10个乘法。

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

我的方法是一个递归算法。类似于上述定义M(n, k)，我定义M(n,j,k)为具有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。

类似的逻辑也可以解释出系数"i"，它在M(n,j+1,k-1)旁边。假设我们现在只有一个因子2。因此我们需要两个更多的因子，所以我们将2乘以接下来的迭代，应该得到： 2*(3*sum(4,5) + 4*sum(5,5)) 然而，由于某种我还不能解释的原因，代码不起作用。它返回错误的值，并且还有“return”问题，导致函数没有返回任何内容，我不知道为什么。

这就是我在这里发布这个问题的原因，希望有人能帮助我。要么通过修复此代码，要么分享他自己的代码。解释我的错误将是最受欢迎的。

提前感谢您，对于这个非常长的问题，表示抱歉， Matan。

-----------------------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;
    }
}

- Matan

double s1 = n/2*(n+1); 这行代码可能存在一个错误。如果 n 等于 1，请检查 s1 的值。 - antonpp

确实是个bug，非常感谢！已经进行了修正和更新，但还没有解决问题。 - Matan

为什么s1和s2被声明为双精度浮点数？你只是想计算两个整数之间的和。 - QBrute

这是为了确保在涉及奇数时也考虑到余数，只是为了谨慎起见。 - Matan

请注意，long n = 5 表示行 double x = n / 2 将使您的 x 值为 2.0 而不是 2.5。 - antonpp

3个回答

2

我不确定你的算法，但你的求和函数肯定出了问题。你的问题与类型转换和整数除法有关。尝试使用类似以下代码：

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 ;
}

- antonpp

2

我看到你得到了答案，我很喜欢你的算法，但我忍不住想发表一个更好的算法。以下是我的想法： M(n,k) = (1+x)(1+2*x)(1+3*x)...(1+n*x)中x^k的系数 你可以通过分治算法解决上述表达式点击此处，从而获得形如ax^n + bx^(n-1)....+c的多项式函数。

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

最棒的部分是，在尝试找到M(n,k)的解时，你将会找到M(n,x)的解，其中1<=x<=n。

希望这对你有用 :)

- pola sai ram

哥们！我刚坐在这等着这个解决方案！递归方案很棒，但当我们需要非常大的值时，递归深度和运行时间会变得太快了。生成函数是一个很好的方法，我现在正在确保理解你的解决方案！非常感激！我真的要感谢你发布这个！非常感谢！@polasairam - Matan

这里其他用户发布的答案是不正确的，只适用于某些情况。因此，我会接受你的答案，因为我知道它确实是正确的。我重写了我的算法并修复了错误，现在使用我的递归方法完美地运行。然而，我无法实现你的方法。你能否编写一个程序来使用你的方法解决它？@polasairam - Matan

尝试使用映射..将幂映射到系数..如果不存在幂..系数将自动为零..明白了吗？试一试吧。 - pola sai ram

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- yahya el fakir · Accepted Answer

您的求和函数存在问题：以下是正确的公式：

public static long sum (long i, long n)
    {
        double s1 = n*(n+1)/2;
        double s2 = i*(i-1)/2;
        return (long)(s1-s2);
    }

这是完整的解决方案：

    static int n = 5; 
    static long k = 3;
// no need to add n and k them inside your M function cause they are fixed.
    public static long M (long start) // start = 1
    {
        if(start > k) // if start is superior to k : like your example going from 1..3 , then you return 0
            return 0;
        int res = 0; // res of your function
        for(long i=start+1;i<n;i++){
            res+=start*i*sum(i+1,n); // here you take for example 1*2*sum(3,5) + 1*3*sum(4,5).... ect

        }

        return res+M(start+1); // return res and start again from start+1 wich would be 2.

    }
    public static long sum (long i, long n)
    {
        if(i>n)
            return 0;
        double s1 = n*(n+1)/2;
        double s2 = i*(i-1)/2;
        return (long)(s1-s2);
    }
    public static void main(String[] args) {
        System.out.println(M(1));
    }

希望您能从中受益。