Автор | Сообщение |
|
Отправлено: 21.05.16 08:17. Заголовок: Динамическое программирование. Задача №5 (размен монет).
Здравствуйте, Константин Юрьевич! Пишем программы с ребятами из Вашего учебника. Динамическое программирование. Задача №5 (размен монет). При вычислении элементов матрицы T[i,w] = T[i - 1,w] + T[i-1, w-p] при w >=p получается другая матрица не та, которая приведена в учебнике. Если же написать по другому T[i,w] = T[i - 1,w] + T[i, w-p] при w >=p Тогда получается матрица совпадающая с матрицей из учебника. Да и по смыслу объяснения этой задачи больше подходит второй вариант вычисления. Ниже привожу код нашей программы, написанной для этой задачи. PROGRAM razmen_monet; uses crt; const n=10; k=4; var t: array [1..k, 0..n] of integer; p: array [1..k] of integer; i,w: integer; begin clrscr; //инициализирую массив монет p[1]:= 1; p[2]:= 2; p[3]:= 5; p[4]:= 10; //инициализирую первую строку массива t for i:=1 to n do t[1,i] := 1; //инициализирую первый столбец массива t for i:=1 to k do t[i,0] := 1; for i:= 2 to k do for w:=1 to n do if w<p then t[i,w] := t[i-1,w] else t[i,w] := t[i-1,w] + t[i, w-p]; for i:=1 to k do begin writeln; for w:=1 to n do write (t[i,w], ' '); end; end. С уважением, Каган Григорий Владимирович 11 школа Ярославля
|
|
|
Ответов - 1
[только новые]
|
|
|
| Администратор
|
Сообщение: 1141
|
|
Отправлено: 02.06.16 21:26. Заголовок: Каган пишет: Если же..
Каган пишет: цитата: | Если же написать по другому T[i,w] = T[i - 1,w] + T[i, w-p] при w >=p Тогда получается матрица совпадающая с матрицей из учебника. |
|
Это опечатка, она есть в списке опечаток и уже исправлена в издании 2015 года.
|
|
|