Selección e iteración

AP Ciencias de la Computación A · Tema 2

Lección de video para este tema Abrir la página de video

2.1

Selección e Iteración en Algoritmos

Syllabus

Objetivo de aprendizaje 2.1.A: Representar patrones y algoritmos que involucran selección y repetición presentes en la vida cotidiana utilizando lenguaje escrito o diagramas.

2.1.A.1 Los bloques de construcción de los algoritmos incluyen secuencia, selección y repetición.
2.1.A.2 Los algoritmos pueden contener selección, a través de la toma de decisiones, y repetición, mediante bucles.
2.1.A.3 La selección ocurre cuando una elección sobre cómo procederá la ejecución de un algoritmo se basa en una decisión verdadera o falsa.
2.1.A.4 La repetición es cuando un proceso se repite hasta alcanzar un resultado deseado.
2.1.A.5 El orden en que se utilizan la secuencia, la selección y la repetición contribuye al resultado del algoritmo.

Fuente: College Board AP Course and Exam Description

Un diagrama de flujo con un rombo de decisión: la selección elige qué camino sigue el algoritmo

Los algoritmos se construyen a partir de tres estructuras de control: secuencia (pasos en orden), selección (elegir una ruta) e iteración (repetir pasos). Este tema cubre la selección y la iteración, las herramientas que permiten a un programa tomar decisiones y repetir bloques de código.

Las tres estructuras de control: secuencia, selección e iteración

Vocabulario Entrenar

Inglés	Chino	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
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.2

Expresiones Booleanas

Syllabus

Objetivo de Aprendizaje 2.2.A: Desarrollar código para crear expresiones booleanas con operadores relacionales y determinar el resultado de estas expresiones.

2.2.A.1 Los valores se pueden comparar utilizando los operadores relacionales == y != para determinar si los valores son iguales. Con tipos primitivos, esto compara los valores primitivos reales. Con tipos de referencia, esto compara las referencias del objeto.
2.2.A.2 Los valores numéricos se pueden comparar utilizando los operadores relacionales <, >, <= y >= para determinar la relación entre los valores.
2.2.A.3 Una expresión que involucra operadores relacionales se evalúa como un valor booleano.

Fuente: College Board AP Course and Exam Description

Compuertas lógicas y el sumador medio

Una expresión booleana 布尔表达式 evalúa a true o false, utilizando operadores relacionales 关系运算符: == (igual), != (diferente), <, >, <=, >=. Tenga en cuenta que == compara valores primitivos pero referencias de objeto para objetos, por lo que debe usar .equals para Strings.

Las tres familias de operadores: aritméticos, relacionales y lógicos

Explorar

Explorar la tabla de verdad AND

Una expresión booleana se evalúa como true o false. AND es verdadero solo cuando ambos operandos son verdaderos; alterne las entradas para ver los cuatro casos.

2.3

La sentencia if

Syllabus

Objetivo de aprendizaje 2.3.A: Desarrollar código para representar procesos lógicos de ramificación mediante sentencias de selección y determinar el resultado de estos procesos.

2.3.A.1 Las sentencias de selección modifican la ejecución secuencial de las instrucciones.
2.3.A.2 Una instrucción if es un tipo de sentencia de selección que afecta el flujo de control ejecutando diferentes segmentos de código según el valor de una expresión booleana.
2.3.A.3 Una selección de un solo camino (instrucción if) se utiliza cuando hay un segmento de código que debe ejecutarse bajo una condición determinada. En este caso, el cuerpo se ejecuta únicamente cuando la expresión booleana es true.
2.3.A.4 Una selección de dos caminos (instrucción if-else) se utiliza cuando hay dos segmentos de código: uno para ser ejecutado cuando la expresión booleana es true y otro segmento para cuando la expresión booleana es false. En este caso, el cuerpo del if se ejecuta cuando la expresión booleana es true, y el cuerpo del else se ejecuta cuando la expresión booleana es false.

Fuente: College Board AP Course and Exam Description

Una sentencia if 条件语句 ejecuta un bloque solo cuando su condición es verdadera; un opcional else ofrece una alternativa:

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

Semáforos: la selección elige qué rama se ejecuta, al igual que las sentencias if eligen rutas de código

Explorar

Ver qué rama elige un if

Una sentencia if ejecuta su cuerpo solo cuando la condición es verdadera, de lo contrario salta a else. Deslice la puntuación a través de los límites y observe cómo cambia la calificación.

2.4

Sentencias if anidadas

Syllabus

Objetivo de aprendizaje 2.4.A: Desarrollar código para representar procesos lógicos de ramificación anidada y determinar el resultado de estos procesos.

2.4.A.1 Las instrucciones if anidadas consisten en instrucciones if, if-else o if-else-if dentro de instrucciones if, if-else o if-else-if.
2.4.A.2 La expresión booleana de la instrucción if anidada interna se evalúa solo si la expresión booleana de la instrucción if externa se evalúa como true.
2.4.A.3 Una selección múltiple (if-else-if) se utiliza cuando hay una serie de expresiones con diferentes segmentos de código para cada condición. La selección múltiple se realiza de tal manera que no se ejecuta más de un segmento de código según la primera expresión que se evalúa como true. Si ninguna expresión se evalúa como true y existe una instrucción trailing else, entonces se ejecuta el cuerpo de la instrucción else.

Fuente: College Board AP Course and Exam Description

Colocar un if dentro de otro, o encadenar con else if, permite probar varios casos en orden. Solo se ejecuta la rama coincidente primera:

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

2.5

Expresiones Booleanas Compuestas

Syllabus

Objetivo de aprendizaje 2.5.A: Desarrollar código para representar expresiones booleanas compuestas y determinar el resultado de estas expresiones.

2.5.A.1 Operadores lógicos ! (negación), && (conjunción) y || (disyunción) se utilizan con expresiones booleanas. La expresión !a se evalúa como true si a es false y se evalúa como false en caso contrario. La expresión a && b se evalúa como true si tanto a como b son true y se evalúa como false en caso contrario. La expresión a || b se evalúa como true si a es true, b es true o ambas lo son, y se evalúa como false en caso contrario. El orden de precedencia para evaluar los operadores lógicos es ! (negación), && (conjunción) y luego || (disyunción). Una expresión que involucra operadores lógicos se evalúa a un valor booleano.
2.5.A.2 La evaluación por cortocircuito ocurre cuando el resultado de una operación lógica utilizando && o || puede determinarse evaluando únicamente la primera expresión booleana. En este caso, la segunda expresión booleana no se evalúa.

Fuente: College Board AP Course and Exam Description

Evaluación de cortocircuito

Los operadores lógicos 逻辑运算符 combinan condiciones: && (y – ambas verdaderas), || (o – al menos una verdadera), ! (no – inverso). Java utiliza evaluación de cortocircuito 短路求值: && se detiene si el lado izquierdo es falso, y || se detiene si el lado izquierdo es verdadero – útil para proteger contra errores, p. ej., if (n != 0 && total / n > 5).

2.6

Comparando Expresiones Booleanas

Syllabus

Objetivo de Aprendizaje 2.6.A: Comparar expresiones booleanas equivalentes.

2.6.A.1 Dos expresiones booleanas son equivalentes si evalúan al mismo valor en todos los casos. Las tablas de verdad se pueden utilizar para demostrar que las expresiones booleanas son equivalentes.
2.6.A.2 La ley de De Morgan se puede aplicar a las expresiones booleanas para crear expresiones booleanas equivalentes. Según la ley de De Morgan, la expresión booleana !(a && b) es equivalente a !a || !b y la expresión booleana !(a || b) es equivalente a !a && !b.

Objetivo de Aprendizaje 2.6.B: Desarrollar código para comparar referencias de objetos utilizando expresiones booleanas y determinar el resultado de dichas expresiones.

2.6.B.1 Dos variables diferentes pueden contener referencias al mismo objeto. Las referencias de objeto se pueden comparar utilizando == y !=.
2.6.B.2 Una referencia de objeto se puede comparar con null, utilizando == o !=, para determinar si la referencia realmente apunta a un objeto.
2.6.B.3 Las clases suelen definir su propio método equals, el cual se puede utilizar para especificar los criterios de equivalencia para dos objetos de la clase. La equivalencia de dos objetos se determina más frecuentemente utilizando los atributos de ambos objetos.
- Afirmación de exclusión: Sobrescribir el método equals está fuera del alcance del curso y del examen de AP Computer Science A.

Fuente: College Board AP Course and Exam Description

Las leyes de De Morgan 德摩根定律 reescriben negaciones: !(a && b) es igual a !a || !b, y !(a || b) es igual a !a && !b. Dos expresiones booleanas son equivalentes si dan el mismo resultado para cada entrada; una tabla de verdad lo demuestra. Simplificar condiciones de esta manera es una tarea común en los exámenes.

2.7

Bucle while

Syllabus

Objetivo de Aprendizaje 2.7.A: Identificar cuándo se requiere un proceso iterativo para obtener un resultado deseado.

2.7.A.1 La iteración es una forma de repetición. Las sentencias de iteración modifican el flujo de control repitiendo un segmento de código cero o más veces mientras la expresión booleana que controla el bucle sea true.
2.7.A.2 Un bucle infinito ocurre cuando la expresión booleana en una sentencia iterativa siempre evalúa a true.
2.7.A.3 El cuerpo del bucle de una sentencia iterativa no se ejecutará si la expresión booleana evalúa inicialmente a false.
2.7.A.4 Los errores off by one (error de uno) ocurren cuando la sentencia de iteración se ejecuta una vez demasiado o una vez insuficiente.

Objetivo de Aprendizaje 2.7.B: Desarrollar código que represente procesos iterativos utilizando bucles while y determinar el resultado de estos procesos.

2.7.B.1 Un bucle while es un tipo de sentencia iterativa. En los bucles while, la expresión booleana se evalúa antes de cada iteración del cuerpo del bucle, incluida la primera. Cuando la expresión evalúa a true, se ejecuta el cuerpo del bucle. Esto continúa hasta que la expresión booleana evalúa a false, momento en el cual termina la iteración.

Fuente: College Board AP Course and Exam Description

Un bucle while 循环 repite mientras su condición se mantiene verdadera, probándola antes de cada paso. Debe cambiar algo dentro para que el bucle se detenga eventualmente, o se convertirá en un bucle infinito 无限循环:

Los tres tipos de bucles difieren en dónde se prueba la condición

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

Explorar

Rastrear un bucle while

Un bucle while se repite mientras su condición permanezca verdadera, actualizando sus variables en cada pasada. Pase paso a paso para ver cómo se acumula la suma de cuadrados.

2.8

Bucle for

Syllabus

Objetivo de aprendizaje 2.8.A: Desarrollar código que represente procesos iterativos utilizando bucles for y determinar el resultado de estos procesos.

2.8.A.1 Un bucle for es un tipo de instrucción iterativa. El encabezado de un bucle for tiene tres partes: la inicialización, la expresión booleana y la actualización.
2.8.A.2 En un bucle for, la instrucción de inicialización solo se ejecuta una vez antes de la primera evaluación de la expresión booleana. La variable que se está inicializando se denomina variable de control del bucle. La expresión booleana se evalúa inmediatamente después de inicializar la variable de control del bucle y luego tras cada ejecución de la instrucción de incremento hasta que sea false. En cada iteración, la actualización se ejecuta después de que se completa todo el cuerpo del bucle y antes de evaluar nuevamente la expresión booleana.
2.8.A.3 Un bucle for puede reescribirse como un bucle while equivalente (y viceversa).

Fuente: College Board AP Course and Exam Description

Un bucle for agrupa inicialización, condición y actualización en una sola línea; es ideal cuando se conoce la cantidad:

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

Un for y un while equivalente realizan el mismo trabajo; debe ser capaz de convertir entre ellos.

Una línea de ensamblaje: los bucles repiten un proceso para cada elemento, como for y while

Explorar

Rastrear un bucle for

Un bucle for se ejecuta un número fijo de veces, avanzando su contador a través de un rango. Observe cómo el contador y el total acumulado avanzan una pasada a la vez.

2.9

Construcción de Algoritmos Completos de Selección e Iteración

Syllabus

Objetivo de aprendizaje 2.9.A: Desarrollar código para algoritmos estándar y originales (sin estructuras de datos) y determinar el resultado de dichos algoritmos.

2.9.A.1 Existen algoritmos estándar para:
- identificar si un entero es o no divisible exactamente por otro entero
- identificar los dígitos individuales de un entero
- determinar la frecuencia con la que se cumple un criterio específico
- determinar un valor mínimo o máximo
- calcular una suma o un promedio

Fuente: College Board AP Course and Exam Description

Combine bucles y condiciones para resolver problemas reales: contar, sumar, encontrar un máximo o probar una propiedad:

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

Dos patrones de enteros que el examen prueba directamente usan % y /. Para leer los dígitos de un entero uno a la vez, tome repetidamente n % 10 (el último dígito) y luego n = n / 10 (elimínelo). Para probar divisibilidad, n % d == 0 significa que n es divisible exactamente por d. Combínelos con un contador para encontrar la frecuencia con la cual se cumple algún criterio.

Patrones estándar como un total acumulado, un contador o una bandera 标志 (un booleano que registra si ocurrió algo) aparecen a lo largo del curso.

2.10

Algoritmos de Cadenas

Syllabus

Objetivo de Aprendizaje 2.10.A: Desarrollar código para algoritmos estándar y originales que involucran cadenas y determinar el resultado de estos algoritmos.

2.10.A.1 Existen algoritmos estándar de cadenas para:
- encontrar si uno o más subcadenas tienen una propiedad particular
- determinar la cantidad de subcadenas que cumplen criterios específicos
- crear una nueva cadena con los caracteres invertidos

Fuente: College Board AP Course and Exam Description

Recorra una cadena por índice para procesar cada carácter:

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

Tareas típicas: contar ocurrencias, construir una copia invertida o filtrada, o probar si una cadena contiene otra.

2.11

Iteración Anidada

Syllabus

Objetivo de Aprendizaje 2.11.A: Desarrollar código para representar procesos iterativos anidados y determinar el resultado de estos procesos.

2.11.A.1 Las instrucciones de iteración anidadas son instrucciones de iteración que aparecen en el cuerpo de otra instrucción de iteración. Cuando un bucle está anidado dentro de otro bucle, el bucle interno debe completar todas sus iteraciones antes de que el bucle externo pueda continuar con su siguiente iteración.

Fuente: College Board AP Course and Exam Description

Un bucle anidado 嵌套循环 coloca un bucle dentro de otro; el bucle interno se completa completamente para cada paso del externo. Si el externo se ejecuta $n$ veces y el interno $m$ veces, el cuerpo se ejecuta $n\times m$ veces; esto es la base para procesar cuadrículas y comparar todos los pares.

2.12

Análisis Informal del Tiempo de Ejecución

Syllabus

Objetivo de aprendizaje 2.12.A: Calcular el conteo de ejecuciones de sentencias y la comparación informal del tiempo de ejecución de sentencias iterativas.

2.12.A.1 Un conteo de ejecuciones de sentencias indica el número de veces que una sentencia es ejecutada por el programa. Los conteos de ejecuciones de sentencias a menudo se calculan de forma informal mediante trazado y análisis de las sentencias iterativas.

Fuente: College Board AP Course and Exam Description

Tasas de crecimiento Big-O

El análisis del tiempo de ejecución 运行时间分析 cuenta cuántos pasos básicos toma un algoritmo a medida que crece el tamaño de la entrada $n$. Cuente las ejecuciones de la declaración más interna: un solo bucle sobre $n$ elementos es lineal ($n$ pasos); dos bucles anidados sobre $n$ son cuadráticos ($n^2$). Este conteo informal le permite comparar la eficiencia de dos algoritmos.

Cómo crece el tiempo de ejecución con el número de elementos n

Habilidad de examen: para un bucle anidado, sea capaz de indicar cuántas veces se ejecuta la declaración interna en función de los límites de los bucles; es una pregunta de opción múltiple frecuente.

Ejemplo resuelto. ¿Cuántas estrellas imprime este código?

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

El bucle interno se ejecuta i veces para cada i externo: 0 + 1 + 2 + 3 = 6 estrellas. Cuando el límite interno es la variable externa, el total es la suma triangular $0+1+\dots+(n-1)=\dfrac{n(n-1)}{2}$; aquí $\dfrac{4\times3}{2}=6$, no los $n^2=16$ completos de un bucle anidado rectangular.

Explorar

Comparar cómo escalan los algoritmos

Tiempo de ejecución describe cómo crece el número de pasos con el tamaño de entrada $n$. Aumente $n$ y observe cómo una complejidad lineal $O(n)$ supera ampliamente a una cuadrática $O(n^2)$.

2.12

Consejos para el examen

Establezca correctamente las condiciones de contorno: use < vs <= deliberadamente, y vigile la primera y última iteración de cada bucle (el error clásico es off-by-one).
Construya condiciones compuestas con &&, ||, ! y recuerde la evaluación de cortocircuito (coloque la comprobación de nulo primero).
Realice trazados de bucles anidados contando cuántas veces se ejecuta el cuerpo interno en total.
Elija la estructura adecuada: if/else if para rangos, un bucle para repeticiones; evite un bucle infinito actualizando la variable del bucle.
Aplique las leyes de De Morgan cuando simplifique o niegue una condición booleana.

Lecciones interactivas sobre este tema

Trátalo paso a paso, con ejercicios de verificación instantánea.

Exámenes Anteriores

Más temas en AP Ciencias de la Computación A

Colecciones de datos