algorithm - n 算法的基 b 扩展

Question

我正在阅读关于n算法的base b扩展，这本书真的很难阅读和理解，我不确定底部是什么意思......

它返回 n 还是什么？你会怎么做...谢谢

some method (n,b)
if b == 0
    return 1
q = n
k = 0
while q does not == 0
    a[k] = q % b
    q = q / b
    k = k + 1
    return ???

Answer 1

我用 C 语言为这个函数编写了一个实现。它使用指针作为输入参数，输出（整数向量）将被放置在其中。该函数还返回一个整数——向量的逻辑大小。

#include <assert.h>

int toBase(int n, int b, int* answer) {
    assert(b > 1);
    q = n
    k = 0
    while (q != 0) {
        answer[k] = q % b;
        q /= b;
        ++k;
    }
    return k;
}

int main() {
    int answer[32];
    int n = 100000;
    int b = 2;
    int answerSize = toBase(n, b, answer);

    // use answer and answerSize

    return 0;
}

另一种方法（没有指针参数）是在函数内部为向量分配内存并返回它，要求调用函数在完成处理后释放使用的内存。

在这种情况下，您无法判断向量的逻辑大小，因此您必须将 answer[k] 设置为一个特殊值（此处为 -1），以了解向量的结束位置。

#include <assert.h>

int* toBase(int n, int b) {
    assert(b > 1);
    int* answer = malloc(33 * sizeof(int));
    q = n
    k = 0
    while (q != 0) {
        answer[k] = q % b;
        q /= b;
        ++k;
    }
    answer[k] = -1;
    return answer;
}

int main() {
    int n = 100000;
    int b = 2;
    int *answer = toBase(n, b);

    // use answer

    free(answer);
    return 0;
}

一个更优雅的解决方案（在 C++ 中）是使用 STL 向量类。

Answer 2

这个算法背后的想法是它创建一个值列表 a _k， a _k-1， a _k-2，...， a ₀。最后，它希望返回该值列表，并以类似于数字的 base-b 表示的形式返回。

例如，如果你在这个算法中输入 33 并要求它的 base-16 表示，算法将设置₁ = 2 和₀ = 1。算法的返回值是表示 21，即₁ ( 2) 后跟一个₀ (1)。

他们使用的符号只是花哨的数学语言，用于“返回此算法产生的值列表”。您可以将其视为返回数字的以 b 为基数的数组。

希望这可以帮助！