Относительно универсальное решение задач 19—21.

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

Дана картинка в формате PBM (формальное описание этого формата легко найти в интернете).

Пара примеров для удобства приведена ниже.

Требуется написать программу на любом языке программирования, которая читает эту картинку (лучше из файла, хуже — с клавиатуры), и выводит (лучше в файл) корректный документ на языке LaTeX, который после компиляции будет выглядеть как бланк для японского кроссворда, ответом на который является эта картинка.

Изучите, как принято рисовать бланки для японских кроссвордов. Горизонтальные группы желательно выровнять по правому краю, вертикальные — по нижнему, каждую пятую горизонталь и вертикаль — сделать более толстой.

P1
5 10
0 0 0 1 1
0 0 0 1 1
1 1 0 1 1
1 1 0 1 1
0 0 0 1 1
0 0 0 1 1
0 0 0 1 1
1 0 0 1 1
1 1 1 1 1
0 1 1 1 0

P1
30 40
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 0 0
0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 0 1 1 0 0
0 0 1 1 0 0 0 0 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 0
0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0
1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 1 1 1 1 1 0 1 1 0 0 0 1 1
0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0
0 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 1 0
0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0
0 0 0 1 1 0 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Про стек

Запускаться с большим стеком, если нет возможности передать виртуальной машине параметр -Xss10M:

fun main() = Thread(null, { solve() }, "", 10_000_000).start()

Обход в глубину

Задачи A—E вот отсюда.

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

Задачи A—C вот отсюда.

Хранение графов

Задачи A—M вот отсюда.

Сложная задача на графы (Лёне и очень желающим) и ещё одна попроще.

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

Техническое задание.

Описание криптосистемы, если вас не было на уроке, можно найти в Википедии.

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

Ваша программа должна работать в трёх режимах. Режим задаётся, например, вводом пользователя в начале работы программы.

1) Режим генерации ключей. Программа создает новый открытый и закрытый ключ, кладя их в файлы public.txt и private.txt. Продумайте, как этот метод будет получать «зерно» (randseed) для генератора псевдослучайных чисел и в каком формате будет выдавать ключи.

2) Режим шифрования. Программа читает файл message.txt, состоящий из нулей и единиц, и используя файл public.txt шифрует это сообщение, выводя результат в файл encrypted.txt. Можно считать, что в файле message.txt количество нулей и единиц не превышает n. Если их строго меньше n, можно дополнить сообщение нулями до длины n, или сделать что-то более умное.

3) Режим расшифровки. Программа расшифровывает файл encrypted.txt, используя файл private.txt, и полученное сообщение из нулей и единиц выводися в файл decrypted.txt.

Присылать код программы на почту mikhail.dvorkin@gmail.com

Дин. прог.

Сначала задачи A—F.

Решатель японских кроссвордов

Черновик от 16 января.

«Ещё немного комбинаторных объектов»

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

Немаленькое задание «Генерация комбинаторных объектов»

Вот из этого набора задачи от А до F и от H до J.

Домашнее задание на листочке «Хранение целых чисел»

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

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

Устанавливаем среду разработки IDEA

Установить IntelliJ IDEA Community Edition. Создать новый проект вида Kotlin/JVM или Kotlin > Console Application. Написать первую программу и запустить её:

fun main() {
	print("Hello, world!")
}

Вот тут пошаговая инструкция, но на английском.

Регулярные выражения: кроссворд

То, что сделали вместе на уроке.
Удобный сайт для решения онлайн.
Пустышка для тех, у кого есть принтер.
Сдавать скриншоты или фотки М. Э. в какой-нибудь соцсети или по почте.

Алгоритм Кнута—Морриса—Пратта

Задачи D, B и G (советую в таком порядке) из из этого набора.

Полиномиальное хеширование

Код с урока.

Задачи B, C и D из этого набора. Будьте готовы к тайм лимитам, поставленным довольно впритык.

Дерево отрезков

Все пять задач из этого набора.

Необычное задание про «ассемблер»

(Задание не обязательное, но желательное: оценка только 5 тем, кто выполнит.)
Что выведет вот эта программа?

В ней: set это присвоить ("set a 5" это "a = 5"), sub это вычесть ("sub a 5" это "a -= 5"), mul это умножить ("mul a 5" это "a *= 5"), jnz это jump if not zero на столько-то шагов вперёд. Например, "jnz a 2" это "если a не ноль, то пропусти следующую строку" (перейди на строку +2 от текущей). А, например, "jnz a 1" это бессмысленная команда (и в случае нуля, и в случае не нуля произойдёт переход на следующую строку).

Словари

Задачи L—Q из этого набора.

Стеки-очереди-деки. Задание от Толика Анищенко!

Задачи A—F отсюда, а кто решит H-I-J, тот совсем молодец.

Последнее задание 2010-х!

Advent of code, день 14.

Двоичный поиск

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

Корзинная сортировка

Реализуйте корзинную сортировку. Ваша программа должна считывать массив вещественных чисел, про который известно, что он состоит из равномерно распределённых случайных чисел в интервале [0, 1); сортировать его корзинной сортировкой и выводить на экран. Код пришлите по эл. почте: mikhail.dvorkin@gmail.com

Сортировка подсчётом

Задачи A, C, D (и опционально, бонусно, задача B) вот отсюда.

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

Задачи A—D вот отсюда.

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

Задачи A—H без F.

Д/з про ханойские башни.

__Бонусное__ (только для тех, кто сделал всё предыдущее) задание.

Задачи A—L отсюда = работа в классе 12 апреля. (В космос с функциями!)

Работа в классе, 15 марта.

Работа в классе, 1 марта.

Списки списков, они же двумерные массивы

Задачи от A до J отсюда.

Не очень легко дается считывание прямоугольной таблицы чисел? Попробуйте следущий код, для начала как "магию", а потом мы очень подробно разберём все его составляющие:

height, width = map(int, input().split())
a = [list(map(int, input().split())) for i in range(height)]

Теория чисел

Набор задач к 15-му февраля (предлагается его решать после занятия 8-го, но не воспрещается и заранее...)

Списки

Во-первых, вам надо узнать "магическую" строчку, позволяющую считать массив, данный в одной строке через пробел:

a = list(map(int, input().split()))

Протестируйте ее, проверьте, как она работает. Теперь решите задачи A—H вот отсюда.

Работа в классе на последней неделе декабря

Ребята, не болейте (вот у меня не получилось)! В классе вам предлагается решить задачи от B до H из этого набора.

Цикл for

Задачи T-Z отсюда, кроме W.

Осваиваем систему informatics

5 любых задач отсюда (и большое уважение тем, кто уже решил намного-намного больше!): условный оператор.
И 5 любых задач отсюда: циклы.

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

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

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

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

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

Д/з Знакомство с Python

Установить у себя на компьютере Python 3.

Д/з про системы счисления

1. Перевести в десятичную систему:
   а) 11010110₂;
   б) 566₇;
   в) BE4₁₆.
2. Перевести из десятичной системы:
   а) 200 в 3-чную;
   б) 89 в 4-чную;
   в) 497 в 16-чную.
3. Перевести в шестнадцатеричную систему:
   а) 101101101₂;
   б) 32001₄;
   в) 71025₈.
4. Сколько цифр в:
   а) 2-чной записи числа 1768?
   б) 16-чной записи числа 4321?
5. В системе счисления с каким наименьшим основанием:
   а) 91₁₀ заканчивается на 0?
   б) 566₁₀ содержит четыре цифры?
   в) 299₁₀ содержит три цифры и начинается на 4?

Д/з про булеву логику

1. Построить таблицу истинности для следующей функции:
   f(a, b, c) = (¬a ∨ (b ∧ ¬c)) ∧ ¬(a ∨ b)
2. Найти булеву формулу, описывающую функцию f(a, b, c) с данной таблицей истинности:
   

   a	b	c	f(a, b, c)
   0	0	0	0
   0	0	1	1
   0	1	0	1
   0	1	1	1
   1	0	0	0
   1	0	1	0
   1	1	0	1
   1	1	1	0

3. Перечислите все целые X, для которых истинно высказывание ¬((X>2) → (X>3)).
4. Каково наибольшее целое число X, при котором истинно высказывание (50 < X * X) → (50> (X+1) * (X+1))?
5. Какое из приведенных имен удовлетворяет логическому условию:
   ¬(последняя буква гласная → первая буква согласная) ^ вторая буква согласная
   1) ИРИНА 2) АРТЕМ 3) СТЕПАН 4) МАРИЯ
6. Дан фрагмент таблицы истинности выражения F:

   	x1	x2	x3	x4	x5	x6	F
   	0	1	1	1	1	0	1
   	0	0	1	1	1	0	1
   	0	1	0	1	0	1	1
   

   Каким выражением может быть F?
   1) (x1 v x2) ^ (x3 v x4) ^ (x5 v x6)
   2) (x1 v x4) ^ (x2 v x5) ^ (x3 v x6)
   3) (x1 v x6) ^ (x2 v x3) ^ (x4 v x5)
   4) (x1 v x3) ^ (x2 v x6) ^ (x3 v x5)

 

официальная информация • контакты • © 2003–2024 • ФТШ • Виктор Кропп