Forum Sveta kompjutera

Nazad   Forum Sveta kompjutera > Test Run > Programiranje

Programiranje Programski jezici, tehnike, alatke...

Odgovor
 
Alatke vezane za temu Vrste prikaza
Stara 3.9.2012, 20:01   #1
Goonotora
Član
 
Član od: 15.10.2007.
Lokacija: Novi Beograd
Poruke: 145
Zahvalnice: 19
Zahvaljeno 4 puta na 4 poruka
Određen forumom C zadatak sa nizovima

Zadatak sa junskog ispitnog roka 2012 iz C programiranja:

Trazi se funkcija za spajanje dva ucitana niza celih brojeva u niz koji sadrzi sve elemente iz dva niza osim onih elemenata koji su isti u oba niza.

E sad ako sam dobro razumeo trazi se ovako nesto (matematicki receno) (AUB)/(A∩B)
ucitavanje nizova mi nije problem, jedino mi je problem ta funkcija, jer ne znam da li treba da poredim prvo jedan niz pa drugi ili neki drugi nacin...

Nasao sam jedan slican zadatak, ali on u treci niz stavlja elemente koji su isti u oba niza. Da li da krenem od njega?

Unapred hvala za pomoc.
Goonotora je offline   Odgovor sa citatom ove poruke
Stara 3.9.2012, 20:22   #2
voodoo_
V.I.P. GNU/Linux
 
Avatar korisnika voodoo_
 
Član od: 1.11.2005.
Poruke: 10.663
Zahvalnice: 1.807
Zahvaljeno 4.590 puta na 2.618 poruka
Određen forumom Re: C zadatak sa nizovima

Mislim da je nešto u ovom fazonu (uzmimo da su to dva niza od po 20 elemenata)

Kod:
int niz1[20];
int niz2[20];

// Prvo prebrojimo koliko ima elemenata zrelih za novi niz, a ima ih po dva za svaki indeks za koji se elementi razlikuju

int counter = 0;

for (int i=0; i<20; i++)
    if (niz1[i] != niz2[i]) counter += 2;


// Dinamički zauzimamo memoriju za novi niz, pošto nismo na početku znali koliki će biti

int* noviniz = (int*) malloc(counter * sizeof(int));

counter = 0;
for (int i=0; i<20; i++)
    if (niz1[i] != niz2[i]
    {
        noviniz[counter] = niz1[i];
        noviniz[counter+1] = niz2[i];
        counter += 2;
    }

// Kad završimo sa poslovima u vezi sa nizom, oslobađamo memoriju
free(noviniz);
Alternativno, može se napraviti i verzija sa jednim prolazom kroz izvorne nizove, s tim što ćemo na kraju uraditi realokaciju na tačnu dužinu:

Kod:
int niz1[20];
int niz2[20];
int* noviniz = (int*) malloc(40 * sizeof(int)); // Ne može biti više od 40 elemenata u najgorem slučaju


int counter = 0;

for (int i=0; i<20; i++)
    if (niz1[i] != niz2[i])
    {
        noviniz[counter] = niz1[i];
        noviniz[counter+1] = niz2[i];
        counter += 2;
    }

realloc((int*) noviniz, counter * sizeof(int));


free(noviniz);

E sad, ako oni pod elementom podrazumevaju samo vrednost, a ne vrednost sa indeksom, onda se nizovi tretiraju kao skupovi različitih veličina i rešenje je dosta složenije. Recimo, možeš da napraviš kopije nizova očišćene od duplikata u njima samima, sortiraš ih rastuće ili opadajuće i onda zaređaš duplu petlju gde porediš svaki element jednog sa svakim elemenom drugog i ubacuješ u finalni niz koji povećavaš za dva komada pre svakog uspešnog dodavanja.

Uglavnom, ako je ovo drugo, nizovi nisu najsrećniji metod. Mnogo elegantnije se rešava preko ulančane liste. Recimo, za svaki element druge liste ispitaš da li postoji u prvoj. Ako ne postoji, dodaš ga u prvu. Ako postoji, preskočiš ga, a iz prve ga ukloniš. Na kraju, ono što je ispalo od prve liste je rezultat.

Poslednja ispravka: voodoo_ (3.9.2012 u 21:24) Razlog: Dopuna
voodoo_ je offline   Odgovor sa citatom ove poruke
Stara 4.9.2012, 2:17   #3
fingerprint
Veteran
 
Član od: 5.11.2006.
Lokacija: Dark Side Of The Moon
Poruke: 1.121
Zahvalnice: 394
Zahvaljeno 594 puta na 222 poruka
Slanje poruke preko MSN-a korisniku fingerprint Slanje poruke preko Yahooa korisniku fingerprint
Određen forumom Re: C zadatak sa nizovima

Evo rešenja za taj problem. Nisam znao kako da nazovem funkciju pa sam samo lupio ime.
Kod nije preterano lep ali radi, nadam se bez puno bagova. Sutra kad ustanem napisaću ukratko i kako radi, mada mislim da je jasno.

Kod:
#include "stdlib.h"
#include "stdio.h"

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

void wubzidub(int *a, int size_a, int *b, int size_b, int **result_out, int *result_size_out)
{
	int *ab = (int*)malloc(sizeof(int) * (size_a+size_b));
	int *result = (int*)malloc(sizeof(int) * (size_a+size_b));
	memcpy(ab, a, size_a * sizeof(int));
	memcpy(ab + size_a, b, size_b * sizeof(int));
	qsort(ab, size_a+size_b, sizeof(int), &comparator);

	int *iter = ab, *end = ab + (size_a + size_b);
	int result_size = 0;
	while(iter != end)
	{
		int current = *iter;
		if((iter + 1) != end && *(iter + 1) == current)
		{
			//lookahead
			int *ahead_iter = iter + 1;
			while(ahead_iter != end && *ahead_iter == current)
				ahead_iter++;
			iter = ahead_iter;
		}
		else
		{
			result[result_size] = *iter;
			result_size++;
			iter++;
		}
	}
	free(ab);
	*result_out = result;
	*result_size_out = result_size;
}


int main(int argc, char* argv[])
{
	int a[5] = {1, 2, 5, 6, 2};
	int b[5] = {6, 2, 5, 8, 3};
	int *result;
	int sz;
	wubzidub(a, 5, b, 5, &result, &sz);
	for(int i = 0; i < sz; ++i)
		printf("%d ", result[i]);
	printf("\n");
	getchar();
	return 0;
}
EDIT: Ovaj program zapravo ne radi šta treba u svim slučajevima. Pogledaću sutra :|
fingerprint je offline   Odgovor sa citatom ove poruke
Stara 4.9.2012, 2:58   #4
Ivan452
Veteran
 
Član od: 25.7.2008.
Lokacija: Beograd
Poruke: 772
Zahvalnice: 33
Zahvaljeno 189 puta na 152 poruka
Slanje poruke preko MSN-a korisniku Ivan452
Određen forumom Re: C zadatak sa nizovima

@Goonotora
Koliko kapiram ovo ti je ispit iz nekog uvoda u programiranje?
Ako je tako smatram da je resenje koje ti je fingerprint ponudio isuvise komplikovano za razumevanje(posebno bez pojasnjenja autora).
Resenje koje cu ti ja ponuditi nadovezuje se na ovo koje ti je voodoo ponudio (medjutim u zadatku kada se kaze na element mislis se bilo gde u nizu a ne na odredjenoj poziciji pa njegovo nije to ispunilo).
Kod pisem napamet, pa javi se ako nesto ne radi. Generalno ne volim da dajem 100% resenja, tako da ces neke stvari morati sam da resis.

Kod:
int niz1[20];
int niz2[20];
int* niz3= (int*) malloc(40 * sizeof(int));

int counter = 0;
int postoji=0;

for (int i=0; i<20; i++)
    {
        for (int j=0; j<20; j++)
        {
            if (niz1[i] == niz2[j])
            {
                postoji=1;
                break;
            }
        }

        if(postoji==0)
            niz3[counter++] = niz1[i];

        postoji=0;
    }

for (int i=0; i<20; i++)
{
    for (int j=0; j<20; j++)
    {
        if (niz2[i] == niz1[j])
        {
            postoji=1;
            break;
        }
    }
    if(postoji==0)
        niz3[counter++] = niz2[i];

    postoji=0;
}

realloc((int*) niz3, counter * sizeof(int));
free(niz3);
Ovo ti je najjednostavnije, skolsko resenje, ali takodje i najneoptimalnije.
Prvo prolazis kroz sve element prvog niza i uporedjujes sa svim clanovima drugog niza.
Ako se nadje isti clan promenljiva postoji se postavlja na 1 i izlazi se iz unutrasnje petlje (jer je nepotrebno dalje da se proverava).
Ako po izlasku iz unutrasnje petlje promenljiva postoji nije promenila vrednost ona znaci da taj element ne postoji u oba niza i on se upisuje u niz3.
Kada se ovo zavrsi, potom se svaki element drugog niza uporedjuje sa svakim elementom prvog niza. I radi se istva stvar.


Kada ovo razumes, prva popravka bi bila da resis problem ako jedan niz sadrzi 2 ista elementa koja drugi niz nema. Npr:
niz1: 1 1 2 3 4
niz2: 2 3 4 5 6
rezultujuci niz3 bi bio: 1 1 5 6.
Posle toga mozes da resavas da nizovi ne budu fiksirani na maksimum od 20 elemenata.

Ako se od vas ipak ocekuje malo bolje resenje ovakvih problema (sa algoritamske strane).
Mnogo bolje resenje mozes npr. da dobijes ovako:

1. Sortiras niz1 i niz2 i ocistis od duplikata.
2. Jednim prolazom kroz oba niza uporedjujes da li je prvi clan niza1 manji od prvog clana niza2. Ako jeste povecavas index niza1 koji gledas i upisujes u niz3. Ako je posmatrani element niza2 manji od niza1 upisujes taj element niza2 u niz3 i povecavas index niza2.

Ovim dobijas optimalno resenje kompleksnosti O(n) i od ovog ne moze bolje. Naravno, varijacije na temu postoje.
Ivan452 je offline   Odgovor sa citatom ove poruke
Stara 5.9.2012, 11:41   #5
Stevvan
Veteran
 
Član od: 17.12.2005.
Lokacija: Zarkovo, Beograd
Poruke: 1.114
Zahvalnice: 97
Zahvaljeno 179 puta na 104 poruka
Slanje poruke preko MSN-a korisniku Stevvan Slanje poruke preko Skypea korisniku Stevvan
Određen forumom Re: C zadatak sa nizovima

Kod:
int niz1[20], n1;
int niz2[20], n2;
int res[40], r;

void dodajElement(int elem, int *niz, int *duzina) {
    for (int i = 0; i < (*duzina); i++) {
        if (niz[i] == elem)
            return;
    }
    niz[*duzina] = elem;
    (*duzina)++;
}

int main() {
    //Ucitaj niz1, niz2 i njihove duzine
    r = 0;
    for (int i = 0; i < n1; i++)
        dodajElement(niz1[i], res, &r);
    for (int i = 0; i < n2; i++)
        dodajElement(niz2[i], res, &r);
    return 0;
}
Nisam testirao, trebalo bi da radi slozenost je manja od (n1+n2)^2. Ako si upoznat sa pokazivacima, resenje ne bi trebalo da te zbunjuje previse

Edit:
Zaboravio sam da napomenem, izbaci ce sve moguce kopije iz nizova, tako da ce ostati samo skroz razlicite vrednosti. Tako da ako se nadje npr. da niz1 ima clanove 1 2 5 2 3, uzece samo prvu dvojku

Poslednja ispravka: Stevvan (5.9.2012 u 11:45) Razlog: dodatno objasnjenje
Stevvan je offline   Odgovor sa citatom ove poruke
Stara 26.9.2012, 11:38   #6
tina
Novi član
 
Član od: 25.9.2012.
Poruke: 11
Zahvalnice: 1
Zahvaljeno 0 puta na 0 poruka
Exclamation Re: C zadatak sa nizovima

znali neko da mi uradi zadate iz programiranja il da mi barem objasni.hvala u napred
tina je offline   Odgovor sa citatom ove poruke
Stara 26.9.2012, 11:52   #7
ivan90BG
Veteran
 
Član od: 3.5.2008.
Lokacija: Beograd
Poruke: 760
Zahvalnice: 81
Zahvaljeno 213 puta na 144 poruka
Određen forumom Re: C zadatak sa nizovima

Pa prvo moraš da nam napišeš zadatak.
ivan90BG je offline   Odgovor sa citatom ove poruke
Odgovor

Bookmarks sajtovi

Alatke vezane za temu
Vrste prikaza

Vaš status
Ne možete postavljati teme
Ne možete odgovarati na poruke
Ne možete slati priloge uz poruke
Ne možete prepravljati svoje poruke

BB kod: uključeno
Smajliji: uključeno
[IMG] kod: uključeno
HTML kod: isključeno


Slične teme
tema temu započeo forum Odgovora Poslednja poruka
Vicevi Oblivion Cvet kompjutera 5469 7.4.2021 17:33
Toonstruck dijego_ Avanturističke igre 17 4.8.2015 17:53
Problemi sa efiks-om.. kwar Grafika 2 23.12.2008 10:51
zadatak sa n-touglom barjaktar Programiranje 9 5.7.2006 10:57


Sva vremena su po Griniču +2 h. Sada je 8:38.


Powered by vBulletin® verzija 3.8.7
Copyright ©2000–2021, vBulletin Solutions, Inc.
Hosted by Beograd.com