1

我正在编写一个 C 程序来计算 Pascular Triangle 中的第 (i,j) 个元素，即 f(n,1) = f(n,n) = n 和 f(n,k) = f(n-1,k ) + f(n-1,k-1) for 1 < k < n 我需要打印模 1000000007 的值。代码如下：

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

unsigned long int returnModPascal(unsigned long int n,unsigned long int k);

int main()
{
    int t;
    unsigned long int ans,n,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lu %lu",&n,&k);
        ans=returnModPascal(n,k);
        printf("%lu",ans);
    }

    return 0;
}

unsigned long int returnModPascal(unsigned long int n,unsigned long int k)
{
    unsigned long int tempans,tempans1,tempans2;
    if(k==1 || k==n)
        tempans=n;
    else
    {
        tempans1=returnModPascal(n-1,k);
        if (tempans1>=1000000007)
            tempans1=tempans1%1000000007;
        tempans2=returnModPascal(n-1,k-1);
        if (tempans2>=1000000007)
            tempans2=tempans2%1000000007;
        if (tempans1+tempans2>=1000000007)
            tempans=tempans1+tempans2-1000000007;
        else
            tempans=tempans1+tempans2;
    }

    return tempans;
}

当我将输入例如 123456 3 作为 n & k 时（它适用于较小的整数值，如 23 2 或 12 3 作为 n&k）错误来了

DummyProject.exe 中 0x003C3D79 处的未处理异常：0xC00000FD：堆栈溢出（参数：0x00000001、0x003D2F70）。

任何帮助表示赞赏。

4

3 回答 3

1

由于您使returnModPascal函数递归，因此每次递归调用的堆栈上都必须有空间。

例如，如果您读入123456，您对 的调用returnModPascal最终将为n = 123456、n = 123455、n = 123454等分配一个堆栈帧。几乎没有足够的内存。

为了解决这个问题，你将不得不重写你的函数，这样你最终就不会对更大的输入进行这么多的递归调用。

于 2013-09-28T00:00:18.033 回答
1

典型的堆栈限制为大约 1000 KB。在linux中你可以使用

ulimit -a

了解你的（我的大约 8 MB）。由于 unsigned long int 可以达到（再次假设 gcc）18446744073709551615（64 位）或 4294967295（32 位）[我可能错了，请参阅您的 limits.h]，并且您的一个堆栈帧的大小必须为 2 个字，堆栈溢出迫在眉睫。

编辑：我看到你想要一个替代方案。您是否考虑过使用组合学？通过i C j “计算”第 (i,j) 个条目。我的意思是实际上并没有找到阶乘和乘法，而是取消所有可以的项（整数值总是会出现），直到只剩下一个整数序列（数学意义上）。使用模乘法（mod 1000000007）。阅读有关使用生成器指数的高效模乘法。

于 2013-09-28T00:14:16.173 回答
0

看这行代码：

tempans1=returnModPascal(n-1,k);

您在一开始就调用递归函数，这意味着该函数将一直运行到递归链的最后，然后才有机会进一步处理输入。因此，如果您使用相对较大的输入（例如 ）调用此函数123456，这意味着该函数必须“堆叠”12345 次才能最终评估if条件。

if您应该尝试减少输入，或者更好的选择是在语句之​​后递归调用函数。

于 2013-09-28T00:01:03.093 回答