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

Работа в классе: задачи AEGILONP.

Бонус (для Никиты и желающих): Паззл с убиранием одинаковых цветов.

Критерий Поста

Те, кто не слушал рассказ про критерий Поста, почитайте о нём тут или тут.

Затем надо написать программу, которая считывает
а) восемь ноликов/единичек - таблицу истинности функции от трёх переменных;
б) число n, а затем 2n ноликов/единичек - таблицу истинности функции от n переменных.

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

Присылать в конце урока М. Э. на почту, либо приносить через неделю на урок.

Генетические алгоритмы

Генетическими алгоритмами расставить на доске 10×10 как можно больше кентавров (фигура, которая ходит как король или конь) так, чтобы они не били друг друга.

Для справки: текст-1, текст-2.

Метод отжига

Задача о ферзях

Задача коммивояжера

Для справки: текст-1, текст-2.

Задание "оптимизируем ассемблерный код"

Чему будет равно значение в переменной h после выполнения программы?

set a 1
set b 67
set c b
jnz a 2
jnz 1 5
mul b 100
sub b -100000
set c b
sub c -17000
set f 1
set d 2
set e 2
set g d
mul g e
sub g b
jnz g 2
set f 0
sub e -1
set g e
sub g b
jnz g -8
sub d -1
set g d
sub g b
jnz g -13
jnz f 2
sub h -1
set g b
sub g c
jnz g 2
jnz 1 3
sub b -17
jnz 1 -23

Опциональное участие в марафон-матче

Условия марафон-матча. Визуализатор.

Задание "Идентикон"

Разобраться с форматом svg (например, посмотрив примеры, набрав в поисковике "svg tutorial"). Написать метод genIdenticon(size, string), который возвращает строчку с svg-кодом уникального идентикона для строки string. В методе main вывести страницу .html, на которой расположить 100 ваших идентиконов для строк "0".."99".

Задание "Японский кроссворд"

Дана картинка в формате PBM (google it), вывести документ в LaTeX, который после компиляции будет выглядеть как бланк для японского кроссворда, ответом на который является эта картинка.

Проект «Криптосистема Меркла—Хеллмана»

Пример работы с BitSet.

Реализовать три описанных ниже метода для полноценной работы криптосистемы Меркла—Хеллмана. Предлагаемое число передаваемых бит n (и, соответственно, длина сверхвозрастающей последовательности): нескольно сотен. Число бит (цифр в двоичной записи) в числах последовательности: примерно от n до 2n.

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

encrypt(message, publicKey): Зашифровать данное сообщение открытым ключом.

decrypt(message, privateKey): Расшифровать данное сообщение закрытым ключом.

Работа в классе, 12 сентября

Расширенный алгоритм Евклида + задачи.

Сервер игры в виселицу, краткое описание

Реализовать модель игры в виселицу (Model из шаблона Model-View-Control). Она хранит:

У нее должны быть методы:

Реализовать перевод ее в Entity и обратно, например:

Реализовать сервлет, который принимает get-запросы типа "id=123" и "id=123&move=a" и делает следующее:

Datastore example
NimModel
NimConsoleView
NimController
StringUtils
TestStringUtils

Сайт в Google App Engine

Создайте проект в Google App Engine: https://console.cloud.google.com/home/dashboard

Залогиньтесь в ваш google-аккаунт в Eclipse. Создайте проект в Eclipse (new Google Project), укажите id проекта, созданного на предыдущем шаге. Похоже, меньше проблем возникает, если делать именно в этом порядке.

Теперь, собственно, задания.

1) В your_site.appspot.com/homework1.html должна лежать любая корректная html-страница, в которой использованы любые три новые тега, которых нет в созданном за вас index.html и которые не обсуждались на уроке (найдите что угодно в интернете).

2) Страница your_site.appspot.com/homework1 (без html) должна быть не статической, а генерироваться Java-кодом (вперед вручную править web.xml). Выведите посетителю в text- или html-виде текущую дату и время, желательно в приятном человеко-читаемом виде, а также случайное число от 0 до 999.

3) В your_site.appspot.com/homework2.html должна лежать форма, в которой есть текстовое поле, "чекбокс" и несколько "радиобаттонов", из которых можно выбрать только один (как обычно. Выясните, как это сделать средставами html). При отправке формы посетитель попадает на your_site.appspot.com/homework2 и видит результат обработки его запроса. Текст из текстого поля переводится в ВЕРХНИЙ РЕГИСТР, нижний регистр или Смешанный Регистр в зависимости от выбора "радиобаттона". Если же была поставлена галочка в "чекбоксе", то все последовательности из более чем одного пробела заменяются на один пробел ("a    b" -> "a b")

Пришлите М. Э. просто ссылку на your_site.appspot.com.

Обращение к API

1) Пользователь вводит id (или screenname) пользователя VK.

Ваша программа обращается к VK API и выдает на экран фамилию пользователя с этим id (или screenname).

Например, 7373 -> Dvorkin, rezniko -> Reznik.

2) Пользователь вводит id (или screenname) пользователя VK и строку s.

Ваша программа обращается к VK API и выдает на экран имена и фамилии друзей пользователя с этим id (или screenname), фамилии которых начинаются на s. Но если таковых больше 5, то выводит только 5 из них (любых).

Например, 7373 Rez -> Ivan Reznik, Yury Reznik, Denis Reznichenko.

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

Например, 7373 Korotk -> Maxim Korotkov NO, Anton Korotkov NO, Fyodor Korotkov NO, Gennady Korotkevich YES.

4) В вашем домашнем Eclipse убедитесь, что вы скачали следующие дополнения (с одного и того же сайта дополнений):

Забираем данные из интернета

1) Научитесь забирать данные со стороннего сервера данные html-страницы.

(Сделать URL, открыть у него openConnection, взять у соединения inputStream, обернуть в какой-нибудь читатель — Scanner или BufferedReader, считать всё в строку или поумнее в StringBuilder. Это гуглится, "java http get".)

Напишите программу, которая считывает с клавиатуры имя человека на английском языке (например, "Albert Einstein"), формирует url статьи в англоязычной Википедии про этого человека, подключается к Википедии, забирает содержимое этой статьи, и выводит все четырехзначные числа, которые присутствуют в статье. (Ожидается получить годы, важные в биографии этого человека, но куча посторонних чисел тоже будет встречаться.)

2) Скачайте и установите Google Plugin for Eclipse.

Массив ArrayList'ов

Работа в классе, 29 сентября

Ссылка на задачи.

Движение частиц

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

Бонус: добавить силу гравитации между частицами (притягивание каждой пары друг к другу).

Игра «Жизнь»

Реализовать игру жизнь с заданием начального положения мышкой и демострацией новых поколений по таймеру.

Часть 2а. Сделать меню в этом апплете, в котором расположить кнопки: старт, пауза, перезаплнить поле случайным образом, очистить поле.

Часть 2б. Рисовать живые клетки так: если в папке есть файл cell.png, то брать изображение из него, иначе рисовать как раньше.

Пример с перерисовыванием панели

Передвижение нарисованного объекта

На апплете две панели, в одной из них кнопки управления вверх/вниз/влево/вправо, в другой — нарисованный круг, двигающийся при нажатии кнопок.

Гонки

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

Тренажер клавиатуры.

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

Игра с угадыванием числа.

Программа загадывает число от 0 до 1000. Пользователь вводит в текстовое поле свою версию. По нажатию на кнопку или нажатию Enter проверяется версия пользователя и сообщается, она больше, меньше или равна загаданному числу. Если в текстовое поле введено не число, то программа должна не сломаться, а выдать содержательное сообщение. Если пользователь угадал, его следует поздравить.

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

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

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

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

Действия на кнопках

Создайте апплет, в котором изначально присутствуют две кнопки.

По нажатию первой из них: у второй кнопки изменяется надпись, а на апплет добавляется JLabel.

По нажатию второй из них: первая кнопка пропадает (становится невидимой), на апплет добавляется новая кнопка "Exit".

По нажатию кнопки "Exit", программа завершает работу.

При этом на первую и вторую кнопку в качестве ActionListener должен быть добавлен this, а на кнопку "Exit" — объект анонимного класса.

Кстати, если нажимать на вторую кнопку много раз, то кнопок "Exit" должно появиться много, и каждая из них должна работать.

Код присылать куда-либо не нужно, а нужно иметь его на уроке.

Апплеты

Создайте и запустите самодельный апплет. На него должны быть добавлены две панели, на каждую из которых добавлены кнопка и любой другой элемент. Должны быть использованы BorderLayout для всего апплета, и FlowLayout для панелей. Код присылать куда-либо не нужно, а нужно иметь его на уроке.

Дополнительный двоичный код

Чтобы перевести отрицательое число (например, -9) в доп. двоичный код, работает следующая процедура:

Доказать, что эта процедура верна. Устно/в тетрадке, сдавать на листочке не надо.

Частотный анализ текста

Подсчитать слова в файле: Ромео и Джульетта.

Стек, очередь, дек — задание в классе и дома

Задачи A, B, D, E, G, H отсюда, а также задачи C, D отсюда.

Парочка алгоритмов

Реализовать алгоритмы:

  1. Шейкерная сортировка;
  2. Перетасовка массива.

Убедиться в корректности первого, сдав его как решение задачи (например, B из прошлого д/з) на informatics. После чего послать обе программы по почте М. Э.

Квадратичные сортировки

Реализовать три метода сортировки массива:

Каждая из них должна быть оформлена как метод вида: void название(int[] a)

После чего сдать задачи B, D и E вот сюда.

То есть в каждую из этих задач надо послать файл, в котором в методе main происходит чтение массива, затем вызывается нужная из трёх сортировок и выводится на экран ответ.

Кстати, если вам в сортировке выбором больше нравится выбирать на каждом шаге минимум, а не максимум, делайте так на здоровье!

Рекурсия

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

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

(В численных задачах можете считать, что входные данные — натуральные числа до миллиарда, и ответ тоже не превышает миллиарда.)

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

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

Программу из задания 1 и текст из задания 2 прислать одним письмом по почте М. Э.

Методы

В одном файле, в одном классе:

  1. Напишите метод int max(int a, int b), возвращающий максимум из двух чисел.
  2. Используя метод max из предыдущего задания, напишите метод, возвращающий максимум из трех чисел.
  3. Напишите метод, возвращающий минимум из трех чисел.
  4. Используя методы из предыдущих двух заданий, напишите метод, возвращающий медиану из трех чисел (медиана — то, которое не минимум и не максимум).
  5. Напишите метод int max(int[] a), возвращающий максимум в одномерном массиве целых чисел.
  6. Используя метод из предыдущего задания, напишите метод, возвращающий максимум в двумерном массиве целых чисел.

Прислать на почту М. Э.

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

Хозяйке на заметку: символ "\" можно вывести командой System.out.print("\\");

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

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

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

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

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

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

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

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

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

Сделанную программу (одну, выводящую сразу все картинки!) прислать по эл. почте М. Э.

Ввод данных с клавиатуры и циклы while и do-while

1) Напишите программу, которая вначале спрашивает у пользователя натуральное число n, а затем производит следующую операцию над числом n:

Эта операция производится много-много раз, и каждое очередное полученное число выводится на экран. Остановиться следует после получения единицы.

(Например, из семёрки получится последовательно: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1)

2) Верно ли, что начиная с любого n от 2 до 5000, эта операция приведёт к получению единицы? Проверьте это вручную, вводя в программу из пункта 1 все натуральные числа от 2 до 5000. Шутка! Наоборот, напишите программу, которая сама проверяет, верно ли это утверждение.

Результатом работы этой программы должен стать следующий текст, выведенный ею на экран:

Starting from 2: received 1 after 1 operation.
Starting from 3: received 1 after 7 operations.
Starting from 4: received 1 after 2 operations.
Starting from 5: received 1 after 5 operations.
(и так далее)

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

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

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

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

  1. Верно ли, что оба эти числа положительные.
  2. Верно ли, что хотя бы одно из этих чисел — семерка.
  3. Абсолютная величина (то есть модуль) числа x.
  4. Максимум из них.
  5. Сколько среди этих двух чисел четных.
  6. Среднее арифметическое этих двух чисел, причём в случае, если оно нецелое, то округленное вверх (!).
  7. Верно ли, что одно из этих чисел — куб другого числа.
  8. Квадрат гипотенузы прямоугольного треугольника с катетами x и y.
  9. Верно ли, что у этих чисел совпадают последние цифры.
  10. Предпоследняя цифра числа x.

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

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

Написанную программу прислать по почте М. Э.

Установка JDK и Eclipse, написание первой программы

  1. Установить JDK и Eclipse;
  2. Написать и запустить программу, выводящую на экран (в консоль) надпись "Hello, world!";
  3. Если всё получилось, присылать по почте ничего не надо. Если возникли проблемы, прислать по почте описание проблем.

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

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