Encoder le message par alphabets

Question

J'essaie de résoudre le problème ci-dessous pour améliorer mes compétences. J'apprécierais que quelqu'un améliore mon code d'une meilleure manière.

Compte tenu du mappage a = 1, b = 2, ... z = 26 et d'un message codé, comptez le nombre de façons dont il peut être décodé. Par exemple, le message «111» donnerait 3, car il pourrait être décodé comme «aaa», «ka» et «ak». Vous pouvez supposer que les messages sont décodables. Par exemple, «001» n'est pas autorisé.

#include <stdio.h>
#include <stdlib.h>

#define MIN_ALPH 1
#define MAX_ALPH 26

//return number of possible encode methods
int encode(unsigned int num)
{
    int count=0;
    unsigned int ddigit;
    
    //encode by 2 digits
    for(int i=10; i<=num; i*=10)
    {
        ddigit = (num % (i*10)) / (i/10);
        if (ddigit >= MIN_ALPH && ddigit <= MAX_ALPH)
            count++;
    }
    
    //extra count for the single digit encoding since all digits are non-zero
    return ++count;
}

int main(void) 
{
    /*Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, 
    count the number of ways it can be decoded.
    For example, the message '111' would give 3, 
    since it could be decoded as 'aaa', 'ka', and 'ak'.
    You can assume that the messages are decodable. 
    For example, '001' is not allowed.*/
    
    printf( "result: %d\n",  encode(512));
    printf( "result: %d\n",  encode(542));
    printf( "result: %d\n",  encode(112));
   
}

Answer 1

La terminologie est un peu bâclée - j'appellerais l'opération consistant à passer du décodage des chiffres au décodage des caractères alphabétiques plutôt qu'à l'encodage - et notre fonction n'est vraiment ni l'une ni l'autre: c'est compter . (Je suppose que vous n'êtes pas anglophone, alors ne prenez pas cette critique trop durement!).

---

L'interface est surprenante: accepter un type entier limite grandement la longueur maximale d'entrée, et on pourrait renvoyer un type non signé comme résultat:

unsigned int count_decodings(const char *input);

À titre indicatif, il est sûr de convertir un caractère en chiffre en soustrayant '0'(C garantit que les chiffres 0..9 ont des encodages consécutifs, quel que soit le codage des caractères de l'environnement hôte).

---

L'algorithme produit des résultats incorrects :

Ce commentaire n'est pas justifié:

//extra count for the single digit encoding since all digits are non-zero
return ++count;

Certains chiffres peuvent en effet être zéro - par exemple, 10et 201chacun peut être décodé exactement dans un sens. Cela devrait suggérer des tests supplémentaires que vous pourriez (et devriez) faire.

---

C'est bien que nous ayons des tests main(); J'irais plus loin et ferais les tests auto-vérifiés . Au lieu de simplement imprimer les résultats, nous devrions comparer les valeurs attendues et EXIT_SUCCESSne renvoyer que si tous les tests réussissent. Il existe plusieurs bibliothèques disponibles pour vous aider avec des tests unitaires comme celui-ci, ou vous pouvez le faire tout simplement:

int failures = 0;
failures += count_decodings("10") != 1;
failures += count_decodings("11") != 2;
// more tests here

Nous n'avons aucune indication sur les tests qui ont échoué et sur leurs résultats attendus et réels. Nous pourrions créer des macros pour aider ici (ce qui est exactement ce que les frameworks de tests unitaires nous fournissent).

Answer 2

Pour le message, 111111j'obtiens 13 combinaisons:

......aaaaaa

_.... kaaaa
._... akaaa
.._.. aakaa
..._. aaaka
...._ aaaak


__..  kkaa
_._.  kaka
_.._  kaak
.__.  akka
._._  akak
..__  aakk

___   kkk

Avec un "3" à la première place, vous perdez kkk, kaak, kaka, kkaa et kaaaa. Je pense que vous devez partir du maximum combinatoire et ensuite vérifier combien vous pouvez exclure. Mais cela doit être très non trivial. D'où ça vient?

Ce:

99991999919999199991999919

peut encore être lu de plusieurs façons selon la façon dont vous combinez les cinq choix pour «ai» ou «s».

---

Le programme imprime uniquement "6" pour "111111". Il ne compte que de "aaaaaa" à "aaaak" (ci-dessus).