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

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

Вычгеом

Задачи B—F вот отсюда.

Методы глобальной оптимизации

Реализовать метод симуляции отжига. С помощью него соптимиризировать две задачи до как можно более хорошего результата:

Обход в ширину

Пробуем поверить в новый информатикс!.. Задачи A и B из этого набора.

Фракталы

Код с урока про кривую дракона.

Код с урока про видео «Жюлиа→Мандельброт».

Получившееся видео.

Черепашья графика

Напишите программу, которая получает строку из "L" и "R" и рисует ломаную, у которой звенья имеют равную длину, а повороты соответствуют символам из строки.

(*) Сложнее: научитесь генерировать строку, соответствующую поворотам в кривой Дракона n-го порядка (n вводится, например, с клавиатуры) и "скормите" её программе из предыдущего абзаца.

Алгоритм Краскала

Задать прямоугольник h×w, размеры прямоугольника задаются константами в коде или вводятся с клавиатуры. Каждой стенке между соседними клетками сопоставить случайное число, например:

-----------------
|       |       |
|      0.5      |
|       |       |
---0.2-----0.7---
|       |       |
|      0.6      |
|       |       |
-----------------

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

Д/з "Треугольник Серпинского"

Изучить два способа построения треугольника Серпинского на картинках ниже. Доказать себе, что в пределе получается одна и та же фигура. (Это может быть неочевидно! Ведь на всех конечных фазах в первом случае получается набор треугольников, а во втором случае — ломаная.)

Выбрать, какой из двух вариантов вы хотите реализовать. Написать код на любом языке прогаммирования, который генерирует svg-файл, в котором "нарисован" треугольник Серпинского n-го порядка, где n — число, например, считанное с клавиатуры.

Код присылайте на почту (электронную :)).

Вариант 1 с заполненными треугольниками

Вариант 2 с ломаной линией
(Сетка нужна только для наглядности, в вашем коде её выводить не требуется!)

Код, написанный на уроке.

Кривая Гильберта

Выведите кривую Гильберта n-го порядка, где n считывается с клавиатуры.

Д/з 2 для группы "Ъ"

Вот эти семь задач.

Видео 1 про разбор выражений

Видео 2 про разбор выражений

Под вопросом: видео про альтернативный подход

Д/3 1 для группы "Ь"

Пользователь вводит число n, нарисовать звёздочками кривую Пеано n-го порядка.

Д/3 1 для группы "Ъ"

Вот эти шесть задач.

Разбираем чужие комментарии

HTML-код, чтоб не скачивать самим, ну или собственно вот.
Ключевые слова: requests и возможно beautifulsoup для Python, jsoup для Java.

Очень здорово, если ваш код достаточно обобщённый и сразу сработает для такой же записи про 2019 год

Задачи на массивы — задачи от A до E из этого набора.

Задачи на циклы — задачи от A до G из этого набора.

Первая программа на Java

0) Установить Java Development Kit (JDK) и либо Eclipse, либо IDEA.

1) Создать проект, создать класс с методом main, в методе main написать вывод на экран надписи "Hello, world!". Запустить эту программу, убедиться, что она сработала.

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

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

Архив: 9-й класс

Задачи на выигрышные и проигрышные позиции.

Динамическое программирование. Задачи A—G отсюда и A—F отсюда.

Работа в классе, 10 апреля.

(Код с доски: свой куки-кликер под Heroku.)

Свой простенький сервер

(Код с доски: свой HTTP-сервер.)

Запустить на своем комьютере http-сервер, см. код выше. Убедиться, что вы на него можете зайти в браузере по адресу 127.0.0.1:3333 . Изменить его код так, чтобы он стал url-калькутятором, а именно: при посещении страницы 127.0.0.1:3333/5+6+6 сервер выдает html-страничку с ответом "17", и так для любого примера со сложением.

(Хозяйке на заметку: посмотрите как работает команда 'tratata'.split('a'), вызов split с параметром вам пригодится.)

Получение данных по API

На странице Codeforces API найти метод, выдающий изменения рейтинга после контеста. Написать программу на питоне, используя модуль requests, которая по данному индентификатору контеста выводит список всех участников, рейтинг которых поднялся на этом контесте на 100 и более единиц.

«Бродилка по лабиринту»

Код с доски

Пользователь видит "героя" (можно кружочек, а лучше стилизованного человечка или изображение) и выход в противоположном углу поля. Ваша игра "мысленно загадала" лабиринт, но не показывает его пользователю. Пользователь пытается делать ходы вверх-вниз-вправо-влево, они срабатывают, только если там нет стенки. Обязательно надо запретить пользователю выходить за пределы поля.

Инвертирование крестиков

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

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

Статическая картинка в Tkinter

Создайте приложение в Tkinter, которое отображает статический цветной циферблат: 12 надписей (Label), расположенных по кругу, как это принято в часах, цвета которых плавно (!) переходят от, например, красного к синему (1 час - красная, 2 часа - чуть-чуть синеватая красная и т. д., 12 часов - синяя). Любой другой аналогичный дизайн поощряется.

Работа в классе и дома «Объект по номеру и обратно»

Все четыре задачи отсюда.

Работа в классе и дома «Рекурсивная генерация объектов»

Задачи отсюда, любые 8 штук.

Д/з «Двоичный поиск»

Задачи C+D отсюда и задачи A+E+F отсюда.

Набор задач "Быстрые сортировки"

(не в информатикс) Дан массив чисел, вывести число инверсий в нем. Программа должна работать за O(n log n), а именно сортировка слиянием + учет инверский.
Сдать сюда быструю сортировку.
Задачи A-D отсюда.

Работа в классе: квадратичные сортировки

Как можно больше задач отсюда

Обмен через xor

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

a = a ^ b
b = a ^ b
a = a ^ b

Архив: 8-й класс

Отсюда задачи номер ABDGIO...

Используя заготовку, сделанную на уроке на доске, решите задачи от A до E про Ханойские башни.

Текущее задание к 21 апреля: из этого же блока (ссылка чуть ниже) решить всё до R, но "субботней" группе можно без Q.

Задание на функции, решаем A-J.

Бонусный уровень.

Архивное

Задание на алг. Евклида.

Задание в классе для субботней группы на 10-е февраля

Задания A-J про двумерные массивы

Текущие задания, январь

Задачи A-L отсюда.

И этот набор задач.

Работа в классе, 12.01.18

задание в классе, H-N

бонус

Работа в классе, 18.12.17

Вот из этого набора надо решить задачи от M до U. Если задача уже вами сдана (в д/з), то вам повезло. Антон Михайлович расскажет, как пользоваться школьными компьютерами. Количество штрафных попыток не учитывается, но не надо этим злоупотреблять.

Условный оператор

Важно: если вы не видите себя в табличке "ФТШ, 2021а", сообщите свой id на адрес mikhail.dvorkin@gmail.com. Чтобы узнать свой id, нужно (на сайте informatics) нажать сверху на свои имя-фамилию, после чего в адресной строке браузера найти надпись вроде id=123123.

Вот этот набор задач, надо решить: A, D, F, G, J, L, M, O.

Первые задачи на informatics

Зарегистрироваться на informatics.mccme.ru, если вы этого ещё никогда не делали. Указать настоящие фамилию, имя, класс, школу (желательное написание: "Лицей ФТШ").

Выучить свой логин и пароль!

Зайти на страницу: http://informatics.mccme.ru/mod/statements/view.php?id=3309#1

Слева снизу есть список задач. Вам нужно решить и сдать до состояния "ОК" задачи: A, B, C, D, E, I, J, S.

Работа с переменными

В переменные x и y присвойте целые числа. Затем выведите про них:

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

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

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

Домашнее задание "Знакомство с Python"

Установить к себе на компьютер Python 3.
Запустить интерактивный режим, убедиться, что у вас рабоает вычисление 2**100.
(Желательно) установить к себе на компьютер Wing IDE 101, убедиться, что вы в нем можете написать и запустить программу, выводящую на экран "Hello, world!".
(Желательно) написать в блокноте или любом обычном текстовом редакторе программу, выводящую "Hello, world!" и суметь её запустить в командной строке. (Ключевые слова: cmd, cd название_папки, python название_файла; можно и нужно всё это "гуглить")

Домашнее задание в тетради "Хранение целых чисел"

Процессор 8-битного компьютера (например, старой игровой приставки Денди) может хранить целые числа в диапазоне от -128 до 127 (каждое число хранится в 8 битах).

Какой результат получится, если к числу 112 прибавить 36? Произведите сложение «в столбик».
Какой результат получится, если возвести 17 в квадрат? Произведите умножение «в столбик».
Какой результат получится, если вычесть из -80 число 62? Получите ответ любым способом.
Какой результат получится, если умножить -80 на 4? Получите ответ любым способом.

Домашнее задание на листочке "Системы счисления"

Переведите 1011011 из двоичной системы счисления в десятеричную.
Переведите CF из 16-чной системы счисления в десятеричную.
Переведите 194 из 18-чной системы счисления в десятеричную.
Переведите 183 из десятичной системы счисления в двоичную.
Переведите 330 из десятичной системы счисления в шестеричную.
Упорядочите по возрастанию числа 500₉, 23A₁₄, 12221₄, 122010₃, 611₉.