algorithm - n アルゴリズムの base 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 ベクトル クラスを使用することです。

Answer 2

このアルゴリズムの背後にある考え方は、値 a _k、 a _k-1、 a _k-2、...、 a ₀のリストを作成するというものです。最後に、その値のリストを返し、数値の base-b 表現のような形式で返したいと考えています。

たとえば、このアルゴリズムに 33 を入力し、その基数 16 表現を要求すると、アルゴリズムは₁ = 2 と₀ = 1 を設定します。アルゴリズムの戻り値は表現 21 であり、これは₁ ( 2) の後に₀ (1) が続きます。

彼らが使用している表記法は、「このアルゴリズムによって生成された値のリストを返す」という単なる凝った数学用語です。これは、数値の base-b 桁の配列を返すものと考えることができます。

お役に立てれば！