Gráfos verseny feladat
2019-07-19T23:36:27+02:00
2019-07-22T14:47:23+02:00
2022-07-20T20:17:22+02:00
  • A téma átkerült a társalgóba.
    Mutasd a teljes hozzászólást!
  • El szeretném fogadni xy megildását(aki a kódot írta, nem aki átformázta)
    de nem tudom, mert egyszerűen nincs ott elfogadás megoldásnak gomb.
    Ez miért lehet?
    Már véletlen elfogadtam valakiét, vagy lezárta a témát, vagy mi van?
    Mutasd a teljes hozzászólást!
  • Átelemeztem a kódodat, ugyanolyan tárolási szerkezettel megcsináltam én is 30 at kaptam rá. Nagy felinfultságomba megcsináltam  az 1. ,szintén gráfos feladatot , a tanácsokat követve ,átgondolva , az is 30 as lett 20 perc alatt. Nagyon hálás vagyok a segítségért, további szép nyarat.
    Mutasd a teljes hozzászólást!
  • Inkább újra írom az egészet az itt leírtak szerint.
    Mutasd a teljes hozzászólást!
  • És az Owerflow jelzését nagyon köszönöm, az tényleg okozhat hibás kimenetet. Nemsokára kijavítom,beküldöm aztán meglátjuk mi lesz. Lehet hogy csak maga ez a hiba is sok mindenért felelős...
    Mutasd a teljes hozzászólást!
  • Köszönöm a választ, elrendezem amit mondtatok, de szerintem nem a lassúság okozza, hiszen azt az értértékelőrendszer jelezné. Úgy működik hogy tesztel 30 esetre, és minden tesztesetre kiírja külön hogy mi volt a baj. sokszor volt már időtúllépésem ,de most itt nincsen.A leghosszab idő ami alatt lefutott egy tesztre ,fele a leírásban foglaltaknak, és nem is időtúllépést jelez ,hanem hibás kimenetet.
    Mutasd a teljes hozzászólást!
  • Most ez a"csak" azért van mert az volt a kérdés hogy mi az ami miatt rossz megoldást ad.

    Csak az ember nehezebben szánja rá az idejét egy igénytelen kódra, hogy debuggolja..
    A logikai hibát úgy lehetne legegyszerűbben kiszűrni, ha leírnád az algoritmusod (kerek mondatokban, hogy mit miért, vagy pseudo kóddal)

     Persze az is fontos hogy hogy lesz a kódomból nem egy rakat lassú kaki,

    A lassú kód önmagában okozhatja a nem 100% pontszámot, hiszen memória és futási idő limit is definiálásra kerül a feladat által. A faluk és utak száma pedig felmegy 100k és 500k-ig..
    Tesztelted a futásidőt ilyen nagy bemenetekre? (0.2s a futásidő limit elvileg, persze ez  HW és fordító függő)

    Mert hiába szépítgetem amíg valami logikai hiba miatt rossz eredményt ad.

    Az nem szépítgetés, hogy egy buffer overflow-t javítasz, hanem egy fatális hiba javítása!

    int bm[f+1]; ... while(i<f+2) { bm[i] = 0; // i = f + 1-el túl indexelsz..
    Röviden:
    Logikai hibát egyszerűbb nem csúnya (és hibás) kódból kihámozni, valamint az időkorlát önmagában okozhatja a nem 100%-os eredményt.
    Mutasd a teljes hozzászólást!
  • Értem,rendben, de ezek a dolgok a teljesítményt,az átláthatóságot, normál kód kinézetet befolyásolják "csak". Most ez a"csak" azért van mert az volt a kérdés hogy mi az ami miatt rossz megoldást ad.(pontosabban milyen gráfokra). Tehát valahol kell hogy legyen még benne algoritmikai vagy logikai(nem tudom mi a rendes megfogalmazás így is biztos mindenki megérti) hiba. Persze az is fontos hogy hogy lesz a kódomból nem egy rakat lassú kaki, de odáig is ell kell jutni valahogy. Mert hiába szépítgetem amíg valami logikai hiba miatt rossz eredményt ad.


    Lényeg hogy az lenne az igazi segítség ha erre a logikai hibára világítana rá valaki. Mindenkinek köszi!
    Mutasd a teljes hozzászólást!
  • Lehet indítok egy prog.hu fórum használati képzést

    #include <iostream> using namespace std; int main() { int falvak_szama, utak_szama; cin >> falvak_szama >> utak_szama; int* falvak_fokszama = new int[falvak_szama]; int** szomszedok = new int*[falvak_szama]; for (int i = 0; i < falvak_szama; i++) { falvak_fokszama[i] = 0; szomszedok[i] = new int[2]; } while (utak_szama--) { int honnan, hova; cin >> honnan >> hova; honnan--; hova--; if (falvak_fokszama[honnan] < 2) szomszedok[honnan][falvak_fokszama[honnan]] = hova; if (falvak_fokszama[hova] < 2) szomszedok[hova][falvak_fokszama[hova]] = honnan; falvak_fokszama[honnan]++; falvak_fokszama[hova]++; } int leghosszabb_ut = 0, kiindulo_falvak_szama = 0, *kiindulo_falvak = new int[falvak_szama]; for (int i = 0; i < falvak_szama; i++) { if (falvak_fokszama[i] != 1) continue; int ut = 1, elozo = i, aktualis = szomszedok[i][0]; while (falvak_fokszama[aktualis] == 2) { ut++; if (elozo == szomszedok[aktualis][0]) { elozo = aktualis; aktualis = szomszedok[aktualis][1]; } else { elozo = aktualis; aktualis = szomszedok[aktualis][0]; } } if (leghosszabb_ut == ut) kiindulo_falvak[kiindulo_falvak_szama++] = i; else if (leghosszabb_ut < ut) { leghosszabb_ut = ut; kiindulo_falvak_szama = 1; kiindulo_falvak[0] = i; } } if (leghosszabb_ut == 0) cout << -1; else { cout << leghosszabb_ut << '\n'; for (int i = 0; i < kiindulo_falvak_szama; i++) cout << kiindulo_falvak[i] + 1 << ' '; } return 0; }
    Mutasd a teljes hozzászólást!
  • Na belepillantottam a kódodba. A következőek az észrevételeim:
     - A változóknak tényleg adj rendes nevet, ez nem minél rövidebb forráskódú verseny, mellesleg kommentet sem adtál mindegyikhez (de inkább rendes nevet adj!)
     - A helyesírás nem az erősséged, a kommentekben kifejezetten zavaró.
     - Az 1-től való indexelés miatt több memóriát használsz feleslegesen, de az elemek (pl. a zsákfalvak) számosságát is hozzáigazítod ehhez, így azok is elemszám+1 értéket vesznek fel.
     - Szükségtelen logikai változókat vezetsz be, pl. a 'zs' változó helyett a zsákfalvak számát is megnézhetnéd, 'ih' helyett 'k' értékét a 'while(ih)' sorban, 'z' helyett 'x', 'maxi' helyett pedig semmi, mert egyáltalán nem használod.
     - Az int i = 1; while( i < [...] ) { [...]; i++; } helyett írhatod egyetlen sorban, hogy
    for( int i = 1; i < [...]; i++) { [...] }
     - A cin >> x; cin >> y; helyett egyetlen sorban
    cin >> x >> y;
     - Sok fogalmat rosszul használsz. Tudod, mi az a bitmap? És az alias?
     - Ha már megvan, hogy egy falu hányszor szerepelt a bemeneten, akkor minek számolod újra össze, hogy hány irányba lehet továbbhaladni? Itt jön szóba, hogy nem választottál hatékony tárolási módot, mert másképp nem kéne megkeresni újra és újra a falvakat.
     - A program legelején az utak és falvak számát miért ellenőrzöd? Ha nincs út, akkor nincs zsákfalu sem.
     - Az e és m tömböket nem kell nullázni, mert rögtön utána minden elemének adsz új értéket.
    Ezekre az apróságokra akkor is figyelj (és érdemes őket kijavítani), ha ennek ellenére maximális pontszámot ad az értékelő. Én pl. most vettem észre, hogy abban a megoldásban, amit
    küldtem nem szabadítottam fel delete[] segítségével a lefoglalt memóriaterületeket, ám ezt a mester egyáltalán nem ellenőrzi, viszont a valóságban fontos lett volna ügyelnem rá (már nem tudom szerkeszteni a hozzászólást).
    Mutasd a teljes hozzászólást!
  • Amúgy elvi szinten szerintem nincs túl nagy különbség, csak a megvalósítás egy kicsit más.
    Mutasd a teljes hozzászólást!
  • Leírom, azt hogy én hogyan gondolkodtam.
    A bemenet 1. oszlopát egy tömbben gyűjtöttem 1-től indexelve,ugyanígy a 2. oszlopot is.
    A beolvasás közben bittérképen növeltem az éppen beolvasott csúcsot.
    Létrehoztam külön a zsákfalvaknak egy tömböt,amibe azokat az elemeket tettem bele amik a bittérképen 1 es értékkel szerepelnek(1 út vezet, belőlük, 1 szer szerepelnek a bemeneten).
    Utána ciklust indítottam ami végigment a zsákfalvak tömb elemein( a zsákfalvakon).
    Ebbe a ciklusba beágyaztam egy második ciklust ami a 2 tömb( amikben a bemenet 1. ,és amiben a 2. oszlopa van) elemein egyszerre megy végig(ahány sora van a bemenetnek annyiszor).
    Ha a 2 tömb egyikében megtalálta azt a zsákfalvat aminél éppen a külső ciklus járt ,és az nem volt nem az volt, mint ahonnan jött(ha jött valahonnan), akkor amelyik oszlopban találta , vette az ugyanannyiadik elemét a másik oszlopnak , és azon hajtotta végre ugyanezt,közben a db számot növelte. 
    Na ez így elég zavaros lehet de kóddal együtt talán könnyebben érthetővé vált.
    A biztonság kedvéért csatolom a a forrásfájlt, hátha az én szellemi vagy a progponthu egyéb hiányasságaiból adódóan megint valami más jön ki mint aminek kéne....
    Kód:



    #include <iostream> using namespace std; int main() { int u,x,y,f; // U=UTAK SZÁMA F=FALVAK SZÁMA cin>>u; cin>>f; if(u==0&&f==1) { cout<<0<<endl; cout<<1; return 0; } int bm[f+1];//BITTÉRKÉP int e[u+1];//BEMENET 1.OSZLOPA int m[u+1];//BEMEET 2. OSZLOPA int zsf[f+1];//ZSÁKFALVAK //--------------------------------- int i=1; while(i<f+2) { bm[i]=0; //BITMAP 0 ÁZÁSA i++; } i=1; while(i<u+2) { e[i]=0; m[i]=0; //bemenet 2 oszlopát tartalmazni fogó tömb 0 ázása i++; } //--------------------------------- i=1; while(i<u+1) { cin>>x; cin>>y; bm[x]++; bm[y]++; m[i]=y; e[i]=x; //INPUT i++; } i=1; //---------------------------------- int s=1; bool zs=false; // ha van zsákfalu akkor IGAZ i=1; while(i<f+1) { if(bm[i]==1) // ha egyszer szerepel a bemeneten alias zsákfalu akkor beteszi a zsákfalvakat tartalmazó tömbbe { zs=true; zsf[s]=i; //zsákfalvak keresése s++; } i++; } //------------------------------------ i=1; int elozo=-1,k; int z; int j=1; bool ih; int db; int sor; int max=0; int mt[f+2]; int maxi=0; //------------------------------------ while(i<s)// végigmegy a zsákfalvakat tartalmazÓ tömbbön { db=0; x=zsf[i]; ih=true; elozo=-1; while(ih) { j=1; k=0; while(j<u+1) //MEGKERESI A 2 TÖMBBEN A ZSÁKFALUT { if(e[j]==x && j!=elozo)//számolja hogy hány irányba lehet innen továbbhaladni { z=m[j]; sor=j; k++; } if(m[j]==x && j!=elozo) //számolja hogy hány irányba lehet innen továbbhaladni { z=e[j]; sor=j; k++; } j++; } if(k==1) // ha innen csak egy irányba lehet továbbhaladni akkor erre megismétli az eljárást { elozo=sor; db++; x=z; } else// ha 1 nél több irányba lehet innen továbbhaladni , akkor ennek a zsalfalunak a vizsgálata véget ért { ih=false; } } mt[i]=db; if(db>max) // maximum kiválasztás { max=db; maxi=i; } i++; } //------------------------------------ if(zs)//ha van zsákfalu, végeredmény kiiratása ha nincs -1 kiiratása a feladat leirása szerint { cout<<max<<endl; i=1; while(i<s) { if(mt[i]==max) { cout<<zsf[i]<<" "; } i++; } } else { cout<<"-1"; } return 0; }
    Mutasd a teljes hozzászólást!
    Csatolt állomány
  • Szia!

    Kíváncsiságból megoldottam a feladatot. Nem olvastam el a kódot, amit írtál, mert így elég átláthatatlan. Adok pár tanácsot ezekhez a feladatokhoz (amiket lehet, hogy ismersz, de legalább megerősítésnek jó lesz).
     - Használj rendes változóneveket, akkor másnak is könnyebb átlátni a kódot, és neked is könnyebb, ha valamennyi idő után folytatod a programot vagy megnéznéd, hogyan is oldottad meg, nem kell visszakeresni a kommentek közé, hogy milyen funkciót látnak el. Leírni valószínűleg nem lesz több idő, ha használsz fejlesztői környezetet, akkor az automatikusan felajánlja kiegészíteni a megkezdett szót.
     - Senki nem fog több pontot adni arra, hogy kommentben vonalakkal elválasztod a részeket, inkább rakj egyszerű sortörést, sokkal gyorsabb, következetesebb, ez nem egy könyv lesz.
     - Gondold végig, hogy mire kíváncsi a feladat, feleslegesen ne dolgozz, nem kell sem általánosítani a problémát, sem több információt összegyűjtenie/tárolnia az algoritmusnak.
     - Gráfok esetében sokféleképpen lehet eljárni. Mielőtt az összes feladatot megoldanád, nézz utána, milyen tárolási módok, bejárások, tipikus algoritmusok vannak, milyen esetekben melyeket célszerű használni, esetleg C++ implementálása is érdekes lehet.

    A feladattal kapcsolatban:
    Nyilván csak az 1 fokú csúcsból induló, 2 fokú csúcsokon át haladó utak érdekesek. Én emiatt inkább nyilvántartottam a csúcsok fokszámát, és szomszédot csak akkor tároltam egy csúcshoz, ha az még nem volt 2 fokú. Tehát 2 szomszéd tárolásával már meg lehet oldani, az úton haladáskor kell csak ellenőrizni, hogy a következő csúcs ne az előző legyen. Korábban érintett csúcsra úgysem léphetünk rá többször, hisz egy csúcsra egy élen be, egyen meg kimentünk, az meg pont 2, viszont 1 fokú csúcsról indulunk, tehát nem teszünk semmiképpen kört. A tárolásra lehetne használni szomszédossági tömböt is (akár láncolt listával), de annak a feltöltése ebben a feladatban bonyolultabb, kiolvasásnál pedig most nem nyerünk semmit, más feladatoknál bőven megéri használni. Esetleg nézd át a megoldásom, mester 30-at adott rá.

    #include <iostream> using namespace std; int main() { int falvak_szama, utak_szama; cin >> falvak_szama >> utak_szama; int *falvak_fokszama = new int[falvak_szama]; int **szomszedok = new int*[falvak_szama]; for(int i = 0; i < falvak_szama; i++) { falvak_fokszama[i] = 0; szomszedok[i] = new int[2]; } while(utak_szama--) { int honnan, hova; cin >> honnan >> hova; honnan--; hova--; if(falvak_fokszama[honnan] < 2) szomszedok[honnan][falvak_fokszama[honnan]] = hova; if(falvak_fokszama[hova] < 2) szomszedok[hova][falvak_fokszama[hova]] = honnan; falvak_fokszama[honnan]++; falvak_fokszama[hova]++; } int leghosszabb_ut = 0, kiindulo_falvak_szama = 0, *kiindulo_falvak = new int[falvak_szama]; for(int i = 0; i < falvak_szama; i++) { if(falvak_fokszama[i] != 1) continue; int ut = 1, elozo = i, aktualis = szomszedok[i][0]; while(falvak_fokszama[aktualis] == 2) { ut++; if(elozo == szomszedok[aktualis][0]) { elozo = aktualis; aktualis = szomszedok[aktualis][1]; } else { elozo = aktualis; aktualis = szomszedok[aktualis][0]; } } if(leghosszabb_ut == ut) kiindulo_falvak[kiindulo_falvak_szama++] = i; else if(leghosszabb_ut < ut) { leghosszabb_ut = ut; kiindulo_falvak_szama = 1; kiindulo_falvak[0] = i; } } if(leghosszabb_ut == 0) cout << -1; else { cout << leghosszabb_ut << '\n'; for(int i = 0; i < kiindulo_falvak_szama; i++) cout << kiindulo_falvak[i] + 1 << ' '; } return 0; }
    UI.: A forráskód beillesztő elnyeli a tabulátorokat, de még az indentáló szóközöket is, egyesével kellett beírnom őket. Hmm és úgy látszik, még ezt is felülírta...
    Mutasd a teljes hozzászólást!
  • Hali!

    #include <iostream> #include <string> using namespace std; void swap(string *a, string *b) { string temp = *a; *a = *b; *b = temp; } void sort(string arr[], int length) { int i, j; for (i = 0; i < length - 1; i++) for (j = i + 1; j < length; j++) if (arr[i] > arr[j]) swap(&arr[i], &arr[j]); } void printArray(string arr[], int length, string title) { int i; cout << title; for (i = 0; i < length; i++) cout << arr[i] << (i < length - 1 ? ", " : " "); cout << "\n"; } int main() { string fruits[] = {"cherry", "peach", "banana", "apple", "kiwi"}; int length = sizeof(fruits) / sizeof(fruits[0]); printArray(fruits, length, "Eredeti sorrendben: "); sort(fruits, length); printArray(fruits, length, "Sorbarendezve: "); return 0; }

    Nekem nem tűnik úgy, hogy lenyelné.
    Mutasd a teljes hozzászólást!


  • Már jó ideje rossz a forráskód beillesztés, ugyanúgy lenyeli az indexelést. Érdemes lenne elgondolkodni a javításán, ha már programozási portál és 2019-et írunk.
    Mutasd a teljes hozzászólást!
  • Így nem fogunk tudni segíteni. Legalábbis én biztosan nem fogom azzal tölteni a szabadidőm, hogy kitaláljam, hogy te hol akartál indexelni :)

    Néhány megjegyzés:
    - szabvány C++-ban nincs VLA
    Variable-length array

    - C++-ban nem kell a blokk elején felsorolni a használt változókat. Érdemes a változókat a lehető legkisebb scope-on belül használni.

    - kicsit több komment is elfért volna, hogy hol mit csinálsz, vagy legalább a hozzászólásodban kifejthetted volna, hogy mi az algoritmus amit implementálni szerettél volna, hogy legalább a szándékodat ne kelljen a kódból bogarászni.
    (Hiszen lehet, hogy nincs is baj az implementációval, hanem maga az algoritmusod rossz)

    - Olvashatóbb a kódod, ha külön szerkezetekbe foglalod a különálló részeket. Pl külön függvénybe a beolvasást, stb..
    100+ soros egyetlen függvény törzsben, akkor gyanakodhatsz, hogy bőven érdemes lenne átstrukturálnod a kódod :)
    Mutasd a teljes hozzászólást!
  • Tényleg hasznos lenne a forráskód gomb, mert nem még csak be se tudom másolni egy szerkesztőbe, mert az i-vel való indexelések például teljesen elvesztek így.
    Mutasd a teljes hozzászólást!
  • Hali!

    Használd a forráskód-gombot (a szerkesztő-mező felett, balról a harmadik: </>), ha forráskódot illesztesz be.

    Mutasd a teljes hozzászólást!
  • Ez a Nemes Tihamér verseny tavalyi feladatsorának 5. feladata(Csatolva).
    Szóval, ezeket egy online értékelő rendszerrel(mester.inf.elte.hu) lehet ellenőriztetni ami különböző teszt bemenetekre figyeli hogy ami kijön az jó e(forráskódot kell beküldeni).Én erre a feladatra az alábbi kódot írtam. A megadott példabemenetre nálam tökéletesen lefutott, továbbá papíron rajzolgattam még gráfokat(mindenféle extra helyzetet) és azokra tesztelve is jó lett.Ezután beküldtem a mesterre ahol 16 pont lett a 30 ból. Tudnátok olyan extra helyzeteket(gráfokat) mondani amire esetleg egy mezei gráfra jól lefutó program hibás eredméyt(időkorláton belül lefutva) adhat???
    Kód:

    #include <iostream>
    using namespace std;

    int main()
    {
    int u,x,y,f; // U=UTAK SZÁMA F=FALVAK SZÁMA
    cin>>u;
    cin>>f;
    int bm[f+1];//BITTÉRKÉP
    int e[f+1];//BEMENET 1.OSZLOPA
    int m[f+1];//BEMEET 2. OSZLOPA
    int zsf[f+1];//ZSÁKFALVAK
    //---------------------------------
    int i=1;
    while(i<f+1)
    {
    bm=0; //BITMAP 0 ÁZÁSA
    i++;
    }
    //---------------------------------
    i=1;
    while(i<u+1)
    {
    cin>>x;
    e
    =x;
    cin>>y;
    m=y;
    bm[x]++;
    bm[y]++; //INPUT
    i++;
    }

    i=1;
    //----------------------------------
    int s=1;
    bool zs=false;
    i=1;

    while(i<f+1)
    {
    if(bm
    ==1)
    {
    zs=true;
    zsf[s]=i; //zsákfalvak keresése
    s++;
    }
    i++;
    }
    //------------------------------------
    i=1;
    int elozo=-1,k;
    int z;
    int j=1;
    bool ih;
    int db;
    int sor;
    int max=0;
    int mt[f+1];
    int maxi=0;
    //------------------------------------
    while(i<s)
    {
    db=0;
    x=zsf;
    ih=true;
    elozo=-1;
    while(ih && db<f)
    {
    j=1;
    k=0;
    while(j<u+1) //MEGKERESI A 2 TOMBBEN A ZSAKFALUT
    {
    if(e[j]==x && j!=elozo)
    {

    z=m[j];
    sor=j;
    k++;

    }

    if(m[j]==x && j!=elozo)
    {
    z=e[j];
    sor=j;
    k++;
    }

    j++;
    }

    if(k==1)
    {
    elozo=sor;
    db++;
    x=z;
    }
    else
    {
    ih=false;
    }
    }
    mt
    =db;
    if(db>max)
    {
    max=db;
    maxi=i;
    }
    i++;
    }
    //------------------------------------
    if(zs)
    {
    cout<<max<<endl;
    i=1;
    while(i<s)
    {
    if(mt==max)
    {
    cout<<zsf
    <<" ";
    }
    i++;
    }

    }

    else
    {
    cout<<"-1";
    }
    return 0;
    }
    Mutasd a teljes hozzászólást!
    Csatolt állomány
abcd