O Scratch em acção: primeiros passos

Como refiro noutro artigo, onde as razões da decisão foram expostas, resolvi dedicar algum tempo à divulgação da programação entre os mais jovens. A aquisição do gosto pela programação que, no fundo, não é mais do que uma poderosa ferramenta de resolução de poblemas, pode ser encarada como um acontecimento probabilístico: apresente-se a coisa a X pessoas e uma dada fracção delas, X/N, entrará no comboio. Quanto maior for a audiência X, maior o número de "programadores" contagiados no final.

O principal objectivo destes  posts é elencar algumas ideias fundamentais à escrita e ao desenvolvimento de programas em computador, seguindo uma abordagem que procurará ser independente da linguagem de programação utilizada, e aplicar essas ideias na realização de tarefas de programação bem definidas, mas que sejam didácticas, divertidas e exigindo apenas um nível de conhecimento e um grau de dificuldade adequados à jovem audiência.

Para efectivar esta acção resolvi apostar no Scratch, uma linguagem visual desenvolvida no MIT sobre uma plataforma aberta de Smalltalk, o Squeak. O Scratch é software livre e está disponível para Windows, Macintosh (Mac OS X) e Linux (pelo menos para as distribuições Ubuntu e Fedora). As instruções de instalação naqueles sistemas operativos podem ser consultadas no site do Scratch. Na figura seguinte está o ecrã inicial com que o Scratch nos brinda em Windows.

Janela de trabalho do Scratch, onde são visíveis os painéis mais importantes.

A programação em Scratch (que, em Dezembro de 2010, está na versão 1.4) consiste em interligar blocos visualmente apelativos que correspondem a tarefas de programação concretas. Esta metodologia de programação com gráficos denomina-se programação visual, sendo um exemplo comercial muito vulgarizado deste paradigma de programação o Labview. Alguns daqueles blocos, com possibilidades de parametrização, são personalizados pelo utilizador para a acção que pretende implementar (por exemplo, definindo o número de ciclos que quer executar num "loop"). O Scratch 1.4 dispõe de oito (8) categorias de instruções: Motion (movimento), Control (controle), Looks (aparência), Sensing (interacção), Sound (som), Operators (operadores), Pen (caneta) e Variables (variáveis). Estas categorias são visíveis no painel superior esquerdo da janela de desenvolvimento do Scratch. Para auxiliar a identificação dos blocos, cada categoria está associada a uma cor (por exemplo, os blocos da categoria "Control" são amarelos). Carregando no botão de cada uma das categorias, ficam acessíveis os elementos (de programação) que ela contém: na anterior figura, são visíveis, no painel inferior esquerdo, os elementos "azuis" relacionados com movimento ("Motion").

A língua utilizada nos menus e nos blocos de programação é seleccionada clicando no pequeno globo situado no canto superior esquerdo da janela do editor (mesmo à direita da palavra "Scratch" escrita com uma fonte estilizada). O Português está disponível. Porém, como há muitos itens que não são traduzidos, optámos por utilizar todos os menus na linguagem original: o Inglês. Se quer ser programador de computadores, é bom que se comece a habituar ao Inglês...

No Scratch existem sprites (espíritos, duendes ou fadas...), correspondentes às imagens, como é o exemplo do gato na figura. Também existem sons. Os sprites podem ter vários fatos ("costumes"), o que permite fazer animação com eles. Os painéis para gerir os fatos e os sons são abertos nos marcadores visíveis sobre a janela central (scripts, costumes, sounds). No painel scripts são criados os programas através do arrastamento, a partir do painel da esquerda onde se pode abrir qualquer das oito categorias de blocos, dos blocos necessários ao programa que pretendemos realizar. No problema matemático de hoje serão usados operadores, blocos de controle e variáveis.

O painel da direita é o cenário onde se movem as imagens, caso o programa efectue algum tipo de animações. Os scripts são executados desde o início sempre que se carrega na bandeira verde, e pára-se a sua execução quando se carrega na bola vermelha. Podem haver vários sprites e cada um eles estar associado a um ou mais scripts.

Para terminar esta breve introdução, chama-se a atenção para a existência de quase um milhão e meio de  projectos desenvolvidos com o Scratch disponibilizados no seu site. Os respectivos scripts são de consulta livre.

O problema

O problema do dia é retirado do Projecto Euler. Este projecto publica regularmente problemas matemáticos que, regra geral, necessitam do auxílio do computador para ser resolvidos. Eis o enunciado do problema 1 transcrito ipsis verbis:

"If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000."

(a palavra below foi propositadamente realçada.) Ao resolver este problema e, por conseguinte, ao divulgar a sua solução, não estamos a ser exageradamente desmancha-prazeres (spoilers!), pois ela já está espalhada na Internet: na presente data, já mais de 111000 utilizadores registados no projecto descobriram a solução!

Análise do problema e estratégia de resolução

A análise do problema basicamente consiste apenas na leitura cuidada do seu enunciado e no sequenciamento das acções necessárias:

1. enumerar, um a um, os inteiros de 0 até 999 (inclusive); 
2. testar cada um dos inteiros para verificar se é múltiplo de 3 ou de 5; 
3. em caso afirmativo, adicioná-lo ao acumulador; e no caso contrário passar ao próximo inteiro. Se este for 1000, parar, e a solução do problema é o valor guardado no acumulador.

Vamos necessitar de duas variáveis para resolver o problema: o acumulador, inicializado com 0, ao qual vamos somando os números que satisfazem a condição de ser múltiplos de 3 ou de 5; e n, um contador que varre sequencialmente a gama de inteiros de 0 a 999 (inclusive). Note que a denominação das variáveis no Scratch é arbitrária, tendo-se apenas de garantir  que o seu nome começa por uma letra. Porém, é uma boa prática dar nomes às variáveis que reflictam o seu significado: assim, é muito mais fácil ler e entender os programas, quer ao autor, quer aos eventuais "interessados".

Para determinar se um número, k, é múltiplo de outro, m, usa-se a função matemática módulo que nos dá o resto (inteiro) da divisão inteira k/m: se o resto for 0, então k é múltiplo de m. Habitualmente esta operação é escrita k mod m.  Por exemplo, 17 mod 5=2 (pois 17=3*5+2) e 25 mod 5=0 (pois 25 é múltiplo de 5). A função módulo já existe no Scratch.

Solução computacional: versão lenta

Na figura seguinte mostra-se um script que resolve o problema. Os programas em Scratch são chamados scripts. Abrimos o painel da esquerda nas variáveis, sendo visível que há duas, acumulador e n, que desempenham os papéis que anteriormente descrevemos. O "v" a marcar estas variáveis dá a indicação de que pretendemos visualisar o seu valor no painel da direita.

O sprite do feiticeiro foi escolhido para figurar no painel porque pensamos que ele reflecte bem a filosofia subjacente a este texto. Não fosse esta razão, qualquer boneco podia servir como ilustração...

Script que resolve o problema 1 do projecto Euler. A solução é o valor da variável acumulador.

O programa é simples de entender observando a figura, mas para benefício de todos fazemos alguns breves comentários. Inicializamos o contador com n=0, e o acumulador também com 0. Depois, executamos um ciclo do tipo "repeat-until" que pára quando n>999, ou seja, neste ciclo varre-se a sequência de inteiros definida no enunciado do problema. Dentro do ciclo testa-se se n é multiplo de 3 ou de 5 e, em caso afirmativo, adiciona-se n ao acumulador. No final do script o acumulador tem a solução.

A solução do problema é o valor no acumulador, 233168. O script é executado desde o início sempre que se carrega na bandeira verde, e pára quando se carrega na bola vermelha. A bandeira e a bola estão situadas no topo direito da janela do Scratch, sobre o painel do cenário.

Versão rápida da solução computacional

O anterior script é lento: temos que percorrer toda a lista de inteiros entre 0 e 999. E a lentidão é um dos males que deve ser evitado em todos os algoritmos, a todo o custo! Uma estratégia para acelerar a resolução  consiste em percorrer apenas as sequências dos múltiplos de 3 e de 5 e ir adicionando os seus membros ao acumulador. É isso que se vai fazer de seguida.

Pensando um pouco melhor, reconhece-se que a anterior estratégia de solução está errada porque os números que são simultaneamente múltiplos de 3 e 5 serão contados duas vezes! Temos que evitar que isso aconteça. Para implementar esta salvaguarda usa-se um bloco de controle if: a condição que deixa acumular n na sequência dos múltiplos de 5 é "not ( (n mod 3)=0 )" ou seja, descrevendo-a coloquialmente, acumulamos apenas os "os múltiplos de 5 que não são divisíveis por 3". A solução, agora, é a correcta (veja o valor do acumulador na figura abaixo, que é igual ao da figura anterior).

Precavendo a acumulação dos múltiplos de 5 que também são múltiplos de 3, obtemos o resultado correcto (veja o valor do acumulador).

Solução do problema pela sua análise matemática
Este problema, porém, não carece de computador para ser resolvido de forma expedita e rápida. Usando apenas a fórmula da soma da progressão aritmética de incremento unitário:



Sn=1+2+3+...+n=n*(n+1)/2
é fácil obter a solução.

Vejamos primeiro a soma, S3, de todos os múltiplos de 3 inferiores a 1000. Ora bem, teremos



S3=3+6+...+996+999=3*(1+...+333)=3*333*334/2=166833
Repetindo o procedimento para calcular S5, a soma dos múltiplos de 5 inferiores a 1000, teremos



S5=5+10+...+990+995=5*(1+...+199)=5*199*200/2=99500
e a soma de S3 e S5 é



S3+S5=266333
superior à solução do problema que, como já vimos, é 233168!

O que estará a falhar no raciocínio? É deveras óbvio que os números que são simultaneamente múltiplos de 3 e 5 foram "pescados" duas vezes, em S3 e em S5! Assim, obteremos a solução correcta se subtrairmos a soma destes "duplos múltiplos" ao valor de S3+S5.

Ora bem, os números a que nos referimos são os múltiplos de 3*5=15 inferiores a mil. A sua soma, S15, é calculada de forma semelhante a S3 e S5:


S15=15+30+...+975+990=15*(1+...+66)=15*66*67/2=33165
Então


SOLUÇÃO=S3+S5-S15=266333-33165=233168
é a solução do problema, igual àquela já obtida computacionalmente.

Conclusão

Esta primeira digressão pelo uso do Scratch focou simultaneamente o raciocínio matemático estruturado  adequado à resolução de um (simples) problema, e um conjunto de blocos (ou "instruções") do Scratch que permitiram, quando convenientemente sequenciados e parametrizados, a solução computacional da questão. Esta abordagem será repetida em futuros artigos.

Até breve!