[Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu

[Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu 29.10.2005. u 16:47 · pre 255 meseci #1

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

Potpis

77 77 77 2E 65 73 6E 69 70 73 2E 63 6F 6D

Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu 29.10.2005. u 17:44 · pre 255 meseci #2

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 $p_1$ i $p_2$ ti uopšte ne trebaju (umesto njih imaš promenljive $i$ i $j$ ).

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.

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu 29.10.2005. u 17:48 · pre 255 meseci #3

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--)
...

Potpis

... Mu .... Mu ...

Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu 29.10.2005. u 18:37 · pre 255 meseci #4

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

Potpis

77 77 77 2E 65 73 6E 69 70 73 2E 63 6F 6D

Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu 29.10.2005. u 19:33 · pre 255 meseci #5

Da, slažem se oko onog "pucanja" programa, ja sam imao u vidu da se stvarno izbace iz igre $p_1$ i $p_2$ , a umesto njih ostave $i$ i $j$ (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...

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu 29.10.2005. u 19:57 · pre 255 meseci #6

na primer, da ne vrtis dve petlje, nego da i prvi i poslednji trazis jednim prelazom, ako bas hoces da pretrazujes grubom silom.

Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu 29.10.2005. u 21:59 · pre 255 meseci #7

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.

Potpis

77 77 77 2E 65 73 6E 69 70 73 2E 63 6F 6D

Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu 30.10.2005. u 00:22 · pre 255 meseci #8

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 $a_0,a_1,\ldots,a_{i-1}$ već sortiran (od najmanjeg ka najvećem) i da sada treba sortirati ostatak niza, tj. podniz $a_i,\ldots,a_{n-1}$ i zamislimo da je taj isti podniz sortiran tako da je $a_i>a_{i+1}>\ldots >a_{n-1}$ , onda bi tvoja unutrašnja petlja odradila $3\cdot(n-1-i)$ dodela vrednosti ( i to potencijalno velikih objekata (dakle sa ko-zna-koliko još implicitnih dodela vrednosti)), dok bi ova u Selection Sortu odradila samo $n-1-i$ 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 $\frac {1}{vremeKucanjaKoda\cdot vremeIzvrsavanja}$

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu 30.10.2005. u 06:09 · pre 255 meseci #9

evo pa se zanimaj ;)

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

Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu 30.10.2005. u 10:54 · pre 255 meseci #10

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

Potpis

Never argue with an idiot. They bring you down to their level and beat you with
experience.

Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu 30.10.2005. u 11:54 · pre 255 meseci #11

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));

Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu 30.10.2005. u 13:17 · pre 255 meseci #12

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

Potpis

77 77 77 2E 65 73 6E 69 70 73 2E 63 6F 6D

c.JPG116.39k

Re: [Zadatak] Mesto prvog i poslednjeg pojavljivanja broja u nizu 30.10.2005. u 15:09 · pre 255 meseci #13

@NastyBoy to je to.
@Pharos MSVS kompajlira uredno i C kod ;-)
Pozdrav.

Potpis

Never argue with an idiot. They bring you down to their level and beat you with
experience.

Forum kao aplikacija na telefonu

Srodne teme