base d'extension b de l'algorithme n

Question

im lecture sur l'expansion base b de l'algorithme n et ce livre est vraiment difficile à lire et à comprendre, je ne suis pas sûr de ce que la partie inférieure signifie ...

ça retourne n ou quoi? comment voulez-vous faire ... grâce

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

J'ai écrit une implémentation en C pour la fonction. Il utilise un pointeur comme paramètre d'entrée, où la sortie (un vecteur d'entiers) sera placée. La fonction renvoie également un entier - la taille logique du vecteur.

#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; 
} 

Une autre façon de le faire (sans le paramètre de pointeur) est à allouer de la mémoire pour le vecteur à l'intérieur de la fonction, et le retourner, ce qui nécessite la fonction d'appel pour libérer la mémoire utilisée après son traitement fini.

Dans ce cas, vous ne pouvez pas indiquer la taille logique du vecteur, vous devez donc définir la réponse [k] sur une valeur spéciale (-1 ici) pour savoir où s'arrête le vecteur.

#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; 
} 

Une solution plus élégante (en C++) consiste à utiliser la classe de vecteur STL.

Answer 2

L'idée derrière cet algorithme est que cela crée une liste de valeurs a _k, un _k-1, un _k-2, .. ., un . À la toute fin, il veut retourner cette liste de valeurs et le faire sous une forme qui ressemble à la représentation de base-b du nombre.

Par exemple, si vous entrez 33 dans cet algorithme et demander sa représentation de base-16, l'algorithme mis un = 2 et = 1. La valeur de retour de l'algorithme est alors la la représentation 21, qui est un (2) suivi d'un (1). La notation qu'ils emploient est juste mathspeak de fantaisie pour "renvoyer la liste des valeurs produites par cet algorithme." Vous pouvez le considérer comme renvoyant un tableau des chiffres de base-b du nombre.

Espérons que cela aide!