Arquivo mensais:junho 2007

Operação Mindfuck neste sábado!

ATENÇÃO: Este conteúdo foi publicado há 10 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Museu histórico de Itajaí

Na expectativa de difundir mais o nome da Deusa em Itajaí, o Rev. Schneider sugeriu que realizássemos mais uma operação mindfuck neste sábado, 23 de junho. A idéia é evocar coletivamente Éris na frente do museu histórico de Itajaí (aquela construção bonita que você pode ver na outra operação mindfuck) para que um busto comece a falar!

Vamos fazer isto sábado de manhã, porque é quando todo mundo sai para fazer compras… Tá todo mundo convidado. Sábado, às 9h00, no calçadão de Itajaí (rua Hercílio Luz), na frente do museu. Tragam seus Principias!

Viva a discórdia, todos salvem Éris!

Crivo de Eratóstenes

ATENÇÃO: Este conteúdo foi publicado há 10 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Encontrar números primos é um problema comum em olimpíadas e maratonas de programação. Até hoje não existe uma maneira fácil de determinar se um número é ou não primo, mas para resolver estes problemas é indispensável o conhecimento de alguns algoritmos clássicos e simples, como o Crivo de Eratóstenes.

O Crivo de Eratóstenes é um método bastante prático para encontrar os primos de 2 até um valor limite, que pode ser feito a mão e é fácil de implementar.

O algoritmo consiste em:

  1. Determinar (ou receber na entrada do programa) o valor limite, isto é, o maior número que desejamos saber se é primo.
  2. Fazer a raiz quadrada do valor limite. Pode-se arredondar para baixo caso a raiz não seja exata (e quase nunca é).
  3. Criar um vetor (lista) com os números de 2 até o valor limite.
  4. Para i=2 até raiz do valor limite, caso o número (i) não esteja riscado insira-o na lista dos primos (ou imprima-o, ou não faça nada, isso depende da utilidade que você quer dar para o crivo) e risque todos os seus múltiplos na lista.

Há várias maneiras de implementar este algoritmo. Eu pseudocodaria (meu pseudocódigo é bem próximo de uma linguagem normal, porque acho que assim é mais fácil de entender e depois implementar) ele assim:

/* Primeiro passo */
recebe valorLimite

/* Segundo passo */
raiz \leftarrow \sqrt{valorLimite}

/* Terceiro passo */
para i \leftarrow 2 até valorLimite
    vetor[i] \leftarrow i
fim-para

/* Quarto passo */
para i \leftarrow 2 até raiz
    se vetor[i] = i
        imprima "O número " i " é primo."
        para j \leftarrow i+i até valorLimite, de i e i
            vetor[j] \leftarrow 0
        fim-para
    fim-se
fim-para

Vêem como é simples?

Crivo de Eratóstenes implementado em C

#include <stdio.h>
#include <math.h> // necessário para raiz
 
#define NMAX 1000000 // valor máximo para o valor máximo
 
int main() {
    int i, j, vetor[NMAX];
    int valorMaximo, raiz;
 
    // Primeiro passo
    scanf("%d", &valorMaximo);
 
    // Segundo passo
    raiz=sqrt(valorMaximo);
 
    // Terceiro passo
    for (i=2; i<=valorMaximo; i++) {
        vetor[i]=i;
    }
 
    // Quarto passo
    for (i=2; i<=raiz; i++) {
        if (vetor[i]==i) {
            printf("%d é primo!n", i);
            for (j=i+i; j<=valorMaximo; j+=i) {
                vetor[j]=0; // removendo da lista
            }
        }
    }
 
    return 0;
}

No USACO Training Program Gateway (programa de treinamento para olimpíadas dos estado-unidenses) há um problema muito interessante (Prime Palindromes) cujo objetivo é determinar palíndromos primos de X a Y. Uma das melhores situações que já encontrei para usar o Crivo e sem dúvidas é um ótimo treinamento. Além de determinar primos, você terá que determinar palíndromos e é outro ótimo exercício lógico-matemático.

Divirtam-se e qualquer dúvida usem os comentários!

Além do bem e do mal

ATENÇÃO: Este conteúdo foi publicado há 10 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.
Além do bem e do mal

Mais uma sugestão de leitura do Mal Vicioso! O livro da vez é: Além do bem e do mal

Escrito por Nietzsche e publicado por várias editoras aqui no Brasil, “Além do bem e do mal” é um livro que não pode faltar na cabeceira de um filósofo. A obra desde seu primeiro capítulo critica filosofias metafísicas, religiões, moralismos e verdades. Faz-nos refletir sobre os nossos valores, ética e sobre a natureza do homem.

Nota: O estilo aforismático de autor traz tantas frases de tamanho efeito que resolvi me privar de colocar alguma aqui para não desprezar as outras.

O prelúdio a uma filosofia do futuro é um livro pesado, que deve ser digerido com muita atenção. Ainda estou no terceiro capítulo (A natureza religiosa), mas não posso deixar de recomendar esta obra excepcional de Nietzsche, que talvez hoje não fosse tão incompreendido (ou talvez o mundo não tenha mudado tanto assim nos últimos cem anos…).

Escada perfeita (OBI2006)

ATENÇÃO: Este conteúdo foi publicado há 10 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Depois de meses sem postar, resolvi que a partir de agora darei mais atenção pra este blog. Muita gente me manda e-mail e comentários com dúvidas e gostaria de deixar bem claro que eu não faço trabalhos de faculdade pra ninguém, mas que se você tiver uma dúvida real onde eu possa ajudar eu ajudarei de bom grado.

Pensei muito sobre o que postar aqui, tenho rascunhos sobre buscas em grafos e sobre resoluções de problemas de grafos, mas resolvi quebrar toda a ordem e, a partir de um scrap de orkut, acabei me lembrando do problema Escada perfeita, da OBI 2006, e me deu vontade de resolvê-lo aqui.

Por que o problema Escada Perfeita?

A programação deste problema é extremamente simples, mas a sua lógica (matemática pura) é muito inteligente. Tente resolver o problema antes de ver minha solução e, caso não consiga, depois veja como a solução é bonita.

Vamos ao enunciado…

Uma construtora, durante a criação de um parque temático, encontrou no terreno um conjunto de várias pilhas de cubos de pedra. Ao invés de pagar pela remoção dos cubos de pedras, um dos arquitetos da empresa achou interessante utilizar as pedras para decoração do parque, determinando que as pedras fossem rearranjadas no formato de “escada”. para isso, os funcionários deveriam mover alguns cubos para formar os degraus das escadas. Só que o arquiteto decidiu que, entre uma pilha e outra de pedras deveria haver exatamente uma pedra de diferença, formando o que ele chamou de escada perfeita. O exemplo abaixo mostra um conjunto de cinco pilhas de pedras encontradas e as cinco pilhas como ficaram após a arrumação em escada perfeita.

Tarefa

Dada uma seqüência de pilhas de cubos de pedras com suas respectivas alturas, você deve determinar o número mínimo de pedras que precisam ser movidas para formar uma escada perfeita com exatamente o mesmo número de pilhas de pedras encontrado inicialmente (ou seja, não devem ser criadas ou eliminadas pilhas de pedras). O degrau mais baixo da escada deve sempre estar do lado esquerdo.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha contém um inteiro n que indica o número de pilhas de pedras. A segunda linha contém N números inteiros que indicam a quantidade de cubos de pedras em cada uma das pilhas, da esquerda para a direita.

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo um inteiro: o número mínimo de cubos de pedras que devem ser movidos para transformar o conjunto de pilhas em uma escada perfeita, conforme calculado pelo seu programa. Caso não seja possível efetuar a transformação em escada perfeita, imprima como resultado o valor -1.

Exemplos

Exemplo 1

Entrada
5
5 4 5 4 2

Saída
5

Exemplo 2

Entrada
6
9 8 7 6 5 4

Saída
9

Exemplo 3

Entrada
2
1 5

Saída
-1

OK. Estão prontos?

Depois de pensar um pouco, conclui-se que:

  1. A escada perfeita é uma PA de razão 1 (aumenta de um em um). Você lembra disso do seu primeiro ano do Ensino Médio? Senão, é bom dar uma relembrada. As fórmulas (simples e facilmente deduzíveis) da PA são:

    Termo geral da PA

    a_{n} = a_{1} + (n-1).r

    Soma de PA

    \displaystyle S_{n} = (a_{1}+a_{n}).\frac{n}{2}

  2. Sabemos quanto vale n (o número de pilhas, número de elementos da PA) e conseguimos calcular a soma de todos os elementos (podemos fazer isso até durante o loop da entrada, certo?)
  3. Sabemos quanto vale a razão (r=1).
  4. Substituindo o que sabemos nas fórmulas conseguimos formar um sistema de equações básico e desta forma torna-se fácil descobrir o valor do primeiro e do último termo da PA (a_{1} e a_{n}). Resumindo um pouco os cálculos, depois de alguma manipulação algébrica você chega a: \displaystyle a_{n} = \frac{\frac{2.S_{n}}{n}+n-1}{2}

    \displaystyle a_{1} = 1 + a_{n} - n

  5. Agora que já sabemos onde começa e onde termina a escada basta fazer um loop em cada fila de blocos e adicionar à uma variável movimentos a quantidade de quadradinhos que estão sobrando nesta fileira (por exemplo, na primeira fileira da figura do enunciado está sobrando três quadradinhos para chegar ao a_{1}=2). Ao mesmo tempo, adicionamos à outra variável (moves) a quantidade de quadradinhos que devem ser retirados ou colocados na fileira (porque depois se esta variável não for igual a 0 imprimimos -1). Ficou claro?

Implementação

Variáveis

  • n: número de degraus (fileiras de blocos)
  • a: a_{1}, número de blocos do primeiro degrau.
  • b: a_{n}, número de blocos do último degrau.
  • soma: S_{n}, soma da PA.
  • pilha[]: vetor de degraus.
  • movimentos e moves: explicados no quinto passo da solução.
  • i e j: variáveis auxiliares para fazer os loops.

Codeado em C

#include <stdio.h>
#define PMAX 10001
 
int main() {
    int i, j;
    int n;
    int soma=0;
    int a, b;
    int pilha[PMAX];
    int moves=0;
    int movimentos=0;
 
    scanf("%d", &n);
    for (i=0; i<n; i++) {
        scanf("%d", &pilha[i]);
        soma+=pilha[i];
    }
 
    b=(((2*soma)/n)+(n-1))/2;
    a=1+b-n;
 
    for (i=0; i<n; i++) {
        moves+=(pilha[i]-(i+a));
        if (pilha[i]>i+a) {
            movimentos+=(pilha[i]-(i+a));
        }
    }
 
    if (moves!=0) {
        printf("-1n");
    } else {
        printf("%dn", movimentos);
    }
 
    return 0;
}

Prontinho! Qualquer dúvida escrevam seus comentários.

A sala de aula ideal

ATENÇÃO: Este conteúdo foi publicado há 10 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Sala de aula

“Educai as crianças e não será necessário punir os homens.” (Pitágoras)

Peraí… Como assim educar as crianças?

Minha professora de história, nos últimos cinco minutos de sua aula, jogou uma pergunta à classe: Como deveriam ser as aulas de história? Enquanto uma grande parte dos alunos conversava, várias pessoas se manifestaram e sugeriram idéias diferentes. Fiquei a pensar: como contentar a todos? Como, afinal, seria uma sala de aula ideal?

Após a primeira reflexão, discuti com a professora como é complicado dar aula para uma sala. Existem vários tipos de aluno e cada um está na escola por um motivo e objetivo diferente (entre aqueles sem objetivo). Como juntar todos os alunos, ensiná-los do mesmo modo e avaliá-los da mesma forma? Como é possível dar aula para 40 pessoas tão diferentes uma da outra?

Na verdade o sistema da escola, a maneira como ela é uma obrigação (e as pessoas são empuradas para ela), a avaliação, a nota, o ensino, a juventude e suas metas (ou falta de metas)… tudo torna o processo educativo muito complicado. E ainda há duas questões de extrema importância: o porquê de educar e se realmente todos precisam saber do conteúdo.

Concluí que ninguém deveria estar numa instituição que prega que todos que têm a mesma idade são obrigados a aprender o mesmo conteúdo, no mesmo período, da mesma maneira e serem avaliados igualmente. E sim, eu sei que isso é uma máxima “Faça o que eu digo, mas não faça o que eu faço”. Mas mais do que isso, algumas pessoas em especial eu acho que não deveriam estar na escola. Há muita gente com dificuldade de concentração e de aprendizagem do conteúdo escolar…

Seriam eles inferiores? Creio que essa mentalidade está presente na construção da nossa sociedade. Porém, na minha opinião, nem todos nascem para o meio acadêmico e é para ele que a escola forma. Algumas pessoas (e não são nem um pouco inferiores por isso) têm outro jeito e deveriam ser tratadas de outra maneira. É uma pena que todos sejam mandados pro mesmo lugar e tratados como iguais. A igualdade nem sempre é boa, aliás, quase nunca.

Mas refletindo somente sobre a pergunta da Caroline individualmente e de maneira muito egoísta, resolvi que a melhor maneira de eu aproveitar as duas horas e meia semanais de história que temos (três aulas de cinqüenta minutos) é:

  1. Segunda-feira: discussão cultural-filosófica do conteúdo que todos pesquisaram e estudaram final de semana.
  2. Terça-feira: prova sobre o conteúdo que todos estudaram no final de semana e discutiram segunda-feira.
  3. Quarta-feira, quinta-feira: não tem aula de história. A professora corrige a prova.
  4. Sexta-feira: a professora entrega da prova, há uma socialização dos resultados e uma discussão para fechar o conteúdo. Tarefa para segunda-feira: pesquisar sobre um novo conteúdo (professora sugere um tema).
  5. Sábado, domingo: Alunos pesquisam e aprendem sobre o tema que a professora passou.

Já sobre a escola como um todo, sua obrigatoriedade, sua divisão por matérias e por idade, etc. é preciso um outro post, muito maior. Assim que Éris me inspirar escreverei sobre isto.