Selection and Iteration · ⁨Выбор и итерация⁩

AP Computer Science A · ⁨AP Информатика A⁩ · Topic 2 · ⁨Тема 2⁩

View Slides · ⁨Просмотр слайдов⁩ Train · ⁨Тренировать⁩

Video lesson for this topic · ⁨Видеоурок по этой теме⁩ Open the video page · ⁨Открыть страницу видео⁩

2.1

Selection and Repetition in Algorithms · ⁨Выбор и повторение в алгоритмах⁩

Syllabus · ⁨Программа⁩

English

Learning Objective 2.1.A: Represent patterns and algorithms that involve selection and repetition found in everyday life using written language or diagrams.

2.1.A.1 The building blocks of algorithms include sequencing, selection, and repetition.
2.1.A.2 Algorithms can contain selection, through decision making, and repetition, via looping.
2.1.A.3 Selection occurs when a choice of how the execution of an algorithm will proceed is based on a true or false decision.
2.1.A.4 Repetition is when a process repeats itself until a desired outcome is reached.
2.1.A.5 The order in which sequencing, selection, and repetition are used contributes to the outcome of the algorithm.

Русский

Цель обучения 2.1.A: Представлять паттерны и алгоритмы, включающие выбор и повторение, встречающиеся в повседневной жизни, с помощью письменного текста или диаграмм.

2.1.A.1 Базовыми элементами алгоритмов являются последовательность, выбор и повторение.
2.1.A.2 Алгоритмы могут содержать выбор через принятие решений и повторение через циклы.
2.1.A.3 Выбор происходит, когда выбор направления выполнения алгоритма основан на истинном или ложном решении.
2.1.A.4 Повторение — это процесс, который повторяется до достижения желаемого результата.
2.1.A.5 Порядок, в котором используются последовательность, выбор и повторение, влияет на результат алгоритма.

Source: College Board AP Course and Exam Description · ⁨Источник: Описание курса и экзамена College Board AP⁩

English

Algorithms are built from three control structures 控制结构: sequence (steps in order), selection 选择 (choosing a path), and iteration 迭代 (repeating steps). This topic covers selection and iteration – the tools that let a program make decisions and loop.

Русский

Схема потока с ромбом решения: выбор определяет, какой путь алгоритм выполнит — Блок-схема с ромбом решения: выбор определяет путь, который проходит алгоритм

Алгоритмы строятся из трёх операторов управления: последовательность (шаги по порядку), выбор (выбор пути) и итерация (повторение шагов). Эта тема охватывает выбор и итерацию – инструменты, позволяющие программе принимать решения и выполнять циклы.

Три оператора управления: последовательность, выбор и итерация

Vocabulary · ⁨Словарь⁩ Train · ⁨Тренировать⁩

English	Русский
control structures/kənˈtrəʊl ˈstrʌktʃəz/	структуры управления
selection/sɪˈlekʃn/	выбор
iteration/ˌɪtəˈreɪʃn/	итерации
boolean expression/ˈbuːlɪən ekˈspreʃn/	булево выражение
relational operators/rɪˈleɪʃənl ˈɒpəreɪtəz/	относительные операторы
if statement/ɪf ˈsteɪtmənt/	оператор if
Logical operators/ˈlɒdʒɪkl ˈɒpəreɪtəz/	Логические операторы
short-circuit evaluation/ʃɔːt ˈsɜːkɪt ɪˌvæljuːˈeɪʃn/	короткое замыкание (short-circuit evaluation)
De Morgan's laws/də ˈmɔːɡənz lɔːz/	законы де Моргана
while loop/waɪl luːp/	цикл while
infinite loop/ˈɪnfɪnət luːp/	бесконечный цикл
flag/flæɡ/	флаг
nested loop/ˈnestɪd luːp/	вложенный цикл
Run-time analysis/rʌn taɪm əˈnæləsɪs/	Анализ во время выполнения

2.2

Boolean Expressions · ⁨Булевы выражения⁩

Syllabus · ⁨Программа⁩

English

Learning Objective 2.2.A: Develop code to create Boolean expressions with relational operators and determine the result of these expressions.

2.2.A.1 Values can be compared using the relational operators == and != to determine whether the values are the same. With primitive types, this compares the actual primitive values. With reference types, this compares the object references.
2.2.A.2 Numeric values can be compared using the relational operators <, >, <=, and >= to determine the relationship between the values.
2.2.A.3 An expression involving relational operators evaluates to a Boolean value.

Русский

Цель обучения 2.2.A: Разработать код для создания булевских выражений с реляционными операторами и определить результат этих выражений.

2.2.A.1 Значения можно сравнивать с помощью реляционных операторов == и !=, чтобы определить, одинаковы ли значения. Для примитивных типов это сравнивает фактические примитивные значения. Для ссылочных типов это сравнивает ссылки на объекты.
2.2.A.2 Числовые значения можно сравнивать с помощью реляционных операторов <, >, <= и >=, чтобы определить соотношение между значениями.
2.2.A.3 Выражение, содержащее реляционные операторы, вычисляется как булево значение.

Source: College Board AP Course and Exam Description · ⁨Источник: Описание курса и экзамена College Board AP⁩

English

Logic gates & the half-adder

A boolean expression 布尔表达式 evaluates to true or false, using relational operators 关系运算符: == (equal), != (not equal), <, >, <=, >=. Note == compares primitive values but object references for objects, so use .equals for Strings.

Русский

Логические вентили и полусумматор

Булево выражение вычисляется как true или false, используя относительные операторы: == (равно), != (не равно), <, >, <=, >=. Заметьте, что == сравнивает примитивные значения, но ссылки на объекты для объектов, поэтому используйте .equals для Strings.

Три семейства операторов: арифметические, реляционные и логические — Три группы операторов: арифметические, относительные и логические

Explore · ⁨Исследовать⁩

Explore the AND truth table · ⁨Исследуйте таблицу истинности AND⁩

A Boolean expression evaluates to true or false. AND is true only when both operands are true; toggle the inputs to see all four cases. · ⁨Логическое выражение вычисляется как true или false. Операция AND истинна только тогда, когда оба операнда истинны; переключите входные значения, чтобы увидеть все четыре варианта.⁩

2.3

The if Statement · ⁨Оператор if⁩

Syllabus · ⁨Программа⁩

English

Learning Objective 2.3.A: Develop code to represent branching logical processes by using selection statements and determine the result of these processes.

2.3.A.1 Selection statements change the sequential execution of statements.
2.3.A.2 An if statement is a type of selection statement that affects the flow of control by executing different segments of code based on the value of a Boolean expression.
2.3.A.3 A one-way selection (if statement) is used when there is a segment of code to execute under a certain condition. In this case, the body is executed only when the Boolean expression is true.
2.3.A.4 A two-way selection (if-else statement) is used when there are two segments of code—one to be executed when the Boolean expression is true and another segment for when the Boolean expression is false. In this case, the body of the if is executed when the Boolean expression is true, and the body of the else is executed when the Boolean expression is false.

Русский

Цель обучения 2.3.A: Разработать код для представления ветвящихся логических процессов с использованием операторов выбора и определить результат этих процессов.

2.3.A.1 Операторы выбора изменяют последовательное выполнение операторов.
2.3.A.2 Оператор if является типом оператора выбора, который влияет на поток управления, выполняя различные сегменты кода в зависимости от значения булевого выражения.
2.3.A.3 Однонаправленный выбор (оператор if) используется, когда существует сегмент кода для выполнения при определенном условии. В этом случае тело выполняется только тогда, когда булево выражение равно true.
2.3.A.4 Двухнаправленный выбор (оператор if-else) используется, когда есть два сегмента кода: один для выполнения, когда булево выражение равно true, и другой сегмент для выполнения, когда булево выражение равно false. В этом случае тело оператора if выполняется, когда булево выражение равно true, а тело оператора else выполняется, когда булево выражение равно false.

Source: College Board AP Course and Exam Description · ⁨Источник: Описание курса и экзамена College Board AP⁩

English

An if statement 条件语句 runs a block only when its condition is true; an optional else gives an alternative:

Русский

Оператор if выполняет блок только тогда, когда его условие истинно; опциональный else предоставляет альтернативу:

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

Светофоры: выбор определяет, какой веткой будет выполнен код, аналогично тому, как условные операторы if выбирают пути выполнения кода — Светофор: выбор определяет, какой ветвь выполнить, так же как операторы if выбирают пути кода

Explore · ⁨Исследовать⁩

See which branch an if chooses · ⁨Узнайте, какой ветви выбирает оператор if⁩

An if statement runs its body only when the condition is true, otherwise it skips to else. Slide the score across the boundaries and watch the grade change. · ⁨Оператор if выполняет свой блок только при истинном условии, иначе он пропускает его к else. Передвигайте оценку по границам и наблюдайте, как меняется оценка.⁩

2.4

Nested if Statements · ⁨Вложенные операторы if⁩

Syllabus · ⁨Программа⁩

English

Learning Objective 2.4.A: Develop code to represent nested branching logical processes and determine the result of these processes.

2.4.A.1 Nested if statements consist of if, if-else, or if-else-if statements within if, if-else, or if-else-if statements.
2.4.A.2 The Boolean expression of the inner nested if statement is evaluated only if the Boolean expression of the outer if statement evaluates to true.
2.4.A.3 A multiway selection (if-else-if) is used when there are a series of expressions with different segments of code for each condition. Multiway selection is performed such that no more than one segment of code is executed based on the first expression that evaluates to true. If no expression evaluates to true and there is a trailing else statement, then the body of the else is executed.

Русский

Цель обучения 2.4.A: Разработать код для представления вложенных ветвящихся логических процессов и определить результат этих процессов.

2.4.A.1 Вложенные операторы if состоят из операторов if, if-else или if-else-if внутри операторов if, if-else или if-else-if.
2.4.A.2 Булево выражение внутреннего вложенного оператора if вычисляется только в том случае, если булево выражение внешнего оператора if оценивается как true.
2.4.A.3 Множественный выбор (оператор if-else-if) используется, когда имеется серия выражений с различными сегментами кода для каждого условия. Множественный выбор выполняется таким образом, что выполняется не более одного сегмента кода на основе первого выражения, которое оценивается как true. Если ни одно выражение не оценивается как true, и присутствует оператор else в конце, то выполняется тело оператора else.

Source: College Board AP Course and Exam Description · ⁨Источник: Описание курса и экзамена College Board AP⁩

English

Placing an if inside another, or chaining with else if, tests several cases in order. Only the first matching branch runs:

Русский

Размещение оператора if внутри другого или цепочка с помощью else if проверяют несколько случаев по порядку. Выполняется только первая подходящая ветвь:

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

2.5

Compound Boolean Expressions · ⁨Составные булевы выражения⁩

Syllabus · ⁨Программа⁩

English

Learning Objective 2.5.A: Develop code to represent compound Boolean expressions and determine the result of these expressions.

2.5.A.1 Logical operators ! (not), && (and), and || (or) are used with Boolean expressions. The expression !a evaluates to true if a is false and evaluates to false otherwise. The expression a && b evaluates to true if both a and b are true and evaluates to false otherwise. The expression a || b evaluates to true if a is true, b is true, or both, and evaluates to false otherwise. The order of precedence for evaluating logical operators is ! (not), && (and), then || (or). An expression involving logical operators evaluates to a Boolean value.
2.5.A.2 Short-circuit evaluation occurs when the result of a logical operation using && or || can be determined by evaluating only the first Boolean expression. In this case, the second Boolean expression is not evaluated.

Русский

Цель обучения 2.5.A: Разработать код для представления составных булевских выражений и определить результат этих выражений.

2.5.A.1 Логические операторы ! (не), && (и) и || (или) используются с булевскими выражениями. Выражение !a вычисляется как true, если a равно false, и вычисляется как false в противном случае. Выражение a && b вычисляется как true, если оба выражения a и b равны true, и вычисляется как false в противном случае. Выражение a || b вычисляется как true, если a равно true, b равно true или оба, и вычисляется как false в противном случае. Порядок приоритета вычисления логических операторов: ! (не), затем && (и), затем || (или). Выражение, содержащее логические операторы, вычисляется как булево значение.
2.5.A.2 Короткое замыкание (short-circuit evaluation) происходит, когда результат логической операции с использованием && или || может быть определен путем вычисления только первого булевого выражения. В этом случае второе булево выражение не вычисляется.

Source: College Board AP Course and Exam Description · ⁨Источник: Описание курса и экзамена College Board AP⁩

English

Short-circuit evaluation

Logical operators 逻辑运算符 combine conditions: && (and – both true), || (or – at least one true), ! (not – reverse). Java uses short-circuit evaluation 短路求值: && stops if the left side is false, and || stops if the left side is true – useful to guard against errors, e.g. if (n != 0 && total / n > 5).

Русский

Короткое замыкание при вычислении

Логические операторы объединяют условия: && (and – оба истинны), || (or – хотя бы один истинен), ! (not – инверсия). Java использует короткое замыкание при вычислении: && останавливается, если левая часть ложна, а || останавливается, если левая часть истинна – это полезно для защиты от ошибок, например, if (n != 0 && total / n > 5).

2.6

Comparing Boolean Expressions · ⁨Сравнение булевых выражений⁩

Syllabus · ⁨Программа⁩

English

Learning Objective 2.6.A: Compare equivalent Boolean expressions.

2.6.A.1 Two Boolean expressions are equivalent if they evaluate to the same value in all cases. Truth tables can be used to prove Boolean expressions are equivalent.
2.6.A.2 De Morgan's law can be applied to Boolean expressions to create equivalent Boolean expressions. Under De Morgan's law, the Boolean expression !(a && b) is equivalent to !a || !b and the Boolean expression !(a || b) is equivalent to !a && !b.

Learning Objective 2.6.B: Develop code to compare object references using Boolean expressions and determine the result of these expressions.

2.6.B.1 Two different variables can hold references to the same object. Object references can be compared using == and !=.
2.6.B.2 An object reference can be compared with null, using == or !=, to determine if the reference actually references an object.
2.6.B.3 Classes often define their own equals method, which can be used to specify the criteria for equivalency for two objects of the class. The equivalency of two objects is most often determined using attributes from the two objects.
- Exclusion statement: Overriding the equals method is outside the scope of the AP Computer Science A course and exam.

Русский

Цель обучения 2.6.A: Сравнивать эквивалентные булевские выражения.

2.6.A.1 Два булевских выражения являются эквивалентными, если они вычисляются как одно и то же значение во всех случаях. Таблицы истинности могут использоваться для доказательства эквивалентности булевских выражений.
2.6.A.2 Закон де Моргана может быть применен к булевским выражениям для создания эквивалентных булевских выражений. Согласно закону де Моргана, булево выражение !(a && b) эквивалентно !a || !b, а булево выражение !(a || b) эквивалентно !a && !b.

Цель обучения 2.6.B: Разработать код для сравнения ссылочных переменных объектов с использованием булевских выражений и определить результат этих выражений.

2.6.B.1 Две разные переменные могут хранить ссылки на один и тот же объект. Ссылочные переменные объектов можно сравнивать с помощью == и !=.
2.6.B.2 Ссылочную переменную объекта можно сравнить с null, используя == или !=, чтобы определить, действительно ли ссылка указывает на объект.
2.6.B.3 Классы часто определяют свой собственный метод equals, который можно использовать для определения критериев эквивалентности для двух объектов данного класса. Эквивалентность двух объектов чаще всего определяется на основе атрибутов этих двух объектов.
- Исключение: Переопределение метода equals не входит в рамки курса и экзамена по информатике AP.

Source: College Board AP Course and Exam Description · ⁨Источник: Описание курса и экзамена College Board AP⁩

English

De Morgan's laws 德摩根定律 rewrite negations: !(a && b) equals !a || !b, and !(a || b) equals !a && !b. Two boolean expressions are equivalent if they give the same result for every input – a truth table proves it. Simplifying conditions this way is a common exam task.

Русский

Законы де Моргана преобразуют отрицания: !(a && b) равно !a || !b, а !(a || b) равно !a && !b. Два булевых выражения считаются эквивалентными, если они дают одинаковый результат для любого набора входных данных — это подтверждается таблицей истинности. Упрощение условий таким образом является типичным заданием на экзамене.

2.7

while Loops · ⁨Циклы while⁩

Syllabus · ⁨Программа⁩

English

Learning Objective 2.7.A: Identify when an iterative process is required to achieve a desired result.

2.7.A.1 Iteration is a form of repetition. Iteration statements change the flow of control by repeating a segment of code zero or more times as long as the Boolean expression controlling the loop evaluates to true.
2.7.A.2 An infinite loop occurs when the Boolean expression in an iterative statement always evaluates to true.
2.7.A.3 The loop body of an iterative statement will not execute if the Boolean expression initially evaluates to false.
2.7.A.4 Off by one errors occur when the iteration statement loops one time too many or one time too few.

Learning Objective 2.7.B: Develop code to represent iterative processes using while loops and determine the result of these processes.

2.7.B.1 A while loop is a type of iterative statement. In while loops, the Boolean expression is evaluated before each iteration of the loop body, including the first. When the expression evaluates to true, the loop body is executed. This continues until the Boolean expression evaluates to false, whereupon the iteration terminates.

Русский

Цель обучения 2.7.A: Определять, когда для достижения желаемого результата требуется итеративный процесс.

2.7.A.1 Итерация — это форма повторения. Операторы итерации изменяют поток управления, повторяя фрагмент кода ноль или более раз, пока логическое выражение, управляющее циклом, оценивается как true.
2.7.A.2 Бесконечный цикл возникает, когда логическое выражение в операторе итерации всегда оценивается как true.
2.7.A.3 Тело цикла оператора итерации не выполнится, если логическое выражение изначально оценивается как false.
2.7.A.4 Ошибки off by one (на единицу больше/меньше) возникают, когда оператор итерации выполняется на один раз слишком много или на один раз слишком мало.

Цель обучения 2.7.B: Разработать код для представления итеративных процессов с использованием циклов while и определить результат этих процессов.

2.7.B.1 Цикл while является видом итеративного оператора. В циклах while логическое выражение вычисляется перед каждой итерацией тела цикла, включая первую. Когда выражение принимает значение true, выполняется тело цикла. Это продолжается до тех пор, пока логическое выражение не примет значение false, после чего итерация завершается.

Source: College Board AP Course and Exam Description · ⁨Источник: Описание курса и экзамена College Board AP⁩

English

A while loop 循环 repeats while its condition stays true, testing before each pass. You must change something inside so the loop eventually stops, or it becomes an infinite loop 无限循环:

Русский

Цикл while повторяется пока его условие остаётся истинным, проверяя его перед каждой итерацией. Вы должны изменить что-то внутри, чтобы цикл в конце прекратился, иначе он станет бесконечным циклом:

Три типа циклов различаются местом проверки условия — Три типа циклов различаются тем, где проверяется условие

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

Explore · ⁨Исследовать⁩

Trace a while loop · ⁨Отследите цикл while⁩

A while loop repeats as long as its condition stays true, updating its variables each pass. Step through to see the sum of squares build up. · ⁨Цикл while повторяется, пока его условие остается истинным, обновляя свои переменные на каждом проходе. Пройдитесь по шагам, чтобы увидеть, как накапливается сумма квадратов.⁩

2.8

for Loops · ⁨Циклы for⁩

Syllabus · ⁨Программа⁩

Learning Objective Essential Knowledge

2.8.A
Develop code to represent iterative processes using for loops and determine the result of these processes.

2.8.A.1 A for loop is a type of iterative statement. There are three parts in a for loop header: the initialization, the Boolean expression, and the update.
2.8.A.2 In a for loop, the initialization statement is only executed once before the first Boolean expression evaluation. The variable being initialized is referred to as a loop control variable. The Boolean expression is evaluated immediately after the loop control variable is initialized and then following each execution of the increment statement until it is false. In each iteration, the update is executed after the entire loop body is executed and before the Boolean expression is evaluated again.
2.8.A.3 A for loop can be rewritten into an equivalent while loop (and vice versa).

Source: College Board AP Course and Exam Description · ⁨Источник: Описание курса и экзамена College Board AP⁩

English

A for loop packs initialization, condition, and update into one line – best when you know the count:

A for and an equivalent while do the same work; be able to convert between them.

Русский

Цикл for упаковывает инициализацию, условие и обновление в одну строку – лучше всего подходит, когда вы знаете количество:

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

Структура for и эквивалентная структура while выполняют ту же работу; нужно уметь конвертировать между ними.

Конвейер: циклы повторяют процесс для каждого элемента, подобно конструкциям for и while — Конвейер: циклы повторяют процесс для каждого элемента, как in for и while

Explore · ⁨Исследовать⁩

Trace a for loop · ⁨Отследите цикл for⁩

A for loop runs a fixed number of times, its counter stepping through a range. Watch the counter and running total advance one pass at a time. · ⁨Цикл for выполняется фиксированное количество раз, его счетчик проходит по диапазону. Наблюдайте, как счетчик и накопленная сумма увеличиваются на один проход за раз.⁩

2.9

Building Complete Selection and Iteration Algorithms · ⁨Создание полных алгоритмов выбора и итерации⁩

Syllabus · ⁨Программа⁩

English

Learning Objective 2.9.A: Develop code for standard and original algorithms (without data structures) and determine the result of these algorithms.

2.9.A.1 There are standard algorithms to:
- identify if an integer is or is not evenly divisible by another integer
- identify the individual digits in an integer
- determine the frequency with which a specific criterion is met
- determine a minimum or maximum value
- compute a sum or average

Русский

Цель обучения 2.9.A: Разработать код для стандартных и оригинальных алгоритмов (без структур данных) и определить результат этих алгоритмов.

2.9.A.1 Существуют стандартные алгоритмы для:
- определения, кратно ли целое число другому целому числу или нет
- определения отдельных цифр в целом числе
- определения частоты выполнения определенного критерия
- определения минимального или максимального значения
- вычисления суммы или среднего значения

Source: College Board AP Course and Exam Description · ⁨Источник: Описание курса и экзамена College Board AP⁩

English

Combine loops and conditions to solve real problems – count, sum, find a maximum, or test a property:

Two integer patterns the exam tests directly use % and /. To read the digits of an integer one at a time, repeatedly take n % 10 (the last digit) and then n = n / 10 (drop it). To test divisibility, n % d == 0 means n is evenly divisible by d. Combine them with a counter to find the frequency with which some criterion is met.

Standard patterns like a running total, a counter, or a flag 标志 (a boolean that records whether something happened) recur throughout the course.

Русский

Объедините циклы и условия для решения реальных задач – подсчет, суммирование, поиск максимума или проверка свойства:

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

Два целочисленных паттерна, которые непосредственно проверяются на экзамене, используют % и /. Чтобы читать цифры целого числа по одной, необходимо последовательно брать n % 10 (последнюю цифру), а затем выполнять n = n / 10 (убрать её). Для проверки делимости n % d == 0 означает, что n делится на d без остатка. Объедините их со счетчиком, чтобы найти частоту, с которой выполняется определенное условие.

Стандартные паттерны, такие как накопительная сумма, счетчик или флаг (булево значение, фиксирующее, произошло ли что-то), встречаются на протяжении всего курса.

2.10

String Algorithms · ⁨Алгоритмы со строками⁩

Syllabus · ⁨Программа⁩

English

Learning Objective 2.10.A: Develop code for standard and original algorithms that involve strings and determine the result of these algorithms.

2.10.A.1 There are standard string algorithms to:
- find if one or more substrings have a particular property
- determine the number of substrings that meet specific criteria
- create a new string with the characters reversed

Русский

Цель обучения 2.10.A: Разрабатывать код для стандартных и оригинальных алгоритмов, связанных со строками, и определять результат этих алгоритмов.

2.10.A.1 Существуют стандартные строчные алгоритмы для:
- поиска наличия у одной или нескольких подстрок определенного свойства
- определения количества подстрок, соответствующих определенным критериям
- создания новой строки с обратным порядком символов

Source: College Board AP Course and Exam Description · ⁨Источник: Описание курса и экзамена College Board AP⁩

English

Loop through a string by index to process each character:

Typical tasks: count occurrences, build a reversed or filtered copy, or test whether one string contains another.

Русский

Проход по строке по индексам для обработки каждого символа:

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

Типичные задачи: подсчет вхождений, создание перевернутой или отфильтрованной копии, или проверка содержит ли одна строку другую.

2.11

Nested Iteration · ⁨Вложенная итерация⁩

Syllabus · ⁨Программа⁩

English

Learning Objective 2.11.A: Develop code to represent nested iterative processes and determine the result of these processes.

2.11.A.1 Nested iteration statements are iteration statements that appear in the body of another iteration statement. When a loop is nested inside another loop, the inner loop must complete all its iterations before the outer loop can continue to its next iteration.

Русский

Цель обучения 2.11.A: Разработать код для представления вложенных итеративных процессов и определить результат этих процессов.

2.11.A.1 Вложенные операторы итерации — это операторы итерации, которые находятся внутри тела другого оператора итерации. Когда цикл вложен внутрь другого цикла, внутренний цикл должен завершить все свои итерации, прежде чем внешний цикл сможет перейти к своей следующей итерации.

Source: College Board AP Course and Exam Description · ⁨Источник: Описание курса и экзамена College Board AP⁩

English

A nested loop 嵌套循环 puts one loop inside another; the inner loop completes fully for each pass of the outer. If the outer runs $n$ times and the inner $m$ times, the body runs $n\times m$ times – the basis for processing grids and comparing all pairs.

Русский

Вложенный цикл помещает один цикл внутрь другого; внутренний цикл полностью завершается для каждой итерации внешнего. Если внешний выполняется $n$ раз, а внутренний $m$ раз, тело выполняется $n\times m$ раз – основа для обработки сеток и сравнения всех пар.

2.12

Informal Run-Time Analysis · ⁨Неформальный анализ времени выполнения⁩

Syllabus · ⁨Программа⁩

English

Learning Objective 2.12.A: Calculate statement execution counts and informal run-time comparison of iterative statements.

2.12.A.1 A statement execution count indicates the number of times a statement is executed by the program. Statement execution counts are often calculated informally through tracing and analysis of the iterative statements.

Русский

Цель обучения 2.12.A: Вычислять количество выполнений операторов и проводить неформальное сравнение по времени выполнения итеративных операторов.

2.12.A.1 Количество выполнений оператора указывает на число раз, когда программа выполняет данный оператор. Количество выполнений операторов часто вычисляется неформально путем трассировки и анализа итеративных операторов.

Source: College Board AP Course and Exam Description · ⁨Источник: Описание курса и экзамена College Board AP⁩

English

Big-O growth rates

Run-time analysis 运行时间分析 counts how many basic steps an algorithm takes as the input size $n$ grows. Count the executions of the innermost statement: a single loop over $n$ items is linear ($n$ steps); two nested loops over $n$ are quadratic ($n^2$). This informal counting lets you compare two algorithms' efficiency.

Exam skill: for a nested loop, be able to state how many times the inner statement runs in terms of the loop bounds – a frequent multiple-choice question.

Worked example. How many stars does this print?

The inner loop runs i times for each outer i: 0 + 1 + 2 + 3 = 6 stars. When the inner bound is the outer variable, the total is the triangular sum $0+1+\dots+(n-1)=\dfrac{n(n-1)}{2}$ – here $\dfrac{4\times3}{2}=6$ – not the full $n^2=16$ of a rectangular nested loop.

Русский

Темпы роста Big-O

Анализ времени выполнения считает, сколько базовых шагов выполняет алгоритм по мере роста размера входных данных $n$. Подсчитайте выполнение самого внутреннего утверждения: одиночный цикл по $n$ элементам является линейным ($n$ шагов); два вложенных цикла по $n$ являются квадратичными ($n^2$). Этот неформальный подсчет позволяет сравнить эффективность двух алгоритмов.

Как время выполнения растет вместе с количеством элементов n — Как время выполнения растет с количеством элементов n

Навык для экзамена: для вложенного цикла нужно уметь stating, сколько раз выполняется внутреннее утверждение в зависимости от границ циклов – частый вопрос с множественным выбором.

Разобранный пример. Сколько звезд будет напечатано?

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

Внутренний цикл выполняется i раз для каждого внешнего i: 0 + 1 + 2 + 3 = 6 звёздочек. Когда внутренняя граница зависит от внешней переменной, общее количество равно треугольной сумме $0+1+\dots+(n-1)=\dfrac{n(n-1)}{2}$ – здесь $\dfrac{4\times3}{2}=6$ – а не полной $n^2=16$ прямоугольного вложенного цикла.

Explore · ⁨Исследовать⁩

Compare how algorithms scale · ⁨Сравните масштабирование алгоритмов⁩

Run-time describes how the number of steps grows with the input size $n$. Increase $n$ and watch a linear $O(n)$ pull far ahead of a quadratic $O(n^2)$. · ⁨Временна́я сложность описывает, как растет количество шагов с размером входных данных $n$. Увеличьте $n$ и наблюдайте, как линейная $O(n)$ значительно опережает квадратичную $O(n^2)$.⁩

2.12

Exam tips · ⁨Советы для экзамена⁩

English

Get boundary conditions right: use < vs <= deliberately, and watch the first and last iteration of every loop (off-by-one is the classic bug).
Build compound conditions with &&, ||, ! and remember short-circuit evaluation (put the null check first).
Trace nested loops by counting how many times the inner body runs in total.
Choose the right structure — if/else if for ranges, a loop for repetition — and avoid an infinite loop by updating the loop variable.
Apply De Morgan's laws when you simplify or negate a boolean condition.

Русский

Правильно задавайте граничные условия: сознательно используйте < или <= и следите за первой и последней итерацией каждого цикла (ошибка на единицу — классическая ошибка).
Составляйте сложные условия с помощью &&, || и ! и помните о коротком замыкании (коротком вычислении) логических выражений (первым ставьте проверку на null).
Отслеживайте вложенные циклы, подсчитывая, сколько раз всего выполняется тело внутреннего цикла.
Выбирайте правильную структуру — if/else if для диапазонов, цикл для повторений — и избегайте бесконечного цикла, обновляя переменную цикла.
Применяйте законы де Моргана при упрощении или отрицании булевого условия.

Interactive lessons on this topic · ⁨Интерактивные уроки по этой теме⁩

Work through it step by step, with instant-check exercises. · ⁨Пройдите его шаг за шагом с упражнениями мгновенной проверки.⁩

Past Papers · ⁨Архив экзаменационных работ⁩

More topics in AP Computer Science A · ⁨AP Информатика A⁩ · ⁨Больше тем в AP Computer Science A · ⁨AP Информатика A⁩⁩

Data Collections · ⁨Data Collections (Наборы данных)⁩