Использование таблиц при решении задач |
Важнейшим моментом при решении задачи является способ сведения задачи к подзадачам. Но не менее важным вопросом является и способ построения решения исходной задачи из решений подзадач. Одним из наиболее эффективных таких способов является использование таблиц для запоминания результатов решения подзадач. Задача может быть формализована в виде функции, которая зависит от одного или нескольких аргументов. Если взять таблицу, у которой количество элементов равно количеству всех возможных различных наборов аргументов функции, то каждому набору аргументов может быть поставлен в соответствие элемент таблицы. Вычислив элементы таблицы (то есть, решив подзадачи), можно найти и решение исходной задачи. Одним из способов организации таблиц является такой подход, когда размерность таблицы определяется количеством аргументов у функции, соответствующей подзадаче. |
Пример 1. Для заданной последовательности чисел A[1..N] найти максимальную длину M подпоследовательности подряд идущих одинаковых элементов. Пусть L(i) - количество подряд идущих одинаковых элементов, стоящих в конце подпоследовательности A[1..i]. ДЛЯ A=[2,1,1,1,7,4,3,3,3,3,5,5,6,8,8], то L(4) = L([2,1,1,1]) = 3, L(8) = L([2,1,1,1,7,4,3,3]) =2. Идея решения задачи состоит в создании массива L, заполненного по следующему правилу: Если A[i+1] = A[i],то L[i+1]=L[i]+1, иначе L[i+1]=1 Ответ-максимальное L(i) (i = 1,2,…N) M= max(L[i]). |
Пример 2. Для заданной последовательности чисел A[1..N] найти длину M максимальной подпоследовательности элементов со строго возрастающими значениями в порядке возрастания индексов и напечатать эту последовательность B. Решение: Пусть L[i] - максимальное количество элементов, образующих строго возрастающую подпоследовательность в массиве A[1..i], причем элемент A[i] входит в нее и является последним в ней. Например, для заданного выше массива A имеем: L(4) = L([-3,0,5,2]) = 3, B = (-3, 0,2), L(5) = L([-3,0,5,2,4]) =4 B = (-3, 0, 2, 4). Очевидно, значение L[i] может быть либо равно L[i-1], если A[i] = A[i-1], либо на 1 больше одного из значений L[j] (j=1,2,…i-1), для которых A[i] > A[j].
Массив L будем заполнять по следующему правилу: |
maxL[i] (i = 1,2,…N) - ответ на 1 вопрос задачи Реализация 1 части программы: |
ЧАСТЬ2. Найдем последовательность B[L[K].],B[L[K]-1]…B[1] в обратном порядке: 1. B[L[K]] = A[k]. 2. Найдем предыдущий A[i] подпоследовательности из коньюнкции условий: i<k, L[i] = L[k]–1, A[i] <A[k], i – максимальное с такими свойствами массив B - ИСКОМЫЙ. |
Пример3. У исполнителя Утроитель две команды, которым присвоены номера: 1. прибавь 1 2. умножь на 3 Первая из них увеличивает число на экране на 1,вторая — утраивает его. Программа для Утроителя — это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20? Решение. Прежде всего отметим, что при выполнении любой из команд число увеличивается (не может уменьшаться). Начнем с простых случаев, с которых будем начинать вычисления. Понятно, что для числа 1 существует только одна программа — пустая, не содержащая ни одной команды. Для числа 2 есть тоже только одна программа, состоящая из команды сложения Если через KN обозначить количество разных программ для получения числа N из 1, то K1 = K2 = 1. Теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую KN с предыдущими элементами последовательности K1, K2, ..., KN, то есть с решениями таких же задач для меньших N. Если число N не делится на 3, то оно могло быть получено только последней операцией сложения, поэтому KN = KN–1. Если N делится на 3, то последней командой может быть как сложение, так и умножение. Поэтому нужно сложить KN–1 (количество программ с последней командой сложения) и KN//3 (количество программ с последней командой умножения). В итоге получаем: |
Остается заполнить таблицу для всех значений от 1 до N: |
ответ в данной задаче — 12. При составлении программы с полной таблицей нужно выделить в памяти целочисленный массив K, индексы которого изменяются от 1 до N, и заполнить его по приведенным выше формулам: |
K[1]:= 1; for i:= 2 to N do if i mod 3 = 0 then K[i]:= K[i-1] + K[i div 3] else K[i]:= K[i-1];
Ответом будет значение K[N]. |
Упражнения для самостоятельной работы Задача1 У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 1 2. умножь на 4 Напишите программу, которая вычисляет, сколько существует различных программ, преобразующих число 1 в число N, введенное с клавиатуры. Задача 2. Для заданной числовой последовательности A[1..N] найти максимальную длину такой подпоследовательности ее элементов, что каждый последующий элемент делится на предыдущий (N, A[i] < 100). Например, при N=6, A = [5, -3, 6, 6, 12, 10] искомая длина = 4. Задача3. В цистерне N литров молока. Есть бидоны объемом 1, 5 и 6 литров. Нужно разлить молоко в бидоны так, чтобы все бидоны были заполнены и количество используемых бидонов было минимальным. Задача4. Для последовательности чисел A[1..100] (|A[i]|<100) найти максимальную сумму подряд идущих элементов. Задача5 У исполнителя Калькулятор три команды, которым присвоены номера: 1. прибавь 1 2. умножь на 3 3. умножь на 4 Напишите программу, которая вычисляет, сколько существует различных программ, преобразующих число 1 в число N, введенное с клавиатуры. Задача6. На прямой дощечке вбиты гвоздики. Любые 2 гвоздя можно соединить ниточкой. Надо соединить некоторые пары гвоздиков так, что к каждому гвоздику привязана хотя бы 1 ниточка, а сумма длин всех нитей была минимальной.
|
Кошманов В.А. 10 «A» класс |
МБОУ СОШ №27 |
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
A[i] |
2 |
1 |
1 |
1 |
7 |
4 |
3 |
3 |
3 |
3 |
5 |
5 |
6 |
8 |
8 |
L[i] |
1 |
1 |
2 |
3 |
1 |
1 |
1 |
2 |
3 |
4 |
1 |
1 |
1 |
1 |
2 |
L[i] =
|
L[i-1], если A[i] = A[i-1], |
1+ L[j-1] (j=1,2,…i-1), где A[i] > A[j]. |
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
a |
-3 |
0 |
5 |
2 |
4 |
1 |
0 |
3 |
5 |
3 |
6 |
6 |
9 |
4 |
L |
1 |
2 |
3 |
3 |
4 |
3 |
2 |
3 |
4 |
3 |
4 |
4 |
5 |
4 |
I |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
A |
-3 |
0 |
5 |
2 |
4 |
1 |
0 |
3 |
5 |
3 |
6 |
6 |
9 |
4 |
L |
1 |
2 |
3 |
3 |
4 |
3 |
2 |
3 |
4 |
3 |
4 |
4 |
5 |
4 |
B |
-3 |
0 |
3 |
6 |
9 |
|
|
|
|
|
|
|
|
|
N |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
Kn |
1 |
1 |
2 |
2 |
2 |
3 |
3 |
3 |
5 |
5 |
5 |
7 |
7 |
7 |
9 |
9 |
9 |
12 |
12 |
12 |