Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
Dlaprzykładuzrys.3otrzymalibyśmynastępującyciągprzecięć:
2s,4s,8s,10s,11s,11n,10n,8n,8s,9n,5n,2n,
gdzienoznacza,żerybapłynęłanapółnoc,as-żenapołudnie.Usuwając
iteracyjniesąsiadującezesobąprzecięciadotyczącetejsamejbariery,dostajemy
następującyciągprzecięć(pogrubionazostałaparausuwanawdanymkroku):
1.2s,4s,8s,10s,11s,11n,10n,8n,8s,9n,5n,2n,
2.2s,4s,8s,10s,10n,8n,8s,9n,5n,2n,
3.2s,4s,8s,8n,8s,9n,5n,2n,
4.
2s,4s,8s,9n,5n,2n(trasajestwrzeczywistościcykliczna,więcuznajemy,
żeostatnielementsąsiadujezpierwszym),
5.4s,8s,9n,5n.
Przecięciadozignorowaniamożnawyznaczyćwczasieliniowympodczas
wyznaczaniabarier,któredanatrasaprzecina.Wtymcelumożnanapotkane
nadanejtrasieprzecięciapamiętaćnastosie.Ponapotkaniunowegoprzecięcia
wystarczysprawdzić,czyniedotyczyonotejsamejbarierycopoprzednieijeśli
takjest,toobaprzecięcianależyusunąć.Nakoniecwystarczyusuwaćpierwsze
iostatnieprzecięcietakdługo,jakdługodotycząonetejsamejbariery.Podczas
usuwaniaprzecięćmożnanieuwzględniaćwogólekierunkuprzecięć,gdyżryba
niemożeprzekroczyćdwarazyzrzędutejsamejbarieryztejsamejstrony.
Takutworzonyciągbędziemynazywaćreprezentacjądladanejtrasy.Kierunek
przecięćmaznaczeniejedynieprzyporównywaniureprezentacjidlaróżnych
tras,gdyżpozwalaodróżnićrybęopływającąwyspęzgodniezkierunkiemruchu
wskazówekzegaraodrybyopływającejtęwyspęwkierunkuprzeciwnym.
Równoważnośćcykliczna
Okazujesię,żedwiepowstałetrasysąrównoważnewtedyitylkowtedy,kiedy
ichreprezentacjesąrównoważnecyklicznie*.Fakttenpozostawimybezdo-
wodu,aleCzytelnikmożeprzekonaćsięotym,analizującprzykładowetrasy
ryb.Opisymogąbyćprzesuniętecyklicznie,ponieważcykliczneprzesunięcie
trasyzależyodmiejsca,wktórymrybarozpoczęłaswojąwędrówkę,co,jak
wiemy,niewpływanarównoważnośćtras.
*
Dwaciąginazywamyrównoważnymicyklicznie,jeślipewnecykliczneprzesunięciejednego
ciągujestrównedrugiemuciągowi.Cykliczneprzesunięciesłowaa1a2…a
n
tokażdesłowopostaci
aiai+1…ana1a2…ai−1.
marcinandrychowicz/ryby
39
