Лог №5
Содержание
Диктант
Мы описываем функцию collatz, которая принимает на вход число n. Если n меньше двух, выходим из функции. Печатаем значение n на экран. Если n кратно трём, запускаем collatz печатать ответы для n/3. Иначе запускаем collatz печатать ответы для 2n+1. Конец описания функции collatz.
Вызываем функцию collatz для n=19 и для n=20.
Лирическое отступление
"Collatz numbers"1, по-русски их же называют "числа-градины", – это предмет одной из неразрешённых задач современной математики.
Гипотеза Коллатца про них состоит в том, что для любого входного значения n рано или поздно пройдёт через значение 1. Хотя эту гипотезу проверили для чисел до миллиона (кажется, и дальше), и кажется, что она верна, ведут себя эти числа слишком непредсказуемо, и доказать эту гипотезу пока что никому не удалось.
Рекурсия
В этом примере функция collatz вызывает в некоторые моменты саму себя. За счёт того, что рано или поздно (если гипотеза Коллатца верна) n уменьшится до 1, процесс вызова функцией самой себя рано или поздно завершится.
Однако, в питоне зашито ограничение, что всего вызовов функций, которые он исполняет одновременно, может быть не более 1000, поэтому для сложных входных значений n (например, 20) питон не справится с вычислением ответа и выдаст в итоге ошибку.
while
В питоне есть ещё один вид циклов, о которых я пока что не успел вам рассказать.
Не успел рассказать про них я неспроста: они почти никогда не нужны, и за очень редкими случаями, если вы пользуетесь этим видом циклов, вы почти наверняка что-то делаете не самым простым способом.
Пишутся они так:
Условие – это любое выражение, которое смогла бы проинтерпретировать функция bool (как и для if). Тело цикла – это любой питонский код. Главное, чтобы он шёл с бОльшим отступом от начала строки, чем сам while.
Поведение этих циклов в точности совпадает с тем, как они себя ведут в Pascal, C, Javascript, PHP и почти любом другом языке2, а именно:
проверяем условие; если оно вычислилось в значение False или эквивалент, то на этом цикл завершается; в противном случае продолжаем
выполняем тело
снова проверяем условие; если оно вычислилось в значение False или эквивалент, то на этом цикл завершается; в противном случае продолжаем
выполняем тело
... [и так покуда условие даёт нам эквивалент True, продолжем выполняться]
Мы можем переписать наши числа-градины с использованием while так, чтобы наша программа не упиралась в ограничение количества одновременно вычисляемых функций:
Упражнение. Завершится ли такая программа?
Два слова о return
Поставим задачу немного другим боком: мы хотим получить значение n спустя сколько-то (скажем, 100) шагов.
Для сравнения
Что мы можем с ними делать?
То, что мы дали в print(), ушло на экран, мы это увидели, нам хорошо, но в программе мы уже никак не дотянемся до этого значения.
То, что мы отправили в return, оказалось результатом функции. Мы этого не видим на экране, зато можем с этим значением делать что угодно: положить в переменную, дать в качестве аргумента другой функции, выдать на экран.
Сравните:
Напоминание: в питоне любая функция возвращает результат, даже, если мы не просили её об этом. (В этом смысле в питоне нет разделения на "функции" и "процедуры", как в паскале)
Локальные переменные
А чего мы ожидаем от такой пары команд:
Если вы ещё не забыли, то переменная n у нас в хвост и в гриву использовались в функции collatz.
Но в том-то и дело, что вы имели полное право это забыть. Более того, вы имели полное право не знать, какие переменные для чего использует какая-нибудь функция (например sin(), который, вообще, очень сложно устроен).
Поэтому питон делает так, что переменные, которые вы создавали в теле функции, видны только изнутри этой самой функции. Такие переменные называются локальными. И при вызове функции снаружи вы ни в коем случае не должны думать о том, как функция устроена. Вы должны думать только о том, что она делает.
Надо заметить, что аргументы функции – это тоже самые обычные локальные переменные.
Разделяй и властвуй
Подход про то, что мы не должны думать о том, как устроена функция, когда мы ей пользуемся, можно обобщить.
Во-первых, когда мы реализуем функцию, лучше всего тоже никогда не думать о том, что происходит вокруг неё: это знание нам не поможет, а только отвлечёт.
А во-вторых, когда мы решаем большую задачу, очень хороший подход состоит в том, чтобы найти в неё небольшую часть, которой мы можем дать имя и объяснить себе (а лучше, специально для этого заведённому собеседнику), чего мы от неё хотим. В таком случае, мы можем дальше решать задачу так, как будто у нас есть функция, которая эту задачу решает. (А потом делать эту функцию так, как будто внешней большой задачи нет).
В древнем Риме этот подход назывался "разделяй и властвуй".
Программирование почти всегда призвано решать задачи, которые мы своим умом решить не можем (иначе зачем бы их программировать). А значит, основная цель программирования состоит в том, чтобы подстраивать задачу под свои мозги так, чтобы мозгам с этой задачей было как можно проще справиться. Мозг – это самый главный самый ценный ресурс, который должен экономить программист (а не такты процессора или занятая оперативная память).
Да будем же стараться выкидывать из мозга все лишние вещи, какие только можем, в тот момент, когда мы решаем какую-то часть задачи.
Два слова про понятие "алгоритм"
Более-менее умышленно я давал вам до сих пор всяческие программистские задачи, и не говорил слова "алгоритм".
Алгоритм – это описание схемы поведения, которое не допускает неоднозначного прочтения.
Для решения любой сложной задачи всегда лучше сначала описать для себя алгоритм на более удобном нам языке, а потом перевести с него на питон.
Упражнение. Представьте себе гордого выходца с гор в центре Москвы. Опишите для него алгоритм решения задачи "безопасно перейти улицу".
(Для этого нужно сесть, взять листок бумаги и ручку, сосредоточиться, подумать, и написать такой алгоритм).
Упражнение. Возьмите только что написанное решение и найдите пример ситуации или улицы, для которой оно не применимо.
(Если вы честно и тщательно выполняли предыдущее упражнение, такой пример придумать обязательно получится. Если у вас не получается найти такого примера, то, вероятно, вы написали решение в слишком общих терминах, которые горцу не помогут).
То, как мы выполняли эти упражнения, и есть правильный подход к сочинению алгоритма решения любой задачи: сначала придумать общий ход решения для наиболее типичного случая, а потом искать и искать, долго и тщательно, случаи, для которых такой ход решения работать не будет. И подправлять соответствующим образом решение. И снова искать острые углы.
Файлы
Попробуем написать игру в загадки: программа загадывает слово и даёт нам поле ввода, чтобы мы пытались это слово разгадать. В чуть более сложной версии мы захотим от программы видеть подсказки, но пока что, для простоты отладки, будем выводить в качестве подсказки просто само слово.
Сначала пишем болванку программы:
Вроде, ничего сложного? Label делает то же, что и кнопка, только никак не реагирует, если в него тыкать мышко. То есть это просто неподвижный кусочек текста в окошке.
Добавим какой-то список слов, из которых выберем случайное, и будем при нажатии на кнопку выводить его:
1 import tkinter as tk
2 import random
3
4 words = ['берёза', 'дуб', 'ясень', 'ива']
5
6 def check_guess():
7 word = random.choice(words)
8 answer.configure(text="it was " + word)
9
10 root = tk.Tk()
11 answer = tk.Label(root, text="Guess a word:")
12 answer.pack(fill='x')
13 guess = tk.Entry(root)
14 guess.pack(fill='x')
15 ok = tk.Button(root, text="Guess", command=check_guess)
16 ok.pack(fill='x')
17 root.mainloop()
Нет, фигня. Мы-то хотим, чтобы слово было один раз случайным на весь запуск программы, а оно каждый раз меняется. Так мы никогда не угадаем загаданное.
Значит нужно бросать монетку и выбирать слово в самом начале, а не каждый раз, когда мы жмём на кнопку:
1 import tkinter as tk
2 import random
3
4 words = ['берёза', 'дуб', 'ясень', 'ива']
5 word = random.choice(words)
6
7 def check_guess():
8 answer.configure(text="it was " + word)
9
10 root = tk.Tk()
11 answer = tk.Label(root, text="Guess a word:")
12 answer.pack(fill='x')
13 guess = tk.Entry(root)
14 guess.pack(fill='x')
15 ok = tk.Button(root, text="Guess", command=check_guess)
16 ok.pack(fill='x')
17 root.mainloop()
Так-то лучше.
И теперь мы можем добавить проверку на то, что введённое слово совпадает с загаданным:
1 import tkinter as tk
2 import random
3
4 words = ['берёза', 'дуб', 'ясень', 'ива']
5 word = random.choice(words)
6
7 def check_guess():
8 if guess.get() == word:
9 answer.configure(text="YESS!")
10 else:
11 answer.configure(text="No, it was " + word)
12
13 root = tk.Tk()
14 answer = tk.Label(root, text="Guess a word:")
15 answer.pack(fill='x')
16 guess = tk.Entry(root)
17 guess.pack(fill='x')
18 ok = tk.Button(root, text="Guess", command=check_guess)
19 ok.pack(fill='x')
20 root.mainloop()
Теперь интересное. Мы хотим не носить список слов в программе, а брать его из файла.
В питоне для того, чтобы с файлом работать, его нужно сначала открыть, потом прочитать, потом закрыть.
Для того, чтобы мы не забывали к каждому "открыть" делать "закрыть" в питоне есть специальная конструкция with (она используется почти только для работы с файлами, хотя, если очень захотеть, можно использовать и для чего-нибудь ещё):
Делает примерно то же самое, что и:
Файл открывается функцией open(), которой мы даём имя файла:
Когда мы открываем файл, мы получаем объект, который представляет файл. Первый вариант, что мы можем с ним сделать – это просто прочитать целиком содержимое файла и получить его в виде питонской строки. Это делает метод .read():
Кодировки
Очень важное лирическое отступление.
Кажется, все мы знаем, что такое байт:
это восемь бит (а бит – это либо 0, либо 1)
- это самая всеми любимая единица измерения объёма данных
это число от 0 до 255 (или от 1 до 256 или от -128 до 127 – смотря откуда отсчитывать; но обычно отсчитывают от 0)
Так вот: файл – это последовательность байт. То есть последовательность чиселок. А мы хотим получить последовательность букевок. Значит, нам нужна таблица, в которой про каждое чиселко сказано, как оно выглядит, в духе такого:
... |
... |
32 |
пробел |
... |
... |
48 |
'0' |
... |
... |
65 |
'A' |
В самом понятии ничего сложного.
Впрочем, бывают ньюансы. Например, благодаря в первую очередь нашим братьям с иеролифической письменностью (а иероглифов, надо заметить, у китайцев больше 10000), но и не без помощи языкового разнообразия, появились кодировки, которые задают символ для пары соседних байт, в таком духе:
... |
... |
00, 32 |
пробел |
... |
... |
04, 79 |
'я' |
... |
... |
И, даже такие, которые в зависимости от первого байта задают символ либо только по одному байту, либо по двум.
Реальная же трудность в том, что таких кодировок за время существования текстов в компьютерах накопилось дикое множество, и нужно как-то в них разбираться.
Всё же, всё не так страшно. Для русского языка вы почти наверняка встретите только одну из двух кодировок:
utf-83
- cp1251 (она же windows-1251)
str.split
Итак, вернёмся к нашей программе с файлами.
Сделаем файл, в котором на каждой строке написано по слову. И для простоты сохраним его там же, где лежит наша питонская программа.
Мы уже можем прочитать файл и получить его текст в переменной в виде питонской строки. Нужно разбить эту строку на слова.
В питоне для этого есть готовое решение:
1 words = text.split()
Этот метод разбивает текст на слова по любому количеству пробелов между ними.
Сложив вместе всё свежеизученное, получаем (новых строк по сравнению с прошлой версией только три):
1 import tkinter as tk
2 import random
3
4 with open("words.txt", encoding='utf-8') as file:
5 text = file.read()
6 words = text.split()
7 word = random.choice(words)
8
9 def check_guess():
10 if word in guess.get():
11 answer.configure(text="YESS!")
12 else:
13 answer.configure(text="No, it was " + word)
14
15 root = tk.Tk()
16 answer = tk.Label(root, text="Guess a word:")
17 answer.pack(fill='x')
18 guess = tk.Entry(root)
19 guess.pack(fill='x')
20 ok = tk.Button(root, text="Guess", command=check_guess)
21 ok.pack(fill='x')
22 root.mainloop()
str.split() и str.join()
Для полноты картины (для тех, кому лень читать help("".split) или поэкспериментировать), .split() умеет ещё:
- разбивать строку по какому-нибудь другому разделителю:
- ограничиваться только небольшим количеством разделителей:
И есть ещё и обратная к split() функция, которая называется (о неожиданность): .join().
В ней только одна странность: разделитель, который мы втыкаем между склеиваемыми частями, мы должны дать как объект, из которого мы достаём метод join(), а в качестве аргумента уже даём только список слов:
file.readlines()
Вернёмся к игре в загадки.
Добавим в наш файл подсказки к каждому слову: просто в виде слово пробел подсказка. Например, так:
дуб с волнистыми листьями, очень тупой кошка с усами и лапами вместо паспорта ива плакучая
И сохраним это в words.txt
Что нам с этим файлом делать? Мы хотим получить его в виде списка строк. Можно прочитать в виде одной строки и потом с помощью split() разбить по переносу строки, но вообще для этого в питоне есть специальный метод readlines().
Теперь мы можем выбрать из строк произвольную – которая будет описывать какое-то произвольное слово.
И нам осталось разбить результат, отрезать от него первое слово (но остаток-то нужно склеить обратно, чтобы получить строку!)
Например, так:
1 import tkinter as tk
2 import random
3
4 with open("words.txt", encoding='utf-8') as file:
5 lines = file.readlines()
6 line = random.choice(lines)
7
8 hint = line.split()
9 word = hint.pop(0)
10 hint = " ".join(hint)
11
12 def check_guess():
13 attempt = guess.get()
14 if word.lower() in attempt.lower():
15 answer.configure(text="YESS!")
16 else:
17 answer.configure(text="Нет, " + hint)
18
19 root = tk.Tk()
20 answer = tk.Label(root, text="Guess a word:")
21 answer.pack(fill='x')
22 guess = tk.Entry(root)
23 guess.pack(fill='x')
24 ok = tk.Button(root, text="Guess", command=check_guess)
25 ok.pack(fill='x')
26 root.mainloop()
Или, сильно проще так, если вспомнить про второй аргумент .split(), да и вдобавок про прекрасную констркцию "распаковка кортежа", которую мы узнали в прошлый раз:
1 import tkinter as tk
2 import random
3
4 with open("words.txt", encoding='utf-8') as file:
5 lines = file.readlines()
6 line = random.choice(lines)
7
8 word, hint = line.split(maxsplit=1)
9
10 def check_guess():
11 attempt = guess.get()
12 if word.lower() in attempt.lower():
13 answer.configure(text="YESS!")
14 else:
15 answer.configure(text="Нет, " + hint)
16
17 root = tk.Tk()
18 answer = tk.Label(root, text="Guess a word:")
19 answer.pack(fill='x')
20 guess = tk.Entry(root)
21 guess.pack(fill='x')
22 ok = tk.Button(root, text="Guess", command=check_guess)
23 ok.pack(fill='x')
24 root.mainloop()
str.strip()
Тут мы внезапно увидели такую неприятность: у строки в конце остаётся лишний символ '\n' (символ переноса строки), поэтому мы видим после текста подсказки ещё одну пустую строку.
Вот тут-то и возникает задача отрезать с краёв слова лишние незначимые символы (ну то есть всяческие пробелы и переносы строк), которую мы для строк решать научились давным-давно, но не знали куда применить:
1 import tkinter as tk
2 import random
3
4 with open("words.txt", encoding='utf-8') as file:
5 lines = file.readlines()
6 line = random.choice(lines)
7
8 word, hint = line.split(maxsplit=1)
9
10 def check_guess():
11 attempt = guess.get()
12 if word.lower() in attempt.lower():
13 answer.configure(text="YESS!")
14 else:
15 answer.configure(text="Нет, " + hint.strip())
16
17 root = tk.Tk()
18 answer = tk.Label(root, text="Guess a word:")
19 answer.pack(fill='x')
20 guess = tk.Entry(root)
21 guess.pack(fill='x')
22 ok = tk.Button(root, text="Guess", command=check_guess)
23 ok.pack(fill='x')
24 root.mainloop()
На паре я по ошибке назвал их числами Марсена Мерсенна (видимо, он всплыл у меня в памяти как автор одного из лучших генераторов псевдослучайных чисел), да и вдобавок несколько изменил определение. (1)
По крайней мере, из нешуточных языков программирования, это верно для каждого, который я знаю. (2)
Если вы можете влиять на кодировки, советую всегда пользоваться именно ей (3)