Thread Closed 
 
Thread Rating:
  • 0 Votes - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
C++ primjeri
Author Message
schmrz Offline
____
*

Posts: 567
Joined: Feb 2007
Post: #41
RE: C++ primjeri
Pa zato je i dobio opomenu

I have no drinking problems. I drink. Get drunk. Fall down. NO PROBLEM
Registered As Linux User #484215
Moj skromni blog
Savjet za buduće programere: ovdje
25-04-2009 10:39 AM
Find all posts by this user
ivicasb Offline
Novi korisnik
*

Posts: 12
Joined: Aug 2009
Reputation: 0
Post: #42
RE: C++ primjeri
Bok Ljudi!
Evo patim se sa programiranjem i c++ vec 15-ak dana.Imam ispit uskoro i evo zamolio bih vas koji znate da mi pokusate rijesiti zadatak koji je bio na proslom ispitu.Za mene je on pretezak i zato ga ne mogu zapoceti(hvala na razumijevanju)Evo ga;
Puno hvala proficima na rijesenju unaprijed!Palac-gore
(Dolje na Attachmentu sve pise)


Attached File(s)
.doc  Vjezba sa Ispita.doc (Size: 40 KB / Downloads: 26)
(This post was last modified: 04-08-2009 05:11 PM by ivicasb.)
04-08-2009 05:10 PM
Find all posts by this user
schmrz Offline
____
*

Posts: 567
Joined: Feb 2007
Post: #43
RE: C++ primjeri
Kažeš ( u ovoj temi )da si pročitao ovu knjigu. Prema tome, u njoj je vjerovatno objašnjeno pretraživanje polja metodom slijednog i binarnog pretraživanja kao i Merge i Quick sort. Jednostavno pogledaš u knjizi gdje su objašnjene te metode i onda to novostečeno znanje primjeniš da riješiš ovu vježbu.

Ako gdje zapne, javiš se. Vjeruj mi, najmanje će ti pomoči ako ti neko napiše program a ti ga pokušaš napamet naučiti.

I have no drinking problems. I drink. Get drunk. Fall down. NO PROBLEM
Registered As Linux User #484215
Moj skromni blog
Savjet za buduće programere: ovdje
05-08-2009 12:18 AM
Find all posts by this user
ivicasb Offline
Novi korisnik
*

Posts: 12
Joined: Aug 2009
Reputation: 0
Post: #44
RE: C++ primjeri
Ok Schmrz obecavam da cu pokusati sam i naravno da si necu napraviti uslugu ako mi netko rijesi zadatak,nego sam mislio po rijesenom zadatku uciti i onda sam raditi ,usporedujuci njega.Ali thx na odgovoru!
05-08-2009 07:43 AM
Find all posts by this user
schmrz Offline
____
*

Posts: 567
Joined: Feb 2007
Post: #45
RE: C++ primjeri
No problem, i drugi put. Zadatak je prilično jednostavan, ali ako nisi upoznat sa terminima izgleda kao bauk :) Ako ti je u toj knjizi to previše zapetljano i komplikovano uvijek se možeš okreniti Wikipediji ili Google za pomoć:
Nijedan od ovih algoritama nije previše komplikovan pa ću ti pokušati malo pojasniti svaki posebno.

Binarno pretraživanje
Iako zvuči kao napredna metoda pretraživanja ona je vrlo slična najjednostavnijoj metodi - linearnoj ( objašnjeno dole ). Uslov za uspješno korištenje ove metode je da je lista prethodno sortirana ( od najmanjeg do najvećeg ). Sve što je potrebno uraditi je pretraživanje započeti na sredini traženog opsega na ciljanoj listi i ako je element u sredini manji od traženog onda je potrebno na isti način pretražiti prvi dio liste a u suprotnom potrebno je pretražiti drugi dio.

Prema tome jednostavna implementacija u c++ bi izgledala ovako:
Code:
int bfind(int list[], int last, int value, int offset = 0)
{
    while (offset <= last)
    {
        int mid = (offset + last) / 2;
        
        if (value < list[mid])
            last = mid - 1;
        else if (value > list[mid])
            offset = mid + 1;
        else
            return mid;
    }
    
    return -1;
}

Ova funkcija, naravno, vraća poziciju traženog elementa ili -1 u slučaju da ne pronađe zadani element.
Parametri funkcije su:
  • list je sortirana lista na kojoj će se vršiti pretraga
  • last je zadnji element do kojeg želimo ići
  • value je vrijednost koju tražimo
  • offset je pozicija vrijednosti od koje želimo započeti pretragu koja je po defaultu 0, odnosno početak liste

Primjer korištenja:
Code:
int bfind(...)
{
    ...
}

int main(int arc, char **argv)
{
    int lista[5] = {1, 3, 5, 6, 7};

    // ispisat ce na ekranu broj 4 jer je to pozicija elementa 7
    std::cout << bfind(lista, 5, 7) << std::endl;  
    return 0;
}

Slijedno / Linearno pretraživanje
Linearno pretraživane je najjednostavnije i najčešće korišteno pretraživanje. Također je i najsporije jer prolazi kroz sve elemente niza pa tako ako imamo niz sa 100.000 elemenata i element koji mi tražimo nalazi se na samom kraju, recimo na poziciji 99.999 onda će pretraga trajati dosta dugo. Princip je jednostavan, krećemo od prvog do zadnjeg elementa i provjeravamo njihove vrijednosti, kada pronađemo traženu vrijednost, vratimo njenu poziciju.

Implementacija u c++ izgleda ovako:
Code:
int lfind(int list[], int last, int value, int offset = 0)
{
    for (; offset <= last; offset++)
        if (value == list[offset])
        return offset;
    
    return -1;
}

Parametri su isti kao i kod binarnog pretraživanja.

Prije nego i pokušam objasniti Mergesort i Quicksort algoritme, trebaš mi reći da li koristite std vektore umjesto običnih nizova? ( Koristit ću obične nizove )

Merge sort
Ovo je još jedan "podijeli pa vladaj" algoritam. U biti funkcija na početku podijeli niz na dva dijela i onda počne rekurzivno djelovati na te dijelove. Prvo se ista funkcija poziva na prvi a onda na drugi dio. Kada sredi i jedan i drugi niz onda se izvršava Merge funkcija na ta dva dijela. Merge uzima dva niza ( koja su prethodno podijeljena od strane Merge sort funkcije ) i onda provjerava koji je element u ta dva niza manji i dodaje ga u niz koji predstavlja rezultat. Kada doda element u rezultat onda prelazi na slijedeći element u onom nizu od koga je uzeo taj element.

Tako da recimo ako imamo situaciju da je merge funkcija dobila dva niza: A[2, 3, 5] i B[4, 6, 10] onda će izvedba izgledati ovako:
  • Uspoređuju se prvi elementi oba niza. Uzima se prvi element iz niza A i dodaje se u rezultat. Onda se prelazi na drugi element u nizu A.
  • Uspoređuju se drugi element prvog i prvi element drugog niza. Uzima se drugi element iz niza A i dodaje se u rezultat. Prelazi se na treci element niza A.
  • Sada se usporeduje treci element niza A i prvi element niza B. Uzima se prvi element niza B i dodaje se u rezultat. Prelazi se na drugi element niza B.
  • Sada se usporeduje treci element niza A i drugi element niza B (...)

Tako na kraju dobivamo rezultat C [2, 3, 4, 5, 6, 10]

Jednostavna implementacija u c++ izgleda ovako:
Code:
#include <iostream>
#include <stdlib.h>

int *merge(int *left, int *right, int leftLength, int rightLength)
{
    int *result = (int*) malloc((leftLength+rightLength)*sizeof(int));
    
    int leftIndex = 0, rightIndex = 0, resIndex = 0;
    while (leftIndex != leftLength && rightIndex != rightLength)
    {
        if (left[leftIndex] < right[rightIndex])
            result[resIndex++] = left[leftIndex++];
        else
            result[resIndex++] = right[rightIndex++];
    }
    
    while (leftIndex != leftLength)
        result[resIndex++] = left[leftIndex++];
    
    while (rightIndex != rightLength)
        result[resIndex++] = right[rightIndex++];
    
    return result;
}

int *mergeSort(int array[], int length)
{
    int *sortedArray = (int*) malloc(length*sizeof(int));
    
    if (length > 1)
    {
        int leftLength = length/2;
        int rightLength = leftLength;
        
        if (length % 2 != 0)
            rightLength++;
        
        int *left = (int*) malloc(leftLength*sizeof(int));
        int *right = (int*) malloc(rightLength*sizeof(int));
        
        for (int i = 0; i < leftLength; left[i] = array[i++]);        
        for (int i = leftLength; i < length; right[i - leftLength] = array[i++]);
        
        left = mergeSort(left, leftLength);
        right = mergeSort(right, rightLength);
    
        array = merge(left, right, leftLength, rightLength);
    }Evo sad ovo da imaš dok napišem info za Quick sort metodu.
    
    return array;
}



int main(int argc, char **argv)
{
    int lista[10] = {1,3,2,-6,2,3,42,1,9,10};
    int *sorted = mergeSort(lista, 10);
    
    for (int i = 0; i < 10; i++)
        std::cout << sorted[i] << std::endl;
    return 0;
}

Code:
int *merge(int *left, int *right, int leftLength, int rightLength)

Parametri funkcije:
  • left je prvi array
  • right je drugi array za spajanje
  • leftLength i rightLength sadrže broj elemenata left i right nizova.

Code:
while (leftIndex != leftLength && rightIndex != rightLength)
{
    if (left[leftIndex] < right[rightIndex])
        result[resIndex++] = left[leftIndex++];
    else
        result[resIndex++] = right[rightIndex++];
}

Ova while petlja se ponavlja sve dok je ostalo neupoređenih elemenata u jednom od nizova. Ovaj dio koda sam objasnio kada sam prethodno pričao o merge funkciji. Jednostavno se provjerava koji je element manji i onda se on dodaje u rezultat. leftIndex i rightIndex označavaju koji se element u nizu trenutno uspoređuje. resIndex označava na koju se poziciju treba u rezultat upisati slijedeći element.

Code:
while (leftIndex != leftLength)
    result[resIndex++] = left[leftIndex++];
    
while (rightIndex != rightLength)
    result[resIndex++] = right[rightIndex++];

Kada se odradi uspoređivanje elemenata u jednom od nizova će ostati višak elemenata. Taj višak je uređen i može se jednostavno dodati na rezultat.

U mergeSort funkciji imamo dva parametra:
  • array je niz koji želimo sortirati
  • length je broj elemenata u array nizu

Code:
for (int i = 0; i < leftLength; left[i] = array[i++]);        
for (int i = leftLength; i < length; right[i - leftLength] = array[i++]);

Ovaj dio koda jednostavno dijeli ulazni niz na dva dijela. Nakon ovoga se rekurzivno poziva mergeSort na prvi i drugi dio niza i nakon što se to završi poziva se merge funkcija koja spaja i finalno sortira rezultat.

Quick sort
Kao i druge i ova metoda je podijeli pa vladaj. Ova metoda glasi za najpoznatiju i najefikasniju metodu za sortiranje. Ova implementacija koju ćemo mi koristiti ( bez ikakvih optimizacija ) po efikasnosti je vrlo blizu Merge sort metode.

U quick sort metodi prvo izaberemo tzv. pivot varijablu. Ona se obično uzima sa kraja niza i onda sve ostale elemente ( ne smijemo zaboraviti isključiti element koji smo izabrali kao pivot vrijednost iz pretrage ) niza poredimo sa njom. Ako je vrijednost manja, ubacujemo je u niz za manje vrijednosti, a u suprotnom ide u niz za veće vrijednosti. Na početku smo dužinu nizova za manje i veće vrijednosti definisali kao dužinu ulaznog niza umanjeno za jedan jer je to minimalna potrebna vrijednost.

Kada usporedimo sve vrijednosti sa pivot elementom onda rekurzivno pozivamo quickSort funkciju na ta dva dobivena niza ( niz sa manjim i niz sa većim vrijednostima ). Na kraju, povežemo niz sa najmanjim vrijednostima, pivot element i niz sa većim vrijednostima. I na taj način smo dobili sortirani niz.

Implementacija u c++ izgleda ovako:
Code:
int *quickSort(int array[], int length)
{
    if (length <= 1)
        return array;
    
    int *result  = (int*) malloc (length * sizeof(int) );
    int *less    = (int*) malloc ((length-1) * sizeof(int) );
    int *greater = (int*) malloc ((length-1) * sizeof(int) );
    
    int lessIndex = 0, greaIndex = 0;
    int pivot = array[length-1];
    
    for (int i = 0; i < length-1; i++)
    {
        if (array[i] <= pivot)
        {
            less[lessIndex++] = array[i];
        }
        else
        {
            greater[greaIndex++] = array[i];
        }
    }
    
    less    = quickSort(less, lessIndex);
    greater = quickSort(greater, greaIndex);
    
    if (lessIndex)
        for (int i = 0; i < lessIndex; result[i] = less[i++]);
    result[lessIndex] = pivot;
    if (greaIndex)
        for (int i = 0; i < greaIndex; result[lessIndex+1+i] = greater[i++]);
    
    return result;
}

Sve bi trebalo biti poprilično jasno iz samog koda. Ako imaš još nekih pitanja, pucaj :)

I have no drinking problems. I drink. Get drunk. Fall down. NO PROBLEM
Registered As Linux User #484215
Moj skromni blog
Savjet za buduće programere: ovdje
05-08-2009 12:13 PM
Find all posts by this user
ivicasb Offline
Novi korisnik
*

Posts: 12
Joined: Aug 2009
Reputation: 0
Post: #46
RE: C++ primjeri
Wow schmrz!
Sokiro sam se kad sam vidio tvoj opsezni odgovor,a jos nije ni gotov!?!(Naravno pozitivno!) Svaka cast,jesi ti programer po zanimanju,radis ili kolega student?
Malo me je sramota,ali ti ne mogu u ovom trenutku odgovoriti na tvoje pitanje o std vektorima ili obicnim nizovima,jer ne znamConfused sorry
ako mogu pomoci tako da ti posaljem cijeli zadatak sa pdf-ma!? ili nekako drukcije samo javi saljem odmah!
pöööööözdrav i thx na odgovorima cooool si!
(This post was last modified: 05-08-2009 04:14 PM by ivicasb.)
05-08-2009 04:12 PM
Find all posts by this user
schmrz Offline
____
*

Posts: 567
Joined: Feb 2007
Post: #47
RE: C++ primjeri
Hmm pa možeš, postavi, ako to nije ovo što si već stavljao. Ali ako nisi čuo za vektore onda ih niste ni koristili ( nadam se ) pa te neću zamarati s time.

Što se tiče drugog pitanja, programer po zanimanju nisam ( još uvijek ), ne radim i nisam student :) Zadnja sam godina srednje ( Elektrotehničke ) škole. Ostatak posta dolazi ubrzo :)

I have no drinking problems. I drink. Get drunk. Fall down. NO PROBLEM
Registered As Linux User #484215
Moj skromni blog
Savjet za buduće programere: ovdje
05-08-2009 05:38 PM
Find all posts by this user
ivicasb Offline
Novi korisnik
*

Posts: 12
Joined: Aug 2009
Reputation: 0
Post: #48
RE: C++ primjeri
Respekt,gdje bi ja sad bio da sam u srednjoj toliko znao ....Hmmm
Evo staviti cu jos 2 pdf-a sto idu uz zadatke
nesto mi nece ubaciti pdf-ove(vjerovatno su preveliki)mozes mi poslati event.tvoj mail pa ti posaljem
pöööööözdrav
THANKS!
(This post was last modified: 05-08-2009 06:16 PM by ivicasb.)
05-08-2009 06:13 PM
Find all posts by this user
schmrz Offline
____
*

Posts: 567
Joined: Feb 2007
Post: #49
RE: C++ primjeri
Bump :) Updateovao sam post za Merge sort i Quick sort. Sada bi trebao biti u mogućnosti završiti svoj zadatak bez većih problema.

I have no drinking problems. I drink. Get drunk. Fall down. NO PROBLEM
Registered As Linux User #484215
Moj skromni blog
Savjet za buduće programere: ovdje
05-08-2009 06:51 PM
Find all posts by this user
Ella Offline
Novi korisnik
*

Posts: 1
Joined: Sep 2009
Reputation: 0
Post: #50
RE: C++ primjeri
Ciao,
moze mi li neko pomoci:)Treba mi kako da uzmem elemenat iz liste (prvi ili zadnji,ili bilo koji),i poredim ih...?
01-09-2009 12:15 PM
Find all posts by this user
Thread Closed 


Forum Jump:


User(s) browsing this thread: 1 Guest(s)