Использование таблиц при решении задач

Важнейшим моментом при решении задачи является способ сведения задачи к подзадачам. Но не менее важным вопросом является и способ построения решения исходной задачи из решений подзадач. Одним из наиболее эффективных таких способов является использование таблиц для запоминания результатов решения подзадач.

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

Одним из способов организации таблиц является такой подход, когда размерность таблицы определяется количеством аргументов у функции, соответствующей подзадаче.

Пример 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 есть тоже только одна программа, состоящая из команды сложения

Если через K_N обозначить количество разных программ для получения числа N из 1, то K₁ = K₂ = 1.

Теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую K_N с предыдущими элементами последовательности K₁, K₂, ..., K_N, то есть с решениями таких же задач для меньших N.

Если число N не делится на 3, то оно могло быть получено только последней операцией сложения, поэтому K_N = K_N–1. Если N делится на 3, то последней командой может быть как сложение, так и умножение. Поэтому нужно сложить K_N–1 (количество программ с последней командой сложения) и K_N//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 
с углубленным изучением отдельных предметов