Programmino in C
devo scrivere un programmino in C che genera un grafo p-casuale e ne enumera i vertici ricorsivamente al fine
di trovare cicli di lunghezza massima. Come devo fare ?? dove posso prendere dei spunti??
di trovare cicli di lunghezza massima. Come devo fare ?? dove posso prendere dei spunti??
Risposte
ho messo un N 10 invece di riga o colonna va bene cosi?
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define N 10
void genera_matrice(int m[N][N], double p) {
int i, j;
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; ;
return;
}
void stampa_matrice(int m[N][N]) {
int i, j;
for (i=0; i<N; i++) {
for (j=0; j<N; j++)
printf("%d ", m[i][j]);
printf("\n");
}
return;
}
int main(void) {
double p = 0.5;
int m[N][N];
genera_matrice(m,p);
stampa_matrice(m);
}
No, come ti ho detto non puoi settare la dimensione della matrice come una costante. Non può essere costante perché avrai bisogno di cambiarlo a runtime.. Ci sono in generale tre soluzioni:
1. Settare N ad un numero molto grande e poi passare la dimensione n effettiva alla funzione. Questo ti permette di usare le matrici bidimensionali come hai fatto, ma ovviamente non è una soluzione ideale o particolarmente flessibile. In alcuni linguaggi senza l'allocazione dinamica della memoria era spesso il modo in cui si lavorava (vedi alcuni codici in fortran per esempio).
2. Usare array monodimensionali di dimensione \(n \times n\) per tutto. Diventa necessario usare codice particolare per accedere ai singoli elementi della matrice (normalmente qualcosa del tipo i*n + j), ma è la strada più usata in codici seri in C. Di fatto gli algoritmi dell'articolo che avevo postato nella prima pagina davano per scontato questo approccio. Osservando che stai semplicemente eseguendo la stessa operazione su tutti gli elementi, usando questo approccio puoi dimenticarti del tutto che sono matrici e scrivere qualcosa come segue:
3. Usare un array di puntatori ad array. Allocazione e deallocazione sono molto complicate e le performance sono le peggiori tra le 3 alternative. L'accesso agli elementi è però come quello degli array bidimensionali e sembra piacere molto per qualche assurda ragione ai professori dei primi corsi di informativa nelle università.
Scegli quella che preferisci. Vista la tua poca conoscenza del C, ti consiglierei la prima. Il codice sarebbe il seguente (non testato). Nota che il valore della dimensione n passata deve essere inferiore alla dimensione della matrice completa N.
Spero ti sia chiaro che cosa ho fatto, hai dubbi?
1. Settare N ad un numero molto grande e poi passare la dimensione n effettiva alla funzione. Questo ti permette di usare le matrici bidimensionali come hai fatto, ma ovviamente non è una soluzione ideale o particolarmente flessibile. In alcuni linguaggi senza l'allocazione dinamica della memoria era spesso il modo in cui si lavorava (vedi alcuni codici in fortran per esempio).
2. Usare array monodimensionali di dimensione \(n \times n\) per tutto. Diventa necessario usare codice particolare per accedere ai singoli elementi della matrice (normalmente qualcosa del tipo i*n + j), ma è la strada più usata in codici seri in C. Di fatto gli algoritmi dell'articolo che avevo postato nella prima pagina davano per scontato questo approccio. Osservando che stai semplicemente eseguendo la stessa operazione su tutti gli elementi, usando questo approccio puoi dimenticarti del tutto che sono matrici e scrivere qualcosa come segue:
void genera_matrice(int *matrice, size_t n, double p)
{
size_t i = 0;
for ( ; i < n*n; ++i) {
matrice[i] = (rand() < p*RAND_MAX) ? 1 : 0;
}
}
3. Usare un array di puntatori ad array. Allocazione e deallocazione sono molto complicate e le performance sono le peggiori tra le 3 alternative. L'accesso agli elementi è però come quello degli array bidimensionali e sembra piacere molto per qualche assurda ragione ai professori dei primi corsi di informativa nelle università.
Scegli quella che preferisci. Vista la tua poca conoscenza del C, ti consiglierei la prima. Il codice sarebbe il seguente (non testato). Nota che il valore della dimensione n passata deve essere inferiore alla dimensione della matrice completa N.
#include <assert.h> /* se elimini gli assert che ho sparso per il codice puoi eliminarlo.. */
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
/* Definisco un nuovo tipo per le matrici.. */
#define N 10
typedef int matrice[N][N];
void genera_matrice(matrice m, size_t n, double p) {
size_t i = 0, j = 0;
assert(n <= N);
srand((unsigned) time(NULL));
for (i = 0; i < n; i++) { /* nota l'uso della n minuscola.. */
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;
assert(n <= N);
for (i = 0; i < n; i++) { /* come nella funzione prima.. n minuscolo nei cicli.. */
for (j = 0; j < n; j++) { printf("%d ", m[i][j]); }
printf("\n");
}
}
int main(void)
{
double p = 0.5;
matrice m;
genera_matrice(m, 4, p);
stampa_matrice(m, 4);
return 0;
}
Spero ti sia chiaro che cosa ho fatto, hai dubbi?
grazie si ho capito. volendo aggiungere al codice presente sopra gli in /out degree come va fatto? io l'ho fatto nel modo seguente però non mi funziona mi da errori nel void degrees(), come va fatto??
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
/* Definisco un nuovo tipo per le matrici.. */
#define N 10
typedef int matrice[N][N];
void degrees();
void genera_matrice(matrice m, size_t n, double p) {
size_t i = 0, j = 0;
assert(n <= N);
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;
assert(n <= N);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) { printf("%d ", m[i][j]); }
printf("\n");
}
}
void degrees()
{
int idegree,odegree;
int i,j;
for( i=0;i<n;i++)
{
idegree=odegree=0;
for(int j=0;j<n;j++)
{
if(m[i][j]!=0)
odegree++;
if(m[j][i]!=0)
idegree++;
}
printf("\nvertex : %d\tIndegree :%d\tOut degree:%d\tTotal Degree:%d",i,idegree,odegree,idegree+odegree);
}
}
int main(void)
{ int i,j;
double p = 0.5;
matrice m;
genera_matrice(m, 5, p);
stampa_matrice(m, 5);
degrees();
return 0;
}
La variabile n non è stata definita all'interno di degrees per cui immagino ti dia un errore di compilazione. Devi passare n come argomento alla funzione come negli altri casi. Per il resto mi sembra corretto, però credo sarebbe più utile restituire degli array contenenti gli in/out degree di ogni nodo (che andrebbero probabilmente anch'essi passati in modo simili alle matrici).
grazie ho corretto, in che modo praticamente?
Intendi dire come fare a restituire degli array? Direi che puoi scrivere qualcosa come il seguente:
/* anche la matrice la dovresti passare come argomento.. */
void degrees(matrice m, size_t n, int *indegrees, int *outdegrees)
{
size_t i = 0, j = 0;
/* inizializza arrays.. */
for (i = 0; i < n; ++i) { indegrees[i] = outdegrees[i] = 0; }
/* calcola gradi.. */
for (i = 0; i < n; ++i) {
for(j = 0; j < n; ++j) {
/* ricordandosi che m[i][j] è 0 o 1 si può semplicemente usare la somma ed evitare un inutile selezione. */
indegrees[j] += m[i][j];
outdegrees[i] += m[i][j];
}
}
}
mi da errore nel printf di void degrees cosa è?
void degrees(matrice m, size_t n, int *indegrees, int *outdegrees)
{
size_t i = 0, j = 0;
/* inizializza arrays.. */
for (i = 0; i < n; ++i) { indegrees[i] = outdegrees[i] = 0; }
/* calcola gradi.. */
for (i = 0; i < n; ++i) {
for(j = 0; j < n; ++j) {
/* ricordandosi che m[i][j] è 0 o 1 si può semplicemente usare la somma ed evitare un inutile selezione. */
indegrees[j] += m[i][j];
outdegrees[i] += m[i][j];
}
}
printf("\nvertici : %d\tIndegree :%d\tOut degree:%d\tDegree Totali:%d",i,indegrees,outdegrees,idegrees+odegrees);
}
int main(void)
{ int i,j;
double p = 0.5;
matrice m;
genera_matrice(m, 5, p);
stampa_matrice(m, 5);
degrees(m,5,indegrees,outdegrees);
return 0;
}
Ma non hai visto che l'avevo tolto? idegrees e odegrees non ci sono più come variabili nel codice che ti avevo scritto per cui anche il printf scritto così non ha senso. In generale le funzioni per la stampa e per fare i calcoli andrebbero sempre separate. Il main andrebbe cambiato nel seguente:
int main(void)
{ int i,j;
double p = 0.5;
size_t n = 5;
matrice m;
int indegrees[N], outdegrees[N];
genera_matrice(m, n, p);
stampa_matrice(m, n);
degrees(m, n, indegrees, outdegrees);
for (size_t i = 0; i < n; ++i) {
printf("\nvertice : %d\tIndegree :%d\tOut degree:%d\tDegree Totale:%d", i,
indegrees[i], outdegrees[i], indegrees[i] + outdegrees[i]);
}
return 0;
}
ok grazie,però da errore nella printf del main()
for (size_t i = 0; i < n; ++i) {
printf("\nvertice : %d\tIndegree :%d\tOut degree:%d\tDegree Totale:%d", i,
indegrees[i], outdegrees[i], indegrees[i] + outdegrees[i]);
}
Dovresti imparare a scrivere quale errore ti da.. non sto provando a compilare il codice..
dice in function main,conflicting types for i,previous declaration of i was here, for loop initial declaration used outside c99 mode
Sì, scusa.. non avevo visto che i e j erano stati definiti all'inizio del main. Ma quale compilatore stai usando? Cancella il size_t davanti a i nel ciclo.. e anche la variabile j all'inizio del main che non la stai usando..
ok funziona,dev c++. per quando riguarda la permutazione, deve prendere tutti i vertici del grafo fare tutte le possibili permutazioni e alla fine dire se c è o non c è un ciclo hamiltoniano.
Grafo G[]=Soluzione(cioè vettore,contiene la permutazione su come sono allineati i vertici di G).
n=numero di vertici di G.
K=ci dice il livello di permutazione(da 0 a n-1).
il codice deve essere fatto cosi è una bozza, però praticamente mi serve una mano:
Grafo G[]=Soluzione(cioè vettore,contiene la permutazione su come sono allineati i vertici di G).
n=numero di vertici di G.
K=ci dice il livello di permutazione(da 0 a n-1).
il codice deve essere fatto cosi è una bozza, però praticamente mi serve una mano:
permutazione(k){
int i;
if(k>n-1){
return;
}
for(i=0;i<n;i++){
if(Soluzione^-1[i]==0){
Soluzione[k]=i;
Soluzione^-1[i]=k;
}
}
permutazione(k+1){
Soluzione^-1[i]=n;
Soluzione[k]=0;
}
}
Per le permutazioni devi usare un array di supporto che ti servirà per accedere alle righe e alle colonne della matrice. Non mi è del tutto chiaro cosa dovrebbe fare quel codice..
me l'ha scritto il prof, la permutazione come la vuole lui diciamo che sembra uno pseudo codice. se ho capito bene lo scopo della funzione è prendere tutti i vertici del grafo fare tutte le possibili permutazioni e alla fine dire se c è o non c è un ciclo hamiltoniano. qual è il modo più semplice per farla praticamente??
questo codice va bene però si può modificare rendendolo più semplice come vuole il Prof, e applicarlo al codice che abbiamo scritto nei precedenti post???
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
void permutazioni(int*,int,int);
void permutazioni(int elementi[], int index,int dim) {
register int i,j;
int app;
if(index >= 1) {
for(i=index; i >= 0; i--) {
app=elementi[i];
elementi[i]=elementi[index];
elementi[index] = app;
permutazioni(elementi, index-1, dim);
app=elementi[i];
elementi[i]=elementi[index];
elementi[index] = app;
}
}
else {
for(j=0; j < dim; j++)
printf("%d", elementi[j]);
printf("\n");
}
}
int main() {
int* elementi;
int nElementi;
register int i;
printf("%s", "Inserire numero elementi ==> ");
scanf("%d", &nElementi);
elementi = (int*) malloc(sizeof(int) * nElementi);
for(i=0; i < nElementi; i++) {
printf("%s%d\n", "Inserire elemento ", i+1);
scanf("%d", &elementi[i]);
}
permutazioni(elementi, nElementi-1, nElementi);
#ifdef __WIN32
system("PAUSE");
#endif
}
ho scritto questa semplice permutazione però non mi funziona perchè manca qualcosa nel codice. mia aiutate a farlo funzionare???
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
/*genera tutte le permutazioni sui valori 0,1,...,n-1,
inizialmente k = -1 e val[i] = 0, per 0=i<n.
prec: vett != NULL && val != NULL;
*postc: stampa a video tutte le permutazioni su 0,1,...,n-1, memorizzate in vett.*/
//vett=un parametro di tipo vettore,di interi per la permutazione//
//n= Un parametro di tipo intero per la lunghezza del vettore vett//
//k=un parametro di tipo intero per la posizione corrente nella permutazione//
//val=un parametro di tipo vettore di interi per i valori già usati//
void genTPerm(int *vett,int k,int *val,unsigned int n){
int i;
if (k == n - 1){
stampaVett(vett,n);
}else{
for(i=0;i<n;i++){
if (val[i] == 0){
vett[k+1] = i;
val[i] = 1;
genTPerm(vett,k+1,val,n);
val[i] = 0;
}
}
}
}
int main(void){
int i;
int vett[i];
genTPerm(vett,-1,0, 3);
}
Che cosa devi farne di questa permutazione esattamente?
la devo portare al Prof
Il principale problema nell'usare una funzione sviluppata in quel modo è che devi scrivere il resto della logica del programma all'interno della tua funzione. Esistono algoritmi che ti permettono di generare la successiva permutazione rispetto all'ordine lessicografico che sono un po' più flessibili. Ma questo codice di fatto non ha nulla a che vedere con il resto.. Puoi metterli insieme senza alcun problema. Quello che manca è l'uso di tali permutazioni. Per cui, che cosa devi fare con ogni permutazione?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo