lmx Ierakstīts Janvāris 8, 2005 Share Ierakstīts Janvāris 8, 2005 Sveicinaati! Probleema ir sekojosha - jaaatrod dazhaado celju skaits starp 2 orienteeta grafa virsotneem (konkreetaak - starp grafa ieejaam un izejaam). Pashi celji nav vajadziigi, tikai skaits. It kaa bija sanaacis kaut kas apmeeram straadaajoshs, tikai kaaraas, ja grafaa paraadiijaas cikli. Grafs ir uzdots ar blakus virsotnu matricu, bet var arii tikt pie incidences matr. Varbuut kaads ir saskaaries ar ko liidziigu, vai zin kaadu gatavu algoritmu? Paldies jau ieprieksh Link to comment Share on other sites More sharing options...
lmx Janvāris 8, 2005 Author Share Janvāris 8, 2005 nu jaa, katraa celjaa viena virsotne vai loks var atkaartoties tikai 1 reizi Link to comment Share on other sites More sharing options...
VIL Janvāris 8, 2005 Share Janvāris 8, 2005 Man ir zināmi veseli divi algoritmi - apstaigāšana dziļumā un apstaigāšana plašumā. P.S. Aņuks: Cilvēks jautā programmētājam, kas ir koks. Šis atbild - sakarīgs mežs. Šito atcerējos, tiklīdz kolēga pieminēja ciklus. P.P.S. Kurā skolā kurā priekšmetā ir šis mājas darbs? Link to comment Share on other sites More sharing options...
lmx Janvāris 8, 2005 Author Share Janvāris 8, 2005 man gan liekas, ka paarmekleeshanas iisti nederees celju atrashanai Vieniigais risinaajums shobriid shkiet backtracking Link to comment Share on other sites More sharing options...
VIL Janvāris 8, 2005 Share Janvāris 8, 2005 Bet vai šie algoritmi (platumā, dziļumā) pasaka, cik dažādu ceļu ir no virsotnes A līdz virsotnei B? Es teiktu, ka lieliski pasaka. Par dziļumu varu apgalvot droši. Plašumā nekad neesmu izmantojis. Link to comment Share on other sites More sharing options...
Vilx- Janvāris 8, 2005 Share Janvāris 8, 2005 Shos algoritmus var izmantot, lai pateiktu, cik dazjaadu celju ir. Vienkaarshi apstaigaa sho grafu (platumaa vai dziljumaa), un atziimee, kuras virsotnes esi jau apstaigaajis (pieliec virsotnei flagu). Shiis tad otrreiz neapstaigaa. Kad nonaac liidz galam, pieskaiti 1 celju skaitam. Pievienots:Btw - vai ar dazjaadaam apstaigaashanaam nevar buut dazjaads celju skaits? Pievienots 2:Never mind. Apstaigaashana nederees vis. Cik dazjaadu celju ir kvadraatam, kuram savienotas virsotnes pa perimetru un viena diagonaale? Apstaigaashana saakas vienaa no virsotneem, kurai ir tikai 2 skjautnes, un beidzas otraa shaadaa pashaa virsotnee. :? Link to comment Share on other sites More sharing options...
VIL Janvāris 8, 2005 Share Janvāris 8, 2005 Pievienots 2:Never mind. Apstaigaashana nederees vis. Cik dazjaadu celju ir kvadraatam, kuram savienotas virsotnes pa perimetru un viena diagonaale? Apstaigaashana saakas vienaa no virsotneem, kurai ir tikai 2 skjautnes, un beidzas otraa shaadaa pashaa virsotnee. :? Atbilde: 4 Paņēmiens: DFS Link to comment Share on other sites More sharing options...
lmx Janvāris 8, 2005 Author Share Janvāris 8, 2005 emm, tam kvadraatam shkautnes ir orienteetas? iespeejams, ka ir kaut kaada metode celju skaita apreekjinashanai skaitot/reizinot/kaapinot vai kaut kaa tml paarveidojot blakus virsotnu matricu, bet tas tikai man liekas, kaa ir patiesiibaa, kas to lai zin. Link to comment Share on other sites More sharing options...
VIL Janvāris 8, 2005 Share Janvāris 8, 2005 emm, tam kvadraatam shkautnes ir orienteetas? iespeejams, ka ir kaut kaada metode celju skaita apreekjinashanai skaitot/reizinot/kaapinot vai kaut kaa tml paarveidojot blakus virsotnu matricu, bet tas tikai man liekas, kaa ir patiesiibaa, kas to lai zin. Vai Tev uzdevuma prasībās ir aizliegts apstaigāt grafu dziļumā un pateikt, cik reizes izdevās nokļūt galapunktā? ----> Atcerējos vēl vienu labu lietu. Kad vēl LU FMF mācījos, tur mēs apskatījām tādu štelli kā dinamisko programmēšanu. Uzdevuma nostādne bija tāda: dota valūtas kursu tabula. Noteikt, vai ir iespējams valūtas samainīt ar peļņu un uzrādīt risinājumus. Man pie valūtu skaita n sanāca O(n^3). Šis faktiski ir tieši tāds pats uzdevums. Link to comment Share on other sites More sharing options...
Vilx- Janvāris 9, 2005 Share Janvāris 9, 2005 Duh! Protams! Kaut kaads melnais bija uznaacis! DFS der vienmeer! Bruteforce 4ever (kaa teiktu Pokemoni). Iisteniibaa, es pat nevaru iedomaties nevienu citu veidu. BFS arii nederees, manupraat. Vai arii tomeer? :? Link to comment Share on other sites More sharing options...
VIL Janvāris 9, 2005 Share Janvāris 9, 2005 Duh! Protams! Kaut kaads melnais bija uznaacis! DFS der vienmeer! Bruteforce 4ever (kaa teiktu Pokemoni). Iisteniibaa, es pat nevaru iedomaties nevienu citu veidu. BFS arii nederees, manupraat. Vai arii tomeer? :? Ja Tu būtu turpinājis sākotnēji izteikto domu, es biju gatavs uzdot šīs nedēļas TOP jautājumu: ko pīpē? BFS aspektus tagad nepateikšu. Pats nekad neesmu izmantojis, bet grāmatu ar ēzeli esmu palienējis tiem, kam vairāk vajadzīga. Intuitīvi ir tā: ejam dziļumā un pie virsotnēm skaitām ceļus. Beigās jau pie galapunkta nonāksim un ciparus sasummēsim. DFS gadījumā kā nonākam galapunktā, tā skaitītājs+1. Intuitīvi BFS arī strādā. Link to comment Share on other sites More sharing options...
Vilx- Janvāris 9, 2005 Share Janvāris 9, 2005 Ar BFS buus gruutaak deelj tiem cikliem. Nesaku, ka nevar, bet shajaa vakara stundaa praats laaga nenesas vairs uz domaashanu... Arlabunakti! Link to comment Share on other sites More sharing options...
gathis Janvāris 10, 2005 Share Janvāris 10, 2005 izmanto to pashu apieshanu dziljumaa. kad viens celjsh ir iziets, tad lokiem pa kuru izgaajis shis celjs atziimee kaukaa, ka pa shejieni ir iets un atkaarto to visu no gala, liidz briidim, kad vairs nebuus loku pa kurieni iet! Link to comment Share on other sites More sharing options...
Recommended Posts
Izveido kontu, vai pieraksties esošajā, lai komentētu
Jums ir jābūt šī foruma biedram, lai varētu komentēt tēmas
Izveidot jaunu kontu
Piereģistrējies un izveido jaunu kontu, tas būs viegli!
Reģistrēt jaunu kontuPierakstīties
Jums jau ir konts? Pierakstieties tajā šeit!
Pierakstīties tagad!