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

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

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

Programando melhor: Aula 2 – Estruturas de Dados

Mais um pouco de conhecimento adquirido!

Bem pessoal, venho hoje postar a segunda aula do nosso curso “Programando melhor”, como sempre baseado no livro Programming Challenges, de Steven Skiena e Miguel Revilla, falando hoje um pouco sobre Estruturas de Dados, as quais infelizmente eu não vi no curso do CEFET-RN (atual IF-RN), contudo acredito serem essenciais para um bom programador. No final estarei indicando os links de exercícios para vocês praticarem o assunto estudado, blz? Vamos começar!

Aula 2 – Estruturas de Dados

Conteúdo: abordagem das estruturas de dados elementares, assim como mais dicas de como abordar um problema e os métodos para testar/debuggar.

Estruturas de dados são primordiais em qualquer programa robusto, sendo primordial a escolha da estrutura certa para representar o problema, evitando códigos feios e diversos bugs pela frente. ^^

Iremos mostrar as principais estruturas de dados (pilhas, filas e dicionários), com algumas operações básicas para manipulá-las. Para aqueles programadores de C++ e Java já existem bibliotecas prontas para esse controle, contudo é interessante o entendimento de como elas trabalham por dentro. Para C++: stl.h; para Java: java.util.

Pilhas: as pilhas e as filas são estruturas nas quais seus itens são controlados de acordo com a ordem de inserção e não pelo conteúdo armazenado. Ao inserir ou remover um item, fazemos em seu topo. As operações básicas são as seguintes:

Push(x, s) – Insere o item x no topo da pilha s.

Pop(s) – Retorna (e remove) o item do topo da pilha s.

Initialize(s) – Cria uma pilha vazia.

Full(s), Empty(s) – Testa se a pilha pode aceitar mais Push ou Pop, respectivamente.

Obs.: Não há operação para procurar um item na pilha, justamente pelo fato que o conteúdo não importa, somente é vista a ordem de inserção.

Filas: assim como nas pilhas, não importa o conteúdo, apenas a ordem. Nas filas os itens são inseridos em seu final e removidos do início. Um exemplo interessante do uso de filas é quando se trabalha com baralhos de cartas (tente fazer um exemplo para entender melhor XD ). A seguir, as operações:

Enqueue(x,q) – Insere o item x no fim da fila q.

Dequeue(q) – Retorna (e remove) o item da frente da fila q.

Initialize(q), Full(q), Empty(q) – Análogos às operações de pilhas.

Filas precisam de um pouco mais de cuidado, já que acontecem coisas nos dois lados da estrutura. O modo mais simples de implementação é utilizando arrays (vetores), inserindo no final e movendo todos os elementos restantes para preencher o espaço vazio do Dequeue. Contudo, temos que pensar um pouco antes de criar filas com vetores, pois é bastante desperdício esse movimento a cada Dequeue e o fato de filas circulares, ou seja, o primeiro e o último elemento são iguais. Por essas e outras, filas são estruturas mais simples de se trabalhar com listas encadeadas (um pouco sobre ponteiros para os adeptos de Pascal aqui) do que com vetores.

Dicionários: estruturas as quais pode-se trabalhar com o conteúdo dos elementos, tendo como operações primárias:

Insert(x,d) – Insere o item x no dicionário d.

Delete(x,d) – Deleta o item x (ou o item apontado por x) do dicionário d.

Search(k,d) – Retorna o item com a chave k se o mesmo existir no dicionário d.

Nós precisamos, então, saber qual é a melhor maneira de se trabalhar com esse tipo de estrutura e assim segue abaixo cada caso:

Dicionários estáticos => Essas estruturas são criadas uma vez e nunca mais mudadas, precisando então apenas do Search, não mais do Insert ou Delete. O melhor jeito para se trabalhar com eles é na utilização de vetores, sendo então sua preocupação apenas de como mantê-los ordenados, para otimizar suas buscas, contudo isso iremos ver em outras aulas.

Dicionários semi-dinâmicos => São aqueles em que se pode inserir ou pesquisar (Search), porém não pode deletar. Se soubermos o máximo de elementos, é possível a utilização de vetores, contudo sem essa informação será preciso novamente trabalhar com listas encadeadas.

Dicionários dinâmicos => Aqueles em que é permitida qualquer operação. Como muitos já devem ter percebido, a melhor maneira de se implementar esse tipo de estrutura é com a utilização de listas encadeadas, somente, para não tornar nosso código extremamente horroroso.

Finalmente chegamos ao fim dessa abordagem sobre estruturas de dados propriamente dita, esperando ter conseguido relembrar e otimizar o uso delas, além de fazê-lo mais preparado para os problemas que virão. A seguir colocarei mais dicas de resolução de problemas.

Sua solução começa agora

  • Leia o programa atentamente – Leia cada linha do problema cuidadosamente e releia quando o juiz online lhe reportar algum. Veja até mesmo a história que você acha não ter importância, no início do problema, porém preste bastante atenção às descrições de entrada/saída, além de seus exemplos.
  • Não assuma nada – Esteja atento a instruções de entrada não especificadas, números sem limites, linhas longas de entrada, números negativos, etc. NÃO ESQUEÇA: qualquer situação que não é explicitada como proibida deve ser assumida como possível!
  • Não tão rápido – Não se preocupe tanto com eficiência, a menos que você esteja passando por problemas com o juiz (como um conhecido “Time limit exceeded”). Ao conhecer bem as especificações, ou seja, sabendo qual o valor máximo para as entradas, é possível prever quão rápido necessitará ser seu algoritmo. IMPORTANTE: eu não estou incentivando códigos feios e cheios de gambiarras, todavia não é preciso um cuidado excessivo com isso logo no começo do trabalho, deu pra entender?

Testando e “debuggando”

Aprender a evitar erros bestas que podem penalizá-lo em situações de competição é crucial para o sucesso em qualquer lugar, por isso seguem abaixo algumas táticas:

  • Mesmo que pareça simples, é importantíssimo o teste feito com as entradas dadas pelo problema, pois lhe dirá qual a maneira de colocar sua saída na tela;
  • Se o problema exige determinadas ações ao se colocar entradas inválidas, certifique-se primeiramente que elas estão sendo feitas;
  • Crie sempre situações de teste simples, as quais você pode testar no papel e compare as soluções, pois pode ajudar na procura de erros mais comuns;
  • Coloque sempre entradas gigantescas (no limite do permitido), para ver como o programa se comporta, ou seja, se ele não fica “doido” com números grandes, comportando-se de maneira inesperada.
  • Conheça seu “Debugger” – Qualquer ambiente de desenvolvimento vem agora com um “debugger” (a opção de executar o programa linha por linha) e é preciso que você o conheça claramente. Quanto mais cedo você começar a usá-lo, mais tempo e frustação que você vai evitar ^^;
  • No caso de não possuir esse “debugger”, crie pontos no programa para imprimir certos valores importantes, entretanto faça-os com linhas relevantes para ler a saída rapidamente e achar os possíveis erros;
  • Faça seus vetores um pouco maiores do que o necessário – precisa comentar? É apenas para garantir que a memória não vai “acabar” durante a execução…

É isso aí! Agora vamos para os exercícios e, como já avisado, apenas colocarei os links para eles no site do UVa Online Judge:

Posts interessantes:

Como falei no meu Twitter: Bora lá pessoal, nossa guerra ainda está no começo! Animação! Qualquer dúvida sobre o assunto pode perguntar. Novamente, quando tiver dicas sobre os exercícios postarei e vocês façam o mesmo. Comentem!

Helton de Melo Duarte

“Ainda que a figueira não floresça, nem haja frutos nas vides; ainda que falhe o produto da oliveira, e os campos não produzam mantimento; ainda que o rebanho seja extirpado da malhada e nos currais não haja gado; todavia eu me alegrarei no Senhor, exultarei no Deus da minha salvação.” Habacuque 3.17,18

Fevereiro 20, 2009 Publicado por Helton de Melo Duarte | Programando Melhor | , , , | 11 Comentários

Programando melhor: Aviso

Olá pessoal!

Hoje não haverá aula nem exercícios não, infelizmente, eu vim aqui apenas para comunicá-los como será a programação do nosso curso durante essa e a próxima semana, pois acontecerão algumas coisas não previstas…=(

Primeiramente, foi detectada o baixo aproveitamento do curso nos posts que traziam apenas exercícios e, por isso, eles não irão acontecer mais. Porém, não fique triste, pois não vou deixá-los na mão sem poder treinar o que aprenderam aqui, é claro, e serão disponibilizados os links para os problemas no próprio post de conteúdo, sendo essa uma forma de estimulá-los até a submeter os problemas para o juiz online, blz? Além disso, no próprio post de conteúdo poderão ser colocados comentários sobre os problemas, assim como dicas (minhas e do público) sobre como melhor resolvê-los, ok?

O outro aviso é a respeito das nossas aulas dessa e da próxima semana: o conteúdo dessa semana será proposto apenas na sexta-feira, porque não houve tempo suficiente para a resolução dos problemas propostos na semana passada e não iremos atolá-los de assunto sem treinamento, não é mesmo? Próxima semana irá ocorrer o carnaval (infelizmente) e essa pessoa que vos fala participará de um evento durante esse período (SECOPE). Portanto, na próxima semana irei apenas me reestruturar após o evento e resolver os exercícios sobre o assunto, para que a partir do dia 03/03/2009, daqui a 15 dias, nós publiquemos a terceira aula do curso “Programando melhor”.

Por fim, gostaria de agradecer a todos os quais contribuíram com comentários durante a primeira semana do curso e me fizeram elogios. Queria apenas dizer que fiquei muito grato por ver a quantidade de pessoas visitando o blog e é esse mesmo meu objetivo: ver os brasileiros com sede de conhecimento e buscando aprender coisas novas.

Posts interessantes:

O que você achou das novidades? O que tem achado do nosso curso até agora? Tem vontade de nos ajudar, pois mande um e-mail para hm_duarte@hotmail.com para conversarmos melhor e, se possível, fazermos juntos um post para todos nós. Comente!

Helton de Melo Duarte

“Filho meu, se aceitares as minhas palavras, e entesourares contigo os meus mandamentos, para fazeres atento à sabedoria o teu ouvido, e para inclinares o teu coração ao entendimento; sim, se clamares por discernimento, e por entendimento alçares a tua voz; se o buscares como a prata e o procurares como a tesouros escondidos; então entenderás o temor do Senhor, e acharás o temor de Deus.” Provérbios 2.1-5

Fevereiro 17, 2009 Publicado por Helton de Melo Duarte | Programando Melhor | , | 1 Comentário

Programando melhor: Exercícios 1 (Parte II)

Mais diversão para vocês!

Problema 3: LCD Display

UVa ID: 706    ;    Nível: Fácil

Um amigo seu acabou de comprar um novo computador. Antes disso, a máquina mais poderosa que ele havia usado foi uma calculadora de bolso. Ele está um pouco desapontado porque ele gostava do display LCD da sua calculadora mais do que da tela do seu novo computador! Para fazê-lo feliz, escreva um programa que imprima números no estilo de um display LCD.

Entrada

O arquivo de entrada contém diversas linhas, uma para cada número a ser disposto na tela. Cada linha contém inteiros s e n, onde n é o número a ser disposto (0 <= n <= 99.999.999) e s é o tamanho que ele irá aparecer (1 <= s <= 10). A entrada será terminada por uma linha contendo dois zeros, que não deve ser processada.

Saída

Escreva os números especificados no arquivo de entrada em estilo display LCD usando s sinais “-” para os segmentos horizontais e s sinais “|” para os verticais. Cada dígito ocupa exatamente s + 2 colunas e 2s + 3 linhas. Esteja certo de preencher todos os espaços brancos ocupados pelos dígitos com “espaços”, incluindo o último dígito. Deve haver exatamente uma coluna de “espaços” entre dois dígitos.

Coloque uma linha de “espaço” após cada número. Você encontrará um exemplo de cada dígito no Exemplo de saída abaixo.

Exemplo de entrada

2 12345

3 67890

Exemplo de saída


Exemplo de Saida

Problema 4: Interpreter (Interpretador)

UVa ID: 10033       ;     Nível: Médio

Um certo computador tem dez registradores e 1000 palavras de RAM. Cada registrador ou local na RAM armazena um inteiro de três dígitos entre 0 (zero) e 999. Intruções são codificadas como inteiros de três dígitos e armazenadas na RAM. Os códigos são os seguintes:

100  | manter

2dn  | armazena no registrador d o valor n (entre 0 e 9)

3dn  | adiciona n ao valor armazenado em d

4dn  | multiplica por n o valor armazenado em d

5ds  | armazena em d o mesmo valor armazenado em s

6ds  | adiciona o valor armazenado em s ao armazenado em d

7ds  | multiplica o valor armazenado em d pelo de s

8da  | armazena em d o valor de RAM que tiver seu endereço armazenado no registrador a

9sa  | armazena na RAM, cujo endereço esteja em a, o valor armazenado no registrador s

0ds  | vai para o local armazenado no registrador d a menos que o registrador s cotenha 0 (zero)

Todos os registradores inicialmente contém 000 (zero). O conteúdo inicial da RAM é lido de uma entrada padrão. A primeira instrução a ser executada é no endereço RAM zero. Todos os resultados são reduzidos módulo 1000.

Entrada

A entrada começa com um único inteiro positivo na linha, indicando o número de casos, cada um descrito abaixo. É seguido por uma linha em branco e haverá uma linha em branco entre cada duas entradas consecutivas.

Cada caso de entrada consiste num inteiro sem sinal de três dígitos, representando os conteúdos de locais consecutivos na RAM, começando pelo zero. Locais de RAM não especificados são inicializados com 000 (zero).

Saída

A saída de cada caso de teste é um único inteiro: o número de instruções executadas acima e incluindo a de “manter”. Você pode assumir que o programa faz o “manter”. Separe a saída de dois casos consecutivos por uma linha em branco.

Exemplo de entrada

1

299

492

495

399

492

495

399

283

279

689

078

100

000

000

000

Exemplo de saída

16

É isso aí pessoal, temos agora a segunda parte da primeira bateria de exercícios proposta como treinamento, ok? Os exeercícios de agora são um pouco mais difíceis (confesso que não entendi nem o que pede o problema 4 de primeira olhada xD ), contudo não desanimem, pois precisamos pegar pesado se queremos alguma coisa.

Posts interessantes:

Novamente, qualquer dica para a solução de problemas é extremamente bem vinda e dúvidas serão, à medida do possível, respondidas. Deixe seu comentário falando o que achou dos problemas! E conte também seu caso de sucesso!

Helton de Melo Duarte

“A sabedoria exalta aos que a favorecem, honra aos que a amam, e empresta graça à aparência de uma pessoa, para que esta seja admirada e respeitada por aqueles que a conhecem.” Charles Fritsch

Fevereiro 14, 2009 Publicado por Helton de Melo Duarte | Programando Melhor | , , | 4 Comentários

Programando melhor: Exercícios 1 (Parte I)

Agora é a hora da diversão!!!

Bem pessoal, como prometido, chegou hoje a primeira bateria de exercícios do nosso curso “Programando melhor”, para você que deseja se tornar um melhor programador/competidor. Além disso, venho compartilhar com vocês a enorme vantagem nesse tipo de competição de quem domina bem a matemática (em competições também), pois hoje tive mais uma aula do Programa de Iniciação Científica OBMEP 2007 e fiquei ainda mais amando essa matéria (o que me faz gostar cada vez mais de programação pesada!). Mas vamos pôr a mão na massa!

Problema 1: The 3n+1 Problem (O problema do 3n+1)

UVa ID (código no site da Universidad de Valadollid): 100 ; Nível: Fácil

Considere o seguinte algoritmo para gerar uma sequência de números. Comece com um inteiro n. Se n é par, divida por 2. Se n é ímpar, multipique por 3 e some 1. Repita esse processo com o novo valor de n, terminando quando n = 1. Por exemplo, a seguinte sequência de números será gerada a partir de n = 22.

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

É conjecturado (mas ainda não provado) que esse algoritmo terminará em n=1 para qualquer inteiro n. Ainda, a conjectura assegura para todos os inteiros até 1 milhão.

Para uma entrada n, o tamanho do ciclo de n é o número de números gerados, incluindo o 1. No exemplo acima, o tamanho do ciclo de 22 é 16. Dados qualquer dois números i e j, você deve determinar o maior tamanho do ciclo dentre todos os inteirosdf entre i e j, incluindo ambos os extremos.

Entrada

A entrada consistirá numa série de pares de inteiros i e j, um par de inteiros por linha. Todos os inteiros serão menores do que 1 milhão e maiores que 0.

Saída

Para cada par de inteiros i e j, coloque i e j na mesma ordem que eles apareceram na entrada e então o maior tamanho de ciclo para todos os inteiros entre e incluindo i e j. Esses três números devem estar separados por um espaço, com todos os três números em uma linha e com uma linha de saída para cada linha de entrada.

Exemplo de entrada/saída

Entrada -> 1 10 ; Saída -> 1 10 20

Entrada -> 100 200 ; Saída -> 100 200 125

Entrada -> 201  210; Saída ->201 210 89

Entrada -> 900 1000 ; Saída -> 900 1000 174

Problema 2: The Trip (A Viagem)

UVa ID: 10137  ;  Nível: Fácil

Um grupo de estudantes são membros de um clube que viaja anualmente para diferente locais. Os destinos deles no passado incluem Indianapolis, Phoenix, Nashville, Philadelphia, San Jose e Atlanta. Essa primavera eles estão planejando uma viagem para Eindhoven.

O grupo concorda a princípio compartilhar as despesas igualmente, mas não é prático compartilhar cada despesa no momento em que ela ocorre. Então indivíduos no grupo pagam por certas coisas, como refeições, hotéis, táxi e passagens aéreas. Depois da viagem, as despesas de cada estudante são contadas e o dinheiro é trocado para que o custo líquido para cada um seja o mesmo, para cada centavo. No passado, esse dinheiro trocado foi tedioso e consumiu muito tempo. Seu trabalho é computar, de uma lista de despesas, a quantia mínima de dinheiro que deve trocar de mãos em virtude de igualar (com diferença máxima de 1 centavo) todos os custos dos estudantes.

Entrada

A entrada padrão irá conter a informação para diversas viagens. Cada viagem consiste de uma linha contendo um inteiro positivo n, o qual representa o número de estudantes na viagem. Isso é seguido por n linhas de entrada, cada uma contendo a quantia gasta pelo estudante em dólares e centavos. Não há mais do que 100 estudantes e os estudantes não irão gastar mais do que $10.000,00 cada. Uma linha contendo 0 segue a informação da última viagem.

Saída

Para cada viagem, forneça uma linha de saída informando a quantia total de dinheiro, em dólares e centavos, que deve ser trocada para igualar os custos dos estudantes.

Exemplo de entrada

3

10.00

20.00

30.00

4

15.00

15.01

3.00

3.01

Exemplo de saída (correspondente à entrada acima)

$10.00

$11.99

Bem pessoal, agora mesmo irei colocar a Parte II desses exercícios, com mais um do nível Fácil e outro do nível Médio, ok? Fiquem à vontade para perguntar e, com certeza, dar dicas para a resolução dos problemas. Soluções completas dos problemas não serão aceitas em comentários, pois (após discutir com algumas pessoas) seria algo que tiraria a “graça” dos problemas propostos, porém qualquer dica a respeito é bem-vinda! Além disso, eu mesmo irei postar as minhas dicas quando eu pegar esses problemas pra valer (amanhã), blz?

Posts interessantes:

Helton de Melo Duarte

“A sabedoria é a coisa principal: adquire, pois, a sabedoria; sim, com tudo o que possuis adquire o entendimento. Estima-a e ela te exaltará; se a abraçares, ela te honrará. Ela dará à tua cabeça uma grinalda de graça; e uma coroa de glória te entregará.” (Provérbios 4.7-9)

Fevereiro 13, 2009 Publicado por Helton de Melo Duarte | Programando Melhor | , , , | 14 Comentários

Programando melhor: Aula 1 – Começando

Finalmente pessoal!

Hoje irá iniciar o curso de programação focado em competições existentes em todo o mundo. O curso terá como título “Programando melhor” e será composto de aulas iniciantes até programação pesada! Vamos embarcar comigo nessa empreitada!

Aula 1 – Começando

Conteúdo: introdução a competições de programação, assim como dicas iniciais e cuidados a serem tomados na criação de soluções para os problemas apresentados.

Existem por aí alguns sites que podem nos ajudar a exercitar nossos conhecimentos, pois disponibilizam juízes online para testar a eficiência do seu programa. Os principais sites para esse tipo de exercício são o da Universidad de Valladolid, o da Olimpíada Brasileira de Informática e o do livro Programming Challenges (base para o desenvolvimento desse curso). Cadastre-se neles (com excessão do site da OBI, que não precisa de cadastro) e comece a testar soluções para os mais diversos programas encontrados, inclusive para os exercícios que serão propostos aqui.

Como primeiro passo rumo a sua vitória em diversas dessas competições, você precisará primeiramente escolher em qual linguagem desenvolverá seus programas. Eu recomendo o C, pois é de fácil entendimento (sem a orientação a objeto presente no C++/Java) e é aceito em praticamente todas as competições. Pascal é uma boa recomendação apenas para quem está no ensino médio e deseja participar da OBI (pois é uma das únicas que ainda permite essa linguagem); Java é desagradável pela sua POO (programação orientada a objeto), algo bastante desagradável quando não se vai trabalhar com programas grandes os quais precisariam de reaproveitamento de algumas partes; C++ é aconselhável a programadores mais experientes, desejosos de participar do TopCoder (não aceita o C).

É preciso também tomar cuidados com algumas práticas do nosso dia-a-dia na programação que não devem ser praticadas por um competidor. Primeiramente, as entradas e saídas do seu programa devem ser exclusivamente as padrões, ou seja, não é permitida a abertura de arquivos ou funções desse estilo durante a programação. Já para programadores Java funções de internet e threads não são permitidas, além de nada poder ser público, até mesmo o Main, contudo pacotes como math, util e similares são possíveis.

Dicas de programador para programador:

  • Comece seu programa e cada uma das funções criadas comentando cada passo a ser realizado, pois isso facilitará seu entendimento do problema (se você não conseguir fazer isso, então não está entendendo o que é preciso fazer no programa). Esse esforço extra irá ajudar muito no futuro…
  • Faça o mesmo para cada variável, explicando qual será sua “função” no programa (não é preciso colocar nomes gigantes, como ModuloDoQuadradoDoVetorResultante, apenas comente bem (não é Elomar e Bryan? hehehehehe).
  • Crie, sempre que possível, constantes para representar números bastante utilizados no programa, como PI, TAMVETOR, etc., isso irá prevenir erros futuros e deixará BEM mais legível seu código (ajudando a encontrar bugs que possam aparecer).
  • Eficácia. Essa é a base para competições de progração (e para sua vida de programador). Evite ao máximo códigos redundantes, como
    • if (x == ‘A’) Código
    • else if (x == ‘B’) Código quase igual;
  • Além do mais (nunca pensei que iria falar isso na minha vida xD ): evite GAMBIARRAS! Você pode achar o máximo quando você faz uma daquelas bem grotescas, todavia isso pode lhe causar um belo de um “Time Limit Exceeded”, ou seja, seu programa pode ficar lento e não ser executado no tempo máximo permitido (é, existe um tempo máximo!). ^^
  • Por fim, é de extrema importância o conhecimento na arte de “DEBUGGAR”, ou seja, conheça o sistema de Debug do seu compilador ou faça isso manualmente (mandando imprimir o valor de certa variável em um determinado local – CUIDADO com doideras no código ao fazer isso). Esse item é muito bom caso receba alguma mensagem de erro do sistema de correção.

Um bom caminho a seguir é o de evitar tipos de dados não elementares, como POO, e até a utilização excessiva de ponteiros em C, o que pode gerar erros inesperados, sendo sempre bom recorrer aos bons e velhos Vetores. Tome também cuidados com Records/Structs/Registros, pois eles podem gerar uma grande dor de cabeça na hora de precisar alterar o seu código.

Bem, gostaria de finalizar esse post com um alerta para aqueles os quais desejam participar da OBI, pois durante a competição você não tem o acesso ao juiz dizendo se o seu programa passou nos testes ou não, isso só é disponibilizado na seção Pratique do site, portanto é necessária a sabedoria para você mesmo criar testes que poderiam dar erro em um programa, ok?

Os exercícios seguem no próximo post e eles estão todos disponibilizados no UVa Online Judge, para serem testados. Eles correspondem aos problemas do Capítulo 1 do livro Programming Challenges, de autoria de Miguel Revilla e Steven Skiena.

Posts interessantes:

E você, o que achou dessas dicas? Está pronto para começar essa jornada e se tornar um competidor dos mais fortes? Deixe seu comentário e tire as suas dúvidas!

Helton de Melo Duarte

“Porém o SENHOR disse a Samuel: Não atentes para a sua aparência, nem para a altura da sua estatura, porque o tenho rejeitado; porque o SENHOR não vê como vê o homem. Pois o homem vê o que está diante dos olhos, porém o SENHOR olha para o coração.” (1 Samuel 16.7)

Fevereiro 10, 2009 Publicado por Helton de Melo Duarte | Competições, Cursos, Programando Melhor | , , , , , | 12 Comentários

Curso de Programação – Confirmado!

Olá pessoal!!! =D

Eu venho aqui não para falar do novo Google Earth, como vocês poderiam imaginar, já que ele saiu hoje (apesar de ser uma boa falar dele)…mas para comunicá-los sobre uma novidade que eu já havia prometido para vocês leitores a algumas semanas, porém só foi confirmada hoje, após contatar Miguel Revilla e Steven Skiena (a nata da programação).

O curso de programação preparatório para competições desse assunto está confirmado no meu blog! Após resolver algumas pendências que poderiam vir, como direitos autorais e coisas do tipo, confirmei agora a pouco com os autores do livro Programming Challenges a elaboração desse meu projeto!

Livro para competições de programação

Livro para competições de programação

O curso consistirá basicamente de um abordagem sobre os assuntos desse livro citado (considerado a bíblia das competições de programação), para facilitar o acesso a esse tipo de assunto. O livro é completamente em inglês e, por isso, irei fazer esse resumo em português para vocês, além de abordar os exemplos em C e Pascal (pois no livro é apenas em C). Outro ponto importante que gostaria muito da colaboração de todos é a disponibilização de soluções para os problemas da seção Pratique, no site da OBI, as quais serão feitas por mim e por qualquer um que deseje colaborar conosco (mande as soluções para meu e-mail, em hm_duarte@hotmail.com , para que passe pela devida avaliação e, então seja postada também no blog, com seus devidos direitos ao autor). OBS: pode ser em C, C++ ou Pascal.

Peço a todos os leitores desse post para divulgarem esse assunto de toda a forma possível, pois espero que esse curso possa ajudar muitos a crescer como programadores, assim como lutar por sonhos que possam parecer distantes, como vencer esse tipo de competição.

PS: O direcionamento principal desse curso é para a participação na OBI (Olimpíada Brasileira de Informática), porém irá formar um programador completo, auxiliando, portanto, a OAH (Olimpíada de Algoritmo Hostnet), a ACM (ou online-judge, da Universidad de Valladolid) e TopCoder.

PS2: O objetivo do curso não é ensinar a linguagem C ou Pascal e sim métodos que possam auxiliar a resolver diversos problemas comuns em competições de programação e presentes no dia-a-dia, portanto tem-se como pré-requisitos desse curso o conhecimento em algoritmos e nas linguagens C ou Pascal.

Helton de Melo Duarte

“Um Vencedor respeita aqueles que são superiores a ele e tenta aprender alguma coisa com eles. Um Perdedor ressente-se daqueles que são superiores a ele e faz racionalizações a respeito de suas conquistas.

Um Vencedor explica; um Perdedor justifica.

Um Vencedor diz: ‘Vamos descobrir uma saída’; um Perdedor diz: ‘não há nenhuma saída’.

Um Vencedor enfrenta o problema; um Perdedor tenta contorná-lo.

Um Vencedor diz: ‘Deve haver um jeito melhor de fazer isso’; um Perdedor diz: ‘Isso sempre foi feito assim’.

Um Vencedor mostra que lamenta o fato de ter de compensar por algo; um Perdedor diz: ‘Eu lamento’, mas ele continua a fazer a mesma coisa.

Um Vencedor sabe pelo que lutar e com o que se comprometer; um Perdedor compromete-se com o que não deveria e luta por aquilo que não vale a pena lutar.

Um Vencedor trabalha mais duro que o Perdedor, e tem mais tempo; um Perdedor está sempre ‘muito ocupado’ para fazer o que é necessário.

Um Vencedor não tem medo da derrota; um Perdedor secretamente teme a vitória.

Um Vencedor compromete-se; um Perdedor faz promessas.”

GEORGE, Jim. Um Jovem segundo o coração de Deus, p. 159-160. CPAD, 2008.

Fevereiro 3, 2009 Publicado por Helton de Melo Duarte | Competições, Programando Melhor | , , , | 3 Comentários