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

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

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

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

Пример 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]).

Text Box: program pr1;
       const a:array[1..15] of integer=(2,1,1,1,7,4,3,3,3,3,5,5,6,8,8);
       var L:array[1..15] of integer; I,MAX:INTEGER;
begin  L[1]:=1;          FOR I:=2 TO 15 DO  IF A[I-1]=A[I] THEN L[I]:=L[I-1]+1 ELSE L[I]:=1;
           MAX:=1;  	For  i:=2 to 15 do       if L[i]>L[MAX]  then        MAX:=i;
           writeln(L[MAX]);
end.

Пример 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 части программы:

Text Box: const n=14;a:array[1..n] of integer=(-3,0,5,2,4,1,0,3,5,3,6,6,9,4);
var L,B:array[1..n] of integer; I,J,MAX,K:INTEGER;
begin L[1]:=1;
FOR I:=2 TO n DO
  IF A[I]=A[I-1] THEN L[I]:=L[I-1]
	 ELSE  FOR J:=1 TO I-1 DO  IF A[J]<A[I] THEN  L[I]:=L[J]+1 ;
         
   K:=1; For  i:=1 to n do   if L[i]>L[K]  then  K:=i;
writeln(L[K]);
READLN;
end.

ЧАСТЬ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 - ИСКОМЫЙ.

Text Box: I:=L[K];
   B[L[K]]:=A[K];
   MAX:=L[K]; MAX:=MAX-1;
    WHILE MAX<>0  DO
    BEGIN
    K:=K-1;
    IF ( L[K]=MAX) and(a[k]<b[max+1]) THEN BEGIN B[MAX]:=A[K];MAX:=MAX-1 END;
    END;
    FOR K:=1 TO I DO     WRITE(B[K]:5);

Пример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

(количество программ с последней командой умножения). В итоге получаем:

Text Box: если N не делится на 3: KN = KN–1;
если N делится на 3: KN = 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].

Text Box: program Project1;
var k:array of integer; N,n1,i:integer;
 begin   readln(n); setlength(k,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];
 writeln(k[n]);    readln;
end.

Упражнения для самостоятельной работы

Задача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