Динамическо епрограммирование и рекуррентные соотношения (стр. 2 )

T[0, 0]: = 0

нц для j от 1 до 16

½ T[0, j] = 0

кц

нц для i от 1 до 5 (4. 9)

½ T[i, 0] = 0

кц

нц для i от 1 до 5

½ нц для j от 1 до 16

½ ½ если j >= M[i]

½ ½ ½ то

½ ½ ½ T[i, j] = max(T[i – 1, j], T[i – 1, j – M[i]] + C[i])

½ ½ ½ иначе

½ ½ ½ T[i, j] = T[i – 1, j]

½ ½ все

½ кц

кц

1. К каким подзадачам может сводиться поиск одной фальшивой монеты среди 27 монет, если известно, что она легче других, а все остальные имеют одинаковую массу.

2. К каким подзадачам может сводиться задача вычисления значения N! (N! = 1*2*3*... *N).

3. К каким подзадачам может сводиться задача поиска суммы положительных элементов таблицы, состоящей из 10 элементов.

4. Являются ли правильными следующие рекуррентные уравнения, где i – натуральное число?

a) S(i) = S(i – 1) – ai;

b) S(i) = S(i – 1) + S(i – 1) для i ³ 2,

S(1) = 1;

c) P(i) = P(i – 1)i для i ³ 2,

P(1) = 1;

d) S(i) = S(i div 2) + 1 для i ³ 2,

S(0) = 1;

e) S(i) = S(i – 1) + 1/i для i ³ 1,

S(0) = 0;

f) S(i) = S(i – 1) + (–1)ixi/i для i ³ 1,

S(0) = 1;

g) F(i) = F((i div 2) + 1) + 1 для i ³ 2,

F(1) = 0, F(1) = – 1;

5. Укажите, при каких размерах таблиц могут быть реализованы следующие рекуррентные соотношения?

a) S(i) = S(i div 2) + S(i – 1) для 2 £ i £ 20,

S(1) = 1

b) S(i, j) = min(S(i – 1, j), S(i – 1, j – 1), aij ) для 2 £ i £ N, 2 £ j £ M,

S(1, j) = a1j, S(i, 1) = ai1

6. Пусть v1 = 1.5; vi =  vi-1. Получить v2, v3, ..., vn, где n заданное натуральное число.

7. Пусть x0 = c, x1 = d; xi = xi–1 + xi–2 + b. Получить x2, x3, ..., xn, где n, b, c, d заданные натуральные числа.

8. Пусть u1 = 0, u2 = 1; ui = ui–1+ ui–2 * ui–1 – ui–2. Получить u3, u4, ..., un, где n заданное натуральное число.

9. Пусть a0 = a1 = 1; ai =  + ai–2. Получить a2, a3, ..., an, где n заданное натуральное число.

10. Пусть а1 = b1 = 1, ai = 0.5(+ 0.5), bi = 2ai–12 + bi–1. Получить a2, a3, ..., an, b2, b3, ..., bn, где n – натуральное число.

11. Пусть а1 = u, b1 = v, ai = 2bi–1 + ai–1, bi = 2ai–12 + bi–1. Получить a2, a3, ..., an, b2, b3, ..., bn, где n – натуральное число, а u, v – некоторые действительные числа.

12. Пусть а1 = 1, b1 = 1, ai = 3/4ai–1 – bi–1, bi = 4/3bi–1 – ai–1. Получить a2, a3, ..., an, b2, b3, ..., bn, где n – натуральнoе числo.

13. Пусть а1 = 1, b1 = 1, ai=2i ai–1 + i!bi–1, bi = i!ai–1 + 3i bi–1. Получить a2, a3, ..., an, b2, b3, ..., bn, где n – натуральное число.

14. Вычислить значение дробей.

14.1.

14. 5.

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

2. Составить алгоритм определения количества 2N-значных "счастливых" билетов, у которых сумма первых N цифр равна сумме последних N цифр; N – произвольное натуральное число.

3. Найти количество n-значных чисел в десятичной системе счисления, у каждого из которых сумма цифр равна k. При этом в качестве n-значного числа мы допускаем и числа, начинающиеся с одного или нескольких нулей. Например, 000102 рассматривается как шестизначное число, сумма цифр которого равна 3.

4. Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K. Найти число различных путей, по которым фишка может пройти поле от позиции 1 до позиции N.

Пример. N = 4, K = 2

Возможные длины ходов:

1, 1

2

1

Ответ: 3.

5. Покупатель имеет купюры достоинством A1, ..., An, а продавец – B1, ..., Bm. Необходимо найти максимальную стоимость товара P, который покупатель не может купить, потому что нет возможности точно рассчитаться за этот товар с продавцом, хотя денег на покупку его достаточно.

6. У покупателя есть n монет достоинством H1, ..., Hn. У продавца есть m монет достоинством B1, ..., Bm. Может ли покупатель приобрести вещь стоимости S так, чтобы у продавца нашлась точная сдача (если она необходима).

7. По матрице A[1..N, 1..N] построить матрицу B[1..N, 1..N]. Элемент B[i, j] равен максимальному из элементов матрицы А, принадлежащему части, ограниченной справа диагоналями, проходящими через A[i, j] (см. таблицу).

*

*

*

*

*

*

.

*

*

*

*

*

*

*

.

*

*

*

*

*

*

*

*

*

*

*

*

*

*

.

*

*

*

*

.

*

*

.

.

.

.

8. Задана матрица натуральных чисел A[1.. n, 1.. m]. За каждый проход через клетку (i, j) взымается штраф A[i, j]. Необходимо минимизировать штраф и

а) Пройти из какой-либо клетки 1-ой строки в n-ую строку, при этом из текущей клетки можно перейти в любую из 3-х соседних, стоящих в строке с номером на 1 большем;

б) Реализовать пункт a) для перехода из клетки (1, 1) в (n, m).

9. Выпуклый n-угольник, n ³ 3, задается координатами своих вершин в порядке обхода по контуру. Разбить его на треугольники (n – 3)-мя диагоналями, не пересекающимися кроме как по концам, таким образом, чтобы:

а) сумма их длин была минимальной;

б) самая длинная из диагоналей имела наименьшую длину.

10. Пусть x = (a1, a2, ..., am) и y = (b1, b2, ..., bn) – две заданные строки символов.

Обозначим через d(x, y) минимальное количество вставок, удалений и замен символов, которое необходимо для преобразования x в y.

Например: d(ptslddf, tsgldds) = 3

удаление p вставка g замена f

ptslddf ¾¾¾¾® tslddf ¾¾¾® tsglddf ¾¾¾® tsgldds

Для заданных сторок x и y определить d(x, y).

11. Даны две строки x и y. Строка x состоит из нулей и единиц, строка y состоит из символов A и B. Можно ли строку x преобразовать в строку y по следующему правилу: цифра 0 преобразуется в непустую последовательность букв A, а цифра 1 – либо в непустую последовательность букв A, либо в непустую последовательность букв B?

12. Пусть известно, что для перемножения матрицы размера n * m на матрицу размера m * k требуется n * m * k операций и в результате получается матрица размера n * k. Необходимо определить, какое минимальное число операций потребуется для перемножения s матриц A1, ..., As, заданных своими размерами n(i) * m(i). При этом можно перемножать любые две рядом стоящие матрицы. Замечание: