c - 这是一个 C 程序，用于计算 k 从 0 到 n 的总和：nCk。我遇到了分段错误

Question

1. 变量 test 是后面的测试用例的数量
2. 函数 factorial 返回数字的阶乘
3. 函数 summ 给出 k 从 1 到 n nCk 的总和

这是我的代码：

#include<stdio.h>
float factorial(int x)
{
    if(x==1)
    return 1.0;
    else
    return (x*factorial(x-1));
}
int summ(int y)
{
    int k=1;double sum=0;int r;
    while(k<=y)
    {
        sum=sum +((factorial(y))/(factorial(y-k)*factorial(k)));
        k++;
    }
    r=(int)sum%(int)((1000000007.00));
    return r;
}
main()
{
    int test;
    scanf("%d",&test);int j=0;
    int i=0;int arr[test];int val;int flag;
    while(i<test)
    {
        scanf("%d",&val);
        flag=summ(val);
        arr[i]=flag;
    i++;
    }
    while(j<test)
    {
        printf("%d\n",arr[j] );
        j++;
    }
    return 0;
}

Answer 1

作为提示，请查看二项式定理，它说

(n 选择 0) + (n 选择 1) + ... + (n 选择 n) = 2 ⁿ

这可以使用位移在单行代码中计算出来。

希望这可以帮助！

Answer 2

(nC1 + nC2 + nC3...nCn) = 2^n - 1 使用二项式定理

2^n 可以使用快速求幂在 O(logn) 中计算

快速求幂

Answer 3

在阶乘函数中 Do if(n==1||n==0) return 1; ......

Answer 4

要修复您的程序，请注意 when x = 0，您的函数factorial将崩溃，因为递归从 0 到 -1、到 -2、到 -3 等。检查您的summ函数，然后您可以发现何时调用k = y, 。factorial(0)

但是，要以有效的方式解决您的问题，而不是仅仅修复您的程序，您应该参考templatetypedef的想法。