Форум » Динамическое программирование » Задание 18, №42 » Ответить
Задание 18, №42
olha: 42) (А. Кабанов) Дана таблица вещественных чисел размера NxN (1 < N 20). Перемещаться между числами можно по горизонтали и вертикали (в любом направлении). Необходимо найти самую длинную последовательность чисел, такую, что каждое следующее число больше предыдуще-го. В ответе запишите длину этой цепочки. Можно ли ходить "ступеньками"? Что-то ужасное я придумала, и не рабочее
Ответов - 11
cabanov.alexey: Константин Юрьевич, в номере 42 почему-то поменялась формулировка вопроса. Там теперь спрашивается наибольшая сумма (ответ под неё не подходит). Правильная формулировка записана в первом сообщении.
Поляков: cabanov.alexey пишет: Правильная формулировка записана в первом сообщении. Спасибо, я поправил.
olha: А какой правильный ответ? У меня получалось 7, не могу открыть новые ответы answers.xls от 18.02.2020 "файл не соответствует формату, или поврежден"
Поляков: olha пишет: не могу открыть новые ответы answers.xls Спасибо за сообщение, файл восстановлен. Ответ 8.
mskorotkov: Конкретно это задание программой решается?
Поляков: mskorotkov пишет: Конкретно это задание программой решается? Видимо, да. Но основная тематика - электронные таблицы.
GasDM: Поляков пишет: Видимо, да. Но основная тематика - электронные таблицы. Если основная тематика - это электронные таблицы, то какую программу нужно написать под MS Excel (Basic исключили из языков экзамена), чтобы было найдено решение. Пробую решить таким способом. Нулем помечены клетки, из которых нужно начинать движение (вокруг них все числа больше). Затем нужно двигаться от меньшего к небольшему числу. Но т.к. возможны несколько вариантов движения из одной и той же клетки, то получаем алгоритм перебора с возвратом: просмотрели один путь из клетки, затем второй путь и т.д. Как такое описать с помощью функций Excel. PS С материалами сайта знаком. Если на сайте есть материал, кроме файла ege18.doc, который поможет решить это задание, прошу указать его. Заранее спасибо за помощь
cabanov.alexey: Плохо, что вы не можете решить это стандартными средствами. Подтягивайте знание электронных таблиц. Решение задания
GasDM: cabanov.alexey пишет: Плохо, что вы не можете решить это стандартными средствами. Подтягивайте знание электронных таблиц. Учиться никогда не поздно. Я размышлял совсем в другом направлении. Спасибо за решение. Оно оказалось не сложным.
VarERiy6: GasDM, скажите, пожалуйста, а как с суммой? Так же не получается
GasDM: Решение для задания написал рекурсивное. Можно, конечно, было организовать чтение данных из файла, программа была бы короче. если будут замечания к решению или предложения по ДИНАМИЧЕСКОМУ решению, будут рад их прочитать. [pre2] const n = 15; var a : array [0..n+1,0..n+1] of integer = ((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0), (0,42,100,3,87,2,6,98,19,1,48,59,99,91,33,96,0), (0,15,32,6,94,38,32,74,16,85,7,14,31,4,35,93,0), (0,84,25,59,24,90,26,96,52,8,21,25,3,58,72,6,0), (0,43,38,54,81,37,35,24,98,94,14,62,86,75,47,57,0), (0,6,62,69,56,84,50,89,99,8,18,47,57,38,100,63,0), (0,55,36,34,12,93,77,45,44,84,56,8,25,29,57,60,0), (0,84,35,31,66,21,94,80,52,8,62,55,21,48,69,76,0), (0,10,77,83,82,35,5,24,12,35,35,72,57,34,49,88,0), (0,3,16,96,78,51,92,91,67,79,81,97,26,83,73,37,0), (0,36,95,25,46,91,84,33,82,98,53,8,70,52,39,63,0), (0,6,59,11,11,6,13,83,20,39,65,53,68,4,55,34,0), (0,27,60,15,42,15,24,12,57,20,9,1,79,29,46,60,0), (0,47,52,94,76,42,38,8,24,31,8,61,24,89,52,16,0), (0,92,21,56,57,61,68,41,29,11,62,2,38,27,97,56,0), (0,77,32,95,53,4,95,72,28,69,7,41,89,39,67,12,0), (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)); b : array [0..n+1,0..n+1] of integer; i, j, curMStep, MStep : integer; procedure PrintArrB; var i, j : integer; begin for i:= 1 to n do begin for j:=1 to n do write(b[i,j]:4); writeln; end; end; procedure find_way(step, x0,y0 : integer); begin if a[x0-1,y0]>a[x0,y0] then find_way(step+1,x0-1,y0); if a[x0+1,y0]>a[x0,y0] then find_way(step+1,x0+1,y0); if a[x0,y0+1]>a[x0,y0] then find_way(step+1,x0,y0+1); if a[x0,y0-1]>a[x0,y0] then find_way(step+1,x0,y0-1); if Step > curMStep then curMStep := Step; end; //основная программа begin //заполнение массива B for i:=0 to n + 1 do for j := 0 to n + 1 do b[i,j] := 0; MStep := 0; for i := 1 to n do for j := 1 to n do begin curMStep := 0; find_way(1,i,j); b[i,j] := curMStep; if curMStep > MStep then MStep := curMStep; end; //вывод массива B - контрольный вывод PrintArrB; Writeln('Максимальное количество шагов = ',MStep); end. [/pre2]
полная версия страницы