Codice in loop
Il codice sottostante viene eseguito , però va in loop stampando 000.Non riesco a capire da dove dipende.Qualcuno può darmi una mano???
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
const int N0=10; /* limite inferiore al numero di vertici dei digrafi da generare */
const int N= 10; /* limite superiore al numero di vertici dei digrafi da generare */
const int H0= 0; /* limite inferiore al numero dei digrafi da generare */
const int H=10; /* limite superiore al numero dei digrafi da generare */
/* variabili globali */
typedef int matrice [10][10] ; /* matrice adiacenza dei grafi */
matrice m;
int Chr[100]; /* vettore soluzione (permutazione) */
int Chr1[100]; /* soluzione inversa */
int nChr=0; /* numero soluzioni costruite dalla procedura esaustiva */
int Succ=1; /* flag che indica il successo della procedura esaustiva */
int n=3; /* numero vertici digrafi */
double p=0.0;
double supp=0.0;
double infp=0.0;
int Ftns=0;
void genera_matrice(matrice m, size_t n, double p) {
size_t i = 0, j = 0;
srand((unsigned) time(NULL));
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) { m[i][j] = rand() < p * RAND_MAX ? 1 : 0; }
}
}
void stampa_matrice(matrice m, size_t n) {
size_t i = 0, j = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) { printf("%d ", m[i][j]); }
printf("\n");
}
}
void initChr()
{
int i=0;
for(i=0;i<n;i++)
{
Chr[i]=n;
Chr1[i]=n;
}
}
/* procedura di stampa di Chr[] */
void stampaVett()
{
int i=0;
for(i=0;i<n;i++)
printf ("%d ",Chr[i]);
printf("\n");
}
/* procedura esaustiva di calcolo soluzioni */
/* ho modificato da void a int per errori*/
int genTPerm(int k)
{
int i=0;
if(k>(n-1))
{
/* aggiornamento di Ftns, del numero di link ciclci consecutivi della soluzione */
Ftns=Ftns+m[Chr[k-1]][Chr[0]];
stampaVett();
/* Incrementa il numero di soluzioni (permutazioni) calcolate */
nChr++;
/* verifica se la soluzione trovata è un ciclo: se si Succ=1 e termina genTPerm */
if(Ftns==n)
{
Succ=1;
return;
}
/*
nel caso in cui la soluzione trovata non è un ciclo Hamiltoniano ed il numero di soluzioni
generate è maggiore di una soglia polinomiale (ThSol=n), allora: Succ=0 e termina genTPerm
*/
int ThSol=n;
if(nChr>ThSol)
{
Succ=0;
return ;
}
/* aggiornamento di Ftns, del numero di link ciclci consecutivi della soluzione */
Ftns=Ftns-m[Chr[k-1]][Chr[0]];
}
else
for(i=0;i<n;i++)
{if(Chr1[i]==n)
{Chr[k]=i;
Chr1[i]=k;
/* aggiornamento di Ftns, del numero di link consecutivi della soluzione */
if(k>0){
Ftns=Ftns+m[Chr[k-1]][Chr[k]];
genTPerm(k+1);
}
if(k>0){
Ftns=Ftns+m[Chr[k-1]][Chr[k]];
Chr1[i]=n;
Chr[k]=n;
}
}
}
}
int main(void)
{
int i=0, k=0,flag=0;
double p = 0.5; /* probabilità di definizione per grafi di Gilbert */
nChr = 0;
int h;
int media[n];
int media2[n];
int devstandard[n];
/* inizializza variabili e vettori */
initChr();
/* calcola le soluzioni (permutazioni) */
/* inizializzazione di p */
/*
definisci i limiti inferiore pInf e superiore pSup per p tali che:
pSup rappresenta il valore di caso peggiore noto per cui genTPerm ha sempre successo
pInf rappresenta il valore di caso migliore noto per cui genTPerm fallisce almeno una volta
Inizialmente pSup=1 e pInf=0
*/
/* Inizializza p al valor medio tra pInf e pSup */
int pSup=1;
int pInf=0;
p=(pSup+pInf)/2;
/* ciclo su p per determinare le soglie di resistenza per istanze con n vertici */
while(fabs(p-pSup)>0.05)
{
/* inizializza le statitische di successo */
int PS;
PS=0;
/* generazione ciclica dei grafi di Gilbert con probabilità p */
int Gg;
int MaxGg=5;
for(Gg=0;Gg<=MaxGg;Gg++)
{
/* Gg conta l'occorrenza di grafo di Gibert di n vertici generata con probabilità p */
/* generazione di un'istanza (digrafo) */
genera_matrice(m, n, p);
stampa_matrice( m, n);
/*
sequenzizione dei vertici dell'istanza (codificata dal grafo), ovvero
calcolo di una permutazione di vertici che formino un ciclo Hamiltoniano
*/
genTPerm(0);
/* aggiorna le statistiche di successo (percentuale di successi PS + deviazione standard) */
PS=PS+Succ;
/* Fine ciclo su Gg */
}
/* se genTPerm ha avuto sempre successo (PS==MaxGg), allora pSup=p e p=(pSup+pInf)/2 */
if(PS==MaxGg){
pSup=p;
p=(pSup+pInf)/2 ;
}
/* se invece genTPerm ha fallito almeno una volta (PS!=MaxGg), allora pInf=p e p=(pSup+pInf)/2 */
if(PS!=MaxGg){
pInf=p;
p=(pSup+pInf)/2;
}
/* Fine ciclo su p */
}
for ( n=10;n<N;n++){
for( h=0;h<H;h=h+2){
p=0.5;
supp=1.0;
infp=0.0;
flag = 1;
while(flag)
{
genera_matrice(m, n, p);
int succ=genTPerm(0);
if(succ==0){infp=p; p=0.5*(supp+p);}
else{supp=p;p=0.5*(p+infp);}
if(fabs(infp-supp)<.05){flag=0;}
/* fine ciclo while(flag) */
}
media[n]+=supp;
media2[n]+=supp*supp;
/* fine ciclo for(h... */
}
devstandard[n]=sqrt(1/(H-1)*(media2[n]-media[n]*media[n]));
media[n]=media[n]/(H-1);
/* fine ciclo for(n... */
}
}
Risposte
Il mio compilatore mi presenta vari errori.
Per prima cosa non hai inserito math.h anche se la stai usando.
Come seconda cosa, più grave, ci sono dei return in genTperm che non restituiscono alcun valore anche se genTperm dovrebbe restituire un intero. La stessa funzione non possiede inoltre un return alla fine. Considerando che il tutto usa variabili globali come caramelle direi che probabilmente genTperm dovrebbe ritornare void.
Mi informa inoltre che non stai usando due variabili nel main: i e k.
Il tuo stile e il tuo uso massiccio di variabili globali non aiuta a trovare gli errori.
Per prima cosa non hai inserito math.h anche se la stai usando.
Come seconda cosa, più grave, ci sono dei return in genTperm che non restituiscono alcun valore anche se genTperm dovrebbe restituire un intero. La stessa funzione non possiede inoltre un return alla fine. Considerando che il tutto usa variabili globali come caramelle direi che probabilmente genTperm dovrebbe ritornare void.
Mi informa inoltre che non stai usando due variabili nel main: i e k.
Il tuo stile e il tuo uso massiccio di variabili globali non aiuta a trovare gli errori.
come imposto genTperm in modo da far ritornare il valore invece di return e poi ritornare void per genTperm??
se sposto le procedure nel main genera_matrice(m, n, p); stampa_matrice( m, n); prima del while(fabs(p-pSup)>0.05)...
non va in loop però mi stampa solo la matrice random.Quali modifiche occorrono per farlo funzionare correttamente aspetto un vostro aiuto.
non va in loop però mi stampa solo la matrice random.Quali modifiche occorrono per farlo funzionare correttamente aspetto un vostro aiuto.
Posta la versione che non va in loop, così provo a vedere.
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
const int N0=10; /* limite inferiore al numero di vertici dei digrafi da generare */
const int N= 10; /* limite superiore al numero di vertici dei digrafi da generare */
const int H0= 0; /* limite inferiore al numero dei digrafi da generare */
const int H=10; /* limite superiore al numero dei digrafi da generare */
/* variabili globali */
typedef int matrice [10][10] ; /* matrice adiacenza dei grafi */
matrice m;
int Chr[100]; /* vettore soluzione (permutazione) */
int Chr1[100]; /* soluzione inversa */
int nChr=0; /* numero soluzioni costruite dalla procedura esaustiva */
int Succ=1; /* flag che indica il successo della procedura esaustiva */
int n=3; /* numero vertici digrafi */
double p=0.0;
double supp=0.0;
double infp=0.0;
int Ftns=0;
void genera_matrice(matrice m, size_t n, double p) {
size_t i = 0, j = 0;
srand((unsigned) time(NULL));
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) { m[i][j] = rand() < p * RAND_MAX ? 1 : 0; }
}
}
void stampa_matrice(matrice m, size_t n) {
size_t i = 0, j = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) { printf("%d ", m[i][j]); }
printf("\n");
}
}
void initChr()
{
int i=0;
for(i=0;i<n;i++)
{
Chr[i]=n;
Chr1[i]=n;
}
}
/* procedura di stampa di Chr[] */
void stampaVett()
{
int i=0;
for(i=0;i<n;i++)
printf ("%d ",Chr[i]);
printf("\n");
}
/* procedura esaustiva di calcolo soluzioni */
/* ho modificato da void a int per errori*/
int genTPerm(int k)
{
int i=0;
if(k>(n-1))
{
/* aggiornamento di Ftns, del numero di link ciclci consecutivi della soluzione */
Ftns=Ftns+m[Chr[k-1]][Chr[0]];
stampaVett();
/* Incrementa il numero di soluzioni (permutazioni) calcolate */
nChr++;
/* verifica se la soluzione trovata è un ciclo: se si Succ=1 e termina genTPerm */
if(Ftns==n)
{
Succ=1;
return;
}
/*
nel caso in cui la soluzione trovata non è un ciclo Hamiltoniano ed il numero di soluzioni
generate è maggiore di una soglia polinomiale (ThSol=n), allora: Succ=0 e termina genTPerm
*/
int ThSol=n;
if(nChr>ThSol)
{
Succ=0;
return ;
}
/* aggiornamento di Ftns, del numero di link ciclci consecutivi della soluzione */
Ftns=Ftns-m[Chr[k-1]][Chr[0]];
}
else
for(i=0;i<n;i++)
{if(Chr1[i]==n)
{Chr[k]=i;
Chr1[i]=k;
/* aggiornamento di Ftns, del numero di link consecutivi della soluzione */
if(k>0){
Ftns=Ftns+m[Chr[k-1]][Chr[k]];
genTPerm(k+1);
}
if(k>0){
Ftns=Ftns+m[Chr[k-1]][Chr[k]];
Chr1[i]=n;
Chr[k]=n;
}
}
}
}
int main(void)
{
int flag=0;
double p = 0.5; /* probabilità di definizione per grafi di Gilbert */
nChr = 0;
int h;
int media[n];
int media2[n];
int devstandard[n];
/* inizializza variabili e vettori */
initChr();
/* calcola le soluzioni (permutazioni) */
genera_matrice(m, n, p);
stampa_matrice( m, n);
/* inizializzazione di p */
/*
definisci i limiti inferiore pInf e superiore pSup per p tali che:
pSup rappresenta il valore di caso peggiore noto per cui genTPerm ha sempre successo
pInf rappresenta il valore di caso migliore noto per cui genTPerm fallisce almeno una volta
Inizialmente pSup=1 e pInf=0
*/
/* Inizializza p al valor medio tra pInf e pSup */
int pSup=1;
int pInf=0;
p=(pSup+pInf)/2;
/* ciclo su p per determinare le soglie di resistenza per istanze con n vertici */
while(fabs(p-pSup)>0.05)
{
/* inizializza le statitische di successo */
int PS;
PS=0;
/* generazione ciclica dei grafi di Gilbert con probabilità p */
int Gg;
int MaxGg=5;
for(Gg=0;Gg<=MaxGg;Gg++)
{
/* Gg conta l'occorrenza di grafo di Gibert di n vertici generata con probabilità p */
/* generazione di un'istanza (digrafo) */
/*genera_matrice(m, n, p);
stampa_matrice( m, n); */
/*
sequenzizione dei vertici dell'istanza (codificata dal grafo), ovvero
calcolo di una permutazione di vertici che formino un ciclo Hamiltoniano
*/
genTPerm(0);
/* aggiorna le statistiche di successo (percentuale di successi PS + deviazione standard) */
PS=PS+Succ;
/* Fine ciclo su Gg */
}
/* se genTPerm ha avuto sempre successo (PS==MaxGg), allora pSup=p e p=(pSup+pInf)/2 */
if(PS==MaxGg){
pSup=p;
p=(pSup+pInf)/2 ;
}
/* se invece genTPerm ha fallito almeno una volta (PS!=MaxGg), allora pInf=p e p=(pSup+pInf)/2 */
if(PS!=MaxGg){
pInf=p;
p=(pSup+pInf)/2;
}
/* Fine ciclo su p */
}
for ( n=10;n<N;n++){
for( h=0;h<H;h=h+2){
p=0.5;
supp=1.0;
infp=0.0;
flag = 1;
while(flag)
{
genera_matrice(m, n, p);
int succ=genTPerm(0);
if(succ==0){infp=p; p=0.5*(supp+p);}
else{supp=p;p=0.5*(p+infp);}
if(fabs(infp-supp)<.05){flag=0;}
/* fine ciclo while(flag) */
}
media[n]+=supp;
media2[n]+=supp*supp;
/* fine ciclo for(h... */
}
devstandard[n]=sqrt(1/(H-1)*(media2[n]-media[n]*media[n]));
media[n]=media[n]/(H-1);
/* fine ciclo for(n... */
}
}
Nella riga 252 hai che succ = genTPerm ma genTPerm non possiede un valido valore di ritorno. Immagino quindi che il problema è che devi modificare genTPerm e il resto in modo che abbia senso.
Comunque questo ciclo è infinito
while(fabs(p-pSup)>0.05)
{
int PS;
PS=0;
int Gg;
int MaxGg=5;
for(Gg=0;Gg<=MaxGg;Gg++)
{
genTPerm(0);
PS=PS+Succ;
}
/* se genTPerm ha avuto sempre successo (PS==MaxGg), allora pSup=p e p=(pSup+pInf)/2 */
if(PS==MaxGg){
pSup=p;
p=(pSup+pInf)/2 ;
}
/* se invece genTPerm ha fallito almeno una volta (PS!=MaxGg), allora pInf=p e p=(pSup+pInf)/2 */
if(PS!=MaxGg){
pInf=p;
p=(pSup+pInf)/2;
}
/* Fine ciclo su p */
}
come posso impostarlo per farlo ritornare correttamente genTperm()???e come posso modificare praticamente il ciclo while???
Non sapendo che cosa dovrebbe fare il programma mi viene difficile correggerlo (oltre ad avere uno stile che non aiuta).
Detto queste se chr e chri sono permutazioni allora dovrebbe essere
Detto queste se chr e chri sono permutazioni allora dovrebbe essere
void initChr()
{
int i=0;
for(i=0;i<n;i++)
{
Chr[i]=i;
Chr1[i]=i;
}
}
va lo stesso in loop.
Come imposto il codice tipo: verifica se la soluzione trovata è un ciclo: se si Succ=1 e termina genTPerm?? ho inserito return(1)
}
if(Ftns==n)
{
Succ=1;
return(1);
}
al return ho inserito return Succ, come risolvo il loop?? il ciclo while come può essere corretto??
È una condizione complessa e il ciclo è certamente non banale. Se non so che cosa deve fare il programma mi viene difficile correggertelo. La mia correzione era legata al fatto che so cos'è una permutazione. Quindi o quella non era una permutazione o la tua inizializzazione non aveva senso.
come posso modificare la procedura di permutazione(genTperm()) in modo da scegliere come primo valore un vertice a caso,e poi ciclare su tutti i possibili vertici adiacenti?? Come posso scrivere nel modo più semplice una lista di adiacenza??
la permutazione deve tener conto dei vertici adiacenti utilizzando una lista di adiacenza, sceglie un vertice a caso tra 0 e (n-1) tipo chr=0.ciclo su tutti i possibili vertici adiacenti for(i=0,i<(n-1)degli adiacenti a zero,i++), poi sostituisco ad i=Chr[k-1].Come modifico il codice della permutazione in modo da farlo funzionare secondo questo criterio???
Codice Permutazione da modificare:
Codice Permutazione da modificare:
/*
VARIABILI GLOBALI:
n
nChr = numero di permutazioni alcolate (inizialmente 0)
Chr = permutazione
Chr1 = permutazione inversa (Chr1[i] = n equivale ad elemento di permutazione non definito
(se Chr[i]=j, allora Chr1[i]=j)
Succ = risposta della procedura genTPerm (inizialmente 1)
*/
int Chr[100]; /* vettore soluzione (permutazione) */
int Chr1[100]; /* soluzione inversa */
int nChr=0; /* numero soluzioni costruite dalla procedura esaustiva */
int Succ=1; /* flag che indica il successo della procedura esaustiva */
int n=3; /* numero vertici digrafi */
/* procedura di inizializzazione dei vettori soluzione (Chr[] e Chr1[]) */
void initChr()
{
int i=0;
for(i=0;i<n;i++)
{
Chr[i]=n;
Chr1[i]=n;
}
}
/* procedura di stampa di Chr[] */
void stampaVett()
{
int i=0;
for(i=0;i<n;i++)
printf ("%d ",Chr[i]);
printf("\n");
}
/* procedura esaustiva di calcolo soluzioni */
/* metto 0 nella prima posizione e generola permutazione su 1 2,
poi metto 1 nella prima posizione e genero la permutazione su 0 2,
ed infine metto 2 nella prima posizione e genero la permutazione su 0 1 , */
void genTPerm(int k)
{
int i=0;
if(k>(n-1))
{
stampaVett();
/* verifica se la soluzione trovata è un ciclo: se si succ=1 e termina genTPerm */
nChr++;
if(nChr>n)
{
Succ=0;
return ;
}
}
else
for(i=0;i<n;i++)
{if(Chr1[i]==n)
{Chr[k]=i;
Chr1[i]=k;
genTPerm(k+1);
Chr1[i]=n;
Chr[k]=n;
}
}
}
/* programma principale */
int main(void)
{
int i=0, k=0;
/* inizializza variabili, vettori e strutture dati */
nChr = 0;
initChr(); /* procedura che inizializza Chr e Chr1 */
genTPerm(0); /* procedura esaustiva per il calcolo di soluzioni */
}
Vuoi insomma calcolare tutti i cammini sul grafo che passano per tutti i nodi? È questo che dovrebbe fare la tua funzione che calcolano le permutazioni?
inizialmente scegliendo un vertice a caso del grafo e poi vado a considerare gli adiacenti a quest ultimo.non deve fare la scelta su tutti i vertici ammissibili, ma solo sugli adiacenti.
Mi è chiaro che dato un vertice ne vuoi scegliere uno adiacente al prossimo passaggio. Ma volevo capire che scopo ha esattamente la funzione all'interno della teoria dei grafi. Prendendo i vertici come da te indicato stai insomma estraendo un cammino da questo grafo che parte da un vertice casuale, ma quando devi fermarti? Devi scegliere vertici sempre diversi (non devono insomma esserci vertici che si ripetono nella successione come sembra indicare il termine permutazione oppure puoi visitare nuovamente un nodo già visitato come sembra indicare il fatto che sembri cercare cicli?) Di quella funzione non si capisce molto e credo che sia meglio ripartire da capo nell'implementarla e soprattutto iniziare a fare un po' di chiarezza su quali siano esattamente i passaggi dell'algoritmo che devi implementare..
quello che mi è stato spiegato è modificare il codice sottostante nel seguente modo :
prima del ciclo for() della permutazione mettere in if(k=0), se k=0 la procedura viene eseguita regolarmente, else (k>0) ciclo su tutti gli adiacenti ovvero Chr(k-1), facendo un ciclare il for() che va da i
prima del ciclo for() della permutazione mettere in if(k=0), se k=0 la procedura viene eseguita regolarmente, else (k>0) ciclo su tutti gli adiacenti ovvero Chr(k-1), facendo un ciclare il for() che va da i
/* variabili globali */
unsigned m[1000][1000] ; /* matrice adiacenza grafo generato */
unsigned Adj[1000][1000] ; /* lista di adiacenza grafo generato */
unsigned Adj1[1000][1000] ; /* lista di incidenza del grafo generato */
unsigned nAdj[1000] ; /* numero di adiacenti in lista di adiacenza */
unsigned nAdj1[1000] ; /* numero di incidenti in lista di incidenza */
int Chr[100]; /* vettore soluzione (permutazione) */
int Chr1[100]; /* soluzione inversa */
int nChr=0; /* numero soluzioni costruite dalla procedura esaustiva */
int Succ=1; /* flag che indica il successo della procedura esaustiva */
int n=6; /* numero vertici digrafi */
float p=.5; /* inizializzazione di p */
float pSup=1.0;
float pInf=0.0;
int Ftns=0; /* numero di link ciclci consecutivi della soluzione */
float PS=0.0; /* inizializza le statitische di successo */
int MaxGg=100; /* numero massimo dei grafi di Gilbert */
int ThSol; /* Numero di soluzioni generate al più da genTperm(0) */
int genTPerm(int k)
{
int i=0;
if(k>(n-1))
{
/* aggiornamento di Ftns, del numero di link ciclci consecutivi della soluzione */
Ftns=Ftns+m[Chr[k-1]][Chr[0]];
printf("Aggiornamento Ftns [se k>(n-1)] :%d\n\n",Ftns);
stampaVett();
/* Incrementa il numero di soluzioni (permutazioni) calcolate */
nChr++;
/* verifica se la soluzione trovata è un ciclo: se si Succ=1 e termina genTPerm */
if(Ftns==n)
{
Succ=1;
printf("Successo Ftns=n\n\n");
return Succ;
}
/*
nel caso in cui la soluzione trovata non è un ciclo Hamiltoniano ed il numero di soluzioni
generate è maggiore di una soglia polinomiale (ThSol=n), allora: Succ=0 e termina genTPerm
*/
if(nChr>ThSol)
{
Succ=0;
printf("Insuccesso: ciclo non trovato (nChr:%d>ThSol:%d)\n\n",nChr,ThSol);
return Succ ;
}
/* aggiornamento di Ftns, del numero di link ciclci consecutivi della soluzione */
Ftns=Ftns-m[Chr[k-1]][Chr[0]];
printf("Aggiornamento Ftns=(Ftns-m[Chr[k-1]][Chr[0]])=:%d\n\n",Ftns);
}
else
for(i=0;i<n;i++)
{if(Chr1[i]==n)
{
/* aggiunge un prossimo vertice alla permutazione */
Chr[k]=i;
Chr1[i]=k;
/* aggiornamento di Ftns, del numero di link consecutivi della soluzione fin qui costruita,
fino all'elemento (k+1)-esimo della soluzione */
if(k>0)
Ftns=Ftns+m[Chr[k-1]][Chr[k]];
printf("Aggiornamento Ftns=(Ftns+m[Chr[k-1]][Chr[k]])=:%d\n\n",Ftns);
genTPerm(k+1);
if(Succ!=2) return Succ ;
/* ripristina il numero di link trovati fino alla posizione k della soluzione */
if(k>0)
Ftns=Ftns-m[Chr[k-1]][Chr[k]];
printf("Aggiornamento Ftns=(Ftns-m[Chr[k-1]][Chr[k]])=:%d\n\n",Ftns);
/* annulla l'aggiunta del vertice in posizione k della soluzione */
Chr1[i]=n;
Chr[k]=n;
}
}
}
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo