Комбинирование циклов при решении задач. Сложные циклические алгоритмы

Вопросы:

·     Сложные циклические алгоритмы.

·     Вложенные циклы.

Рассмотрим задачу. Написать программу, которая определяет количество значимых нулей в целом положительном числе, введённом пользователем, кроме нулей в младших разрядах.

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

Напишем программу для решения задачи. Сначала с помощью инструкции print выведем на экран сообщение о том, что это программа, определяющая количество нулей в целом положительном числе, кроме тех, которые находятся в младших разрядах, и запрос на ввод числа. Теперь считаем или число в переменную n. По условию задачи число целое, поэтому при считывании его значение мы будем преобразовывать в целочисленный тип int. Теперь напишем цикл для того, чтобы убрать из числа нули в младших разрядах. Он будет работать, пока остаток от деления n на 10 равен нулю. Тело цикла будет содержать единственную инструкцию присваивания переменной n результата её безостаточного деления на десять. Таким образом, мы будем убирать из числа все правые цифры, равные нулю. Теперь объявим переменную-счётчик количества нулей. Назовём её s и присвоим ей значение 0, так как ни одного нуля мы ещё не учли. Дальше напишем цикл для определения количества оставшихся нулей в числе. Он будет работать до тех пор, пока n > 0. В теле цикла напишем ветвление, которое будет проверять, равна ли правая цифра числа нулю, то есть её n % 10 = 0. Если это условие выполняется, то мы присвоим счётчику s его значение, увеличенное на 1. После того, как мы проверили значение правой цифры, уберём её из числа. Для этого переменной n присвоим результат её безостаточного деления на 10. После цикла переменная s будет содержать ответ на вопрос задачи. С помощью инструкции print выведем на экран сообщение о том, что количество нулей во введённом числе, за исключением младших разрядов равно значению переменной s.

print ('Программа, определяющая количество нулей в целом положительном числе, кроме младших разрядов. Введите число.')

n = int (input ())

while n % 10 == 0:

    n = n // 10

s = 0

while n > 0:

    if n % 10 == 0:

        s = s + 1

    n = n // 10

print ('Количество нулей во введённом числе, кроме младших разрядов:', s)

Сохраним написанный модуль и запустим его на выполнение. Введём число 107 003 500. Очевидно, что в этом числе 5 нулей, но 2 из них находятся в младших разрядах. Поэтому программа вывела значение 3. Снова запустим программу на выполнение и зададим число 32 007. В этом числе действительно 2 нуля, и ни один из них не находится в младшем разряде, поэтому программа вывела 2. Снова запустим программу и введём число 125. В этом числе нет нулей, поэтому программа вывела значение 0. Программа работает правильно, задача решена.

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

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

Начнём написание программы для решения задачи. Сначала с помощью инструкции print выведем на экран сообщение «Таблица Пифагора:». Теперь запишем цикл для перебора номеров строк. Это будет цикл для параметра i, изменяющегося в диапазоне от 1 до 10 с шагом 1, который записывается функцией range (1, 11), так как число одиннадцать не будет включено в диапазон. Тело этого цикла будет содержать ещё один цикл для перебора номеров столбцов.  Это будет цикл с параметром j, изменяющимся в диапазоне от 1 до 11, не включая последнее значение, с шагом 1. Тело этого цикла будет содержать единственную инструкцию print, которая будет выводить на экран значение произведения номеров строки и столбца. Для того, чтобы эти значения выводились в одну строку, в составе функции print изменим параметр end. Это строка, которая выводится по завершении работы инструкции print. По умолчанию эта строка содержит единственный символ перехода на следующую строку.  Зададим вместо него пустую строку. Для того, чтобы наши столбцы получились ровными с помощью функции Формат выделим для каждого из них по четыре знаковых позиции. После того, как мы описали цикл для вывода очередной строки значений, нам нужно перейти на следующую строку. Для этого запишем инструкцию print без параметров. Написание модуля завершено.

print ('Таблица Пифагора:')

for i in range (1, 11):

    for j in range (1, 11):

        print ('{:4d}'.format (i * j), end = '')

    print ()

Сохраним написанный модуль и запустим его на выполнение. Программа действительно вывела на экран таблицу Пифагора. Программа работает правильно. Задача решена.

Обратим внимание на цикл для решения задачи. Очевидно, что тело внешнего цикла выполнилось в программе 10 раз, а тело внутреннего цикла при каждом выполнении внешнего выполнялось 10 раз. Таким образом, тело внутреннего цикла было выполнено в программе 10 раз по 10, то есть 100 раз. Стало быть, при использовании вложенных циклов стоит заранее продумать, сколько раз они будут выполняться в программе, так как от этого зависит время выполнения программы.

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

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

Начнём написание программы для решения задачи. Сначала с помощью инструкции print выведем на экран сообщение о том, что это программа поиска чисел, меньших n, сумма цифр которых совпадает с суммой цифр n. С помощью следующей инструкции print выведем запрос на ввод n без перехода на следующую строку. Для этого в составе инструкции присвоим параметру end пустую символьную строку. Далее считаем значение переменной n с клавиатуры. Так как по условию это целое число, при считывании будем преобразовывать его значение в целочисленный тип int. Теперь рассчитаем сумму цифр числа n. Так как само число n нам ещё понадобится, создадим для расчёта суммы цифр его копию в переменной copy_n. Сумму цифр n будем хранить в переменной s_n. Так как мы ещё не учли ни одной цифры, присвоим ей значение 0. Теперь запишем цикл для расчёта суммы цифр n. Это будет цикл while, повторяющийся до тех пор, пока в переменной copy_n ещё есть цифры, то есть пока она больше нуля. В теле цикла мы будем выделять правую цифру значения переменной copy_n, добавлять её к значению переменной s_n, после чего убирать её из числа. Для этого переменным s_n и copy_n будем присваивать соответственно значения s_n + copy_n % 10, а также n // 10.

После того, как мы рассчитали сумму цифр числа n, в переменной i мы будем искать числа, сумма цифр которых равна значению s_n. Для начала, мы объявим переменную p, которая будет содержать истинность утверждения о том, что такие числа есть. Предположим, что их нет, и присвоим p значение False. Дальше запишем цикл с параметром i, изменяющимся в диапазоне от 1 до n, не включая последнее. В этом цикле мы будем вычислять сумму цифр для каждого значения i. Но так как в теле цикла мы не можем изменять значение i, мы создадим его копию в переменной c и будем вычислять сумму цифр c в переменной s таким же образом, как мы это делали ранее для числа n. Далее мы запишем ветвление, сравнивающее сумму цифр i, которая хранится в переменной s, со значением переменной s_n. Если они совпадают, то мы проверим, является ли число i первым найденным. Для этого запишем ветвление с условием not p. Оно будет выполняться только тогда, когда значение p – False, то есть при условии, что до этого не было найдено ни одного числа. Если это условие выполняется, то мы выведем на экран поясняющее сообщение «Найденные числа», заканчивающееся двоеточием, и присвоим p значение True. Таким образом, это ветвление может сработать всего один раз, то есть тогда, когда мы найдём первое число. После этого ветвления выведем на экран значение числа i. Так мы найдём все числа, которые меньше n, с суммой цифр равной сумме цифр n. Теперь нам осталось только рассмотреть случай, когда таких чисел нет. Для этого напишем ветвление с условием not p, которое при условии, что ни одного числа не было найдено, выведет на экран с помощью инструкции print сообщение о том, что искомых чисел не найдено.

print ('Программа поиска чисел меньших n, сумма цифр которых совпадает с суммой цифр n.')

print ('n = ', end = '')

n = int (input ())

copy_n = n

s_n = 0

while copy_n > 0:

    s_n, copy_n = s_n + copy_n % 10, copy_n // 10

p = False

for i in range (1, n):

    c = i

    s = 0

    while c > 0:

        s, c = s + c % 10, c // 10

    if s == s_n:

        if not p:

            print ('Найденные числа:')

            p = True

        print (i)

if not p:

    print ('Искомых чисел не найдено.')

Описание модуля завершено. Сохраним его и запустим на выполнение. Введём n = 43. Его сумма цифр равна 7, поэтому программа вывела все числа, которые меньше 43, с суммой цифр равной 7: 7, 16, 25 и 34. Снова запустим программу на выполнение и введём число 99. Его сумма цифр равна 18. Положительных чисел, сумма цифр которых равна 18 и которые были бы меньше 99, нет. Программа вывела, что таких чисел не найдено. Программа работает правильно. Задача решена.

Мы узнали:

·     Вложенными циклами называются циклы, которые выполняются в составе других циклов.

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