1

Escreva um algoritmo que decifre um dado texto baseado em análise de frequência da língua portuguesa.

Exemplo: exemplo

O exemplo acima usa chave de substituição. A técnica que deve ser utilizada para decifrar a mensagem consiste em análise estatística. Por exemplo, o caractere a é o que aparece mais vezes na língua portuguesa. Portanto, o símbolo que aparecer mais vezes deverá ser a letra a. A ordem de frequência dos caracteres na língua portuguesa é:

a e o s r d n i t m u l c v p g q b f h j x z k y w

A ordem acima mostra o espectro de frequência dos caracteres, iniciando pelo a com a maior frequência e w com a menor frequência. A mensagem que deve ser decifrada é:

Cscmxcszfsocmfzscssjncwcgfspezgcfkjgznvcwbmcjcwesjvcncbfmxcmzsnenkcgzcnvzsncazicgfsbcsscmcxcjngccwzxgcvcbmfocnczxbzmjifsziezmmcszsrfmkcgfsxcjsgfpezbmfxzvjccrfmkchexcnczznvm

A mensagem cifrada acima não tem espaços, acentuação ou pontuação, e deve ser escrita sem levar essas questões em consideração. Lembrem-se que por se tratar de um método estatístico, alguns caracteres errados podem prevalecer. Isso surge eventualmente de forma marginal, e é possível com intervenção humana revisar essa questão. Portanto, com a mensagem decifrada, deve existir espaço ainda para alguma modificação.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
main()
{
    char chave[26],texto[30],frase[30];

    int cont,i;

    printf("Digite o texto: ");
    scanf("%s",chave);

    cont=strlen(chave);
    strcpy(texto, chave);  

    for(i=0;i<cont;i++)     
    {
        if (texto[i]=='c')
            frase[i]='a';                 
        else if (texto[i]=='z')
            frase[i]='e';
        else if (texto[i]=='s')
            frase[i]='o';
        else if (texto[i]=='m')
            frase[i]='r';
            else if (texto[i]=='n')
            frase[i]='n';
            else if (texto[i]=='e')
            frase[i]='z';
            else if (texto[i]=='j')
            frase[i]='d';
            else if (texto[i]=='a')
            frase[i]='w';             
        else frase[i]=texto[i];
    } 
    printf("\n %s\nTexto Descriptografada e :\n %s\n",texto, frase);  
}
5
  • Tentei elaborar uma resposta para o seu problema e ele é bem mais difícil do que parece, e a sua tentativa de solução está muito longe do que seria uma forma de resolvê-lo. Analisando-se as frequências de letras da mensagem, há vários casos onde elas que aparecem um igual número de vezes (sendo esse número diferente de zero). S e Z aparecem 18 vezes cada. A e H aparecem 1 vez cada. B, E e V aparecem 6 vezes cada. K e W aparecem 4 vezes cada. J e X aparecem 8 vezes cada. O, P e R aparecem 2 vezes cada. Commented 22/04/2018 às 8:42
  • Isso significa que há pelo menos 576 formas diferentes igualmente prováveis de decodificar isso. E claro, supondo que o texto siga rigorosamente a ordem de frequência de letras dada, o que pode não ser verdade. Commented 22/04/2018 às 8:43
  • e vcs teriam uma ideia de como resolver?
    – Henrique M
    Commented 22/04/2018 às 12:56
  • eu passei a noite em claro e vou tentar fazer isso
    – Henrique M
    Commented 22/04/2018 às 12:59
  • 1
    Possível duplicata de Comparação entre letras Commented 23/04/2018 às 14:34

1 Resposta 1

2

A melhor tentativa de decodificação que consegui foi essa. Explicações no código:

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

#define MAX_STR 1000
#define NUM_LETRAS 26

int main() {

    int i, j;

    char alfabeto[] = "abcdefghijklmnopqrstuvwxyz";
    char ordem[] = "aeosrdnitmulcvpgqbfhjxzkyw";
    char trocas[] = "jgmfri";
    char chave[NUM_LETRAS + 1]; // + 1 por causa do terminador da string.
    int frequencias[NUM_LETRAS];
    int frequencias2[NUM_LETRAS];
    char codificado[MAX_STR];
    char decodificado[MAX_STR];

    // Passo 1:
    // Limpa o vetor "frequencias".
    for (i = 0; i < NUM_LETRAS; i++) {
        frequencias[i] = 0;
    }

    // Passo 2:
    // Lê a string codificada do usuário.
    printf("Digite o texto criptografado: ");
    fgets(codificado, MAX_STR, stdin);

    // Passo 3:
    // Percorre a string "codificado" e conta quantas vezes cada letra aparece,
    // guardando a contagem no vetor "frequencias".
    for (i = 0; codificado[i]; i++) {
        if (codificado[i] >= 'a' && codificado[i] <= 'z') { // Se for letra minúscula.
            frequencias[codificado[i] - 'a']++;
        } else if (codificado[i] >= 'A' && codificado[i] <= 'Z') { // Se for letra maiúscula.
            frequencias[codificado[i] - 'A']++;
        }
        // Poderia ter um else para os casos onde não é nenhum dos dois,
        // mas quando isso acontece, não precisamos fazer nada.
    }

    // Passo 4 (opcional):
    // Mostra o vetor "frequencias".
    // Aproveita para copiar "frequencias" para "frequencias2".
    printf("\n\nTabela de frequências:");
    for (i = 0; i < NUM_LETRAS; i++) {
        printf(" %c=%d", i + 'a', frequencias[i]);
        frequencias2[i] = frequencias[i];
    }
    printf("\n");

    // Passo 5:
    // Percorre a tabela "frequencias" para montar a "chave", utilizando a ordem das letras
    // dada pelo vetor "ordem". Entretanto, o vetor "frequencias" acaba sendo destruído
    // por esse processo, e é por isso que temos uma cópia em "frequencias2".
    for (i = 0; i < NUM_LETRAS; i++) {
        int maior = -1;
        int maior_indice = 0;
        for (j = 0; j < NUM_LETRAS; j++) {
            if (frequencias[j] >= maior) {
                maior = frequencias[j];
                maior_indice = j;
            }
        }
        chave[maior_indice] = ordem[i];
        frequencias[maior_indice] = -1;
    }
    chave[NUM_LETRAS] = 0;

    // Passo 6 (opcional):
    // Percorre a tabela "frequencias2" para procurar por letras que ocorram um mesmo
    // número de vezes (que não seja zero) e mostrar isso ao usuário.
    // Entretanto, "frequencias2" acaba sendo destruído nesse processo.
    for (i = 0; i < NUM_LETRAS; i++) {
        if (frequencias2[i] == 0) continue;
        int p = 0;
        for (j = i + 1; j < NUM_LETRAS; j++) {
            if (frequencias2[j] != frequencias2[i]) continue;
            if (p == 0) {
                printf("Frequências iguais [%d]: %c", frequencias2[i], i + 'a');
                p = 1;
            }
            printf("%c", (j + 'a'));
            frequencias2[j] = 0;
        }
        frequencias2[i] = 0;
        if (p != 0) printf("\n");
    }

    // Passo 7 (opcional):
    // Troca algumas letras da "chave" a fim de ajeitar manualmente os casos que estiverem errados.
    // As letras das posições pares são permutadas com as das posições ímpares de "trocas".
    for (i = 0; trocas[i]; i += 2) {
        char temp = chave[trocas[i] - 'a'];
        chave[trocas[i] - 'a'] = chave[trocas[i + 1] - 'a'];
        chave[trocas[i + 1] - 'a'] = temp;
    }

    // Passo 8 (opcional):
    // Mostra a chave.
    printf("\nA chave é:\n%s\n%s\n", alfabeto, chave);

    // Passo 9:
    // Tendo o vetor "chave" montado, usa ele para formar a string "decodificado"
    // a partir de "codificado".
    for (i = 0; codificado[i]; i++) {
        if (codificado[i] >= 'a' && codificado[i] <= 'z') { // Letras minúsculas.
            decodificado[i] = chave[codificado[i] - 'a'];
        } else if (codificado[i] >= 'A' && codificado[i] <= 'Z') { // Letras maiúsculas.
            decodificado[i] = chave[codificado[i] - 'A'] - 'a' + 'A';
        } else { // Copia qualquer outra coisa diretamente.
            decodificado[i] = codificado[i];
        }
    }
    decodificado[i] = codificado[i]; // Copia o terminador nulo.

    // Passo 10:
    // Mostra o texto "decodificado".
    printf("\nO texto descriptografado é:\n%s\n", decodificado);  
}

Eis a saída:

Digite o texto criptografado: 

Tabela de frequências: a=1 b=6 c=36 d=0 e=6 f=13 g=9 h=1 i=3 j=8 k=4 l=0 m=14 n=11 o=2 p=2 q=0 r=2 s=18 t=0 u=0 v=6 w=4 x=8 y=0 z=18
Frequências iguais [1]: ah
Frequências iguais [6]: bev
Frequências iguais [8]: jx
Frequências iguais [4]: kw
Frequências iguais [2]: opr
Frequências iguais [18]: sz

A chave é:
abcdefghijklmnopqrstuvwxyz
hlawustfgnvyrdbqkpozxmcije

O texto descriptografado é:
Aoariaoesobarseoaoondacatsoquetasvntedmaclranacuonmadalsriareodudvateadmeodahegatsolaooaraiandtaaceitamalrsbadaeilerngsoeguerraoeopsrvatsoianotsquelrsiemnaapsrvafuiadaeedmr

Veja aqui funcionando no ideone.

Observe o texto descriptografado:

Aoariaoesobarseoaoondacatsoquetasvntedmaclranacuonmadalsriareodudvateadmeodahegatsolaooaraiandtaaceitamalrsbadaeilerngsoeguerraoeopsrvatsoianotsquelrsiemnaapsrvafuiadaeedmr

Entretanto, tive que forçar algumas trocas de letra (com o array trocas). As trocas foram (na chave), J com G, M com F e R com I. Achei essas possíveis trocas na base da tentativa e erro, e chute. Sem essas trocas, o texto produzido é esse:

Aoasiaoerobasreoaootdacanroquenarvtnedmaclsatacuotmadalrsiaseodudvaneadmeodahepanrolaooasaiatdnaaceinamalsrbadaeilestproepuessaoeogrsvanroiatonrquelsriemtaagrsvafuiadaeedms

E então, você irá ter que ter a tarefa inglória de chutar várias possíveis trocas até achar o resultado correto.

Um abordagem que tente várias possíveis combinações de trocas e procure qual é a que forma o maior número de palavras em um dicionário dado com dezenas de milhares de palavras seria uma possibilidade, mas isso claramente está bem longe do proposto nesse seu problema.

Se o texto criptografado tivesse espaços, a tarefa seria muito mais fácil.

1
  • show de bola, muito obrigado de coração
    – Henrique M
    Commented 24/04/2018 às 2:24

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .