Pagalbos su c++

http://www.part.lt/img/e262a46d0ad60fcd8493fcb744482811222.PNG

Sveiki, reikia pagalbos su užduotimi, nežinau nuo ko pradėti.

Dėkui, bet tikėjaus kažko konkretesnio. Nežinau kaip turėtų atrodyt algoritmas, kuris rastų ilgiausią maršrutą.

Raktiniai žodžiai: grafas, paieška gilyn (DFS).

Raktiniai žodžiai: grafas, paieška gilyn (DFS).

Pirdunai KTU profesoriai, sita uzduoti duoda metai is metu pirmam kurse, nors diskreciaja matematika mokomes ir grafus paciupent gaunam tik antram kurse :) Praktiskai kiekvienas gaves sita uzduoti labai prasikankina. Pats dabar grafus pradejau mokytis tai lengvesne atrodo uzduotis nei pries lygiai metus :)

Nu ir pataikei, aš pirmakursis iš ktu ir niekur dar nesu girdėjęs apie tuos grafus :/

Šis uždavinys ko gero iš Kazicko konkurso, kuriame dalyvauja mokiniai nuo 9 klasės. Todėl neįsivaizduokit kad čia kažkas stebuklingo, viskas pakankamai elementaru.

Šis uždavinys ko gero iš Kazicko konkurso, kuriame dalyvauja mokiniai nuo 9 klasės. Todėl neįsivaizduokit kad čia kažkas stebuklingo, viskas pakankamai elementaru.

Ne stebuklinga, bet is patirties sakau, kad mano kurso 50% zmoniu, kuriems reikejo atlikti sita uzduoti, to padaryti neiseijo :)

Šis uždavinys ko gero iš Kazicko konkurso, kuriame dalyvauja mokiniai nuo 9 klasės. Todėl neįsivaizduokit kad čia kažkas stebuklingo, viskas pakankamai elementaru.

Kas vienam elementaru, kitam gali būti neįkandama

Gal galite kas nors užvest ant kelio and bent paaiškint pirmakursiui kaip man čia pritaikyt tuos grafus? Ar turiu nusiskaityti viršūnes ir briaunas į atskyras klases? Ar turėčiau naudoti atskyrus masyvus vienos klasės viduje briaunom ir viršūnėm? Nes pakolkas tai viską nuskaičiau į vieną klasę. C++ pradėjau vos nuo rugsėjo, prieš tai programavau paskaliu, tad pasistenkit būt kuo paprastesni.

O tu gal Vytauto Žemkalnio gimnaziją baigęs? :) Čia šiaip tik dėl nick'o teiraujuos.

O tu gal Vytauto Žemkalnio gimnaziją baigęs? :) Čia šiaip tik dėl nick'o teiraujuos.

Taip, Panevėžio VŽG

Paisdarai iš tų visų miestų grafų taškus, po to sujungi (nu čia jau neaiškinsiu, ne į filologiją įstojai kad nepadarytum). Tada pasigooglini apie tokį metodą *Depth first search*, pritaikai jį iš tavo pradinio taško ir valio.

Paisdarai iš tų visų miestų grafų taškus, po to sujungi (nu čia jau neaiškinsiu, ne į filologiją įstojai kad nepadarytum). Tada pasigooglini apie tokį metodą *Depth first search*, pritaikai jį iš tavo pradinio taško ir valio.

Grafų taškus? Turi omeny jų viršūnes sudėt į atskyrus masyvus?

Masyvo tai nelabai tau čia reikia. Pasidarai kiekvienam miestui po kokį nors tai objektą (gali objektą daryti, jeigu nori labiau C, tai struktūrą, skirtumo jokio), objekte turi parametrus kaip pavadinimas ir rodyklės į kitus tokius objektus (kokį masyvą šitam pasidaryk), su rodyklėm dar kaip nors paraleliškai saugok atstumą (referencui, šitas dalykas vadinamas svoriu, gal rasi kur minint tokį dalyką). Tada kai turi kiekvienam miestui po kokį nors objektą, pradedi pagal tą grafiką kur turi, sujunginėti tas rodykles (čia vėl, krūvos metodų yra, susirasi internete koks labiau patiks).

Masyvo tai nelabai tau čia reikia. Pasidarai kiekvienam miestui po kokį nors tai objektą (gali objektą daryti, jeigu nori labiau C, tai struktūrą, skirtumo jokio), objekte turi parametrus kaip pavadinimas ir rodyklės į kitus tokius objektus (kokį masyvą šitam pasidaryk), su rodyklėm dar kaip nors paraleliškai saugok atstumą (referencui, šitas dalykas vadinamas svoriu, gal rasi kur minint tokį dalyką). Tada kai turi kiekvienam miestui po kokį nors objektą, pradedi pagal tą grafiką kur turi, sujunginėti tas rodykles (čia vėl, krūvos metodų yra, susirasi internete koks labiau patiks).

Dėkui :)

Masyvo tai nelabai tau čia reikia. Pasidarai kiekvienam miestui po kokį nors tai objektą (gali objektą daryti, jeigu nori labiau C, tai struktūrą, skirtumo jokio), objekte turi parametrus kaip pavadinimas ir rodyklės į kitus tokius objektus (kokį masyvą šitam pasidaryk), su rodyklėm dar kaip nors paraleliškai saugok atstumą (referencui, šitas dalykas vadinamas svoriu, gal rasi kur minint tokį dalyką). Tada kai turi kiekvienam miestui po kokį nors objektą, pradedi pagal tą grafiką kur turi, sujunginėti tas rodykles (čia vėl, krūvos metodų yra, susirasi internete koks labiau patiks).

Kaip suprasti "Pasidarai kiekvienam miestui po kokį nors tai objektą"? Juk aš nežinau kokie ir kiek tų miestų bus. Sorry, kad tokie buki mano klausimai, tiesiog nesu aš labai pežengęs

Kaip suprasti "Pasidarai kiekvienam miestui po kokį nors tai objektą"? Juk aš nežinau kokie ir kiek tų miestų bus. Sorry, kad tokie buki mano klausimai, tiesiog nesu aš labai pežengęs

Susikuri standartine klase (ar struktura, nors struktura irgi klase, tik fieldai pagal nutylejima public)saugot miesto duomenims ir prisikuri tiek skirtingu objektu, kiek rasi skirtingu miestu.

Susikuri standartine klase (ar struktura, nors struktura irgi klase, tik fieldai pagal nutylejima public)saugot miesto duomenims ir prisikuri tiek skirtingu objektu, kiek rasi skirtingu miestu.

nesuprantu, miestai juk jokių duomenų neturi, tik miesto vardą

Susikuri standartine klase (ar struktura, nors struktura irgi klase, tik fieldai pagal nutylejima public)saugot miesto duomenims ir prisikuri tiek skirtingu objektu, kiek rasi skirtingu miestu.

pasidarau klasę, sudedu į ją miestų vardus ir kas tada? kur saugot grafų svorius?

nesuprantu, miestai juk jokių duomenų neturi, tik miesto vardą

 

 

pasidarau klasę, sudedu į ją miestų vardus ir kas tada? kur saugot grafų svorius?

Kaip tai neturi, o tai jungtys su kitais miestais? Cia yra pats svarbiausias dalykas miestui apibudint, koks skirtumas ten tas pavadinimas, gali pasikeist visus i a,b,c... Svarbu i kur gali nukeliaut is jo ir koks atstumas kelio.

Kaip tai neturi, o tai jungtys su kitais miestais? Cia yra pats svarbiausias dalykas miestui apibudint, koks skirtumas ten tas pavadinimas, gali pasikeist visus i a,b,c... Svarbu i kur gali nukeliaut is jo ir koks atstumas kelio.

tai klasėje turi būti miesto vardas ir masyvas su kaimynais miestais?

tai klasėje turi būti miesto vardas ir masyvas su kaimynais miestais?

Taip. Ir dar kazkur atstumai, kad ir kitam masyve, vienoda tvarka sudeta. Aisku cia viskas priklauso koki sprendimo budo renkiesi, nes sprendziant dabar is tokiu klausimu tai vis dar nera supratimo, kaip sprest.

Taip. Ir dar kazkur atstumai, kad ir kitam masyve, vienoda tvarka sudeta. Aisku cia viskas priklauso koki sprendimo budo renkiesi, nes sprendziant dabar is tokiu klausimu tai vis dar nera supratimo, kaip sprest.

na kaip aukščiau sakė žmonės, tai bandysiu naudot tą paiešką į gylį

Paprasčiausia paieška į plotį ar į gylį čia neveiks, nes reikia rasti ne kelią kuris aplankytų daugiausia miestų, o kelią kuris būtų ilgiausias nesilankant tame pačiame mieste kelis kartus. Šiaip šios problemos sudėtingumas NP, tačiau tavo atveju grafas neturi ciklų, kas šioj situacijoj labai gelbėja. Gali pabandyti įgyvendinti kažką panašaus į http://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

Taip. Ir dar kazkur atstumai, kad ir kitam masyve, vienoda tvarka sudeta. Aisku cia viskas priklauso koki sprendimo budo renkiesi, nes sprendziant dabar is tokiu klausimu tai vis dar nera supratimo, kaip sprest.

o miesto vardus string ar char saugot? Ir išvis koks tarp jų skirtumas? nes bent paskaly, tai aišku, kad vienam simboliui, o string eilutei

Paprasčiausia paieška į plotį ar į gylį čia neveiks, nes reikia rasti ne kelią kuris aplankytų daugiausia miestų, o kelią kuris būtų ilgiausias nesilankant tame pačiame mieste kelis kartus. Šiaip šios problemos sudėtingumas NP, tačiau tavo atveju grafas neturi ciklų, kas šioj situacijoj labai gelbėja. Gali pabandyti įgyvendinti kažką panašaus į http://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

blemba aš net tų grafų nesuprantu, nieko dar nesimokėm apie juos, tą paiešką į gylį vos supratau kaip veikia, bet dar net nežinau kaip užrašyt reiks, o tu man dar kažkokių keistų dalykų duodi, kurių aš nėkiek nesuprantu. būkit jūs biški paprastesni, aš dar tik pirmakursis ir dabar esu nebesveikai pasimetęs ar tikrai man čia reikėjo stot :/

Paprasčiausia paieška į plotį ar į gylį čia neveiks, nes reikia rasti ne kelią kuris aplankytų daugiausia miestų, o kelią kuris būtų ilgiausias nesilankant tame pačiame mieste kelis kartus. Šiaip šios problemos sudėtingumas NP, tačiau tavo atveju grafas neturi ciklų, kas šioj situacijoj labai gelbėja. Gali pabandyti įgyvendinti kažką panašaus į http://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

o darant tą "paprasčiausią" paiešką į gylį, aš juk galiu saugoti visus kelius kokiam nors masyve ir kai apeinu visus galimus variantus, tada tiesiog iš to masyvo atrenku patį ilgiausią. Ar turi pasiūlyti kažką lengvesnio ar šiaip geresnio?