Blog de Helton Duarte

Estou de volta!

Para aqueles que estavam ansiosos por mais uma aula preparatória para competições de programação (principalmente OBI, pois já está próxima), venho aqui para isso! A aula de hoje não será tão grande, contudo tem uma importância extrema (quem viu a prova da 2ª fase da OAH 2008 perceberá a importância desse assunto) e, como sempre, virá seguida de exercícios.

Eu sei que muitos podem estar achando os exercícios complicados, e realmente são, mas preciso informá-los que a persistência é o melhor remédio, pois eu estava empacado em um deles a mais de semana, só que ontem consegui receber um “Accepted” no site da UVa Online Judge! =) Vamos, então, à batalha!

Aula 3 – Strings

Conteúdo: visão geral de como tratar strings, desde o modo em que elas aparecem nas diversas linguagens, até os principais métodos para lidar com elas.

Strings são estruturas fundamentais de crescente importância. Vocês verão que os problemas apresentados nessa aula são um pouco mais fáceis do que o passado, todavia eles revelam a forma de como strings e caracteres são representados, além dos melhores algoritmos para manipular esse tipo de dado.

Códigos dos caracteres: Os caracteres são apenas códigos os quais o computador associa a um símbolo, por esse motivo linguagens como C, C++ e Pascal tratam o tipo char como alguma coisa de 1 byte, nada mais do que isso. O American Standard Code for Information Interchange (ASCII), ou Código Padrão Americano para Troca de Informações, representa o caracter por 1 byte, tendo um total de 2^7 = 128 tipos diferentes. Eles não foram ordenados ao acaso, possuindo algumas propriedades interessantes para o programador:

• Todos os caracteres não-imprimíveis possuem os 3 primeiros bits iguais a 0 (zero) ou os 7 menos sigficativos iguais a 1;
• As letras minúsculas e maiúsculas aparecem ambas ordenadas sequencialmente, o que nos permite a criação de loops do primeiro (“a”) ao último (“z”);
• Além do loop, podemos ver qual a posição apenas subtraindo pelo valor do início: “I” – “A” = 8;
• Podemos converter de maiúscula para minúscula com operações simples como: “C” – “A” + “a”. Analogamente uma letra será maiúscula se estiver entre “A” e “Z”;
• Ao ordenar um texto, estaremos simplesmente ordenando o seu código ASCII.

Códigos mais modernos, como Unicode, utilizam 2 ou até 3 bytes para representar um caracter, abrangendo qualquer língua do planeta.

Representando strings: aqui apenas diferenciarei os modos de linguagens básicas tratarem as strings.

• Vetores terminados com NULO: C/C++ tratam strings apenas como vetores de caracteres, terminando com o “” (zero ASCII). A não colocação desse último caracter pode gerar muita confusão no decorrer do programa, pois seria uma string “infinita”. Vantagem: pode-se acessar cada valor apenas indexando-os, assim como vetores.
• Vetor mais tamanho: Outro modo usual é utilizar o primeiro elemento do vetor para o tamanho da string, o que dispensa a utilização do caracter NULO. Essa forma é utilizada internamente pelo Java, apesar de ser mostrado ao programador como um objeto.

Manipulando strings: Para a sua manipulação será necessário o conhecimento de como sua linguagem trata esse dado, contudo para uma simplificação, iremos exemplificar com o suporte feito em C.

• Computando o tamanho de uma String: Varre os caracteres, até encontrar o NULO, com um contador para o cálculo;
• Copiando uma String: Ao menos que sua linguagem de programação suporte igualar dois vetores de uma só vez, você terá que copiar elemento por elemento. OBS: não esqueça de criar o caracter NULO no fim!;
• String ao contrário: Se não for necessário manter a string original é preciso apenas trocar os elementos, num loop até a metade do tamanho. Caso seja preciso a primeira, então copia-se para outra string, só que da direita para a esquerda. OBS: novamente, não esqueça de criar o caracter NULO no fim!;
• Por último, será apresentado um algoritmo, pouco eficaz, diga-se de passagem, mas SIMPLES, para contar quantas vezes alguma string p aparece em outra t.

Bibliotecas de funções para strings: Já estamos no final da aula, mas deixaremos para vocês dicas de algumas bibliotecas já presentes nas linguagens, para o tratamento de strings:

• C => <ctype.h> Manipulação de caracteres; <string.h> Manipulação de strings;
• C++ => as mesmas do C, além de uma classe string, a qual possui algumas funcionalidades interessantes. MAIS;
• Java => A classe String, com diversas operações avançadas em java.text;
• Pascal => Nativo do SysUtils, portanto todas as funções estão a sua disposição. MAIS.

Bem pessoal, o conteúdo era esse, agora vamos praticar! OBS: Novamente eu lembro que todos os exercícios dispostos abaixo estão no UVa Online Judge e eles possuem todos os direitos sobres os problemas.

• WERTYU – Nível 1
• Where’s Waldorf? – Nível 2
• Common Permutation – Nível 1
• Crypt Kicker II – Nível 2
• Automated Judge Script – Nível 1
• File Fragmentation – Nível 2
• Doublets – Nível 3
• Fmt – Nível 2

Posts interessantes:

• Programando melhor: Aula 2 – Estrutura de Dados
• Programando melhor: Aula 1 – Começando
• Cursos grátis na Internet – MIT
• OAH 2008

Nossa primeira batalha está por vir, se preparem, porque a OBI vem aí! Vão treinando com esses exercícios e os da seção pratique da OBI que na prova será moleza! Qualquer dúvida e/ou sugestão postem! Vamos lá! Comentem!

Helton de Melo Duarte

“Sonda-me, ó Deus, e conhece o meu coração; prova-me e conhece os meus pensamentos. E vê se há em mim algum caminho mau e guia-me pelo caminho eterno.” Salmos 139.23,24

This entry was posted on terça-feira, março 3rd, 2009 at 16:49 and is filed under Programando Melhor. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.