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
ok grazie funziona
Poi mi chiede sia n che va da n1 a n-1, per un certo numero di grafi di dimensione n,per P che va da 1 a (logn)/n-1 genera Gp(ovvero un grafo casuale)di matrice adiacente Ai:
-Calcola il ciclo(ad esempio con una procedura ricorsiva di Permuta()), poi aggiunge le stime statistiche e stampe queste statistiche per la dimensione n.
Come si fa?? non so nemmeno da dove partire
-Calcola il ciclo(ad esempio con una procedura ricorsiva di Permuta()), poi aggiunge le stime statistiche e stampe queste statistiche per la dimensione n.
Come si fa?? non so nemmeno da dove partire
A grandi linee si tratta di scrivere tre cicli annidati, ognuno dei quali cambia uno dei valori del parametro. Ma c'è una ragione per cui vuole che tu faccia uso del C? Sarebbe molto più semplice in altri linguaggi..
non lo so perchè è fissato con il C infatti all 'uni non l'abbiamo fatto. come procediamo ?
questa procedura ricorsiva di permuta va bene per il nostro caso ???
/* ================================================================= */
/* permuta <valore>... */
/* Permutazioni. */
/* ================================================================= */
#include <stdio.h>
#include <stdlib.h>
/* Variabile globale. */
int iDimArray;
/* ================================================================= */
/* visualizza (<array>, <dimensione>) */
/* ----------------------------------------------------------------- */
void visualizza (int lista[], int dimensione)
{
int i;
for (i = 0; i < dimensione; i++)
{
printf ("%d ", lista[i]);
}
printf ("\n");
}
/* ================================================================= */
/* permuta (<lista>, <inizio>, <fine>) */
/* ----------------------------------------------------------------- */
void permuta (int lista[], int a, int z)
{
int scambio;
int k;
/* Se il segmento di array contiene almeno due elementi, si */
/* procede. */
if ((z - a) >= 1)
{
/* Inizia un ciclo di scambi tra l'ultimo elemento e uno */
/* degli altri contenuti nel segmento di array. */
for (k = z; k >= a; k--)
{
/* Scambia i valori. */
scambio = lista[k];
lista[k] = lista[z];
lista[z] = scambio;
/* Esegue una chiamata ricorsiva per permutare un */
/* segmento più piccolo dell'array. */
permuta (lista, a, z-1);
/* Scambia i valori. */
scambio = lista[k];
lista[k] = lista[z];
lista[z] = scambio;
}
}
else
{
/* Visualizza l'array e utilizza una variabile dichiarata */
/* globalmente. */
visualizza (lista, iDimArray);
}
}
/* ================================================================= */
/* Inizio del programma. */
/* ----------------------------------------------------------------- */
int main (int argc, char *argv[])
{
/* int lista[argc-1]; */
int *lista = (int *) malloc ((argc - 1) * sizeof (int));
int i;
/* Considera gli argomenti come gli elementi */
/* dell'array da permutare. */
for (i = 1; i < argc; i++)
{
sscanf (argv[i], "%d", &lista[i-1]);
}
/* Salva la dimensione dell'array nella variabile globale. */
iDimArray = argc-1;
/* Esegue le permutazioni. */
permuta (lista, 0, argc-2);
return 0;
}
oppure va bene questo tipo di permutazioni???
#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
}
Ma dove stai prendendo questi codici? Immagino vadano bene (dovrei studiarli più a fondo di quanto abbia tempo di fare adesso), ma credo che il problema sia più che altro in come devi usarli.. Secondo me dovresti partire dallo scrivere una specie di scheletro a grandi linee di come dovrebbe funzionare il tuo codice lasciando l'implementazione delle funzione che ti servono per ora vuote. Oppure, visto che hai problemi con il C, perché non provi a scrivere tutto in un altro linguaggio (hai mai programmato in qualche linguaggio?) o pseudocodice che poi lo traduciamo?
utilizzavo java, e lo scheletro come lo impostiamo??
Come scriveresti a grandi linee in Java quello che ti ha chiesto il professore di scrivere? Diciamo di iniziare dal main e dai per scontato di avere tutte le classi che vuoi e di cui pensi di aver bisogno..
come prima cosa devo generare i grafi casuali,una volta fatto questo usare la procedura delle permute e poi infine stampare questi risultati
E come lo scriveresti in Java? Ci preoccupiamo poi dopo di convertirlo in C..
per generare un grafo vedi se va bene:
public Integer[][] matrix_generator ( int n ) {
this.matrix = new Integer[n][n];
for (int righe = 0; righe < n ; righe ++){
for (int colonne = 0; colonne < n ; colonne ++){
this.matrix[righe][colonne] = (int)(Math.random());
}
}
}
return this.matrix;
}
per le permute ho trovato questo perchè non so come farlo:
public class Permutation {
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
int[] a = new int[N];
// insert integers 0..N-1
for (int i = 0; i < N; i++)
a[i] = i;
// shuffle
for (int i = 0; i < N; i++) {
int r = (int) (Math.random() * (i+1)); // int between 0 and i
int swap = a[r];
a[r] = a[i];
a[i] = swap;
}
// print permutation
for (int i = 0; i < N; i++)
System.out.print(a[i] + " ");
System.out.println("");
// print checkerboard visualization
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (a[j] == i) System.out.print("* ");
else System.out.print(". ");
}
System.out.println("");
}
}
}
per le permute è in maniera ricorsiva ho trovato anche questo ed ho l'eseguibile anche in C:
import java.io.*;
public class permutation {
public static void main(String args[]) throws IOException{
String str;
System.out.println("Enter the initial string");
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
str=br.readLine();
System.out.println("Permutations are :");
permute("", str);
}
public static void permute(String beginningString, String endingString) {
if (endingString.length() <= 1)
System.out.println(beginningString + endingString);
else
for (int i = 0; i < endingString.length(); i++) {
try {
String newString = endingString.substring(0, i) + endingString.substring(i + 1);
permute(beginningString + endingString.charAt(i), newString);
} catch (StringIndexOutOfBoundsException exception) {
exception.printStackTrace();
}
}
}
}
va bene il codice che ho messo?? come facciamo ad implementare il tutto?
Sinceramente speravo che in Java seguissi un approccio un po' meno basato sul copia-incolla..
perchè non capisco molto come farlo praticamente
Questo è chiaro, ma sarebbe importante se cercassi invece di capire come farlo.. La matrice di adiacenza che devi generare è semplicemente una matrice \(n \times n\) che contiene solo valori 0 e 1 e in cui la probabilità di avere un uno in una qualsiasi posizione della matrice è \(p\). In linguaggi come matlab dovresti semplicemente scrivere
In un linguaggio come il C o Java devi scrivere due cicli annidati in cui per ogni elemento generi un valore casuale e lo confronti con p per sapere se scrivere un uno o uno zero. Il codice che hai scritto in Java non fa però questo.
Per le permutazioni devi prima di tutto capire che cosa devi realmente fare.. Tu stai generando una permutazione dell'insieme \(\{1, \dotsc, n\},\) ma che cosa dovresti farne di questa permutazione? Se non sai rispondere a questa domanda è inutile cercare di implementare tale funzione. Il fatto che il tuo professore abbiamo poi parlato di una implementazione ricorsiva non significa che non sia possibile implementarlo diversamente. Ma se invece di porti domande ti butti su google a cercare quello che credi di dover fare non credo arriveremo molto avanti.
n = 3; p = 0.5; % valori a caso.. A = rand(n) < p;
In un linguaggio come il C o Java devi scrivere due cicli annidati in cui per ogni elemento generi un valore casuale e lo confronti con p per sapere se scrivere un uno o uno zero. Il codice che hai scritto in Java non fa però questo.
Per le permutazioni devi prima di tutto capire che cosa devi realmente fare.. Tu stai generando una permutazione dell'insieme \(\{1, \dotsc, n\},\) ma che cosa dovresti farne di questa permutazione? Se non sai rispondere a questa domanda è inutile cercare di implementare tale funzione. Il fatto che il tuo professore abbiamo poi parlato di una implementazione ricorsiva non significa che non sia possibile implementarlo diversamente. Ma se invece di porti domande ti butti su google a cercare quello che credi di dover fare non credo arriveremo molto avanti.
ho scritto in C questo pezzo di codice però mi genera una matrice con tutti elementi 0.Come va aggiustata?
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define RIGHE 4
#define COLONNE 4
#define MAX 50
void genera_matrice(int m[RIGHE][COLONNE], double p) {
int i, j;
srand((unsigned) time(NULL));
for (i=0; i<RIGHE; i++)
for (j=0; j<COLONNE; j++)
m[i][j] = rand() < p ;
return;
}
void stampa_matrice(int m[RIGHE][COLONNE]) {
int i, j;
for (i=0; i<RIGHE; i++) {
for (j=0; j<COLONNE; j++)
printf("%d ", m[i][j]);
printf("\n");
}
return;
}
int main(void) {
double p = 0.5;
int m[RIGHE][COLONNE];
genera_matrice(m,p);
stampa_matrice(m);
}
Siccome la dimensione della matrice deve variare nel tuo programma non puoi usare delle costanti per le dimensioni della matrice e non puoi quindi usare le matrici bidimensionali. In ogni caso in quel codice dovresti piuttosto scrivere qualcosa come
perché rand restituisce un numero intero compreso tra 0 e RAND_MAX. Siccome p è minore di 1, quel codice restituisce 1 solo quando rand() restituisce zero (evento abbastanza raro). In realtà non c'è in effetti alcuna garanzia che restituisca 1 se non sbaglio nel C (ma forse non ha alcuna importanza). quindi il codice corretto dovrebbe essere:
o qualcosa del genere (usando un if ad esempio).
rand() < p*RAND_MAX
perché rand restituisce un numero intero compreso tra 0 e RAND_MAX. Siccome p è minore di 1, quel codice restituisce 1 solo quando rand() restituisce zero (evento abbastanza raro). In realtà non c'è in effetti alcuna garanzia che restituisca 1 se non sbaglio nel C (ma forse non ha alcuna importanza). quindi il codice corretto dovrebbe essere:
m[i][j] = (rand() < p*RAND_MAX) ? 1 : 0;
o qualcosa del genere (usando un if ad esempio).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo