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

Mathématiques Discussion :

algorithme pour suite cyclique


Sujet :

Mathématiques

  1. #1
    Membre régulier

    Inscrit en
    Août 2007
    Messages
    308
    Détails du profil
    Informations forums :
    Inscription : Août 2007
    Messages : 308
    Points : 100
    Points
    100
    Billets dans le blog
    1
    Par défaut algorithme pour suite cyclique
    Bonjour à tous,

    Je voudrai ecrire un algorithme qui me dit si une suite de termes est cylique
    sans utiliser des tableaux pour stocker les termes de la suite.
    par exemple: la suite 2, 9, 20, 12, 3, 5, 8, 20, 12, 3, 5, 8.... est cyclique
    est-ce possible?

  2. #2
    Expert éminent

    Profil pro
    Fabricant et casseur d'avions
    Inscrit en
    Avril 2004
    Messages
    3 807
    Détails du profil
    Informations personnelles :
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : Fabricant et casseur d'avions
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Avril 2004
    Messages : 3 807
    Points : 7 613
    Points
    7 613
    Par défaut
    Salut,

    Citation Envoyé par nina2007 Voir le message
    sans utiliser des tableaux pour stocker les termes de la suite.
    Et tu les stockes dans quoi tes termes pour appliquer l'algorithme???
    Une pile, tu considères ça comme un tableau ou pas?

    Cela dit, parler de tableau dans un algo, c'est un peu introduire des notions de langage informatique... ça ne se fait pas!

    Je présume que les algos de détection de cycle (genre lièvre et tortue...) ne te conviennent pas donc...
    "Errare humanum est, sed perseverare diabolicum"

    Ma page sur DVP.com

  3. #3
    Membre régulier

    Inscrit en
    Août 2007
    Messages
    308
    Détails du profil
    Informations forums :
    Inscription : Août 2007
    Messages : 308
    Points : 100
    Points
    100
    Billets dans le blog
    1
    Par défaut
    merci pour votre réponse...
    mais j'ai pas besoin de stocker les termes de la suite, je peux juste les afficher seulement

    j'ai une idée: dites-moi si c'est faisable
    utiliser deux boucles imbriquées
    calculer le terme U_i et recalculer les termes de U_1 à U_(i-1)
    si U_i = à l'un des termes déjà calculés alors la suite est cylique

    je pense que ça marche, dites-le moi si je me trompe ou y a t-il une meilleur idée?
    merci

  4. #4
    Membre expert
    Avatar de kwariz
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    Octobre 2011
    Messages
    898
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet en SSII
    Secteur : Conseil

    Informations forums :
    Inscription : Octobre 2011
    Messages : 898
    Points : 3 352
    Points
    3 352
    Par défaut
    Citation Envoyé par nina2007 Voir le message
    merci pour votre réponse...
    mais j'ai pas besoin de stocker les termes de la suite, je peux juste les afficher seulement

    j'ai une idée: dites-moi si c'est faisable
    utiliser deux boucles imbriquées
    calculer le terme U_i et recalculer les termes de U_1 à U_(i-1)
    si U_i = à l'un des termes déjà calculés alors la suite est cylique

    je pense que ça marche, dites-le moi si je me trompe ou y a t-il une meilleur idée?
    merci
    Bonjour,

    oui ton algo fonctionnera, mais il n'est pas optimal. Dans ton cas tu peux adapter l'algo du lièvre et de la tortue (ou moins poétiquement l'algorithme de Floyd de détection de cycle). La page wiki décrit tout ça pas trop mal : Algorithme du lièvre et de la tortue. S'il y a un cycle il le trouve, sinon il boucle ... j'espère que soit tu es sure d'avoir un cycle ou il faudra lui donner une longueur max de cycle.

  5. #5
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par kwariz Voir le message
    Dans ton cas tu peux adapter l'algo du lièvre et de la tortue (ou moins poétiquement l'algorithme de Floyd de détection de cycle). La page wiki décrit tout ça pas trop mal : Algorithme du lièvre et de la tortue. S'il y a un cycle il le trouve, sinon il boucle ... j'espère que soit tu es sure d'avoir un cycle ou il faudra lui donner une longueur max de cycle.
    Cela ne marche que pour une suite de valeurs provenant d'une fonction itérée. En d'autre terme, ca ne marche que si la valeur suivante dans le suite ne dépend que de la valeur actuelle: A[i+1] = f( A[i] ).

    Pour ce cas là, ce n'est pas applicable:
    1,2,1,3,1,4,1,5,1,6, 1,5,1,6, 1,5,1,6 1,5,1,6, ...
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  6. #6
    Membre émérite
    Avatar de prgasp77
    Homme Profil pro
    Ingénieur en systèmes embarqués
    Inscrit en
    Juin 2004
    Messages
    1 306
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Ingénieur en systèmes embarqués
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : Juin 2004
    Messages : 1 306
    Points : 2 466
    Points
    2 466
    Par défaut
    Le problème est particulièrement difficile, car il faut d'une part déterminer quelle est la période de l'éventuel cycle, mais aussi la position du premier cycle. Ces deux valeurs peuvent être arbitrairement grandes.

    Une astuce pourrait être de « partir de la fin » de la séquence, si celle-ci en a une (on fait de l'informatique après tout). Dans ce cas favorable, il n'y aurait plus que la période à déterminer. Et cela est bien plus simple.

    Peut-on avoir quelques informations supplémentaires sur la source des données ?

    Cdlt,
    -- Yankel Scialom

  7. #7
    Membre régulier

    Inscrit en
    Août 2007
    Messages
    308
    Détails du profil
    Informations forums :
    Inscription : Août 2007
    Messages : 308
    Points : 100
    Points
    100
    Billets dans le blog
    1
    Par défaut
    merci pours vos commentaires

    Je vous donne plus de précisions
    la suite d'entiers est construite mathématiquement :
    U_n+1 est est égale à la somme des carrés des chiffres de U_n
    exemple: si U_i=56 alors U_i+1=61

    Alors ma solution marche toujours?

  8. #8
    Membre régulier

    Inscrit en
    Août 2007
    Messages
    308
    Détails du profil
    Informations forums :
    Inscription : Août 2007
    Messages : 308
    Points : 100
    Points
    100
    Billets dans le blog
    1
    Par défaut
    exemple: $U_0=12$, $U_1=5$, $U_2=25$, $U_3=29$, $U_4=85$, $U_5=89$, $U_6=145$,
    $U_7=42$,
    $U_8=20$, $U_9=4$, $U_{10}=16$, $U_{11}=37$, $U_{12}=58$, $U_{13}=89$,
    $U_{14}=145$, $U_{15}=42$,... est une suite cyclique.

  9. #9
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par nina2007 Voir le message
    merci pours vos commentaires

    Je vous donne plus de précisions
    la suite d'entiers est construite mathématiquement :
    U_n+1 est est égale à la somme des carrés des chiffres de U_n
    exemple: si U_i=56 alors U_i+1=61

    Alors ma solution marche toujours?
    On est typiquement dans une fonction itérée: U_i+1 dépend seulement de U_i.
    L'algo de Floyd, ou ton algo de recherche exhaustive fonctionnent.

    A noter que cette suite est celle des "happy/sad numbers". Elle est soit convergente (vers 1), soit cyclique (longueur 4), suivant la valeur du 1er élément.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  10. #10
    Membre régulier

    Inscrit en
    Août 2007
    Messages
    308
    Détails du profil
    Informations forums :
    Inscription : Août 2007
    Messages : 308
    Points : 100
    Points
    100
    Billets dans le blog
    1
    Par défaut
    merci

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Algorithme pour suite.
    Par fred61 dans le forum Débuter
    Réponses: 7
    Dernier message: 19/11/2013, 16h31
  2. algorithme pour calcul de probabilité
    Par filsdugrand dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 14/12/2005, 15h11
  3. Quel algorithme pour insertion d'objets "triés" da
    Par phplive dans le forum Langage
    Réponses: 3
    Dernier message: 04/08/2005, 10h27
  4. Algorithme pour trier trois nombres
    Par legosam dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 17/01/2005, 22h47
  5. Algorithme pour chiffres significatifs en Assembleur
    Par lutin2003 dans le forum Assembleur
    Réponses: 5
    Dernier message: 09/09/2004, 11h47

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