Грязные трюки: кеширование

• Разбор задач.
• Понятие кеша. Снижение вычислительной сложности при введении кеша

• Разбор работы кеширующей функции на примере «задачи о распиле брёвен»

• Связь задач, оптимизируемых с помощью кеша, и динамического программирования

Домашнее задание

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

1. Почитать о кешировании в Википедии. Какое отношение это может иметь к решению сложных задач?

2. MCCME Прямоугольники. Дан прямоугольник N×M, состоящий из квадратиков 1 ´ 1. Некоторые квадратики вырезали. Надо найти наименьшее количество прямоугольников, на которое можно разрезать оставшуюся фигуру.

   • Формат входных данных. В первой строке входных данных заданы числа N и M, (1 ≤ N, M ≤ 10). Далее следует N строк. В (i+1)-ой содержится M чисел; j-е число равно 1, если клетку на i-й строке и в j-м столбце вырезали из доски, 0 – если оставили.

     Формат выходных данных. Выведите единственное число – минимальное количество прямоугольников, на которое можно разрезать полученную фигуру.

3. MCCME. Пилообразные последовательности. Назовем последовательность пилообразной, если каждый ее элемент либо строго больше, либо строго меньше своих соседей. По данными числам n и k определите число пилообразных последовательностей длины n, составленных из чисел 1..k. Программа получает на вход два натуральных числа n и k, не превосходящих 10⁶.

Условные обозначения

• — тема по Linux

• ­— тема повышенной сложности

• — теоретическое задание

• — тема для самостоятельного изучения

CategoryClass CategoryVmsh