Zadaci za prijemni ispit za PMF

[ozzytheking]

Kako dobijes najvecu povrsinu za 1, 5, 10? Stranice trougla treba da budu takve da zbir dve bude veci od trece, a 1 i 5 nisu veci od 10. Pogotovo sto onda ispod korena dobijes negativnu vrednost... sqrt(8*7*3*(-2))...

Jedino sto mi pada na pamet je da ukoliko su daske sortirane, krenes unazad, proveris da li od njih moze da se dobije trougao i ako moze to je trougao sa najvecom povrsiom.

EDIT: Po tvom zadatku stranice se izgleda ne unose u opadajucem ili rastucem poretku tako da bi ti trebao da sortiras taj niz pa onda da krenes sa proverom.

[PeTkO]

Hm...Mislim da nije potrebno sortiranje, zato sto ja kroz petlje uporedjujem svaki clan niza, tako da mi sortiranje, barem ja tako mislim, nije potrebno.

[ozzytheking]

Kolko ja vidim ti uporedjujes susedne clanove (123, 234, 345, itd). Sta ako neko unese niz, lupam, 10, 3, 1, 18, 52, 6 (nesortiran niz)?
Pazi logiku, osim pravila da zbir dve stranice mora biti veci od trece (u suprotnom to ne moze da bude trougao), za sto vecu povrsinu ti trebaju sto vece stranice, logicno. Zbog toga ti treba sortiran niz. Sortiras ih u opadajucem poretku, napravis funkciju BOOL da_li_je_ovo_trougao(a, b, c) i krenes od pocetka i uporedjujes po 3 susedne daske (kao sto vec i radis). Kada ova funkcija vrati TRUE nasao si najveci trougao, cak ti ni ne treba racunanje povrsine. Mrzi me da pisem program, ali mi ovo deluje logicno. Probaj ako imas vremena.

EDIT: Mogao bi ti i da napises program koji ce uporedjivati sve moguce kombinacije stranica.

Jos nesto, sad mi pade na pamet, ne znam kako C stoji sa NaN vrednostima (u Javi verovatno od korena negativnog broja dobijes NaN) ali mislim da C ne vodi racuna o tome. Verovatno si zato i dobio koren iz 72 kad si izvadio koren iz negativnog broja...
Zbog ovoga bi ti trebao pre trazenja povrsine da proveris da li je to uopste trougao pa tek odna da racunas P.

[PeTkO]

Hm...Sad sam stavio tvoj niz na papir i peske izracunao svaku mogucu kombinaciju brojeva i preko Heronovog obrasca ne moze da se dobije nijedan trougao sa pozitivnom povrsinom.

Edit: a moj program, cak i kada sortiram niz u opadajucem redosledu, opet dobijem 6 za primer koji je dat u zadatku i -1 (tj. ne postoji trougao) kada ubacim tvoj niz.

[PeTkO]

Evo jos jednog zadatka. Pretpostavljam da moze i lakse da se napravi, ali meni je ovo jedino palo na pamet:

Tekst:

Data su dva stringa a i b. Odrediti da li je string a anagram stringa b (da li se string b dobija premeštanjem slova
stringa a). Na primer, za a = ‘matematika’ i b = ‘temamakati’ odgovor je ‘DA’, dok je za a = ‘matematika’ i b =
‘matematike’ odgovor ‘NE’.

Kod:

#include <iostream>
#include <string.h>
#include <stdlib.h>

using namespace std;

int main()
{
    char rec1[120];
    char rec2[120];
    bool tacno = true;
    cout << "Unesite prvu rec: ";
    cin.getline(rec1, 120);
    cout << "Unesite drugu rec: ";
    cin.getline(rec2, 120);
    char slova[]={"abcdefghijklmnoprqrstuvwxyz"};
    int a[26] = {0};
    int b[26] = {0};
    int duzina = (int)strlen(rec1);
    int duzina2 = (int)strlen(rec2);
    if(duzina != duzina2)
    {
        cout << "NE";
    }
    for(int i=0; i<duzina; i++)
    {
        for(int j=0; j<26; j++)
        {
            if(rec1[i] == slova[j])
            {
                a[j] += 1;
            }
            if(rec2[i] == slova[j])
            {
                b[j] += 1;
            }
        }
    }
    for(int i=0; i<26; i++)
    {
        if(a[i] != b[i])
        {
            tacno = false;
        }
    }

    if(tacno == 1)
    {
        cout << "da";
    }
    else
    {
        cout << "ne";
    }
    cin.get();
    cin.ignore();
    return 0;
}

[Roddick]

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

bool isTriangle(float x, float y, float z)
{
	return (x<(y+z) && y<(x+z) && z<(x+y));
}
double Povrsina(float x,float y,float z)
{
	float s = (x+y+z)/2;
	return sqrt(s*(s-x)*(s-y)*(s-z));
}
void Sort(float *a,int n)
{
	float pom;
	for (int i = 0;i < n-1;i++)
		for (int j = i+1;j < n;j++)
			if (a [i] < a [j])
			{
				pom = a [i];
				a [i] = a [j];
				a [j] = pom;
			}
}

void main (void)
{
	float* niz;
	int br;
	cin>>br;
	niz = new float [br];
	for (int i = 0;i < br;i++)
		cin>> niz [i];
	Sort(niz,br);
	double max = -1,p;
	for (i = 0;i < br-2;i++)
		if (isTriangle(niz [i],niz [i+1],niz [i+2]))
			if (max < (p = Povrsina(niz [i],niz [i+1],niz [i+2])))
				max = p;
		cout<<max;
}

Evo ovaj prethodni.

[Geomaster]

chaami kaže:

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.

Nema veze sa Microsoftom, C++ koliko ja znam uopšte ne bi trebalo da podržava VLA. Čini mi se da je propozicijom za TR2 to uzeto u razmatranje ali ništa od toga.

[Roddick]

PeTkO kaže:

Evo jos jednog zadatka. Pretpostavljam da moze i lakse da se napravi, ali meni je ovo jedino palo na pamet:

Tekst:

Data su dva stringa a i b. Odrediti da li je string a anagram stringa b (da li se string b dobija premeštanjem slova
stringa a). Na primer, za a = ‘matematika’ i b = ‘temamakati’ odgovor je ‘DA’, dok je za a = ‘matematika’ i b =
‘matematike’ odgovor ‘NE’.

Kod:

#include <iostream>
#include <string.h>
#include <stdlib.h>

using namespace std;

int main()
{
    char rec1[120];
    char rec2[120];
    bool tacno = true;
    cout << "Unesite prvu rec: ";
    cin.getline(rec1, 120);
    cout << "Unesite drugu rec: ";
    cin.getline(rec2, 120);
    char slova[]={"abcdefghijklmnoprqrstuvwxyz"};
    int a[26] = {0};
    int b[26] = {0};
    int duzina = (int)strlen(rec1);
    int duzina2 = (int)strlen(rec2);
    if(duzina != duzina2)
    {
        cout << "NE";
    }
    for(int i=0; i<duzina; i++)
    {
        for(int j=0; j<26; j++)
        {
            if(rec1[i] == slova[j])
            {
                a[j] += 1;
            }
            if(rec2[i] == slova[j])
            {
                b[j] += 1;
            }
        }
    }
    for(int i=0; i<26; i++)
    {
        if(a[i] != b[i])
        {
            tacno = false;
        }
    }

    if(tacno == 1)
    {
        cout << "da";
    }
    else
    {
        cout << "ne";
    }
    cin.get();
    cin.ignore();
    return 0;
}

Meni je najzgodnije da sortiram oba niza karaktera i onda pokomponentno poredim u while petlji.

[Geomaster]

Roddick kaže:

Meni je najzgodnije da sortiram oba niza karaktera i onda pokomponentno poredim u while petlji.

To je nlogn, njegovo je n, brže je.

[ozzytheking]

PeTkO kaže:

Hm...Sad sam stavio tvoj niz na papir i peske izracunao svaku mogucu kombinaciju brojeva i preko Heronovog obrasca ne moze da se dobije nijedan trougao sa pozitivnom povrsinom.

Edit: a moj program, cak i kada sortiram niz u opadajucem redosledu, opet dobijem 6 za primer koji je dat u zadatku i -1 (tj. ne postoji trougao) kada ubacim tvoj niz.

Ma lupio sam niz, i tacno je da nema trouglova u tom nizu. Ali u slucaju da je zadat niz koji nije u rastucem ili opadajucem poretku, tvoj program nece naci max povrsinu. 'Ajde sad da dam primer koji radi:
8, 1, 6, 3, 5, 12, 4.
Jedina kombinacija koja zadovoljava uslov trougla je (6, 5, 3) po tvom programu (jer 8-1-6 nije trougao, 1-6-3, 3-5-12 i 5-12-4 takodje nisu trouglovi), ali kada sortiras taj niz (i dobijes 12, 8, 6, 5, 4, 3, 1) vidis da je trougao sa najvecom P u stvari (12, 8, 6).

[PeTkO]

Ok, hvala na detaljnom razjasnjavanju. Kada sam ubacio sortiranje, program radi. Hvala jos jednom

Edit: Sto se tice ovog programa sa anagramima...Meni apsolutno nije bitno da li je brze ili ne, vec da li postoji prostiji nacin od mog da se zadatak uradi.

Edit2: @Roddick, Da, moze i tako da se odradi zadatak, ali mislim da je moj nacin jednostavniji, tj. manja pisanija Nadam se da ne gresim

Edit3: Ovaj zadatak nikako da resim, i mnogo me nervira. Uopste ne mogu da dobijem ono sto oni traze, pa molim za pomoc. Tekst zadatka:

 Dat je niz n prirodnih brojeva. Odrediti dužinu najdužeg podniza uzastopnih brojeva koji je rastući. Na primer za niz
5, 1, 3, 2, 5, 8, 9, 4 najduži rastući uzastopni podniz je 2, 5, 8, 9 – pa je odgovor 4.

[ozzytheking]

Uzmes dve ugnjezdene FOR petlje, i onda sa ovom drugom ides od trenutnog clana sve dok ne naidjes na clan koji ne zadovoljava uslov (tj. koji prekida rastuci poredak) i na kraju samo vratis taj broj (ista analogija kao u zadatku sa trouglovima i promenljivom max). Ovom logikom ces samo vratiti najduzi podniz, ali ako ti trebaju indeksi prvog i poslednjeg clana tog podniza, samo prilikom cuvanja max duzine podniza, cuvaj i indekse.

EDIT: Imam osecaj da sam mnogo gore objasnio nego sto sam zamislio resenje. Tako da evo ga na brzinu sklepan kod.

int D = 0;
for(int i = 0; i < n; i++)
{
	int j;
	for(j = i; j < n - 1; j++)
	{
		if(niz[j] > niz[j + 1])
			break;
	}
	if(j - i > D)
		D = j - i + 1;
	i = j;//da ne bi ponovo prolazio kroz vec pronadjeni podniz
}

Ima ovde jos dosta prostora za optimizaciju, ali ideja je bitna.

[PeTkO]

Ajde probacu tvoj nacin kad se vratim veceras iz grada

[Roddick]

#include<iostream.h>

void main(void)
{
	int br,max = 0,pom;
	int* niz;
	cin>> br;
	niz = new int [br];
	for (int i = 0;i < br;i++)
		cin>> niz [i];
	i = -1;
	while (++i < br)
	{
		pom = 1;
		while (niz [i] < niz [i+1] && i < br)
		{
			pom++;
			i++;
		}
		if (pom > max)
			max = pom;
	}
	cout<< max;
}

Javite ako nesto ne valja.Mozda sam propustio neki granicni slucaj.

[PeTkO]

@Roddick radi tvoj primer, hvala

Evo jos jednog zadatka gde sam ceo dan zaglavio, jer dobijam sve osim onog sto treba da dobijem
Treba u nizu brojeva pronaci najmanji jedinstveni broj...U nizu 5, 4, 1, 2, 1, 2, 6, 2, najmanji jedinstveni je broj 4.

Ja sam probao metodom da sortiram niz u rastucem redu i da pronadjem prvi clan koji nije jednak sledecem i manji je od sledeceg. I tu uvek dobijem zadnji broj, jer jelte, nema vise brojeva posle zadnjeg. Najverovatnije mi je logika skroz pogresna, ali mi nista pametnije ne pada na pamet.

Evo koda:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main()
{
    cout << "Unesite broj ponuda: " << endl;
    int x;
    cin >> x;
    int niz[x];
    bool provera = false;
    int min;
    cout << "Unesite ponude: " << endl;
    for (int i=0; i<x; i++)
    {
        cin >> niz[i];
    }
    qsort(niz, x, sizeof(int), compare);

    for(int i=0;i<x; i++)
    {
        for (int j=1;j<x;j++)
        {
            if(niz[i] != niz[j] && niz[i] < niz[j])
            {
                min = niz[i];
            }
        }
    }
    cout << min;
    return 0;
}

[ozzytheking]

Cek, treba samo da nadjes najmanji jedinstven broj? Koj' ce ti ovol'ko for-ova?
Sortiras niz u rastucem poretku i krenes od pocetka. Ako je trenutni broj manji od sledeceg, prekidas petlju i nasao si najmanji jedinstveni broj u nizu, ako nije ides dalje dok ne naidjes na takav broj, ali pritom cuvas ovaj broj sto je duplikat da u slucaju 222345, kod ove trece dvojke ne bi vratio kako je dvojka jedinstvena.

int prethodni = <nesto>;//mora da bude razlicito od svih vrednosti u nizu
for(int i = 0; i < n - 1; i++)
{
    if(niz[i] < niz[i + 1] && niz[i] != prethodni)
    {
        //broj je pronadjen
        break;
    }
    else
        prethodni = niz[i];
}

[Roddick]

#include<iostream.h>

void main(void)
{
	int br,tek,min;
	bool x = true;
	int* niz;
	cin >> br;
	niz = new int [br];
	for (int i = 0;i < br;i++)
		cin >> niz [i];
	for (i = 0;i < br;i++)
	{
		tek = 0;
		for (int j = 0;j < br;j++)
		{
			if (niz [j] == niz [i])
				tek++;
		}
		if (tek == 1)
		{
			if (x)
			{
				min = niz [i];
				x = false;
			}
			else
				if(min > niz [i])
					min = niz [i];
		}
	}
	if (x)
		cout<<"Nema jedinstvenog broja";
	else
		cout<<min;
}

Posto ti nije bitno da bude sto efikasnije resenje, mislim da je ovo najlakse za razumevanje.Imas 2 FOR petlje.Fiksiras jedan element, i trazis u celom nizu taj element i brojis koliko puta se ponavlja.Posto ces ga naci samo jedanput ako je jedinstven, ispitujes i stampas.

[PeTkO]

@Ozzytheking Au, ne mogu da verujem da je ovako prosto. Ako mi verujes, milion kombinacija sam probao i nista mi nije uspelo, ceo dan radim taj zadatak i nikako da mi proradi mozak. Totalna blokada.

Evo jos jedan gotov zadatak:

Dat je prirodan broj n. Odrediti da li je broj n jednak proizvodu tačno dva prosta broja. Na primer, za n = 85 –
odgovor je ‘DA’.*

#include <iostream>

using namespace std;

int main()
{
    cout << "Unesite broj (manji od  2601):";
    int x;
    cin >> x;
    bool provera = false;
    int pBrojevi[15] = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51};
    for(int i=0; i<15; i++)
    {
        for(int j=0; j<15; j++)
        {
            int a = pBrojevi[i] * pBrojevi[j];
            if(a == x )
            {
                provera = true;

            }
        }
    }

    if(provera)
    {
        cout << "DA";
    }
    else
    {
    cout<<"NE";
    }
}

[ozzytheking]

Sto se tice ovih mojih resenja, testiraj ih detaljno, posto napisem ono sto mi prvo padne na pamet bez kompajliranja i testiranja/debagovanja.

[clzola]

51 nije prost broj i zaboravio si 2 xD
I stavi break kada nadjes broj, nema potrebe za daljom provjerom
Druga petlja neka ti ide od i+1. a[i] * a[j] je isto sto i a[j] * a[i]

A imas i drugo resenje koje je bolje

napravis niz od 0 do n/2+1 i popunis ga sa nulama i jedinicama. Jedan znaci da je taj index prost, a nula da nije. Na primer

int a[10] = { 0, 0, 1, 1, 0, 1, 0, 1, 0, 0 };

5 je prosto broj i zato je a[5] = 1;

E sad zadatak trazi sledece: prostoBroj * prostoBroj = nekiBroj. Sto znaci nekiBroj / prostoBroj = prostBroj. I ovo sad iskoristis

for(int i=0; i<n/2+1; i++) {
    if( a[i] == 1 && x % i == 0 ) {   // Moras da provjeravas da li je ostatak 0. Na primer broj 35/2 = 17 (Ako je u pitanju integer), a 17 je prost broj, tako da bi on rekao 35 se dobija mnozenjem dva prosta broja sto nije tacno
        int temp = x / i;
        if ( a[temp] == 1 ) {
            brojJeProst = true;
            break;
        }
    }
}

trebalo bi da radi, nisam kompajlirao
Slozenos O(n). Dok je tvoja slozenost O(n*n).
Mozes i sam da generises niz prostih brojeva. Za to ti treba algoritam "Eratostenovo sito". Ako te interesuje probaj da odradis sa time. Algoritam nije puno tezak 5-6 linija koda, a ne utice na slozenost programa, ona ostaje O(n)