Zadaci za prijemni ispit za PMF

[voodoo_]

Stavi ovo cin.get i cin.ignore i sačekaće da pritisneš enter.

[clzola]

Skini Code::Blocks. On ti zadrzava prozor na ekranu tako da mozes da vidis rezultat...
http://www.codeblocks.org/downloads/26

[PeTkO]

Ja i radim u code::block, i konzola radi lepo sve dok ne pokrenem sam aplikaciju, tj. dok je ne otvorim iz foldera.

Inace, posto jos uvek ne znam u kom IDE okruzenju radimo na prijemnom, da li postoji neka razlika izmedju Visual C++, CodeBlocka ili neceg treceg sto bi mogli da nam daju?

[EclipsE]

Odakle tebi ideja da ćeš polagati prijemni na računaru?

Mislim, ako je to tačno onda super, ali nigde ne piše u informatoru da se prijemni ispit iz programiranja polaže na računarima.
Uostalom, ne postoji samo jedan programski jezik, šta ako neko odluči da rešava zadatke u javascriptu a nema instaliran node.js? (totalno moguće, rešavao sam codejam u JS https://github.com/proof/codejam-201.../qualification)

Takođe, obzirom na broj studenata koji se verovatno prijavljuje da polaže prijemni, ne verujem da će moći da obezbede računar svakom kandidatu...

[Andross]

Polagaces na papiru najverovatnije, kao i svaki kontrolni iz programiranja u srednjoj.

[PeTkO]

Ja se iskreno nadam da hoce, posto je pretprosle godine bilo prijavljeno samo 21, a primali su 32, a prosle godine je prijavljeno 32 i takodje su primali 32. I upali su svi. A malo mi je glupo da ne obezbede racunare, posto prvo ima jako malo prijavljenih, drugo, ipak je to PMF, odsek za racunare, pa valjda imaju za toliko resursa. Od jezika su dozvoljeni svi jezici visokog nivoa: C, C++, C#, Basic, Pascal, Java.

Evo jos jednog zadatka koji sam uradio.
Tekst zadatka:

Data su dva niza a i b dužina n i m, koja su sortirana u rastućem redosledu. Što efikasnije novi niz c, koji predstavlja
uniju ova dva niza, sortiranu takođe u rastoćem redosledu. Na primer, za a = (1, 3, 5, 6) i b = (2, 4, 7, 8, 9) – odgovor
je c = (1, 2, 3, 4, 5, 6, 7, 8, 9).

Kod zadatka:

#include <iostream>

using namespace std;

int main()
{
    cout << "Unesite velicinu prvog niza: ";
    int x = 0;
    cin >> x;
    cout << "Unesite velicinu drugog niza: ";
    int y = 0;
    cin >> y;
    int niz1[x];
    int niz2[y];
    int a = x+y;
    int niz3[x+y];
    cout << "Unesite podatke za prvi niz: ";
    for(int i=0; i<x; i++)
    {
        cin>>niz1[i];
    }
    cout << "Unesite podatke za drugi niz: ";
    for(int i=0; i<y; i++)
    {
        cin>>niz2[i];
    }
    for(int k=0, l=0; k+l < x+y;)
    {
        if(l == y || k !=x && niz1[k] > niz2[l])
        {
            niz3[l+k] = niz1[k];
            k++;
        }
        else
        {
            niz3[l+k] = niz2[l];
            l++;
        }
    }

    for (int i = 0; i < a; i++)
    {

    int najmanji = i;


    for (int j = i + 1; j < a; j++)
    {

        if (niz3[j] < niz3[najmanji])

            najmanji = j;
    }
    swap(niz3[i], niz3[najmanji]);
}
    cout << "Spojeni niz, poredjani brojevi: ";
    for(int i=0; i<a; i++)
    {
        cout << niz3[i]<<", ";
    }
    cin.get();
    cin.ignore();
    return 0;
}

Neki savet, kritika...Inace, mislim da sam sad morao da napravim funkciju koja ce treci niz da sortira od najmanjeg ka najvecem broju.

[EclipsE]

var a = [1, 3, 5, 6], b = [2, 4, 7, 8, 9];
var c = new Array(a.length + b.length);
var i = 0, j = 0, x;
for (x = 0; x < c.length; x++)
  c[x] = (a[i] < b[j]) ? a[i++] : b[j++];
c;

>> [1, 2, 3, 4, 5, 6, 7, 8, 9]

Jednostavno krenes od pocetka oba niza, i onaj koji je manji ubacujes u treci niz i jos dodatno predjes na sledeci element tog niza:

a[0] < b[0] = true -> c[0] = a[0]
a[1] < b[0] = false -> c[1] = b[0]
a[1] < b[1] = true -> c[2] = a[1]

etc..

[Sun Tzu]

PeTkO kaže:

drugo, ipak je to PMF, odsek za racunare, pa valjda imaju za toliko resursa.

Ha.
Na pmfu u bgd se do ove godine polagalo programiranje na papiru.
Uvek očekuj loše stvari od domaćih fakulteta, manje ćeš se razočarati.

Inače, ovo:

cout << "Unesite velicinu prvog niza: ";
int x = 0;
cin >> x;
cout << "Unesite velicinu drugog niza: ";
int y = 0;
cin >> y;
int niz1[x];
int niz2[y];

Ne radi. Ili dinamički alociraj nizove ili moraš odma veličinu da staviš.

[PeTkO]

Evo jos jednog zadatka:

Tekst:

Ispred blagajne je poređano n ljudi sa svojim visinama h [1], h [2], ..., h [n] u tom redosledu. Odrediti broj ljudi koje
vidi blagajnik sa početka reda. Na primer, za ljude sa visinama 155, 170, 165, 180, 175, 195, blagajnik vidi prvog,
drugog,*četvrtog i šestog*čoveka – odgovor je 4.**

Kod

#include <iostream>

using namespace std;

int main()
{
    cout << "Unesite broj ljudi ispred blagajne: ";
    int x = 0;
    cin >> x;
    int niz[x];
    int broj = 0;
    cout << "Unesite visine ljudi u redu: ";
    for(int i=0; i<x; i++)
    {
        cin >> niz[i];
    }
    int max = niz[0];
    for(int i=0; i<x; i++)
    {
        if(max > niz[i])
            {
             
            }
        else
        {
                broj++;
                max = niz[i];
                
        }
    }
    cout << broj;
    cin.get();
    cin.ignore();
    return 0;
}

Edit: Ispravka koda, nakon sugestije @Sun Tzu.

[Sun Tzu]

if(niz[i]<niz[i+1])
{
broj++;
}

Loše. Šta da imaš u nizu 170, 165, 166 ljude. Ovaj treći jeste veći od prethodnog, ali se neće videti jer si pre njega imao ovog od 170.

Nešto tipa:

max = prvi iz niza
petlja kroz ostatak niza
{
ako je visina trenutnog veća od max, uvećaš za 1 brojač i postaviš max na tu visinu
ako nije, ideš na sledećeg
}

[PeTkO]

Sun Tzu kaže:

Inače, ovo:

cout << "Unesite velicinu prvog niza: ";
int x = 0;
cin >> x;
cout << "Unesite velicinu drugog niza: ";
int y = 0;
cin >> y;
int niz1[x];
int niz2[y];

Ne radi. Ili dinamički alociraj nizove ili moraš odma veličinu da staviš.

Kako ne radi? ne razumem...Kod mene taj program lepo radi.
To sam hteo da pitam...Kako da definisem niz, od n brojeva, ali da pre toga ne trazim od korisnika da unese velicinu niza?

[Sun Tzu]

PeTkO kaže:

Kako ne radi? ne razumem...Kod mene taj program lepo radi.

Hmm. Nije htelo kad sam probao sa Visual C++, sad pod Linuksom oće. Nešto sam ja onda omašio.
Zaboravi da sam išta rekao.

[PeTkO]

Hm...Imam problem oko sledeceg zadatka. Treba da nadjem velicinu najduzeg uzastopnog podniza brojeva. U nizu imam date sledece brojeve: 5 1 3 2 5 8 9 4, a podniz uzastopnih brojeva je 2 5 8 9, i njegova velicina je 4. E sad...Ja sam ne googlu nasao dosta primera gde je prikazano resenje podniza rastucih brojeva, gde bi u ovom primeru resenje bilo 1 2 8 9, sto meni ne treba. Na koji nacin bi mogao da resim ovaj zadatak?

[EclipsE]

Sun Tzu kaže:

Hmm. Nije htelo kad sam probao sa Visual C++, sad pod Linuksom oće. Nešto sam ja onda omašio.
Zaboravi da sam išta rekao.

Ovo radi u gcc-u (mingw na windowsu), a mozda i u clang... ne radi u VSC++. I ja sam bio zacudjen kada sam video ovakav primer negde

PeTkO kaže:

Hm...Imam problem oko sledeceg zadatka. Treba da nadjem velicinu najduzeg uzastopnog podniza brojeva. U nizu imam date sledece brojeve: 5 1 3 2 5 8 9 4, a podniz uzastopnih brojeva je 2 5 8 9, i njegova velicina je 4. E sad...Ja sam ne googlu nasao dosta primera gde je prikazano resenje podniza rastucih brojeva, gde bi u ovom primeru resenje bilo 1 2 8 9, sto meni ne treba. Na koji nacin bi mogao da resim ovaj zadatak?

simulation kaže:

5
5 1 - kraj jer 1 < 5, najduzi podniz = 5, velicina 1
1
1 3
1 3 2 - kraj jer 2 < 3, najduzi podniz = 1 3, velicina 2 veca od prethodnog
2
2 5
2 5 8
2 5 8 9
2 5 8 9 4 - kraj jer 4 < 9, najduzi podniz = 2 5 8 9, velicina 4 veca od prethodnog

[chaami]

Sun Tzu kaže:

Hmm. Nije htelo kad sam probao sa Visual C++, sad pod Linuksom oće. Nešto sam ja onda omašio.
Zaboravi da sam išta rekao.

Korisnički definisan niz spada u VLA odnosno variable lenght arrey. U C jezik je uključen sa C99 standardom. MS koliko ja znam (pošto ga ne koristim) se drži C89 standarda tako da ne podržava VLA. Što se mog skromnog mišljenja tiče uvek je pametnije niz alocirati u memoriji ...

cin >> n
int *niz = new int[n];

... i to iz par razloga. Izbegavaš zbunjivanje onih koji korist VC++, izbegavaš mogućnost da ti rešenje zadatka odbiju na nekom takmičenju, možeš da alociraš mnogo mnogo veći prostor za niz a i dobro je navikavati se na heap od samog početka.

[PeTkO]

Treba mi jedan mali hint.
U par zadataka mi se trazi da izracunam najvecu vrednost nekog broja. I obicno taj broj, ciju najvecu vrednost ja trazim, dobijam kroz neku petlju. Npr:

for(int i=0; i<x; i++)
    {
        for(int j=i+1, k=i+2; j<x, k<x; j++, k++)
        {
            float a = niz[i];
            float b = niz[j];
            float c = niz[k];
            float s = (a+b+c)/2;
            float p = sqrt(s*(s-a)*(s-b)*(s-c));
            cout << p <<endl;
        }
    }

Ovde se preko Heronovog obrasca izracunava povrsina nekog trougla, cije su stranice date u nizu. Konkretnije od n dasaka x duzine treba da nadjem trougao sa najvecom povrsinom. Ja sam ovde izracunao povrsinu za svaku kombinaciju dasaka, ali meni treba najvece p. Kako to da dobijem, tj. kako da uporedim novo p, sa starim p?

[ozzytheking]

Smestis p u novu promenljivu (npr. max) i onda ukoliko je max < p, max postaje p (max = p).

[PeTkO]

Ako to uradim ovako:

for(int i=0; i<x; i++)
    {
        for(int j=i+1, k=i+2; j<x, k<x; j++, k++)
        {
            float a = niz[i];
            float b = niz[j];
            float c = niz[k];
            float s = (a+b+c)/2;
            float p = sqrt(s*(s-a)*(s-b)*(s-c));
            max = p;
            if(max < p)
            {
                max = p;
            }
        }
    }
    cout << max;

Uvek dobijem nulu. Gde gresim?

[ozzytheking]

PeTkO kaže:

Ako to uradim ovako:

for(int i=0; i<x; i++)
    {
        for(int j=i+1, k=i+2; j<x, k<x; j++, k++)
        {
            float a = niz[i];
            float b = niz[j];
            float c = niz[k];
            float s = (a+b+c)/2;
            float p = sqrt(s*(s-a)*(s-b)*(s-c));
            max = p;
            if(max < p)
            {
                max = p;
            }
        }
    }
    cout << max;

Uvek dobijem nulu. Gde gresim?

Ovde. Obrisi to. Inicijalizuj max na neku minimalnu vrednost (van ovih petlji), posto se radi o povrsinama koje su uvek >= 0, rokni max = -1. I to je to.

[PeTkO]

@ozzytheking Hvala puno na pomoci.

Evo jos jednog zadatka koji sam uradio.
Tekst:

Dato je n dasaka sa svojim dužinama. Potrebno je odrediti najveću moguću površinu trougla koji se može napraviti
pomoću neke tri daske. Heronov obrazac za površinu trougla sa stranicama a, b i c glasi P = sqrt (s * (s – a) * (s – b) *
(s – c)), gde je s = (a + b + c) / 2. Na primer, za daske sa dužinama 1, 3, 4, 5, 10, najveći trougao koji možemo napraviti
je trougao sa stranicama 3, 4 i 5 – pa je odgovor 6.

Kod:

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
    int x=0;
    cout << "Unesite broj dasaka: ";
    cin >> x;
    float niz[x];
    cout << "Unesite duzinu dasaka: ";
    float max = -1;
    for(int i=0; i<x; i++)
    {
        cin >>niz[i];
    }
    for(int i=0; i<x; i++)
    {
        for(int j=i+1, k=i+2; j<x, k<x; j++, k++)
        {
            float a = niz[i];
            float b = niz[j];
            float c = niz[k];
            float s = (a+b+c)/2;
            float p = sqrt(s*(s-a)*(s-b)*(s-c));

            if(max < p)
            {
                max = p;
            }
        }
    }
    cout << "Najveca povrsina je: "<< max;
    cin.get();
    cin.ignore();
    return 0;
}

Valjda sam ga dobro uradio. Mada nije mi jedna stvar jasna kod ovog zadatka. Najveca povrsina se dobija sa daskama duzine 1, 5 i 10 (resenje za P je koren iz 72), a ne 3, 4 i 5 (resenje za P je 6) kao sto su oni dobili. Da li su oni pogresili, ili je ceo zadatak netacan ili je nesto trece?