|
Programiranje Programski jezici, tehnike, alatke... |
|
Alatke vezane za temu | Vrste prikaza |
3.9.2012, 20:01 | #1 |
Član
Član od: 15.10.2007.
Lokacija: Novi Beograd
Poruke: 145
Zahvalnice: 19
Zahvaljeno 4 puta na 4 poruka
|
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. |
3.9.2012, 20:22 | #2 |
V.I.P. GNU/Linux
Član od: 1.11.2005.
Poruke: 11.166
Zahvalnice: 2.086
Zahvaljeno 4.923 puta na 2.859 poruka
|
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); 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 |
4.9.2012, 2:17 | #3 |
Veteran
|
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; } |
4.9.2012, 2:58 | #4 |
Veteran
|
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); 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. |
5.9.2012, 11:41 | #5 |
Veteran
|
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; } 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 |
26.9.2012, 11:38 | #6 |
Novi član
Član od: 25.9.2012.
Poruke: 11
Zahvalnice: 1
Zahvaljeno 0 puta na 0 poruka
|
Re: C zadatak sa nizovima
znali neko da mi uradi zadate iz programiranja il da mi barem objasni.hvala u napred
|
26.9.2012, 11:52 | #7 |
Veteran
Član od: 3.5.2008.
Lokacija: Beograd
Poruke: 760
Zahvalnice: 81
Zahvaljeno 213 puta na 144 poruka
|
Re: C zadatak sa nizovima
Pa prvo moraš da nam napišeš zadatak.
|
Bookmarks sajtovi |
|
|
Slične teme | ||||
tema | temu započeo | forum | Odgovora | Poslednja poruka |
Vicevi | Oblivion | Cvet kompjutera | 5481 | 27.5.2022 5:52 |
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 |