Blog de Helton Duarte

O seu portal de informações sobre TI

Programando melhor: Revisão

Olá pessoal!

Como a prova da primeira fase da OBI é amanhã resolvi fazer esse post para uma revisão rápida de vocês sobre algumas questões importantes.

Primeiramente, quero avisá-los para termos bastante atenção com a quantidade de loops feitos, pois diversos loops encadeados podem fazer você não passar em alguns dos testes feitos (normalmente passará nos mais simples, contudo não conseguirá a pontuação completa).

Segundo vim trazer mais um assunto possível para a prova, o qual explicarei posteriormente na aula sobre grafos, no entanto colocarei um exemplo de fácil entendimento da seção pratique da OBI, do nível 2, Batuíra (código resolvido abaixo):
#include

#define INF 1000000;

int main()
{
/* Batuíra */
int num = 1; /* Número do teste */
int n, x, y, z; /* Quantidade de pontos e variáveis para distância */
int dist[110][110]; /* Grafo para distância dos pontos */
int i, j, k; /* Contadores para loop for */

/* O Grafo dist[110][110] representa as distâncias entre os pontos de
repouso. Por exemplo, o valor de dist[i][j] é a distância entre os pontos
i e j */

/* Entrada do número de pontos */
scanf (“%d”, &n);

while (n != 0)
{
/* Coloca a distância padrão entre os pontos */
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
if (i == j)
{
dist[i][j] = 0; /* A distância para o próprio
ponto de repouso é zero */
}
else
{
dist[i][j] = INF; /* Diz que a distância entre os pontos
é “infinita”, ou seja, não há ligação entre eles */
}
}
}

/* Lê os pontos e a distância entre eles */
scanf (“%d %d %d”, &x, &y, &z);
/* A distância do ponto x ao ponto y é igual a z */

while (x != 0) /* Quando qualquer valor for zero é o fim da
entrada dos pontos */
{
/* Coloca as distâncias nas duas direções */
dist[x][y] = z;
dist[y][x] = z;

/* Lê os pontos e a distância entre eles */
scanf (“%d %d %d”, &x, &y, &z);
}

/* Algoritmo de Floyd-Warshall */
for (k = 1; k <= n; k++)
{
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
/* Se houver um ponto de repouso entre i e j com uma
menor distância, então o valor de pontos[i][j] é
substituído pelo de (dist[i][k] + dist[k][j]) */
if ((dist[i][k] + dist[k][j]) < dist[i][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
dist[j][i] = dist[i][k] + dist[k][j];
}
}
}
}

/* Depois desse laço principal o valor de dist[1][n] é a menor
distância entre o ponto inicial e o final, a qual representa o valor
pedido pelo problema */

/* Saída de dados */
printf (“Teste %d\n%d\n\n”, num, dist[1][n]);

/* Incremento para o próximo caso de teste */
num++;

/* Entrada para o próximo caso de teste */
scanf (“%d”, &n);
}

return (0);
}

Fiquem bem atentos a parte de grafo, além do famoso algoritmo de Floyd-Warshall, o qual é suficientemente eficiente para esse problema.

Serão colocados comentários com dicas para os problemas “The Trip”, em Exercícios 1 (Parte I) e “Jolly Jumpers”, na Aula 2, pois foram resolvidos por mim no site do UVa Online Judge (finalmente).

Por fim, boa sorte a todos os que irão participar da competição amanhã (OBI), tomara que seja uma boa prova! Eu também participarei, esperando um bom resultado, se Deus quiser.

Posts interessantes:

E você, como se preparou para a OBI? Ah, quando a prova terminar, postem suas opiniões aqui e vamos discutir as questões! Comentem!

Helton de Melo Duarte

“Entrega o teu caminho ao Senhor, confia nEle e Ele tudo fará.” Salmos 37.5

“O meu escudo está com Deus, que salva os retos de coração.” Salmos 7.10

Março 27, 2009 Publicado por Helton de Melo Duarte | Competições, Programando Melhor | , , | 2 Comentários

Hospedagem Hostnet

Olá pessoal,

Primeiramente, peço desculpas a todos pelo bom tempo que passei sem postar nada novo aqui no blog. O caso é o seguinte: como fui vencedor da OAH 2008 (Olimpíada de Algoritmo Hostnet), tenho direito a um domínio e hospedagem grátis pela empresa realizadora da competição e, recentemente, fui contatado pelo Diretor de Marketing, Kauê Linden, para migrar o blog para os servidores deles, no domínio heltonduarte.com , o qual está em construção, tentando exportar todos os posts daqui para lá.

O blog continuará do mesmo modo, com a mesma seriedade de sempre e buscando novidades a cada dia, com total imparcialidade, como procurei durante todo esse tempo aqui, além da continuação do curso “Programando melhor”, ainda em criação. Portanto, venho apenas para informar essa novidade que está sendo realizada para o melhor aproveitamento de todos ao conhecimento, certo? Pois possuiremos muitíssimas novas funcionalidades depois dessa migração.

Espero a compreensão de todos e assim que houver novidades trarei-as a esse local (como finalização da migração, por exemplo), atualizando esse próprio post.

E você, o que achou das novidades? Dê o seu feedback e conte-nos sua opinião!

Helton de Melo Duarte

“E não vos conformeis a este mundo, mas transformai-vos pela renovação da vossa mente, para que experimenteis qual seja a boa, agradável, e perfeita vontade de Deus.” Romanos 12.2

Março 23, 2009 Publicado por Helton de Melo Duarte | Outro | , , , | Sem comentários ainda

Programando melhor: Aula 4 – Ordenação

Olá pessoal!

Mais uma aula de preparação para a OBI 2009 (principalmente)! Pessoal do IF-RN, preparem-se pesado, porque esse ano precisamos ter alguma medalha! =) A aula de hoje abordará um assunto também bem importante para competidores, visto que otimizar o método de ordenação é um fato muito importante nesse caso (não podemos sempre utilizar o Bubble Sort!).

Aula 4 – Ordenação

Conteúdo: principais aplicações dos algoritmos de ordenação, assim como uma abordagem dos melhores métodos para esse tipo de atividade.

Ordenação é um dos pontos primordias na ciências da computação, estando presente na solução de diversos problemas existentes nas competições e na vida do programador. Muitos algoritmos de ordenação já foram desenvolvidos, sendo necessário saber para que tipo de situação serve cada um (embora já existam muitos os quais não serão mais usados, por haver outros mais otimizados). Nessa aula, procurarei abordar as aplicações mais importantes da ordenação, além de uma teoria a respeito dos principais algoritmos da área.

Aplicações da ordenação:

  • Teste de unicidade: Como testar se os elementos de uma coleção S são todos distintos? Ordene-a crencente ou decrescentemente e faça uma varredura testando se S[i] = S[i+1].
  • Priorizando eventos: Suponha que existem diversos trabalhos a serem feitos, cada um com seu deadline (data limite). Ordenando-os de acordo com o deadline os  colocará na ordem certa para serem cumpridos.
  • Mediana: Se for necessário encontrar o k-ésimo maior item em uma lista S, é preciso apenas ordená-la, tendo o elemento S[k] como o requerido.
  • Encontrando o par correto: Como podemos testar se existem dois inteiros x, y em S que x+y = z, onde z é um inteiro qualquer? Ao invés de testar todos os pares possíveis, ordene os números crescentemente. Como S[i] aumenta com o i, o provável parceiro j que tem S[j] = z – S[i] diminui. Com esse método fica bem mais eficiente sua procura.
  • Busca eficiente: Para saber se um elemento s encontra-se em S, simplesmente ordena-se e lista e realiza-se uma busca binária na fila, um dos métodos mais comuns de aplicação da ordenação.

Algoritmos de ordenação:

Você já deve ter ouvido muitos algoritmos diferentes para ordenação de dados, no entanto deve estar pensando: para que uma pessoa precisa saber de tantos modos para se fazer a mesma coisa? O real motivo para se estudar todos esses códigos são as ideias por trás dos mesmos, ou seja, o modo como foi desenvolvido certo algoritmo pode ser utilizado para algum problema de uma forma parecida, deu pra entender? Abaixo serão mostrados os três mais interessantes para o estudo da sua teoria:

  • Selection Sort – Esse algoritmo divide o vetor de entrada em partes ordenadas e não-ordenadas e a cada varredura pela parte não-ordenada ele encontra o menor elemento e o transfere para o fim da região ordenada. São feitas muitas comparações, todavia é muito eficiente se contarmos o número de troca de posições, pois são apenas n-1, no pior dos casos. Segue no link os códigos em diversas linguagens: Selection Sort.
  • Insertion Sort – Esse algoritmo também mantém regiões ordenadas e não-ordenadas. Em cada vez o próximo elemento não-ordenado é movido para a sua posição apropriada na região ordenada. Insertion sort é particularmente eficiente no que diz respeito a quantidade de movimento de dados, pois ele só inverte  um par de elementos para o local já certo, ou seja, em uma lista praticamente ordenada ele pode ser extremamente eficaz. Novamente os códigos seguem com o link: Insertion Sort.
  • Quick Sort – É um dos mais eficientes e rápidos, reduzindo o trabalho de ordenar uma grande lista em ordenar duas listas menores. A partição separa o vetor nos elementos menores do que um certo x e os maiores do que o mesmo x. Como nenhum elemento precisará mover-se para fora de sua região, cada vetor menor poderá ser ordenado independentemente. Para facilitar a ordenação o quicksort também recebe como argumentos os índices do começo e fim do sub-vetor. Esse código é muito interessante por diversas razões, pois quando é implementado corretamente consome menos memória do que qualquer outro, além de ser uma das melhores demonstrações do poder da recursividade (uma função que chama ela mesma). Os exemplos em cada linguagem seguem no link: Quick Sort.

Estamos no final da aula, mas não podemos deixar de praticar, não é verdade? Abaixo seguem os exercícios para o treinamento de ordenação:

PS: Lembrando a todos que o conteúdo desse post e de todo o curso “Programando melhor” é baseado no livro Programming Challenges, de autoria de Miguel Revilla e Steve Skiena e foi permitido o “resumo” e tradução do mesmo pelos próprios autores para a criação desse curso. Além disso os exercícios estão todos disponibilizados no site UVa Online Judge.

Posts interessantes:

Pessoal, mais uma aula completa e dedicação é necessária! Façam sempre os exercícios! Procurarei nas próximas duas semanas, dedicar-me aos exercícios que já foram propostos aqui, colocando dicas para cada um, ok? Além disso, os próprios problemas da seção pratique do site da OBI. Comentem e tirem suas dúvidas! Vamos lá!

Helton de Melo Duarte

“Bem-aventurado o varão que não anda segundo o conselho dos ímpios, nem se detém no caminho dos pecadores, nem se assenta na roda dos escarnecedores.” Salmos 1.1

Março 11, 2009 Publicado por Helton de Melo Duarte | Programando Melhor | , , , | 6 Comentários

OBI vem aí!

Fiquem atentos, pessoal!

Para aqueles os quais ainda não sabem, a OBI (Olimpíada Brasileira de Informática) é uma competição realizada pela Sociedade Brasileira de Computação e Fundação Carlos Chagas com o objetivo de estimular o estudo da ciência da computação nos estudantes brasileiros de ensino fundamental e médio.

Ela é dividida em diversas modalidades e níveis, de acordo com a escolaridade do participante:

Modalidade Iniciação: não envolve conhecimentos em liguagens de programação propriamente ditas, apenas lógica para problemas diversos (para aqueles que não sabem o RN está tendo um desempenho muito bom nessas categorias nos últimos anos, tendo até um 2º lugar nacional, o Leon Deharbe, do CEI, no nível 1).

  • Nivel 1: alunos até o sétimo ano (sexta série) do Ens. Fund.
  • Nível 2: alunos até o nono ano (oitava série) do Ens. Fund.

Modalidade Programação: problemas que devem ser desenvolvidos em C, C++ ou Pascal e avaliados apenas pelo seu resultado, não havendo “meio certo”.

  • Nível Júnior: alunos do Ens. Fund.
  • Nível 1: alunos do 1º e 2º anos do Ens. Médio.
  • Nível 2: alunos do 3º ano do Ens. Médio ou que terminou-o até o ano passado (2008).

Os melhores colocados de cada nível (de acordo com sua modalidade) irão para a Unicamp (uma referência em computação em todo o Brasil), participar de um curso sobre Introdução à Programação (Iniciação), Programação Intermediária (Prog. Nível Júnior) e Programação Avançada (Prog. Níveis 1 e 2). Além disso, os alunos do nível 2 de Programação irão realizar uma seletiva (durante o período do curso) para a IOI (Olimpíada Internacional de Informática, em português), sendo 4 classificados do Brasil.

O cadastro das escolas (e de seus competidores) deverá ser feito até o dia 23 de março de 2009, pelo professor responsável. Informo também aos alunos do IF-RN (antigo CEFET-RN) que devem encaminhar um e-mail para o professor Leonardo Minora (minora@cefetrn.br), manifestando interesse em participar, para que ele possa contabilizar o número de inscritos e os dê mais orientações. Também precisará ser preenchido um formulário de inscrição, o qual será entregue ao professor, de acordo com sua idade. Veja: Menores de 18 anos; 18 anos ou mais.

As datas de realização das provas podem ser vistas no próprio site da OBI. Assim como qualquer dúvida pode ser tirada aqui mesmo ou por meio do site.

Blz pessoal? Lembrando que estou realizando nesse mesmo blog um curso preparatório para competições de programação, denominado “Programando melhor”, vejam!

Tirem suas dúvidas ou digam suas experiências em OBIs passadas! Vamos lá, comentem!

PS: Esse post foi criado a pedidos do professor Leonardo Minora, do IF-RN, para o aviso a todos os interessados na competição.

Posts interessantes:

Helton de Melo Duarte

“Oh! Quão bom e quão suave é que os irmãos vivam em união.” (Salmos 133.1)

“Em paz também me deitarei e dormirei, poruqe só tu, SENHOR, me fazes habitar em segurança.” (Salmos 4.8)

Março 7, 2009 Publicado por Helton de Melo Duarte | Competições | , , , , | 4 Comentários

Programando melhor: Aula 3 – Strings

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.

Strings

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.

Posts interessantes:

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

Março 3, 2009 Publicado por Helton de Melo Duarte | Programando Melhor | , , , | 12 Comentários