Author |
Message |
07/06/2019 01:24:55
|
Scratcher
Joined: 21/01/2013 16:53:12
Messages: 14
Offline
|
http://mendo.mk/Task.do?id=850
Немам никаква друга идеја за решавање на оваа задача освен со рекурзија(backtracking)
каде пробувам секој број од едната низа да го сведам во број од другата низа, а потоа рекурзивно решавам за следната состојба
Поконкретно, паѓа на овој тест пример
9
1 14 22 11 6 11 14 1 24
5
34 37 20 8 5
каде:
очекувано: 8
добиено: INT_MAX(не наоѓа решение)
Еве го кодот
Забелешка: На МЕНДО 9/20 се точни а останатите се погрешен резултат или надминат временски лимит
|
|
|
09/06/2019 00:20:47
|
longhi
Joined: 16/01/2019 22:52:02
Messages: 18
Offline
|
Scratcher wrote:Немам никаква друга идеја за решавање на оваа задача освен со рекурзија(backtracking)
Втората акција што може да ја направи роботот (две вреќи да се спојат во една) е многу поедноставна од првата (бидејќи таму треба да одлучуваме колку подароци да префрлиме).
Ова може да го средиме така што првата операција воопшто нема да ја правиме, туку ќе ја правиме само втората - но во две насоки, т.е. почнувајќи и од почетната состојба (како што се ќесите спакувани на почеток) и од крајната состојба (како што треба да бидат спакувани). Ова има логика бидејќи едната акција на роботот е слична на втората - само обратно - наместо да спојуваме две вреќи во една, делиме една вреќа на две.
Значи, можеме да напишеме програма која што ќе користи неколку идеи
1) Да пресметаме со колку акции може да се стигне од една состојба до сите други со спојување на вреќи (за тоа може да се искористи queue - слична идеја како кај алгоритамот BFS)
2) Ако од почетната состојба можеме да дојдеме до некоја состојба X, и од крајната состојба може да дојдеме до истата таа состојба X - тогаш може да се стигне од почетната состојба до крајната состојба. Притоа, ако требаат A чекори за да се стигне од почетната состојба до X, и B чекори за да се стигне од крајната состојба до X, тогаш за доаѓање од почетната до крајната состојба преку X требаат вкупно (A+B) чекори.
Ако е уште нејасно, еве решение
|
|
|
09/06/2019 23:41:15
|
Scratcher
Joined: 21/01/2013 16:53:12
Messages: 14
Offline
|
Благодарам за идејата, еве ја мојата имплементација
This message was edited 1 time. Last update was at 09/06/2019 23:41:35
|
|
|
|
|
|