программирование


Эффективное программирование 3D-приложений с помощью Irrlicht и Jython. Часть 6

В прошлый раз мы начали изучение графических средств irrlicht и пока ограничиваемся работой только с 2d-графикой, параллельно изучая на простых примерах особенности языка python|jython. В КГ №7 был начат большой пример игры “угадай число”. Сегодня продолжим ее развивать с помощью пользовательских функций (udf — user defined functions).

Развивающее задание №4. Что такое функция, и как они позволяют нам писать более компактный и управляемый код, я уже говорил ранее. Ранее мы уже использовали стандартные функции python — например, прочитать строку, сгенерировать случайное число. Теперь же надо попробовать создавать собственные функции. Вам нужно будет создать функцию get_random_number, которая будет служить для генерации начального случайного числа, угадываемого пользователем. У этой функции входными параметрами будут числа A, B, задающие диапазон. Кроме того, созданная вами функция не должна возвращать четные числа, а только нечетные. Момент в том, что нельзя при генерации случайного числа сказать, мол, хочу только четные или только нечетные. Но можно возвращенное функцией randint случайное число проверить на четность (как именно, см. похожий пример с определением, високосный сейчас год или нет), и, если число четное, нужно сгенерировать его заново до тех пор, пока не получим нужное нам нечетное случайное число (внимание: здесь нужен цикл внутри функции). Теперь рассмотрим еще примеры UDF-функций:

import sys
import math

def factorial(n):
if n <= 1:
return 1
else:
return n*factorial(n — 1)

def my_pow (x, y):
mult = 1.0
i = 0
while i < y:
mult *= x
i = 1 + i
return mult

def exponenta (x, delta):
sum = 0
i = 0
while 1:
step = my_pow (x, i) / factorial(i)
sum += step
if (step < delta):
break
i = 1 + i
return sum

print exponenta (2, 0.001)

Здесь мы вводим несколько новых понятий. Цель данной программы — расчет значения функции exp(x), или чему равно число e в степени x. Разумеется, в модуле math, который, кстати, мы подключили во второй строке, есть функция, уже умеющая это делать. Например, так:

print exponenta (2, 0.001) — math.pow(math.e, 2)

Здесь я обратился к модулю math и в нем нашел константу e, равную 2.718281828 (кстати, это число легко запомнить, так как в ней после 2.7 дважды идет дата рождения Л.Н. Толстого, но это к слову). А потом я вызвал функцию pow, которая получает два аргумента: первый из них — что будет возведено в некоторую степень, второй — соответственно, значение этой самой степени. Мне все же хочется вычислить значение данной функции с помощью следующей суммы: exp(x) = 1 + x + x^2/2! + x^3/3! + … и так далее. Эта сумма является бесконечной. И очередной ее член под номером I (кстати, отсчет начинается с нуля) определяется как x в степени I разделить на значение функции факториал от I (записывается как i!). Раз сумма бесконечная, то наш цикл, по идее, никогда не должен был бы закончиться — он все считал бы и считал значение exp(x) все точнее и точнее, добавляя все меньшие и меньшие доли в итоговую сумму. Следовательно, через бесконечное время мы бы получили бесконечно идеальный ответ. Правда, во время этого расчета сначала наступил бы следующий ледниковый период, потом потухло бы солнце, и, наконец, вселенная сжалась бы в бесконечно маленькую точку перед следующим большим взрывом. В общем, вы догадались, что работать с бесконечностями нужно крайне аккуратно. В практике расчет ведется до какой-то величины погрешности. Так, если очередной член, добавляемый к сумме меньше, чем, скажем, 0.0001, то и вся последующая сумма также не превысит этой поправки. Следовательно, созданная мною функция exponenta (при объявлении функции вы используете ключевое слово def — от англ. definition — определение) должна получить два параметра: собственно значение x и второе — точность вычислений — delta. Цикл будет прерван, как только эта delta окажется больше, чем очередной член бесконечного суммируемого ряда. Для расчета значения x^n я создал собственную функцию my_pow, которая получает два аргумента (какое число и в какую степень надо его возвести). Возведение в степень я проимитировал через последовательные умножения (такой способ, правда, не будет работать, если нужно возвести число в дробную степень — скажем, 5^(3/4)). Главное — что результат своего расчета функция должна вернуть в тот код, откуда она была вызвана с помощью оператора return.

Когда мы разрабатываем программы, то выделяем составные части — функции, по возможности максимально автономные и слабо связанные между собой. Здесь я упоминаю об одном из правил разработки приложений, заключающемся в стремлении избежать зависимостей одной функции от косвенных результатов деятельности другой. Прямая взаимосвязь — это когда функция вызывает другую функцию и зависит только от того, что эта вызванная функция вернула с помощью оператора return. Косвенные зависимости сложнее в определении. Например, если функция для проведения своих расчетов создает файл “tmp.calc.dat”, то это можно принять за косвенные влияния на другие функции. Может, файл под таким именем используется другой частью программы для хранения настроек или сведений профиля пользователя, а тут мы этот файл портим. Функция factorial гораздо сложнее — в ней вводится понятие рекурсии. Любая подпрограмма (функция) может вызывать другую подпрограмму. Возникает вопрос: а может ли некоторая подпрограмма вызвать саму себя, и что из этого получится? Подобный прием называется рекурсией — практически все языки программирования поддерживают ее. Более того, существует класс задач, которые без использования рекурсии не имеют решения. В качестве простейшего примера рекурсии из жизни: представьте, что перед человеком и за ним поставили зеркало. Если человек посмотрит в переднее зеркало, то увидит в нем себя и, разумеется, зеркало сзади, в котором он увидит отражение снова себя и переднего зеркала, в котором он увидит снова отражение себя и отражение заднего зеркала, в котором … — и так до бесконечности. Часто для демонстрации возможностей рекурсии используют такие математические объекты, как факториал, цепные дроби. В качестве примера далее приводится пример кода рекурсивного и итеративного вычисления факториала.

Как известно из математики, факториал числа N! = 1*2*3 … (N-1)*N. Но ведь если взять произведение всех чисел, кроме последнего, мы получим формулу факториала, правда, уже для числа N-1. Итак: N! = 1*2*3 … (N-1)*N = (N-1)!*N.

Давайте по шагам рассмотрим, как работает рекурсия для функции factorial. Рекурсия всегда выполняется в виде некоторой подпрограммы и состоит из условно двух частей: рекурсивной части и нерекурсивной. Мы попытаемся по шагам пройти рекурсивное решение. Прежде всего, следует ввести понятие уровня рекурсии, нумеруя эти уровни от нуля. 0 — это уровень той функции, которая первый раз вызывает рекурсивный алгоритм. Каждый раз, когда рекурсивная процедура будет вызывать сама себя, мы будем добавлять единичку к текущему уровню.


УровеньОписание и состояние переменных
0Мы еще не вызывали рекурсивную функцию
1Значение N=5, согласно заданному условию, результатом значения 5!=5*4! Следовательно, нам необходимо сделать рекурсивный вызов с N=N-1.
2Значение N=4 — мы еще не дошли до ситуации, когда не требуется применение рекурсии и, следовательно, должны снова вызвать себя уже со значением N=3
3N=3
4N=2
5N=1
6N=0, ну наконец-то, рекурсивный спуск был завершен, и мы знаем значение факториала при N=0, N! = 1. Теперь начинаем подъем.
5При подъеме уровни рекурсии постепенно уменьшаются, пока мы не дойдем до 0, т.е. не вернемся в ту точку, откуда был сделан первый рекурсивный вызов. Мы возвращаемся из функции, и в качестве результата будет значение factorial = N*1. Здесь 1 — это результат, который мы получили с уровня 5. Значение N=1. Следовательно, возвращается из функции значение 1.
4Вычисляем текущее значение factorial = 2*1
3Вычисляем текущее значение factorial = 3*2
2Вычисляем текущее значение factorial = 4*6
1Наконец, мы вернулись к первому вызову рекурсивной функции — таким образом, мы завершаем подъем и как результат получаем factorial = 5 * 24 = 120
0Работа рекурсивной функции завершена: результатом 5!= 120


Когда я в таблице описывал спуск с постепенным нарастанием уровня, то остановился, когда N стало равным нулю. До этого мы определили, что значение 0!=1 по определению (значение факториала для отрицательных значений не определено). Отсюда есть очень важное следствие: рекурсия всегда имеет терминальную или конечную ветвь. Если мы об этом забудем, то получим нечто похожее на бесконечный цикл, который забирал все ресурсы машины и никогда не завершался сам, ведь вы действительно не хотите этого. Когда стоит применять рекурсию? На этот вопрос есть очень простой ответ: по возможности никогда. Вот пример той же функции, но не рекурсивной, а использующей цикл:

def factorial_cicle (_n):
if _n < 0:
print 'N не может быть менее, чем ноль'
os.abort () # вызов функции abort из модуля os аварийно завершает работу всей программы
f = 1
while _n > 1:
f *= _n
_n = _n — 1
return f

Дело в том, что рекурсия всегда является с точки зрения вычислительных ресурсов слишком дорогой и в ряде ситуаций из-за этого просто не работает. В качестве демонстрации попробуйте запустить приведенные выше фрагменты кода для N = 1, 5, 10, 100, 1000, 1000000. В то время как итеративный алгоритм работает и продолжает работать, выдавая все большие и большие числа, рекурсия начиная с какого-то шага завершается аварийно. Примечание: если бы вы запрограммировали этот же цикл на c|c++|Delphi, то начиная с некоторого шага получался бы неверный результат из- за переполнения переменной F. Дело в том, что факториал — очень быстрорастущая функция, и вскоре ее значение превышает предельные 2 млрд для целых чисел в с/с++/delphi. В python, к счастью, проблема переполнения так остро не стоит. Далее рекурсивная же версия применительно к c|c++ с некоторого момента начинает завершаться аварийно с сообщением “stack overflow” (переполнение стека) или о попытке доступа к чужой памяти. Также учитывайте, что время вычисления в рекурсивной версии заметно больше, чем в итеративной. Тогда у вас должен возникнуть вопрос: а зачем нам нужен подобный инструмент? Да потому, что рекурсия гораздо гибче, чем итерация, и я снова вам повторю, что есть такой класс задач, которые не имеют решения без использования рекурсии или их решение слишком неэффективно. Как проектировать рекурсивные алгоритмы? Да, это действительно сложный вопрос. Прежде всего, определитесь с самой задачей — какова ее природа. Если вам необходимо найти, например, максимальный элемент в массиве, то это обычный цикл с перебором всех элементов и отбором среди них. Разумеется, всякий итеративный алгоритм можно переписать с помощью рекурсии, и, кстати, это неплохая тренировка. Так, для демонстрации я далее приведу примеры той же задачи с поиском максимального элемента.

  Рекурсивное решение Итеративное решение
Концепция Что есть максимальный элемент в массиве? Пусть нам будет как будто очень сложно ответить на этот вопрос, и поэтому мы ищем упрощение. Да, тяжело найти максимальный среди N элементов — гораздо проще найти его среди (N-1) элементов, а затем сравнить это значение и первый элемент и определить, кто же на самом деле наибольший.1. Максимальный элемент в массиве из N элементов есть наибольший из первого и максимального элемента в хвосте массива (2..N).2. (Это терминальная ветвь, она должна обязательно присутствовать). Очевидно, что в массиве, состоящем из одного элемента, этот элемент и будет максимальным. Предположим, что MAX — максимальный элемент массива — пусть это будет его первый элемент (или второй — в общем, любой). Переберем все оставшиеся элементы и для каждого из них проверим истинность первого предположения: может быть, мы ошибались, и на самом деле некоторый текущий элемент A[i] более подходит на роль максимального: A[i]> MAX, если данное условие выполняется, то исправим нашу “ошибку”, положив: MAX = A [i]
Реализация def max_rec (A): if (len (A) == 0): 
print 'array is empty' # в массиве нет элементов и понятие максимального элемента не определено 
os.abort () 
if (len (A) == 1): 
return A [0] 
max = max_rec (A [1:]) 
if max < A [0]: 
return A [0] 
else: 
return max 
print 'max rec = ' , max_rec ([1,2,4,6,7,2,5,9,0])print 'max rec = ', 
max_rec ([])
A = [1,2,4,6,7,2,5,9,0];

max = A [0]
i = 1
while i < len (A):
if (max < A [i]):
max = A [i]
i = 1 + i
print 'max = ', max
Замечания Когда мы формулируем рекурсивный алгоритм, то больше внимания уделяем описанию характеристик того, что должно получиться, или как оно выглядит.Рекурсивный алгоритм сводится к самому себе, но всегда чуть более простому и близкому к моменту, когда для решения поставленной задачи рекурсия будет не нужна, решение будет тривиально и достижимо с помощью итерации или иного нерекурсивного приема (терминальная ветвь). Здесь основной упор на определение четкой последовательности действий. Пройдя их от начала до конца, мы достигнем поставленной цели.



Запись A [1:] означает, что из массива мы берем все элементы начиная с первого (нулевой элемент не берется) и подаем на вход рекурсивной функции max_rec. Рекурсия опасна тем, что вы можете забыть или неправильно сформулировать терминальное условие. Тогда рекурсивная функция будет вызывать сама себя, мгновенно пожирая ресурсы памяти и процессора. В общем случае можно ограничить глубину рекурсии некоторым числом. Разработчики python поступили очень грамотно, когда этот предел взаимных вызовов определили в виде настраиваемого числа. Итак, есть две функции в модуле sys: getrecursionlimit() — эта функция возвращает число максимальной глубины рекурсии;
setcheckinterval() — а эта функция устанавливает значение этого лимита.

Для иллюстрации схемы работы этих двух функций:
import sys
import os

def factorial_recursion(n):
if n <= 1:
return 1
else:
return n*factorial_recursion(n — 1)

print 'Лимит рекурсии сейчас' , sys.getrecursionlimit ()
print '5! = ', factorial_recursion (5)
sys.setrecursionlimit (4) # теперь мы устанавливаем предел вызовов в 4
print '5! = ', factorial_recursion (5)

А вот результат работы примера кода выше:
Лимит рекурсии сейчас 1000
5! = 120
5! =
Traceback (most recent call last):
File "f:\kolya\py\src\a10.py", line 27, in ?
print '5! = ', factorial_recursion (5)
File " f:\kolya\py\src\a10.py", line 20, in factorial_recursion
return n*factorial_recursion(n — 1)
File " f:\kolya\py\src\a10.py", line 20, in factorial_recursion
return n*factorial_recursion(n — 1)
File " f:\kolya\py\src\a10.py", line 20, in factorial_recursion
return n*factorial_recursion(n — 1)
RuntimeError: maximum recursion depth exceeded

Для тренировки навыков работы в 2d попробуем нарисовать какую-нибудь замечательную кривую. Вот пример программы, рисующей дерево Пифагора. В основе самоповторяющегося дерева лежат “те самые штаны, которые…” Почему я сказал “самоповторяющегося дерева”? Построение дерева Пифагора начинается с квадрата, у которого на одной из сторон размещен равнобедренный прямоугольный треугольник. Катеты этих треугольников равны и являются сторонами новых квадратов. И так фигура разрастается. Если же рисовать вместо квадратов линии, можно получать картинки, очень похожие на настоящие деревья. Что и делается в примере ниже.

import java
import math

import net.sf.jirr
from net.sf.jirr import dimension2di
from net.sf.jirr import position2di
from net.sf.jirr import recti
from net.sf.jirr import SColor

def lineto (x, y, len, u, _driver):
_driver.draw2DLine (position2di (x,y), position2di (int(x +len*math.cos(u) ), int(y — len*math.sin(u) )),
SColor (255, 0 , 0 , 0)
)

def pifagor (x, y, len, u, _driver):
if (len > 3):
len = 0.7 * len
lineto (x, y, len, u, _driver)
x = int (x + len*math.cos (u))
y = int (y — len*math.sin (u))
pifagor(x, y, len, u — math.pi/4, _driver)
pifagor(x, y, len, u + math.pi/6, _driver)

java.lang.System.loadLibrary ('irrlicht_wrap')
device = net.sf.jirr.Jirr.createDevice(
net.sf.jirr.E_DRIVER_TYPE.EDT_DIRECT3D9, dimension2di(640, 480), 32
)
device.setWindowCaption("1.2 дерево Пифагора");
driver = device.getVideoDriver()

while device.run():
driver.beginScene(1, 1, SColor(255,255,255,255)) # вначале все поле закрашивается черным цветом
pifagor(320, 460, 200, math.pi/2, driver);
driver.endScene()
device.drop

Разумеется, это не единственная самоподобная фигура. В Интернете можно найти примеры изображений/формул/текста программ — например, на сайт

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



black zorro, black-zorro@tut.by

© компьютерная газета