1

我很难将函数从递归转换为使用 MPIR 库变量“mpz_t”而不是“unsigned __int64”的非递归函数。我也在尝试思考我应该如何编写循环。当我使它递归时，这很容易，但是当我尝试使它成为非递归时，就很难了！

unsigned __int64 exampleFunc( unsigned __int64 a,
                              unsigned __int64 b,
                              unsigned __int64 c )
{
    if( a <= 2 )
        return a + 1;
    if( b <= 4 )
        return b;
    if( c == 3 )
        return c - 1;
    if( b == 5 )
        c += 2;
    // How will I put these into a loop?
    return exampleFunc( a - 1, b - 2, c ) + exampleFunc( 0, b + 1, c - 1 );
};

部分问题是我们不能编写返回 mpz_t 值的函数。我们只能向它写入一个值（如指针）。所以，这样的事情是行不通的：

mpz_t exampleFunc( ... );

这意味着，这样的事情可以工作：

void exampleFunc( mpz_t out, ... );

甚至是全局变量（不强烈推荐）：

mpz_t g_out;
mpz_init( g_out );
void exampleFunc( ... ) { g_out = ? };

笔记：

我们应该尽量不要使用数组甚至向量，因为这些数字会非常非常大——这解释了为什么我要从 unsigned __int64 切换到 mpz_t。除非我们真的必须...

请帮忙，我真的很紧张。谢谢。

4

2 回答 2

1

关于 gmp 的问题：尝试使用 gmpxx.h - 您可以mpz_class像返回整数一样返回对象。

mpz_class withgmp( const mpz_class &a, const mpz_class &b, mpz_class c )
{
    if( a <= 2 )
        return a + 1;
    if( b <= 4 )
        return b;
    if( c == 3 )
        return c - 1;
    if( b == 5 )
        c += 2;
    return withgmp( a - 1, b - 2, c ) + withgmp( 0, b + 1, c - 1 );
}

请注意，我c按值传递，因为它可能在函数中被修改。

或者，如果您必须使用纯 C，您应该为结果传递第四个参数，如下所示：

void withmpz( mpz_t a, mpz_t b, mpz_t c, mpz_t result)
{
     // ... leaving out the boundary conditions
     mpz_t left; mpz_init(left);
     // ... leaving out code for adjusting a,b and c
     withmpz(a,b,c, left);
     mpz_t rightt; mpz_init(right);
     // ... leaving out code for adjusting a,b and c
     withmpz(a,b,c, right);
     mpz_add(result, left, right);
}

注意 mpz_t 看起来好像是按值传递，但实际上它总是按引用传递，所以调用后 a,b,c 会发生变化withmpz

您问题的第二部分，如何将其转换为迭代，确实更困难。一种方法是将其更改为基于堆栈的算法，其中每个迭代步骤将堆栈顶部替换为需要添加的 2 个值，直到可以立即计算一个，然后将其添加到最终结果中，重复此操作直到你的堆栈上没有更多的值。

于 2013-03-19T10:54:06.423 回答
0

指向指针的指针可能是解决方案：您通过值将指针传递给指针并根据需要修改指针及其指向的数据

于 2013-03-19T10:01:13.697 回答