* Писна ми от задачи с преливания
Публикувано на 02 ноември 2011 в раздел Математика.
Класическата задача с преливане на вода от едни съдове в други се дава непрекъснато по различни блогове и форуми. Не ви ли писна? Хайде да свършим веднъж завинаги с нея!
Дадени са n на брой съда a1,...an, всеки от които побира съответно b1,...,bn литра вода. Първите a1,...ak съда са пълни с вода, а останалите ak+1,...an са празни. Покажете как (ако е възможно) ще напълните точно "l" на брой съда с точно "x" литра вода. (l≤n и x≤max(bi), i=1,...,n). Успех!
Ъъъ, за това има генерална формула ли? Никога не ми е хрумвало да търся такава o.O
Хаха, ами не, формула едва ли има. Не, че съм търсил и чел много, но задачи от подобен тип винаги са били тежки и то дадени с конкретни числа. А тук задачата е обобщена с произволни параметри :)
В една съвместна публикация с един колега разгледахме систематизиран метод за решаване на задачи с дискретна оптимизация и в частност дадохме пример със задачата с преливанията от три туби (уточнявам за по-младите - задачата от "Умирай Трудно 3" :P). Начинът беше с построяване на проективна равнина, в която всеки връх се явява точка на възможно текущо състояние, а всяка съседна - възможен преход. Така имаме постановка, при която имаме дадено текущо състояние и трябва да намерим най-късия път до търсено крайно състояние. Нататък решението е лесно - дискретната математика е открила отдавна как се правят тези неща с графите :)
Да де, ама там имаме дадени точно определени параметри. А в тази горе - не. Освен това тубите са "n" и малко трудно се чертае (то трудно се и фантазира, а за чертаене и дума да не става). Затова и написах "успех" :) Ако някой я реши (за което вярвам 100-120 страници ще са достатъчни само за резюме на извършения труд), то ще свърши едно добро дело - няма повече да ни занимават със задачи с преливания.