Форум » Форум, сайт и общие вопросы » Динамическое программирование. Задача №5 (размен монет). » Ответить
Динамическое программирование. Задача №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
Поляков: Каган пишет: Если же написать по другому T[i,w] = T[i - 1,w] + T[i, w-p] при w >=p Тогда получается матрица совпадающая с матрицей из учебника. Это опечатка, она есть в списке опечаток и уже исправлена в издании 2015 года.
полная версия страницы