Немного о динамическом программировании

@Annie_Jeevas · Регистрация: 24.11.2015

Author24 — интернет-сервис помощи студентам

Динамическое программирование – это способ решения сложных оптимизационных или расчетных задач путем разбиения данной задачи на более простые, меньшие по размерности подзадачи. Чтобы убедиться в удобстве этого аппарата, рассмотрим задачу.
Кубик, грани которого помечены цифрами от 1 до 6, бросают N раз. Определите вероятность того, что произведение выпавших чисел будет в точности равна Q.
Теперь рассмотрим N-ное бросание кубика. Оно обязательно увеличит текущее произведение в 1, 2, 3, 4, 5 или 6 раз. Тогда нам нужно просто посмотреть, из каких произведений на предыдущем броске (N-1) можно получить текущее путем умножения его на 1, 2, 3, 4, 5 или 6. Другими словами, мы обращаемся к тем произведениям, количество выпадений которых мы подсчитали на предыдущем броске и которые получились из текущего путем деления нацело на 1, 2, 3, 4, 5 или 6. Сложив количество этих исходов, мы получим как раз то количество, которое нам нужно.
Тогда будем заполнять таблицу слева направо сверху вниз по формуле:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?a[i,j]=a[i,j]+a[i-1, \frac{j}{k}]$

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	Q
1	1	1	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0
2	1	2	2	3	2	4	0	2	1	2	0	4	0	0	2	1	0	2
3	1	3	3	6	3	9	0	7	3	6	0	15	0	0	6	6	0	9
4	1	4	4	10	4	16	0	16	6	12	0	36	0	0	12	19	0	24
5	1	5	5	15	5	25	0	30	10	20	0	70	0	0	20	45	0	50
6	1	6	6	21	6	36	0	50	15	30	0	120	0	0	30	90	0	90
7	1	7	7	28	7	49	0	77	21	42	0	189	0	0	42	161	0	147
8	1	8	8	36	8	64	0	112	28	56	0	280	0	0	56	266	0	224
9	1	9	9	45	9	81	0	156	36	72	0	396	0	0	72	414	0	324
10	1	10	10	55	10	100	0	210	45	90	0	540	0	0	90	615	0	450
N

Например, для N = 7 и Q = 12 проверяем, на что делится нацело число 12:
• На 1 – тогда по формуле (1) нам надо обратиться к ячейке с индексами i = 7 – 1 = 6 и j = 12 / 1 = 12. В этой ячейке a[6,12] лежит значение 120.
• На 2 – обращаемся к ячейке i = 6 и j = 12/2 = 6. В ячейке a[6, 6] находится значение 36.
• На 3 – в ячейке a[6, 12/3] значение 21.
• На 4 - в ячейке a[6, 12/4] значение 6.
• На 5 Q = 12 не делится, значит этот пункт мы пропускаем.
• На 6 - в ячейке a[6, 12/6] значение 6.

Привожу программу, составляющую таблицу для введенных значений:

Pascal    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
var
  n, i, j, k, z: integer;
  x: real;
  q: integer;
  a: array[,] of real;
 
function y(a, b: integer): integer;
var
  i: integer;
  x: integer;
begin
  x := 1;
  for i := 1 to b do
    x := x * a;
  y := x;
end;
 
begin
 writeln('Введите произведение: Q = ');
  read(q);
   writeln('Введите количество бросков: N = ');
   read(n);
  setlength(a,  n + 1,q + 1);
  for i := 0 to n do
    for j := 0 to q do
      a[i, j] := 0;
  if q < 6 then z := q else z := 6;//если произведение меньше шести
  for j := 1 to z do
    a[1, j] := 1;
    
  for i := 1 to n do
    for j := 1 to q do
      for k := 1 to 6 do
        if j mod k = 0 then
          a[i, j] := a[i, j] + a[i - 1, j div k];
  for i:=0 to n do
   a[i,0]:=i;
  for j:=0 to q do
   a[0,j]:=j;   
   
  for i := 0 to n do 
  begin
    writeln;
    for j := 0 to q do
      write(a[i, j]:3:0, ' ');
  end;
  writeln;
  x:=a[n,q]/y(6,n);
   writeln('Вероятность: ',x);
end.

Очевидно, что количество удачных исходов лежит в ячейке a[N, Q]. Для того чтобы перейти к вероятности, нам нужно всего лишь разделить это значение на количество всех исходов при N бросках:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?p(N,Q)=\frac{a[N,Q]}{{6}^{N}}$

magirus · 24.11.2015, 22:05

и к чему весь этот опус?

@Annie_Jeevas · 24.11.2015, 22:45 **[ТС]**

А Вы считаете этот "опус" бесполезным? Я решила поделиться им, потому что у многих моих знакомых возникали проблемы с подобными задачами.

@кот Бегемот · 26.11.2015, 00:19

Не слушайте этого супер-пупера, Вы правильно сделали, что поместили этот пример. Тема сложная и хорошо, когда её объясняют простыми словами и понятным языком. Спасибо.

Новые блоги и статьи Все статьи Все блоги /
Не удержался от оценки концепции двигателя Стирлинга. Hrethgir 03.04.2025 Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .	Метод с двумя буферами (или double buffering) или ping-pong buffering Hrethgir 02.04.2025 Из ответов LM модели. Метод, который предполагает использование двух массивов для хранения промежуточных результатов сложения векторов, обычно применяется в сценариях, где необходимо минимизировать. . .	На любовном киберфронте Alexander-7 01.04.2025 Недавно на одном малоизвестном сайте знакомств мною заинтересовалась девушка: «Текст немного странный. Но, судя по адресу почты, иностранка», – подумал я. Поколебавшись пару суток, я ответил ей:. . .	Как работает Node.js изнутри run.dev 29.03.2025 Node. js изменил подход к разработке веб-приложений, позволив использовать JavaScript не только на стороне клиента, но и на сервере. Созданный в 2009 году Райаном Далем, этот открытый,. . .	Моки в Python: Mock Object Library py-thonny 29.03.2025 Тестирование кода требует особого подхода, когда речь идёт о компонентах, взаимодействующих с внешним миром. Мы часто сталкиваемся с непредсказуемостью HTTP-запросов, чтением данных из базы или. . .
JavaScript: Управление памятью и улучшение производительности run.dev 29.03.2025 В отличие от низкоуровневых языков программирования, JavaScript не требует ручного выделения и освобождения памяти. Здесь работает автоматический сборщик мусора, который определяет, какие объекты. . .	Мультитенантная архитектура со SpringBoot и PostgreSQL ArchitectMsa 29.03.2025 SaaS-приложения редко обслуживают одного клиента и обычно они должны поддерживать множество организаций, каждая из которых работает в своём изолированном пространстве. Мультитенантная архитектура. . .	std::span в C++: Производительность и лучшие практики NullReferenced 28.03.2025 std::span — одно из самых недооценённых нововведений стандарта C++20, которое радикально меняет подход к работе с непрерывными последовательностями данных. По сути, это невладеющее представление. . .	Многопоточность в C#: Threadpool UnmanagedCoder 28.03.2025 Пул потоков в C# — это коллекция заранее созданных и готовых к использованию потоков, которые находятся в распоряжении приложения. Вместо того чтобы создавать и уничтожать потоки для каждой небольшой. . .	Вопросы на собеседованиях по микросервисам ArchitectMsa 27.03.2025 Работодатели ищут не просто разработчиков, знающих базовые концепции, а специалистов, разбирающихся в тонкостях масштабирования, отказоустойчивости и производительности. Сейчас на первый план выходят. . .

magirus Почетный модератор 28047 / 15783 / 983 Регистрация: 15.09.2009 Сообщений: 67,753 Записей в блоге: 78
	24.11.2015, 22:05
	и к чему весь этот опус? 0

@Annie_Jeevas 0 / 0 / 0 Регистрация: 24.11.2015 Сообщений: 2
	24.11.2015, 22:45 [ТС]
	А Вы считаете этот "опус" бесполезным? Я решила поделиться им, потому что у многих моих знакомых возникали проблемы с подобными задачами. 0

@кот Бегемот Платежеспособный зверь 8959 / 4384 / 1652 Регистрация: 28.10.2009 Сообщений: 11,629
	26.11.2015, 00:19
	Не слушайте этого супер-пупера, Вы правильно сделали, что поместили этот пример. Тема сложная и хорошо, когда её объясняют простыми словами и понятным языком. Спасибо. 1