Soutenez-nous
Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 10 sur 10
  1. #1
    Membre du Club
    Inscrit en
    août 2007
    Messages
    223
    Détails du profil
    Informations forums :
    Inscription : août 2007
    Messages : 223
    Points : 47
    Points
    47

    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 Confirmé Sénior

    Profil pro Jean-Michel BORLOT
    Fabricant et casseur d'avions
    Inscrit en
    avril 2004
    Messages
    3 404
    Détails du profil
    Informations personnelles :
    Nom : Jean-Michel BORLOT
    Localisation : France, Haute Garonne (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 404
    Points : 5 579
    Points
    5 579

    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 du Club
    Inscrit en
    août 2007
    Messages
    223
    Détails du profil
    Informations forums :
    Inscription : août 2007
    Messages : 223
    Points : 47
    Points
    47

    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
    Expert Confirmé

    Homme Profil pro Fred Kwariz
    Chef de projet en SSII
    Inscrit en
    octobre 2011
    Messages
    888
    Détails du profil
    Informations personnelles :
    Nom : Homme Fred Kwariz
    Âge : 41
    Localisation : France, Moselle (Lorraine)

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

    Informations forums :
    Inscription : octobre 2011
    Messages : 888
    Points : 3 135
    Points
    3 135

    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/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 962
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 962
    Points : 15 080
    Points
    15 080

    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 Expert Avatar de prgasp77
    Homme Profil pro Yankel Scialom
    Ingénieur en systèmes embarqués
    Inscrit en
    juin 2004
    Messages
    1 084
    Détails du profil
    Informations personnelles :
    Nom : Homme Yankel Scialom
    Âge : 27
    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 084
    Points : 1 410
    Points
    1 410

    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,

  7. #7
    Membre du Club
    Inscrit en
    août 2007
    Messages
    223
    Détails du profil
    Informations forums :
    Inscription : août 2007
    Messages : 223
    Points : 47
    Points
    47

    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 du Club
    Inscrit en
    août 2007
    Messages
    223
    Détails du profil
    Informations forums :
    Inscription : août 2007
    Messages : 223
    Points : 47
    Points
    47

    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/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 962
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 962
    Points : 15 080
    Points
    15 080

    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 du Club
    Inscrit en
    août 2007
    Messages
    223
    Détails du profil
    Informations forums :
    Inscription : août 2007
    Messages : 223
    Points : 47
    Points
    47

    Par défaut

    merci

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

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •