Программирование в процедурах и функциях

Перевод целого числа из системы с основанием p в систему с основанием q

Заголовок и заголовочный комментарий выписываются просто:

def TranslateIntFromPtoQ(ix:str, p: int, q: int)->str:
    """
    Перевод целого числа x, представленного строкой в системе счисления с основанием p,
    в строку в системе счисления с основанием q
    """ 

Код опять требует декомпозиции. Мы не умеем переводить из p в q, но есть промежуточная система счисления, с которой мы умеем работать, - это привычная десятичная система, поэтому перевод p =" q заменим двумя переводами p =" 10 =" q.

Эта идея позволяет опять-таки написать короткий условно корректный код из нескольких строчек:

    #Декомпозиция к более простым задачам
    if ix == '' :
        return ''
    nx = TranslateIntFromPto10(ix, p)
    sx = TranslateIntFrom10toQ(nx, q)
    return sx;

Вначале проверяется особый случай, когда целой части нет - путая строка, тогда и переводить нечего, результат - это пустая строка. В противном случае последовательно выполняются два перевода из p в 10 и из 10 в q.

Займемся переводами в десятичную систему и обратно. Для десятичной системы уже можно выписать некоторые соотношения, позволяющие сформулировать алгоритм перевода. Пусть N - десятичное целое число. Его можно записать в любой позиционной системе счисления. Пусть p - основание системы, а $$c_k$$ - цифры системы. Тогда запись $$N = c_n c_{n-1}\dots c_0$$ в реальности означает:

Соотношение (*) позволяет достаточно просто записать алгоритм перевода целого числа из системы с основанием p в десятичную систему. В этом случае известны цифры $$c_k$$ и основание p. Соотношение (*) - это частный случай полинома n-й степени и значение N вычисляется по известной ранее рассмотренной схеме Горнера.

Обратный перевод из десятичной системы в систему с основанием p выполняется также достаточно просто, используя соотношение (*). В этом случае известно N и p, требуется найти цифры $$c_k$$. Остаток от деления нацело N на p позволяет получить последнюю цифру в записи числа, а операция деления нацело позволяет отрезать эту цифру. Применяя в цикле эту пару операций n + 1 раз, получим все нужные цифры.

Приведу вначале функцию перевода целого числа из p в 10, использующую схему Горнера:

def TranslateIntFromPto10(ix:str, p: int)->int:
    """
    Перевод целого числа x, представленного строкой в системе счисления с основанием p,
    в число в десятичной системе счисления
    2 <= p <= 30
    """
    if ix == '' :
        return 0
    digits = '0123456789ABCDEFGHIJKLMNOPQRST'
    res = 0 
    n = len(ix)
    for i in range(n):
        sd = ix[i] 
        d = digits.index(sd)
        res = res * p + d
    return res

Вначале анализируется особый случай, когда число задается пустой строкой. Результат в этом случае равен нулю. Поскольку цифры могут быть заданы буквенными символами, то для них необходимо определить численное значение. С этой целью вводится строка цифр digits. Индекс вхождения цифры в эту строку дает численное значение цифры. Эта небольшая модификация стандартной схемы Горнера дает решение задачи. И здесь, как мы видим десяти строк кода хватает для записи алгоритма.

Вот код алгоритма перевода целого числа из десятичной системы в систему с основанием q:

def TranslateIntFrom10toQ(nx: int, q: int)->str:
    """
    Перевод целого числа nx в систему счисления с основанием q
    2 <= q <= 30
    """
    if nx == 0 :
        return ''
    digits = '0123456789ABCDEFGHIJKLMNOPQRST'
    res = ''
    while nx > 0:
        d = nx % q
        nx = nx // q
        res = digits[d] + res
    return res

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

Перевод дроби из системы с основанием p в систему с основанием q

Для перевода дроби будем использовать ту же идею перевода дроби, используя промежуточную десятичную систему:

def TranslateFractFromPtoQ(ix:str, p: int, q: int)->str:
    """
    Перевод дроби - числа x, представленного строкой в системе счисления с основанием p,
    в строку в системе счисления с основанием q
    """
    #Декомпозиция к более простым задачам
    if ix == '' :
        return ''
    nx = TranslateFractFromPto10(ix, p)
    sx = TranslateFractFrom10toQ(nx, q)
    return sx   

Сам код прозрачен, условно корректен, так что остается только понять, как дробь из системы с основанием p перевести в десятичную систему и обратно. Пусть N - десятичная дробь. В системе с основанием p ее можно записать в виде: $$N = .c_1 c_2 \dots c_n$$. Реально, эта запись означает:

Соотношение (**) аналогично соотношению (*). Если известны цифры ck и основание системы p, то вычисление N выполняется небольшой модификацией схемы Горнера. Приведу соответствующий код:

def TranslateFractFromPto10(ix:str, p: int)->float:
    """
    Перевод дроби - числа x, представленного строкой в системе счисления с основанием p,
    в число в десятичной системе счисления
    2 <= p <= 30
    """
    if ix == '' :
        return 0
    digits = '0123456789ABCDEFGHIJKLMNOPQRST'
    res = 0 
    n = len(ix)
    f = 1 / p
    for i in range(n - 1):
        sd = ix[n - i - 1] 
        d = digits.index(sd)
        res = (res + d) * f
    return res

Нам осталось рассмотреть функцию перевода дроби из десятичной системы счисления в систему с основанием p. На входе функции задана число N, представляющее дробь, и основание системы p. Требуется определить цифры в разложении дроби по отрицательным степеням системы счисления. Запишем соотношение (**) в виде:

В этом соотношении $$c_1$$ - это старшая цифра, а d - дробь с отрезанной старшей цифрой. Чтобы получить старшую цифру, достаточно N умножить на p и взять целую часть этого произведения, d вычисляется как разность произведения и старшей цифры:

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

Приведу теперь код, работающий в соответствии с этим алгоритмом:

def TranslateFractFrom10toQ(nx: float, q: int)->str:
    """
    Перевод десятичной дроби числа nx в систему счисления с основанием q
    Максимальное число цифр результата равно d_max = 10
    2 <= q <= 30
    """
    if nx == 0 :
        return ''
    digits = '0123456789ABCDEFGHIJKLMNOPQRST'
    res = '';    n = 0; d_max = 10
    while (nx > 0)  (n < d_max):
        nx = nx * q
        d = int(nx)
        nx -= d
        n = n + 1
        res = res + digits[d]
    res = '.' + res
    return res

Обратите внимание, в условии цикла while необходимы скобки для корректного вычисления булевского значения.

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

def test4():
    x = '1A.A1'
    y = TranslateFromPtoQ(x, 16, 2)
    print('x =', x)
    print('y = TranslateFromPtoQ(x, 16, 2) = ', y)
    x = '10.11'
    y = TranslateFromPtoQ(x, 2, 3)
    print('x =', x)
    print('y = TranslateFromPtoQ(x, 2, 3) = ', y)
    x = '55'
    y = TranslateFromPtoQ(x, 20, 10)
    print('x =', x)
    print('y = TranslateFromPtoQ(x, 20, 10) = ', y)
    x = '.55'
    y = TranslateFromPtoQ(x, 20, 10)
    print('x =', x)
    print('y = TranslateFromPtoQ(x, 20, 10) = ', y)
test4()

Результаты работы:

Нетрудно видеть, что функция дает правильные результаты на всех рассмотренных тестах. Это еще не является доказательством корректности. Тестирование может доказать, что программа работает некорректно, если приведен тест, на котором программа ломается. Но если программа корректно работает на n тестах, это не означает, что она будет корректно работать на n+1-ом тесте. Тем не менее на практике тестирование является важным инструментом проверки корректности программы. Важно уметь построить такую систему тестов, чтобы она проверяла как типичные ситуации, так и граничные случаи. В данном примере мы проверяем, что программа корректно работает, когда на вход подается число, имеющее как целую, так и дробную часть при разных значениях p и q. Но также проверяются ситуации, когда на вход подается только целое число без дробной части, или когда на входе дробь без целой части.

Более важно то, что при построении каждой функции мы строили корректный код. Хотя формальное доказательство корректности не проводилось, но обоснованию корректности каждой создаваемой функции уделялось достаточное внимание.

Подведем некоторые итоги. Нам нужно было решить некоторую не совсем простую задачу. Мы понимали, что создаваемый код может повторно использоваться, поэтому решение искали как функцию. Что должна делать функция, что у нее на входе и какой должен быть результат было понятно, так что заголовок функции и заголовочный комментарий был легко написан. Неясно было, как делать, алгоритм решения был не очевиден, по крайней мере, его нельзя было записать в десяток строк кода. Поэтому пришлось применить декомпозицию задачи и выделить более простые задачи. В результате декомпозиции вместо одной функции пришлось написать 8 функций, дающие в совокупности решение задачи. В чем преимущество такого подхода? Каждая из построенных функций - простая функция. Размер кода ограничен - не более 10 -15 строк кода, так что код функции можно полностью видеть на экране компьютера, что облегчает понимание работы функции. В коде не более двух операторов цикла и двух операторов выбора, что облегчает обоснование корректности работы такого кода. Каждая функция решает достаточно простую задачу. Все это способствует достижению главной задачи - построению корректного кода, дающего решение задачи.

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

Еще одно важное замечание. Подход, который мы использовали в этом примере, называется проектированием "сверху вниз" (top dawn). Мы вначале написали код основной функции, в котором вызывались еще не реализованные функции, решающие частный подзадачи. Этот процесс продолжался до тех пор, пока подзадачи не сводились к простым задачам, для которых можно было написать короткий корректный код.

На практике чаще применяется подход проектирования "снизу - вверх" (dawn up). Это связано с тем, что каждая ИТ компания, каждый профессиональный программист имеет в своем багаже богатую библиотеку готовых, корректно работающих модулей. Новое решение строится из уже имеющихся кубиков, примерно так, как создаются конструкции из набора Лего.

Точнее говоря, чаще применяется смешанный подход "навстречу друг другу", когда что-то конструируется из готовых модулей, но какие-то модули приходится строить заново.

Студентам нужно начинать строить свой набор Лего, начиная с первого курса, тогда к выпускной работе удастся построить величественное здание собственного большого проекта.

Встроенные функции

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

Первой из этих функций рассмотрим функцию zip, уже появлявшуюся в главе, где речь шла об итераторах. Функция zip создает итератор - объект, содержащий итерируемую последовательность. На вход этой функции поступает произвольное число итерируемых последовательностей. Функция zip параллельно обходит эти последовательности, создавая из получаемых элементов кортеж. Длина кортежа равна числу входных последовательностей. Обход заканчивается, когда исчерпывается самая короткая последовательность, переданная на вход. Последовательность из создаваемых кортежей составляет результирующую последовательность. Приведем пример работы с функцией zip:

"""
    Пример вызова функции zip
"""
def test15():
    a = [7, 9, 3, -5]
    print("a = ", a)
    b = [6, 2, 12, 7, -8]
    print("b = ", b)
    c = [-2, -6, 88]
    print("c = ", c)

    print ("zip итератор zz(a, b, c):")
    zz = zip(a, b, c)
    for item in zz:
        print( item)
test15()

Вот результаты работы:

Функция map также создает итератор. По сути, это модификация функции zip. На вход функции также подается произвольное число итерируемых последовательностей. К каждому кортежу, создаваемому функцией zip, применяется функция, задаваемая первым аргументом функции map. Полученные значения и составляют результирующую последовательность. Покажем на примере две возможности задания функции, обрабатывающей кортежи. В первом случае для задания функции используется лямбда определение, во-втором, классическое def определение. Обрабатываемые последовательности в обоих случаях те же, что и в предыдущем примере работы с функцией zip:

def Sum (*p ):
    sum =0
    for item in p:
       sum += item
    return sum
"""
Вызовы функции map
"""
def test16():
    a = [7, 9, 3, -5]    
    b = [6, 2, 12, 7, -8]    
    c = [-2, -6, 88]
    mm = map(lambda x, y, z : x + y + z, a, b, c)
    print(итератор mm)
    for item in mm:
        print(item)
    mm1 = map(Sum, a, b, c)
    print(итератор mm1)
    for item in mm1:
        print(item)
test16()

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

Еще одна функция, создающая итератор, - это функция filter. В соответствии с ее названием функция filter фильтрует элементы итерируемой последовательности, передаваемой на ее вход. Фильтром является функция, которая передается в качестве первого аргумента. В этом функция filter схожа с функцией map. Вот пример ее применения:

"""
Функция filter
"""
def test17():
    b = [6, 2, 12, 7, -8] 
    ff = filter(lambda x: x % 2 == 0 ,  b)
    print("filter итератор ff(x % 2 == 0(b)")
    for item in ff:
        print(item)
test17()

В данном случае фильтр отбирает четные элементы последовательности.

Результаты фильтрации:

Функция reduce находится в модуле functools, который предварительно необходимо импортировать. В отличие от трех описанных выше функций эта функция не создает итератор. На вход также поступает итерированная последовательность. Над элементами этой последовательности поочередно выполняется бинарная операция, где первым операндом является результирующая переменная, например, sum, если речь идет о суммировании элементов последовательности, или max, - в случае вычисления максимума. Для результирующей переменной можно задать начальное значение. По умолчанию его значением становится первый элемент последовательности, а итерирование начинается со второго элемента. В общем случае у функции reduce три параметра. Первый - задает бинарную операцию, второй - итерируемую последовательность, третий - начальное значение.

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

"""
Функция reduce
"""
def test18():
    from functools import reduce
    b = [6, 2, 12, 7, -8] 
    sum = reduce(lambda sum, x: sum + x, b, 0)
    print("sum = ", sum)

    mad = reduce(lambda max, x: x if x > max else max, b, b[0])
    print("max = ",mad) 
test18()

Приведу результаты выполнения: