Seleção e Iteração

Ciência da Computação A do AP · Tópico 2

Videoaula para este tópico Abrir a página do vídeo

2.1

Seleção e Repetição em Algoritmos

Programa

Objetivo de Aprendizagem 2.1.A: Representar padrões e algoritmos que envolvem seleção e repetição encontrados no cotidiano usando linguagem escrita ou diagramas.

2.1.A.1 Os blocos de construção de algoritmos incluem sequenciamento, seleção e repetição.
2.1.A.2 Algoritmos podem conter seleção, através da tomada de decisão, e repetição, via laços.
2.1.A.3 Seleção ocorre quando uma escolha sobre como a execução de um algoritmo prosseguirá é baseada em uma decisão verdadeira ou falsa.
2.1.A.4 Repetição é quando um processo se repete até que um resultado desejado seja alcançado.
2.1.A.5 A ordem em que sequenciamento, seleção e repetição são usados contribui para o resultado do algoritmo.

Fonte: College Board AP Course and Exam Description

Um fluxograma com um losango de decisão: a seleção escolhe qual caminho o algoritmo seguirá *Um fluxograma com diamante de decisão: seleção escolhe qual caminho o algoritmo toma

Algoritmos são construídos a partir de três estruturas de controle 控制结构: sequência (passos em ordem), seleção 选择 (escolher um caminho) e iteração 迭代 (repetir passos). Este tópico cobre seleção e iteração – as ferramentas que permitem a um programa tomar decisões e fazer laços.

*As três estruturas de controle: sequência, seleção e iteração

Vocabulário Treinar

Inglês	Chinês	Pinyin
control structures/kənˈtrəʊl ˈstrʌktʃəz/	控制结构	kòng zhì jié gòu
selection/sɪˈlekʃn/	选择	xuǎn zé
iteration/ˌɪtəˈreɪʃn/	迭代	dié dài
boolean expression/ˈbuːlɪən ekˈspreʃn/	布尔表达式	bù ěr biǎo dá shì
relational operators/rɪˈleɪʃənl ˈɒpəreɪtəz/	关系运算符	guān xì yùn suàn fú
if statement/ɪf ˈsteɪtmənt/	条件语句	tiáo jiàn yǔ jù
Logical operators/ˈlɒdʒɪkl ˈɒpəreɪtəz/	逻辑运算符	luó jí yùn suàn fú
short-circuit evaluation/ʃɔːt ˈsɜːkɪt ɪˌvæljuːˈeɪʃn/	短路求值	duǎn lù qiú zhí
De Morgan's laws/də ˈmɔːɡənz lɔːz/	德摩根定律	dé mó gēn dìng lǜ
while loop/waɪl luːp/	循环	xún huán
infinite loop/ˈɪnfɪnət luːp/	无限循环	wú xiàn xún huán

2.2

Expressões Booleanas

Programa

Objetivo de Aprendizagem 2.2.A: Desenvolver código para criar expressões booleanas com operadores relacionais e determinar o resultado dessas expressões.

2.2.A.1 Valores podem ser comparados usando os operadores relacionais == e != para determinar se os valores são iguais. Com tipos primitivos, isso compara os valores primitivos reais. Com tipos de referência, isso compara as referências do objeto.
2.2.A.2 Valores numéricos podem ser comparados usando os operadores relacionais <, >, <= e >= para determinar a relação entre os valores.
2.2.A.3 Uma expressão que envolve operadores relacionais avalia para um valor Booleano.

Fonte: College Board AP Course and Exam Description

*Portas lógicas e meio somador

Uma expressão booleana 布尔表达式 avalia para true ou false, usando operadores relacionais 关系运算符: == (igualdade), != (desigualdade), <, >, <=, >=. Note que == compara valores primitivos mas referências de objeto para objetos, então use .equals para Strings.

*As três famílias de operadores: aritméticos, relacionais e lógicos

Explorar

Explorar a tabela verdade AND

Uma expressão Booleana avalia para true ou false. AND é verdadeiro apenas quando ambos os operandos são verdadeiros; alterne as entradas para ver todos os quatro casos.

2.3

A instrução if

Programa

Objetivo de Aprendizagem 2.3.A: Desenvolver código para representar processos lógicos de ramificação usando instruções de seleção e determinar o resultado desses processos.

2.3.A.1 Instruções de seleção alteram a execução sequencial de instruções.
2.3.A.2 Uma instrução if é um tipo de instrução de seleção que afeta o fluxo de controle executando diferentes segmentos de código com base no valor de uma expressão Booleana.
2.3.A.3 Uma seleção de um caminho (instrução if) é usada quando há um segmento de código a ser executado sob uma certa condição. Neste caso, o corpo é executado apenas quando a expressão Booleana é true.
2.3.A.4 Uma seleção de dois caminhos (instrução if-else) é usada quando há dois segmentos de código: um para ser executado quando a expressão Booleana é true e outro segmento para quando a expressão Booleana é false. Neste caso, o corpo do if é executado quando a expressão Booleana é true, e o corpo do else é executado quando a expressão Booleana é false.

Fonte: College Board AP Course and Exam Description

Uma instrução if 条件语句 executa um bloco apenas quando sua condição é verdadeira; um else opcional oferece uma alternativa:

if (score >= 60) {
    System.out.println("Pass");
} else {
    System.out.println("Fail");
}

Semáforos: a seleção escolhe qual ramo é executado, assim como as instruções if escolhem caminhos de código *Semáforos: seleção escolhe qual ramo é executado, assim como instruções if escolhem caminhos de código

Explorar

Ver qual ramificação um if escolhe

Uma instrução se executa seu corpo apenas quando a condição é verdadeira, caso contrário pula para else. Deslize a pontuação pelos limites e observe a nota mudar.

2.4

Instruções if Aninhadas

Programa

Objetivo de Aprendizagem 2.4.A: Desenvolver código para representar processos lógicos de ramificação aninhados e determinar o resultado desses processos.

2.4.A.1 Instruções if aninhadas consistem em instruções if, if-else ou if-else-if dentro de instruções if, if-else ou if-else-if.
2.4.A.2 A expressão Booleana da instrução if aninhada interna é avaliada apenas se a expressão Booleana da instrução externa if avaliar para true.
2.4.A.3 Uma seleção de múltiplos caminhos (instrução if-else-if) é usada quando há uma série de expressões com diferentes segmentos de código para cada condição. A seleção de múltiplos caminhos é realizada de forma que nenhum mais de um segmento de código seja executado com base na primeira expressão que avalia para true. Se nenhuma expressão avaliar para true e houver uma instrução else final, então o corpo da else é executado.

Fonte: College Board AP Course and Exam Description

Colocar um if dentro de outro, ou encadeando com else if, testa vários casos em ordem. Apenas o primeiro ramo correspondente é executado:

if (g >= 90) grade = 'A';
else if (g >= 80) grade = 'B';
else grade = 'C';

2.5

Expressões Booleanas Compostas

Programa

Objetivo de Aprendizagem 2.5.A: Desenvolver código para representar expressões Booleanas compostas e determinar o resultado dessas expressões.

2.5.A.1 Operadores lógicos ! (not), && (and) e || (or) são usados com expressões Booleanas. A expressão !a avalia para true se a for false e avalia para false caso contrário. A expressão a && b avalia para true se tanto a quanto b forem true e avalia para false caso contrário. A expressão a || b avalia para true se a for true, b for true, ou ambos, e avalia para false caso contrário. A ordem de precedência para avaliar operadores lógicos é ! (not), && (and), depois || (or). Uma expressão envolvendo operadores lógicos avalia para um valor Booleano.
2.5.A.2 Avaliação de curto-circuito ocorre quando o resultado de uma operação lógica usando && ou || pode ser determinado avaliando apenas a primeira expressão Booleana. Neste caso, a segunda expressão Booleana não é avaliada.

Fonte: College Board AP Course and Exam Description

*Avaliação de curto-circuito

Operadores lógicos 逻辑运算符 combinam condições: && (e – ambos verdadeiros), || (ou – pelo menos um verdadeiro), ! (não – inverso). Java usa avaliação de curto-circuito 短路求值: && para se a esquerda for falsa, e || para se a esquerda for verdadeira – útil para proteger contra erros, p. ex. if (n != 0 && total / n > 5).

2.6

Comparando Expressões Booleanas

Programa

Objetivo de Aprendizagem 2.6.A: Comparar expressões Booleanas equivalentes.

2.6.A.1 Duas expressões Booleanas são equivalentes se avaliarem para o mesmo valor em todos os casos. Tabelas-verdade podem ser usadas para provar que expressões Booleanas são equivalentes.
2.6.A.2 A lei de De Morgan pode ser aplicada a expressões Booleanas para criar expressões Booleanas equivalentes. Sob a lei de De Morgan, a expressão Booleana !(a && b) é equivalente a !a || !b e a expressão Booleana !(a || b) é equivalente a !a && !b.

Objetivo de Aprendizagem 2.6.B: Desenvolver código para comparar referências de objetos usando expressões Booleanas e determinar o resultado dessas expressões.

2.6.B.1 Duas variáveis diferentes podem conter referências para o mesmo objeto. Referências de objeto podem ser comparadas usando == e !=.
2.6.B.2 Uma referência de objeto pode ser comparada com null, usando == ou !=, para determinar se a referência realmente referencia um objeto.
2.6.B.3 Classes frequentemente definem seu próprio método equals, que pode ser usado para especificar os critérios de equivalência para dois objetos da classe. A equivalência de dois objetos é mais frequentemente determinada usando atributos dos dois objetos.
- Instrução de exclusão: Substituir o método equals está fora do escopo do curso e exame AP Computer Science A.

Fonte: College Board AP Course and Exam Description

Leis de De Morgan 德摩根定律 reescrevem negações: !(a && b) é igual a !a || !b, e !(a || b) é igual a !a && !b. Duas expressões booleanas são equivalentes se derem o mesmo resultado para toda entrada – uma tabela-verdade prova isso. Simplificar condições dessa forma é uma tarefa comum de prova.

2.7

Laços while

Programa

Objetivo de Aprendizagem 2.7.A: Identificar quando um processo iterativo é necessário para obter um resultado desejado.

2.7.A.1 Iteração é uma forma de repetição. Instruções de iteração mudam o fluxo de controle repetindo um segmento de código zero ou mais vezes enquanto a expressão Booleana que controla o laço avalia para true.
2.7.A.2 Um laço infinito ocorre quando a expressão Booleana em uma instrução iterativa sempre avalia para true.
2.7.A.3 O corpo do laço de uma instrução iterativa não será executado se a expressão Booleana avaliar inicialmente para false.
2.7.A.4 Erros off by one ocorrem quando a instrução de iteração executa o laço uma vez a mais ou uma vez a menos.

Objetivo de Aprendizagem 2.7.B: Desenvolver código para representar processos iterativos usando laços while e determinar o resultado desses processos.

2.7.B.1 Um laço while é um tipo de instrução iterativa. Em laços while, a expressão Booleana é avaliada antes de cada iteração do corpo do laço, incluindo a primeira. Quando a expressão avalia para true, o corpo do laço é executado. Isso continua até que a expressão Booleana avalie para false, momento em que a iteração termina.

Fonte: College Board AP Course and Exam Description

Um laço while 循环 repete enquanto sua condição permanece verdadeira, testando antes de cada passagem. Você deve alterar algo dentro para que o laço eventualmente pare, ou ele se torna um laço infinito 无限循环:

Os três tipos de loop diferem no local onde a condição é testada *Os três tipos de laço diferem em onde a condição é testada

int i = 0;
while (i < 5) {
    System.out.println(i);
    i++;
}

Explorar

Rastrear um loop while

Um loop while repete enquanto sua condição permanecer verdadeira, atualizando suas variáveis a cada passagem. Avance para ver a soma dos quadrados se acumular.

2.8

Laços for

Programa

Objetivo de Aprendizagem 2.8.A: Desenvolver código para representar processos iterativos usando laços for e determinar o resultado desses processos.

2.8.A.1 Um laço for é um tipo de instrução iterativa. Há três partes no cabeçalho de um laço for: a inicialização, a expressão Booleana e a atualização.
2.8.A.2 Em um laço for, a instrução de inicialização é executada apenas uma vez antes da primeira avaliação da expressão Booleana. A variável sendo inicializada é referida como uma variável de controle de laço. A expressão Booleana é avaliada imediatamente após a variável de controle do laço ser inicializada e depois após cada execução da instrução de incremento até que esteja false. Em cada iteração, a atualização é executada após todo o corpo do laço ser executado e antes que a expressão Booleana seja avaliada novamente.
2.8.A.3 Um laço for pode ser reescrito como um laço while equivalente (e vice-versa).

Fonte: College Board AP Course and Exam Description

Um laço for empacota inicialização, condição e atualização em uma linha – melhor quando você conhece a contagem:

for (int i = 0; i < n; i++) {
    // runs n times, i = 0..n-1
}

Um for e um while equivalentes fazem o mesmo trabalho; seja capaz de converter entre eles.

Uma linha de montagem: loops repetem um processo para cada item, como for e while *Uma linha de montagem: laços repetem um processo para cada item, como for e while

Explorar

Rastrear um loop for

Um loop for executa um número fixo de vezes, com seu contador passando por uma faixa. Observe o contador e o total acumulado avançarem uma passagem de cada vez.

2.9

Construindo Algoritmos Completos de Seleção e Iteração

Programa

Objetivo de Aprendizagem 2.9.A: Desenvolver código para algoritmos padrão e originais (sem estruturas de dados) e determinar o resultado desses algoritmos.

2.9.A.1 Existem algoritmos padrão para:
- identificar se um número inteiro é ou não divisível por outro número inteiro sem resto
- identificar os dígitos individuais em um número inteiro
- determinar a frequência com que um critério específico é atendido
- determinar um valor mínimo ou máximo
- computar uma soma ou média

Fonte: College Board AP Course and Exam Description

Combine laços e condições para resolver problemas reais – contar, somar, encontrar um máximo ou testar uma propriedade:

int max = arr[0];
for (int k = 1; k < arr.length; k++) {
    if (arr[k] > max) max = arr[k];
}

Dois padrões inteiros que a prova testa diretamente usam % e /. Para ler os dígitos de um inteiro um de cada vez, pegue repetidamente n % 10 (o último dígito) e depois n = n / 10 (remova-o). Para testar divisibilidade, n % d == 0 significa que n é divisível por d sem resto. Combine-os com um contador para encontrar a frequência com que algum critério é atendido.

Padrões padrão como total acumulado, contador ou flag 标志 (um booleano que registra se algo aconteceu) ocorrem constantemente ao longo do curso.

Vocabulário Treinar

Inglês	Chinês	Pinyin
flag/flæɡ/	标志	biāo zhì
nested loop/ˈnestɪd luːp/	嵌套循环	qiàn tào xún huán
Run-time analysis/rʌn taɪm əˈnæləsɪs/	运行时间分析	yùn xíng shí jiān fēn xī

2.10

Algoritmos de String

Programa

Objetivo de Aprendizagem 2.10.A: Desenvolver código para algoritmos padrão e originais que envolvem strings e determinar o resultado desses algoritmos.

2.10.A.1 Existem algoritmos padrão de string para:
- encontrar se um ou mais substrings possuem uma propriedade particular
- determinar o número de substrings que atendem a critérios específicos
- criar uma nova string com os caracteres invertidos

Fonte: College Board AP Course and Exam Description

Percorra uma string por índice para processar cada caractere:

for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    // count vowels, reverse, check for a substring, ...
}

Tarefas típicas: contar ocorrências, construir uma cópia invertida ou filtrada, ou testar se uma string contém outra.

2.11

Iteração Aninhada

Programa

Objetivo de Aprendizagem 2.11.A: Desenvolver código para representar processos iterativos aninhados e determinar o resultado desses processos.

2.11.A.1 Instruções de iteração aninhadas são instruções de iteração que aparecem no corpo de outra instrução de iteração. Quando um laço está aninhado dentro de outro laço, o laço interno deve completar todas as suas iterações antes que o laço externo possa continuar para sua próxima iteração.

Fonte: College Board AP Course and Exam Description

Um laço aninhado 嵌套循环 coloca um laço dentro de outro; o laço interno completa totalmente para cada passagem do externo. Se o externo roda $n$ vezes e o interno $m$ vezes, o corpo roda $n\times m$ vezes – a base para processar grades e comparar todos os pares.

2.12

Análise Informal de Tempo de Execução

Programa

Objetivo de Aprendizagem 2.12.A: Calcular contagens de execução de instruções e comparação informal de tempo de execução de instruções iterativas.

2.12.A.1 Uma contagem de execução de instrução indica o número de vezes que uma instrução é executada pelo programa. As contagens de execução de instruções são frequentemente calculadas informalmente através de rastreamento e análise das instruções iterativas.

Fonte: College Board AP Course and Exam Description

*Taxas de crescimento Big-O

Análise de tempo de execução 运行时间分析 conta quantos passos básicos um algoritmo leva conforme o tamanho da entrada $n$ cresce. Conte as execuções da instrução mais interna: um único laço sobre $n$ itens é linear ($n$ passos); dois laços aninhados sobre $n$ são quadráticos ($n^2$). Essa contagem informal permite comparar a eficiência de dois algoritmos.

Como o tempo de execução cresce com o número de elementos n

Habilidade para prova: em um loop aninhado, saber declarar quantas vezes a instrução interna é executada em termos dos limites dos loops — uma questão de múltipla escolha frequente.

Exemplo resolvido. Quantas estrelas isso imprime?

for (int i = 0; i < 4; i++)
    for (int j = 0; j < i; j++)
        System.out.print("*");

O loop interno executa i vezes para cada i externo: 0 + 1 + 2 + 3 = 6 estrelas. Quando o limite interno é a variável externa, o total é a soma triangular $0+1+\dots+(n-1)=\dfrac{n(n-1)}{2}$ – aqui $\dfrac{4\times3}{2}=6$ – e não o total $n^2=16$ de um loop aninhado retangular.

Explorar

Comparar como os algoritmos escalam

Tempo de execução descreve como o número de etapas cresce com o tamanho da entrada $n$. Aumente $n$ e observe uma linear $O(n)$ ultrapassar longe uma quadrática $O(n^2)$.

2.12

Dicas de prova

Obter as condições de fronteira corretas: use < vs <= deliberadamente, e observe a primeira e a última iteração de todo loop (off-by-one é o bug clássico).
Construa condições compostas com &&, ||, ! e lembre-se da avaliação curto-circuito (coloque a verificação de nulo primeiro).
Rastreie loops aninhados contando quantas vezes o corpo interno roda no total.
Escolha a estrutura certa — if/else if para intervalos, um loop para repetição — e evite um loop infinito atualizando a variável do loop.
Aplique as leis de De Morgan ao simplificar ou negar uma condição booleana.

Aulas interativas sobre este tópico

Passe por ele passo a passo, com exercícios de verificação instantânea.

Provas Anteriores

Mais tópicos em Ciência da Computação A do AP

Coleções de Dados