Лицей ФТШ > Задания по программированию для 2017а

Задания по программированию для 2017а

Задачи по выч. геом.

Алгоритмы на строках

Наш маленький MVC с урока

Задание в классе: на основе этого реализовать крестики-нолики для двух игроков.

from http.server import HTTPServer, SimpleHTTPRequestHandler
import time
 
hostName = "localhost"
hostPort = 566
 
 
class Model:
    def __init__(self, n):
        self.__n = n
        self.__field = None
        self.restart()
 
    def restart(self):
        self.__field = [[0 for i in range(self.__n)] for j in range(self.__n)]
 
    def n(self):
        return self.__n
 
    def field(self):
        return self.__field # TODO: clone
 
    def move(self, x, y):
        self.__field[x][y] += 1
 
 
class MyHandler(SimpleHTTPRequestHandler):
    def do_GET(self):
        self.send_response(200)
        self.send_header("Content-type", "text/html")
        self.end_headers()
        html = control.get_html(self.path)
        self.wfile.write(bytes(html, "utf-8"))
 
 
class Control:
    def __init__(self, model, view):
        self.__model = model
        self.__view = view
 
    def get_html(self, path):
        if path == "/index.html" or path == "/index.htm":
            path = "/"
        if len(path) >= 5:
            x, y = map(int, path[2:].split(","))
            self.__model.move(x, y)
        if path == "/":
            self.__model.restart()
 
        html = "<html><body>"
        html += self.__view.draw_field()
        html += "</body></html>"
        return html
 
 
class HTMLView:
    def __init__(self, model):
        self.__model = model
 
    def draw_field(self):
        html = "<table>"
        for i in range(self.__model.n()):
            html += "<tr>"
            for j in range(self.__model.n()):
                html += "<td><a href='/?%s,%s'>" % (i, j)
                html += str(self.__model.field()[i][j])
                html += "</a></td>"
            html += "</tr>"
        html += "</table>"
        html += "<br/><a href='/'>Restart</a>"
        return html
 
model = Model(3)
view = HTMLView(model)
control = Control(model, view)
myServer = HTTPServer((hostName, hostPort), MyHandler)
print(time.asctime(), "Server Starts - %s:%s" % (hostName, hostPort))
try:
    myServer.serve_forever()
except KeyboardInterrupt:
    pass

Наш маленький POST-сервер

index.html и a.py

Задание: свой сервер

Реализовать свой сервер, который делает перевод из римских чисел в арабские и наоборот.

127.0.0.1/12 должно выдавать XII
127.0.0.1/XIII должно выдавать 13
127.0.0.1 должно выдавать правила пользования сервером

Наш маленький серверок с урока

from http.server import HTTPServer, SimpleHTTPRequestHandler
import time

hostName = "localhost"
hostPort = 80

class MyHandler(SimpleHTTPRequestHandler):
def write(self, s):
self.wfile.write(bytes(s, "utf-8"))

def do_GET(self):
global counter
if self.path == "/":
self.path = "/favicon.ico"
if self.path == "/favicon.ico" or self.path == "/a.py":
SimpleHTTPRequestHandler.do_GET(self)
return
a = self.path[1:].split("+")
print(a)
a = map(int, a)
ans = sum(a)
counter += 1

self.send_response(200)
self.send_header("Content-type", "text/html")
self.end_headers()
self.write("Title goes here.")
self.write("This is a test.")
self.write("You accessed path: " + self.path + "")
self.write("Answer: " + self.path[1:] + "=" + str(ans) + "")
self.write("You are Number " + str(counter) + ".")
self.write("")

counter = 0

#HTTPServer((hostName, hostPort), MyHandler).serve_forever()
myServer = HTTPServer((hostName, hostPort), MyHandler)
print(time.asctime(), "Server Starts - %s:%s" % (hostName, hostPort))

try:
myServer.serve_forever()
except KeyboardInterrupt:
pass

myServer.server_close()
print(time.asctime(), "Server Stops - %s:%s" % (hostName, hostPort))

Задание «Web-запросы-1»

Пользователь вводит число — чей-то id во Вконтакте.
Ваша программа узнает про этот id его имя и фамилию на английском. (Для этого разобраться в https://vk.com/dev/api_requests)
Ваша программа берет первые буквы имени и фамилии и узнает,
как расшифровывается эта аббревиатура в самом частом случае. (Разобраться в: http://www.nactem.ac.uk/software/acromine/rest.html)

Пример: 7373 -> Mikhail Dvorkin -> MD -> molecular dynamics

Задание «Web-запросы-2»
Интеллектуальная забава "Антибуриме" заключается в восстановлении последних слов в данной строфе. Например:
Котлете радуюсь _____

Она не раз воспета _____

Но в то же время и _____

Неоднократно мной _____

Ваша программа должна:

Скачать страницу http://www.vekperevoda.com/alphabet.htm (в формате HTML)
Выбрать произвольного переводчика из этого списка
Скачать страницу работ этого переводчика (в формате HTML)
С этой страницы "вынуть" четыре строчки из начала стихотворения, они будут выглядеть примерно так:
<div class="poem-body"> 
Я с вами жил, страдал и плакал вместе с вами. 
Кто честен был, тот никогда мне не был дальным. 
Теперь иду от вас я к духам, жить с тенями 
И, точно счастье было здесь, иду печальным.

Показать эти 4 строки пользователю с последними словами, замененными на _____.
Спросить у пользователя его вариант заполнения пропусков.
Выдать пользователю его результат — число от 0 до 4.

Примечание. Пример работы с кодировками:
r = requests.get("http://www.vekperevoda.com/alphabet.htm")
s = r.content.decode(r.apparent_encoding)

Пример использования шаблона «Model, View, Controller»

GUI в библиотеке tkinter

На экране должны быть два поля ввода (Entry), кнопка "Add" и текст (Label), вначале пустой.
По нажатию кнопки программа должна взять из полей ввода два числа и вывести их сумму в Label.
Гарантируется, что в полях ввода действительно будут числа.
Вывести на экране шахматную доску 8×8, составленную из кнопок. Обязательно квадратных.
(Клетки должны быть раскрашены в шахматном порядке).

Пользователь вводит с консоли число n, и затем n строк в следующем формате:
x y цвет надпись_без_пробелов

Например:
2
300 50 green HELLO_WORLD
50 200 red GOOD_LUCK

Вывести на экране эти надписи в этих позициях с этими цветами.

На экране четыре кнопки по краям окошка с надписями вверх, вниз, влево, вправо соответственно.
В центре экрана 25 кнопок в форме квадрата 5×5, на которых написаны номера от 0 до 24.
Сверху экрана поле для ввода (Entry).

При нажатии кнопки вверх, вниз, влево, вправо происходит следующее:
Из поля ввода берется число m (гарантируется, что там натуральное число), и
все кнопки из центрального блока, номера которых делятся на m, двигаются на 5 пикселей в
соответствующем направлении.
Задание номер 1, но с «защитой от дурака»: при некорректном вводе
в текстовое поле должен выводиться текст "Error".
На экране одна кнопка. При нажатии на клавиатуре клавиш "w", "a", "s", "d" она двигается
вверх, влево, вниз, вправо соответственно. При нажатии "i" она становится больше, при нажатии
"k" — меньше. На самой кнопке всегда отображаются её текущие координаты и размер,
в формате: "x=5, y=100, size=20".

Резюме

(Хозяйке на заметку: шпаргалка по LaTex.)

Написать и сверстать в системе LaTeX своё резюме.

Содержательно — не забудьте включить туда следующие данные о вас:

образование;
имеющиеся умения, знания;
достижения.

Технически — ваша задача использовать:

разбиение на разделы (section), а можно и подразделы (subsection);
оформление заголовка (author + title + date);
работу со шрифтом: курсив/полужирный, размер...;
ну и всякое разное на ваш вкус.

Результат прислать М. Э. на почту. Причём, возможно, всем будет удобнее, если вы создадите документ
на сайте Papeeria или ShareLaTeX, и пришлёте М. Э. просто ссылку на него.
Но, внимание, тогда, оказывается, нужно, зайти на этот сервис не анонимно, а
залогинившись и специально отметить этот документ как публичный, а не приватный.

Метод Гаусса

Материалы про метод Гаусса.

Проект «Электрические схемы»

Здесь появится описание проекта и этапов работы над ним.

Лабиринт — теперь графический!

В левой части экрана поле лабиринта — прямоугольник с препятствиями.
По нему ходит герой (окружность, а лучше человечек, а ещё лучше изображение из файла).

В правой части экрана кнопки управления вверх-вниз-вправо-влево.

Пример апплета с графикой и управлением

Игра на прогрессбарах

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

Игра на чекбоксах

Пользователю показывается прямоугольник из чекбоксов.
В начале поле заполняется произвольным образом (каждый чекбокс либо выбран, либо нет, с вероятностью 50%).

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

Тест

Написать апплет, который задает пользователю вопрос(ы) c ответами да/нет.

Пример апплета

Рисование отрезка

После изучения формата BMP, напишите программу, реализующую следующую процедуру:

Пользователь вводит с клавиатуры 4 числа: x₁, y₁, x₂, y₂.
Программа выводит в итоговый bmp-файл изображение, на котором
пискели (x₁, y₁) и (x₂, y₂) соединены отрезком.

Должны корректно обрабатываться случаи вертикального и горизонтального отрезков и отрезка нулевой длины.

Самостоятельное изучение формата BMP

Ваша задача — самостоятельно разобраться в том, как устроен формат BMP.

Серьезное улучшение относительно того, что было рассказано на уроке:

Лучше читать файл с помощью FileInputStream, а записывать с помощью FileOutputStream.

FileInputStream in = new FileInputStream("a.bmp");
in.read(); // вернет один байт из файла или -1, если файл закончился.
FileOutputStream out = new FileOutputStream("b.bmp");
out.write(239); // запишет в файл байт равный 239
in.close();
out.close(); // не забывайте это делать

Предлагаемый (но не обязательный) план работы таков:

Зафиксировать размер картинок, с которыми вы будете работать, например, 16×16.
Создать (в программе Paint или чем-то подобном) bmp-файл такого размера, например, белого цвета.
Прочитать содержимое этого файла написанной вами программой (используйте FileInputStream), поизучать.
Изменить bmp-файл, например, закрасить синим, провести черный отрезок и т. д.
Повторять предыдущие 2 пункта, пока всё не станет ясно.
Написать программу, которая выводит корректный bmp-файл
(используйте FileOutputStream и .write(x)), в котором изображено то, что вы хотите
(разноцветные линии и фигуры, первая буква вашего имени и т. д.)
Дополнительное задание: научиться работать с файлами не зафиксированного, а произвольного размера.

Работа в классе 12/13 марта

В любом порядке задачи из этих трех наборов:

первый;
второй;
третий.

Анализ текста

Прочитать файл romeo_and_juliet.txt и вывести в файл analysis.txt
результат частотного анализа слов в тексте.

Базовый вариант: вывести в любом порядке слова, встречающиеся в тексте,
и их количество, например:

not 30

the 566

a 239

Продвинутый вариант: только 20 самых частых слов, в порядке уменьшения частоты.

Сам текст можно скачать.

Рекурсия

Напишите рекурсивные методы, вычисляющие:

сумму чисел от 1 до n;
n!! (произведение только тех чисел от 1 до n, которые имеют ту же четность, что и n; например 6!! = 6×4×2 = 48);
число Фибоначчи номер n (первое и второе число Фибоначчи равно 1, каждое следующее — сумма двух предыдущих);
a в степени b (a и b — натуральные числа);
a × b, при этом не используя операцию умножения;
старшую цифру (то есть первую цифру) натурального числа n;
сумму цифр натурального числа n;
максимальную из цифр натурального числа n;
является ли данная строчка s палиндромом;
на сколько в данном английском слове s согласных букв больше, чем гласных.

Реализовать одну программу (один класс), в котором присутствуют методы, решающие эти задачки,
а также метод main, в котором эти методы вызываются на примерах (хотя бы один пример на каждую задачку).
Программу прислать по почте М. Э.

Игра «Быки и коровы»

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

Ваша программа загадывает произвольное число из описанного выше класса
(но не сообщает его пользователю).

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

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

Задание на тему «строки»

Пользователь вводит строку s. Обозначим буквой L длину введённой строки.

Вывести её же, по одному символу на строке.
Вывести её же в обратном порядке.
Вывести сначала чётные символы строки s (2-й, 4-й, ... в «бытовой» нумерации), затем нечётные символы (1-й, 3-й, ... в «бытовой» нумерации).
Вывести строку s, в которой символы номер (L / 3) и номер (2 * L / 3) поменяны местами.
Вывести L копий строки s; в i-й копии вместо i-го символа должна стоять звёздочка, например:
*hip
s*ip
sh*p
shi*

Определить, является ли строка s палиндромом.
Вывести все циклические сдвиги строки s, например:
ship
hips
ipsh
pshi

(Задание на 5+) Среди всех циклических сдвигов строки s найти наименьший (в примере: hips).

Все задания можно сделать в одной программе: пользователь вводит одну строку,
а программа выдает подряд ответы на вышеперечисленные задания.
Сделанную программу прислать по эл. почте М. Э.

Вложенные циклы

1) Доделать задание с урока:
Рассматривается процесс: текущее число делится пополам, если оно четное,
и умножается на три и увеличивается на единицу, если нечетное.
(Например, 3, 10, 5, 16, 8, 4, 2, 1, 4.)

Пользователь вводит два числа a и b, программа должна
для каждого натурального числа из диапазона от a до b вывести
количество действий, за которое из этого числа процесс доходит до цикла 4-2-1-4.

2) Пользователь вводит с клавиатуры число n.
Программа должна вывести на экран вот такой набор изображений (это просто пример для
n=5, программа же должна работать для произвольного n):

*****
*****
*****
*****
*****
(квадрат n*n)

.
/ \
/ \
/ \
/ \
("горка" высоты n)

*****
* *
* *
* *
*****
("полый" квадрат n*n)

***** *****
*\ * * /*
* \ * * / *
* \* */ *
***** *****
(именно так, два квадрата с диагоналями рядом по горизонтали, а не друг под другом)

*********************
* * * * * *
* * * * * *
* * * * * *
*********************
(это n квадратов n*n, у которых "слиплись" соседние стороны)

. . .
/ \ / \ /
/ \ / \ /
/ \ / \ /
. . .
(это ломаная, в которой n звеньев, а ее высота составляет n строчек)
(ваша программа должна работать и для четных, и для нечетных n)

И ещё 1 любая картинка на ваше усмотрение :)

Считайте, что пользователь вводит n не меньшее 3
(ну или разберите случаи 1 и 2 вручную, но это необязательное задание).

Сделанные программы прислать по эл. почте М. Э.

Применение бинарных операторов

1) Исследовать, как работают операторы деления ("/") и
остатка ("%"), если один или оба операнда — отрицательные.
Каков знак результата? Куда происходит округление?
Результатом выполнения этого задания является связный текст
на русском языке, в котором описывается работа этих операторов
при всех вариантах знаков операндов.

2) Напишите программу, в которой сначала объявляются и
инициализируются две целочисленные переменные:

int x = (некоторое целое число);
int y = (некоторое целое число);

А затем на экран выводятся на отдельных строчках
следующие данные:

Верно ли, что оба эти числа положительные.
Верно ли, что хотя бы одно из этих чисел — семерка.
Абсолютная величина (то есть модуль) числа x.
(*) (необязательный пункт) Квадрат гипотенузы прямоугольного треугольника с катетами x и y.
Верно ли, что у этих чисел совпадают последние цифры.
Предпоследняя цифра числа x.

Выполняя последние три пункта, можете считать, что
x и y — оба положительные.

Обязательно запустите вашу программу для нескольких различных пар
значений x и y, чтобы убедиться в правильности ее работы.

На эл. почту надо прислать и текст из пункта 1, и программу из пункта 2.
Желательно прислать одно письмо, в «теле» которого текст из
пункта 1, а во вложении — программа.

Объявление переменных, вывод на экран

1) Написать и прислать по эл. почте М. Э. программу, в которой:

объявлены по одной переменной каждого примитивного типа;
каждой из этой переменных присвоено некоторое значение;
значение каждой переменной (конечно, после объявления и присваивания) выводится на экран.

2) Заметим, что команда
System.out.println(1e3);
выводит на экран тысячу в «обычном» виде.
А вот команда
System.out.println(1e12);
выводит на экран триллион в «научном» виде.

Исследуйте, где же проходит граница — начиная с какой величины вещественные числа выводятся в «научном» виде.

Hello, World!

Установить Java Development Kit (JDK).
Установить Eclipse.
Написать программу .Hello, World!.
Запустить её, убедиться, что она сработала.

Электронная почта

(желательно) зарегистрировать адрес электронной почты, которым будет не стыдно пользоваться через 30 лет. Если ваш текущий адрес уже таков, ничего предпринимать не нужно.
Прислать Михаилу Эдуардовичу (mikhail.dvorkin@gmail.com) приветственное письмо, соблюдая при этом основы делового этикета.