Эксперт по сдаче вступительных испытаний в ВУЗах
Практическое занятие №2
В Питоне можно использовать цепочки операций сравнения, о которых не говорилось на лекции. Рассмотрите следующие примеры и попробуйте объяснить код:
In [3]:
x = 5
1 < 5 < 10
Out[3]:
True
In [4]:
x = 5
1 < (5 < 10)
Out[4]:
False
Некто попытался реализовать «наивную» функцию умножения с помощью сложений. К сожалению, в коде много ошибок. Сможете ли вы их исправить?
In [5]:
def naive_mul(x, y):
r = 1
for i in range(0, y — 1):
x = x + r
naive_mul(10, 15)
File «<ipython-input-5-14a37f229255>», line 3
for i in range(0, y — 1):
^
IndentationError: unexpected indent
Добавьте к naive_mul автоматическое тестирование для проверки обоих аргументов в диапазоне от 0 до 100. Сравнивайте с встроенным умножением, используя конструкцию assert.
Существует старинный метод умножения по методу русского крестьянина. Разобрать его проще на примере.
Предположим, мы хотим перемножить 10 и 15:
10
15
5
30
2
60
1
120
В первом столбце последовательно записывают результаты деления на 2 с отбрасыванием остатка. Во втором столбце находятся результаты умножения на 2. Отмечаем нечетные числа в первом столбце. Складываем те
числа в правом столбце, которые стоят напротив отмеченных ранее чисел. То есть 30 + 120 = 150. В нашем случае мы не учитывали исходные числа при сложении, но учитывать их, вообще говоря, нужно.
В этом алгоритме используются лишь простейшие операции: умножение на 2, целочисленное деление на 2, проверка на нечетность и сложение. Эти операции соответствуют тем элементарным операциям, которые эффективно выполняет любой процессор. Сам же алгоритм, несмотря на кажущуюся необычность, является вариантом умножения в столбик при использовании двоичного представления чисел:
1111
1010 *
—-
0000
1111
0000
1111
Задачи:
1. Реализуйте функцию fast_mul в соответствии с алгоритмом двоичного умножесия в столбик. Добавьте автоматическое тестирование, как в случае с naive_mul.
2. Реализуйте аналогичную функцию fast_pow для возведения в степень (ее легко получить из предыдущего решения).
3. (повышенной сложности) Реализуйте генератор решений fast_mul_gen(y) для задач на тему замены умножения сложением. Ваша функция должна выдать текст функции f(x) (умножение на ранее заданный y), тело которой состоит из некоторого числа присваиваний. Для вывода функции используйте print. Добавьте автоматическое тестирование. Объясните, почему в общем случае у вас получается большее количество сложений, чем в исходном условии части 1.
Скачайте игру DandyBot. Код для своего игрока записывается в файле user_bot.py. Игра запускается с помощью main.py.
Вот простой пример содержимого user_bot.py:
def script(check, x, y):
return ‘right’
Игровая логика записывается исключительно в теле функции script. В нашем случае игрок будет постоянно двигаться вправо.
Полный список действий, которые можно возвращать из функции script, задающей «интеллект» игрока:
‘up’. Двигаться вверх на клетку.
‘down’. Двигаться вниз на клетку.
‘left’. Двигаться влево на клетку.
‘right’. Двигаться вправо на клетку.
‘pass’. Ничего не делать.
‘take’. Взять золото.
Для изучения среды есть функция check:
check(‘player’, x, y). True, если какой-то игрок в позиции (x, y).
check(‘gold’, x , y). Если золото в позиции (x, y), то вернуть его количество, иначе вернуть 0.
check(‘wall’, x, y). True, если стена в позиции (x, y).
check(’empty’, x, y). True, если пусто в позиции (x, y).
check(‘level’). Вернуть номер текущего уровня.
Ваша задача — пройти 4 уровня. Дополнительно устанавливаемыми библиотеками и глобальными данными пользоваться нельзя.
