IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Problème d'algorithmique (itératif)


Sujet :

Algorithmes et structures de données

  1. #1
    Membre averti
    Homme Profil pro
    Inscrit en
    Mars 2011
    Messages
    20
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Mars 2011
    Messages : 20
    Par défaut 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.

  2. #2
    Membre Expert
    Avatar de Franck Dernoncourt
    Homme Profil pro
    PhD student in AI @ MIT
    Inscrit en
    Avril 2010
    Messages
    894
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : PhD student in AI @ MIT
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2010
    Messages : 894
    Par défaut
    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

  3. #3
    Membre averti
    Homme Profil pro
    Inscrit en
    Mars 2011
    Messages
    20
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Mars 2011
    Messages : 20
    Par défaut
    Merci pour ta correction. Effectivement il y a 11 valeurs possibles.
    Je vais regarder ce que tu m'as conseillé.
    Merci!

  4. #4
    Membre Expert
    Avatar de Franck Dernoncourt
    Homme Profil pro
    PhD student in AI @ MIT
    Inscrit en
    Avril 2010
    Messages
    894
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : PhD student in AI @ MIT
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2010
    Messages : 894
    Par défaut 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 C++ : Sélectionner tout - Visualiser dans une fenêtre à part
    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);
    }

Discussions similaires

  1. Un Problème d'Algorithmique
    Par theUgk dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 24/04/2012, 10h27
  2. problème exercice algorithmique
    Par chicabonux dans le forum Débuter
    Réponses: 37
    Dernier message: 25/02/2009, 16h55
  3. problème d'algorithmique et recherche de mots
    Par Jasmine80 dans le forum Langage
    Réponses: 0
    Dernier message: 28/11/2007, 14h50
  4. probléme en algorithmique
    Par zicoadis dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 23/10/2007, 16h59
  5. Problème en Algorithmique
    Par psychoman dans le forum Mathématiques
    Réponses: 30
    Dernier message: 17/09/2007, 11h37

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo