Глава 7 Петли

Компьютеры часто используются для автоматизации повторяющихся задач. Повторение задач без ошибок - это то, что компьютеры делают хорошо, а люди - плохо.

Выполнение одного и того же кода несколько раз называется итерацией. Мы видели такие методы, как обратный отсчет и факториал, которые используют рекурсию для итерации. Хотя рекурсия элегантна и мощна, к ней нужно привыкнуть. Java предоставляет языковые функции, которые значительно упрощают итерацию: операторы while и for.

7.1 Оператор while

Используя оператор while, мы можем переписать обратный отсчет следующим образом:

Вы можете почти прочитать выражение while, например, по-английски: «Пока n больше нуля, выведите значение n, а затем уменьшите значение n на 1. Когда вы дойдете до нуля, выведите Blastoff!»

Выражение в скобках называется условием. Выражения в фигурных скобках называются телом. Последовательность выполнения оператора while:

1. Оцените условие: истинно или ложно.
2. Если условие ложно, пропустите тело и перейдите к следующему оператору.
3. Если условие истинно, выполните тело и вернитесь к шагу 1.

Этот тип потока называется циклом, потому что последний шаг возвращается к первому.

Тело цикла должно изменить значение одной или нескольких переменных, чтобы в конечном итоге условие стало ложным и цикл завершился. В противном случае цикл будет повторяться бесконечно, что называется бесконечным циклом. Бесконечный источник забавы для компьютерных ученых - наблюдение, что указания на шампунь «вспенить, сполоснуть, повторить» представляют собой бесконечный цикл.

В случае обратного отсчета мы можем доказать, что цикл завершается, когда n положительно. Но в целом определить, завершился ли цикл, не так-то просто. Например, этот цикл продолжается до тех пор, пока n не станет 1 (что делает условие ложным):

Каждый раз при прохождении цикла программа отображает значение n, а затем проверяет, четное оно или нечетное. Если он четный, значение n делится на два. Если он нечетный, значение заменяется на 3 n +1. Например, если начальное значение (аргумент, переданный в последовательность) равно 3, результирующая последовательность будет 3, 10, 5, 16, 8, 4, 2, 1.

Поскольку n иногда увеличивается, а иногда уменьшается, нет очевидных доказательств того, что n когда-либо достигнет 1 и что программа когда-либо завершится. Для некоторых значений n мы можем доказать, что он завершается. Например, если начальное значение - степень двойки, то значение n будет четным каждый раз в цикле, пока мы не дойдем до 1. Предыдущий пример заканчивается такой последовательностью, начиная с того момента, когда n равно 16.

Трудный вопрос заключается в том, завершается ли эта программа для всех значений n. Пока никому не удалось это ни доказать, ни опровергнуть! Для получения дополнительной информации см. Https://en.wikipedia.org/wiki/Collatz_conjecture.

7.2 Создание таблиц

Циклы удобны для создания и отображения табличных данных. До того, как компьютеры стали доступными, людям приходилось вручную вычислять логарифмы, синусы, косинусы и другие общие математические функции. Чтобы упростить это, были книги таблиц, в которых можно было искать значения различных функций. Создание этих таблиц вручную было медленным и утомительным, а результаты часто были полны ошибок.

Когда на сцене появились компьютеры, одной из первых реакций было: «Это здорово! Мы можем использовать компьютер для создания таблиц, поэтому ошибок не будет ». Это оказалось правдой (в основном), но недальновидно. Немного позже компьютеры стали настолько распространенными, что печатные таблицы устарели.

Даже в этом случае для некоторых операций компьютеры используют таблицы значений, чтобы получить приблизительный ответ, а затем выполняют вычисления для улучшения приближения. В некоторых случаях в базовых таблицах были ошибки, наиболее известная из которых - таблица, в которой исходный Intel Pentium использовался для выполнения деления с плавающей запятой (см. Https://en.wikipedia.org/wiki/Pentium_FDIV_bug).

Хотя «таблица журналов» уже не так полезна, как раньше, она по-прежнему является хорошим примером итерации. В следующем цикле отображается таблица с последовательностью значений в левом столбце и их логарифмами в правом столбце:

Результат этой программы:

Math.log вычисляет натуральные логарифмы, то есть логарифмы по основанию e. Для приложений информатики нам часто нужны логарифмы по основанию 2. Чтобы вычислить их, мы можем применить это уравнение:

Мы можем изменить цикл следующим образом:

И вот результаты:

Каждый раз в цикле мы добавляем единицу к x, так что результатом является арифметическая последовательность. Если вместо этого мы умножим x на что-то, мы получим геометрическую последовательность:

Первая строка сохраняет Math.log (2) в конечной переменной, чтобы не вычислять это значение снова и снова. В последней строке x умножается на 2. Результат:

В этой таблице показаны степени двойки и их логарифмы с основанием 2. Таблицы журнала могут больше не быть полезными, но для компьютерных специалистов знание степени двойки очень помогает!

7.3 Инкапсуляция и обобщение

В Разделе 6.2 мы представили способ написания программ, называемый инкрементальной разработкой. В этом разделе мы представляем другой процесс разработки программы, называемый «инкапсуляция и обобщение». Шаги следующие:

1. Напишите несколько строк кода в основном или другом методе и протестируйте их.
2. Когда они заработают, оберните их новым методом и проверьте еще раз.
3. Если возможно, замените буквальные значения переменными и параметрами.

Второй шаг называется инкапсуляцией; третий шаг - обобщение.

Чтобы продемонстрировать этот процесс, мы разработаем методы, отображающие таблицы умножения. Вот цикл, который отображает числа, кратные двум, в одной строке:

Первая строка инициализирует переменную с именем i, которая будет действовать как переменная цикла: по мере выполнения цикла значение i увеличивается с 1 до 6; когда i равно 7, цикл завершается.

Каждый раз при прохождении цикла мы отображаем значение 2 * i, заполненное пробелами, так что его ширина составляет четыре символа. Поскольку мы используем System.out.printf, вывод отображается в одной строке.

После цикла мы вызываем println, чтобы напечатать новую строку и завершить строку. Помните, что в некоторых средах вывод не отображается до тех пор, пока строка не будет заполнена.

Результат кода на данный момент:

Следующий шаг - «инкапсулировать» этот код в новый метод. Вот как это выглядит:

Затем мы заменяем постоянное значение 2 параметром n. Этот шаг называется «обобщением», потому что он делает метод более общим (менее конкретным).

Вызов этого метода с аргументом 2 дает тот же результат, что и раньше. С аргументом 3 вывод:

А с аргументом 4 вывод:

К настоящему моменту вы, наверное, уже догадались, как мы будем отображать таблицу умножения: мы будем вызывать printRow несколько раз с разными аргументами. Фактически, мы будем использовать другой цикл для перебора строк.

Результат выглядит так:

Спецификатор формата \% 4d в printRow заставляет вывод выравниваться по вертикали, независимо от того, являются ли числа однозначными или двухзначными.

Наконец, мы инкапсулируем второй цикл в метод:

Одна из проблем программирования, особенно для начинающих, - это понять, как разделить программу на методы. Процесс инкапсуляции и обобщения позволяет вам проектировать по мере продвижения.

7.4 Дальнейшее обобщение

Предыдущая версия printTable всегда отображает шесть строк. Мы можем обобщить это, заменив литерал 6 параметром:

Вот результат с аргументом 7:

Так лучше, но у него все еще есть проблема: он всегда отображает одинаковое количество столбцов. Мы можем сделать больше обобщений, добавив параметр в printRow:

Теперь printRow принимает два параметра: n - это значение, кратное которому должно отображаться, и cols - количество столбцов. Поскольку мы добавили параметр в printRow, мы также должны изменить строку в printTable, где он вызывается:

Когда эта строка выполняется, она оценивает строки и передает значение, равное 7 в этом примере, в качестве аргумента. В printRow это значение присваивается столбцам. В результате количество столбцов равно количеству строк, поэтому мы получаем квадратную таблицу 7x7:

Когда вы надлежащим образом обобщаете метод, вы часто обнаруживаете, что у него есть возможности, которые вы не планировали. Например, вы могли заметить, что таблица умножения симметрична; поскольку ab = ba, все записи в таблице появляются дважды. Вы можете сэкономить чернила, распечатав половину таблицы, и вам нужно будет изменить только одну строку printTable:

На словах длина каждой строки равна ее номеру. В результате получилась треугольная таблица умножения.

Обобщение делает код более универсальным, более вероятным для повторного использования, а иногда и более простым для написания.

7.5 Оператор for

Циклы, которые мы написали до сих пор, имеют несколько общих элементов. Они начинают с инициализации переменной, у них есть условие, которое зависит от этой переменной, и внутри цикла они что-то делают для обновления этой переменной. Этот тип цикла настолько распространен, что есть другой оператор, цикл for, который выражает его более кратко.

Например, мы могли бы переписать printTable следующим образом:

Циклы for содержат в скобках три компонента, разделенных точкой с запятой: инициализатор, условие и обновление.

1. Инициализатор выполняется один раз в самом начале цикла.
2. Условие проверяется каждый раз через петлю. Если оно ложно, цикл завершается. В противном случае выполняется тело цикла (снова).
3. В конце каждой итерации запускается обновление , и мы возвращаемся к шагу 2.

Цикл for часто легче читать, потому что он помещает все операторы, связанные с циклом, в начало цикла.

Есть одно различие между циклами for и while: если вы объявляете переменную в инициализаторе, она существует только внутри цикла for. Например, вот версия printRow, в которой используется цикл for:

Последняя строка пытается отобразить i (только для демонстрации), но это не сработает. Если вам нужно использовать переменную цикла вне цикла, вы должны объявить ее вне цикла, например:

Присваивания вроде i = i + 1 нечасто появляются в циклах for, потому что Java предоставляет более лаконичный способ сложения и вычитания на единицу. В частности, ++ - оператор приращения; он имеет тот же эффект, что и i = i + 1. А - оператор декремента; он имеет тот же эффект, что и i = i - 1.

Если вы хотите увеличить или уменьшить переменную на величину, отличную от 1, вы можете использовать + = и - =. Например, i + = 2 увеличивает i на 2.

7.6 Цикл do-while

Операторы while и for являются циклами предварительного тестирования; то есть они проверяют условие сначала и в начале каждого прохождения цикла.

В Java также есть цикл посттестирования: оператор do-while. Этот тип цикла полезен, когда вам нужно запустить тело цикла хотя бы один раз.

Например, в Разделе 5.7 мы использовали оператор return, чтобы избежать чтения недопустимого ввода от пользователя. Мы можем использовать цикл do-while, чтобы продолжать читать ввод до тех пор, пока он не станет действительным:

Хотя этот код выглядит сложным, по сути, он состоит всего из трех шагов:

1. Показать подсказку.
2. Проверить ввод; если недействителен, отобразите ошибку и начните заново.
3. Прочтите ввод.

Код использует переменную флага, хорошо, чтобы указать, нужно ли нам повторять тело цикла. Если hasNextDouble () возвращает false, мы потребляем недопустимый ввод, вызывая next (). Затем мы отображаем сообщение об ошибке через System.err. Цикл завершается, когда hasNextDouble () возвращает true.

7.7 Прервать и продолжить

Иногда ни предварительный, ни посттестовый цикл не обеспечивают именно того, что вам нужно. В предыдущем примере «тест» должен был произойти в середине цикла. В результате мы использовали переменную флага и вложенный оператор if - else.

Более простой способ решить эту проблему - использовать оператор break. Когда программа достигает оператора break, она выходит из текущего цикла.

Использование true в качестве условия в цикле while - это идиома, которая означает «цикл навсегда» или, в данном случае, «цикл до тех пор, пока вы не дойдете до оператора break».

В дополнение к оператору break, который завершает цикл, Java предоставляет оператор continue, который переходит к следующей итерации. Например, следующий код считывает целые числа с клавиатуры и вычисляет промежуточный итог. Оператор continue заставляет программу пропускать любые отрицательные значения.

Хотя операторы break и continue дают вам больше контроля над выполнением цикла, они могут затруднить понимание и отладку кода. Используйте их экономно.

7.8 Словарь

7.9 Упражнения

Код для этой главы находится в каталоге ch07 ThinkJavaCode. См. Страницу ?? для получения инструкций по загрузке репозитория. Перед тем, как приступить к упражнениям, мы рекомендуем вам скомпилировать и запустить примеры.

Если вы еще не прочитали Приложение A.5, возможно, сейчас самое подходящее время. Он описывает Checkstyle, инструмент, который анализирует многие аспекты вашего исходного кода.

Рассмотрим следующие методы:

1. Нарисуйте таблицу, которая показывает значения переменных i и n во время выполнения цикла. Таблица должна содержать по одному столбцу для каждой переменной и по одной строке для каждой итерации.
2. Что дает эта программа?
3. Можете ли вы доказать, что этот цикл завершается при любом положительном значении n?

Допустим, вам дано число a , и вы хотите найти его квадратный корень. Один из способов сделать это - начать с грубого предположения об ответе, x 0 , а затем улучшить предположение, используя эту формулу:

Например, если мы хотим найти квадратный корень из 9 и начинаем с x 0 = 6 , тогда x 1 = (6 + 9/6) / 2 = 3,75 , что ближе. Мы можем повторить процедуру, используя x 1 для вычисления x 2 и так далее. В этом случае x 2 = 3,075 и x 3 = 3 00091 . Таким образом, он быстро приходит к правильному ответу.

Напишите метод под названием squareRoot, который принимает значение типа double и возвращает приближенное значение квадратного корня из параметра, используя эту технику. Вы не должны использовать Math.sqrt.

Как ваше первоначальное предположение, вы должны использовать / 2 . Ваш метод должен повторяться до тех пор, пока он не получит две последовательные оценки, которые отличаются менее чем на 0,0001. Вы можете использовать Math.abs для вычисления абсолютного значения разницы.

В упражнении 9 мы написали рекурсивную версию power, которая принимает двойное x и целое число n и возвращает xn . Теперь напишите итерационный метод для выполнения того же вычисления.

В разделе 6.7 представлен рекурсивный метод вычисления факториальной функции. Напишите итеративную версию факториала.

Один из способов вычислить ex - использовать расширение бесконечного ряда:

Я й член в серии XI / я! .

Напишите метод под названием myexp, который принимает x и n в качестве параметров и оценивает ex , добавляя первые n членов этого ряда. Вы можете использовать факторный метод из Раздела 6.7 или вашу итерационную версию из предыдущего упражнения.

Вы можете использовать escape-последовательность «\\ t», чтобы поместить символ табуляции между столбцами таблицы.

Один из способов оценить exp (- x 2) - использовать расширение бесконечного ряда:

Я й член в этой серии (-1) IX 2 я / я! . Напишите метод с именем gauss, который принимает x и n в качестве аргументов и возвращает сумму первых n членов ряда. Вы не должны использовать factorial или pow.