Problème d'algorithmique (itératif)

Version imprimable

28/03/2011, 18h19
guadock

Problème d'algorithmique (itératif)

Bonjour à tous.
J'ai un petit souci car je ne trouve pas un algorithme qui ne doit pourtant pas etre si compliqué.
Le problème est le suivant:
J'ai un nombre N de variables qui peuvent prendre chacune un certain nombre de valeur.
Par exemple la 1ere variable varie entre Min = 0 et Max = 10 avec un pas de 1. Cette variable va donc prendre 10 valeurs.

Je dois afficher les résultats d'une fonction appliquée sur l'ensemble des N-uplét possibles. IE: s'il existe une combinaison possible de variable alors le résultat de la fonction appliquée à cette combinaison doit etre affiché.

Cela peut parraitre simple. Mais je dois en fait construire un algorithme générique (dynamique) car je ne connais pas par avance le nombre de variable.

J'ai pensé à un algorithme récursif mais je n'ai pas le droit d'en utiliser.

Merci d'avance pour votre aide.
28/03/2011, 19h27
Franck Dernoncourt
Citation:

la 1ere variable varie entre Min = 0 et Max = 10 avec un pas de 1. Cette variable va donc prendre 10 valeurs.

11 :)

Google "combinatorial algorithms".

Un algo intuitif serait de boucler sur i=0 to 11^N, de prendre a[0] = i % 11 pour le premier, a[k] = ((i - a[k-1]) / 11) % 11 avec :
- N ton nombre de variables
- k entre 1 et 11.
- a ton n-uplet
29/03/2011, 10h36
guadock

Merci pour ta correction. Effectivement il y a 11 valeurs possibles.
Je vais regarder ce que tu m'as conseillé.
Merci!

Code C++

Tiens par hasard je viens de devoir programmer cela en C++, j'ai pris un autre algo qui me passait par la tête (je n'ai pas besoin de l'optimiser), voici le code si intéressé :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
std::vector<std::vector<int> > all_tuples;
std::vector<int> a(N);
int number_of_values = Max - Min + 1;
int number_of_tuples = pow(number_of_values,N);
for (int i = 0; i < number_of_tuples; ++i) {
	std::vector<int> a(N);
	std::fill(a.begin(), a.end(), 0);
	for (int cursor = 0; cursor < N; ++cursor) {
		a[cursor] = ((int)(floor(i / pow(number_of_values,cursor))) % number_of_values));
	}
	all_tuples.push_back(a);
}