在 C 中计算嵌套根

Question

我被要求仅使用递归计算以下嵌套根表达式。

我写了下面的代码，但它们允许我们只使用一个函数和 1 个输入n，而不是像我使用的那样使用 2 个。有人能帮我把这段代码转换成一个可以计算表达式的函数吗？不能使用任何库，除了来自<math.h>.

n=10 时的输出： 1.757932

double rec_sqrt_series(int n, int m) {
    if (n <= 0)
        return 0;
    if (m > n)
        return 0;
    return sqrt(m + rec_sqrt_series(n, m + 1));
}

double helper(int n) {
    return rec_sqrt_series(n, 1);
}

Answer 1

使用 的高位n作为计数器：

double rec_sqrt_series(int n)
{
    static const int R = 0x10000;
    return n/R < n%R ? sqrt(n/R+1 + rec_sqrt_series(n+R)) : 0;
}

当然，当初始n值为R或更大时，它会出现故障。这是一个更复杂的版本，适用于 的任何正值n。有用：

• 当n为负时，它的工作方式与上述版本类似，使用高位计数。
• 当n为正时，如果小于R，则调用自身 with-n来评估上述函数。否则，它用R-1否定来调用自己。这会评估函数，就像它是用 调用的一样R-1。这会产生正确的结果，因为在仅仅几十次迭代后，该系列就停止以浮点格式变化——更深的数字的平方根变得如此稀薄，以至于没有任何影响。因此，该函数在所有n小阈值上都具有相同的值。

double rec_sqrt_series(int n)
{
    static const int R = 0x100;
    return
        0 < n ? n < R ? rec_sqrt_series(-n) : rec_sqrt_series(1-R)
              : n/R > n%R ? sqrt(-n/R+1 + rec_sqrt_series(n-R)) : 0;
}

Answer 2

这个问题需要扭曲的解决方案。

这是一个使用带有一两个int参数的单个函数的函数：

• 如果第一个参数为正，则计算该值的表达式
• 如果第一个参数为负，则必须紧跟第二个参数，并在计算中执行单个步骤，递归上一步。
• 它使用<stdarg.h>可能或可能不允许的内容。

这是代码：

#include <math.h>
#include <stdarg.h>

double rec_sqrt_series(int n, ...) {
    if (n < 0) {
        va_arg ap;
        va_start(ap, n);
        int m = va_arg(ap, int);
        va_end(ap);
        if (m > -n) {
            return 0.0;
        } else {
            return sqrt(m + rec_sqrt_series(n, m + 1));
        }
    } else {
        return rec_sqrt_series(-n, 1);
    }
}

这是另一个具有单个函数的解决方案，仅使用<math.h>，但以不同的方式滥用规则：使用宏。

#include <math.h>
#include <stdarg.h>

double rec_sqrt_series(int n, ...) {
    if (n < 0) {
        va_arg ap;
        va_start(ap, n);
        int m = va_arg(ap, int);
        va_end(ap);
        if (m > -n) {
            return 0.0;
        } else {
            return sqrt(m + rec_sqrt_series(n, m + 1));
        }
    } else {
        return rec_sqrt_series(-n, 1);
    }
}

还有一个，严格来说是 recursive，但只有一个递归级别，没有其他技巧。正如Eric评论的那样，它使用了一个for在 OP 的约束下可能无效的循环：

double rec_sqrt_series(int n) {
    if (n > 0) {
        return rec_sqrt_series(-n);
    } else {
        double x = 0.0;
        for (int i = -n; i > 0; i--) {
            x = sqrt(i + x);
        }
        return x;
    }
}

Answer 3

如果不对公式进行数学转换（我不知道是否可行），您不能真正只使用一个参数，因为对于每个元素，您需要两个信息：当前步骤和原始n. 但是你可以作弊。一种方法是对int参数中的两个数字进行编码（如Eric所示）。

另一种方法是将原始文件存储n在静态局部变量中。在我们保存n在这个静态变量中的第一次调用中，我们开始递归，并在最后一步将其重置为哨兵值：

// fn(i) = sqrt(n + 1 - i + fn(i - 1))
// fn(1) = sqrt(n)
//
// note: has global state
double f(int i)
{
    static const int sentinel = -1;
    static int n = sentinel;

    // outside call
    if (n == sentinel)
    {
        n = i;
        return f(n);
    }

    // last step
    if (i == 1)
    {
        double r = sqrt(n);
        n = sentinel;
        return r;
    }

    return sqrt(n + 1 - i + f(i - 1));
}

显然static int n = sentinel不是标准的 C，因为sentinel它不是C 中的编译时常量（这很奇怪，因为 gcc 和 clang 都不会抱怨，即使有-pedantic）

你可以这样做：

enum Special { Sentinel = -1 };
static int n = Sentinel;