C++ hatékonyabb megoldás

C++ hatékonyabb megoldás
2018-02-28T11:58:59+01:00
2018-03-01T15:59:03+01:00
2022-08-11T00:45:31+02:00
SzabolcsiJ
A gyufa.png fájlban leírt feladatra készítettem az itt olvasható kódot. Lefut minden engedélyezett n-re
és szerintem jó is. Viszont a feladat végén megadott időlimitet (0,1 mp) nem tartja be. n=100-nál 0,484-et mértem. Hogyan lehetne gyorsítani?
Másik kérdésem: Hogyan tudom azt ellenőrizni, hogy a memórialimitet (32M) betartja-e a program?

#include <iostream> #include <algorithm> #include <ctime> using namespace std; int main() { short int n, k=0, hanyadik=0, munka; short int oldalak[3]; short int kiirt[100][3] = { 0 }; //ebben fogjuk tárolni a jó háromszögek oldalait bool volt_e = false; cin >> n; //3-100 time_t start = clock(); for (short int i = 1; i <= n - 2; i++) //első oldal hossza { for (short int j = 1; j <= n - 1 - i; j++) //második oldal hossza { k = n - i - j; //harmadik oldal hossza if (i + j > k && i + k > j && j + k > i) // ha a háromszög egyenlőtlenség teljesül { volt_e = false; oldalak[0] = i; oldalak[1] = j; oldalak[2] = k; sort(begin(oldalak), end(oldalak)); //növekvő sorrendbe rakjuk az oldalakat (az elforgatott háromszög ugyanaz) for (int m = 0; m < hanyadik; m++) //megnézzük, hogy volt-e már ez a háromszög { if (kiirt[m][0] == oldalak[0] && kiirt[m][1] == oldalak[1] && kiirt[m][2] == oldalak[2]) { volt_e = true; break; } } if (!volt_e) //ha még nem volt, eltároljuk { kiirt[hanyadik][0] = oldalak[0]; kiirt[hanyadik][1] = oldalak[1]; kiirt[hanyadik][2] = oldalak[2]; hanyadik++; } } } } //csak teszteléshez: cout << hanyadik << " db megoldas van." << endl; //kiírás (egyelőre képernyőre, ha jó, akkor mehet majd fájlba) for (short int i = 0; i < hanyadik; i++) { cout << kiirt[i][0] << " " << kiirt[i][1] << " " << kiirt[i][2] << endl; } time_t end = clock(); cout << (double)(end - start) / CLOCKS_PER_SEC << endl; cin.get(); return 0; }
Mutasd a teljes hozzászólást!
Csatolt állomány
A volt-e már vizsgálat nem kell, ha csak egyszer mész végig a lehetséges háromszögeken és csak az i <= j <= k eseteket nézed.
A 'kiirt' tömböd 100 elemszámú, de a 'jó háromszögek' száma ettől több is lehet (n=100-ra 208db), std::vector-t használnék helyette, 
de mivel nincs vizsgálat, el is hagyhatod és közvetlenül kiirathatod a találatokat.

#include <iostream> #include <algorithm> #include <ctime> #include <array> #include <vector> using namespace std; typedef array<short, 3> hszog_t; int main() { short int n; vector<hszog_t> kiirt; //ebben fogjuk tárolni a jó háromszögek oldalait cin >> n; //3-100 time_t start = clock(); for (short int i = 1; i <= n - 2; i++) //első oldal hossza { for (short int j = i; j <= n - 1 - i; j++) //második oldal hossza { short int k = n - i - j; if (k >= j && i + j > k && i + k > j && j + k > i) // ha a háromszög egyenlőtlenség teljesül { kiirt.push_back( {i,j,k} ); } } } //csak teszteléshez: cout << kiirt.size() << " db megoldas van." << endl; //kiírás (egyelőre képernyőre, ha jó, akkor mehet majd fájlba) for (short int i = 0; i < (int)kiirt.size(); i++) { cout << kiirt[i][0] << " " << kiirt[i][1] << " " << kiirt[i][2] << endl; } time_t end = clock(); cout << (double)(end - start) / CLOCKS_PER_SEC << endl; cin.get(); return 0; }
Mutasd a teljes hozzászólást!

  • Hali,

    a kódodat még nem néztem, de a csatolt képen levő példa is hibás.  Ugyanis 5 gyufaszállal 2 háromszöget is lehet összerakni.
    Mutasd a teljes hozzászólást!
  • Szerintem amire gondolsz, az két különálló háromszög 1 közös oldallal (összesítve: rombusz).
    Ha jól értem a feladatot, akkor itt az összes gyufaszálat fel kell használni a háromszög előállítására (tehát nem 2 különbözőre, hanem 1 "nagyobbra").
    Így első ránézésre 5 gyufa esetén nem látok másmilyen háromszöget, mint aminek az oldalai: 1,2,2

    Szerk: nem gondoltam végig, de gyanítom, hogy a páros gyufaszámokat ki lehet hagyni (ha a szálak egyforma hosszúak).
    Mutasd a teljes hozzászólást!
  • A növekvő sorrendbe rakás nem egyezik a forgatással.
    A 2-3-4 és a 2-4-3 nem ugyanaz a háromszög
    Mutasd a teljes hozzászólást!
  • A volt-e már vizsgálat nem kell, ha csak egyszer mész végig a lehetséges háromszögeken és csak az i <= j <= k eseteket nézed.
    A 'kiirt' tömböd 100 elemszámú, de a 'jó háromszögek' száma ettől több is lehet (n=100-ra 208db), std::vector-t használnék helyette, 
    de mivel nincs vizsgálat, el is hagyhatod és közvetlenül kiirathatod a találatokat.

    #include <iostream> #include <algorithm> #include <ctime> #include <array> #include <vector> using namespace std; typedef array<short, 3> hszog_t; int main() { short int n; vector<hszog_t> kiirt; //ebben fogjuk tárolni a jó háromszögek oldalait cin >> n; //3-100 time_t start = clock(); for (short int i = 1; i <= n - 2; i++) //első oldal hossza { for (short int j = i; j <= n - 1 - i; j++) //második oldal hossza { short int k = n - i - j; if (k >= j && i + j > k && i + k > j && j + k > i) // ha a háromszög egyenlőtlenség teljesül { kiirt.push_back( {i,j,k} ); } } } //csak teszteléshez: cout << kiirt.size() << " db megoldas van." << endl; //kiírás (egyelőre képernyőre, ha jó, akkor mehet majd fájlba) for (short int i = 0; i < (int)kiirt.size(); i++) { cout << kiirt[i][0] << " " << kiirt[i][1] << " " << kiirt[i][2] << endl; } time_t end = clock(); cout << (double)(end - start) / CLOCKS_PER_SEC << endl; cin.get(); return 0; }
    Mutasd a teljes hozzászólást!
  • 6-ból lehet háromszöget csinálni: 2-2-2 szabályos háromszög
    Mutasd a teljes hozzászólást!
  • Jogos - erre nem gondoltam...
    Mutasd a teljes hozzászólást!
  • Igen, a kiirt tömb elemszámát azóta megnöveltem
    Mutasd a teljes hozzászólást!
  • Mi lenne a másik 5-ből összerakható háromszög?
    Mutasd a teljes hozzászólást!
  • Igaz, visszaszívtam.
    Mutasd a teljes hozzászólást!
  • Szia!

    Csak egy apróság így hirtelen: ne használj short típust....
    Milyen CPU-n fut le ez a rutin 0,484 másodperc alatt?
    Mutasd a teljes hozzászólást!
  • Mégiscsak kell vizsgálat... 5-re a te változatod 1,2,2 és a 2,2,1-et is. Ez ugyanaz a háromszög.
    Mutasd a teljes hozzászólást!
  • Bocs, kipróbáltam, mégis jó 5-re is!
    Mutasd a teljes hozzászólást!
  • Többek tippjeit felhasználva (pl. hogy a 2 3 4 nem ugyanaz, mint a 2 4 3 háromszög) írtam egy javított verziót. Megnéznétek? Vector azért nincs benne, mert egy olyan srácnak írtam, aki azt nem ismeri, csak a tömböt.

    Az a kérdésem továbbra is fennáll, hogy hogyan tudom megnézni a memória-felhasználását a programomnak? (A feladat kiírásban van egy memória-limit 32 MB kitétel)

    #include <iostream> #include <ctime> using namespace std; int main() { bool volt_e; short int n,k, hanyadik=0; int kiirt[400][3]; //ebben fogjuk tárolni a jó háromszögek oldalait cin >> n; //3-100 time_t start = clock(); for (short int i = 1; i <= n - 2; i++) //első oldal hossza { for (short int j = i; j <= n - 1 - i; j++) //második oldal hossza { k = n - i - j; //harmadik oldal hossza volt_e = false; if ( i + j > k && i + k > j && j + k > i) // ha a háromszög egyenlőtlenség teljesül { for (short int m = 0; m < hanyadik; m++) //összehasonlítom a már elkészült háromszögekkel { if (kiirt[m][0] == k && kiirt[m][1] == j && kiirt[m][2] == i) volt_e = true; //144 és 441 ugyanaz if (kiirt[m][0] == j && kiirt[m][1] == k && kiirt[m][2] == i) volt_e = true; //234 és 342 ugyanaz if (kiirt[m][0] == k && kiirt[m][1] == i && kiirt[m][2] == j) volt_e = true; //234 és 423 ugyanaz } if (!volt_e) { kiirt[hanyadik][0] = i; kiirt[hanyadik][1] = j; kiirt[hanyadik][2] = k; hanyadik++; } } } } //csak teszteléshez: cout <<hanyadik<< " db megoldas van." << endl; //kiírás (egyelőre képernyőre, ha jó, akkor mehet majd fájlba) for (short int i = 0; i < hanyadik; i++) { cout << kiirt[i][0] << " " << kiirt[i][1] << " " << kiirt[i][2] << endl; } time_t end = clock(); cout << (double)(end - start) / CLOCKS_PER_SEC << endl; cin.get(); return 0; }
    Mutasd a teljes hozzászólást!
  • Itt az ideje, hogy tanulja meg a vector-t. STL nélkül nem megy sokra C++-ban.

    Nagyon sokat lehetne még optimalizálni a kódon.

    Különböző-e a?
    2-3-4 vs 2-4-3. Egybevágósági transzformációkkal átvihetők egymásba, tehát nem feltétlenül kell különbözőnek számítani őket, ez inkább feladat specifikációtól függ.
    Igazából, ha generáltuk az összes lehetséges megoldást, ahol nem vettük figyelembe a körüljárást, csak az oldalak hosszát, akkor utána nagyon egyszerű generálni a más körüljárást. Magyarul 2-3-4 -> 2-4-3at,
    Meg kéne tudni, hogy pontosan mi is a feladat specifikációja.

    Lehetséges algoritmus.
    Kezdjük a keresést az egyik legkisebb oldaltól. Elég N / 3-ig keresni, hiszen ha ennél tovább mennénk, akkor nem lehetne ez az egyik legkisebb oldal. (a <= b <= c)
    a = 1 -> N / 3

    Kerssük hozzá a második leghosszabb oldalt.
    b = max( a, ceil((N - 2a)/2))  -> a + (N - a) / 2

    (b > (N-2a/)/ 2 ebből a két egyenletből jön: a + b > c && a+b+c=N)
    'a'-tól nem lehet kisebb, hiszen akkor nem 'a' lenne az egyik legkisebb. Elég a maradék elemek feléig vizsgálni, hiszen ha több mint a maradék elemek felét 'b'-hez rendelnénk, akkor 'c' a legnagyobb oldal kisebb lenne, mint a középső oldal hossza.

    c = N - a - b
    Ez a számhármas megfelelő, hiszen
    a + b > c  (for ciklusban választott feltétel miatt)
    a + c > b  (hiszen c az egyik legnagyobb és a > 0) 
    b + c > a  (detto)
    Mutasd a teljes hozzászólást!
  • Az egyik képlet-ben van egy kicsi hiba, de akit érdeke a dolog, az megfogja találni az elírást :)
    Mutasd a teljes hozzászólást!
  • Száguld akárcsak a szerelemvonat

    #include <iostream> #include <cmath> int main() { int count = 0; int n; std::cin >> n; for (int i = std::ceil(n / 3.0); i < std::ceil(n / 2.0); ++i) { for (int j = std::ceil((n - i) / 2.0); j <= i; ++j) { // std::cout << '(' << i << ';' << j << ';' << n - i - j << ')' << '\n'; ++count; } } std::cout << count << '\n'; }
    Mutasd a teljes hozzászólást!
  • Ez tényleg nagyon gyors, feltöltöttem az ELTE Mester oldalára (onnan van a feladat, de nem beadandó, hanem gyakorlásként). Mind a 15 tesztre 0 sec-et mért  és a maximumot,  100 pontot adott rá :)

    Megtennéd, hogy elmagyarázod, hogy miért jó, ha az i és a j ilyen intervallumba esik? Azt látom, hogy működik, de szeretném megérteni...
    Mutasd a teljes hozzászólást!
  • (off: Egész számok csonkításos osztásához tényleg esszenciális a lebegőpontos matek?)
    Talán egy ciklust még ki lehetne hagyni:

    /* gyufa.c */ #include <stdio.h> #include <stdlib.h> int main (void) { int n= -1; int i; int count; scanf ("%d", &n); if (n<3 || n>30000) exit (100); count= 0; for (i=1; i<=n/3; ++i) { count += (n-i)/2 - i + 1; /* j lehetséges értékei: i..(n-i)/2, ezek száma: (n-i)/2 - i + 1 */ } printf ("%d\n", count); return 0; }
    Szerk: bár, mint látom, fordítva jelöltem, itt 1<=i<=j<=k; i<=[n/3]; k<=[(n-1)/2], j<=[(n-i)/2],k=(n-i-j)
    Mutasd a teljes hozzászólást!
  • Végiggondoltam, és megértettem, köszi.
    Mutasd a teljes hozzászólást!
  • Egyébként már a Zoley megoldása is elég gyors, arra is 100 pontot adott a kiértékelő program.
    Mutasd a teljes hozzászólást!
  • Nem baj, úgyis kihagytam egy feltételt:

    i<=j<=k;

    1<=i<=[n/3]

    j>=i,
    j>=[n/2]+1-i
    j<=[(n-i)/2]

    k>=j
    k>=[(n+2)/3]
    k<=[(n-1)/2]

    /* gyufa.c */ #include <stdio.h> #include <stdlib.h> #define max(u,v) ((u)<(v)?(v):(u)) int main (void) { int n= -1; int i; int count; scanf ("%d", &n); if (n<3 || n>30000) exit (100); count= 0; for (i=1; i<=n/3; ++i) { int jmin= max(i,n/2+1-i); int jmax= (n-i)/2; if (jmin<=jmax) count += jmax-jmin+1; } printf ("%d\n", count); return 0; }
    Az igazi persze egy zárt képlet lenne, durván n*n/50
    Mutasd a teljes hozzászólást!
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd