[Zadatak] Broj u nizu koji se najvise ponavlja

[ hafyy @ 11.05.2008. 20:14 ] @

Imam problem sa pokazivacima...za uneseni varijabilni niz treba da mi
ispise element niza koji se najvise ponavlja...ja sam ovako uradio ali mi na kraju ispise nekad zadnji broj koji unesem a nekad se potrefi i onaj koji se najvise ponavlja...
Unaprijed zahvaljujem!

Code:

#include<iostream.h>
int main(){
int duzina;
    cout<<"Unesi duzinu niza: ";
    cin>>duzina;
int *niz=new int[duzina];
cout<<"Unesite elemente niza: "<<endl;
    for(int i=0;i<duzina;i++)
    cin>>niz[i];
cout<<"Ispis niza"<<endl;

for(int i=0;i<duzina;i++){
for(int j=0;j<duzina;j++){
}
cout<<niz[i];
}
cout<<"Broj koji se najvise ponavlja je: "<<niz[4]<<endl;
delete[]niz;
system("pause");
return 0;
}

_{[Ovu poruku je menjao X Files dana 11.05.2008. u 22:11 GMT+1]}

[ Eurora3D Team @ 12.05.2008. 02:12 ] @

Za ovakve stvari trebalo bi da se zna moguci raspon brojeva (npr od 1 do 10 ili od 1 do 100)

[ xeron @ 12.05.2008. 20:57 ] @

Code:

#include <iostream>
#include <cstring>
using namespace std;

int main(void){
    int duzina = 13;
    int niz[] = {1, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4};

    int maxPonavljanja = 0;
    int trenutnoPonavljanja = 0;
    int najviseSePonavlja =0;
    for(int i =0; i < duzina; i++){
        trenutnoPonavljanja =0;
        for(int j=0; j< duzina ; j++){
            if ( niz[i] == niz [j] )
                trenutnoPonavljanja++;
        }
        if (trenutnoPonavljanja > maxPonavljanja){
            najviseSePonavlja = niz [i];
            maxPonavljanja = trenutnoPonavljanja;
        }
    }
    cout<<"Broj u nizu koji se najvise ponavlja je: "<<najviseSePonavlja<<endl;
return 0;
}

Citat:

./ponavljanje
Broj u nizu koji se najvise ponavlja je: 3

[ Eurora3D Team @ 14.05.2008. 18:57 ] @

Ovaj gornji algoritam je dobar za krace nizove.
Ako se niz brojeva dobija iz nekog fajla ili sl. i duzina mu je npr 100000 onda program mora da prodje petlju 100000*100000=10000000000 puta. Ovde izpod imas drugacije resenje (koje trosi vise memoriske resurse nego procesor) sa relativno manje prelaza (2*DuzinaNiza + 2*NajveciBrojUNizu). Ako imamo niz od 100000 brojeva i najveci broj je npr. 50000 onda je to 200000 + 100000 = 300000 prelaza.
Ako se ovi algoritmi koriste u ozbiljnim programima onda bi trebalo testirati koji algoritam je bolji (brzi) u konkretnom slucaju.

Code:

#include <iostream>

using namespace std;

int main(void)
{
    long duzina =0 ;
    cout <<"Unesi duzinu niza: ";
    cin >> duzina;
    if (duzina < 1)
        return 1;
    long *niz = new long[duzina];
    long i;
    cout << "Unesite elemente niza: " <<endl;
    for(i = 0;i < duzina;i++)
        cin >> niz[i];
    // Ovde u niz[] imamo long niz duzine duzina
    // Trazimo najveci broj
    long MaxNo = 0;
    for(i = 0;i < duzina;i++) // Prvi prelaz
        if(niz[i] > MaxNo)
            MaxNo = niz[i];
    if(MaxNo == 0) // ako je najveci nula vracamo
        return 1;
    MaxNo++; // uvecavamo zbog alociranja memorije itd.
    int* MaxArr = new int[MaxNo]; // niz za brojanje
    for(i = 0;i < MaxNo;i++) // Drugi prelaz
        MaxArr[i] = 0;                // Popunjavamo nule za svaki slucaj
    for(i = 0;i < duzina;i++) // Treci prelaz
        MaxArr[niz[i]]+=1;// Uvecavamo index broja
    long Maximum = 0; // Rezultat = broj = index u drugom nizu
    for(i = 0;i < MaxNo;i++) // Cetvrti prelaz
        if(MaxArr[i] > Maximum) // Trazimo najveci broj
            Maximum = i;
    cout << "Najvise se ponavlja broj " << Maximum << endl;
    delete[]niz;
    delete []MaxArr;
    system("pause");
    return 0;
}

_{[Ovu poruku je menjao Eurora3D Team dana 14.05.2008. u 20:12 GMT+1]}