Author |
Message |
02/03/2018 14:56:11
|
MODDI
Joined: 27/12/2017 18:17:00
Messages: 39
Offline
|
Ај ако може некој да ми даде идеја како да ја решам задачава, најпрво кога ја погледнав ми текна да ја проверувам цела низа бидејќи може да биде само до 4x5 ама таа може да почне од било кој единица кој е во матрицата и не смее да оди на единица која веќе е помината. Малку помош?
|
|
|
02/03/2018 15:44:14
|
MOI
Joined: 07/07/2010 16:31:48
Messages: 447
Offline
|
MODDI wrote:Ај ако може некој да ми даде идеја како да ја решам задачава, најпрво кога ја погледнав ми текна да ја проверувам цела низа бидејќи може да биде само до 4x5 ама таа може да почне од било кој единица кој е во матрицата и не смее да оди на единица која веќе е помината. Малку помош?
Една идеја е да користиш рекурзија. Накратко, замисли функција која што ќе ти прима аргументи кои кажуваат: 1) на која единица си во моментот, 2) кои единици се веќе посетени, и 3) кој потег (прв, втор, трет, итн) треба да се преземе. Од 1 и 3 можеш да знаеш кои се следни можни единици: имено, знаеш каде си сега и од 3 знаеш дали да бараш следен елемент во истиот ред или колона - и со рекурзија да ги испробаш сите можни потези (од 2 знаеш кои се веќе посетени).
Во главната функција можеш да ја почнеш рекурзија од секоја можна единица. Повеќе за идејата можеш да прочиташ во делот Алгоритми http://mendo.mk/Training.do?cid=6 (предавање "Рекурзија. Враќање наназад").
This message was edited 1 time. Last update was at 02/03/2018 15:45:25
|
|
|
15/01/2019 12:21:09
|
KRISS
Joined: 15/01/2019 12:19:43
Messages: 1
Offline
|
Ја решавав оваа задача со ДФС. но ми работи само на 32/50 малку помош!!!
|
|
|
16/01/2019 22:57:30
|
longhi
Joined: 16/01/2019 22:52:02
Messages: 18
Offline
|
KRISS wrote:Ја решавав оваа задача со ДФС. но ми работи само на 32/50 малку помош!!!
Ти работи на многу примери оти се одговорите со ДА или НЕ. На натпревар ако се дадени во групи ќе имаш малку бодови.
Решението не ти е со рекурзија ниту некој вид DFS, туку само на алгоритамот BFS имаш заменето queue со stack.
Целта на решението објаснето во коментарот над твојот е ако почнуваш од 1 (со бројки означуваме поле), да ги посетиш (ова е само пример) и [1, 2, 3] и [1, 3, 2], бидејќи тие се различни (од 3 и 2 може да има различни следни чекори).
Кај тебе кога ќе се стави нешто дека е посетено, нема да ги разгледаш другите можности. Види на мендо има предавање за рекузија, па таму примерот со пермутациите.
Ако заглавиш, прашај си пак.
|
|
|
|
|
|