Pagalbos su c++

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.

 

būkit jūs biški paprastesni, aš dar tik pirmakursis ir dabar esu nebesveikai pasimetęs ar tikrai man čia reikėjo stot :/

 

C++ tas pats, string - eilute, char - simbolis. O del stojimo, tai siulau nepanikuot taip, nes sita uzduotis yra ryskiai sunkesne nei kitu variantu to pacio laboro, kaip ir sakiau, is papirties 50% dariusiuju sita uzduoti kiek man teko girdet nesugebejo jos atlikt, o jie vis dar studijuoja ir jau kitam kurse :)

Pradėkim nuo to, kas yra grafas. O tai yra tiesiog viršūnių aibė su jungtimis (briaunomis) tarp jų. Viso labo tiek.

Kaip atvaizduoti grafą? Tarkim, viršūnes vadinkim skaičiais nuo 0 iki n. O kaip tada apibūdinti briaunas? Briauna jungia dvi viršūnes, todėl tų viršūnių indeksai ir parodys briauną.

Paprasčiau apsirašyti grafą:

list g[];

Jeigu turim viršūnę i, tai g[ i] bus sąrašas viršūnių, su kuriomis jungiasi viršūnė i, bei atstumai iki jų.

Šiam uždaviniui išspręsti užtenka šiek tiek pa'pimp'intos paieškos į gylį.

Kaip veikia paieška į gylį? Ateini į viršūnę v. Iš sąrašo viršūnių, su kuriomis jungiasi v, išsirenki pirmą viršūnę, tarkim, u. Tada eini į viršūnę u, peržiūri jos sąrašą. Jeigu giliau negali lįsti, grįžtu į viršūnę v, išsirenki iš jos sąrašo kitą viršūnę ir eini gilyn į ją.

Bet viskas ne taip paprasta. Kas jeigu iš v ateisiu į u, iš u į w, o w jungiasi su v? Kad nepradėtum vaikščioti ratu, reikia pasižymėti, kokiose viršūnėse jau lankeisi, ir į jas daugiau neiti.

Paklausi, o kaip su atstumu? Elementaru, Vatsonai! Prie kiekvienos viršūnės saugai ilgiausio kelio nuo pradinės viršūnės iki dabartinės ilgį. Tada išvaikščiojęs visą grafą, susirasi viršūnę, kurios atstumas yra didžiausia – čia ir užsibais kelionė.

Aha, o atstumo nepakanka! Reikia įvardinti ir maršrutą! Maršrutą galime lengvai atgaminti atgaliniu būdu. Jeigu iš viršūnės v ateinu į u, tai taip ir pasižymiu:

previous[u] = v;

Tada, kai pagaliau surasi tolimiausią viršūnę, pasižiūrėsi, iš kurios atėjai į jąją. Tada pasižiūrėsi, iš kurios atėjai į pastarąją, taip atgamindamas kelią. Taip ieškosi prieš tai buvusių viršūnių, kol galiausiai pasieksi pradinę.

Belieka tik kiekvienam miestui priskirti viršūnės indeksą. Tada programos pabaigoje iš indeksų atgaminsi miestų pavadinimus.

Nei daug, nei mažai. Visą šią užduotį labai palengvintų STL (Standard Template Library) duomenų struktūros.

Visa paieška gilyn lengvai apsirašo su rekursija.

Pradėkim nuo to, kas yra grafas. O tai yra tiesiog viršūnių aibė su jungtimis (briaunomis) tarp jų. Viso labo tiek.

 

Kaip atvaizduoti grafą? Tarkim, viršūnes vadinkim skaičiais nuo 0 iki n. O kaip tada apibūdinti briaunas? Briauna jungia dvi viršūnes, todėl tų viršūnių indeksai ir parodys briauną.

 

Paprasčiau apsirašyti grafą:

list g[];

Jeigu turim viršūnę i, tai g[ i] bus sąrašas viršūnių, su kuriomis jungiasi viršūnė i, bei atstumai iki jų.

 

Šiam uždaviniui išspręsti užtenka šiek tiek pa'pimp'intos paieškos į gylį.

 

Kaip veikia paieška į gylį? Ateini į viršūnę v. Iš sąrašo viršūnių, su kuriomis jungiasi v, išsirenki pirmą viršūnę, tarkim, u. Tada eini į viršūnę u, peržiūri jos sąrašą. Jeigu giliau negali lįsti, grįžtu į viršūnę v, išsirenki iš jos sąrašo kitą viršūnę ir eini gilyn į ją.

 

Bet viskas ne taip paprasta. Kas jeigu iš v ateisiu į u, iš u į w, o w jungiasi su v? Kad nepradėtum vaikščioti ratu, reikia pasižymėti, kokiose viršūnėse jau lankeisi, ir į jas daugiau neiti.

 

Paklausi, o kaip su atstumu? Elementaru, Vatsonai! Prie kiekvienos viršūnės saugai ilgiausio kelio nuo pradinės viršūnės iki dabartinės ilgį. Tada išvaikščiojęs visą grafą, susirasi viršūnę, kurios atstumas yra didžiausia – čia ir užsibais kelionė.

 

Aha, o atstumo nepakanka! Reikia įvardinti ir maršrutą! Maršrutą galime lengvai atgaminti atgaliniu būdu. Jeigu iš viršūnės v ateinu į u, tai taip ir pasižymiu:

previous[u] = v;

Tada, kai pagaliau surasi tolimiausią viršūnę, pasižiūrėsi, iš kurios atėjai į jąją. Tada pasižiūrėsi, iš kurios atėjai į pastarąją, taip atgamindamas kelią. Taip ieškosi prieš tai buvusių viršūnių, kol galiausiai pasieksi pradinę.

 

Belieka tik kiekvienam miestui priskirti viršūnės indeksą. Tada programos pabaigoje iš indeksų atgaminsi miestų pavadinimus.

 

Nei daug, nei mažai. Visą šią užduotį labai palengvintų STL (Standard Template Library) duomenų struktūros.

 

Visa paieška gilyn lengvai apsirašo su rekursija.

Na va, kažką manau supratau, o apie rekursijas, tai jų dar irgi nesimokėme.

O tą list reikia į klasę rašyt ar jis tiesiog kaip koks atskyras masyvas?

Na va, kažką manau supratau, o apie rekursijas, tai jų dar irgi nesimokėme.

O tą list reikia į klasę rašyt ar jis tiesiog kaip koks atskyras masyvas?

Jeigu dėstytojas nereikalauja, kad darytum su klasėmis, tai geriausia tiesiog kaip atskirą masyvą.

Jeigu dėstytojas nereikalauja, kad darytum su klasėmis, tai geriausia tiesiog kaip atskirą masyvą.

reikia su konteinerinėm klasėm, bet aš nežinau kaip čia aprašyt su jom