Domaci iz programskih jezika

[Krule]

Finaly 

Kod Izaberi Expand


//Copyright 2011 Mirko Kruscic. All rights reserved.

#include "stdio.h"

void unos (int a[], int n)
{
for (int i=0;i<n;i++)
{
printf("A[%d]= ",i+1);
scanf("%d",&a[i]);
}
}
void ispis (int a[], int n)
{
for (int i=0;i<n;i++)
printf("\nA[%d]= %d",i+1,a[i]);
}

int testiranje(int a[], int n)
{
int b=0,k,s;
for (int i=0;i<n;i++)
{
s=a[i];
k=i+1;
while (a[i]==a[k])
{
s+=a[i];
k++;
}
a[b]=s;
b++;
if (k!=i+1)
i=k-1;

}
return (b);
}

int main()
{
int k,a[250],n;
printf("Uneti broj clanova niza a potomi niz: ");
scanf("%d",&n);
unos(a,n);
k=testiranje(a,n);
printf("\n\nNovi niz je: ");
ispis(a,k);

getchar();
return 0;
}

Ako Vam ovaj kod bude, mozda nekim slucajem  , bagovao ostavicu i c++ kod posto sam prvo u njemu radio pa posle samo prebacio cin i cut u scanf i printf i sve sto ide uz te komande. 

Edit: Tek sam sad video da ima skoro isti zadatak na vezbama iz struktura i da je umesto

Kod Izaberi Expand

if (k!=i+1)
     i=k-1;moglo da se jednostavno napise k++;i++; jos u while petlji

[holodoc]

Mali praktičan savet. Pokušaj da funkcije koristiš isključivo za kod koji će se izvršavati više od jednog puta, tj. za tzv. "reusable" kod. Funkcije mogu da spreče nepotrebno ponavljanje koda ali mogu i bitno da uspore aplikaciju jer se svakim pozivom funkciji menja kontekst toka izvršavanja aplikacije pa hardver mora da troši dodatne procesorske cikluse za te operacije.

Za ovako jednostavan primer kao što je tvoj to i nije preterano veliki problem ali pogledaj recimo sledeći primer gde imaš petlju koja ima par desetina ili čak stotina hiljada iteracija.
Primer 1

Kod Izaberi Expand

void funkcija(){
// Kod funkcije.
}

for(i = 0; i < 100000; i++){
     funkcija();
}

Primer 2

Kod Izaberi Expand

for(i = 0; i < 100000; i++){
     // Kod "funkcije".
}
Sa 10 000 i više iteracija preciznim merenjem ćeš utvrditi značajnu prednost drugog primera jer isti ne troši vreme na pozivanje funkcije i time gubi ne dodatno vreme. Tek sa 100 000 i više iteracija prednost nepozivanja funkcija kada to zaista nije potrebno se uočava.

U tvom konkretnom primeru razlike u performansama nećeš uočiti ako sadržaj funkcija unos() i ispis() ubaciš u main() ali ćeš pratiti ustaljenu praksu koja kaže da se kod koji se ne upotrebljava više od jednog puta ne odvaja u funkcije. Plus što je kod lakši za praćenje.

Da ne bude zabune, kod C++-a je situacija recimo skoro potpuno drugačija jer se tamo zbog tzv. "enkapsulacije" (težnje da klase mogu da budu "same sebi dovoljne i nezavisne od ostalih") gleda da se čak i najmanja sposobnost klase evidentira metodom (ekvivalent funkciji sa bitnom razlikom da metoda mora da opisuje sposobnost klase). Otom potom

[marjan]

Znam da malo idem u offtopic, ali me holodoc asocirao da dodam - znači, Žepi,  holodoc je kriv, nisam ja! 

Elem, pozivanje funkcije podrazumeva "pakovanje" parametara na stek, kao i povratne adrese pozivajuće f-je itd, a ako ima toga puno, onda se stek optereti, a ako se mnogo često f-je pozivaju, onda to "šetanje" ume da potraje, pa ako postoji rekurzija, i da pukne itd.
Elem, postoji ono što se zove inline funkcija - kada se f-ja definiše kao inline, znači da kad je neko pozove, kod ne skače na nju, nego je kod faktički iskopiran u pozivajućoj f-ji - ovde u main()u. Praktikuje se za manje funkcije - u suprotnom nije baš celishodno, jer uvećava program.

Elem, evo mali primer, prost mnogo.

Kod Izaberi Expand


#include <stdio.h>
inline void radinesto1(int i)
{
while (i <1000)
i++;
printf("Zavrsio prvi\n");
}

void radinesto2(int i)
{
while (i <1000)
i++;
printf("Zavrsio drugi!\n");
}


int main(int argc, char**argv)
{
int broj;
printf("Unesi neki mali broj :) %d:\n"),
scanf("%d", &broj);

radinesto1(broj);
radinesto2(broj);

return 0;
}

Ovde je jedna funkcija (radinesto1) inline, a druga (radinesto2) je "obična". A rade iste stvari i telo izgleda identično. Uvećava neki brojač do hiljadu.
Kada se pogleda asembly (počev od starta main-a), vidi se da se "pozivanje" inline svodi na kopiranje inline koda, dok druga f-ja ima regularan call.

[holodoc]

Nevolja kod inline funkcija je što kompajleri umeju ponekad da se prave mutavi i da ih ignorišu pa ih zato nećeš baš često nalaziti u kodu sa multiplatformskom podrškom U svakom slučaju poenta je ista... Ne pozivati funkciju ako kod može lepo da se izvrši u kontekstu trenutnog toka izvršavanja.

[Zepi]

Što se tiče poziva funkcija koje se možda samo jednom pozivaju slažem se da može doći do gubitka performansi ali samo u ekstremni slučajevima sa rekurzivnim funkcijama na primer to može imati uticaja.

Pretmet prvog dela vežbi iz programskih jezika upravo rad sa funkcijama pa za vežbu treba svaki problem da reše preko funkcija i da koriste što više manjih funkcija dok se ne naviknu.
Ali ne vezano za ovo ja ovakav pristup preporučujem iz više razloga:

• preglednost koda
• reusable kod
• razvoj višeslojnih aplikacija gde se isključivo funkcijama komunicira sa drugim nivoima
• prednost pri radu u većim grupama gde svako ima svoj deo zadatka tj funkciju da napise
• navikavanje na pisanje metoda za objektne jezike

[holodoc]

Što se tiče poziva funkcija koje se možda samo jednom pozivaju slažem se da može doći do gubitka performansi ali samo u ekstremni slučajevima sa rekurzivnim funkcijama na primer to može imati uticaja.

E ali rekurzivne funkcije su danas po nečemu toliko posebne da zbog tog "nečeg"mogu ponekad da sa'rane i klasičnu iterativnu obradu podataka (klasične petlje u neprekidnom toku obrade)

"Tail recursion". Ring a bell? Iskreno nemam pojma kako ovo domaći autori prevode ako uopšte prevode. Možda "repno ponavljanje" Ukratko, ovo je fora pozajmljena iz programskog jezika Scheme (prvo su njegovi kompajleri podržavali ovaj vid optimizacije) a poenta cele priče je da ako rekurzivna funkcija vrši rekurziju u poslednjoj liniji funkcije koja je već pod rekurzijom onda se uopšte ne radi granjanje i formiranje novog steka (ne radi se poziv) već kompajler radi posebnu vrstu inline zamene koda i tako sprečava da se uopšte rade bilo kakvi prekidi (i popunjavanje steka kad smo već kod toga)

U kratkim crtama objašnjenje kako prepoznati "repnu" rekurziju.

Kod Izaberi Expand

void funkcija(){
     // Neki kod...
     return funkcija();
}
Ovde se jasno vidi da se rekurzivni poziv nalazi na poslednjoj liniji funkcije koja je potencijalno već rekurzivno pozvana pa pošto je to poslednja linija nema potrebe da se pamti adresa na koju program treba da se vrati kad se završi rekurzivni poziv (jer nema više linija posle rekurzivnog poziva) Kompajler ovo jasno identifikuje kao tail rekurziju i optimizuje krajnji program sa raznim inline zamena i sl.

Dobra stvar kod tail rekurzije je što je bar 99% rekurzivnih funkcija ovog tipa. Da ne bude zabune ne mora poslednja linija koda u rekurzivnoj funkciji da bude rekurzivni poziv već je bitno samo da tok programa ne sadrži više ni jednu liniju posle rekurzivnog poziva. Evo jednog primera kako najčešće izgleda realna rekurzivna funkcija.

Kod Izaberi Expand

void funkcija(){
     if(uslov){
          return funkcija();
     } else {
          // Neki kod...
     }
}
Ovde se jasno vidi da je tok uslovnog if bloka takav da posle njega nema više nijedne linije koda i ovo će kompajler jasno prepoznati kao "tail rekurziju"

"Tail rekurzija" mora eksplicitno da se "uključi" u kompajlerima sa -O opcijama i ako me sećanje dobro služi (nisam odavno pisao C/C++ kod) potreban je level 3 optimizacije -O3 da bi "tail rekurzija" bila uključena.

EDIT: Uz ovaj post sam prikačio jedan PDF dokument koji detaljno objašnjava "tail rekurziju". Inače ovo je diplomski rad Marka Probsta, u tadašnje vreme diplomca Tehničkog fakulteta u Beču koji je u velikoj meri odgovoran za to što je GNU GCC dobio dobru podršku za "tail rekurziju" Okačio sam ga ovde zato što je originalan dokument u PostScript formatu pa bi bio potreban Acrobat Distiller da se od njega dobije PDF dokument. Ovako sam ga ja konvertovao u PDF

Čisto usput da vidite kako izgleda diplomski rad diplomca u bečkom sistemu visokoškolskog obrazovanja

P.S. Negde možda ima teksta na nemačkom ali to ne bi trebalo da predstavlja problem jer su najbitniji delovi na engleskom.

[MilosM]

ok... prvi kolokvijum je prosao. Osvojio sam 70% poena, kodovi funkcija su uglavnom bili ok, ali pozivanje funkcije je bilo veoma lose. Hteo sam to naravno da popravim smatrajuci da znam vise. bio je i popravni osvojio sam 59% i ukapirao da sam naucio pozivanje funkcija ali kodove nisam umeo da resim, ipak je programiranje test inteligencije...   
Elem...  domaci idu dalje radili smo pokazivace, i poslednji cas smo radili malloc, realloc i calloc, funkcije za dinamicku alokaciju niza...

domaci je naci presek dva niza, na casu smo radili uniju pa cu je porediti na osnovu tog zadatka...

Ideje? 

[holodoc]

ok... prvi kolokvijum je prosao. Osvojio sam 70% poena, kodovi funkcija su uglavnom bili ok, ali pozivanje funkcije je bilo veoma lose. Hteo sam to naravno da popravim smatrajuci da znam vise. bio je i popravni osvojio sam 59% i ukapirao da sam naucio pozivanje funkcija ali kodove nisam umeo da resim, ipak je programiranje test inteligencije...   
Elem...  domaci idu dalje radili smo pokazivace, i poslednji cas smo radili malloc, realloc i calloc, funkcije za dinamicku alokaciju niza...

domaci je naci presek dva niza, na casu smo radili uniju pa cu je porediti na osnovu tog zadatka...

Ideje? 

Pa nema tu ideja. Dinamičko alociranje ti neće pomoći da na drugačiji način rešiš zadatak već da budeš u mogućnosti da radiš sa podacima koji nemaju predefinisanu veličinu A

ko znaš da uradiš zadatak sa statički zadatim dužinama niza onda samo treba da uradiš isti taj kod tako da koristi dinamički alociranu memoriju.

[Marko Аcović]

Evo ti ukratko ideja:

Kod Izaberi Expand


/**
* Proverava da li dati element postoji u nizu
*
* @param int* a, pokazivac na niz
* @param int n, dimenzija niza
* @param int elem, element za koji se proverava da li je u nizu
* @return int 1=elem postoji u nizu, 0=elem ne postoji u nizu
*/   
int inArray(int *a, int n, int elem) {
    int i;
    int found = 0;
    for (i = 0; < n; ++i) {
        if (elem == a[i]) {
            found = 1;
            break;
        }
    }
    return found;
}

int main(void)
{
    // deklaracija promenljivih
    // unos elemenata oba niza
    // definisi rezultujuci niz koji ce da sadrzi presek
    int *result = calloc(n, sizeof(int));
   
    // prodji kroz elemente veceg niza (npr. niz A)
    j = 0;
    for (i = 0; i < n; ++i) {
        // za svaki element niza A proveri da li se nalazu u B
        if (inArray(b, m, a[i])) {
            // ako se nalazi, proveri da li se nalazi u rezultujucem nizu
            // ovo nam treba da se neki od elemenata ne bi ponavljao
            if (!inArray(result, n, a[i])) {
                // ako se NE nalazi u rezultujucem nizu, ubaci u rezultujuci niz
                result[j++] = a[i];
            }
        }
    }
   
    // stampaj rezultujuci niz
    return 0;
}


Kod nisam proveravao, jer pisem napamet ali to bi mogla da ti bude ideja. Nadam se da sam bio od pomoci

[holodoc]

Evo ti ukratko ideja:

Kod Izaberi Expand


/**
* Proverava da li dati element postoji u nizu
*
* @param int* a, pokazivac na niz
* @param int n, dimenzija niza
* @param int elem, element za koji se proverava da li je u nizu
* @return int 1=elem postoji u nizu, 0=elem ne postoji u nizu
*/   
int inArray(int *a, int n, int elem) {
    int i;
    int found = 0;
    for (i = 0; < n; ++i) {
        if (elem == a[i]) {
            found = 1;
            break;
        }
    }
    return found;
}

int main(void)
{
    // deklaracija promenljivih
    // unos elemenata oba niza
    // definisi rezultujuci niz koji ce da sadrzi presek
    int *result = calloc(n, sizeof(int));
   
    // prodji kroz elemente veceg niza (npr. niz A)
    j = 0;
    for (i = 0; i < n; ++i) {
        // za svaki element niza A proveri da li se nalazu u B
        if (inArray(b, m, a[i])) {
            // ako se nalazi, proveri da li se nalazi u rezultujucem nizu
            // ovo nam treba da se neki od elemenata ne bi ponavljao
            if (!inArray(result, n, a[i])) {
                // ako se NE nalazi u rezultujucem nizu, ubaci u rezultujuci niz
                result[j++] = a[i];
            }
        }
    }
   
    // stampaj rezultujuci niz
    return 0;
}


Kod nisam proveravao, jer pisem napamet ali to bi mogla da ti bude ideja. Nadam se da sam bio od pomoci

Hm... To nije ideja to je kod ;D

[Marko Аcović]

Dobro, necemo sad u detalje 

[MilosM]

evo moje ideje...

Kod Izaberi Expand


#include<stdio.h>
#include<stdlib.h>
int main(int argc, char *argv[]){
int n1,n2,n3,i,j;
double *s1, *s2, *s3;

printf("Unesi broj elemenata skupova: ");
scanf("%d%d",&n1,&n2);

s1=(double *)malloc(n1*sizeof(double));

printf("Elementi prvog skupa su: ");
for(i=0;i<n1;scanf("%lf",&s1[i++]));
if (n1==0) putchar('\n');

s2=(double *)malloc(n2*sizeof(double));

printf("Elementi drugog skupa: ");
for(i=0;i<n2;scanf("%lf",&s2[i++]));
if (n2==0) putchar('\n');
if(n1>n2)
s3=(double *)malloc((n1)*sizeof(double));

for(n3=0;n3<n1;n3++);
for(j=0;j<n2;j++){
for(i=0;i<n1;i++)
if(s2[j]==s1[i]) break;
s3[n3++]=s2[j];
}
s3=(double *)realloc(s3,n3*sizeof(double));
else
s3=(double *)malloc((n2)*sizeof(double));
for(n3=0;n3<n1;n3++);
for(j=0;j<n2;j++){
for(i=0;i<n1;i++)
if(s2[j]==s1[i]) break;
s3[n3++]=s2[j];
}
s3=(double *)realloc(s3,n3*sizeof(double));

printf("Presek pocetnih skupova: ");
for(i=0;i<n3;i++)
printf("%lf ",s3[i]);
free(s1);
free(s2);
free(s3);
    return 0;
}

nisam siguran dal moze...

[MilosM]

greska u drugoj for petlji n3 ide do n2... n3<n2

[Marko Аcović]

Nisam proveravao funkcionalnost ali cim ti se ponavlja kod, znaci da ti dizajn nije dobar. Krsis DRY (Don't Repeat Yourself) princip. Zato su i izmisljene funkcije kako bi kod koji se ponavlja izmestio u njih.

[Zepi]

Kod ima gresaka i logickih i sintaksickih.

Sto se tice ponavljanja koda to u ovom slucaju nije bila poenta a normalno da se funckije pisu gde god je potrebno(unos dva niza dobar primer )

prvo:

Kod Izaberi Expand


for(n3=0;n3<n1;n3++);


ne radi nista tj isto kao i n3 = n1;

drugo ovo je presek skupa a ne unija pa ni provera koja je dimenzija veca nije potrebna pa samim tim ni else deo koda.

Da bi ovo stvarno bila dobra vezba, valjalo bi ovo resiti pokazivacima i dinamckom alokacijom memorije pomocu funkcija, ciji deklaracija bi trebala da izgleda ovako:

Kod Izaberi Expand


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

void unos(double* a, int n){

}

void ispis(double* a, int n){

}

void presek(double* s1, int n1, double* s2, int n2, double* s3, int *n3){

}

int main(int argc, char *argv[]){
int n1,n2,n3;
double *s1, *s2, *s3;

printf("Unesi broj elemenata skupova: ");
scanf("%d%d",&n1,&n2);

s1=(double *)malloc(n1*sizeof(double));

unos(s1, n1);

s2=(double *)malloc(n2*sizeof(double));

unos(s2, n2);

ispis(s1, n1);
ispis(s2, n2);

        s3=(double *)malloc((n1)*sizeof(double));

presek(s1, n1, s2, n2, s3, &n3);

s3=(double *)realloc(s3,n3*sizeof(double));

printf("\n\nPRESEK\n");
ispis(s3, n3);

free(s1);
free(s2);
free(s3);
    return 0;
}


Popunite tela funkcija tj definisite sta treba da rade a da rese ovu problematiku.
Napomena: raditi sve preko pokazivaca tj. da u kodu nema nigde simbola za niz [].

JOS JEDNA:
obratiti paznju na sledeca dva skupa:
n1 = 2, 2, 3, 4
n2 = 3, 3, 2, 5

resenje treba da bude:
n3 = 2, 3

ipak je programiranje test inteligencije...   

POZDRAV