Do problema ao algoritmo

Resumo

Esta aula não contém código, e não por descuido: o algoritmo precede o programa, e quem não sabe descrever com precisão o que deve ser feito também não saberá dizê-lo em C++. Primeiro se ensina a especificar um problema, isto é, a declarar que dados ele recebe, que resultado deve entregar e que relação os une, e se mostra que um mesmo enunciado admite especificações distintas. Depois se define o algoritmo como procedimento finito, preciso e geral, e se escreve em passos numerados o da divisão por subtrações sucessivas. Ensina-se a rastrear um algoritmo à mão com uma tabela de rastreamento, que será durante todo o curso o primeiro instrumento para entender e para depurar. Apresentam-se as três formas de combinar passos (sequência, decisão e repetição), com as quais se escreve todo algoritmo, e aprende-se a justificar que uma repetição termina por meio de uma quantidade que decresce a cada iteração e não pode baixar indefinidamente.

Objetivos de aprendizagem

Especificar um problema simples indicando suas entradas, suas saídas e as condições que devem cumprir.
Descrever um algoritmo em passos numerados, sem ambiguidade, com decisões e repetições explícitas.
Rastrear à mão um algoritmo com uma tabela de rastreamento e determinar seu resultado para uma entrada dada.
Distinguir, em um procedimento dado, a sequência, a decisão e a repetição, e justificar que uma repetição termina.

O que é um problema computacional

Um problema computacional é uma relação entre duas categorias de dados: os que se recebem, chamados entrada, e os que devem ser entregues, chamados saída. Resolvê-lo não consiste em obter uma resposta para um caso, mas em dispor de um método que, para cada entrada admissível, produza uma saída que cumpra a relação. “Quanto é 17 dividido por 5?” é uma pergunta; “dados dois inteiros, obter seu quociente e seu resto” é um problema, porque fala de todos os pares de inteiros ao mesmo tempo.

Ora, a linguagem corrente é imprecisa, e o mesmo enunciado pode ser entendido de várias maneiras. Por isso, antes de resolver, especifica-se: escreve-se o que entra, o que sai e que condições cada coisa deve cumprir. A especificação tem três partes. A entrada enumera os dados com sua categoria (inteiros, decimais, palavras) e as condições que se exigem deles, que se chamam pré-condição: quem usa a solução se compromete a respeitá-las. A saída enumera os resultados. A relação, ou pós-condição, diz o que a saída deve cumprir em relação à entrada: quem escreve a solução se compromete a garanti-la sempre que a pré-condição tiver sido respeitada. Segue-se daí que a especificação é um contrato entre quem propõe o problema e quem o resolve, e que fora da pré-condição a solução não promete nada.

ExemploO máximo de três números

Enunciado corrente: “encontrar o maior de três números”. Especificação:

Entrada: três números $x$ , $y$ , $z$ (inteiros ou decimais, sem outra condição).
Saída: um número $m$ .
Relação: $m$ é um dos três dados, e nenhum deles é maior que $m$ ; isto é, $m \geq x$ , $m \geq y$ e $m \geq z$ .

A relação não diz “o maior dos três”, que é justamente o que se queria precisar, mas duas condições verificáveis. A primeira exige que $m$ seja um dos dados (sem ela, o número 1000 cumpriria a segunda para quase qualquer entrada); a segunda, que nenhum o supere. E a especificação resolve de passagem uma dúvida que o enunciado deixava aberta: se dois dados empatam no máximo, como em $(4, 9, 9)$ , a saída é $9$ , e não há erro algum nisso.

Um mesmo enunciado admite especificações distintas, e escolher entre elas é uma decisão, não um descuido. O caso mais instrutivo é o da divisão inteira. Para inteiros $a \geq 0$ e $b > 0$ , todos estão de acordo: o quociente $q$ e o resto $r$ são os únicos inteiros que cumprem

a = b \cdot q + r, \quad 0 \leq r < b

Assim, para $a = 17$ e $b = 5$ são $q = 3$ e $r = 2$ , porque $17 = 5 \cdot 3 + 2$ . Mas o enunciado “dividir dois inteiros” não diz o que fazer se $a$ for negativo, e a pergunta não é ociosa: para $a = -7$ e $b = 2$ há duas respostas razoáveis.

ExemploDuas especificações da divisão com dividendo negativo

Primeira especificação: o resto nunca é negativo, $0 \leq r < b$ . Então $-7 = 2 \cdot (-4) + 1$ , e a saída é $q = -4$ , $r = 1$ . É a que se estuda em matemática, na aula “Divisibilidade e divisão com resto” do curso Álgebra e Geometria I.

Segunda especificação: o quociente é o resultado da divisão com decimais, com sua parte decimal descartada, isto é, arredondado em direção ao zero; o resto é o que falta, e tem o sinal do dividendo. Então $-7 / 2 = -3{,}5$ se trunca para $-3$ , e $-7 = 2 \cdot (-3) + (-1)$ : a saída é $q = -3$ , $r = -1$ .

Ambas cumprem $a = b \cdot q + r$ ; diferem na condição que se impõe ao resto. Nenhuma é um erro, mas um programa que use uma acreditando que usa a outra dará resultados errados com os negativos. Antecipemos um dado: C++ adota a segunda, como se verá na aula Aritmética; quem esperar a primeira terá uma surpresa.

Há uma terceira opção, que é a mais frequente na prática: excluir o caso pela pré-condição. Se a especificação exige $a \geq 0$ , o problema dos negativos desaparece, não porque tenha sido resolvido, mas porque quem usar a solução se comprometeu a não propô-lo. O que não se pode fazer é deixar a questão sem decidir. E pela mesma razão a especificação exige $b > 0$ : com $b = 0$ não existem $q$ e $r$ que cumpram a relação, e o contrato deve dizê-lo.

Um erro frequente consiste em especificar com um exemplo: “a saída de 17 e 5 é 3 e 2”. Um exemplo ilustra, mas não especifica, porque não diz o que ocorre com as demais entradas; infinitas relações distintas coincidem em um caso. A especificação se escreve como condição geral, e os exemplos servem depois para verificá-la.

Algoritmos

Uma vez especificado o problema, busca-se um método para resolvê-lo. Um algoritmo é uma sequência de instruções que, aplicada a qualquer entrada que cumpra a pré-condição, produz em um número finito de passos uma saída que cumpre a pós-condição. A definição contém três exigências.

Finitude. O algoritmo se escreve com um número finito de instruções e, para cada entrada admissível, termina depois de executar um número finito delas. Um procedimento que para alguma entrada continua para sempre não é um algoritmo para essa entrada.
Precisão. Cada instrução tem um único significado, e quem a executa sabe a todo momento o que fazer e qual é a instrução seguinte. Nenhuma decisão fica a critério de quem executa.
Generalidade. O algoritmo resolve o problema para todas as entradas admissíveis, não só para um caso.

Com certa liberdade, chama-se também algoritmo um procedimento preciso e que termina, mas que para alguma entrada admissível não cumpre a pós-condição: a rigor é um algoritmo para outro problema, e se dirá que é incorreto para o problema especificado. É assim que se falará nos problemas desta aula, que refutam algoritmos incorretos com um contraexemplo.

Uma receita de cozinha se parece com um algoritmo, e por isso é a comparação habitual; mas quase nenhuma o é. “Adicionar uma pitada de sal” não é precisa, porque uma pitada não é uma quantidade; “assar até dourar” depende de um juízo que duas pessoas fariam de maneira distinta; “bater várias vezes” não diz quantas. Um cozinheiro completa essas lacunas com sua experiência; um computador não tem nenhuma. Segue-se daí a exigência que governa todo o curso: um algoritmo deve poder ser seguido por quem não entende o problema, sem adivinhar nada. Se para executar um passo é preciso saber para que ele serve, o passo está mal escrito.

Os algoritmos deste curso se escrevem primeiro em passos numerados, em português, com algumas convenções. Os dados que mudam durante o algoritmo são nomeados com letras ou palavras, como $q$ ou $r$ , e se chamam variáveis. Escreve-se “ $r$ recebe o valor $r - b$ ” para dizer que se calcula $r - b$ com o valor atual de $r$ e o resultado passa a ser o novo valor de $r$ ; o valor anterior se perde. Na forma abreviada, que se usa ao tomar notas, a mesma instrução se escreve com uma seta para a esquerda, que no teclado é r <- r - b. As instruções se executam na ordem de seu número, salvo se uma delas disser outra coisa.

ExemploA divisão por subtrações sucessivas

O problema é o especificado na seção anterior: entrada, dois inteiros $a \geq 0$ e $b > 0$ ; saída, dois inteiros $q$ e $r$ com $a = b \cdot q + r$ e $0 \leq r < b$ . A ideia é a de repartir: tiram-se de $a$ grupos de $b$ enquanto for possível, contam-se os grupos tirados, e o que sobra é o resto.

$q$ recebe o valor $0$ , e $r$ recebe o valor $a$ .
Enquanto valer $r \geq b$ , repetir os passos 3 e 4; quando deixar de valer, continuar no passo 5.
$r$ recebe o valor $r - b$ .
$q$ recebe o valor $q + 1$ ; voltar ao passo 2.
Entregar $q$ e $r$ , e terminar.

O passo 2 é uma pergunta que se faz a cada vez: antes da primeira iteração (ou volta) e depois de cada uma. Os passos 3 e 4 formam o corpo da repetição, o que se repete. Nada fica a critério de quem executa: em cada momento há uma só instrução seguinte.

O algoritmo é lento (para dividir um milhão por três dá mais de trezentas mil iterações), e o método escolar da divisão é muito mais rápido; mas é correto, e sua simplicidade o torna ideal para aprender a raciocinar sobre algoritmos. O curso voltará à diferença entre um algoritmo correto e um eficiente na aula O custo de um algoritmo.

Convém, por último, separar o algoritmo de sua escrita. O algoritmo da divisão por subtrações é o mesmo se for escrito em português, em um diagrama, em C++ ou em qualquer outra linguagem de programação: o que o define é a sequência de operações, não as palavras. Um programa é a escrita de um algoritmo em uma linguagem que uma máquina pode executar, e a aula Programas, compiladores e C++ explicará como ocorre essa execução. Se é assim, um programa pode estar errado de duas maneiras muito distintas: porque o algoritmo é incorreto, e então nenhuma linguagem o salva, ou porque o algoritmo é correto mas foi mal escrito. Distinguir os dois casos é metade do trabalho de depurar, e por isso o curso escreve sempre primeiro o algoritmo.

Rastrear um algoritmo à mão

Ler um algoritmo não basta para saber o que ele faz; é preciso executá-lo. Rastreá-lo à mão, como o faria a máquina, sem pular passos nem adivinhar resultados, é a habilidade mais útil de um programador: com ela se verifica um algoritmo antes de escrevê-lo, prevê-se a saída de um programa antes de executá-lo e encontra-se o erro de um que falha.

O instrumento é a tabela de rastreamento (ou teste de mesa): uma coluna para o número do passo que se executa, uma coluna por variável e, se convier, uma para as condições que se avaliam; e uma linha por passo executado. Em cada linha se anota o valor novo da variável que mudou nesse passo e se deixa em branco o que não mudou, de modo que o valor atual de uma variável é o último escrito em sua coluna. As condições se anotam com seu resultado.

ExemploO rastreamento da divisão de 17 por 5

Rastreamos a divisão por subtrações sucessivas com $a = 17$ e $b = 5$ . A seta da figura indica o passo que acaba de ser executado; a linha pontilhada lembra que o passo 4 volta ao 2.

Demonstração

$(q, r) = (0, 17)$
Passo 1: dão-se os valores iniciais. A entrada cumpre a pré-condição, porque $17 \geq 0$ e $5 > 0$ .
$(q, r) = (1, 12)$
Primeira iteração. No passo 2 se verifica que $17 \geq 5$ , de modo que se executa o corpo: o passo 3 tira um grupo de cinco e o passo 4 o conta.
$(q, r) = (2, 7)$
Segunda iteração: $12 \geq 5$ , e o corpo se executa outra vez.
$(q, r) = (3, 2)$
Terceira iteração: $7 \geq 5$ , e o corpo se executa outra vez.
$17 = 5 \cdot 3 + 2, \quad 0 \leq 2 < 5$
No passo 2 a condição falha, porque $2 < 5$ : o algoritmo continua no passo 5 e entrega $q = 3$ e $r = 2$ . A saída cumpre a pós-condição.

A tabela completa tem doze linhas: o passo 1, três iterações de três linhas cada uma (passos 2, 3 e 4), a verificação que falha e a entrega.

Duas observações sobre a tabela. A primeira: o número de iterações é igual ao quociente, $3$ , e o passo 2 foi executado uma vez mais que o corpo, $4$ vezes; isso ocorre sempre em uma repetição desta forma, porque a última verificação é a que falha. A segunda: o rastreamento ensina algo que o texto do algoritmo não diz à primeira vista; se $a < b$ , por exemplo $a = 3$ e $b = 5$ , a condição falha na primeira vez, o corpo não se executa nenhuma vez, e a saída é $q = 0$ , $r = 3$ , que é correta, porque $3 = 5 \cdot 0 + 3$ . Esquecer o caso em que a repetição não se executa é um dos erros mais frequentes ao projetar algoritmos, e o rastreamento com entradas pequenas o descobre.

O rastreamento de um caso não demonstra que o algoritmo seja correto: verifica um caso. Mas um rastreamento bem escolhido (um caso comum, um caso limite, o caso em que a repetição não se executa) descobre a maior parte dos erros, e o que falha diz onde eles estão. A aula Projetar laços corretos ensinará a passar dos casos a uma demonstração.

Sequência, decisão e repetição

Vistos de perto, os algoritmos se constroem com muito poucas peças. Há instruções elementares (dar um valor a uma variável, entregar um resultado) e três maneiras de combiná-las.

Sequência: uma instrução depois da outra, em ordem. Os passos 3 e 4 da divisão são uma sequência: primeiro se subtrai, depois se conta.
Decisão: conforme uma condição se cumpra ou não, executa-se uma parte ou outra (ou uma parte ou nada). “Se $y > m$ , $m$ recebe o valor $y$ ” é uma decisão.
Repetição: enquanto uma condição se cumprir, executa-se uma parte uma e outra vez. O passo 2 da divisão, com seu corpo, é uma repetição.

Cada forma tem uma só entrada e uma só saída, e seu interior pode ser, por sua vez, qualquer uma das três: o corpo de uma repetição pode conter decisões, um ramo de uma decisão pode conter uma repetição, e assim por diante. Se é assim, com as três formas se constroem algoritmos de qualquer complexidade, como com umas poucas peças que se encaixam entre si se constrói qualquer edifício. Que elas bastem para expressar todo algoritmo é um resultado conhecido da teoria da programação (demonstraram-no Corrado Böhm e Giuseppe Jacopini em 1966); aqui não se demonstra, mas todo o curso o confirma: os programas que se escreverão nele, por longos que sejam, não usarão outra coisa senão estas três formas, escritas em C++ como if para a decisão e while ou for para a repetição, nas aulas Decisões e Laços.

Uma notação útil para ver a forma de um algoritmo é o fluxograma: cada instrução é um retângulo, cada condição um losango com duas saídas (cumprida, que a figura rotula $1$ , e não cumprida, $0$ ), e as setas dizem qual é o passo seguinte. É uma notação, não um fim: serve para olhar um algoritmo pequeno de uma vez, mas não escala, e ninguém escreve um programa grande desenhando-o.

ExemploTrês formas e sua composição

A figura desenha as três formas com instruções genéricas $A$ e $B$ e uma condição $c$ , e depois as compõe no diagrama da divisão por subtrações sucessivas.

Demonstração

$A ; B$
Sequência: executa-se $A$ e depois $B$ ; há uma só entrada e uma só saída.
$c = 1 \Rightarrow A, \quad c = 0 \Rightarrow B$
Decisão: se $c$ se cumpre, executa-se $A$ ; se não, $B$ . Os dois ramos se reúnem em uma só saída.
$c, A, c, A, \ldots, c$
Repetição: avalia-se $c$ ; se se cumpre, executa-se $A$ e volta-se a avaliar $c$ ; se não, sai-se. A condição se avalia uma vez mais que o corpo.
$a = b \cdot q + r, \quad 0 \leq r < b$
Composição: a divisão por subtrações sucessivas é uma sequência (os valores iniciais, a repetição, a entrega) cuja repetição tem por corpo outra sequência (subtrair, contar).

Distinguir as três formas em um procedimento escrito em linguagem corrente é o primeiro passo para traduzi-lo. O sinal de uma decisão é um “se”, um “no caso de” ou um “conforme”; o de uma repetição, um “enquanto”, um “até que”, um “para cada” ou um “tantas vezes quanto”. Um procedimento sem nenhuma dessas palavras é uma sequência, e se deve tratar entradas de tamanho variável (uma lista de números, um texto), falta-lhe uma repetição.

Termina?

A finitude é parte da definição de algoritmo, e uma repetição é o único lugar em que ela pode se perder: uma sequência de cinco passos executa cinco passos, e uma decisão executa um de seus ramos; mas uma repetição executa seu corpo tantas vezes quanto a condição se cumprir, e nada garante de antemão que ela deixe de se cumprir.

Para justificar que uma repetição termina, busca-se uma quantidade, calculada com as variáveis, que cumpra duas condições: é um número natural (inteiro e não negativo) enquanto a repetição continua, e decresce estritamente a cada iteração. Se é assim, a repetição termina: uma sucessão de naturais estritamente decrescente não pode ser infinita, porque cada iteração a baixa pelo menos em um e a partir de um natural $n$ não há mais de $n$ degraus até o zero. Essa quantidade se chama variante ou função limitante, e a aula Projetar laços corretos a usará de maneira sistemática.

ExemploA variante da divisão por subtrações

Na divisão por subtrações sucessivas, a variante é $r$ . Enquanto a repetição continua, $r \geq b > 0$ , de modo que $r$ é um natural. A cada iteração, $r$ recebe o valor $r - b$ , e como $b > 0$ (pré-condição), o novo valor é estritamente menor. Portanto, a repetição termina, e o faz no máximo depois de $a$ iterações (de fato, exatamente depois de $q$ iterações, o quociente).

Observe-se onde se usou a pré-condição $b > 0$ . Se o algoritmo for executado com $b = 0$ , o passo 3 deixa $r$ igual, a condição $r \geq 0$ se cumpre sempre e a repetição não termina nunca: o algoritmo não está errado, mas recebeu uma entrada que o contrato excluía. E se $b$ fosse negativo, $r$ cresceria a cada iteração. A pré-condição não é um adorno: é exatamente o que é preciso para que o raciocínio funcione.

As duas condições da variante são necessárias, e é fácil errar em qualquer uma delas. Considere-se este procedimento, que pretende decidir se um natural $n$ é par: “enquanto $n \neq 0$ , $n$ recebe o valor $n - 2$ ; se se chega ao zero, $n$ era par”. A quantidade $n$ decresce a cada iteração, e mesmo assim o procedimento não termina se $n$ é ímpar: com $n = 5$ passa por $3$ , $1$ , $-1$ , $-3$ , e a condição $n \neq 0$ não falha nunca. O que não se cumpre é a outra condição: $n$ deixa de ser natural, porque a condição da repetição não impede que ele desça abaixo do zero. A correção consiste em repetir enquanto $n \geq 2$ e decidir no final segundo o valor que resta, $0$ ou $1$ ; agora $n$ é natural a cada iteração, porque só se subtrai quando $n \geq 2$ , e decresce: o procedimento termina.

Decidir se uma repetição termina nem sempre é fácil. Um exemplo célebre: partindo de um natural $n \geq 1$ , enquanto $n \neq 1$ , se $n$ é par divide-se por dois, e se é ímpar substitui-se por $3n + 1$ . Com $n = 6$ a sucessão é $6, 3, 10, 5, 16, 8, 4, 2, 1$ , e termina. Ninguém encontrou um $n$ para o qual não termine, e verificou-se com computadores para quantidades enormes de valores; mas ninguém conseguiu demonstrar que termine sempre: é a conjectura de Collatz, um problema aberto da matemática. Nenhuma quantidade conhecida decresce a cada iteração. A moral para quem programa é modesta e firme: um algoritmo cuja terminação não se sabe justificar não está terminado.

Erros frequentes

Passos ambíguos. “Repetir várias vezes”, “até que esteja bom”, “tomar um número adequado”. Cada passo deve poder ser executado sem entender o problema; se não, está mal escrito.
Esquecer o caso em que a repetição não se executa. Toda repetição com a condição no começo pode executar seu corpo zero vezes. É preciso perguntar-se sempre o que o algoritmo entrega nesse caso, e o rastreamento com uma entrada mínima responde a isso.
Especificar com um exemplo. “Para 17 e 5 dá 3 e 2” não é uma especificação; a relação se escreve como condição geral, e o exemplo a ilustra.
Confundir o algoritmo com seu programa. Um programa que falha pode ter o algoritmo errado ou a sua escrita errada. Quem não escreveu o algoritmo antes não sabe qual das duas coisas procurar.
Dar a terminação por suposta. Que uma quantidade decresça não basta: ela deve ser, além disso, natural enquanto se repete.

Problemas resolvidos

Problema resolvido 1O maior de três números, com empates

Escrever um algoritmo que cumpra a especificação do máximo de três números da primeira seção, e rastreá-lo à mão para as entradas $(7, 2, 5)$ e $(4, 9, 9)$ .

Solução

$m = x$
Ideia: percorre-se a entrada guardando o maior visto até agora em uma variável $m$ . Primeiro passo: $m$ recebe o valor $x$ . Depois dele, $m$ é o máximo dos dados vistos, que são só $x$ .
$m = \max(x, y, z)$
Segundo passo: se $y > m$ , $m$ recebe o valor $y$ . Terceiro passo: se $z > m$ , $m$ recebe o valor $z$ . Quarto passo: entregar $m$ . São três instruções em sequência, duas delas decisões sem ramo alternativo.
$(x, y, z) = (7, 2, 5) \Rightarrow m = 7$
Rastreamento para $(7, 2, 5)$ : depois do primeiro passo $m = 7$ ; no segundo, $2 > 7$ é falso e $m$ não muda; no terceiro, $5 > 7$ é falso e $m$ não muda. Entrega-se $7$ .
$(x, y, z) = (4, 9, 9) \Rightarrow m = 9$
Rastreamento para $(4, 9, 9)$ : depois do primeiro passo $m = 4$ ; no segundo, $9 > 4$ e $m$ passa a valer $9$ ; no terceiro, $9 > 9$ é falso e $m$ não muda. Entrega-se $9$ , que é correto: o empate não exige tratamento próprio.
$m \geq x, \quad m \geq y, \quad m \geq z$
Justificação: depois de cada passo, $m$ é um dos dados vistos e nenhum deles o supera. É verdade depois do primeiro, e cada decisão o conserva: se o dado novo é maior, passa a ser $m$ ; se não, não supera $m$ . No final foram vistos os três, e $m$ cumpre a pós-condição.
$(x, y, z) = (4, 9, 9) \Rightarrow p \in \{2, 3\}$
Se se tivesse escrito $y \geq m$ em vez de $y > m$ , o resultado seria o mesmo, porque em caso de empate se atribui um valor igual. A escolha entre $>$ e $\geq$ importaria se se pedisse também a posição do máximo: com $>$ se entrega a primeira das posições empatadas, e com $\geq$ a última; a fórmula chama a posição de $p$ .

Problema resolvido 2O ano bissexto, corrigido com um contraexemplo

No calendário gregoriano, um ano é bissexto se é divisível por $4$ , salvo os divisíveis por $100$ , que só o são se também forem divisíveis por $400$ . Um estudante propõe o algoritmo “se o ano é divisível por $4$ , entregar sim; se não, entregar não”. Encontrar um ano em que ele falha e escrever um algoritmo correto, com sua especificação.

Solução

$(4 \mid n \wedge \neg (100 \mid n)) \vee 400 \mid n$
Especificação. Entrada: um inteiro $n \geq 1583$ (o calendário gregoriano vigora desde outubro de 1582). Saída: sim ou não. Relação: a saída é sim exatamente quando $n$ é divisível por $4$ e não por $100$ , ou é divisível por $400$ .
$1900 = 4 \cdot 475, \quad 1900 = 400 \cdot 4 + 300$
O algoritmo proposto acerta na maioria dos anos, e por isso parece correto. Para refutá-lo basta um ano divisível por $100$ e não por $400$ : $1900$ é divisível por $4$ , e o algoritmo diz sim; mas $1900$ não foi bissexto.
$400 \mid n, \quad 100 \mid n, \quad 4 \mid n$
Algoritmo corrigido, em três decisões encadeadas. Passo 1: se $n$ é divisível por $400$ , entregar sim e terminar. Passo 2: se $n$ é divisível por $100$ , entregar não e terminar. Passo 3: se $n$ é divisível por $4$ , entregar sim; se não, entregar não.
$2000, \quad 1900, \quad 2024, \quad 2023$
A ordem das perguntas é essencial: vão da regra mais particular à mais geral. Se se perguntasse primeiro pelo $4$ , o ano $1900$ receberia sim antes de chegar à exceção. Rastreamento para quatro anos, um de cada caso: $2000$ (passo 1: sim), $1900$ (passo 2: não), $2024$ (passo 3: sim), $2023$ (passo 3: não).
$4 \mid 1900 \wedge \neg (400 \mid 1900)$
A lição não é só de calendários: um algoritmo se refuta com um só contraexemplo, e os contraexemplos se buscam nas bordas das regras, não nos casos comuns. Testar com $2024$ , $2020$ e $2016$ não teria descoberto nada.

Problema resolvido 3Quantas iterações dá a divisão por subtrações

Rastrear à mão a divisão por subtrações sucessivas com $a = 20$ e $b = 5$ , e com $a = 0$ e $b = 7$ . Depois, justificar que para toda entrada admissível o algoritmo termina depois de exatamente $q$ iterações e que sua saída cumpre a pós-condição.

Solução

$20 = 5 \cdot 4 + 0$
Rastreamento com $a = 20$ , $b = 5$ : $r$ passa por $20$ , $15$ , $10$ , $5$ , $0$ , e $q$ por $0$ , $1$ , $2$ , $3$ , $4$ . A quinta verificação, $0 \geq 5$ , falha. Saída: $q = 4$ , $r = 0$ . Aqui o caso limite é a divisão exata: a quarta iteração se dá porque $5 \geq 5$ , e por isso a condição deve ser $\geq$ e não $>$ .
$0 = 7 \cdot 0 + 0$
Rastreamento com $a = 0$ , $b = 7$ : a primeira verificação, $0 \geq 7$ , falha; o corpo não se executa nenhuma vez. Saída: $q = 0$ , $r = 0$ , que é correta.
$\dato{conserva}{b \cdot (q + 1) + (r - b) = b \cdot q + r = a}$
Uma relação que se conserva. Antes da primeira iteração, $b \cdot q + r = b \cdot 0 + a = a$ . A cada iteração $r$ diminui em $b$ e $q$ aumenta em $1$ , de modo que $b \cdot q + r$ não muda. Portanto, a igualdade vale depois de cada iteração.
$r_0 > r_1 > r_2 > \cdots \geq 0$
Terminação. Enquanto se repete, $r \geq b > 0$ , e $r$ é um natural; a cada iteração diminui em $b \geq 1$ . Uma sucessão estritamente decrescente de naturais é finita: a repetição termina.
$a = b \cdot q + r, \quad 0 \leq r < b$
Ao terminar, a condição falhou: $r < b$ . Além disso $r \geq 0$ , porque só se subtrai $b$ quando $r \geq b$ . Junto com a relação que se conserva, a saída cumpre a pós-condição; e como $q$ conta as iterações, o número de iterações é o quociente.

Exercícios on-line

Exercício 1Contar as iterações

Rastrear à mão o algoritmo seguinte e escrever no quadro o valor que ele entrega, só o número.

$n$ recebe o valor $29$ , e $k$ recebe o valor $0$ .
Enquanto valer $n > 1$ , repetir os passos 3 e 4; quando deixar de valer, continuar no passo 5.
Se $n$ é par, $n$ recebe o valor $n / 2$ ; se é ímpar, $n$ recebe o valor $n + 1$ .
$k$ recebe o valor $k + 1$ ; voltar ao passo 2.
Entregar $k$ .

O navegador revisa sua resposta na hora, sem avaliá-la.

Escreva aqui sua resposta

Dica

Faça a tabela: $n$ passa de $29$ a $30$ na primeira iteração. Conte uma iteração por cada mudança de $n$ , até que $n$ valha $1$ .

Exercício 2A condição que falta

O algoritmo seguinte, escrito na forma abreviada, deve calcular o quociente e o resto da divisão por subtrações sucessivas, mas falta-lhe a condição da repetição. Substituir a linha de sublinhados pela condição correta, sem mudar o resto.

O navegador revisa sua resposta na hora, sem avaliá-la.

Escreva aqui sua resposta

Dica

Rastreie à mão o algoritmo com $a = 10$ e $b = 5$ : a segunda iteração deve ocorrer ainda que o resto valha exatamente $5$ .

Problemas propostos

Cada problema tem uma dica, que convém abrir só depois de tê-lo tentado, e uma resposta, que aparece depois de abrir a dica.

Problema proposto 1Especificar a ordem de três números

Escrever a especificação do problema “ordenar três números” (entrada, saída e relação) e assinalar que decisões ela obriga a tomar que o enunciado não tomava. Depois, verificar que a especificação descarta estas duas saídas para a entrada $(5, 2, 5)$ : $(2, 5, 6)$ e $(2, 5, 5, 5)$ , e que admite $(2, 5, 5)$ .

Dica

Uma saída “ordenada” pode não ter nada a ver com a entrada. Que condição liga os números da saída aos da entrada, incluídos os repetidos? Crescente ou decrescente? Estrita ou não?

Resposta

Entrada: três números $x$ , $y$ , $z$ . Saída: três números $u$ , $v$ , $w$ . Relação: $u \leq v \leq w$ , e $(u, v, w)$ é uma reordenação de $(x, y, z)$ , isto é, contém os mesmos valores com as mesmas repetições. Decisões que o enunciado não tomava: o sentido (aqui, do menor para o maior); que a ordem não é estrita ( $\leq$ e não $<$ , porque com valores repetidos a ordem estrita é impossível); e que a saída deve ser uma reordenação. $(2, 5, 6)$ está ordenada mas contém um $6$ que não estava; $(2, 5, 5, 5)$ tem quatro valores; $(2, 5, 5)$ cumpre ambas as condições. Sem a condição de reordenação, $(0, 0, 0)$ seria uma saída correta para qualquer entrada.

Problema proposto 2Os algarismos de um número, da direita para a esquerda

Escrever um algoritmo em passos numerados que receba um natural $n$ e entregue seus algarismos do último ao primeiro (para $4072$ , entrega $2$ , $7$ , $0$ , $4$ ), usando só o quociente e o resto da divisão por $10$ . Rastreá-lo à mão para $4072$ e para $0$ , e justificar que termina para todo $n$ .

Dica

O resto da divisão por $10$ é o último algarismo, e o quociente é o número sem ele. Decida se a condição é perguntada antes ou depois de entregar um algarismo, e veja o que ocorre com $n = 0$ , que tem um algarismo.

Resposta

Um algoritmo correto: (1) entregar o resto da divisão de $n$ por $10$ ; (2) $n$ recebe o valor do quociente da divisão de $n$ por $10$ ; (3) se $n > 0$ , voltar ao passo 1; se não, terminar. A pergunta vai depois do corpo, de modo que o corpo se executa pelo menos uma vez: para $n = 0$ entrega $0$ , que é seu único algarismo. Se se perguntasse no começo (“enquanto $n > 0$ ”), para $n = 0$ não se entregaria nada; é o erro de esquecer o caso em que a repetição não se executa. Rastreamento para $4072$ : entregam-se $2$ , $7$ , $0$ , $4$ , e $n$ passa por $407$ , $40$ , $4$ , $0$ . Terminação: a variante é $n$ , um natural; se se volta ao passo 1 é porque $n > 0$ , e para $n \geq 1$ o quociente por $10$ é estritamente menor que $n$ , de modo que $n$ decresce estritamente a cada iteração.

Problema proposto 3O troco em moedas

Dispõe-se de moedas de $50$ , $10$ e $1$ unidades, em quantidade ilimitada. Especificação: entrada, um natural $m$ ; saída, três naturais $c_{50}$ , $c_{10}$ , $c_1$ com $50 c_{50} + 10 c_{10} + c_1 = m$ e a menor quantidade possível de moedas, $c_{50} + c_{10} + c_1$ . Uma pessoa propõe o algoritmo seguinte. Encontrar uma entrada em que ele falha, explicar cada defeito e corrigi-lo.

$c_{50}$ , $c_{10}$ e $c_1$ recebem o valor $0$ .
Se $m \geq 50$ , $c_{50}$ recebe o valor $c_{50} + 1$ e $m$ recebe o valor $m - 50$ .
Enquanto $m > 10$ : $c_{10}$ recebe o valor $c_{10} + 1$ e $m$ recebe o valor $m - 10$ .
Enquanto $m > 0$ : $c_1$ recebe o valor $c_1 + 1$ e $m$ recebe o valor $m - 1$ .
Entregar $c_{50}$ , $c_{10}$ e $c_1$ .

Dica

A soma das moedas sempre é $m$ ; o que pode falhar é a quantidade. Teste um múltiplo exato de $10$ e um valor de mais de $100$ , e pergunte-se que forma de combinar passos o passo 2 usa e qual deveria usar.

Resposta

Há dois defeitos. Primeiro, o passo 3 usa $m > 10$ : com $m = 10$ não entrega nenhuma moeda de $10$ e entrega dez de $1$ , em vez de uma. Segundo, o passo 2 é uma decisão onde faz falta uma repetição: com $m = 120$ , o algoritmo tal como está escrito entrega uma moeda de $50$ , seis de $10$ e dez de $1$ (dezessete moedas), e mesmo com o passo 3 já corrigido entregaria uma de $50$ e sete de $10$ (oito), em vez de duas de $50$ e duas de $10$ (quatro). A entrada $m = 100$ mostra ambos os defeitos: o algoritmo entrega uma de $50$ , quatro de $10$ e dez de $1$ , quinze moedas, em vez de duas. Correção: passo 2, “enquanto $m \geq 50$ , …”; passo 3, “enquanto $m \geq 10$ , …”. Assim corrigido, o algoritmo toma sempre a moeda maior que cabe, e com estas três moedas isso dá a menor quantidade: o algarismo das unidades de $m$ só pode ser pago com moedas de $1$ , e do que resta convém pagar com moedas de $50$ tudo o que for possível, porque cinco de $10$ valem o mesmo que uma de $50$ . Com outras moedas, por exemplo de $1$ , $3$ e $4$ para $m = 6$ , tomar sempre a maior já não dá o mínimo ( $4 + 1 + 1$ contra $3 + 3$ ).