Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

[Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu

[es] :: C/C++ programiranje :: C/C++ za početnike :: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu

[ Pregleda: 4008 | Odgovora: 12 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Pharos
Pančevo

Član broj: 20664
Poruke: 1029
195.252.85.*



+2 Profil

icon [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu29.10.2005. u 15:47 - pre 224 meseci
Zadatak glasi ovako:
Naći mesto prvog i poslednjeg pojavljivanja datog broja u uređenom nizu brojeva.
Moj kod ide ovako:
Code:

#include <stdio.h>
#include <stdlib.h>
main(){
    int *a,i,j,n,b,x;
    while(1){
        int p1=-1,p2=-1;
        /* Odredivanje duzine niza */
        printf("Unesite duzinu niza: ");scanf("%d",&n);
        if(n<=0)break;
        /* Stvaranje niza */
        a=malloc(n*sizeof(int));
        printf("\nA? ");for(i=0;i<n;scanf("%d",&a[i++]));
        /* Sortiranje niza */
        for (i=0;i<n-1;i++)
            for(j=i+1;j<n;j++)
                if(a[i]>a[j]){b=a[i];a[i]=a[j];a[j]=b;}
        /* Unosnje trazenog broja */
        printf("\nUnesite broj: ");scanf("%d",&x);
        /* Trazenje prvog pojavljivanja u nizu */
        for(j=0;j<n;j++)
            if(a[j]==x){
                p1=j;break;
            }
        /* Trazenje poslednjeg pojavljivanja u nizu */
        for(i=n;i>0;i--)
            if(a[i]==x){
                p2=i;
                break;
            }
        /* Ispisivanje rezultata */
        printf("\n\n");
        if(p1!=-1)
            printf("Prvo pojavljivanje na mestu br. %d\n",p1);
        if(p2!=-1)
            printf("Poslednje pojavljivanje na mestu br. %d\n",p2);
        if(p1==-1)
            printf("Broj se ne pojavljuje u nizu\n");
        printf("\n\n");
        free(a);
    }
}

Šta mi ovde kod koda ne valja?
Konkretno mislim na nalaženje prvog i poslednjeg broja u nizu.
Ne ispisuje mi tačne vrednosti.
Kad se traženi broj pojavljuje prvi i poslednji put u nizu, onda su vrednosti ok. Kad se nalazi na drugim mestima onda ne ispisuje tačne vrednosti.
Nešto nisam otkucao kako valja.
Hvala
77 77 77 2E 65 73 6E 69 70 73 2E 63 6F 6D
 
Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953


+5 Profil

icon Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu29.10.2005. u 16:44 - pre 224 meseci
Dosta stvari se može popraviti, ali evo nekih očiglednih grešaka:
Code:

/* Trazenje poslednjeg pojavljivanja u nizu */
        for(i=n;i>0;i--)
            if(a[i]==x){
                p2=i;
                break;
            }


a trebalo bi da stoji:
Code:

/* Trazenje poslednjeg pojavljivanja u nizu */
        for(i=n-1;i>=0;i--)
            if(a[i]==x){
                p2=i;
                break;
            }


Naravno, promenljive i ti uopšte ne trebaju (umesto njih imaš promenljive i ).

Kasnije, umesto :
Code:

if(p1!=-1)
            printf("Prvo pojavljivanje na mestu br. %d\n",p1);



treba da stoji:
Code:

if(p1!=n)
            printf("Prvo pojavljivanje na mestu br. %d\n",p1);



i na kraju bi trebalo da piše:
Code:

if(p2!=-1)
            printf("Poslednje pojavljivanje na mestu br. %d\n",p2);
        else
            printf("Broj se ne pojavljuje u nizu\n");


Reč, dve o neefikasnosti:

Već posle prve pretrage znaš da li broja ima u nizu ili ne, tako da pre nego što nastaviš potragu za poslednjim pojavljivanjem ne bi bilo loše da upotrebiš tu informaciju

Btw, sortiranje si rešio tačno, ali ne baš efikasno...

Takođe, u čitavom rešenju nigde nisi iskoristio činjenicu da je niz sortiran, a ako je sve ovo bio neki zadatak, pretpostavljam da je poenta bila baš u tome.

[Ovu poruku je menjao uranium dana 29.10.2005. u 17:55 GMT+1]
Attempt all the problems. Those you can do, don't do. Do the ones you cannot.
 
Odgovor na temu

MrLimeni
Montenegro

Član broj: 27761
Poruke: 100
*.crnagora.net.



Profil

icon Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu29.10.2005. u 16:48 - pre 224 meseci
Citat:
Pharos: Zadatak glasi ovako:
Naći mesto prvog i poslednjeg pojavljivanja datog broja u uređenom nizu brojeva.
Moj kod ide ovako:
Code:

...
/* Trazenje poslednjeg pojavljivanja u nizu */
for(i=n;i>0;i--)
if(a[i]==x){
p2=i;
break;
}
...


Ako si se vec odlucio za ovaj nacin,zar ovdje ne treba da stoji:
Code:

for(i=n-1;i>=0;i--)
...

... Mu .... Mu ...
 
Odgovor na temu

Pharos
Pančevo

Član broj: 20664
Poruke: 1029
*.beotel.net.



+2 Profil

icon Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu29.10.2005. u 17:37 - pre 224 meseci
Tipičan školski zadatak zato i treba da stoji p1 i p2.
Naravno, može da se isključi ali ne treba.
Šta recimo da sam posle traženja trebao da zamenim prvi član niza sa poslednjim, drugi sa pretposlednjim... Neću valjda za 16 brojača u programu koristiti 16 različitih i,j,k,l... Sve radim sa i. Što sam stavio i "j", pojma nemam :)
Znači zato stoje p1 i p2, da posle 1000 redova ne bi morao da mislim da li sam još negde upotrebio i i j.
Kad sam stavljao brojač u nazad, treba da stoji for(i=n-1,i>=0...) ...greška :)
Nisam gledao, dešava se.
Ali tamo ne treba da stoji i>=0, zato što je 0 prvi član. A prvi ne može biti i prvi i poslednji. Zato sam i stavio do 0, ne uključujući 0. Ako postoji na tom mestu, to će biti vrednost p1.
Ali nije problem u tome.
Drugo,
Citat:

Kasnije, umesto :
Code:

if(p1!=-1)
printf("Prvo pojavljivanje na mestu br. %d\n",p1);



treba da stoji:
Code:

if(p1!=n)
printf("Prvo pojavljivanje na mestu br. %d\n",p1);

I recimo uzmeš 3 člana niza: 1 2 3
Traženi broj: 4
I program "pukne" kad dođe do ove tvoje linije pošto p1 nije setovano i nema s čim da ga upoređuje.

Dobro sam ja to odradio, pravo školski :)

Citat:
Btw, sortiranje si rešio tačno, ali ne baš efikasno...

Školskiprimer sortiranja čika Lasla. Znači dobro je :)

Citat:
Takođe, u čitavom rešenju nigde nisi iskoristio činjenicu da je niz sortiran, a ako je sve ovo bio neki zadatak, pretpostavljam da je poenta bila baš u tome.

Ma malo je nečitko napisano. Nisam ja sastavljao zadatak.
Poenta je bila, dobiješ niz, sortiraš ga i onda u sortiranom nizu nađeš gde se pojavljuje.
Malo glupo ali...


EDIT:

Program radi, samo što sam ja pogrešno čitao rešenje. Nisam uzimao u obzir to da je niz sortiran. lol.
Neću brisati post, možda nekom zatreba.
pOz

[Ovu poruku je menjao Pharos dana 29.10.2005. u 18:45 GMT+1]
77 77 77 2E 65 73 6E 69 70 73 2E 63 6F 6D
 
Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953


+5 Profil

icon Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu29.10.2005. u 18:33 - pre 224 meseci
Da, slažem se oko onog "pucanja" programa, ja sam imao u vidu da se stvarno izbace iz igre i , a umesto njih ostave i (barem dok ne izvršiš sve potrebne provere), ali sam zaboravio da to prepravim u tvom kodu.

Znači moglo bi ovako:
Code:

/* Trazenje prvog pojavljivanja u nizu */
        for(j=0;j<n && a[j]!=x;j++);


i

Code:

/* Trazenje poslednjeg pojavljivanja u nizu */
        if(j!=n)
             for(i=n-1;i>=0 && a[i]!=x;i--);


a posle bi provera bila:

Code:

        if(j!=n){
            printf("Prvo pojavljivanje na mestu br. %d\n",j);
            printf("Poslednje pojavljivanje na mestu br. %d\n",i);
        }
        else
        printf("Broj se ne pojavljuje u nizu\n");


Dalje, ako se traženi broj pojavljuje samo jednom u nizu, onda je to pojavljivanje i prvo i poslednje, pa nema razloga što on ne bi mogao da se pojavljuje na lokaciji 0.

Citat:
Pharos
Školskiprimer sortiranja čika Lasla. Znači dobro je


Ako misliš na Krausa, pa nije on baš neka faca, ako je mogao sebi da dozvoli toliko loše sortiranje

Kad sam rekao da nisi upotrebio činjenicu da pretražuješ sortirani niz, imao sam u vidu neke mnogo efikasnije načine traganja na koje je autor zadatka verovatno mislio...
Attempt all the problems. Those you can do, don't do. Do the ones you cannot.
 
Odgovor na temu

japan

Član broj: 34328
Poruke: 480
*.dialup.sezampro.yu.



+13 Profil

icon Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu29.10.2005. u 18:57 - pre 224 meseci
na primer, da ne vrtis dve petlje, nego da i prvi i poslednji trazis jednim prelazom, ako bas hoces da pretrazujes grubom silom.
 
Odgovor na temu

Pharos
Pančevo

Član broj: 20664
Poruke: 1029
195.252.85.*



+2 Profil

icon Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu29.10.2005. u 20:59 - pre 224 meseci
Aj mi onda daj bolji primer sortiranja.
Ne mislim da te zezam ili nešto slično.
Stvarno bih hteo da znam ako ima bolje.
pOz

P.S.
Tražim sortiranje, ne pretragu.
Pretraga je mogla da se odradi s jednim brojačem, ne samo sa 2.

77 77 77 2E 65 73 6E 69 70 73 2E 63 6F 6D
 
Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953


+5 Profil

icon Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu29.10.2005. u 23:22 - pre 224 meseci
Ajde, prvo mala modifikacija tvog algoritma, tj. Selction Sort

Code:

void selectionSort(int *niz, int n)
{
  int i, j, min, p;

  for (i = 0; i < n; i++)
  {
    min = i;
    for (j = i+1; j < n; j++)
      if (niz[j] < niz[min]) min = j;
    
    p= niz[i];
    niz[i] = niz[min];
    niz[min] = p;
  }
}


Kao što vidiš, ovde se pre svega pronađe pozicija (index) najmanjeg u nizu, pa se tek onda izvrši swap. Ovde je dat primer sa celobrojnim nizom, ali lako je zamisliti situaciju da treba da sortiraš niz nekih glomaznih objekata, pa je očigledna ušteda u unutrašnjoj petlji, gde radimo samo sa indeksima.

Algoritam sa kojim si ti krenuo, imao bi sledeći problem: zamislimo da je niz već sortiran (od najmanjeg ka najvećem) i da sada treba sortirati ostatak niza, tj. podniz i zamislimo da je taj isti podniz sortiran tako da je , onda bi tvoja unutrašnja petlja odradila dodela vrednosti ( i to potencijalno velikih objekata (dakle sa ko-zna-koliko još implicitnih dodela vrednosti)), dok bi ova u Selection Sortu odradila samo običnih dodela.

Naravno, ovo sve ne treba da znači da je ova vrsta sortiranja dobra u opštem slučaju (na primer sortiranje umetanjem je u proseku duplo brže) ali za kraće nizove ima solidan količnik


[Ovu poruku je menjao uranium dana 30.10.2005. u 00:45 GMT+1]
Attempt all the problems. Those you can do, don't do. Do the ones you cannot.
 
Odgovor na temu

japan

Član broj: 34328
Poruke: 480
*.dialup.sezampro.yu.



+13 Profil

icon Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu30.10.2005. u 05:09 - pre 224 meseci
evo pa se zanimaj ;)

http://www.google.com/search?hl=en&q=sorting+algorithms
 
Odgovor na temu

sucur
Miljan Sucur
Web developer
Istocno Sarajevo

Član broj: 50035
Poruke: 411
*.so.pttrs.net.



+1 Profil

icon Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu30.10.2005. u 09:54 - pre 224 meseci
Zna li neko zasto meni prijavljuje gresku "cann't convert from "void *" to "int *", prilikom kompajliranja ovog koda, i pokazuje na liniju a=malloc(n*sizeof(int));
Koristim MSVS 2003.NET
 
Odgovor na temu

NastyBoy
Bojan Nastic
UK

Član broj: 12041
Poruke: 895
*.plus.com.



+4 Profil

icon Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu30.10.2005. u 10:54 - pre 224 meseci
Citat:
Zna li neko zasto meni prijavljuje gresku "cann't convert from "void *" to "int *", prilikom kompajliranja ovog koda, i pokazuje na liniju a=malloc(n*sizeof(int));


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


[Ovu poruku je menjao NastyBoy dana 30.10.2005. u 11:55 GMT+1]
 
Odgovor na temu

Pharos
Pančevo

Član broj: 20664
Poruke: 1029
195.252.85.*



+2 Profil

icon Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu30.10.2005. u 12:17 - pre 224 meseci
Znam ja zašto ne radi :)
Zato što je ovo C kod, a ne C++(CPP).
Kad napraviš projekat, i dodaš source fajl, stavi mu neko ime pera.c, samo da nije pera.cpp.
pOz
77 77 77 2E 65 73 6E 69 70 73 2E 63 6F 6D
Prikačeni fajlovi
 
Odgovor na temu

sucur
Miljan Sucur
Web developer
Istocno Sarajevo

Član broj: 50035
Poruke: 411
*.so.pttrs.net.



+1 Profil

icon Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu30.10.2005. u 14:09 - pre 224 meseci
@NastyBoy to je to.
@Pharos MSVS kompajlira uredno i C kod ;-)
Pozdrav.
 
Odgovor na temu

[es] :: C/C++ programiranje :: C/C++ za početnike :: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu

[ Pregleda: 4008 | Odgovora: 12 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.