* Писна ми от задачи с преливания
Публикувано на 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 страници ще са достатъчни само за резюме на извършения труд), то ще свърши едно добро дело – няма повече да ни занимават със задачи с преливания.