Применение функций при решении задач

Вопросы:

·     Использование функций при решении задач.

·     Повторное использование кода

·     Модульность.

Рассмотрим первую задачу. В 1742 году член Российской академии наук, математик Кристиан Гольдбах отправил письмо своему другу и коллеге, швейцарскому математику Леонарду Эйлеру, в котором привёл гипотезу о том, что любое натуральное число не меньше 6 можно представить в виде суммы трёх простых чисел. В ответ на это Эйлер заметил, что эту гипотезу можно свести к тому, что любое чётное число не меньше 4 можно представить в виде суммы двух простых чисел. Полученная гипотеза была названа гипотезой Гольдбаха. Она остаётся и не подтверждённой, и не опровергнутой по сей день.

Напишем программу, которая для заданного чётного натурального числа n ≥ 4, проверяет гипотезу Гольдбаха. Если гипотеза была подтверждена, нужно вывести простые числа, суммой которых является заданное n.

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

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

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

Начнём написание этого модуля. Назовём его SimpleNum. Для начала опишем функцию, определяющую, является ли целое число простым. Назовём функцию isSimple. Это будет логическая функция, так как она вернёт одно из двух значений типа bool. Названия логических функций обычно начинаются со слова is. У функции будет один аргумент – целое положительное число n. В теле функции сначала проверим делимость n на 2. Для этого запишем ветвление с условием, что n % 2 == 0 и n != 2, так как 2 – простое число. Если это условие выполняется, значит n не является простым числом, а далее будет следовать инструкция возврата, завершающая работу функции и возвращающая значение False.  Для расчёта квадратного корня из n нам понадобится соответствующая функция из модуля math. Загрузим её в описываемый модуль за пределами функции. Далее напишем цикл для проверки делимости n на нечётные числа от 3 до квадратного корня из него самого. Это будет цикл с параметром i, изменяющимся в диапазоне от 3 до целой части из квадратного корня из n, увеличенной на два, с шагом два. В теле цикла мы запишем ветвление с условием, что n % i == 0, при этом n ! =i. Если это условие выполняется, то мы завершим работу функции, вернув значение False, так как число n не является простым. После цикла, если функция ещё не завершила свою работу – число n является простым, и мы завершим работу функции, вернув значение True. На этом описание первой функции будет завершено.

from math import sqrt

def IsSimple (n):

    if n % 2 == 0 and n != 2:

        return False

    for i in range (3, int (sqrt (n)) + 2, 2):

        if n % i == 0 and n != i:

            return False

    return True

Опишем функцию поиска минимального простого числа, следующего после k. Назовём её nextSimple. У неё будет один параметр – целое число k. В теле функции сначала увеличим значение k на единицу, так как нас интересуют числа после k. Дальше проверим не больше ли k 2. Если это так, то следующим будет минимальное простое число 2 и мы завершим работу функции, вернув это значение. Если k больше 2, то мы продолжим поиск простого числа. Так как чётное число, которое больше 2, не может быть простым, то мы будем искать его среди нечётных чисел. Поэтому проверим чётность k, записав ветвление с условием, что k % 2 == 0; если это условие выполняется, перейдём к следующему нечётному числу, увеличив k на 1. Далее запишем цикл для перебора нечётных чисел, пока одно из них не окажется простым. Это будет цикл while, который будет работать до тех пор, пока k не окажется простым числом. В качестве условия цикла с отрицанием укажем значение функции isSimple (k). Тело цикла будет содержать всего одну команду – переход к следующему нечётному числу, то есть увеличение k на 2. Цикл завершит свою работу, когда число k будет простым. Поэтому после цикла завершим работу функции, вернув значение k. Мы завершили описание модуля. Сохраним его.

def NextSimple (k):

    k = k + 1

    if k <= 2:

        return 2

    else:

        if k % 2 == 0:

            k = k + 1

        while not IsSimple (k):

            k = k + 2

        return k

Теперь напишем модуль для решения задачи. Назовём его Goldbach и сохраним в одной папке с модулем SimpleNum. Загрузим в наш модуль обе функции из модуля, описанного ранее. С помощью инструкции print выведем на экран сообщение о том, что это программа, проверяющая гипотезу Гольдбаха для заданного n. С помощью следующей инструкции print выведем на экран запрос на ввод n без перехода на следующую строку. Далее запишем инструкцию для считывания n. По условию задачи n – целое, поэтому при считывании преобразуем его в целочисленный тип int.  Теперь нам нужно найти такое простое m < n, при котором разность n – m также будет простым числом. Объявим переменную m, которой присвоим наименьшее простое число – 2. Дальше запишем цикл для поиска m, удовлетворяющего заданному условию. Он будет работать до тех пор, пока m < n и n – m не является простым числом. То есть вторая часть условия цикла – это с отрицанием значение функции isSimple (n - m). Тело цикла будет содержать единственную команду – присваивания переменной m следующего простого числа, то есть значения функции nextSimple (m). После завершения работы цикла, чтобы проверить, верна ли гипотеза, запишем ветвление с условием m < n. Если это условие выполняется, значит было найдено простое число m, удовлетворяющее условию задачи и мы с помощью инструкции print выведем на экран сообщение о том, что для заданного числа n гипотеза подтверждена и что n равно сумме m и числа n минус m. Если же условие не выполняется, мы выведем на экран сообщение о том, что гипотеза опровергнута. На этом описание модуля завершено.

from SimpleNum import isSimple, nextSimple

print ('Программа, проверяющая гипотезу Гольдбаха для заданного N.')

print ('N = ', end = '')

n = int (input ())

m = 2

while m < n and not isSimple (n - m):

    m = nextSimple (m)

if m < n:

    print ('Для числа', n, 'гипотеза подтверждена.', n, '=', m, '+', n - m)

else:

    print ('Гипотеза опровергнута.')

Сохраним модуль и запустим на выполнение. Введём число 74. Программа вывела на экран сообщение о том, что для числа 74 гипотеза подтверждена и что его можно представить в виде суммы простых чисел: 3 и 71.  Снова запустим программу на выполнение и зададим число 1024. Программа вывела сообщение о том, что для числа тысяча двадцать четыре гипотеза подтверждена и что его можно представить в виде суммы простых чисел: 3 и 1021. Программа работает правильно. Задача решена.

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

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

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

Начнём написание программы для решения задачи. Наверняка многие догадались, что для этого нам будет полезна функция поиска следующего простого числа nextSimple из модуля SimpleNum, описанного ранее, поэтому загрузим её в описываемый модуль. С помощью инструкции print выведем на экран сообщение о том, что это программа для разложения числа n на простые множители. С помощью следующей инструкции print выведем на экран запрос на ввод n без перехода на следующую строку. Дальше напишем инструкцию для считывания n. По условию задачи n – целое число, поэтому при считывании преобразуем его значение в целочисленный тип int. Объявим переменную m, в которой будем хранить простые числа. Присвоим ей наименьшее простое число – 2. С помощью инструкции print выведем на экран сообщение, состоящее из значения переменной n и знака равенства, а также объявим логическую переменную p, в которой будем хранить истинность высказывания о том, что ни одного простого множителя ещё не найдено. Так как пока это правда, присвоим p значение True.

Далее напишем цикл для поиска множителей n. Это будет цикл while, который будет работать до тех пор, пока n > 1. В цикле запишем ветвление с условием, что n % m == 0. Если это условие выполняется, объявим переменную-счётчик s = 0, в ней будем рассчитывать степень найденного простого числа m в составе n. Запишем для этого цикл. Он будет работать до тех пор, пока n % m != 0. В нём будем увеличивать значение счётчика s на 1, а n нацело делить на m.  По завершении работы цикла в переменной s будет содержаться степень m. Запишем ветвление, которое проверяет, является ли найденное простое число m первым делителем n. Его условием будет значение логической переменной p. Если значение переменной p – «истина», то m – это первый найденный множитель n. Присвоим p значение False, после чего выведем на экран без перехода на следующую строку сообщение m ^ s, в противном случае m – не первый найденный множитель, и мы выведем на экран сообщение * m ^ s. После внешнего ветвления присвоим переменной m значение следующего простого числа, найденного с помощью функции nextSimple (m).

from SimpleNum import nextSimple

print ('Программа для разложения числа N на простые множители.')

print ('N = ', end = '')

n = int (input ())

m = 2

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

p = True

while n > 1:

    if n % m == 0:

        s = 0

        while n % m == 0:

            s = s + 1

            n = n // m

        if p:

            p = False

            print (m, '^', s, end = '')

        else:

            print (' *', m, '^', s, end = '')

    m = nextSimple (m)

Мы завершили описание модуля. Запустим его на выполнение. Введём число 1024. Это число действительно можно представить в виде 2 ^ 10. Снова запустим модуль и зададим число 7. Оно простое, поэтому его можно представить в виде 7 ^ 1. Снова запустим модуль и зададим число 1000. Его действительно можно представить в виде произведения 2 ^ 3 * 5 ^ 3. Программа работает правильно. Задача решена.

Мы узнали:

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

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

·     Эти принципы увеличивают количество доступных инструментов и позволяют ускорить разработку новых программ.