Blog de Helton Duarte

O seu portal de informações sobre TI

Novo domínio

Olá pessoal!

Boas notícias concretizadas! Para quem ainda não sabia esse blog estava em processo de migração para um domínio próprio *.com e o que precisava ser feito já está pronto! O seu novo endereço é heltonduarte.com e trará cada dia mais informações a todos sobre tecnologia, programação e tudo o que há de maravilhoso no mundo da informática! Esse domínio não será desativado, devido ao seu já bom desempenho nos mecanismos de busca, recebendo muitos usuários para-quedas e, por isso, deixará apenas de receber atualizações (sendo todas feitas, a partir de hoje, no novo domínio).

Muito obrigado a todos os que acompanham meus posts e continuem lendo em nosso novo endereço. Aproveitando, votem sobre o que acharam dessa mudança de local e o conheçam!

Helton de Melo Duarte

“Eu louvarei ao SENHOR segundo a sua justiça e cantarei louvores ao nome do SENHOR Altíssimo.” Salmos 7.17

Abril 4, 2009 Publicado por Helton de Melo Duarte | Outro | , | Sem comentários ainda

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

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

Computadores de mão: Smartphones

Começa a batalha!

A nova saga de smartphones chega para deixar o consumidor totalmente em dúvida! Eles chegam mostrando que a tecnologia para dispositivos móveis está cada dia melhor e lançando diversas lojas de aplicativos que irão estimular muitos desenvolvedores pelo mundo.

iPhone 3G: todos já sabem a sua capacidadeiPhone

O smartphone líder em vendas (muitos dos outros que serão citados não estão disponíveis ainda) é da maçã. Ele traz diversas inovações para o consumidor, principalmente no conceito de loja de aplicativos (App Store), os quais podem ser desenvolvidos por qualquer um (lógico que precisa comprar o SDK – kit de desenvolvimento) e que está fazendo muitas empresas se especializarem nisso. Outro fenômeno do iPhone é o acesso à internet, pois 54% dos acessos feitos em smartphones vêm dele xD. Por fim, seus “atalhos” multitoque, como o movimento de pinça com os dedos para dar zoom na tela, são fenomenais e deixam os outros aparelhos um pouco para trás. Contra: Não edita arquivos do Office, apenas os exibe em tela.

G1: o sistema é que faz a diferençaG1 - Android

O G1 – da HTC – é um fenômeno não por ter um hardware muito eficiente, mas por ser o primeiro smartphone com o sistema operacional do Google, o Android. Esse SO se destaca primeiramente por ser OpenSource, o que irá atrair muitas pessoas, além de também possuir loja de aplicativos, o Android Market, e ser muito mais fácil desenvolver para ele, pois seu SDK é disponibilizado gratuitamente. As vantagens sobre o iPhone 3G são o seu teclado QWERTY físico, além de uma boa integração com os serviços na nuvem do Google. Contra: Não é compatível com o Exchange e não há suporte nativo para arquivos do Office.

Palm Pre: a volta por cimaPalm Pre

Primeiramente, temos que destacar o webOS, novíssimo sistema operacional, criado para colocar a Palm de volta no topo dos smartphones. Ele integra e-mail, calendário e contatos com o Synergy; alterna facilmente entre tarefas paralelas com o cards; e possui uma loja de aplicativos onde o desenvolvedor só precisa saber HTML, CSS e Java Script (não tenho certeza, porém acredito que o SDK será grátis). =D Além disso, possui tela multitoque, como o smartphone da Apple. Contra: Algumas limitações no que diz respeito à fotos, músicas e vídeos.

N97: a revolução da NokiaN97

Com uma boa câmera de 5MP, o N97 vêm com a missão de colocar a Nokia frente a frente com o iPhone (na verdade todos os smartphones querem isso). Ele possui incríveis 32GB de espaço, com possibilidade ainda de expansão para 48GB, além de teclado QWERTY físico, bem útil para textos maiores. Além disso, possui um sistema GPS, como os demais smartphones atuais e conexões HSDPA e Wi-Fi. Outro ponto importante, pelo menos para mim, é o sistema Symbian S60, possibilitando a programação de aplicativos em Python! Contra: sinceramente, o único contra que encontrei foi que ele só estará disponível por volta da metade desse ano e na Europa, ou seja, pra chegar aqui vai demorar um pouquinho…=(Ah, também tem sua loja virtual, a qual não sei se é boa…

Windows phones: será que a MS vai ser maleável dessa vez?Ballmer - Windows Mobile

Com mais uma das lojas de aplicativos, Windows Marketplace, será que a Microsoft irá abrí-la para desenvolvimento de terceiros e permitir a instalação de aplicativos? Com o sistema Windows Mobile 6.5, a gigante dos softwares apresentou no Mobile World Congress, o conceito de “Windows phones”, para tentar bater o concorrente da maçã, além de mostrar uma interface amigável ao toque. Outro ponto forte é o MyPhone, serviço que permitirá o backup de agenda, vídeos, fotos e arquivos na internet, sincronizando seus dados com a web. Contra: ninguém sabe ao certo qual será o destino dessa loja de aplicativos, pois está comprovada a importância da ajuda de desenvolvedores de fora para a evolução desse tipo de serviço e, como todos sabem, a MS não é de permitir isso em seus programas.

É isso aí pessoal. Como deu pra perceber, todos querem tirar o iPhone do topo, pois ele já foi lançado e deu MUITO certo, ou seja, Apple que se prepare para os concorrentes de peso que estão por vir. Qual deles você prefere? Comente sobre os pontos positivos/negativos de cada um deles! Vamos lá, comentem!

Posts interessantes:

Helton de Melo Duarte

“Mas tu, SENHOR, és um escudo para mim, a minha glória e o que exalta a minha cabeça.” Salmos 3.3

Fevereiro 18, 2009 Publicado por Helton de Melo Duarte | Apple, Google, Microsoft, Tecnologia | , , , , , , , | 8 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

Itens anteriores