Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicitÓ e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Domande su argomenti programmazione c
Forum - C/C++ - Domande su argomenti programmazione c

Pagine: [ 1 2 ] Precedente | Prossimo
Avatar
gabama (Normal User)
Rookie


Messaggi: 26
Iscritto: 12/04/2009

Segnala al moderatore
Postato alle 23:15
Domenica, 12/04/2009
Intanto Buona Pasqua a tutti,
sono un nuovo iscritto e vorrei chiedere alcune conferme su questo codice
#include<stdio.h>
#define N 5
int pari(int a[N]);
main(){
int a[N];
int i=0;
printf("INSERISCI LISTA\n");
for(i=0;i<N;i++){
printf("\nInserisci elemento %d di %d ",i+1,N);
scanf("%d",&a);}

printf("\nSTAMPA LISTA");
for(i=0;i<N;i++){
printf("\nL' elemento e' %d ",a);}

int cont=0;
cont=pari(a);
printf("\npari e' %d ",cont);
}

int pari(int a[N]){
int u=1;int i=0;
while ((i<N) && (u!=0)){

if(a%3!=0) u=0;
i++;
}
return u;
}

In questo codice, nel ciclo (ovviamente nella funzione)
-l' asserzione iniziale Ŕ i compreso tra 0 e N-1 e u=1?
-l' asserzione finale Ŕ u =0 o 1?
-L'invariante Ŕ i compreso tra 0 e N-1 e u = 0 o 1?
-La complessitÓ Ŕ o O(n) perchŔ al massimo si scorre una volta l' array?
-Nel caso di un ordinamento la complessitÓ Ŕ quadratica perchŔ si richiama al peggio n-1 volte il codice?
Spero che qualcuno risponda perchŔ Ŕ molto importante

PM Quote
Avatar
andrea.b89 (Ex-Member)
Pro


Messaggi: 129
Iscritto: 03/03/2009

Segnala al moderatore
Postato alle 1:27
Lunedý, 13/04/2009
Nel codice ci sono diversi errori, come la lettura degli elementi, o l'accesso agli elementi del vettore.
Poi non si capisce bene quale sia lo scopo di pari. Letta cosý dovrebbe ritornare un valore pari a 1 se tutti gli elementi del vettore sono pari, 0 altrimenti. Ma nel caso il suo scopo fosse proprio questo allora a livello di logica non funziona perchŔ facendo % 3 nell'if si ottengono 3 possibili risulti : 0 1 2. Un numero risulta pari quando tale operazione da esito 0 oppure 2. Lo si dovrebbe sostituire con % 2.

Ora tralasciando il mero codice del programma e analizzando la funzione, giusta o sbagliata che sia, a mio avviso le risposte alle tue domande sono le seguenti.

1) Si
2) Si
3) Che intendi per "invariante"?
4) La complessitÓ dell'intero programma risulta essere O(n^2) in quanto il secondo for del main presenta complessitÓ O(n). La complessitÓ della funzione pari Ŕ O(n) dove n = N perchŔ al massimo devi eseguire N volte una serie di operazioni di costo costante.
Analizzando matematicamente le 2 funzioni O otterresti O(n*n) = O(n^2)

5) O(n^2) in quanto la complessitÓ resta invariata. Ehm.. scusa la domanda, ma che c'entra poi l'ordinamento? Alla fine per il codice che hai postato l'ordinamento non cambia le cose.

Dato che ci˛ che ho scritto Ŕ frutto di una mia personale analisi effettuata in presenza di alcuni dubbi (mi riferisco alle domande che ti ho fatto sopra) se potessi chiarirmeli sarei in grado di confermare quanto detto, e al massimo di correggermi in caso di errori.

Questo Ŕ quanto. Spero di essere stato chiaro e di aiuto. :k:

PM Quote
Avatar
gabama (Normal User)
Rookie


Messaggi: 26
Iscritto: 12/04/2009

Segnala al moderatore
Postato alle 10:47
Lunedý, 13/04/2009
Andrea intanto grazie mille per avermi risposto,
-nel ciclo ho postato %3 per avere i multipli di 3,giustamente come hai detto se lo sono tutti o no
-per invariante intendo l' invariante del ciclo della funzione
-per quanto riguarda l' ordinamento hai ragione a dire che non c' entra niente con questo,era solo per non aprire 2 post.....,quindi mi confermi che la complessitÓ Ŕ O(n^2) perchŔ si usa su n-1 elementi?

Grazie ancora
Ciao e Buona Pasquetta!

PM Quote
Avatar
andrea.b89 (Ex-Member)
Pro


Messaggi: 129
Iscritto: 03/03/2009

Segnala al moderatore
Postato alle 11:31
Lunedý, 13/04/2009
Invariante di un ciclo sinceramente Ŕ la prima volta che lo sento. Magari lo conosco sotto un altro nome.

Si la complessitÓ Ŕ O(n^2) perchŔ nel caso peggiore nella funzione fa N volte il ciclo e stessa cosa nel secondo for del main e quindi diventerebbe N*N = N^2.
Riguardo all'ordinamento, come ti dicevo non ha senso perchŔ ci sono diversi metodi di ordinamento, tanto per citarne alcuni BubbleSort, MergeSort, HeapSort ecc, e in base al metodo cambia la complessitÓ, ce ne sono alcuni (ad esempio BubbleSort) che sono O(n^2) altri (ad esempio MergeSort) che sono O(n*logn) quindi la mia domanda Ŕ :

vuoi sapere se l'ordinamento influenza le tue operazioni oppure altro?

Poi comunque nel codice ci sono degli  errori nell'accesso al vettore. Se devi verificare se l'elemento i-esimo del vettore Ŕ multiplo di 3 allora devi scrivere
Codice sorgente - presumibilmente C/C++

  1. if (a[i] % 3 != 0) ...



stessa cosa quando effettui la letture

Codice sorgente - presumibilmente Plain Text

  1. scanf("%d", &a[i])



e come sopra per quando lo stampi

Codice sorgente - presumibilmente Plain Text

  1. printf("%d\n", a[i])




PM Quote
Avatar
gabama (Normal User)
Rookie


Messaggi: 26
Iscritto: 12/04/2009

Segnala al moderatore
Postato alle 12:19
Lunedý, 13/04/2009
ti ringrazio,no volevo solo sapere la complessitÓ dell' ordinamento senza attinenza al codice.
Sto lavorando a un nuovo codice ,pi¨ tardi saresti cosý gentile ancora da darmi alcune conferme?
Grazie ancora ciao!

PM Quote
Avatar
andrea.b89 (Ex-Member)
Pro


Messaggi: 129
Iscritto: 03/03/2009

Segnala al moderatore
Postato alle 12:20
Lunedý, 13/04/2009
si certo nessun problema :k:

PM Quote
Avatar
gabama (Normal User)
Rookie


Messaggi: 26
Iscritto: 12/04/2009

Segnala al moderatore
Postato alle 18:16
Lunedý, 13/04/2009
Ŕ ancora un codice molto simile al precedente,
main(){
int i=0;int u=1;
int a[N]={3,6,9,10,15};
for(i=0;i<N-1;i++){
if(a%3!=0) u=0;
if(u==0) break;}

-ass. iniziale  ,che u sia = 1
-ass. finale u = 0 o 1
-invariante con i compreso tra 0 o N-1 e u=0 o 1
-complessitÓ O(n)
PROVO A FARE IL DIAGRAMMI A BLOCCHI
a[N]
||
i=0;u=1;
||
i=i+1;
||
test
a%3!=0     SI    print u=0;
||
NO
u=1;
TEST
i=N-1         SI    print u
NO
RICOMINCIA DA SOPRA i=i+1
si pu˛ generalizzare che l' asserzione iniziale sono le condizioni necessarie all' inizio e quella finale il "risultato"

Ultima modifica effettuata da gabama il 13/04/2009 alle 18:25
PM Quote
Avatar
andrea.b89 (Ex-Member)
Pro


Messaggi: 129
Iscritto: 03/03/2009

Segnala al moderatore
Postato alle 18:33
Lunedý, 13/04/2009
la domanda sarebbe?

PM Quote
Avatar
gabama (Normal User)
Rookie


Messaggi: 26
Iscritto: 12/04/2009

Segnala al moderatore
Postato alle 18:38
Lunedý, 13/04/2009
semplicemente se Ŕ tutto ok,o se ho detto stupidaggini

PM Quote
Pagine: [ 1 2 ] Precedente | Prossimo