[МУЗЫКА] Начинаем изучение темы: «Алгоритмы с досрочным выходом из цикла». Прежде всего, нам нужно понять, что именно имеется ввиду под досрочным выходом. В алгоритмах с досрочным выходом из цикла, во-первых, мы всегда используем целый тип данных, так как мы собираемся сравнивать наши данные на точное равенство. Сравнение на точное равенство возможно только для данных целого типа, потому что данные вещественного типа хранятся с определённой точностью, которая не позволит их нам сравнить абсолютно точно. Итак, под алгоритмом с досрочном выходом из цикла мы будем понимать такой алгоритм, в котором цикл может завершиться раньше, чем мы дойдём до последнего элемента массива. И для досрочного выхода из цикла мы всегда будем использовать циклы с предусловием и с постусловием. Вообще говоря, для досрочного выхода из цикла можно использовать и другие конструкции. Например, можно использовать brake, а также можно использовать go to. Но мы с вами делать так не станем, потому что использование этих операторов является нарушением принципов структурного программирования. Мы будем с вами писать такие алгоритмы, которые удобно анализировать и изменять, если нам это необходимо. Итак, рассмотрим первую задачу, на примере которой мы попробуем классифицировать, какие именно способы существуют для организации досрочного выхода. Условие задачи такое: нам дан массив X, количество элементов в котором равно n, и число A. Если в массиве существует хотя бы один элемент, равный этому числу, то мы с вами должны просуммировать все элементы, расположенные после него. Если же такого числа не найдётся, то нам нужно вывести сообщение об отсутствии суммы. Начнём с постановки задачи. Нам дана длина массива, нам дан сам массив X, и нам дано число, с которым мы будем сравнивать. Результатом будет сумма или сообщение о том, что суммы у нас нет. Ограничение на исходные данные касаются длины массива, она должна быть натуральным числом и не превышать максимально возможной длины массива. И рассмотрим, как у нас в данном случае выглядит пункт «связь». В нашем массиве существует некоторый номер k такой, что элемент с этим номером будет равен нашему числу A, и при этом, если мы рассмотрим элементы, расположенные до нашего найденного числа, то среди них элементов, равных заданному числу A, не будет. И затем мы суммируем все наши элементы, начиная с номера k + 1, то есть сразу после найденного числа и до конца массива. Теперь рассмотрим, каким образом мы можем организовать досрочный выход из цикла. Первый приём состоит в следующем: мы с вами вводим исходные данные и берём булевскую логическую переменную flag, которая у нас является признаком наличия элемента, равного заданному. Её начальное значение равно false, то есть «ложь», пока мы не нашли такого элемента. И затем мы берём переменную цикла i и придаём ей начальное значение, равное 1, то есть мы начнём с первого элемента массива. Далее мы записываем цикл, Цикл-«пока» i < n. Иными словами говоря, пока мы не дошли до конца массива, и flag имеет значение false. То есть пока значение flag ещё не изменилось. Далее в теле цикла мы проверяем: если наш текущий элемент массива равен заданному числу, то тогда мы запомним номер того элемента, начиная с которого мы будем вести наши суммирования. То есть k присвоим i + 1, и, кроме того, flag присвоим «истина». Это будет признак того, что наш элемент уже найден. Затем, в противном случае мы просто возьмём следующий элемент массива, закроем наше условие и закроем наш цикл. И далее мы можем по достигнутому значению переменной flag посмотреть, найден ли элемент, равный заданному, или нет. Если наш flag сохранил значение, равное false, значит мы не нашли ни одного элемента, равного заданному, и, следовательно, суммирование невозможно. Замечу, что суммирование невозможно также в том случае, если наш элемент находится на последнем месте, поэтому в заголовке цикла мы записали условие: i < n, а не ≤. Если наш элемент находится на последнем месте в массиве, то суммы тоже не будет. Итак, анализируем, чему равен flag. Если наш flag по завершении цикла имеет значение, равное false, то мы выводим сообщение о том, что у нас нет суммы. А в противном случае мы производим суммирование. Начальное значение суммы является 0, затем мы запускаем цикл от i = k до n, то есть от элемента, следующего за найденным, и до конца массива. И на каждом шаге к сумме прибавляем очередной элемент массива. Затем выводим полученное значение суммы, завершаем наше условие ключевым словом «всё», и на этом алгоритм заканчивается. И этот алгоритм использует две переменных для того, чтобы организовать досрочный выход из цикла. Первая переменная – булевская, которая показывает, найден ли нужный элемент, а вторая — текущий номер шага, который показывает, к какому элементу массива мы сейчас обращаемся. Первый вариант нашего алгоритма использовал логическую переменную для организации досрочного выхода из цикла. Сначала мы вводили исходные данные, то есть сначала мы вводили количество элементов в массиве x и сами эти элементы, затем при помощи логической переменной мы с вами организовывали цикл в виде a – число для сравнения. Мы присваивали flag, логической переменной, начальное значение «ложь», а номеру элемента присваивали 1. Далее, пока мы не дошли до конца массива и flag остаётся равным false, мы сравнивали текущий элемент массива с нашим числом. Если они были равны, то мы запоминали номер элемента, где это равенство достигнуто, и меняли flag. Как только наш flag изменял своё значение с false на true, то есть с «лжи» на «истину», цикл завершался. Если при выходе из нашего цикла flag сохранял значение false, это означает, что у нас нет суммы нужных элементов. Именно суммы, а не нужного элемента, потому что, если нужный элемент располагается на самом последнем месте, то суммы здесь тоже нет. И в противном случае, если элемент найден, мы считали сумму, начальным значением её был 0, и начинали мы от i = k. Давайте попробуем запустить нашу программу и посмотреть, как она работает. Итак, сначала ввожу количество элементов в массиве, допустим, 5 штук, затем введу сами элементы: 1 2 −5, ещё раз 2 6. Теперь я ввожу число a. Предположим, число a = 2. Двойка встречается в нашем массиве два раза, и должна считаться сумма элементов, расположенных после первой двойки, причём сама двойка в сумму не входит. Итак, посмотрим, чему равна наша сумма: −5 + 2 + 6 = 3. Правильно. Теперь запустим программу ещё раз, попробуем дать исходные данные, при которых результата не будет. Допустим, в массиве три элемента: 2 4 и 1, а число a, допустим, равно 0. В данном случае у нас вами нет суммы. То есть наш алгоритм работает правильно, как в том, так и в другом случае. Давайте попробуем ещё третий случай изучить. Предположим, у нас количество элементов массива равно 4, числа у нас 1 2 3 и 4, а число a = 4. То есть такой элемент в нашем массиве есть, но он располагается на последнем месте. В этом случае суммы также нет. Но можно попытаться обойтись и без логической переменной. Для этого рассмотрим второй вариант алгоритма. Мы используем другое условие выхода из цикла. Итак, рассмотрим только фрагмент, который касается вычислений. Ввод данных я опускаю, потому что он точно такой же, как был в предыдущем варианте. Вначале я беру номер элемента, равный 1. Затем я организую цикл с условием, эквивалентным предыдущему. Пока i < n, то есть не дошли до конца массива, и наш элемент текущего массива X не равен заданному числу A. На каждом шаге этого цикла я прибавляю к i единицу. Понятно, что этот цикл может завершиться в одном из двух случаев: или, когда у нас нарушится первое условие, то есть i = n, мы дошли до последнего элемента массива, или у нас Х[i] = A. Нас интересует случай, когда у нас Х[i] = A, в этом случае мы будем производить суммирование. А в противном случае, если наше i = n, то мы тогда выводим сообщение о том, что у нас нет суммы. Если же i ≠ n, то мы тогда будем вычислять нашу сумму, эту часть алгоритма я тоже пропущу, потому то она совершенно аналогична вычислению суммы в предыдущем варианте. Посмотрим на этот вариант алгоритма. Мы с вами видим, что этот вариант несколько короче, в нем меньше переменных. Ну, правда, он требует некоторого другого анализа результата, хотя, в принципе, результат здесь понятен: или мы с вами дошли до конца массива и не нашли числа равного заданному на первых n − 1 местах, или мы вышли потому что элемент наш стал равен заданному числу и тогда i у нас осталось меньше, чем n. И далее мы, начиная с элемента, следующего за найденным, будем производить суммирование. Рассмотрим, как выглядит программа, которая реализует второй вариант алгоритма, там, где у нас с вами не использовалась логическая переменная flag, а вместо flag у нас выступал номер элемента. В начале номер элемента был равен 1, пока мы не дошли до конца массива и не нашли элемента равного заданному, мы увеличивали номер элемента. Если при выходе из цикла этот номер был равен n, то есть мы не вышли из цикла, потому что элемент стал равен заданному числу, то тогда у нас нет суммы, а в противном случае мы считаем сумму, начиная от элемента, следующего за тем, на котором завершился наш цикл. Потому что наш цикл будет завершаться в одном из двух случаев: либо у нас i = n, то есть у нас кончились элементы, которые могут участвовать в суммировании, либо Xi стало равно a, и в этом случае у нас с вами i остается меньшим n, то есть мы нашли нужный элемент и цикл завершился досрочно, в этом случае считается сумма. Давайте попробуем проверить, как работает наш алгоритм во всех тех случаях, которые мы проверяли для первого варианта. Итак, первым делом дадим исходные данные, при которых у нас будет сумма. Допустим шесть элементов массива, элементы: 1 0 −2 4 2 и 8, и, к примеру, число a = 0. Сумма элементов получилась равной 12. Это правильный результат. Обращаю ваше внимание, что если у нас несколько одинаковых чисел, например, вот так… Шесть элементов: 1 2 0, 2 3 и 2, и если я введу число a = 2, то сумма у меня начинает считаться после первой двойки, то есть это 2 + 3 + 2 = 7. Если же такого элемента нет, допустим вот так… Четыре элемента: 1 2 3 и 4, а заданное число, скажем, равно 5, то в этом случае выводится сообщение о том, что нет суммы. Если оно расположено на последнем месте, допустим вот так… Три элемента: 1 2 и 3, а заданное число равно 3, то в этом случае суммы также нет, то есть и этот вариант алгоритма работает правильно во всех возможных случаях. В третьей разновидности нашего алгоритма мы с вами учтем тот факт, что мы вообще-то должны перебрать все элементы нашего массива, от первого до последнего. Просто на каждом шаге мы с вами делаем разные действия. Если наш элемент еще не найден, мы берем следующий элемент, а если он уже найден, то мы суммируем. При этом, если на каком-то шаге элемент найден в первый раз, то мы просто должны запомнить, что теперь наш элемент найден и мы переходим к суммированию. Рассмотрим, как выглядит наш алгоритм, если мы не используем досрочного выхода из цикла. В начале мы с вами должны ввести исходные данные. Мы опять берем логическую переменную flag, даем ей начальное значение «ложь», то есть наш элемент еще не найден, и начальное значение суммы будет равным 0. Теперь мы устроим цикл по всем номерам элементов массива — от первого до предпоследнего, и далее мы будем на каждом шаге цикла проверять: если у нас flag в данный момент равен false, то есть наш элемент еще не найден, то мы смотрим, не найден ли он сейчас на этом шаге. То есть если X[i] наше будет равно заданному числу A, то тогда мы поменяем flag на «истину», и, таким образом, flag покажет, что у нас найден нужный элемент. Закроем это условие и рассмотрим «иначе», которое относится к первому «если». Если у нас к первому «если» написано «иначе» — это значит, что flag наш уже равен «истине», то есть такой элемент, который равен заданному числу был уже найден. Следовательно, на этом шаге мы должны суммировать, то есть мы прибавим к сумме наш очередной элемент массива. Мы закрываем первое условие и завершаем цикл. Теперь проверяем. Если наш flag по-прежнему при выходе из этого цикла равен false, следовательно мы не нашли ни одного элемента равного заданному числу, и суммы у нас нет. В противном случае мы должны завершить наше суммирование, прибавив к сумме последний элемент массива, потому что этот номер мы в цикле не рассматривали. Прибавляем к нашей сумме последний элемент массива, выводим найденное значение суммы, а затем закрываем последнее условие и завершаем наш алгоритм. При решении различных задач, где нужен досрочный выход из цикла, мы будем использовать все рассмотренные варианты. Теперь рассмотрим третий вариант алгоритма, где мы с вами перебирали все элементы массива и выполняли различные действия в зависимости от того, найдено ли уже нужное нам число или нет. Здесь у нас булевская переменная flag показывала найдено ли у нас число. Начальное значение сумме присваивалось до начала цикла, который перебирает все элементы от первого до предпоследнего, и если у нас на каком-то шаге flag еще равен false, то есть еще не найден нужный нам элемент, то тогда мы смотрим, не найден ли он именно на этом шаге. Если X[i] стало равно A, то мы изменим значение переменной flag на «истину», и тогда на следующих шагах суммирование уже происходит. Если же у нас flag уже имел значение true («иначе») от flag равного false, то мы прибавляли к сумме очередной элемент. Когда цикл у нас закрыт, переменная flag показывает, есть у нас сумма или нет. Если он равен false, то суммы нет, в противном случае у нас с вами к сумме нужно прибавить последний элемент, потому что он не рассматривался в нашем цикле, мы рассматривали элементы только до предпоследнего, и выводилось значение суммы. Давайте снова протестируем наш алгоритм, для того чтобы понять, всегда ли он правильно работает. Итак, у нас с вами были следующие случаи. Когда есть хотя бы один элемент равный, заданному числу. Допустим, шесть элементов: 1 0 2 0 3 и 7. Если я введу число a равное 0, то считается сумма элементов, начиная с элемента, следующего за первым 0, — 3 + 7 + 2 = 12. Программа работает верно. Если у нас нет такого числа, ну, например, четыре элемента: 2 4 6 и 8, а заданное число равно 1, то суммы у нас нет. Если число располагается на последнем месте, хотя и равно заданному, допустим четыре элемента: 2 4 6 и 8, а заданное число равно 8, то в этом случае суммы также нет. То есть и третий вариант нашего алгоритма также работает правильно для всех возможных случаев. [МУЗЫКА] [МУЗЫКА]
