Циклы

Лекция 3 Циклы В прошлый раз мы не договорили о цикличных алгоритмах. Я бы назвал их просто циклами. Сложно вообще объяснить, что есть цикличный алгоритм и почему он именно цикличный? Просто потому что какие-то действия повторяются? Или потому что он работает, пока не будет найден результат? Как бы там ни было, цикл, как и условие — это базовая единица кода. Почему единица? Потому что это настолько простая вещь, что она используется чуть ли не в каждой программе. Повторение действий — это одно из преимуществ компьютера. Он делает это быстро, легко и не скучает. Если в алгоритме есть возврат к предыдущему шагу, скорей всего это алгоритм с циклом. Давайте посмотрим простейший пример: 1. 2. 3. 4. 5. 6. Ввести данные Убедится, является ли введенное число положительным Если да, то вывести на экран Конец программы Если нет, попросить пользователя ввести положительное число. Переход на шаг 1. Возможно покажется странным, что конец программы — это четвертый шаг. А после есть и другие шаги. На самом деле — это нормально. Это просто описание того, что должна сделать программа, и никто не может возражать, если конец программы окажется в ее середине. Более того, никто не может возражать, даже если вы сделаете это в реальном коде (конечно, на определенных условиях, о которых в следующий раз). Давайте напишем эту программу: int main(void) { int i = 0; begin: printf("Введите положительное число\n"); scanf("%i", &i); if (i >= 0) { printf("Введенное положительное число: %i", i); return 0; } goto begin; } Сразу смущает begin. Вообще, это «метка», так мы отмечаем, в какое место программы мы хотим перейти оператором goto. Очень давно писались номера строк программы и goto переносил именно на выбранную номером строку. Но отмечать каждую строку числом очень утомительно, поэтому давно уже отказались от такого подхода. Но наследие осталось, старинный оператор goto живет даже в современных языках, хотя реально им уже давно никто не пользуется. Все дело в том, что программы, перескакивающие туда сюда сложно читать. Программа, описанная выше, очень короткая, и в ней было бы просто разобраться. Но представьте, что на 4678 строчке программы, вам вдруг понадобилось бы перейти на 8756, чтобы узнать, чем же все заканчивается. Довольно неудобно. Хотя этот пример и нереальный, в действительности, столь длинные участки кода просто не пишут, их разбивают на модули. Но ведь и пример довольно простой, а что если бы у нас на 100 строчек, было бы 20 меток, разбросанных всюду? Плюс, это и выглядит не очень красиво, да и не очень то понятно, будет ли вообще возврат на эту метку, ведь наличие метки еще возврат на нее не гарантирует. В общем, программисты условились избегать оператора goto, и использовать только в крайней необходимости. Как вы поймете в далеком будущем, этой крайней необходимости просто нет. Так что помните о goto, но не используйте никогда. Чем же его можно заменить? Сама по себе строчка «Переход на шаг 1» говорит нам о повторении действий, о цикле. (Если бы был «переход на шаг 100», т. е. в следующую часть программы, то очевидно, что это не цикл) Но тут явно повторение предыдущих шагов. И на лицо условие выхода из цикла - «Конец программы». Давайте просто представим, что шага 3 и 4 не было. Программа просто повторяла введите положительное число, и ей было бы наплевать, даже если вы ввели положительное число. Ведь последовательность действий говорит: всегда переходить на шаг 1. Это называется бесконечным циклом. Она будет работать, пока пользователь сам не завершит ее, используя «аварийное завершение». Ctrl + C в консоли или «уничтожить процесс» в диспетчере операционной системы (далее ОС). Бесконечные циклы часто бывают проблемой для неопытных программистов, но вы начнете их видеть с опытом, задолго до запуска вашей программы. Кстати, в ideone.com вы получите завершение программы с Ошибка выполнения time: 0 Давайте перепишем программу, согласно новому понятию цикла: 1. Вводить данные, пока не будет введено положительное число 2. Вывести на экран 3. Конец программы Как просто на словах, но ничуть не сложнее в коде while(i < 0) { printf("Введите положительное число\n"); scanf("%i", &i); } printf("Введенное положительное число: %i", i); Как видите, это даже читается легко: Пока i < 0, введите положительное число. Как только i станет больше либо равным нулю, цикл завершится, потому что условие продолжения будет нарушено. Все верно внутри скобок while пишется условие продолжения. Это интуитивно понятней, чем условие выхода в Паскале. Вообще, я слукавил. Тут можно легко словить баг по неопытности. Баг — это, когда программа написана синтаксически верно, но вот беда, правильно она не работает! Типичный новичок напишет вот такой код: int main(void) { int i; while(i < 0) { printf("Введите положительное число\n"); scanf("%i", &i); } printf("Введенное положительное число: %i", i); } И будет разочарован выводом программы: Введенное положительное число: 1433300557 А где, спрашивается, мой цикл?! Вон же он написан, почему программа его игнорирует?! Все дело в том, что переменная «i» не была определена (инициализирована). Она была объявлена, о чем мы можем догадаться по int i; Но значение ей не было присвоено. Неопределенные локальные переменные получают какое-то неопределенное значение. Хоть это и выглядит забавно, но оно так и есть, предсказать, что там за значение в неопределенной переменной i никто не возьмется. Даже если программист знал об этом, то скорей всего, он написал бы: int main(void) { int i = 0; while(i < 0) { printf("Введите положительное число\n"); scanf("%i", &i); } printf("Введенное положительное число: %i", i); } И снова был бы разочарован. Потому что вывод не изменится. Нуль, ведь, точно не меньше нуля. Разрешить такую ситуацию поможет int i = -1; Но сразу распознать будущий баг в программе, дело опыта. Поэтому не бойтесь багов, чем больше вы их ловите в начале обучения, тем легче будет их отлавливать или предсказывать в дальнейшем. Затем вас может смутить %i, но, возможно, вы уже догадались, что это что-то вроде %d. Это действительно так, просто вводить вы можете с клавиатуры не только числа в десятичной системе счисления (далее СС), но и в шестнадцатеричной, к примеру. %d – decimal, очевидно, подходит только для десятичной СС. Это был один пример цикла с предусловием. А какие еще бывают? – цикл со счетчиком (самый распространенный) – цикл с предусловием (второй по популярности) – цикл с постусловием (в реальном коде никогда не встречал) Давайте сразу рассмотрим 3-тий вариант, потому что он похож на второй, уже рассмотренный и довольно прост. do { <действие> … } while(<условие продолжения>); Принципиально он ничем не отличается от второго случая, просто условие продолжения в конце, и хотя бы раз цикл пройдет. Например, мы бы могли заменить предыдущую программу на: int main(void) { int i; do { printf("Введите положительное число\n"); scanf("%i", &i); } while(i < 0); printf("Введенное положительное число: %i", i); } и перспектива бага отпала бы сама собой. Но в реальном коде цикл с постусловием применяется очень редко, поэтому стоит о нем знать, но пользоваться весьма аккуратно. Все дело в том, что часто бывает необходимость пользоваться старым кодом, и программисты не задумываются о том, что старый код может стать источником багов. И они правы, код следует писать так, чтобы он и не становился источником багов в совершенно другой программе. А вот цикл с постусловием может подвести. Что если i уже положительное число, полученное нами ранее? Зачем нам предлагать вводить его еще раз? В предыдущем случае программа просто пропустит ввод числа, поскольку оно и так удовлетворяет условию. Пусть сейчас вы и не осознаете проблему постусловий, но когда столкнетесь с ней самостоятельно, вспомните об этом предупреждении. Цикл с счетчиком самый интересный и запутанный на первый взгляд. Давайте представим, что нам захотелось вывести первые 50 чисел. Действие определенно повторяющееся: «вывести число». Число меняется, но то что его постоянно нужно выводить — это факт. Более опытные сразу смекнут, что и прибавление к числу единицы, тоже повторяющееся действие, т.о.: int main(void) { int i = 0; while(i < 50) { printf("%i ", i); i++; } return 0; } Бросается в глаза i++, но это эквивалентно i = i + 1; Что в свою очередь эквивалентно i += 1; Это оператор инкремента. Есть и обратный: i--. Увеличивать значение счетчика приходится часто, вот и решили сократить такую операцию до 3 знаков. На самом деле, можно было и сократить эту программу до int main(void) { int i = 0; while(i < 50) printf("%i ", i++); return 0; } Она выдает тот же самый результат. Вас может смутить, то что мы выводим уже увеличенное количество счетчика, но это только на первый взгляд. Если взглянуть глубже на операцию инкремента (i++), то оказывается, что он бывает двух видов. В данном случае — это пост инкремент. Он сначала выдает значение, а потом уже увеличивает переменную. Если вы хотите, чтобы сначала было увеличение на 1, то нужно написать ++i. Кстати, второй вариант еще и быстрее работает, все дело в том, что пост инкремент создает буферное значение переменной. Так что в первом случае писать стоило int main(void) { int i = 0; while(i < 50) { printf("%i ", i); ++i; } return 0; } Эти мелочи могут иметь огромное значение, когда вы ограничены в ресурсах компьютера, исполняющего ваш код. Современный компьютер не почувствует разницы между ++i и i++, более того есть еще и оптимизация компилятора, но грамотней писать, все же, ++i, если вы не используете значение до инкремента в этой же строке. Я не зря упомянул, что циклы со счетчиком самые популярные, ведь можно было и не выделять их в отдельный класс. Но трудно уловить беглым взглядом, что while будет со счетчиком, так что мы имеем специальную запись для такого цикла. for (initializations; condition; updates) { … } initializations — поле инициализации, например int i = 0 condition — поле условия продолжения, например i < 50 updates — поле изменений, например ++i И вот наш предыдущий цикл превращается в: int main(void) { for(int i = 0; i < 50; ++i) printf("%i ", i); return 0; } А программа становится еще короче. Как это работает? При входе в for инициализируется переменная i. (Инициализация = объявление + определение значением) Затем проверяется условие продолжения, если условие истинно, выполняется тело цикла, далее i увеличивается на единицу, снова проверяется условие и т. д. Кстати, если вы еще не проверили, что делает программа, то она выдает числа от 0 до 49 включительно. Важно переучиться считать от 0. Конечно, мы бы могли написать программу и так: int main(void) { for(int i = 1; i <= 50; ++i) printf("%i ", i-1); return 0; } И делала бы она тоже самое, но это плохой стиль, прежде всего вы будете запутывать себя, хоть вам так и не покажется, и, конечно, запутаете человека читающего ваш код, потому что в Си так писать не принято. Почему? Вы это и сами поймете в будущем. Кстати, for очень интересен тем, что вы можете пропускать блоки внутри круглых скобок. Чтобы компилятор не запутался, ставить ; придется, но вот что-то описывать необязательно. Например, следующие циклы эквивалентны int i = 0; for(; i < 50; ++i) printf("%i ", i); int i = 0; for(; i < 50;) printf("%i ", i++); Но читабельности коду это не добавляет. Но, что интересно: for(;;) printf("%i ", i++); даст вам бесконечный цикл. Бесконечный цикл штука любопытная, его можно получить самыми разными способами, не только через for. Как правило, он является ошибкой программиста, но бывает, что так и было задумано. Есть даже способы по досрочному выходу их цикла, используя их, программист может свободно написать бесконечный цикл, зная, что он завершится при некотором условии. Следующая программа выведет числа от 0 до 26 включительно: for(int i = 0; i < 50; ++i) { printf("%i ", i); if (i > 25) break; } break это выход из блока цикла, применяется для любого вида циклов. Но помните, что break работает только для текущего блока. Если у вас for в for, а break написан только во внутреннем цикле, то полностью циклы не приостановятся. Есть также способы пропуска итераций (итерация — это один проход цикла, в предыдущих примерах, кроме последнего, итераций было 50) for(int i = 0; i < 50; ++i) { if (i > 25) continue; printf("%i ", i); } continue не сократит количество итераций до 27, как в предыдущем случае, он просто пропустит те, для которых выполняется условие. Он передает управление в блок updates, чем увеличивает i на единицу. Есть еще более интересные штуки, в for можно писать не одну инициализацию и не один апдейт: for(int i = 0, j = 50; i < j; ++i, --j) { printf("%i ", i); } Попробуйте сами догадаться, что произойдет. Все это очень весело, но в реальности только запутывает, поэтому лучше придерживаться стандартной формы for с одной инициализацией и одним апдейтом. Операторы break и continue пока еще незаменимы, так что их использование — вполне нормально, но оно не должно затруднять чтение программы. Лабораторная работа №3 Задание 0. Вывести последовательность Фибоначчи для заданного с клавиатуры n: для n = 6 1 2 3 5 8 13... Вывести факториал числа n: для n = 5 1*2*3*4*5 = 120 Задание 1. Найти в записи числа наибольшую и наименьшую цифру. Число вводится с клавиатуры, как число, а не как набор символов. (Подсказка: число есть последовательность разрядов. 123 = 100 + 20 + 3) Задание 2. Реализовать игру Black Jack по простейшим правилам. Игроку предлагается выбор: продолжить игру или нет. При продолжении выдается «карта» со случайным номиналом от 2 до 11. Бот набирает карты одновременно с игроком, разработать алгоритм, согласно которому бот хочет выиграть, но должен принимать решение: брать следующую карту или нет. Например, у игрока 18 очков, а у бота 17. Если бот остановится сейчас, он все равно проиграет, так что он должен брать еще одну карту. Или если игрок остановился на 3, а у бота 5, то дальнейший набор карт смысла уже не имеет, бот и так выйграл. Победа присуждается тому, кто набирает больше очков, но до 21. Перебор — это поражение, если же он у обоих, то это ничья.