Форум » Динамическое программирование » ege18-91 » Ответить
ege18-91
HG: Квадрат разлинован на N x N клеток (1 < N < 20). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: влево или вверх. По команде влево Робот перемещается в соседнюю левую клетку, по команде вверх – в соседнюю верхнюю. При попытке пересечь границы квадрата Робот разрушается. В каждой клетке квадрата указано одно из двух чисел: 0 или 1. Если в клетке записано число 1, Робот может по-пасть в эту клетку, а если в клетке записано число 0, то робот не может попасть в такую клетку. Определите количество способов, которыми Робот может попасть из правой нижней клетки в левую верхнюю. В ответе укажите искомое число. Исходные данные записаны в электронной таблице 18-91.xls размером N x N, каждая ячейка которых соответствует клетке квадрата. 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 Несколько часов пытаюсь решить, но безуспешно. Помогите пожалуйста.
Ответов - 8
Поляков: HG пишет: Несколько часов пытаюсь решить Показывайте, как пытаетесь. Вам нужно составить формулу динамического программирования, которая выражает количество вариантов для клетки (X,Y) через известное количество вариантов для соседних клеток.
HG: Можете скинуть пример задачи, чтобы можно было опереться на неё?
Vin: здравствуйте, тоже поломала голову, предположила по горизонтали дать формулу =ЕСЛИ(B1=1;1+1;1+0), зависла((
Поляков: Если в клетке стоит 0, то записываем в динамическую таблицу 0. Если стоит 1, складываем значения динамической таблицы для тех клеток, откуда Робот может придти в текущую.
Vin: 10 9 8 7 6 5 4 3 2 10 9 8 7 6 5 4 3 2 1 Здравствуйте, не понятно как формируется значение по диагонали
Поляков: Vin пишет: не понятно как формируется значение по диагонали См. пост выше.
AnnaPershina: В любой ячейке динамической таблицы должна быть формула =если (ячейка исходной таблицы =1,то сумма двух ячеек динамической таблицы, из которых попадаем в текущую, а иначе писать 0)
vin: по диагонали даю формулу =ЕСЛИ(I9=1;J21+I22;0) по вертикали =ЕСЛИ(J9=1;J22+J9) по горизонтали =ЕСЛИ(I10=1;J22+I10;0) ответ28286 не сходится, а вернулась к этой задаче от 114 никак не пойму как задать условие на второй вопрос(((
полная версия страницы