Departamento de Sistemas e Computação

Professor: João Araujo

Alguns sistemas de codificação necessitam que a mensagem codificada seja apresentada em duas partes. A primeira parte, chamada cabeçalho, contém os caracteres da mensagem. A segunda parte contém o padrão que representa a mensagem. Você deve escrever um programa que decodifique a mensagem segundo o seguinte esquema:

O núcleo do esquema de codificação do seu programa é a seqüência de chaves de strings de zeros e uns, como a seguinte:

0,00,01,10,000,001,010,011,100,101,110,0000,0001,. . .,1011,1110,00000,. . .

A primeira chave da seqüência tem tamanho 1, os próximos 3 têm tamanho 2, em seguida os próximos 7 têm tamanho 3, os próximos 15 têm tamanho 4, etc. Se duas chaves têm o mesmo tamanho, o segundo pode ser obtido somando 1 ao primeiro (base 2).

Note que não existem chaves na seqüência consistindo apenas de 1.

As chaves são mapeadas em sua ordem para os caracteres no cabeçalho, isto é, a primeira chave (0) é mapeada para o primeiro caracter no cabeçalho, a segunda chave (00) para o segundo caracter, a k-ésima chave é mapeada para o k-ésimo caracter no cabeçalho.

Por exemplo, suponha que o cabeçalho seja:

Celacanto#!

Então, 0 é mapeado para 'C', 00 para 'e', 01 para 'l', 10 para 'a'… e assim sucessivamente.

A mensagem codificada contém apenas 0 e 1 e possivelmente 'return', que serão ignorados. A mensagem é dividida em segmentos.

Os primeiros 3 dígitos representam o tamanho da chave no segmento. Por exemplo, se os 3 primeiros dígitos são 010, então os restante do segmento consiste de chaves de tamanho 2 (00 01 10). O final do segmento é uma string de uns do mesmo tamanho da chave do segmento (11). A mensagem é terminada por pela seqüência 000 ( que significa um segmento com chaves de tamanho zero). A mensagem é decodificada traduzindo as chaves do segmento, uma por vez, para os caracteres para os quais foram mapeados.

A entrada consiste de vários conjuntos de dados. Cada conjunto consiste de um cabeçalho, que é uma única linha, e uma mensagem, que pode se estender por várias linhas. O tamanho máximo do cabeçalho só é limitado pelo fato das chaves terem no máximo um tamanho igual a sete (111). Se existem múltiplas cópias de um caracter no cabeçalho, então várias chaves mapearam este caracter.

A mensagem codificada contém apenas zeros e uns. O segmento começa com uma seqüência de 3 dígitos e termina com a seqüência apropriada de uns. As chaves numa seqüência têm todas o mesmo tamanho e todas correspondem a caracteres no cabeçalho. A mensagem é terminada por 000. Returns podem aparecer em quaquer ponto da mensagem e não são considerados parte da mensagem.

Para cada conjunto de dados, seu programa deve escrever a mensagem numa linha separada. Não deve haver linhas em branco entre as mensagens. Abaixo, um exemplo:

Entrada               saída 
TNM AEIOU            TAN ME
0010101100011        ##*\$
1010001001110110011  
11000
$#**\
0100000101101100011100101000

Faça um programa que resolva o seguinte problema:

Dada uma entrada composta de um cabeçalho e de uma seqüência de zeros e uns, forneça o texto decodificado.

Cada letra do cabeçalho é mapeada, em ordem, para o seguinte esquema de bits: 0 00 01 10 000 001 010 011 100 101 110 0000

Depois do cabeçalho, vem a seqüência de bits, com seguinte regra:

Os três primeiros bits da seqüência fornecem o tamanho da chave. Depois

deve-se ler cada chave e decodificá-la usando o cabeçalho. Uma seqüência de uns de tamanho da chave interrompe uma seqüência e corresponde a uma linha na mensagem original. Quando for encontrada um tamanho de chave igual a zero, termina-se a tradução da mensagem. (1pt)

       leCzdant co
       010010011
       001010110011
       010010100111
       10111000

Modifique este programa de modo que, antes da chave, seja fornecida uma linha com o número de mensagens a serem decodificadas e que seu programa execute até decodificar este número de mensagens. (3pts)

       3
       leCzdant co
       0100100110010101100
       1101001010011110111000
       actaprove
       01100000
       10100110101
       11010001100101000
       emoro!ta
       01000110110
       11111010101100101
       010000111011010000
       001111000

Modifique o programa para que a primeira linha, com o número de mensagens, também seja codificada, segundo o mesmo esquema.(3pts)

Como no item anterior, a primeira linha poderia ser codificada como:

       54301
       010011
       1000

Modifique o programa de modo que, quando for encontrada uma chave de tamanho 7, as próximas linhas decodificadas tenham suas letras decodificadas com a letra subsequente no código ASCII. Esta seqüência não tem chaves e deve ser terminada por 1111111, como determinado pela regra geral. O valor ASCII consequente a Z (z) é A(a).(3pts)

Boa sorte.