Статичное и динамичное программирование
НАВИГАЦИЯ ПО СТРАНИЦЕ
легко понять и запомнить
Попробуем разобраться в принципиальных отличиях этих двух направлений:
Статичное программирование | Динамическое программирование |
|---|---|
В статике мы собираем статистику о какой-либо последовательности (наборе данных) и одной командой получаем ответ на поставленную задачу. ГЛАВНОЕ: Мы получаем ответ на основании полученной информации о всей последовательности. | В динамических решениях мы постепенно находим элементы ответа (по ходу решая промежуточные задачи), и итоговый ответ будет являться совокупностью найденных ранее. Мы не анализируем всю последовательность (набор данных) целиком, мы собираем данные о последовательности постепенно, в каждый момент времени, для каждого нового ее элемента. Динамическое программирование собирает статистические данные последовательно по шагам. |
Задача 1. Определи количество пар, произведение элементов которых, делится на 7 без остатка. Используй файлы 1A и 1B.txt
Рассмотрим только программный метод.
Способ 1 | Способ 2 | Способ 3 |
|---|---|---|
 |  |  |
Способ 4.
 | Обрати внимание:
С каждым получением из файла нового числа последовательности мы анализируем: «Сколько с этим числом будет пар, произведение которых, кратно 7?» |
Задача 2. Определи количество пар, произведение элементов которых, делится на 28 без остатка. Используй файлы 2A и 2B.txt
Задача 3. Имеется ряд из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найди среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажи количество элементов самой короткой из них.
Описание: Входные данные: Даны два входных файла: файл A (3A.txt) и файл B (3B.txt), каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 108). Каждая из следующих N строк содержит натуральное число, не превышающее 10000.
Пример входного файла:
7
21
13
9
19
17
26
95
В этом наборе можно выбрать последовательности 21+13+9 (сумма 43) и 17+26 (сумма 43). Самая короткая из них, 17 + 26, имеет длину 2. Ответ: 2.
В ответе укажи два числа: сначала значение искомой суммы для файла А, затем для файла B.
Неэффективный алгоритм
Эффективный алгоритм
Нам понадобятся знания из математики: если два числа кратны 43, то разность двух данных чисел также будет кратна 43.
Задача 4. Дан набор целых чисел. Найти среди них количество пар, сумма которых кратна 43. Для решения задачи воспользуйся файлами 4A.txt и 4B.txt. В ответе запиши 2 числа: количество пар для файла 4A.txt и 4B.txt.
