Originariamente inviato da franceskaaaz
Questo codice mi calcola ricorsivamente le permutazioni di N elementi ma non in ordine casuale??
Il codice in Java aveva il limite che non potevo vedere ogni permutazione,
ossia io vorrei che per ogni permutazione del vettore mi facesse questo calcolo:
A partire dal terzo elemento, per ogni elemento bisogna considerare il quadrato della differenza fra l'elemento stesso e l'elemento che lo precede, sommata alla metà del quadrato della differenza fra l'elemento stesso e l'elemento che lo precede di due posizioni.
E' troppo complicato, vero?
Non è complicato. Puoi organizzare il codice in modo che, invece di stampare le permutazioni, la funzione ricorsiva richiami una funzione callback nella quale effettui tutti i calcoli e i controlli che vuoi.
L'esempio precedente, modificato con l'uso di una funzione callback(onChange) diventa:
codice:
/* http://www.cs.utsa.edu/~dj/ut/utsa/c...lecture25.html */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* function to swap array elements */
void swap (int v[], int i, int j)
{
int t;
t = v[i];
v[i] = v[j];
v[j] = t;
}
void onChange(int a[], int v[], int n)
{
int j;
for (j = 0; j < n; j++)
printf ("%d ", a[v[j]]);
printf ("\n");
}
/* recursive function to generate permutations */
void perm (int a[], int v[], int n, int i, void (*pfnOnChange)(int a[], int v[], int n))
{
/* this function generates the permutations of the array
* from element i to element n-1
*/
int j;
int t;
/* if we are at the end of the array, we have one permutation
* we can use (here we print it; you could as easily hand the
* array off to some other function that uses it for something
*/
if (i == n)
{
if ( pfnOnChange )
pfnOnChange(a, v, n);
/*
for (j = 0; j < n; j++)
printf ("%d ", v[j]);
printf ("\n");
*/
}
else
{
/* recursively explore the permutations starting
* at index i going through index n-1
*/
for (j = i; j < n; j++)
{
/* try the array with i and j switched */
/* swap (v, i, j); */
t = v[i];
v[i] = v[j];
v[j] = t;
perm (a, v, n, i+1, pfnOnChange);
/* swap them back the way they were */
/* swap (v, i, j); */
t = v[i];
v[i] = v[j];
v[j] = t;
}
}
}
/* little driver function to print perms of first 5 integers */
int main(/*int argc, char *argv[]*/)
{
clock_t c_start, c_end;
double TempoImpiegato;
int *a;
int *v;
int N;
int i;
N = 4;
a = (int*)calloc(N + 1, sizeof(int));
if ( !a )
{
printf("Error: insufficient memory.\n");
return -1;
}
a[0] = 0;
a[1] = 5;
a[2] = 8;
a[3] = 13;
a[4] = 21;
v = (int*)calloc(N + 1, sizeof(int));
if ( !v )
{
printf("Error: insufficient memory.\n");
free(a);
return -1;
}
for (i = 0; i < N; i++)
v[i] = i+1;
c_start = clock();
perm (a, v, N, 0, onChange);
c_end = clock();
TempoImpiegato = (double)(c_end - c_start) / CLOCKS_PER_SEC;
printf("Tempo impiegato -> %5.5f secondi\n\n", TempoImpiegato);
free(v);
return 0;
}
Rispondi quotando
