gabama (Normal User)
Rookie
 
Messaggi: 26
Iscritto: 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
|
|
|
andrea.b89 (Ex-Member)
Pro
Messaggi: 129
Iscritto: 03/03/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. 
|
|
|
gabama (Normal User)
Rookie
Messaggi: 26
Iscritto: 12/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!
|
|
|
andrea.b89 (Ex-Member)
Pro
Messaggi: 129
Iscritto: 03/03/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++ |
stessa cosa quando effettui la letture
Codice sorgente - presumibilmente Plain Text |
e come sopra per quando lo stampi
Codice sorgente - presumibilmente Plain Text |
|
|
|
gabama (Normal User)
Rookie
Messaggi: 26
Iscritto: 12/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!
|
|
|
andrea.b89 (Ex-Member)
Pro
Messaggi: 129
Iscritto: 03/03/2009
|
si certo nessun problema
|
|
|
gabama (Normal User)
Rookie
Messaggi: 26
Iscritto: 12/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 |
|
|
andrea.b89 (Ex-Member)
Pro
Messaggi: 129
Iscritto: 03/03/2009
|
la domanda sarebbe?
|
|
|
gabama (Normal User)
Rookie
Messaggi: 26
Iscritto: 12/04/2009
|
semplicemente se è tutto ok,o se ho detto stupidaggini
|
|
|
| 
