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

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

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

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

Задачи 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. Перевести в десятичную систему:
    а) 110101102;
    б) 5667;
    в) BE416.
  2. Перевести из десятичной системы:
    а) 200 в 3-чную;
    б) 89 в 4-чную;
    в) 497 в 16-чную.
  3. Перевести в шестнадцатеричную систему:
    а) 1011011012;
    б) 320014;
    в) 710258.
  4. Сколько цифр в:
    а) 2-чной записи числа 1768?
    б) 16-чной записи числа 4321?
  5. В системе счисления с каким наименьшим основанием:
    а) 9110 заканчивается на 0?
    б) 56610 содержит четыре цифры?
    в) 29910 содержит три цифры и начинается на 4?

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

  1. Построить таблицу истинности для следующей функции:
    f(a, b, c) = (¬a ∨ (b ∧ ¬c)) ∧ ¬(a ∨ b)
  2. Найти булеву формулу, описывающую функцию f(a, b, c) с данной таблицей истинности:
    abc f(a, b, c)
    0000
    0011
    0101
    0111
    1000
    1010
    1101
    1110
  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)