algorithm - n 算法的基 b 扩展

Question

我正在阅读 n 算法的基 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 向量类。