:: Игры Разума
Ещё раз о деньгах
akvvohinc
Автор

Сообщений: 4150
Откуда: Москва
Дата регистрации: 11.11.2008
Внучке на уроке информатики предложили две задачки по написанию алгоритма в таких формулировках.

Условие
Есть дом, имеющий PD подъездов и ET этажей.
На каждом этаже каждого подъезда стоит коробка с деньгами (допустим, случайное число от 0 до 100). Все суммы известны (написаны на коробках).
Вы можете взять себе из каждого подъезда лишь одну коробку с любого этажа.

Задача. Построить алгоритм, обеспечивающий себе максимальную сумму.

Ну, тут понятно - пробегаем по подъездам (внешний цикл), и в каждом подъезде находим этаж, на котором стоит коробка с максимальной суммой (внутренний цикл). Забираем себе все такие коробки.

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

Таким образом, эти последовательности этажей в трёхподъездном трёхэтажном доме допустимы:
1, 1, 1
1, 2, 3
2, 3, 3
3, 3, 3

А такие - нет:
2, 2, 1
1, 3, 2

Ниже я привел код, который решает поставленную задачу путем полного перебора всех допустимых комбинаций выбранных этажей по подъездам.
Но этот способ довольно "энергозатратный" - при росте количества подъездов количество допустимых комбинаций стремительно растёт.
Полное количество комбинаций равно ET^PD, что для 14-подъездной 9-этажки (я в такой жил когда-то) равно 14-значному числу.
Конечно, число допустимых комбинаций существенно меньше, но также очень и очень велико (например, при PD=11 и ET=25 оно равно 417'225'900)

А теперь вопрос:
Может ли кто-нибудь предложить принципиально иной алгоритм решения данной задачи - не полным перебором и более быстрый?
(если такой способ может существовать в принципе)

Процедура, решающая задачу для 10 подъездов и заданного параметром количества этажей (default = 10)
= getcombi(20) && около 20 млн. вариантов, у меня отрабатывает за 11-12 секунд



Исправлено 2 раз(а). Последнее : akvvohinc, 10.12.23 01:56
Ratings: 0 negative/0 positive
Re: Ещё раз о деньгах
leonid

Сообщений: 3197
Откуда: Рига
Дата регистрации: 03.02.2006
Если только сумму надо указать, то наверное такой сойдет, а если еще и координаты коробок, то еще чуток подкрутить нужно.
PD = 100
ET = 100
= RAND(-1)
DIMENSION M[PD,ET]
FOR pd1=1 TO PD
FOR et1=1 TO ET
M[pd1,et1] = ROUND(RAND()*100,0)
ENDFOR
ENDFOR
DIMENSION R[PD + 1,ET + 1]
FOR et2 = 1 TO ET + 1
R[1, et2] = 0
ENDFOR
FOR pd2 = 1 TO PD + 1
R[pd2, 1] = 0
ENDFOR
FOR pd3 = 1 TO PD
FOR et3 = 1 TO ET
R[pd3 + 1, et3 + 1] = MAX(R[pd3 + 1, et3], M[pd3, et3] + R[pd3, et3 + 1])
ENDFOR
ENDFOR
? R[PD + 1, ET + 1]
Ratings: 0 negative/1 positive
Re: Ещё раз о деньгах
akvvohinc
Автор

Сообщений: 4150
Откуда: Москва
Дата регистрации: 11.11.2008
Цитата:
Если только сумму надо указать, то наверное такой сойдет, а если еще и координаты коробок, то еще чуток подкрутить нужно.
Спасибо, Леонид.
Код ещё не изучал, но добавлю, что главное - это узнать именно координаты коробок - сумма вторична.
Ratings: 0 negative/0 positive
Re: Ещё раз о деньгах
leonid

Сообщений: 3197
Откуда: Рига
Дата регистрации: 03.02.2006
Координаты коробок - тут ответ неоднозначный. Реально вариантов может быть слишком много, чтобы перечислять все. Нужно еще условие, чтобы выбрать один вариант.
Ratings: 0 negative/0 positive
Re: Ещё раз о деньгах
leonid

Сообщений: 3197
Откуда: Рига
Дата регистрации: 03.02.2006
Вроде вот такая добавочка к тому, что было выше, распечатает один из возможных путей.
et4 = ET + 1
FOR pd4 = PD + 1 TO 2 STEP -1
DO WHILE R[pd4, et4] = R[pd4, et4 - 1]
et4 = et4 - 1
ENDDO
? 'PD = ' + TRANSFORM(pd4 - 1) + ', ET = ' + TRANSFORM(et4) + ', SUM = ' + TRANSFORM(M[pd4 - 1, et4 - 1])
ENDFOR
Ratings: 0 negative/1 positive
Re: Ещё раз о деньгах
akvvohinc
Автор

Сообщений: 4150
Откуда: Москва
Дата регистрации: 11.11.2008
Цитата:
Реально вариантов может быть слишком много, чтобы перечислять все. Нужно еще условие, чтобы выбрать один вариант.
К сожалению, реальных доп.условий нет - видимо, ответом может быть любой вариант с максимальной суммой.

Но если всё же выбирать, то, думаю, наиболее "красивым" был бы тот, где разность между максимальным номером выбранного этажа и минимальным была бы наибольшей, а график изменения выбранной этажности между минимальным и максимальным значением был наиболее "прямым", то есть для матрицы 10x10 идеалом был бы такой:
1,2,3,4,5,6,7,8,9,10

Как считаете, для 6 класса обычной школы можно "засветить" ваш алгоритм преподавателю?
Не окажется ли это для него "слишком"?
Что-то я сомневаюсь, что он ожидает от кого-то из учеников чего-то подобного.



Исправлено 1 раз(а). Последнее : akvvohinc, 10.12.23 19:51
Ratings: 0 negative/0 positive
Re: Ещё раз о деньгах
leonid

Сообщений: 3197
Откуда: Рига
Дата регистрации: 03.02.2006
akvvohinc
наиболее "красивым" был бы тот, где разность между максимальным выбранным этажом и минимальным была бы наибольшей, а график изменения выбранной этажности между минимальным и максимальным значением был наиболее "прямым"

Это условие тоже не дает однозначности. Это видно, например, на таком примере:

2 3
1 4

Здесь два пути, и у обоих указанные параметры одинаковые. Условием для однозначности могли бы быть условия "максимальности" ("минимальности") пути, то есть в каждом следующем подъезде выбирается максимальный (минимальный) этаж, для которого существует решение. Приведенная мною распечатка как раз и дает один из этих вариантов.

Цитата:
Как считаете, для 6 класса обычной школы можно "засветить" ваш алгоритм преподавателю?

Я не знаю, как сейчас в школах обучают программированию. На мой взгляд, для 6 класса такой алгоритм - это черезчур. А с другой стороны, эта задача под такой алгоритм как бы заточена, будто под него писалась. Давать такую задачу для обучения простому перебору - как-то выглядит странным.
Ratings: 0 negative/0 positive
Re: Ещё раз о деньгах
akvvohinc
Автор

Сообщений: 4150
Откуда: Москва
Дата регистрации: 11.11.2008
Цитата:
Это видно, например, на таком примере:
2 3
1 4
Я успел немного подправить условия - имел в виду максимальную разность между номерами этажей,
то есть 4-1 = 3 лучше, чем 3-2 = 1.
Ratings: 0 negative/0 positive
Re: Ещё раз о деньгах
leonid

Сообщений: 3197
Откуда: Рига
Дата регистрации: 03.02.2006
Я наверное плохо пример объяснил. Там два подъезда по два этажа в каждом. Цифры - это количество денег в коробках. Максимум получается, если взять обе коробки на первых этажах, или обе коробки на вторых.
Ratings: 0 negative/0 positive
Re: Ещё раз о деньгах
akvvohinc
Автор

Сообщений: 4150
Откуда: Москва
Дата регистрации: 11.11.2008
Понятно.
В таком случае можно остановиться на условии "минимальности общей работы (пути)", если считать, что после решения задачи "на бумаге" предстоит пешком подниматься до выбранных этажей, забирать коробки и спускаться обратно.
В вашем примере - берём коробки с первых этажей.

Цитата:
На мой взгляд, для 6 класса такой алгоритм - это черезчур. А с другой стороны, эта задача под такой алгоритм как бы заточена, будто под него писалась. Давать такую задачу для обучения простому перебору - как-то выглядит странным.
Значит ли это, что между этими двумя крайностями, вы можете назвать и какой-то "средний" алгоритм?
Ratings: 0 negative/0 positive
Re: Ещё раз о деньгах
leonid

Сообщений: 3197
Откуда: Рига
Дата регистрации: 03.02.2006
akvvohinc
В таком случае можно остановиться на условии "минимальности общей работы (пути)"

Не уверен, но сдается, что тот алгоритм, который я привел выше, именно такой путь и выдает.

Цитата:
Значит ли это, что между этими двумя крайностями, вы можете назвать и какой-то "средний" алгоритм?

Я хотел сказать, не то, что существует какой-то средний алгоритм, а то, что подобные задачи как раз и создаются для того, чтобы обучить тому, какая огромная разница в скорости работы может быть получена, если применять не самый очевидный переборный алгоритм, а поискать такой, который позволяет существенно оптимизировать процесс расчетов.
Ratings: 0 negative/0 positive
Re: Ещё раз о деньгах
akvvohinc
Автор

Сообщений: 4150
Откуда: Москва
Дата регистрации: 11.11.2008
Цитата:
подобные задачи как раз и создаются для того, чтобы обучить тому, какая огромная разница в скорости работы может быть получена, если применять не самый очевидный переборный алгоритм, а поискать такой, который позволяет существенно оптимизировать процесс расчетов.
Большое вам спасибо!
Я хоть и верил, что существует что-то более быстрое, чем полный перебор, но то, что настолько!..
:hi:
Ratings: 0 negative/0 positive
Re: Ещё раз о деньгах
akvvohinc
Автор

Сообщений: 4150
Откуда: Москва
Дата регистрации: 11.11.2008
leonid
Вроде вот такая добавочка к тому, что было выше, распечатает один из возможных путей.
Погонял немного - похоже, распечатывающая добавочка выводит номер этажа на 1 больший, чем реальный.
Я это заметил, когда в первой же строке увидел номер этажа больший, чем этажность дома.

Вот этот код для дома 3x3 начинает выводить путь с ET = 4, если реальный номер ET = 3.
Достаточно ли будет просто изменить вывод этажа TRANSFORM(et4 - 1) ?

PD = 3
ET = 3
= RAND(-1)
DIMENSION M[PD,ET]
FOR pd1=1 TO PD
FOR et1=1 TO ET
M[pd1,et1] = ROUND(RAND()*100,0)
ENDFOR
ENDFOR
DIMENSION R[PD + 1,ET + 1]
FOR et2 = 1 TO ET + 1
R[1, et2] = 0
ENDFOR
FOR pd2 = 1 TO PD + 1
R[pd2, 1] = 0
ENDFOR
FOR pd3 = 1 TO PD
FOR et3 = 1 TO ET
R[pd3 + 1, et3 + 1] = MAX(R[pd3 + 1, et3], M[pd3, et3] + R[pd3, et3 + 1])
ENDFOR
ENDFOR
et4 = ET + 1
FOR pd4 = PD + 1 TO 2 STEP -1
DO WHILE R[pd4, et4] = R[pd4, et4 - 1]
et4 = et4 - 1
ENDDO
? 'PD = ' + TRANSFORM(pd4 - 1) + ', ET = ' + TRANSFORM(et4) + ', SUM = ' + TRANSFORM(M[pd4 - 1, et4 - 1])
ENDFOR
? R[PD + 1, ET + 1]



Исправлено 2 раз(а). Последнее : akvvohinc, 12.12.23 08:20
Ratings: 0 negative/0 positive
Re: Ещё раз о деньгах
leonid

Сообщений: 3197
Откуда: Рига
Дата регистрации: 03.02.2006
akvvohinc
похоже, распечатывающая добавочка выводит номер этажа на 1 больший, чем реальный.

Вполне может быть, я не очень внимательно проверял.

Цитата:
Достаточно ли будет просто изменить вывод этажа TRANSFORM(et4 - 1) ?

Да, конечно
Ratings: 0 negative/0 positive
Re: Ещё раз о деньгах
akvvohinc
Автор

Сообщений: 4150
Откуда: Москва
Дата регистрации: 11.11.2008
Отлично, спасибо!
Ratings: 0 negative/0 positive
Re: Ещё раз о деньгах
akvvohinc
Автор

Сообщений: 4150
Откуда: Москва
Дата регистрации: 11.11.2008
Дополню - при определенных раскладах, например, все нули в первом подъезде, условие DO WHILE R[pd4, et4] = R[pd4, et4 - 1] будет валиться из-за выхода индекса за допустимый интервал (индекс будет равен 0).

Подправил это место так:
DO WHILE et4>=2 AND R[pd4, et4] = R[pd4, et4 - 1]
et4 = et4 - 1
ENDDO
et4 = MAX(et4, 2)



Исправлено 2 раз(а). Последнее : akvvohinc, 15.12.23 17:28
Ratings: 0 negative/0 positive
Re: Ещё раз о деньгах
leonid

Сообщений: 3197
Откуда: Рига
Дата регистрации: 03.02.2006
Да, действительно, недоглядел, но "идейно" правильней было просто в нулевой этаж загнать не нули, а отрицательные числа, скажем -1. А можно вообще обойтись без нулевых подъезда и этажа, тогда надо сначала заполнить рабочий массив для первого подъезда и этажа, алгоритмы заполнения которых элементарны. В таком случае не будет сдвига индексов на 1 между массивом с данными, и рабочим массивом, и, пожалуй, все будет выглядеть наглядней.
Ratings: 0 negative/0 positive
Re: Ещё раз о деньгах
akvvohinc
Автор

Сообщений: 4150
Откуда: Москва
Дата регистрации: 11.11.2008
leonid
А можно вообще обойтись без нулевых подъезда и этажа, тогда надо сначала заполнить рабочий массив для первого подъезда и этажа, алгоритмы заполнения которых элементарны. В таком случае не будет сдвига индексов на 1 между массивом с данными, и рабочим массивом, и, пожалуй, все будет выглядеть наглядней.
Отличное предложение!

Мой вариант его реализации:

Изначально я просто сравнил результаты, полученные по вашему алгоритму, с вариантом полного перебора на "миллионе" вариантов, чтобы убедиться в его правильности.
Но не могли бы вы доступным образом (для нематематиков ) объяснить/доказать, что алгоритм действительно решает данную задачу?



Исправлено 3 раз(а). Последнее : akvvohinc, 17.12.23 06:05
Ratings: 0 negative/0 positive
Re: Ещё раз о деньгах
leonid

Сообщений: 3197
Откуда: Рига
Дата регистрации: 03.02.2006
Массив R - это массив, который содержит решения этой же самой задачи для домов с меньшим количеством подъездов и этажей. Для одноэтажных домов, и домов с одним подъездом решения этой задачи очевидны. Дальше все идет по индукции. Предположим, нам известны решения задачи R[i, j-1] и R[i-1, j]. Этих значений достаточно, чтобы вычислить R[i,j]. Логика такая: если R[i-1, j] + M[i, j] больше, чем R[i, j-1], то для того, чтобы получить максимум, мы должны пройти тем же путем, что и для R[i-1, j], а затем в i-ом подъезде взять еще коробку с j-го этажа. Если же R[i-1, j] + M[i, j] меньше, чем R[i, j-1], то мы коробку с j-го этажа брать не должны, а воспользоваться тем же самым путем, который был в R[i, j-1]. Ну, а если эти два значения совпадают, то годится любой из этих двух вариантов, отсюда и неоднозначность пути.
Ratings: 0 negative/1 positive
Re: Ещё раз о деньгах
akvvohinc
Автор

Сообщений: 4150
Откуда: Москва
Дата регистрации: 11.11.2008
Спасибо большое!
Ratings: 0 negative/0 positive


Извините, только зарегистрированные пользователи могут оставлять сообщения в этом форуме.

On-line: 2 (Гостей: 2)

© 2000-2024 Fox Club 
Яндекс.Метрика