WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 ||

«Чаплыгин А. Н. ...»

-- [ Страница 2 ] --

>>> fact(3) Работает! Осталось только проверить, как функция поведет себя при некорректных значениях параметра (отрицательных или дробных, например), так что не забудьте выполнить упражнение.

Упражнение. Проверьте, как функция fact() будет вести себя с отрицательными и дробными значениями параметра. Объясните, какие проблемы возникли и почему.

Модифицируйте функцию так, чтобы избежать их11.

§5.10. Стековые диаграммы рекурсивных вызовов Разберемся, какой путь проделывает поток выполнения в процессе вычисления факториала. Изобразим стековую диаграмму для вызова fact(3).

11 Имейте ввиду, что функция может не справиться со слишком большими значениями (например, при n > 1000). Это связано с ограничениями, присущими вычислительной технике. Этот случай мы разберем в последующих разделах.

Ревизия: 170 Логические выражения, условия и рекурсия fact(0) fact(1-1)*1 return fact(1) fact(2-1)* return 1 * fact(2) fact(3-1)*3 return 1*1 * fact(3) return 1*1*2 * main Итак, теперь все должно быть понятно. До добавления условия возврата 1 при x == стек вызовов рос бесконечно, поэтому возникало исключение. Когда же мы добавили это условие, все встало на свои места: сначала стек рекурсивных вызовов увеличивается, пока не дойдет до граничного значения параметра, а затем начинает опустошаться – поток выполнения начинает возврат обратно в главную программу, собирая ответ по кусочкам (кстати, термин «рекурсия» происходит от позднелатинского «recursio» – «возвращение»).

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

Можно ли улучшить этот алгоритм? Вы, наверное, обратили внимание, что на втором шаге возврата мы умножаем 1 на 1 – бессмысленная операция. Кроме того, каждый рекурсивный вызов требует выделения некоторого количества памяти, да и сам вызов занимает какое-то время.

Вариант решения: изменить условие, при котором будет начинаться возврат на x == 1.

Проверим его с помощью граничных значений: что произойдет при вызове fact(0)?

Программа зациклится. Попробуем так:

def fact(n):

if type(n) != type(1) or n < 0: # Проверка корректности n return None if n == 1 or n == 0:

return return fact(n-1)*n Такой подход позволит избежать лишний рекурсивный вызов, но увеличивается сложность проверяемого условия, что сказываете на скорости выполнения программы.

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

Упражнение. Как вы думаете, стоит ли в случае функции fact() производить лишнюю проверку? Объясните почему.

Ревизия: 170 Логические выражения, условия и рекурсия §5.11. Максимальная глубина рекурсии Мы уже сталкивались с бесконечной рекурсией, когда рекурсивная функция по тем или иным причинам не достигала условия возврата (в англоязычной литературе base case – «базовый случай»). Но в большинстве программных сред такие программы, конечно же, бесконечно выполняться не будут в силу конечного размера памяти компьютера. В Питоне для предотвращения нарушений работы компьютера, на котором выполняется программа, тоже имеется специальное ограничение – maximum recursion depth (максимальная глубина рекурсии).

Максимальную глубину рекурсии можно изменять, т.к. некоторые задачи требуют большего максимального размера стека вызовов. Для этого в модуле sys имеется две функции: sys.getrecursionlimit(), возвращающая текущую максимальную глубину рекурсии и sys.setrecursionlimit(), изменяющая ее значение.

>>> import sys >>> sys.getrecursionlimit() >>> sys.setrecursionlimit(5) >>> sys.getrecursionlimit() >>> По умолчанию, максимальная глубина рекурсии равна 1000.

Упражнение. Напишите простую функцию, вызывающую саму себя, и поэксперименти руйте с изменением максимальной глубины рекурсии. Прокомментируйте свои результаты.

§5.12. Числа Фибоначчи Леонардо Фибоначчи (Леонардо Пизанский) – крупный средневековый итальянский математик (1170-1240), автор «Книги об абаке» (1202), которая несколько веков оставалась основным сборником сведений об арифметике и алгебре. Сегодня имя Фибоначчи чаще всего упоминается в связи с числовой последовательностью, которую он обнаружил, изучая закономерности живой природы.

Ряд этих чисел образуется следующими значениями 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 и так далее – каждое последующее число ряда получается сложением двух предыдущих.

Особенностью ряда чисел Фибоначчи является то, что по мере роста номера числа в последовательности, отношение предшествующего члена к последующему приближается к значению – 0.618 (древние греки называли это число «золотым сечением»), а последующего к предыдущему – к 1.618. «Золотым» это соотношение называют из-за того, что на нем же основан принцип музыкальной, цветовой и геометрической гармонии.

[NOTE: Про числа Фибоначчи можно много интересного написать, но я оставил это на потом.] Давайте напишем функцию, рассчитывающую n-й элемент ряда Фибоначчи. Итак, мы f = f =1, f = f f, n имеем обобщенную формулу:. Можем ли мы применить 1 2 n n-1 n- здесь рекурсию?

Ревизия: 170 Логические выражения, условия и рекурсия Каждое число Фибоначчи представляет собой сумму двух предыдущих чисел Фибоначчи, которые расчитываются по той же формуле, все числа Фибоначчи целые и положительные, кроме того, мы имеем граничное значение. Так что применить рекурсию в данном случае вполне можно.

>>> def fibonacci(n):

... if n == 1 or n == 2:

... return... return fibonacci(n-1) + fibonacci(n-2)...

>>> fibonacci(5) Замечательно. Теперь осталось добавить проверку типа и положительности параметра функции и готово.

def fibonacci(n):

if type(n) != type(1) or n < 0: # Проверка корректности n return None if n == 1 or n == 2:

return return fibonacci(n-1) + fibonacci(n-2) n Упражнение. Создайте рекурсивную функцию, возвращающую сумму i3 =13...n3.

i= Ревизия: 170 Циклы Глава 6. Циклы §6.1. Оператор цикла while В предыдущей главе мы столкнулись с необходимостью повторения некоторых блоков кода в процессе выполнения вычислений. В некотором смысле, мы справились с этой проблемой, использовав рекурсию, но ее использование далеко не всегда оправдано. Во первых, разобраться, как работает рекурсивная функция не так-то просто, а это означает, что расширение функциональности программы будет затруднено, особенно если над ней будет работать не один программист, а целая команда. Во-вторых, рекурсивные функции очень «прожорливы» – для их выполнения требуется много оперативной памяти, да ограничение максимального размера стека вызовов тоже создает некоторые трудности.

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

Каждый циклический оператор имеет тело цикла – некий блок кода, который интерпретатор будет повторять пока условие повторения цикла будет оставаться истинным.

В языке Питон оператор цикла выглядит так:

while УСЛОВИЕ_ПОВТОРЕНИЯ_ЦИКЛА:

ТЕЛО_ЦИКЛА Очень похоже на оператор условия – только здесь используется другое ключевое слово:

while (англ. «пока»). Где его можно использовать? Первое, что приходит в голову: повтор ввода данных пользователем, пока не будет получено корректное значение:

correct_choice = False while not correct_choice:

choice = raw_input("Enter your choice, please (1 or 2):") if choice == "1" or choice == "2":

correct_choice = True else:

print "Invalid choice! Try again, please."

print "Thank you."

Перед началом цикла мы определили логическую переменную correct_choice, присвоив ей значение False. Затем оператор цикла проверяет условие not correct_choice: отрицание False – истина. Поэтому начинается выполнение тела цикла: выводится приглашение "Enter your choice, please (1 or 2):" и ожидается ввод пользователя. После нажатия клавиши [Enter] введенное значение сравнивается со строками "1" и "2", и если оно равно одной из них, то переменной correct_choice присваивается значение True. В противном случае программа выводит сообщение "Invalid choice! Try again, please.". Затем оператор цикла снова проверяет условие и если оно по-прежнему истинно, то тело цикла повторяется снова, иначе поток выполнения переходит к следующему оператору, и интерпретатор выводит строку "Thank you.". Как видите, все довольно просто.

Ревизия: 170 Циклы Упражнение. Наберите программу в файле и поэкспериментируйте с ней: попробуйте вводить различные строки и цифры. Правильно ли работает программа?

§6.2. Счетчики Еще один вариант использования оператора цикла – вычисление формул с изменяющимся параметром. В одном из упражнений предыдущей главы было задание с n помощью рекурсивной функции вычислить формулу i3 =13...n3 при заданном n. В i= данном случае изменяющимся параметром является i, причем i последовательно принимает значения в диапазоне от 1 до n.

С помощью оператора цикла while решение будет выглядеть так:

n = input("Input n, please:") sum = i = while i <= n:

sum = sum + i**3 #Тоже самое можно записать короче: sum += i** i = i + 1 #Аналогично: i += print "sum = ", sum Разберемся, как работает эта программа. Сначала пользователь вводит n – граничное значение i. Затем производится инициализация переменных sum (в ней будет храниться результат, начальное значение – 0) и счетчика i (по условию, начальное значение – 1). Далее начинается цикл, который выполняется, пока i <= n. В теле цикла в переменную sum записывается сумма значения из этой переменной, полученная на предыдущем шаге, и значение i, возведенное в куб;

счетчику i присваивается следующее значение. После завершения цикла выводится значение sum после выполнения последнего шага.

Следующее значение счетчика получают прибавлением к его текущему значению шага цикла (в данном случае шаг цикла равен 1). Шаг цикла при необходимости может быть отрицательным, и даже дробным. Кроме того, шаг цикла может изменяться на каждой итерации (т.е. при каждом повторении тела цикла).

Теперь давайте попробуем оптимизировать нашу программу. Итак на каждой итерации в теле цикла мы вычисляем следующее значение счетчика. Но на последнем шаге мы вычислем его лишний раз – его новое значение уже использоваться не будет. Конечно, эта операция не требует каких-то особых ресурсов, но привычку обращать внимание на подобные вещи следует вырабатывать, т.к. впоследствии вы, наверняка, будете иметь дело с более сложными операциями. Как избежать выполнения лишнего вычисления? Что если вычислять значение i до вычисления формулы? Давайте попробуем.

n = input("Input n, please:") sum = i = while i <= n:

Ревизия: 170 Циклы i += sum += i** print "sum = ", sum Обратите внимание, на запись вида sum = i = 0. Она работает аналогично простому присваиванию значения переменной, но в данном случае обе переменные получают одинаковое начальное значение.

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

Нет, не изменилось, но выглядит, пожалуй, немного изящнее: после завершения цикла i = n. Это может помочь избежать путаницы, если i будет использоваться далее в программе.

Упражнение. Напишите программу, которая с помощью оператора цикла while выводит все четные числа от 0 до заданного пользователем n.

§6.3. Бесконечные циклы Изучая рекурсивные функции, мы столкнулись с проблемой бесконечного повторения блока кода (бесконечной рекурсией), которое возникает, если условие возврата не достижимо, например, из-за семантической ошибки в программе. Циклы тоже могут выполняться бесконечно и тоже, чаще всего, из-за семантических ошибок. Простейший пример:

i = while i < 10:

print i Этот цикл будет выполняться бесконечно, т.к. условие i < 10 всегда будет истинным, ведь значение переменной i не изменяется: такая программа будет выводить бесконечную последовательность нулей. В отличие от рекурсивных функций, у циклов нет ограничения количества повторений тела цикла, поэтому программа с бесконечным циклом будет работать непрерывно, пока мы не произведем аварийный останов нажатием комбинации клавиш [Ctrl+C], не уничтожим соответствующий процесс средствами операционной системы, не будут исчерпаны доступные ресурсы компьютера (например, может быть достигнуто максимальное допустимое количество открытых файлов), или не возникнет исключение. В таких ситуациях программисты говорят, что программа зациклилась.

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

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

Ревизия: 170 Циклы Циклы – это очень мощное средство реализации ваших идей, но они требуют некоторой внимательности.

§6.4. Альтернативная ветка цикла while Язык Питон имеет много интересных и полезных особенностей, одной из которых является расширенный вариант оператора цикла:

while УСЛОВИЕ_ПОВТОРЕНИЯ_ЦИКЛА:

ТЕЛО_ЦИКЛА else:

АЛЬТЕРНАТИВНАЯ_ВЕТКА_ЦИКЛА Пока выполняется условие повторения тела цикла, оператор while работает так же, как и в обычном варианте, но как только условие повторения перестает выполняться, поток выполнения направляется по альтернативной ветке else – так же, как в условном операторе if, оно выполнится всего один раз.

>>> i = >>> while i < 3:

print i i += else:

print "end of loop" end of loop >>> Надо сказать, что другие языки программирования легко обходятся без альтернативных веток в операторах цикла – это приятная, но необязательная возможность.

Упражнение. Выясните, как поведет себя оператор, если условие повторения цикла будет ложным.

§6.5. Табулирование функций С помощью оператора цикла while удобно строить таблицы значений различных функций. Большинство учебников по высшей математике имеют приложения с такими таблицами значений. До того, как появились компьютеры, математикам приходилось составлять таблицы значений тригонометрических, логарифмических и других функций вручную – это очень трудоемкий и утомительный процесс, что, в свою очередь, увеличивает вероятность возникновения ошибки в расчетах12.

12 Конечно, таблицам, имеющимся в учебниках, доверять можно, т.к. они перепроверялись множество раз.

Ревизия: 170 Циклы По сути такие таблицы представляют собой список значений функции при различных значениях ее параметра. Поэтому, когда науке стали доступны вычислительные машины, первой реакцией было желание автоматизировать табулирование функций (т.е. процесс построения таблиц значений функции). Логично для этих целей использовать циклы.

Рассмотрим такую программу:

import math x = 1. while x < 10.0:

print x, "\t", math.log(x) x += 1. Результат ее работы будет выглядеть так:

1.0 0. 2.0 0. 3.0 1. 4.0 1. 5.0 1. 6.0 1. 7.0 1. 8.0 2. 9.0 2. Строка "\t" обозначает знак табуляции. Благодаря нему значения выстраиваются в два столбца.

Разберем, как эта программа работает. Параметр x изменяется от 1.0 с шагом 1.0, пока он меньше 10.0. В теле цикла выводится текущее значение параметра x, затем знак табуляции и результат вычисления функции math.log(x), т.е. натуральный логарифм от x ( loge x=ln x ). При необходимости вычисления логарифма по основанию 2 мы можем воспользоваться формулой:

ln x log2 x= ln Наша программа будет выглядеть так:

import math x = 1. while x < 10.0:

print x, "\t", math.log(x)/math.log(2) x += 1. Результат будет таким:

1.0 0. 2.0 1. Ревизия: 170 Циклы 3.0 1. 4.0 2. 5.0 2. 6.0 2. 7.0 2. 8.0 3. 9.0 3. Как видите, 1, 2, 4 и 8 являются степенями 2. Модифицируем нашу программу, чтобы найти другие степени 2:

import math x = 1. while x < 100.0:

print x, "\t", math.log(x)/math.log(2) x *= 2. Таким образом, мы получили:

1.0 0. 2.0 1. 4.0 2. 8.0 3. 16.0 4. 32.0 5. 64.0 6. Благодаря символу табуляции позиция второй колонки не зависит от ширины первой – это хорошо видно на последних трех значениях.

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

Упражнение. Измените программу так, чтобы программа вывела все степени 2 до 10-й включительно. Постарайтесь запомнить результаты. Почему в килобайте не байт, а 1024?

§6.6. Специальные и экранируемые символы В этом разделе мы немного отвлечемся от циклов, чтобы внести ясность в вопрос специальных текстовых последовательностей, с одной из которых мы уже столкнулись в предыдущем разделе: "\t". Дело в том, что в кодовых таблицах (наборах цифровых кодов, обозначающих различные символы, которые компьютер может выводить на экран) есть целая группа так называемых непечатаемых символов. Непечатаемые символы используются для управления вводом/выводом. Самые часто используемые из них: знак табуляции, Ревизия: 170 Циклы перенос на новую строку и знак «возврата каретки». Т.к. в кодовой таблице нет символов, отображаемых на экране, для их обозначения придумали специальные последовательности:

Последовательность Назначение \t Табуляция \n Перевод на новую строку \r Возврат «каретки» (курсора) в начало строки Таким образом, если в программе нужно вывести текст из нескольких строк, то на помощь приходят специальные последовательности:

>>> print "hello\rH\n\tworld" Hello world Разберем, что происходит при выводе строки "hello\rH\n\tworld". Сначала выводится строка "hello" – только после нее интерпретатор встречает первую специальную последовательность: "\r" – символ возврата «каретки» на начало строки. Затем Выводится символ "H", но происходит это на позиции первого символа! При этом уже имеющийся на этой позиции символ заменяется новым14. После этого последовательности "\n" и "\t" дают указание произвести перевод на новую строку и оставить отступ в одну табуляцию.

Далее выводится оставшаяся часть строки "world".

Разумеется, не стоит применять специальные последовательности там, где это не обязательно: например, проще было исправить первый символ строки вместо добавления "\rH". Иначе вашу программу будет сложнее читать.

13 Термин «каретка» возник с появлением механических пишущих машинок, которые были устроены так, что после перехода на новую строку нужно было возвращать специальную подвижную часть механизма в положение, соответствующее началу строки. Эта подвижная часть и называлась «кареткой». В процессе печати «каретка» перемещалась справа налево вместе с листом бумаги, «подставляя» место для следующего символа под рычажки с оттисками символов, приводимые в в движение клавишами машинки.

14 Кстати, опытные секретарши, работавшие с пишущими машинками, так исправляли опечатки в документах:

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

Ревизия: 170 Циклы Упражнение. Напишите выражение на языке Питон, которое будет выводить строку такого вида:

I can use tabs and new lines in program output.

Теперь рассмотрим такую ситуацию: предположим, что нам необходимо вывести, например, такую строку "Main \template/".

>>> print "Main \template/" Main emplate/ Интерпретатор распознал последовательность "\t" и вставил специальный символ, а это не то, чего мы хотели добиться.

В подобных ситуациях перед специальным символом "\" ставится так называемый экранирующий символ: еще одна косая черта "\".

>>> print "Main \\template/" Main \template/ Теперь все в порядке. А как вывести кавычки?

>>> print "I said: "Hello world"" File "", line print "I said: "Hello world"" ^ SyntaxError: invalid syntax Интерпретатор воспринимает вторую кавычку, как завершение строкового значения, но следующее за ней продолжение строки некорректно с точки зрения синтаксиса Питона.

Попробуем экранировать кавычки:

>>> print "I said: \"Hello world\"" I said: "Hello world" Еще один вариант решения проблемы – использование одинарных кавычек:

>>> print 'I said: "Hello world"' I said: "Hello world" Главное, чтобы каждая неэкранированная кавычка имела пару и при этом не нарушалась синтаксическая структура выражения. Поэтому, работая с кавычками, будьте внимательны.

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

Зачем? Ну, например, если выражение слишком длинное, и для удобства чтения программы вы хотите разбить его на несколько строк. Вот пример из реальной программы:

Ревизия: 170 Циклы print "Значение переменной n должно быть целым положительным" \ + " числом,\nпопробуйте еще раз."

В конце первой строки стоит символ "\" (обратите внимание: он находится за пределами строкового значения), который экранирует символ переноса строки. Таким образом разделитель выражений Питона игнорируется интерпретатором, и выражение благополучно продолжается на следующей строке.

§6.7. Числа Фибоначчи и оператор цикла while Мир так устроен, что всегда существует множество путей достижения одной и той же цели, всегда есть выбор. В программировании это свойство тоже нашло свое отражение.

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

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

Но теперь мы знаем о циклах и разберем еще один способ решения задачи нахождения f = f =1, f = f f, n чисел Фибоначчи. Итак, мы имеем следующую формулу:.

1 2 n n-1 n- В ней используется три переменные. Обозначим их так: fn – результирующее значение функции, fn1 и fn2 – промежуточные значения функции используемые в формуле. Знак минуса мы не можем использовать в названиях переменных, помните? Определившись с обозначениями перейдем к анализу задачи.

На первых двух шагах значение функции равно 1. Для расчета последующих чисел из ряда Фибоначчи применим оператор цикла while. На каждом шаге цикла будем вычислять значение fn = fn1 + fn2, а затем изменять значения в переменных fn1 и fn2, подготавливая их для следующего шага цикла: на следующей итерации fn2 будет равняться fn1, а fn1 – fn. Разумеется, для контроля количества итераций цикла мы будем использовать переменную-счетчик i. Вот, что у нас должно получиться:

def fibonacciWithWhileLoop(n):

"""Функция вычисления чисел Фибоначчи с использованием оператора цикла while.""" fn = fn1 = fn2 = i = while i <= n:

fn = fn1 + fn fn2 = fn fn1 = fn i += return fn Ревизия: 170 Циклы Упражнение. Проанализируйте процесс выполнения данной функции. Правильно ли она работает? Изменяется ли размер стека вызовов при работе данной функции?

Что произойдет, если функции fibonacciWithWhileLoop() передать в качестве параметра число 2.4? Доработайте программу так, чтобы этот случай корректно обрабатывался.

Выполнили задание? Если лень заниматься этим сейчас, то лучше отложить книгу и пойти прогуляться. В лени и усталости нет ничего плохого – это вполне естественно для человека, и глупо это отрицать. Но «халтурить» не стоит. Как говорится, тяжело в учении, легко в бою.

Если с заданием справились, идем дальше.

§6.8. Вложенные операторы цикла и двумерные таблицы Как вы уже, наверное, догадались, подобно логическим операторам, циклы могут быть вложены друг в друга. При этом циклы могут использовать различные переменные-счетчики.

Простейшее применение вложенных операторов цикла – построение двумерных таблиц, например:

i = while i <= 10:

j = while j <= 10:

print i * j, "\t", j += print i += Разберемся с тем, как работает эта программа. Цикл, проверяющий условие i <= 10, отвечает за повторение строк таблицы. В его теле выполняется второй цикл, который выводит произведение i и j десять раз подряд, разделяя знаками табуляции полученные результаты. При этом запятая, завершающая выражение, запрещает интерпретатору переводит курсор на новую строку. Также обратите внимание на команду print без параметра, следующую после внутреннего цикла. Она производит перевод на новую строку.

В результат выполнения данной программы мы получим следующую таблицу:

1 2 3 4 5 6 7 8 9 2 4 6 8 10 12 14 16 18 3 6 9 12 15 18 21 24 27 4 8 12 16 20 24 28 32 36 5 10 15 20 25 30 35 40 45 6 12 18 24 30 36 42 48 54 7 14 21 28 35 42 49 56 63 8 16 24 32 40 48 56 64 72 9 18 27 36 45 54 63 72 81 10 20 30 40 50 60 70 80 90 Ревизия: 170 Циклы Первый столбец и первая строка содержат числа от 1 до 10. На пересечении i-той строки и j-того столбца находится произведение i и j. Мы получили таблицу умножения.

Если мы добавим еще один цикл, то получим трехмерную таблицу произведений трех чисел. Выводить на экран ее, правда, будет неудобно – «послойно» разве что. Таким образом вложенные циклы позволяют строить таблицы любой размерности, что очень часто применяется в сложных научных расчетах. И в трехмерной графике, кстати, тоже.

§6.9. Классификация операторов цикла В различных языках программирования существует четыре типа циклов. Мы рассмотрели один из них на примере оператора while. Такие циклы называются циклами с предусловием. Их характерная черта заключается в том, что Условие повторения цикла проверяется до выполнения его тела.

Второй тип циклов – циклы с постусловием. Их отличие состоит в том, что они имеют условие выхода из цикла, которое проверяется после выполнения тела цикла. Т.е. в таких циклах обязательно выполняется хотя бы одна итерация. Например, в языке Pascal цикл с постусловием выглядит так:

do {Цикл с постусловием в языке Pascal} ТЕЛО_ЦИКЛА until УСЛОВИЕ_ВЫХОДА;

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

Еще один тип циклов – арифметические циклы. Такие циклы специально предназначены для работы с переменными-счетчиками. Например, в Pascal'е арифметический цикл выглядит так:

for i:=0 to15 9 do {Арифметический цикл в языке Pascal} ТЕЛО_ЦИКЛА;

В C арифметический цикл немного сложнее – в его заголовке можно отдельно указывать начальное значение счетчика (причем, их может быть несколько), условие повторения цикла и операции, которые должны выполняться в конце каждой итерации (например, приращение счетчика):

for (i = 9;

i <= 9;

i += 1) { // Арифметический цикл в языке С ТЕЛО_ЦИКЛА;

} Арифметического цикла в Питоне тоже нет, но он имеет средство, которое прекрасно его заменяет: цикл перебора элементов множества. Такие циклы базируются на концепции итераторов, о которой мы еще поговорим немного позже. Такой цикл в Питоне выглядит так:

for i in range(0,10):

ТЕЛО_ЦИКЛА Немного позже мы к нему еще вернемся и узнаем на что он способен – по гибкости он превосходит обычные арифметические циклы.

15Для обратного отсчета может использоваться ключевое слово downto.

Ревизия: 170 Циклы §6.10. Управляющие структуры Настало время оглянуться назад. В первой главе речь шла о том, что высокоуровневые программы строятся на нескольких видах конструкций. Давайте вспомним их и сопоставим каждую из них со знаниями приобретенными в пройденных главах. Итак, в высокоуровневые программы строятся на основе следующих типов операций:

• Ввод данных (пока мы умеем вводить данные только с клавиатуры с помощью функций input и raw_input);

• Вывод данных (данные мы выводили на экран;

вывод производится с помощью команды print);

• Выполнение некоторых операций над числами, строками или другими объектами (большинство выражений, в том числе, с использованием функций относятся как раз к этим операциям);

• Выбор ветви выполнения программы на основе принятого решения (условный оператор if);

• Повторение группы операций чаще всего с изменением одного или нескольких параметров (операторы цикла while и for).

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

• Любой часто повторяемой последовательности операций мы можем назначить имя и по нему вызывать ее на выполнение;

• Использование функций упрощает понимание программы и процесс ее отладки: мы можем отладить каждую функцию по отдельности с предельными значениями параметров, а затем собрать их в единую систему, устойчивую к ошибкам при вводе данных пользователем и другим непредвиденным ситуациям;

• Функции позволяют избежать дублирование кода, поэтому изменение хорошо спроектированной программы требует не так много усилий;

• Хорошо продуманные функции могут использоваться в других проектах, что повышает нашу производительность и позволяет в полной мере насладиться процессом решения текущей задачи;

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

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

Ревизия: 170 Строки Глава 7. Строки Разобравшись с основами управления потоком выполнения программ, перейдем к более подробному изучению типов данных, ведь для более эффективного управления данными полезно понимать, как они устроены. Начнем с одного из уже знакомых нам по предыдущим главам типов – строк (str).

§7.1. Оператор индексирования Во второй главе мы уже научились выполнять некоторые операции над строками, но до этого момента мы работали со строками как с единым целым. Известные нам операции над строками (конкатенация и итерация) являются, по сути аналогами сложения и умножения чисел, но этот набор неполон – не хватает аналогов операций вычитания и деления.

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

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

Простейший из них – оператор индексирования. Данный оператор позволяет получить любой одиночный символ из строки. У него довольно простой синтаксис:

СТРОКА[ИНДЕКС] Индекс, указываемый в квадратных скобках, представляет собой порядковый номер символа в строке:

>>> 'Hello!'[1] 'e' Хм, это не то, что мы ожидали увидеть – интерпретатор почему-то вернул не первый, а второй символ строки. Объясняется эта семантическая ошибка очень просто. Дело в том, что компьютер начинает считать не с единицы, как привыкли мы с вами, а с нуля. Проверим:

>>> 'Hello!'[0] 'H' Работает! Идем дальше.

§7.2. Длина строки и отрицательные индексы Для удобной работы с оператором индексирования хорошо бы было знать длину строки. Впрочем, выяснить это довольно просто. Смотрите:

>>> len('Hello world!') >>> Обратите внимание, что пробел тоже считается. Теперь давайте попробуем вывести последний символ строки:

Ревизия: 170 Строки >>> a = 'Hello!' >>> a[len(a)] Traceback (most recent call last):

File "", line 1, in -toplevel a[len(a)] IndexError: string index out of range >>> Т.к. нумерация символов в строках начинается с нуля, мы использовали недопустимое значение индекса – символа с таким индексом в этой строке нет, поэтому интерпретатор сгенерировал исключение IndexError: string index out of range. Исправим ошибку:

>>> a = 'Hello!' >>> a[len(a)-1] '!' Использование функции len() в операторе индексирования выглядит громоздко, поэтому в Питоне предусмотрен более короткий вариант записи:

>>> a[-1] '!' Еще один маленький эксперимент. Попробуем подставить в качестве индекса другое отрицательное число:

>>> a[-5] 'e' Таким образом, мы можем индексировать строку с обоих ее концов – это очень удобно.

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

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

§7.3. Перебор и цикл for Научившись обращаться с индексами, поэкспериментируем с циклами. Иногда возникает потребность перебора символов строки и выполнение операции над каждым из них. Для этого как раз и применяются циклы.

string = "hello" index = while index < len(string):

letter = string[index] print letter index = index + Ревизия: 170 Строки Данная программа перебирает все символы строки и выводит каждый из них на новой строке. При этом, благодаря строгому неравенству в условии index < len(string), повтор тела цикла завершается на символе с индексом len(string) - 1, который является последним в строке.

Упражнение. Напишите функцию, которая получает в качестве параметра строку и выводит символы, ее составляющие, в обратном порядке.

Выполняя упражнение, вы, вероятно, заметили, что в циклах с индексами нетрудно запутаться. Поэтому в Питоне есть более удобный способ перебора элементов строк (и не только): цикл for. Наша программа будет выглядеть так:

for letter in string:

print letter Данный цикл не завершается до тех пор, пока каждый элемент строки string не будет поочередно присвоен переменной letter, начиная с первого. Такой подход избавляет программиста от необходимости думать над условием завершения цикла, что позволяет ему сосредоточиться на решаемой задаче.

§7.4. Срезы строк В языках Си и Паскаль индексы позволяют получать доступ к одиночным символам строки, но в Питоне все гораздо интереснее: можно обращаться не только к одиночным символам, но и к целым подстрокам – срезам (по-английски, slices). Смотрите:

>>> s = "Peter, Paul, and Mary" >>> print s[0:5] Peter >>> print s[7:11] Paul >>> print s[17:21] Mary В общем виде: string[n:m],где n указывает индекс начала среза, а m – индекс конца среза. При этом начальный и конечный индексы разделяются двоеточием. Обратите также внимание, что символ с индексом m в срез не включается.

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

>>> print s[:5] Peter >>> print s[17:] Mary Это заметно упрощает читабельность программы, т.к. отпадает необходимость в коде, вычисляющем длину строки, который не относится к сути реализуемого программой алгоритма.

Ревизия: 170 Строки Упражнение. Чему будет соответствовать срез строки s[:]?

Еще одна интересная возможность, которая появилась в интерпретаторе Питона, начиная с версии 2.3. Теперь для оператора индексирования можно указать еще и шаг выбора элементов в срез:

>>> print s[::2] Ptr al n ay Что у нас получилось? Срез состоящий из элементов с четными индексами (если учитывать, что нумерация начинается с нуля)!

Упражнение. Создайте строку длиной 10-15 символов, и извлеките из нее следующие срезы:

1. Все символы кроме последних четырех;

2. Символы с индексами кратными трем;

3. Все символы строки с четными индексами за исключением первых четырех и последних пяти.

Придумайте 2-3 собственных примера.

§7.5. Сравнение строк Операторы сравнения работают и со строками. Когда возникает необходимость проверить равны ли две строки, можно выполнить следущее:

if word == "banana":

print "Yes, we have no bananas!" Другая операция сравнения полезна для упорядочивания слов в алфавитном порядке:

if word < "banana":

print "Your word," + word + ", comes before banana."

elif word > "banana":

print "Your word," + word + ", comes after banana."

else:

print "Yes, we have no bananas!" Но следует заметить, что Питон работает со строчными и заглавными символами несколько необычно для нас людей. Заглавная буква считается большей, чем любая строчная. В результате получаем:

Your word, Zebra, comes before banana.

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

§7.6. Строки нельзя изменить Для изменения символа в строке логично было бы использовать оператор индексирования ([]) слева от знака присваивания. Например:

greeting = "Hello, world!" Ревизия: 170 Строки greeting[0] = 'J' # ERROR!

print greeting Но вместо ожидаемого вывода Jello, world!, этот код генерирует исключение:

TypeError: object doesn't support item assignment.

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

greeting = "Hello, world!" newGreeting = 'J' + greeting[1:] print newGreeting Данное решение состоит в том, что бы сцепить новый символ со срезом строки greeting. Этот оператор не оказывает эффекта на начальную строку.

Упражнение. Напишите программу, заменяющую 5-й (если начинать считать по человечески, т.е. с единицы) символ строки Hello, world! на восклицательный знак.

§7.7. Функция find Рассмотрим такую функцию:

def find(str, ch):

index = while index < len(str):

if str[index] == ch:

return index index = index + return - Что она делает? В некоторым смысле функция find() противоположна оператору индексирования []. Отличие состоит в том, что вместо того, чтобы извлекать из строки символ по его индексу, она возвращает индекс первого вхождения символа в строке. Если символ не найден, то функция возвращает -1.

Это первый пример использования инструкции return внутри цикла. Если условие str[index] == ch, то функция возвращает значение немедленно, прерывая цикл преждевременно.

Если символ не появился в строке, то программа выходит из цикла «в штатном режиме» и возвращает -1.

Упражнение. Измените код функции find() так, чтобы требовался третий параметр – индекс в строке, начиная с которого должен производиться поиск. Не забудьте про обработку ситуаций с некорректными и предельными значениями этого параметра (например, когда указанный индекс выходит за диапазон допустимых значений).

Ревизия: 170 Строки §7.8. Циклы и счётчики Следующая программа считает количество символов, встречающихся в строке:

fruit = "banana" count = for char in fruit:

if char == 'a':

count = count + print count Программа демонстрирует интересный пример использования циклов. Переменная count инициализируется со значением 0 и затем инкрементируется16 каждый раз когда символ a найден. Когда происходит выход из цикла, переменная count содержит результат – количество символов a. Переменные, в которых сохраняется количество элементов в процессе их перебора, удовлетворяющих некоторому условию, называют счетчиками.

Упражнение. Создайте на основе кода примера функцию countLetters и обобщите ее так, чтобы она принимала строку и искомый символ в качестве параметров.

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

§7.9. Модуль string Модуль string содержит полезные функции, заметно упрощающие работу со строками. Как обычно, необходимо сначала импортировать модуль до его использования:

>>> import string Модуль string включает функцию find(), которая делает то же самое, что и функция, написанная нами. Это распространенная ситуация в области программирования:

прежде чем «изобретать велосипед», иногда стоит поискать готовые решения – всегда есть вероятность, что кто-то уже сталкивался с похожей задачей и решил ее лучше нас. К тому же разбираясь в чужом коде можно многому научиться.

Итак, для вызова функции из модуля, мы должны указать имя модуля и имя функции, используя точку в качестве разделителя:

>>> fruit = "banana" >>> index = string.find(fruit, "a") >>> print index Такой способ вызова помогает избежать конфликтов (и семантических ошибок, которые могут стать их следствием) между именами встроенных или написанных нами 16 Инкрементировать – увеличивать значение чего-либо на единицу;

декрементировать – уменьшать значение на единицу.

Ревизия: 170 Строки функций и именами функций, импортированных из модулей. Используя точку в качестве разделителя, мы можем указать какую версию find() хотим использовать.

В подтверждение мысли об «изобретении велосипеда», стоит заметить, что функция string.find() является более общим решением, чем наш вариант. Во-первых, может искать подстроки, не только символы:

>>> string.find("banana", "na") Также имеется возможность задать дополнительный аргумент, который будет определять индекс с которого надо начинать:

>>> string.find("banana", "na", 3) Или может потребоваться пара дополнительных аргументов, которые определяют диапазон индексов:

>>> string.find("bob", "b", 1, 2) - В последнем примере, поиск оказался неудачным, потому что символ b не входит в диапазон индексов от 1 до 2 (не включая 2).

Упражнение. Выведите на экран справку по модулю string и ознакомьтесь со справочной информацией следующих функций:

1. capitalize() 2. capwords() 3. count() 4. find() 5. lower() 6. replace() 7. split() 8. upper() Поэкспериментируйте с ними.

§7.10. Классификация символов Иногда возникает потребность проверить регистр символа или выяснить не является ли он цифрой. Модуль string предоставляет несколько специальных переменных, которые могут быть полезны для этих целей.

Строка string.lowercase содержит все строчные символы. Аналогично в переменной string.uppercase хранятся все заглавные буквы. Попробуйте следущие примеры и посмотрите,какой результат выдаст интерпретатор:

>>> print string.lowercase >>> print string.uppercase >>> print string.digits Мы можем использовать эти переменные и функцию find() для классифицирования символов. Например, если find(lowercase, ch) возвращает результат, отличный от -1, то символ ch должен быть строчным.

Ревизия: 170 Строки def isLower(ch):

return string.find(string.lowercase, ch) != - Так же мы можем использовать оператор in, котрый определяет, входит ли символ в строку или нет:

def isLower(ch):

return ch in string.lowercase Альтернативно мы можем использовать оператор сравнения:

def isLower(ch):

return 'a' <= ch <= 'z' Если ch между a и z, то это строчной символ.

Упражнение. Какая версия isLower() будет самой быстрой? Какие еще причины, помимо скорости, Вы можете привести для предпочтения одного другому?

Другая определенная в модуле string переменная содержит все пробельные (непечатаемые) символы, включая пробел, табуляцию ("\t") и символы возврата каретки ("\r") и новой строки ("\n") :

>>> print string.whitespace Как мы заметили в §6.6, пробельные символы перемещают курсор без печати чего либо: они создают пустое пространство между видимыми символами.

§7.11. Строки unicode Ревизия: 170 Списки Глава 8. Списки §8.1. Создание списков §8.2. Доступ к элементам списка §8.3. Длина списка §8.4. Принадлежность списку §8.5. Списки и цикл for §8.6. Операции над списками §8.7. Срезы списков §8.8. Изменение списков §8.9. Удаление элементов списка §8.10. Объекты и значения §8.11. Ссылки на объекты §8.12. Копирование списков §8.13. Списки-параметры §8.14. Вложенные списки §8.15. Матрицы §8.16. Списки и строки Ревизия: 170 Кортежи Глава 9. Кортежи Ревизия: 170 Словари Глава 10. Словари Строки, списки и кортежи используют в качестве индексов целые числа. Если же мы попытаемся использовать использовать в качестве индексов значения изменяемых типов данных, то интерпретатор выведет ошибку.

Словари схожи со списками за исключением того, что в них могут использоваться в качестве индекса значение любого неизменяемого типа (например, str, float, tuple).

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

Один из способов создать словарь – начать с пустого словаря и добавлять элементы.

Пустой словарь обозначается фигурными скобками {}:

>>> eng2sp = {} >>> eng2sp['one'] = 'uno' >>> eng2sp['two'] = 'dos' Первый оператор присваивания создает словарь названный eng2sp;

остальные операторы добавляют новые элементы в словарь. Мы можем распечатать текущее значение словаря обычным способом:

>>> print eng2sp {'one': 'uno', 'two': 'dos'} Элементы словаря выводятся через запятую;

каждый элемент содержит индекс и значение, разделенные двоеточием. В словаре индексы называют ключами, а элементы называют парами ключ-значение.

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

>>> eng2sp = {'one': 'uno', 'two': 'dos', 'three': 'tres'} Если мы снова распечатаем значение eng2sp, мы получим небольшой сюрприз:

>>> print eng2sp {'one': 'uno', 'three': 'tres', 'two': 'dos'} Пары ключ-значение расположены в другом порядке! К счастью нет повода беспокоиться о расположении, так как элементы словаря никогда не индексируются целыми индексами. Вместо этого для поиска соответствующего значения мы используем ключ:

>>> print eng2sp['two'] 'dos' Ключ 'two' выдал значение 'dos' хотя оно появляется в третьей паре ключ-значение.

§10.2. Операции над словарями Оператор del удаляет из словаря пару ключ-значение. Например, следующий словарь содержит названия различных фруктов и количество каждого фрукта на складе:

Ревизия: 170 Словари >>> inventory = {'apples': 430, 'bananas': 312, 'oranges': 525, 'pears': 217} >>> print inventory {'oranges': 525, 'apples': 430, 'pears': 217, 'bananas': 312} Если кто-нибудь купил все груши, мы можем удалить этот элемент из словаря:

>>> del inventory['pears'] >>> print inventory {'oranges': 525, 'apples': 430, 'bananas': 312} Или если скоро мы ожидаем поступления новых груш, мы можем просто изменить значение связанное с грушами:

>>> inventory['pears'] = >>> print inventory {'oranges': 525, 'apples': 430, 'pears': 0, 'bananas': 312} Функция len также работает со словарями, она возвращает число пар ключ-значение:

>>> len(inventory) §10.3. Методы словарей [NOTE: возможно стоит ввести понятие метода (на простом уровне) немного пораньше] Метод – это обычная функция, принимающая аргументы и возвращающая значения, но отличающаяся синтаксисом вызова. Подробнее с методами мы будем разбираться в главах, посвященных объектно-ориентированному программированию, где станет понятны более глубокие различия между обычными функциями и методами.

Итак, метод key получает словарь и возвращает список ключей которые находит, но вместо синтаксиса функции keys(eng2sp), мы используем синтаксис метода eng2sp.keys ().

>>> eng2sp.keys() ['one', 'three', 'two'] Такая форма записи с точкой задает имя функции, keys, а так же имя объекта, к которому необходимо применить функцию, eng2sp. Пустые круглые скобки показывают, что этот метод не принимает параметров.

Вызов метода называют invocation;

в этом случае, мы могли сказать, что мы вызываем keys() объекта eng2sp.

Похожий метод values() – он возвращает список значений в словаре:

>>> eng2sp.values() ['uno', 'tres', 'dos'] Метод items возвращает список кортежей ключ-значение:

>>> eng2sp.items() Ревизия: 170 Словари [('one','uno'), ('three', 'tres'), ('two', 'dos')] Если метод принимает аргументы, он использует тот же синтаксис что и вызов функции. Например, метод has_key() принимает ключ и возвращает истину (1) если такой ключ присутствует в словаре.

>>> eng2sp.has_key('one') >>> eng2sp.has_key('deux') Если вы пытаетесь вызвать метод без указания объекта, вы получаете ошибку. В этом случае, сообщение об ошибке не очень информативное:

>>> has_key('one') NameError: has_key §10.4. Использование псевдонимов и копирование Так как словари могут быть изменены, необходимо знать о псевдонимах. Всякий раз, когда две переменные ссылаются на один и тот же объект, изменения одной воздействуют на другую.

[TODO: стековая диаграмма] Если вы хотите изменить словарь и сохраняете копию оригинала, используйте метод copy(). Например, opposites – словарь, который содержит пары антонимов:

>>> opposites = {'up': 'down', 'right': 'wrong', 'true': 'false'} >>> alias = opposites >>> copy = opposites.copy() Переменные alias и opposites ссылаются на один и тот же объект;

переменная copy() ссылается на только что созданную копию того же словаря. Если мы изменим псевдонимы, opposites так же изменится.

>>> alias['right'] = 'left' >>> opposites['right'] 'left' Если мы изменим copy, то словарь, opposites останется прежним.

>>> copy['right'] = 'privilege' >>> opposites['right'] 'left' §10.5. Разряженные матрицы В разделе 8.14 для представления матрицы мы использовали список списков. Это хороший выбор для матрицы содержащей в основном не нулевые значения, но рассмотрим разряженную матрицу подобную этой:

Ревизия: 170 Словари 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0 0 [ ] 0 0 0 3 Представление в виде списка содержит множество нулей:

>>> matrix1 = [ [0,0,0,1,0], [0,0,0,0,0], [0,2,0,0,0], [0,0,0,0,0], [0,0,0,3,0] ] Но есть и другой способ хранения матриц – мы можем использовать словарь: ключами будут кортежи, хранящие номер строки и номер столбца. Вот представление той же матрицы в виде словаря:

>>> matrix2 = {(0,3): 1, (2, 1): 2, (4, 3): 3} Нам необходимо только три пары ключ-значение, одной для каждого ненулевого элемента матрицы. Каждый ключ – кортеж и каждое значение целое число.

Для доступа к элементу матрицы мы могли использовать оператор индексирования:

>>> matrix1[0][3] >>> matrix2[0,3] Обратите внимание синтаксис для представления в виде словаря не такой как для представления в виде вложенных списков. Вместо двух целочисленных индексов мы используем один индекс – кортеж целых чисел.

Но в таком подходе есть одна сложность. Если мы укажем на нулевой элемент, мы получим ошибку, так как в словаре нет элемента с таким ключом:

>>> matrix2[1,3] KeyError: (1, 3) Данную проблему решает метод get():

>>> matrix.get((0,3), 0) Первый аргумент – ключ, второй аргумент – значение, которое get() должен возвратить, если такого ключа в словаре нет:

>>> matrix.get((1,3), 0) get definitely improves the semantics of accessing a sparse matrix. Shame about the syntax.

Метод get определенно улучшает семантику доступа к разряженной матрице.

Ревизия: 170 Словари §10.6. Подсказки Если вы забавлялись с рекурсивной функцией поиска чисел Фибоначчи из раздела 5.12, то, наверное, заметили, что чем большие аргументы вы передаете, тем дольше функция выполняется. Более того, время расчетов увеличивается очень быстро. На одной нашей машине, fibonacci(20) завершается мгновенно, fibonacci(30) думает около секунды и fibonacci(40) будет работать почти бесконечно.

Чтобы понять почему так происходит, рассмотрим диаграмму вызовов для функции fibonacci() с n = 4:

[TODO: нарисовать в изображение http://www.ibiblio.org/obp/thinkCSpy/illustrations/fibonacci.png] Диаграмма вызовов функций отображает совокупность прямоугольных блоков, обозначающих функции, с линиями, соединяющими каждый блок с блоками функций которые он вызывает. Вверху диаграммы, fibonacci() с n = 4 вызывает fibonacci() с n = 3 и n = 2. В свою очередь, fibonacci() с n = 3 вызывает fibonacci() с n = 2 и n = 1. И так далее.

Таким образом, каждая ветка дерева, по сути, отображает изменение стека вызовов, т.е.

Поток выполнения в процессе расчетов, должен пройти по каждой ветке этого дерева.

Подсчитайте сколько раз были вызваны fibonacci(0) и fibonacci(1). Не самое эффективное решение задачи, с точки зрения производительности (хотя оно, бесспорно, красивое).

Хорошее решение – сохранять значения, которые были недавно вычислены, запоминая их в словаре. Предыдущее вычисленное значение, которое запоминается для последующего использования, называют подсказкой. Ниже приведена реализация fibonacci(), использующая подсказки:

previous = {0:1, 1:1} def fibonacci(n):

if previous.has_key(n):

return previous[n] else:

newValue = fibonacci(n-1) + fibonacci(n-2) previous[n] = newValue return newValue Словарь названный previous хранит числа Фибоначчи, которые мы уже знаем. Мы начинаем только с двух пар: 0 соответствует 1 и 1 соответствует 1.

Всякий раз, когда вызывается функция fibonacci(), она проверяет словарь, чтобы определить содержит ли он результат. Если это так, функция может немедленно возвратить результат, без выполнения дополнительных рекурсивных вызовов. Если нет, он должна рассчитать новое значение. Новое значение добавляется в словарь, перед тем как функция вернёт результат.

Используя эту реализацию, наша машина может вычислить функцию fibonacci() при n = 40 почти мгновенно. Но когда мы пытаемся вычислить fibonacci(50), мы сталкиваемся с другой проблемой:

Ревизия: 170 Словари >>> fibonacci(50) OverflowError: integer addition Ответ, как вы увидите через минуту 20365011074. Проблема в том, что это число слишком большое чтобы поместиться в тип int. Такую ситуацию называют переполнением.

К счастью эта проблема имеет простое решение.

§10.7. Тип «длинное целое число» Питон предоставляет тип названный long int, который может хранить целые числа любого размера. Есть два пути создать значение типа long int. Первый – написать целое число с заглавной L в конце.

>>> type(1L) Другой способ – использовать функцию long() чтобы преобразовать значение к типу long int. Функция long() может принимать любые численные типы и даже строки цифр:

>>> long(1) 1L >>> long(3.9) 3L >>> long('57') 57L Все математические операции работают с long int, значит, нам не придется сильно переделывать нашу функцию fibonacci():

>>> previous = {0:1L, 1:1L} >>> fibonacci(50) 20365011074L Простым изменением начального содержимого словаря, мы изменяем поведение функции. Первые два числа в последовательности long int, поэтому все последующие числа в последовательности тоже.

Упражнение. Измените функцию factorial() так, чтобы она возвращала результат типа long int. Протестируйте ее.

§10.8. Подсчет букв В упражнении главы 7 мы написали функцию countLetters, которая подсчитывала число вхождений буквы в строку. Более общий вариант этой задачи – построение гистограммы букв в строке, то есть вычисление, сколько раз каждая буква появляется в строке. Такие гистограммы могут пригодиться для частотного анализа – одного из метода расшифровки кодов простой замены (например, шифра Цезаря)17, или для компрессии текстовых файлов. Так как различные буквы появляются с различными частотами, мы можем 17 Кстати, метод частотного анализа использовал Шерлок Холмс для того, чтобы прочестьтекст зашифрованный с помощью «пляшущих человечков».

Ревизия: 170 Словари сжать файл, используя короткие коды для распространенных букв и длинные коды для букв, которые появляются менее часто (алгоритм Фано, алгоритм Хемминга и другие).

Словари предоставляют элегантный способ создавать гистограммы:

>>> letterCounts = {} >>> for letter in "Mississippi":

... letterCounts[letter] = letterCounts.get (letter, 0) +...

>>> letterCounts {'M': 1, 's': 4, 'p': 2, 'i': 4} Мы начинаем с пустого словаря. Для каждой буквы в строке мы находим текущий счетчик (возможно нулевой) и увеличиваем его на единицу. В конце словарь содержит пары:

буквы и их частоты.

Для красоты можно вывести гистограмму в алфавитном порядке с помощью методов items() и sort():

>>> letterItems = letterCounts.items() >>> letterItems.sort() >>> print letterItems [('M', 1), ('i', 4), ('p', 2), ('s', 4)] [NOTE: непонятная фраза:] Вы встречались с методом items() ранее, но метод sort() – первый метод который вы применяете к спискам. Есть другие методы списков, включая append(), extend() и reverse(). Еще раз просмотрите справку (функция help()) для получения их детального описания.

Ревизия: 170 Файлы и обработка исключений Глава 11. Файлы и обработка исключений Ревизия: 170 Классы и объекты Глава 12. Классы и объекты Ревизия: 170 Классы и функции Глава 13. Классы и функции Ревизия: 170 Методы Глава 14. Методы Ревизия: 170 Наборы объектов Глава 15. Наборы объектов Ревизия: 170 Наследование Глава 16. Наследование Ревизия: 170 Связные списки Глава 17. Связные списки Ревизия: 170 Стеки Глава 18. Стеки Ревизия: 170 Очереди и очереди с приоритетами Глава 19. Очереди и очереди с приоритетами Ревизия: 170 Деревья Глава 20. Деревья Ревизия: 170 Функциональное программирование Глава 21. Функциональное программирование Ревизия: 170 Заключение. С высоты птичьего полета Заключение. С высоты птичьего полета «Ты можешь подняться выше, Джонатан, потому что ты учился. Ты окончил одну школу, теперь настало время начать другую» Р. Бах, «Чайка по имени Джонатан Ливингстон».

Ревизия: 170 Советы по отладке программ Приложение A. Советы по отладке программ Ревизия: 170 Создание и использование модулей Приложение B. Создание и использование модулей Ревизия: 170 Создание типов данных Приложение C. Создание типов данных Ревизия: 170 Написание программ с графическим интерфейсом Приложение D. Написание программ с графическим интерфейсом Ревизия: 170 Методологии командной разработки Приложение E. Методологии командной разработки Ревизия: 170 Методические указания преподавателям Приложение F. Методические указания преподавателям

Pages:     | 1 ||



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.