[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
[општински 2019]Дедо Мраз  XML
Forum Index » Задачи од национални натпревари
Author Message
Krenkov



Joined: 22/09/2015 18:30:50
Messages: 11
Offline

Имам прашање за задачава за оние кои ја имат решено бидејќи ми прегоре напојувањето пробувајќи да ја решам за време на натпреварот дали сум на добар пат?


Ви благодарам.


p.s

Ова задача спаѓа во Ad-hoc проблеми?
petarsor



Joined: 15/07/2018 11:58:27
Messages: 83
Offline

Krenkov wrote:Ова задача спаѓа во Ad-hoc проблеми?


Ако сакаш со твојов код, можеш да продолжиш да се обидуваш (сега ја има задачата во тренинг делот на МЕНДО).
Ама, ако сакаш хинт како се решава: (рекурзија) [Има и предавање во делот за алгоритми за користење на рекурзија при решавање на слични задачи]
BATIR



Joined: 20/06/2015 16:36:50
Messages: 153
Offline

Слични?
petarsor



Joined: 15/07/2018 11:58:27
Messages: 83
Offline

BATIR wrote:Слични?

Па да, опишаните техники во предавањата за рекурзија (backtracking) - повикување на истата функција за да се разгледаат разни состојби, функцијата да прима соодветни параметри кои ја опишуваат тековната состојба и од таму создавање на други состојби и слично. Ако сме решиле доста задачи со таа техника, другите задачи делуваат слично бидејќи само треба да откриеме кои параметри се потребни за определување на состојба (во новата задача), кои следни состојби се доволни да ги правиме/разгледуваме, итн.
MODDI



Joined: 27/12/2017 18:17:00
Messages: 35
Offline


Кодов ми работи на 12/20 тест примери, малку хелп ако може??
petarsor



Joined: 15/07/2018 11:58:27
Messages: 83
Offline

Па добро, твојов код користи рекурзија колку да се каже. Самиов кодот можеш да го прекуцаш и без рекурзија.
Поентата кога користиме backtracking е што кога ќе направиме некој потег, продолжуваме натака со рекурзијата како да е тоа правилен потег, меѓутоа после кога се враќаме назад, правиме друг потег во тој чекор.

На пример, замисли три кутии, и сакаме да разгледаме разни ситуации (каде или може да ставиме некое топче во кутија, или да не ставиме).
Со backtracking, во рекурзијата, прво ја гледаме првата кутија и викаме 1) стави топче во првата кутија, и продолжи рекурзивно да ги разгледаш другите кутии.
Потоа, кога рекурзијата ќе се врати назад (кога ќе заврши разгледувањето на другите две кутии), потоа викаме 2) не ставај топче во првата кутија, и продолжи рекурзивно да ги разгледаш другите кутии.
На тој начин разгледуваме разни состојби. Оваа техника е опишана во предавањето за рекурзија/backtracking, но може да се најдат разни примери со пребарување на Google.


Ти не го правиш ова. Може лесно и да се примети од твојот код, бидејќи го зголемуваш "time++" на неколку места и продолжуваш натаму (значи правиш потези), но никаде не ги поништуваш тие потези (да пробаш со нешто друго во тој чекор од рекурзијата).
MODDI



Joined: 27/12/2017 18:17:00
Messages: 35
Offline

Не те сватив баш, може псевдо код за делот со рекурзија
petarsor



Joined: 15/07/2018 11:58:27
Messages: 83
Offline

MODDI wrote:Не те сватив баш, може псевдо код за делот со рекурзија

За backtracking? Отвори го ова предавање http://mendo.mk/Lecture.do?id=31 и види ја Програма 10.1 со пермутациите. Пермутации (на кратко) е како можеш да наредиш одреден број на елементи. На пример, има шест пермутации од [1, 2, 3], и тоа се: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2] и [3, 2, 1].
Мислам дека е поприлично јасно таму дадена програмата (со коментари и све). Види како во 40-ти ред имаме рекурзивен повик и што се случува потоа (42-46 ред). Тој вториот дел е она за што зборував погоре.
MODDI



Joined: 27/12/2017 18:17:00
Messages: 35
Offline


Пишував ново решение со рекурзија, ми работи на 2 тест примери, на 5 ми дава погрешен резултат, а на останатите runtime error, HELP PLS
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team