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



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

Ај ако може некој да ми даде идеја како да ја решам задачава, најпрво кога ја погледнав ми текна да ја проверувам цела низа бидејќи може да биде само до 4x5 ама таа може да почне од било кој единица кој е во матрицата и не смее да оди на единица која веќе е помината. Малку помош?
MOI



Joined: 07/07/2010 16:31:48
Messages: 440
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

KRISS



Joined: 15/01/2019 12:19:43
Messages: 1
Offline


Ја решавав оваа задача со ДФС. но ми работи само на 32/50 малку помош!!!
longhi



Joined: 16/01/2019 22:52:02
Messages: 15
Offline

KRISS wrote:Ја решавав оваа задача со ДФС. но ми работи само на 32/50 малку помош!!!

Ти работи на многу примери оти се одговорите со ДА или НЕ. На натпревар ако се дадени во групи ќе имаш малку бодови.
Решението не ти е со рекурзија ниту некој вид DFS, туку само на алгоритамот BFS имаш заменето queue со stack.

Целта на решението објаснето во коментарот над твојот е ако почнуваш од 1 (со бројки означуваме поле), да ги посетиш (ова е само пример) и [1, 2, 3] и [1, 3, 2], бидејќи тие се различни (од 3 и 2 може да има различни следни чекори).
Кај тебе кога ќе се стави нешто дека е посетено, нема да ги разгледаш другите можности. Види на мендо има предавање за рекузија, па таму примерот со пермутациите.
Ако заглавиш, прашај си пак.
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team