Fig. 1
Arraste para girar · Shift + arraste para mover · clique para desmontar
Role para virar a página
Computer Science A · AP Computer Science A
if, while e for
Um programa executa suas instruções uma após a outra, em ordem. Duas coisas mudam essa ordem: a seleção escolhe quais instruções são executadas, e a iteração executa instruções de novo.
O programa da figura começa com n = 5. Enquanto n não for 1, ele divide n ao meio se for par, ou o triplica e soma 1 se for ímpar, e conta um passo. O losango de cima é a pergunta do laço; o losango abaixo dele é a do if. A ficha vermelha é o ponto de execução, e o código ao lado acende a linha em execução.
int n = 5; int steps = 0; while (n != 1) { if (n % 2 == 0) { n = n / 2; } else { n = 3 * n + 1; } steps++; } System.out.println(steps); n passa por 5, 16, 8, 4, 2, 1. A condição do laço é verificada 6 vezes: verdadeira 5 vezes, depois falsa uma vez, e o programa imprime 5.
Este capítulo é a Unidade 2 do AP Computer Science A, 25–35% da nota de múltipla escolha: expressões booleanas e instruções if (2.1–2.6), laços while e for (2.7–2.8), os algoritmos padrão construídos com eles (2.9–2.10), laços dentro de laços (2.11) e a contagem de quantas vezes uma instrução é executada (2.12).
os três blocos de construção
Todo algoritmo é construído com três coisas: sequenciação (passos em ordem), seleção (uma decisão) e repetição (um laço).
A seleção acontece quando o rumo de um algoritmo depende de uma decisão verdadeira ou falsa. A repetição é um processo que se repete até se chegar ao resultado desejado. As duas aparecem em instruções do dia a dia: “se estiver chovendo, leve um guarda-chuva” é seleção; “mexa até o açúcar dissolver” é repetição.
Os algoritmos podem ser escritos em palavras ou desenhados como um fluxograma: uma caixa para cada passo, um losango para cada decisão de verdadeiro ou falso e uma seta voltando para cima para a repetição. A figura agora escreve o mesmo algoritmo em palavras: “n é par?”, “reduza à metade”, “conte um passo”. O código diz exatamente a mesma coisa em Java.
A ordem dos passos muda o resultado. Estes dois trechos têm as mesmas instruções:
int x = 3; x = x * 2; x = x + 1;
int x = 3; x = x + 1; x = x * 2;
O primeiro deixa x em 7; o segundo, em 8. Na figura, contar um passo depois do laço em vez de dentro dele imprimiria 1, por mais que o laço rodasse.
operadores relacionais
Uma expressão booleana resulta em um de dois valores, true ou false. As mais simples comparam dois valores com um operador relacional.
== e != testam se dois valores são iguais ou diferentes. <, >, <= e >= comparam números. Com tipos primitivos como int, double e boolean, == compara os valores em si. Com tipos de referência, compara as referências: se duas variáveis se referem ao mesmo objeto (2.6).
Na figura, a guarda 7 e b assume os valores 4, 7, 9. Cada comparação produz um bloco, vermelho para verdadeiro:
| b = 4 | b = 7 | b = 9 | |
|---|---|---|---|
a == b | false | true | false |
a != b | true | false | true |
a < b | false | false | true |
a > b | true | false | false |
a <= b | false | true | true |
a >= b | true | true | false |
= atribui; == compara. Um resultado booleano pode ser guardado como qualquer outro valor: boolean same = a == b;
seleção unilateral e bilateral
As instruções de seleção mudam a execução sequencial das instruções. Uma instrução if executa trechos de código diferentes conforme o valor de uma expressão booleana.
Uma seleção unilateral (um if) tem um trecho, executado só quando a condição é verdadeira:
if (temp >= 30) { System.out.println("hot"); } System.out.println("done"); Com temp em 34, ela imprime hot then done; em 22, só done. A última linha vem depois do if, então sempre é executada.
Uma seleção bilateral (um if-else) tem dois trechos: o corpo do if quando a condição é verdadeira, o corpo do else quando é falsa. Exatamente um deles é executado.
if (temp >= 30) { System.out.println("hot"); } else { System.out.println("mild"); } System.out.println("done"); A figura envia duas temperaturas por ele. Em 34, a ficha segue a pista verdadeira e imprime hot; em 22, a pista falsa, mild. Depois as duas imprimem done.
if, else if, else
Uma seleção múltipla (if-else-if) testa uma série de condições em ordem. A primeira que é verdadeira executa seu trecho, e no máximo um trecho é executado.
if (score >= 90) { grade = "A"; } else if (score >= 80) { grade = "B"; } else if (score >= 70) { grade = "C"; } else { grade = "F"; } A figura solta três notas pela cadeia. 83 não passa em score >= 90, passa em score >= 80 e é capturada: conceito "B". As condições abaixo nunca são verificadas. 95 é capturada pelo primeiro portão, "A". 64 não passa em nenhuma das três, então o else final é executado: "F". Sem um else final, um valor que falha em todas as condições não executa trecho nenhum.
Como a primeira condição verdadeira vence, a ordem importa. Teste score >= 70 primeiro e 95 recebe "C": toda nota de 70 ou mais para no primeiro portão. Coloque primeiro o teste mais exigente.
um if dentro de um if
As instruções if aninhadas são instruções if, if-else ou if-else-if dentro de outra instrução if, if-else ou if-else-if.
if (age >= 16) { if (hasPermit) { System.out.println("may drive"); } else { System.out.println("needs a permit"); } } System.out.println("done"); A condição interna é avaliada somente se a externa for verdadeira. A figura passa três pessoas por ela. Idade 17 com habilitação passa nas duas e imprime may drive. Idade 17 sem ela passa no teste externo e falha no interno: needs a permit. Idade 14 falha no teste externo, então a ficha contorna a caixa inteira: hasPermit nem chega a ser olhado, e só done é impresso.
As chaves decidem a qual if um else pertence. Aqui o else está dentro das chaves externas, então forma par com if (hasPermit): quem tem menos de 16 não recebe mensagem nenhuma sobre habilitação.
!, && and ||
Os operadores lógicos ! (não), && (e) e || (ou) combinam expressões booleanas em uma que também é verdadeira ou falsa.
!a é verdadeira quando a é falsa, e falsa caso contrário. a && b é verdadeira só quando as duas são verdadeiras. a || b é verdadeira quando a é verdadeira, b é verdadeira, ou as duas. A figura percorre todas as combinações, uma linha de cada vez:
| a | b | a && b | a || b | !a |
|---|---|---|---|---|
| true | true | true | true | false |
| true | false | false | true | false |
| false | true | false | true | true |
| false | false | false | false | true |
A ordem de precedência é ! primeiro, depois &&, depois ||. Então, com a = false, b = true, c = false, a expressão !a || b && c significa (!a) || (b && c): true. Agrupá-la como (!a || b) && c dá false. Parênteses deixam a ordem clara.
Os operadores relacionais vêm antes dos lógicos, então x > 0 && x < 10 compara primeiro e combina depois: é verdadeira para todo x estritamente entre 0 e 10.
o lado direito pode nunca ser executado
Quando o operando esquerdo de && ou || já decide o resultado, o Java não avalia o direito. Isso é a avaliação em curto-circuito.
false && anything é falsa, e true || anything é verdadeira, seja qual for o lado direito. Então o lado direito é ignorado. A figura avalia duas expressões, primeiro com x = 4, depois com x = 0:
x != 0 && 10 / x > 2 x == 0 || 10 / x > 2
Com x = 4, os dois lados das duas são executados. 10 / 4 é 2 (divisão inteira), não mais que 2, então a primeira é false e a segunda também.
Com x = 0, x != 0 é falsa, então a primeira é false de imediato; e x == 0 é verdadeira, então a segunda é true de imediato. Em nenhuma delas 10 / x é executada, o que é bom: dividir um int por zero lança uma ArithmeticException.
Isso faz do operando esquerdo uma proteção. Escrita ao contrário, 10 / x > 2 && x != 0 divide primeiro e quebra quando x é 0.
tabelas-verdade e leis de De Morgan
Duas expressões booleanas são equivalentes se resultam no mesmo valor em todos os casos. Uma tabela-verdade, com uma linha para cada combinação de entradas, pode provar isso.
As leis de De Morgan dão duas equivalências:
!(a && b) é equivalente a !a || !b !(a || b) é equivalente a !a && !b
Para levar um ! para dentro de parênteses, negue cada parte e troque && por ||, ou || por &&. Na figura, cada coluna da segunda expressão desliza sobre a primeira: as cores coincidem em todas as linhas.
| a | b | !(a && b) | !a || !b | !(a || b) | !a && !b |
|---|---|---|---|---|---|
| true | true | false | false | false | false |
| true | false | true | true | false | false |
| false | true | true | true | false | false |
| false | false | true | true | true | true |
Esquecer de trocar o operador quebra a equivalência: !(a && b) e !a && !b diferem em 2 das 4 linhas. Uma comparação negada inverte o operador: !(x > 5) é x <= 5. Então !(x >= 1 && x <= 10) é equivalente a x < 1 || x > 10.
== contra equals
Duas variáveis diferentes podem guardar referências ao mesmo objeto. == e != em referências perguntam se elas se referem ao mesmo objeto, não se dois objetos têm o mesmo conteúdo.
String s1 = new String("atlas"); String s2 = s1; String s3 = new String("atlas"); String s4 = null; s2 = s1 copia a referência, então s1 e s2 apontam para um objeto: s1 == s2 é true. s3 se refere a um segundo objeto com as mesmas letras: s1 == s3 é false.
As classes costumam definir um método equals que diz quando dois objetos contam como iguais, geralmente comparando seus atributos. O de Fio compara os caracteres, então s1.equals(s3) é true. Compare strings com equals, nunca com ==.
Uma referência pode ser comparada com null usando == ou !=, para saber se ela se refere a algum objeto: s4 == null é true. (Sobrescrever o método equals está fora do escopo do curso.)
verificar, executar, verificar de novo
A iteração é uma forma de repetição: uma instrução de iteração repete um trecho de código zero ou mais vezes, enquanto sua expressão booleana for verdadeira.
Em um laço while, a expressão booleana é avaliada antes de cada passagem pelo corpo, inclusive a primeira. Enquanto ela for verdadeira, o corpo é executado; quando for falsa, o laço termina e o programa continua depois dele.
int sum = 0; int k = 1; while (k <= 4) { sum += k; k++; } System.out.println(sum); Uma tabela de rastreio registra as variáveis a cada vez que a condição é verificada. A figura a preenche linha por linha:
| k | sum | k <= 4 |
|---|---|---|
| 1 | 0 | true |
| 2 | 1 | true |
| 3 | 3 | true |
| 4 | 6 | true |
| 5 | 10 | false |
A condição é verificada 5 vezes e o corpo é executado 4 vezes: a última verificação é a que dá falso. O laço termina com k = 5, e 10 é impresso.
nunca, para sempre, um a menos
A maioria dos bugs de laço é de um de três tipos: o laço nunca executa, nunca para, ou executa uma vez a mais ou a menos.
Se a expressão booleana for falsa na primeira vez, o corpo nunca é executado. while (k < 5) com k em 10 verifica uma vez e segue em frente (linha de cima).
Um laço infinito acontece quando a expressão booleana sempre resulta em verdadeiro. Na linha do meio, k passa por 1, 3, 5, 7, 9, … e nunca é 6, então while (k != 6) nunca se torna falsa. Um laço cujo corpo nunca altera as variáveis da sua condição faz o mesmo.
Um erro de off-by-one é um laço que executa uma vez a mais ou uma vez a menos. Feito para imprimir de 1 a 5, o laço de baixo imprime 1234: while (k < 5) para antes de 5. k <= 5 resolve.
int k = 1; while (k < 5) { System.out.print(k); k++; } Verifique um laço nas suas bordas: a primeira passagem, a última passagem e a verificação que o encerra.
inicialização, expressão booleana, atualização
Um laço for coloca as três partes de um laço de contagem no cabeçalho: a inicialização, a expressão booleana e a atualização.
for (int i = 0; i < 3; i++) { System.out.println(i); } A inicialização é executada uma vez, antes da primeira verificação. A variável que ela define é a variável de controle do laço. A expressão booleana é avaliada logo depois da inicialização e de novo depois de cada atualização, até ser falsa. Em cada passagem, a atualização é executada depois do corpo inteiro e antes da próxima verificação.
A ficha da figura segue inicialização → verificação → corpo → atualização → verificação …. As contagens sob cada estação: inicialização 1, verificação 4, corpo 3, atualização 3. Ele imprime 0, 1, 2, cada um em sua própria linha.
Um laço for pode ser reescrito como um laço while equivalente, e vice-versa:
int i = 0; while (i < 3) { System.out.println(i); i++; } Uma diferença: i declarada no cabeçalho do for existe só dentro do laço; declarada antes de um laço while, ainda existe depois dele.
% 10, / 10 and % k
Dois algoritmos padrão usam o operador resto: desmontar um inteiro dígito por dígito e testar se um inteiro é divisível exatamente por outro.
Para um int n positivo, n % 10 é o seu último dígito e n / 10 (divisão inteira) é n sem esse dígito. Repita até n ser 0:
| n | n % 10 | n / 10 |
|---|---|---|
| 3725 | 5 | 372 |
| 372 | 2 | 37 |
| 37 | 7 | 3 |
| 3 | 3 | 0 |
int n = 3725; int sum = 0; int max = 0; int odd = 0; while (n > 0) { int d = n % 10; sum += d; if (d > max) { max = d; } if (d % 2 == 1) { odd++; } n /= 10; } A figura descasca os dígitos de 3725 da direita para a esquerda, 5, 2, 7, 3, e cada um passa por d.
a % b == 0 é verdadeira exatamente quando a é divisível por b. 3725 % 5 é 0, então 3725 é divisível por 5; 3725 % 3 é 2, então não é divisível por 3. O mesmo teste com 2 separa pares de ímpares, como d % 2 == 1 faz no laço.
acumulando enquanto o laço roda
Mais três algoritmos padrão guardam um valor acumulado em uma variável declarada antes do laço e atualizada dentro dele: uma soma, um mínimo ou máximo e uma contagem.
Uma soma começa em 0 e adiciona cada valor: sum += d. Para 3725, sum termina em 17.
Uma média é a soma dividida pela quantidade de valores. Cuidado com a divisão inteira:
double avg = (double) sum / 4; int avgInt = sum / 4;
avg é 4.25; avgInt é 4, com a parte fracionária descartada. Faça a conversão de tipo antes de dividir, não depois.
Um máximo guarda o maior valor até agora e o substitui sempre que aparece um maior: if (d > max). Aqui max termina em 7. Comece com o primeiro valor, ou com um valor abaixo do qual nenhum valor real pode estar: 0 funciona só porque os dígitos nunca são negativos; em geral, use Integer.MIN_VALUE. Um mínimo é a imagem espelhada: começa em Integer.MAX_VALUE e testa <; o menor dígito é 2.
Uma contagem de quantas vezes um critério é atendido começa em 0 e soma 1 dentro de um if: if (d % 2 == 1) conta os dígitos ímpares, 3 deles.
inverter e contar substrings
Algoritmos com strings percorrem um índice ao longo de uma string e pegam uma substring em cada posição: para construir uma nova string ou para testar ou contar substrings com alguma propriedade.
Para inverter uma string, coloque cada caractere na frente do que já foi construído. substring(i, i + 1) é o único caractere no índice i:
String word = "drawer"; String rev = ""; for (int i = 0; i < word.length(); i++) { rev = word.substring(i, i + 1) + rev; } rev cresce "d", "rd", "ard", "ward", "eward", "reward". (rev = rev + word.substring(i, i + 1) copiaria a palavra sem mudá-la.)
Para contar substrings que atendem a um critério, deslize uma janela ao longo da string e teste cada uma:
String s = "banana"; int count = 0; for (int i = 0; i < s.length() - 1; i++) { if (s.substring(i, i + 2).equals("an")) { count++; } } A janela substring(i, i + 2) olha para "ba", "an", "na", "an", "na": 2 coincidem, então count é 2. A última janela começa no índice 4, então i deve parar abaixo de s.length() - 1; um passo além, substring(5, 7) ultrapassa o fim e lança uma StringIndexOutOfBoundsException.
Compare substrings com equals. Para descobrir se alguma substring tem a propriedade, o mesmo laço pode parar na primeira encontrada, ou indexOf devolve onde uma dada substring aparece pela primeira vez, −1 se não aparecer em lugar nenhum.
um laço dentro de um laço
Iteração aninhada é um laço no corpo de outro laço. O laço interno executa todas as suas iterações antes de o laço externo passar para a próxima.
for (int r = 0; r < 3; r++) { for (int c = 0; c < 4; c++) { System.out.print(r * c + " "); } System.out.println(); } Para r = 0, o laço interno executa c de 0 até 3; depois println termina a linha, e só então r passa a 1. A figura acende a grade célula por célula, linha após linha: o corpo interno executa 3 × 4 = 12 vezes e imprime
0 0 0 0 0 1 2 3 0 2 4 6
Os limites do laço interno podem depender da variável externa. Aqui o laço interno executa r + 1 vezes, então as passagens são 1, 2, 3, 4:
int count = 0; for (int r = 0; r < 4; r++) { for (int c = 0; c <= r; c++) { count++; } } count termina em 10, um triângulo em vez de um retângulo.
contar quantas vezes uma instrução executa
A contagem de execuções de uma instrução é o número de vezes que ela executa. Costuma-se encontrá-la de modo informal, rastreando algumas passagens e raciocinando sobre os laços.
for (int i = 0; i < n; i++) { count++; } Com i de 0 até n − 1, count++ executa n vezes. A verificação i < n executa n + 1 vezes: uma a mais, para encerrar o laço.
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { count++; } } Em laços aninhados, cada uma das n passagens externas executa o laço interno n vezes: count++ executa n × n vezes. Para n = 6 isso dá 6 contra 36; para n = 8, 8 contra 64. A figura cresce nos dois casos conforme n sobe: dobrar n dobra um e quadruplica o outro.
Conte a partir dos limites do laço. for (int i = 1; i <= n; i++) também executa n vezes; i < n começando em 1 executa n − 1; um triângulo como o da última página executa 1 + 2 + … + n vezes. Comparar essas contagens é a maneira de dizer que um laço é mais rápido que outro sem usar cronômetro.