阶乘作为连续数的总和

Question

我最近在解决一个问题"No. of ways to express factorial of a number as sum of consecutive number" 我的解决方案是：

int fact_as_sum(int n) {  // n is the number whose factorial need to be taken
    long int fact=1;
    int temp=0,count=0;

    for(int i=n;i>0;i--){
        fact*=i;
    }

    printf("%d\n",fact);
    for(int i=fact/2;i>0;i--) {
        int j=i;
        temp=fact;
        while(temp>=0) {
            if(temp==0) {
                count++;
                break;
            }
            else
                temp-=j;
            j--;
        }
    }

    return count;    
}

该解决方案一直有效，直到小号。共 10 个！

但是我的解决方案非常复杂。谁能提出一个不太复杂的解决方案？

谢谢

Answer 1

当然可以。我可能会尝试提供一个更简单的解决方案来查找计数：replace

        temp = fact;
        while(temp>=0) {
            if(temp==0) {
                count++;
                break;
            }
            else
                temp-=j;
            j--;
        }

来自

        if ( fact % j == 0 )
            count++;

。这也意味着您不需要 temp，因为您可以使用余数运算符 (%) 来检查 j 是否是除数（这就是您当时尝试做的事情）循环，对吧？）。

Answer 2

首先，您的代码有一个错误。
1.需要将for循环中的i=fact/2改为i=(fact+1)/2;
2.需要在while循环中加入j > 0条件，防止死循环。因为例如 temp-(-1) 将递增 temp.

固定码：

for(long int i=(fact+1)/2; i>0; i--) {
    long int j=i;
    temp=fact;
    while(j > 0 && temp > 0) {
        temp-=j;
        j--;

        if(temp == 0) {
            count++;
            break;
        }
    }
}

根据你的问题，可以在O(sqrt(2*N))时间内完成。这里有一些可以理解的、干净的答案：

long int count = 0;
for (long int L = 1; L * (L + 1) < 2 * fact; L++) {
    float a = (1.0 * fact-(L * (L + 1)) / 2) / (L + 1);
    if (a-(int)a == 0.0) 
        count++;        
}

Answer 3

好吧，这个问题让我很头疼，所以首先要感谢你，我喜欢解决这类问题！为了找到最佳实施方案，我开始对问题进行数学分析，并想出了这个解决方案：

通过将n定义为阶乘结果数，m要执行的求和数和x加法的起始数，全部分解为以下公式：

.

现在可以对此进行简化，得到以下公式：

.

这也可以简化，得到以下结果：

.

求解 x（加法的起始数），结果为：

.

现在可以迭代 m 的所有值来找到想要的 x 值。 m的下界肯定是0，不可能加负数！可以通过注意 x 应该是正数来找到上界，考虑将被相应正数部分抵消的负值是没有意义的！这给出了以下结果：

这会产生以下结果：

如前所述，m的负值被丢弃

转换为以下 C 代码：

#include <stdio.h>
#include <math.h>

void main() {
    int fact = 8;  //select the wanted factorial to compute
    float n = 1;
    int i;
    float x;
    float m;

    printf("calculating %d factorial...\n", fact);

    for (i = 2; i < fact + 1; i++) {
        n *= (float)i;
    }

    printf("the factorial result is %d\n", (int)n);
    printf("calculating the sum of consecutive numbers...\n");

    //compute the maximum number of iterations
    int maxIter = (int)((-1 + sqrt(1 + 8 * n)) / 2);

    for (i = 0; i < maxIter; i++) {
        m = (float)i;
        //apply the formula
        x = (n / (m + 1)) - (m / 2);
        if (x - (float)((int)x) == 0) {
            printf("found a correct sum!\n");
            printf("the starting number is: %d\n", (int)x);
            printf("the number of sums is: %d\n", i + 1);
        }
    }
}

我已经在几个值上尝试了这个解决方案并编写了测试代码，结果似乎是正确的。但是阶乘有一个问题，因为阶乘很快达到非常高的值，内存需要更好地管理。

希望我给出了一个有趣的解决方案，我解决得很开心！

如果此解决方案存在问题，请更正。

阶乘作为连续数的总和

Factorial as a sum of consecutive number

c

factorial