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 :

Palindrome


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Profil pro
    Inscrit en
    Avril 2003
    Messages
    216
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Avril 2003
    Messages : 216
    Par défaut Palindrome
    Bonjour,

    Existe t-il une formule qui calcul les nombres palindrome ?

    Merci...

  2. #2
    Rédacteur

    Avatar de khayyam90
    Homme Profil pro
    Architecte de système d’information
    Inscrit en
    Janvier 2004
    Messages
    10 371
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Architecte de système d’information

    Informations forums :
    Inscription : Janvier 2004
    Messages : 10 371
    Par défaut Re: Palindrome
    Citation Envoyé par casafa
    Bonjour,

    Existe t-il une formule qui calcul les nombres palindrome ?

    Merci...
    bien le bonjour,

    qu'entends-tu par 'une formule' ? tu cherches un algo qui determine si un nombre donne est bien un nombre palindrome ? ou bien cherches-tu a obtenir tous les nombres palindromes compris en deux bornes ? carrement autre chose ?

  3. #3
    Membre confirmé
    Profil pro
    Inscrit en
    Avril 2003
    Messages
    216
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Avril 2003
    Messages : 216
    Par défaut
    Je cherche a obtenir tous les nombres palindromes compris entre 0 et n.

  4. #4
    Rédacteur

    Avatar de khayyam90
    Homme Profil pro
    Architecte de système d’information
    Inscrit en
    Janvier 2004
    Messages
    10 371
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Architecte de système d’information

    Informations forums :
    Inscription : Janvier 2004
    Messages : 10 371
    Par défaut
    et quel est le point qui te pose probleme ?

    le point 'delicat' de cet algo est de determiner si un nombre precis est palindrome ou pas. Une fois que cette fonction est ecrite, il suffit de boucler entre 0 et n.

    comment verrais-tu cet algo ?
    soumets-nous tes idees et on pourra t'aider

  5. #5
    Inactif   Avatar de Médiat
    Inscrit en
    Décembre 2003
    Messages
    1 946
    Détails du profil
    Informations forums :
    Inscription : Décembre 2003
    Messages : 1 946
    Par défaut
    Je partirais de la liste 0, 1, ..., 9 baptisée S1; s'ils sont considérés comme des palindromes, on les conserve dans la liste.

    Puis de la liste 11, 22, ... 99 (baptisée S2)

    à partir de la liste S2n on peut créer des palindromes en ajoutant n'importe quel élément de S1 au milieu, ce qui fabrique la liste S2n+1
    à partir de la liste S2n on peut créer des palindrome en ajoutant n'importe quel palindrome de la liste S2 + {00} au milieu, ce qui fabrique la liste S2(n+1)

    On élimine à chaque tour les nombres > limite.
    On boucle jusque'à ce que le plus petit palindrome fabriqué soit plus grand que la limite.

    [Edit] J'avais oublié d'ajouter le 00[/Edit]

  6. #6
    Membre chevronné Avatar de xxiemeciel
    Inscrit en
    Juin 2005
    Messages
    371
    Détails du profil
    Informations forums :
    Inscription : Juin 2005
    Messages : 371
    Par défaut
    Salut,

    moi je verifierais que le nombre a l'envers est egal au nombre a l'endroit

    ou l'inverse serait : envers(123) = 321
    donc pour un palindrome ca donne envers(919) = 919

    puis tu parcours 0 a n

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    pour i de 0 a n :
        si envers(i) == i:
              //palindrome
        sinon
              // pas palindrome
    XXiemeciel

  7. #7
    Expert confirmé
    Avatar de Baptiste Wicht
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2005
    Messages
    7 431
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : Suisse

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Octobre 2005
    Messages : 7 431
    Par défaut
    J'ai realisé cela en java et je m'y connais pas trop en algorythme, donc je vais essayer de t'expliquer comment je m'y suis pris :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
    pour chaque i de a à b
        pour chaque chiffre dans i de o jusqu'au nombre de chiffres de i
               on met le premier chiffre dans une chaine 1
               on met le dernier chiffre dans une chaine 2
     
        si chaine 1 = chaine 2
                on stocke le i dans un tableau
                on change l'index du tableau
    ensuite on arrivera donc à un tableau contenant tout les palindromes entre a et b dans l'ordre croissant

  8. #8
    Inactif   Avatar de Médiat
    Inscrit en
    Décembre 2003
    Messages
    1 946
    Détails du profil
    Informations forums :
    Inscription : Décembre 2003
    Messages : 1 946
    Par défaut
    Etudier tous les nombres pour vérifier si ce sont des palindromes si n = 999999999, cela fait 1 milliard de vérifications, alors qu'il y a que 100 000 palindromes à générer !

  9. #9
    Membre chevronné Avatar de xxiemeciel
    Inscrit en
    Juin 2005
    Messages
    371
    Détails du profil
    Informations forums :
    Inscription : Juin 2005
    Messages : 371
    Par défaut
    Salut,

    Oui tu as raison Mediat, je proposais juste un algo plus simple au cas ou.

    Sinon ton algo m'a l'air tres bon.

    XXiemeciel

  10. #10
    Membre Expert
    Avatar de méphistopheles
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    1 551
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 1 551
    Par défaut
    Citation Envoyé par Médiat
    Je partirais de la liste 0, 1, ..., 9 baptisée S1; s'ils sont considérés comme des palindromes, on les conserve dans la liste.

    Puis de la liste 11, 22, ... 99 (baptisée S2)

    à partir de la liste S2n on peut créer des palindromes en ajoutant n'importe quel élément de S1 au milieu, ce qui fabrique la liste S2n+1
    tu veut dire la liste S1n+1 non?

  11. #11
    Inactif   Avatar de Médiat
    Inscrit en
    Décembre 2003
    Messages
    1 946
    Détails du profil
    Informations forums :
    Inscription : Décembre 2003
    Messages : 1 946
    Par défaut
    Non, c'est bien S2n+1 :

    S1 = 0;1;2;...;9
    S2 = 11;22;33...;99
    S3 =101;111;121...;191; 202; 212;...999
    S4 = 1001;1111; 1221; 1331;... 2002;2112;2222; 9999

    etc.
    S2n ¤ S1 = S2n+1
    S2n ¤ (S2+00) = S2(n+1)

  12. #12
    Inactif   Avatar de Médiat
    Inscrit en
    Décembre 2003
    Messages
    1 946
    Détails du profil
    Informations forums :
    Inscription : Décembre 2003
    Messages : 1 946
    Par défaut
    On peut aussi créer les palindromes brutalement :

    Soit n le nombre de chiffres maxi

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    Pour i = 1 à n
      on génère tous les nombres de floor(i/2) chiffres ne commençant pas par 0.
      si i est pair on fabrique 1 palindrome en écrivant à la suite les mêmes chiffres, mais à l'envers
      si i est impair, on génère 10 palindromes en insérant entre les deux chaines l'un des chiffres de 0 à 9
    Fin pour
    Exemple si n = 1
    i = 1, floor(i/2) = 0 on génère : vide[0 à 9]vide, c'est à dire les nombres de 0 à 9

    n = 2
    i = 1, floor(i/2) = 0 on génère : vide[0 à 9]vide, c'est à dire les nombres de 0 à 9
    i = 2, floor(i/2) = 1 on génère : [1 à 9][9 à 1], c'est à dire les nombres 11,22,...99

    n = 3
    i = 1, floor(i/2) = 0 on génère : vide[0 à 9]vide, c'est à dire les nombres de 0 à 9
    i = 2, floor(i/2) = 1 on génère : [1 à 9][9 à 1], c'est à dire les nombres 11,22,...99
    i = 3, floor(i/2) = 1 on génère : [1 à 9][0 à 9][9 à 1], c'est à dire les nombres 101,111, ...191, 202, 212, 292...909, ...999

    etc...

Discussions similaires

  1. Palindrome
    Par zouyou dans le forum C++
    Réponses: 18
    Dernier message: 05/05/2010, 01h28
  2. nombre palindrome
    Par nemesis00 dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 10/04/2006, 10h50
  3. Tester si un mot est palindrome
    Par imeys dans le forum Langage
    Réponses: 2
    Dernier message: 22/11/2005, 15h03
  4. palindrome
    Par devdébuto dans le forum C
    Réponses: 6
    Dernier message: 17/11/2005, 22h53
  5. [Debutant] Programme de test de palindrome
    Par lala_ dans le forum Assembleur
    Réponses: 5
    Dernier message: 13/02/2005, 15h48

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