Discussion :

[Rykyu]

Bonjour,

Je développe (ou plutôt j'essaie) un petit programme pour faire des interpolations de Lagrange.

Du coup, j'ai fini par avoir besoin d'une fonction capable de générer des arrangements. Je lui envoie un tableau de X (ici nSize) nombres, je lui dis que je veux tous les arrangements de N (ici iP) dans X, et elle doit me renvoyer un tableau qui contient ces arrangements, ou plus précisément le produit des arrangements.

Pour être plus clair, voici l'exemple avec lequel je fais mes tests :
le tableau contient {1, 2, 3, 4} et je cherche à obtenir tous les arrangements de 3 nombres.
On en a donc quatre, à savoir {1, 2, 3}, {1, 2, 4}, {1, 3, 4} et {2, 3, 4}. Si l'on prend les produits, on obtient 6, 8, 12 et 24. Le programme est également supposé les sortir dans cet ordre.

Voilà donc j'ai fait une petite fonction permutation (j'ai pris le terme anglais, enfin il me semble) qui est récursive, sauf qu'à la ligne "free(tmp)", j'obtiens une erreur pour le dernier arrangement. Enfin le mieux est encore que vous le voyiez par vous-même, sachez juste que le bug est à la ligne du free. Si je l'enlève, le programme fonctionne et me sort fièrement 6, 8, 12 et 24.

La fonction rebelle :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
double* permutation(double nSamples[], int nSize, int nStart, int iP)
{
	int i, j, nRSize = nSize - nStart, rSize, tmpSize;
	double *result = NULL, *tmp = NULL;
 
	if(iP == 1)
	{
		rSize = nRSize;
		result = (double*)malloc(rSize * sizeof(double));
		for(i = 0 ; i < nRSize ; i++)
			result[i] = nSamples[i + nStart];
	}
	else
	{
		tmpSize = nRSize - 1;
		for(i = 2 ; i < iP ; i++)
			tmpSize *= nRSize - i;
		rSize = tmpSize * nRSize;
		tmpSize /= factorial(iP - 1);
		rSize /= factorial(iP);
		result = (double*)malloc(rSize * sizeof(double));
 
		for(i = 0 ; i < nRSize - iP + 1 ; i++)
		{
			tmp = permutation(nSamples, nSize, nStart + i + 1, iP - 1);
			for(j = 0 ; j < tmpSize ; j++)
			{
				result[(i * tmpSize) + j] = tmp[j] * nSamples[nStart + i];
			}
			free(tmp);
		}
	}
 
	return result;
}

La fonction de test :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
void test()
{
	double test[] = {1., 2., 3., 4};
	double *result = NULL;
	int i;
 
	result = permutation(test, 4, 0, 3);
 
	for(i = 0 ; i < 4; i++)
		printf("%f\n", result[i]);
}

L'erreur en question :

HEAP[lagrange.exe]: Invalid address specified to RtlValidateHeap( 00030000, 00031598 )
Windows a déclenché un point d'arrêt dans lagrange.exe.

Merci d'avance, ce soucis est assez pesant, notamment à cause du fait que j'ai bien passé 3h pour m'apercevoir que l'erreur venait du free...

[diogene]

1-
Sauf erreur de ma part, en posant Cnp(n,p) = n!/p!/(n-p)!
tmpSize = Cnp(nSize - nStart-1,iP-1)
et
rSize = Cnp(nSize - nStart,iP) (valable aussi pour iP==1)

Tu as alors intérêt pour la clarté et l'efficacité du code d'écrire la fonction Cnp() plutôt que la fonction factorial(). De plus, cette dernière croît très rapidement, beaucoup plus que Cnp() et si tu as des valeurs de n élevées, factorial() va dépasser la capacité d'un int ou d'un long.
Le plus simple est d'utiliser l'expression Cnp(n,p) = Cnp(n,p-1)*(n-p+1)/p (p!=0) avec Cnp(n,0) =1;
Par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
int Cnp(int n, int p)
{
  int c = 1;
  int i;
  for(i=1;i<=p;i++) c = c*(n-i+1)/i;
  return c;
}

Ton code (toujours avec l'erreur) devient plus clair (à mon goût) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
double* permutation(double nSamples[], int nSize, int nStart, int iP)
{
   int i, j, rSize, tmpSize;
   double *result, *tmp;
   int nRSize = nSize - nStart;
   rSize = Cnp (nRSize,iP);
   result = malloc(rSize * sizeof(double));
   if(iP == 1)
   {
      for(i = 0 ; i < nRSize ; i++) result[i] = nSamples[i + nStart];
   }
   else
   {
      tmpSize = Cnp(nRSize-1, iP-1);
      for(i = 0 ; i < nRSize - iP + 1 ; i++)
      {
         tmp = permutation(nSamples, nSize, nStart + i + 1, iP - 1);
         for(j = 0 ; j < tmpSize  ; j++)
            result[i * tmpSize + j] = tmp[j] * nSamples[nStart + i];
         free(tmp);
      }
   }
   return result;
}

2- Tu écris en dehors des tableaux alloués :

La fonction alloue et renvoie un tableau result[] de Cnp(nSize - nStart,iP) double.
Donc ici,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
tmp = permutation(nSamples, nSize, nStart + i + 1, iP - 1);
for(j = 0 ; j < tmpSize ; j++)
{
  result[(i * tmpSize) + j] = tmp[j] * nSamples[nStart + i];
}

la taille allouée pour tmp est de Cnp(nSize-nStart-i-1,iP-1) alors que j varie jusqu'à Cnp(nSize - nStart-1,iP-1)-1.
Donc, dès que i >0 , tu es hors du tableau tmp.

Il se produira la même chose pour result[] à un moment donné presque certainement. (Je ne comprend pas le tmpSize dans result[(i * tmpSize) + j])