[es] - [Zadatak] Spajanje dva ucitana niza...

Predrag Student
Beograd,Srbija

Član broj: 291472
Poruke: 1
92.244.133.*

Profil

Re: [Zadatak] Spajanje dva ucitana niza...

^{05.10.2011. u 10:09 - pre 152 meseci}

Imam isti tip zadatak na ispitu sutra, glasi ovako:
1. Napisati funkciju na programskom jeziku C za spajanje dva učitana niza celih brojeva u rezultujući niz koji sadrži sve elemente iz dva niza *osim onih elemenata koji su isti u oba niza. U glavnom programu uneti dužinu niza i pozvati funkcije za učitavanje i spajanje niza.

*Razlika je samo u delu zadatka gde se traži ispis svih elemenata iz dva niza osim elemenata koji su isti u oba niza.

Da li neko zna da ovaj postojeći kod koji je ovde na forumu okačen preformuliše u ovaj koji se traži?

----------------------------
Podsetnik: kod koji je urađen (na forumu) za ispisivanje svih elemenata koji su isti u oba niza:
------------------------------
code:

Code:

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

main()
{
    int n,m,i,min;
    int *A,*B,*C;
    printf("Unesite broj clanova niza A:");
    scanf("%d",&n);
    A=citaj(n);
    sort(n,A);

    printf("Unesite broj clanova niza B:");
    scanf("%d",&m);
    B=citaj(m);
    sort(m,B);

    printf("***************************************************\n");
    printf("Clanovi niza A:\n");
    pisi(n,A);
    printf("\n");
    printf("Clanovi niza B:\n");
    pisi(m,B);

    if (m > n)
    {
        min = n;
    }
    else
    {
        min = m;
    }

    C = (int*)malloc(min*sizeof(int));

    min = presek(A,n,B,m,C);
    realloc(C,min*sizeof(int));

    printf("\n");
    printf("***************************************************\n");
    printf("***************************************************\n");
    printf("Clanovi koji su isti u oba niza su:\n");

    for (i=0; i<min; i++)
        printf("c[%d]= %d\n", i, C[i]);

    printf("***************************************************\n");
    printf("***************************************************\n");

    free(A);
    free(B);
    free(C);

    getch();
}

int citaj(int n)
{
    int i;
    int *a;

    a = (int*)malloc(n*sizeof(int));

    if (a == 0)
    {
        printf("Greska!!! Nema dovoljno memorije!!!");
        return 1;
    }

    for(i=0;i<n;i++)
    {
        printf("a[%d]=",i);
        scanf("%d",&a[i]);
    }

    return realloc(a,n * sizeof(int));
}

int pisi(int n,int *a)
{
    int i;

    for(i=0;i<n;i++)
    {
        printf("a[%d]=",i);
        printf("%d\n",a[i]);
    }
}

int sort(int n, int * a)
{
    int i,j,tmp;

    if (n <= 0)
        return n;

    for(i=0;i<n-1;i++)
        for(j=i+1;j<n;j++)   // indeksi i<j
            if(a[i]>a[j])
            {
                tmp=a[i];  // razmena a[i] i a[j]
                a[i]=a[j];
                a[j]=tmp;
            }

    return n;
}

int presek(int *A, int set_size1,
           int *B, int set_size2,int *rezultat)
{

    int i,j,k;

    k=0;
    for (i=0; i<set_size1; i++)
        for (j=0; j<set_size2; j++)
            if( A[i] == B[j] )
            {
                rezultat[k++] = A[i];
                B[j] = B[set_size2-1];
                set_size2--;
                break;
            };

    return k;

    system("pause");
}

--------------------------------------------------------------

Hvala vam unapred, za svaku vrstu pomoći!

_{[Ovu poruku je menjao Mihajlo Cvetanović dana 05.10.2011. u 11:24 GMT+1]}

Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249

+96 Profil

Re: [Zadatak] Spajanje dva ucitana niza...

^{05.10.2011. u 11:00 - pre 152 meseci}

Pa prva stvar je da ona promenljiva min (veličina rezultatnog niza) mora da uzme u obzir najgori scenario. U ovom slučaju najgori scenario je da nema ni jednog elementa zajedničkog u oba niza, što znači da u rezultatni niz ulaze svi elementi iz oba niza. Promenljiva min treba da dobije vrednost m+n, a ne min(m, n). Shodno tome ne bi trebalo ni da se zove min, i bolje bi bilo da se zove duzina_C, ili nešto drugo što ne govori o tome kako je dobijeno, nego čemu služi.

Drugo, funkcija koja radi posao verovatno ne treba da se zove presek, jer se ne traži presek nego simetrična razlika.

Treće, trenutni kod u funkciji presek nije optimalan za računanje preseka, jer ne koristi činjenicu da su nizovi sortirani. Postoji bolji kod koji ima jednu petlju umesto dve. U toj jednoj petlji koristimo dva indeksa, po jedan za svaki niz, ali u jednom prelazu petlje inkrementiramo samo jedan od ta dva, i to onaj koji referencira manji od dva elementa. Cilj ovakve logike je da jurimo iste elemente u dva niza. Funkcija presek je trebalo da izgleda ovako:

Code:
int presek(int *A, int set_size1,
           int *B, int set_size2,int *rezultat)
{
    int i, j, k;

    i = j = k = 0;

    while (i < set_size1 && j < set_size2)
    {
        if (A[i] == B[j])
        {
            rezultat[k++] = A[i];
            i++;
            j++;
        }
        else if (A[i] < B[j])
            i++;
        else
            j++;
    }

    return k;
}

Kad se ovako postave stvari onda računanje simetrične razlike biva lakše. Opisaću šta treba, a ti probaj to da realizuješ. Imaj u vidu da su oba niza sortirana. Funkcija i dalje treba da inkrementira onaj indeks sa manjim elementom, ili oba, ako su elementi jednaki, stoga tu logiku ne diraj. Ono što je razlika je da funkcija treba da nađe elemente koji su različiti, a ne jednaki, tako da ona linija gde se popunjava niz rezultat sad treba da stoji u druge dve grane. Novi element niza rezultat treba da dobije manju vrednost od dve dostupne. Ako ti nije jasno šta se dešava onda uzmi na papiru dva sortirana niza, i prvo nađi presek, a onda nađi i simetričnu razliku, i to tako što slediš logiku sa inkrementiranjem onog indeksa čiji je element manji u svakom koraku. Kad vidiš na papiru kako to radi, biće ti lakše da to pretvoriš u kod.

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: [Zadatak] Spajanje dva ucitana niza...

^{05.10.2011. u 14:13 - pre 152 meseci}

Samo da na brzinu odgovorim na zapažanje na neoptimizovani kod:

http://www.elitesecurity.org/t436366-0#2945515

Kao što se iz mog posta na ovoj temi vidi, ja sam dao rešenje koje ne zahteva da su nizovi sortirani, dok je night rider, deo sa bubble sort ubacio potpuno nepotrebno iz prethodnih snipeta koji nisu rešavali problem (po meni je daleko bolje da night rider nauči kako da koristi bibliotečku funkciju qsort, nego da piše najgori mogići kod po pitanju performansi za sortiranje).

Sada mi je žao što sam dao gotov kod, jer vidim da night rider nije ništa naučio iz njega, a sutra mu je ispit.

Zato ću ti reći isto što kažem i mojoj desetogodišnjoj ćerki kad ima problem sa zadakom iz matematike: NACRTAJ SLIKU!

Ono što tebi treba je da od unije dva skupa (predstavljenih nizovima) oduzmeš presek ta dva skupa. Funkciju za presek imaš od pre, napravi trivijalnu funkciju za uniju i iskoristi caku za brisanje člana niza koju sam ti demonstrirao u svom primeru...

edit: ne treba da se radi prvo unija pa oduzimanje preseka nego (a-p) unija (b - p) gde su ti a i b ulazni nizovi, a p njihov presek..

_{[Ovu poruku je menjao djoka_l dana 05.10.2011. u 15:45 GMT+1]}

Odgovor na temu